1462 lines
70 KiB
Typst
1462 lines
70 KiB
Typst
#set page(
|
||
paper: "a4",
|
||
margin: (y: 30mm, inside: 35mm, outside: 25mm),
|
||
)
|
||
|
||
#set par(justify: false)
|
||
#set text(size: 12pt, font: "Calibri", hyphenate: false)
|
||
|
||
#show heading: set text(size: 12pt, weight: "regular")
|
||
#show heading.where(level: 1): set text(size: 18pt, weight: "bold")
|
||
#show heading.where(level: 2): set text(size: 16pt)
|
||
#show heading.where(level: 3): set text(size: 14pt)
|
||
|
||
#set math.equation(numbering: "(1)")
|
||
|
||
|
||
#let leading = 1.5em // Your line spacing (1, 1.5, 2, etc.)
|
||
#let leading = leading - 0.75em // "Normalization"
|
||
#set par(leading: leading)
|
||
|
||
#show figure.where(kind: raw): set figure(kind: image, supplement: [Slika])
|
||
#show figure.where(kind: image): set figure(supplement: [Slika])
|
||
#show figure.where(kind: table): set figure(supplement: [Tabela])
|
||
#set heading(numbering: "1.1", supplement: [Poglavje])
|
||
|
||
#set math.equation(numbering: (n, ..) => {
|
||
numbering("(1.1)", counter(heading).get().first(), n)
|
||
})
|
||
|
||
#set figure(numbering: (n, ..) => {
|
||
numbering("1.1", counter(heading).get().first(), n)
|
||
})
|
||
|
||
#show figure.caption: it => {
|
||
let pattern = "^[^:]+" + sym.space.nobreak + "[\d.]+"
|
||
it
|
||
}
|
||
|
||
#show heading.where(level: 1): it => {
|
||
counter(math.equation).update(0)
|
||
counter(figure.where(kind: image)).update(0)
|
||
counter(figure.where(kind: table)).update(0)
|
||
counter(figure.where(kind: raw)).update(0)
|
||
it
|
||
}
|
||
|
||
#set math.equation(supplement: "Enačba")
|
||
|
||
#let avthor = "Nikola Petrov"
|
||
#let mentor = "red. prof. dr. Alešu Holobarju"
|
||
#let naslov = upper("Uporabniško vodena evolucija fraktalnih dreves")
|
||
#let naslov_en = upper("User-guided evolution of fractal trees")
|
||
|
||
#set document(
|
||
title: [#naslov],
|
||
author: avthor,
|
||
)
|
||
|
||
#align(center + top)[
|
||
#image("assets/UM_FERI.png", width: 30%)
|
||
]
|
||
|
||
#align(center + horizon)[
|
||
#set text(size: 14pt)
|
||
#avthor
|
||
#show title: set text(size: 26pt)
|
||
#title()
|
||
Diplomsko delo
|
||
]
|
||
|
||
#align(center + bottom)[
|
||
Maribor, oktober 2025
|
||
]
|
||
#pagebreak()
|
||
|
||
#align(center + top)[
|
||
#image("assets/UM_FERI.png", width: 30%)
|
||
]
|
||
|
||
#align(center + horizon)[
|
||
#set text(size: 14pt)
|
||
#avthor
|
||
#show title: set text(size: 26pt)
|
||
#title()
|
||
Diplomsko delo
|
||
]
|
||
|
||
#align(center + bottom)[
|
||
Maribor, oktober 2025
|
||
]
|
||
#pagebreak()
|
||
|
||
#counter(page).update(1)
|
||
#set page(numbering: "i")
|
||
|
||
#align(center + horizon)[
|
||
#title()
|
||
Diplomsko delo
|
||
]
|
||
|
||
#align(bottom)[
|
||
#grid(
|
||
columns: 2,
|
||
gutter: 10pt,
|
||
|
||
[Študent], [#avthor],
|
||
[Študijski program], [visokošolski študijski program \ računalništvo in informacijske tehnologije],
|
||
[Mentor], [#mentor],
|
||
)
|
||
]
|
||
|
||
#pagebreak()
|
||
|
||
|
||
|
||
#align(horizon)[
|
||
#set par(justify: false)
|
||
#set text(hyphenate: false, size: 14pt)
|
||
#grid(
|
||
columns: (1fr, 1fr),
|
||
[],
|
||
[
|
||
*Zahvala*
|
||
|
||
Na tem mestu bi se rad iskreno
|
||
zahvalil vsem, ki so prispevali
|
||
k uspešnemu zaključku te diplomske
|
||
naloge.
|
||
|
||
Zahvaljujem se svojemu
|
||
mentorju #mentor,
|
||
za njegovo pomoč in nasvete skozi
|
||
celoten proces pisanja.
|
||
|
||
Posebna zahvala gre moji družini ter
|
||
starim in novim prijateljem, ki
|
||
so me ves čas podpirali
|
||
in spodbujali skozi celoten študij.
|
||
Brez vas ne bi dosegel tega, kar sem.
|
||
],
|
||
)
|
||
]
|
||
|
||
#pagebreak()
|
||
|
||
|
||
#naslov
|
||
|
||
*Ključne besede:*
|
||
|
||
*UDK:*
|
||
|
||
*Povzetek*
|
||
|
||
#pagebreak()
|
||
|
||
|
||
#naslov_en
|
||
|
||
*Keywords:*
|
||
|
||
*UDC:*
|
||
|
||
*Abstract*
|
||
|
||
#pagebreak()
|
||
|
||
IZJAVA O AVTORSTVU ZAKLJUČNEGA DELA
|
||
|
||
#pagebreak()
|
||
|
||
#outline(
|
||
title: "KAZALO VSEBINE",
|
||
depth: 3,
|
||
)
|
||
|
||
#pagebreak()
|
||
|
||
#outline(
|
||
title: "KAZALO SLIK",
|
||
target: figure.where(kind: image),
|
||
)
|
||
|
||
#pagebreak()
|
||
|
||
#outline(
|
||
title: "KAZALO TABEL",
|
||
target: figure.where(kind: table),
|
||
)
|
||
|
||
#pagebreak()
|
||
|
||
#counter(page).update(1)
|
||
#set page(numbering: "1")
|
||
|
||
|
||
= UVOD
|
||
V današnjem digitalnem svetu sta interaktivnost in prilagodljivost ključnega pomena za ustvarjanje uporabniških izkušenj, ki so tako zabavne kot tudi funkcionalne. Fraktalna drevesa kot matematična in umetniška oblika ponujajo neskončno raznolikost struktur, ki jih je mogoče uporabiti v raznovrstnih aplikacijah, od vizualnih umetnosti do simulacij naravnih procesov. V tem kontekstu se pojavi vprašanje: *kako lahko uporabniki aktivno vplivajo na razvoj in oblikovanje teh struktur?*
|
||
|
||
Ta diploma se osredotoča na razvoj aplikacije *Treender*, ki uporabnikom omogoča interaktivno vodenje evolucije fraktalnih dreves. S pomočjo algoritmov za genetsko evolucijo in uporabniških ocen aplikacija ustvarja in prilagaja fraktalna drevesa, ki odražajo individualne okuse in preference uporabnikov.
|
||
|
||
Cilj projekta je raziskati, kako lahko z algoritmi za evolucijo in uporabniško povratno informacijo ustvarimo dinamične in osebne izkušnje.
|
||
|
||
V nadaljevanju bomo predstavili osnovne koncepte za generiranje in evolucijo fraktalnih dreves, opisali strukturo aplikacije in podrobno razložili uporabljene algoritme. Prav tako bomo raziskali uporabniški vmesnik in proces objave aplikacije na Google Play Store. Na koncu bomo ocenili uporabniško izkušnjo in učinkovitost algoritmov, ki jih uporabljamo.
|
||
#pagebreak()
|
||
|
||
= OPIS APLIKACIJE
|
||
Treender je aplikacija, ki nam omogoča, da izbiramo in ocenjujemo fraktalna drevesa, ki se na podlagi naših ocen razvijajo in prilagajajo našim okusom. V desnem zgornjem kotu prikazuje odstotek, ki pove, kako zelo so si prikazana drevesa med seboj podobna, torej kako zelo se je izbira zožila; v vmesniku je označen kot všečnost, kar je natančneje pojasnjeno v @poglavje_podobnost. Na dnu prikazuje generacijo evolucije in zaporedno številko prikazanega vzorca (@aplikacija-slika-def). Če povlečemo po zaslonu levo se nam v zgornjem levem kotu prikaže napis "DISLIKE" (@aplikacija-slika-dislike), v desno pa se nam prikaže napis "LIKE" (@aplikacija-slika-like).
|
||
|
||
#grid(
|
||
columns: 3,
|
||
gutter: 10pt,
|
||
[
|
||
#figure(
|
||
image("assets/rand/capture_show_noraml.jpg"),
|
||
caption: [Primer aplikacije],
|
||
)<aplikacija-slika-def>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/rand/capture_show_liked.jpg"),
|
||
caption: [Primer aplikacije like],
|
||
)<aplikacija-slika-like>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/rand/capture_show_dislike.jpg"),
|
||
caption: [Primer aplikacije dislike],
|
||
)<aplikacija-slika-dislike>
|
||
],
|
||
)
|
||
|
||
Ko vzorec ocenimo, si aplikacija oceno zapomni, in ko ocenimo vse vzorce, se prikaže črna slika z napisom "new generation". V tem trenutku se glede na ocene ustvari nova generacija in izračuna podobnost med novimi drevesi.
|
||
|
||
== Potek seje <potek_seje>
|
||
Uporabnik od aplikacije ne dobi nobenih drsnikov ali številčnih nastavitev; edino, kar počne, je, da vsako prikazano drevo s potegom levo ali desno oceni z "ne" ali "da". Ena poteza je torej ena binarna ocena, ne vnos podatkov. Prav v tem je namen aplikacije: uporabniku ni treba znati opisati, kaj mu je všeč, dovolj je, da med prikazanimi drevesi prepozna tisto, kar mu je bližje.
|
||
|
||
Generacija obsega 16 dreves, zato uporabnik z 16 potezami zaključi eno generacijo in vidi učinek svojih ocen. Število generacij ni omejeno, seja traja toliko časa, kolikor uporabnik želi. Seje, ki jih analiziramo v @poglavje_podobnost, so bile prekinjene po dvanajsti generaciji, kar pomeni 13 generacij in 208 potez na sejo.
|
||
|
||
@gen0_slika prikazuje vseh 16 dreves začetne, naključne generacije, @gen12_slika pa vseh 16 dreves dvanajste generacije iste seje. Razlika med njima je hkrati odgovor na vprašanje, kaj je rezultat postopka: uporabnik na koncu ne dobi enega drevesa, ampak generacijo dreves z enotnim značajem, iz katere si izbere posamezno sliko. Slike vseh vmesnih generacij so v prilogi.
|
||
|
||
#grid(
|
||
columns: 2,
|
||
gutter: 10pt,
|
||
[
|
||
#figure(
|
||
image("assets/full_generation/1761153347_0.webp"),
|
||
caption: [Generacija 0: naključna začetna populacija],
|
||
)<gen0_slika>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/full_generation/1761153347_12.webp"),
|
||
caption: [Generacija 12 iste seje],
|
||
)<gen12_slika>
|
||
],
|
||
)
|
||
|
||
== Raznolikost izhodnega prostora <raznolikost>
|
||
Ker uporabnik na videz drevesa vpliva samo z izbiranjem, je smiselno vprašanje, kako širok je nabor slik, med katerimi izbira. Videz slike v celoti določa 180-bajtni genom (@dna_objekt), ki ga sestavljajo:
|
||
|
||
- 16 genov za vsako od 8 globin drevesa, ki določajo barvo veje in njeno spreminjanje po dolžini, debelino, dolžino, število otrok in razpon kota med njimi;
|
||
- tri naključna semena za obliko gora, razporeditev zvezd in variacije vej;
|
||
- štirje geni za položaj in velikost sonca oziroma lune ter za barvno shemo ozadja.
|
||
|
||
Ker vsaka veja glede na gen `branchCount` požene dve ali tri veje, ima drevo pri osmih globinah med $2^8 = 256$ in $3^8 = 6561$ končnih vej, barva pa se lahko med globinami spreminja neodvisno, kar daje razpon od enobarvnih do izrazito pisanih dreves. Ozadje ima 13 barvnih shem (tri dnevne palete v štirih odtenkih ter nočna) in znotraj vsake zvezno spremenljivo obliko gorovja, položaj ter velikost sonca oziroma lune.
|
||
|
||
Kolikšna raznolikost je s tem dejansko dosegljiva, je najbolje razvidno iz @gen0_slika: 16 naključnih genomov da drevesa od redkih in temnih do gostih in svetlih, z dnevnim, večernim in nočnim ozadjem. Prav tako pa je iz slike razvidna omejitev, ki je genom ne odpravi: motiv ozadja je vedno isti, torej nebo, sonce ali luna in tri plasti gora, spreminjata se le barvna shema in oblika gora. Aplikacija tako pokriva širok razpon dreves znotraj enega samega slikarskega motiva.
|
||
|
||
|
||
#pagebreak()
|
||
|
||
= UPORABLJENE TEHNOLOGIJE
|
||
V tem poglavju na kratko predstavimo tehnologije, ki smo jih uporabili, in razloge za njihovo izbiro.
|
||
|
||
== C++
|
||
C++ je programski jezik, ki je nastal kot razširitev jezika C in ga je v zgodnjih osemdesetih letih razvil Bjarne Stroustrup. Združuje učinkovitost in nizkonivojni dostop do pomnilnika z objektno usmerjenimi koncepti ter obsežno standardno knjižnico @wiki_cpp.
|
||
|
||
Zanj smo se odločili iz dveh razlogov. Prvi je hitrost izrisa: drevo je sestavljeno iz več deset tisoč risalnih klicev na sliko (@optimizacija_izrisa), kar na mobilni napravi zahteva jezik brez samodejnega čiščenja pomnilnika. Drugi je neposreden dostop do pomnilniške predstavitve podatkov, ki ga izkoriščamo pri delu z genomom: celoten genom obravnavamo kot zaporedje bajtov, zaradi česar so križanje, kloniranje in mutacija preproste zanke čez to zaporedje (@zapis_dna).
|
||
|
||
== Raylib
|
||
Raylib je odprtokodna knjižnica za razvoj iger in multimedijskih aplikacij, ki ponuja preprost vmesnik za 2D- in 3D-grafiko, zvok in vhodne naprave ter podpira več platform, med njimi tudi Android @web_raylib @web_raylib_cheatsheet.
|
||
|
||
Izbrali smo jo, ker potrebujemo le nekaj osnovnih risalnih funkcij (krog, trikotnik, pravokotnik z barvnim prehodom, izris v teksturo) in obravnavo dotika, vse to pa ponuja brez obsežnega ogrodja. Pomembna je bila tudi možnost, da isto kodo prevedemo za namizje in za Android, kar je omogočilo razvoj in razhroščevanje na računalniku.
|
||
|
||
== Dear ImGui
|
||
Dear ImGui je odprtokodna knjižnica za hitro izdelavo uporabniških vmesnikov v aplikacijah, ki tečejo v realnem času. Deluje po načelu neposrednega načina (immediate mode), pri katerem se vmesnik izriše na novo v vsakem okvirju, kar poenostavi njegovo spreminjanje @git_imgui @git_rlImgui.
|
||
|
||
V aplikaciji same ne uporabljamo. Uporabili smo jo za razvijalsko orodje, s katerim smo pregledovali seje, shranjene v podatkovni bazi, in izrisovali drevesa posameznih generacij; slike generacij v tej nalogi so nastale s tem orodjem.
|
||
|
||
== CMake
|
||
CMake je orodje za avtomatizacijo gradnje, ki iz opisa projekta v datotekah `CMakeLists.txt` generira gradbene datoteke za posamezno okolje, na primer `Makefile` ali projekt za Visual Studio, ter skrbi za iskanje in povezovanje odvisnosti @web_cmake @wiki_cmake.
|
||
|
||
Do njega smo prišli po ovinku: sprva smo uporabljali lastno gradbeno skripto, ki je sčasoma zahtevala več vzdrževanja kot sam projekt (@gradilni_sistem). CMake je to delo prevzel in nam omogočil gradnjo za Linux, Windows in Android z enim opisom projekta, hkrati pa sam prenese in zgradi Raylib.
|
||
|
||
== SQLite
|
||
SQLite je lahka vdelana relacijska podatkovna baza, ki teče kot del programa in ne potrebuje ločenega strežnika; celotna baza je shranjena v eni datoteki, podpira večino standardnega SQL in zagotavlja transakcijsko varnost @web_sqlite @wiki_sqlite.
|
||
|
||
Uporabljamo jo na strežniku, kjer hranimo ocene, ki jih odjemalci pošljejo ob koncu generacije, in v razvijalskem orodju za pregled teh podatkov. Za tak obseg podatkov je ločen strežnik za bazo nepotreben, ena datoteka pa poenostavi tudi izdelavo varnostnih kopij. Stanje seje na napravi uporabnika hranimo ločeno od nje, v lastnem binarnem zapisu, saj gre za eno samo strukturo fiksne velikosti.
|
||
|
||
|
||
= STRUKTURA APLIKACIJE
|
||
Preden opišemo posamezne dele, na kratko povzemimo, kaj se v aplikaciji zgodi med eno generacijo. Stanje aplikacije je generacija 16 genomov. Za vsak genom vizualizator izriše sliko, jedro jo prikaže uporabniku in sprejme njegovo oceno, DNA menedžer pa oceno zabeleži. Ko je ocenjenih vseh 16 osebkov, menedžer iz všečnih osebkov zgradi novo generacijo genomov, jedro izračuna podobnost med njimi in postopek se ponovi.
|
||
|
||
Temu ustreza tudi razdelitev besedila: uporabniški vmesnik in ocenjevanje sta opisana v @rotacija_slike, hramba stanja generacije v @dna_menedzer, zapis genoma v @zapis_dna, tvorjenje nove generacije v @genetski_algoritem, izris slike iz genoma pa v @dna_vizualizacija.
|
||
|
||
Aplikacija ima tri glavne enote: DNA menedžer, DNA vizualizator in jedro. DNA menedžer hrani generacijo genomov, skrbi za vrstni red njihovega prikaza in za tvorjenje nove generacije, DNA vizualizator iz genoma izriše sliko, v jedru pa so preostale komponente, med njimi omrežni vmesnik in vmesnik za shranjevanje.
|
||
|
||
Jedro je hrbtenica, ki povezuje vse komponente. Ob zagonu preračuna razmerja za prikaz besedila in slik dreves, med uporabo pa skrbi za premik in rotacijo slike, ko uporabnik s prstom povleče po zaslonu. Ko poteg doseže rob zaslona, jedro oceno posreduje DNA menedžerju in od njega dobi naslednji genom za prikaz, ga preda vizualizatorju in vrnjeno sliko prikaže uporabniku. Vsaka ocena se sproti shrani na disk, ob koncu generacije pa se shrani celotna generacija in se pošlje na strežnik.
|
||
|
||
#figure(
|
||
image("assets/potek_diagram/diagram.svg", height: 400pt),
|
||
caption: [Diagram poteka podatkov],
|
||
)
|
||
|
||
#pagebreak()
|
||
|
||
== UPORABNIŠKI VMESNIK ‒ ROTACIJA SLIKE <rotacija_slike>
|
||
Proces rotiranja slike glede na premik miške je sestavljen iz treh korakov
|
||
in uporabe trigometrije.
|
||
|
||
=== Prvi korak: Ob pritisku miške
|
||
V prvem koraku moramo izračunati velikost (magnitudo) in kot vektorja med miško in levim spodnjim kotom slike (Cyan vektor @Prikaz_vektorjev) in shraniti si moramo trenutno pozicijo miške (Oranžni vektor/Zelena pika @Prikaz_vektorjev).
|
||
|
||
$
|
||
"mouseStartV" = "mouseV"\
|
||
"sizeOfVectorMI" = sqrt(("mouseV"_x - "imageV"_x)^2 + ("mouseV"_y - "imageV"_y)^2)\
|
||
"oldAngleOfVectorMI" = "atan2"("imageV"_x - "mouseV"_x, "imageV"_y - "mouseV"_y)
|
||
$
|
||
- $"mouseV"$ ‒ trenutni vektor miške
|
||
- $"imageV"$ ‒ vektor pozicije slike (Modri vektor @Prikaz_vektorjev)
|
||
- $"vectorMI"$ ‒ vectorMouseImage ‒ vector med miško in sliko
|
||
- $"sizeOfVectorMI"$ ‒ velikost vektorjaMI
|
||
- $"oldAngleOfVectorMI"$ ‒ kot vektorjaMI v radianih
|
||
|
||
#grid(
|
||
columns: 2,
|
||
gutter: 10pt,
|
||
[
|
||
#figure(
|
||
image("assets/rand/cordinats_show_mouse_picture.jpg"),
|
||
caption: [Prikaz vektorjev za premik slike],
|
||
)<Prikaz_vektorjev>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/rand/show_mouse_movement.jpg"),
|
||
caption: [Prikaz delta razdalje],
|
||
)<Prikaz_razdalje>
|
||
],
|
||
)
|
||
|
||
#pagebreak()
|
||
=== Drugi korak: Medtem ko miško držimo stisnjeno
|
||
Sedaj lahko izračunamo rotacijo slike glede na horizontalni premik miške in posledično novo pozicijo slike.
|
||
|
||
$
|
||
Delta"mouseV"_x & = "mouseV"_x - "mouseStart"_x \
|
||
a & = frac(Delta"mouseV"_x, "screenWidth") \
|
||
b & = frac(a + 1, 2) \
|
||
"rotation" & = "lerp"(45,-45, b) \
|
||
"rotationRad" & = (("rotation"* pi) / 180.0)
|
||
$<mat_rotacija>
|
||
|
||
- $"screenWidth"$ ‒ širina zaslona
|
||
- $Delta"mouseV"_x$ ‒ sprememba pozicije $[-"screenWidth", "screenWidth"]$
|
||
- $a$ ‒ normalizirano na razpon $[-1, 1]$
|
||
- $b$ ‒ normalizirano na razpon $[0, 1]$
|
||
- $"rotation"$ ‒ kot za koliko se more slika obrniti v stopinjah
|
||
- $"rotationRad"$ ‒ v radianih
|
||
|
||
#v(10pt)
|
||
V @mat_rotacija za $Delta"mouseV"$ lahko vidimo na (@Prikaz_razdalje), da ko je začetek v zeleni piki in se premikamo proti modri, je delta pozitivna in ko se premikamo proti rdeči, je negativna, zato potrebujemo normalizacijo $a$ in $b$ ker LERP sprejme vrednosti med $[0, 1]$.
|
||
#v(10pt)
|
||
|
||
$
|
||
"newAngleOfVectorMI" & = "rotationRad" + "oldAngleOfVectorMI" \
|
||
"vectorMI"_x & = "sizeOfVectorMI" * sin("newAngleOfVectorMI") \
|
||
"vectorMI"_y & = "sizeOfVectorMI" * cos("newAngleOfVectorMI") \
|
||
"imageV"_x & = "vectorMI"_x + "mouseV"_x \
|
||
"imageV"_y & = "vectorMI"_y + "mouseV"_y \
|
||
"imageRotation" & = 90 + "rotation"
|
||
$
|
||
|
||
- $"imageRotation"$ ‒ novi kot slike v stopinjah
|
||
- $"imageV"$ ‒ pozicija slike
|
||
|
||
#v(10pt)
|
||
Sedaj lahko končno narišemo sliko na poziciji $"imageV"$ in pot kotom $"imageRotation"$.
|
||
|
||
#pagebreak()
|
||
=== Tretji korak: Ob spustitvi miške
|
||
Ko miško spustimo, moramo samo ponastaviti vrednosti slike, da je spet pokončno, in jo postaviti nazaj na originalno pozicijo.
|
||
|
||
$
|
||
"imageRotation" & = 90 \
|
||
"imageV" & = "orgImageV"
|
||
$
|
||
|
||
- $"orgImageV"$ ‒ originalna pozicija slike
|
||
|
||
=== Uporabljene funkcije
|
||
V zgornjih enačbah nastopata dve standardni funkciji. Funkcija $"atan2"$ vrne kot vektorja v pravem kvadrantu, pri čemer upošteva predznaka obeh koordinat @wiki_atan2. Argumenta ji podajamo v vrstnem redu $(Delta x, Delta y)$, zato je dobljeni kot merjen od navpične osi in v enačbah za razstavljanje vektorja nastopa sinus pri komponenti $x$ in kosinus pri komponenti $y$. Funkcija $"lerp"(v_0, v_1, t) = v_0 + t (v_1 - v_0)$ linearno interpolira med vrednostma $v_0$ in $v_1$ s parametrom $t in [0, 1]$ @wiki_lerp.
|
||
|
||
#pagebreak()
|
||
|
||
== DNA MENEDŽER <dna_menedzer>
|
||
#let next = `next`
|
||
#let like = `like`
|
||
#let newGen = `newGen`
|
||
|
||
DNA menedžer hrani celotno populacijo tekoče generacije, skrbi za vrstni red prikaza osebkov in za prehod v naslednjo generacijo. Vmesnik sestavljajo tri funkcije (@dna_manager): #next vrne naslednji osebek za prikaz, #like sporoči uporabnikovo oceno, #newGen pa iz zbranih ocen zgradi naslednjo generacijo. Ko #next vrne `nullptr` in #like vrne `false`, so vsi osebki generacije prikazani in ocenjeni, zato jedro pokliče #newGen.
|
||
|
||
Menedžer dovoli, da naslednji osebek pridobimo, še preden ocenimo prejšnjega. Aplikacija to izkorišča tako, da hkrati hrani dva osebka: zgornjega, ki ga uporabnik premika in ocenjuje, in spodnjega, ki je že izrisan in čaka v ozadju. Po vsaki oceni spodnji osebek postane zgornji, na njegovo mesto pa vstopi naslednji.
|
||
|
||
Za sledenje stanju generacije menedžer uporablja dva indeksa v vektorju osebkov. Indeks `queued` kaže na naslednji osebek za prikaz, indeks `showed` pa na naslednji osebek za oceno. Funkcija #next vrne osebek na mestu `queued` in indeks poveča; ko `queued` doseže velikost generacije, vrne `nullptr`. Funkcija #like uvrsti indeks ocenjenega osebka med všečne ali nevšečne in poveča `showed`; ko sta oba indeksa na koncu vektorja, vrne `false`. Glavna logika evolucije je v funkciji #newGen in je opisana v @genetski_algoritem.
|
||
|
||
#figure(caption: [DnaManager])[
|
||
#grid(
|
||
columns: 2,
|
||
[
|
||
```cpp
|
||
struct DnaManagerData
|
||
{
|
||
int generation;
|
||
uint128 randSeed;
|
||
int64_t id;
|
||
int queued;
|
||
int showed;
|
||
std::vector<Dna> vector;
|
||
std::vector<int> liked;
|
||
std::vector<int> disliked;
|
||
};
|
||
|
||
namespace DnaManager
|
||
{
|
||
UiUnit next(DnaManagerData *data);
|
||
bool like(UiUnit unit, DnaManagerData *data);
|
||
void newGen(DnaManagerData *data);
|
||
}
|
||
```
|
||
],
|
||
[
|
||
```cpp
|
||
struct UiUnit
|
||
{
|
||
Dna *dna;
|
||
Liked liked;
|
||
int index;
|
||
};
|
||
|
||
enum Liked
|
||
{
|
||
tbd,
|
||
yes,
|
||
no
|
||
};
|
||
```
|
||
],
|
||
)
|
||
|
||
]<dna_manager>
|
||
|
||
#pagebreak()
|
||
|
||
== ZAPIS DNA <zapis_dna>
|
||
Dna je sestavljen iz dveh struktur (@dna_objekt). Zanimliv del, ki ga opazimo, je, da je vsak gen točno en bite dolg in celoten objekt je v pomnilniku samo en velik list bitov (array of bites). To značinost uporabljamo v complementarnih funkcijah `newDna`, `makeChiled`, `clone` in `mutate`.
|
||
|
||
#figure(caption: [DNA objekt])[
|
||
|
||
#grid(
|
||
columns: 2,
|
||
[
|
||
```cpp
|
||
struct Dna
|
||
{
|
||
uint128 mountenSeed;
|
||
uint128 starSeed;
|
||
uint128 branchSeed;
|
||
|
||
uint8_t moonX;
|
||
uint8_t moonY;
|
||
uint8_t moonSize;
|
||
uint8_t colorSet;
|
||
Branch branches[MAX_DEPTH];
|
||
};
|
||
```
|
||
],
|
||
[
|
||
```cpp
|
||
struct Branch
|
||
{
|
||
uint8_t colorR;
|
||
uint8_t colorG;
|
||
uint8_t colorB;
|
||
int8_t colorR_change;
|
||
int8_t colorG_change;
|
||
int8_t colorB_change;
|
||
uint8_t colorVar;
|
||
|
||
uint8_t size;
|
||
uint8_t sizeParent;
|
||
uint8_t sizeLevel;
|
||
uint8_t sizeChange;
|
||
uint8_t sizeVar;
|
||
|
||
uint8_t length;
|
||
uint8_t lengthVar;
|
||
|
||
uint8_t branchCount;
|
||
uint8_t branchAngleVar;
|
||
};
|
||
```
|
||
],
|
||
)
|
||
]<dna_objekt>
|
||
|
||
#pagebreak()
|
||
|
||
|
||
Če pogledamo definicijo od `newDna` (@dna_funkcije), vidimo pretvorbo (cast) iz `Dna` v `uint8_t*` in sedaj se lahko enostavno sprehodimo čez objekt in spremenimo vrednosti.
|
||
|
||
#figure(caption: [Primer DNA funkcije])[
|
||
```cpp
|
||
namespace DNA
|
||
{
|
||
void newDna(Dna *dna, uint128 *randState);
|
||
void makeChild(Dna *p1, Dna *p2, Dna *c, uint128 *randState);
|
||
void clone(Dna *p1, Dna *c, uint128 *randState);
|
||
void mutate(Dna *dna, uint32_t num, uint128 *randState);
|
||
}
|
||
|
||
void newDna(Dna *dna, uint128 *state)
|
||
{
|
||
uint8_t *array = (uint8_t *)dna;
|
||
for (size_t i = 0; i < sizeof(Dna); i++)
|
||
{
|
||
array[i] = mrand::getValue(256, state);
|
||
}
|
||
}
|
||
```
|
||
]<dna_funkcije>
|
||
|
||
Ostale funkcije so podobne; najprej pretvorimo v `uint_8*` in nato:
|
||
- `makeChild` naključno kopiramo iz staršev,
|
||
- `clone` naključno kopiramo iz starša in vstavljamo naključne vrednosti,
|
||
- `mutate` pa sprecificirano število vrednosti spremenimo v naključne vrednosti.
|
||
|
||
#pagebreak()
|
||
|
||
== GENETSKI ALGORITEM <genetski_algoritem>
|
||
Ob koncu vsake generacije funkcija `newGen` iz uporabnikovih ocen zgradi novo populacijo. Ker prav ta korak določa, kako hitro se populacija zoži k uporabnikovemu okusu in koliko naključnosti v njej ostane, ga v nadaljevanju opišemo po posameznih delih.
|
||
|
||
=== Selekcija in elitizem
|
||
Vsi všečni osebki se v naslednjo generacijo prenesejo nespremenjeni, otroci pa prepišejo samo mesta nevšečnih osebkov. Velikost populacije zato ostane enaka, delež na novo ustvarjenih osebkov pa je enak deležu nevšečnih ocen v prejšnji generaciji. Če uporabnik označi kot všečnih deset od šestnajstih osebkov, se na novo ustvari le preostalih šest.
|
||
|
||
=== Križanje
|
||
Za vsako mesto nevšečnega osebka enakomerno naključno izberemo dva različna starša iz množice všečnih. Križanje je uniformno na ravni bajtov: za vsak bajt genoma z verjetnostjo 0,5 prepišemo vrednost prvega ali drugega starša, tako da otrok v povprečju podeduje polovico genoma od vsakega starša.
|
||
|
||
=== Robna primera
|
||
- *En všečni osebek.* Križanje ni mogoče, zato uporabimo funkcijo `clone`, ki vsak bajt otroka z verjetnostjo 0,5 prepiše od starša, sicer pa ga nadomesti z naključno vrednostjo. Polovica genoma otroka je torej naključna, kar je najmočnejši vir naključnosti v celotnem postopku.
|
||
- *Noben všečni osebek.* Celotno populacijo nadomestimo z novo naključno populacijo.
|
||
|
||
=== Mutacija
|
||
Po križanju mutiramo *vse* osebke, tudi všečne. Mutacija na naključno izbranih mestih zamenja tri bajte z naključnimi vrednostmi. Genom obsega 180 bajtov, kar pomeni približno 1,7 % genoma na osebek na generacijo.
|
||
|
||
Ker mutacija deluje tudi na všečne osebke, se populacija ne more nikoli povsem poenotiti. To je tudi razlog, da podobnost znotraj generacije doseže strop pri približno 82 % in ne pri 100 % (@interpretacija_konvergence), kar so kot motečo lastnost opazili tudi uporabniki (@moteca_podobnost).
|
||
|
||
#figure(caption: [Postopek tvorjenja nove generacije])[
|
||
```
|
||
newGen(populacija, všečni, nevšečni):
|
||
če je množica všečni prazna:
|
||
za vsak osebek v populaciji: newDna(osebek)
|
||
končaj
|
||
če ima množica všečni natanko en element:
|
||
za vsako mesto i iz množice nevšečni:
|
||
clone(všečni[0], populacija[i])
|
||
sicer:
|
||
za vsako mesto i iz množice nevšečni:
|
||
p1, p2 = dva različna naključna starša iz množice všečni
|
||
makeChild(p1, p2, populacija[i])
|
||
za vsak osebek v populaciji: mutate(osebek, 3)
|
||
```
|
||
]<psevdokoda_newgen>
|
||
|
||
=== Viri naključnosti
|
||
V postopku nastopa pet virov naključnosti (@tabela_nakljucnost). Nobeden od njih ni odvisen od zaporedne številke generacije: verjetnost križanja in stopnja mutacije sta skozi celotno sejo konstantni. Naključnost se spreminja le posredno, prek števila všečkov, saj to določi, katera veja postopka se izvede in koliko osebkov se sploh na novo ustvari. Kako se to pozna na izmerjeni podobnosti med osebki, prikazuje @interpretacija_konvergence.
|
||
|
||
#align(center)[
|
||
#figure(caption: [Viri naključnosti v postopku tvorjenja nove generacije])[
|
||
#table(
|
||
columns: 3,
|
||
align: (left, left, left),
|
||
table.header([Vir], [Obseg naključnosti], [Odvisnost od generacije]),
|
||
table.hline(),
|
||
[Izbira staršev], [enakomerno iz množice všečnih], [posredna, prek števila všečkov],
|
||
[Uniformno križanje], [$p = 0,5$ na bajt], [ni odvisno],
|
||
[Kloniranje (en všeček)], [$p = 0,5$ naključni bajt, tj. približno polovica genoma], [le v tem robnem primeru],
|
||
[Mutacija], [3 bajti od 180, tj. približno 1,7 % genoma], [ni odvisno],
|
||
[Nova naključna populacija \ (brez všečkov)], [celoten genom vseh osebkov], [le v tem robnem primeru],
|
||
)
|
||
]<tabela_nakljucnost>
|
||
]
|
||
|
||
#pagebreak()
|
||
|
||
=== Izbira parametrov <izbira_parametrov>
|
||
Postopek ima dva prosta parametra: velikost generacije in stopnjo mutacije. K tema se pridruži še dolžina seje, torej število generacij, ki jih uporabnik prehodi.
|
||
|
||
*Velikost generacije* je nastavljena na 16 osebkov. Vrednost je kompromis med dvema nasprotujočima si zahtevama. Večja generacija pomeni več staršev in s tem zanesljivejšo selekcijo, hkrati pa uporabnik dlje čaka na spremembo, saj mora pred vsako novo generacijo opraviti toliko ocen, kolikor je osebkov. Pri 16 osebkih uporabnik vidi učinek svojih ocen po 16 potezah. Vrednosti nismo določili eksperimentalno, zato je ne predstavljamo kot optimalne; testni uporabniki so opozorili prav na nasprotni učinek, da je 16 osebkov premalo za zanesljivo razlikovanje med lastnostmi slik (@nepricakovani_rezultati).
|
||
|
||
*Stopnja mutacije* je nastavljena na tri bajte na osebek. Pri manjši vrednosti populacija hitreje obtiči v enolični množici zelo podobnih dreves, pri večji pa uporabnik med generacijami ne prepozna več svojih izbir. Tudi ta vrednost je bila izbrana med razvojem po opazovanju izrisanih generacij in ne z meritvijo.
|
||
|
||
*Dolžina seje* ni omejena; aplikacija lahko teče poljubno dolgo. Seje, ki jih analiziramo v @poglavje_podobnost, so bile prekinjene po dvanajsti generaciji, ker podobnost znotraj generacije do takrat naraste s približno 0 % na 82 % in nato ne narašča več (@graf_podobnost). Nadaljnje generacije torej ne prinesejo več opazne konvergence, prinesejo pa dodatnih 16 potez na generacijo.
|
||
|
||
Sistematično iskanje najboljših vrednosti teh treh parametrov presega obseg naloge in ga navajamo med predlogi za nadaljnje delo (@zakljucek).
|
||
|
||
#pagebreak()
|
||
|
||
== DNA VIZUALIZACIJA <dna_vizualizacija>
|
||
|
||
|
||
#figure(
|
||
image("assets/rand/slika_drevesa.jpg", height: 200pt),
|
||
caption: [Končna slika po vizualizaciji],
|
||
)
|
||
|
||
Je sestavljena iz treh razredov: `Canvas`, `BackGround`, `Tree` (@razredi_vizualizacije). Tukaj je Canvas samo vmesni razred, ki postavi risanje na teksturo in nato pokliče BackGround in Tree.
|
||
|
||
#figure(caption: [Razredi za vizualizacijo])[
|
||
#grid(
|
||
columns: 2,
|
||
[
|
||
```cpp
|
||
class Canvas
|
||
{
|
||
public:
|
||
void draw(
|
||
RenderTexture2D &target,
|
||
Dna *dna);
|
||
private:
|
||
BackGround backGround;
|
||
Tree tree;
|
||
};
|
||
|
||
class BackGround
|
||
{
|
||
public:
|
||
void draw(Dna *dna);
|
||
private:
|
||
void drawStars();
|
||
void drawSun();
|
||
void drawMounten(
|
||
size_t mountenSegments, int min,
|
||
int max, Color color, float scale);
|
||
};
|
||
```
|
||
],
|
||
[
|
||
```cpp
|
||
class Tree
|
||
{
|
||
public:
|
||
void draw(Dna *dna);
|
||
private:
|
||
void drawBranch();
|
||
std::vector<DrawArgs> drawCalls;
|
||
};
|
||
|
||
struct DrawArgs
|
||
{
|
||
Vector2 startPoint;
|
||
float angle;
|
||
int depth;
|
||
Color parent;
|
||
int perentSize;
|
||
};
|
||
```
|
||
],
|
||
)
|
||
]<razredi_vizualizacije>
|
||
|
||
#pagebreak()
|
||
|
||
=== Ozadje
|
||
Ozadje izrišemo v štirih korakih. Najprej narišemo nebo, in sicer podnevi kot navpičen barvni prehod s funkcijo `DrawRectangleGradientV` (@steps_nebo), ponoči pa kot enobarvno površino z zvezdami, katerih položaje določa naključno seme iz genoma (@steps_zvezde). Sledita sonce oziroma luna, sestavljena iz več koncentričnih krogov z nizko prosojnostjo, da dobimo mehak rob (@steps_sonce). Nazadnje izrišemo tri plasti gorovja, vsako s svojo barvo in višinskim razponom (@steps_gora_1 do @steps_gora_5).
|
||
|
||
Gore so bile med vsemi elementi najzahtevnejše. Rešili smo jih s trakom trikotnikov (triangle strip) @wiki_triangle_strip, pri katerem se točke izmenjujejo med tlemi in naključno izbrano višino, tako da vsaka nova točka s prejšnjima dvema tvori trikotnik (@Triangle_Strip). Plast izrišemo iz 150 takih segmentov od levega do desnega roba slike.
|
||
|
||
Barvno shemo ozadja določata dva gena: `colorSet` izbere eno od štirih shem, tri dnevne in eno nočno, `moonY` pa znotraj dnevne sheme enega od štirih odtenkov, kar ustreza različnim delom dneva. Skupaj je torej na voljo 13 barvnih shem, znotraj vsake pa se zvezno spreminjajo oblika gorovja, razporeditev zvezd ter položaj in velikost sonca oziroma lune.
|
||
|
||
|
||
#block(breakable: false)[
|
||
#grid(
|
||
columns: 3,
|
||
gutter: 10pt,
|
||
[
|
||
#figure(
|
||
image("assets/draw_steps/steps_1_1.png", height: 100pt),
|
||
caption: [Korak dnevno nebo],
|
||
)<steps_nebo>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/draw_steps/steps_2_2.png", height: 100pt),
|
||
caption: [Korak nočno nebo z zvezdami],
|
||
)<steps_zvezde>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/draw_steps/steps_1_2.png", height: 100pt),
|
||
caption: [Korak sonce oziroma luna],
|
||
)<steps_sonce>
|
||
],
|
||
|
||
[
|
||
#figure(
|
||
image("assets/draw_steps/steps_1_3_1.png", height: 100pt),
|
||
caption: [Korak gora 1],
|
||
)<steps_gora_1>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/draw_steps/steps_1_3_2.png", height: 100pt),
|
||
caption: [Korak gora 2],
|
||
)<steps_gora_2>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/draw_steps/steps_1_3.png", height: 100pt),
|
||
caption: [Korak gora 3],
|
||
)<steps_gora_3>
|
||
],
|
||
|
||
[
|
||
#figure(
|
||
image("assets/draw_steps/steps_1_4.png", height: 100pt),
|
||
caption: [Korak gora 4],
|
||
)<steps_gora_4>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/draw_steps/steps_1_5.png", height: 100pt),
|
||
caption: [Korak gora 5],
|
||
)<steps_gora_5>
|
||
],
|
||
)
|
||
#figure(
|
||
image("assets/rand/Triangle_Strip.svg.png", height: 150pt),
|
||
caption: [Triangle strip],
|
||
)<Triangle_Strip>
|
||
]
|
||
|
||
#pagebreak()
|
||
|
||
|
||
=== Drevo
|
||
#let da = `DrawArgs`
|
||
#let dn = `Branch`
|
||
|
||
Algoritem za izris drevesa je iterativni proceduralni generator. Za izris uporabljamo strukturo #dn (@dna_objekt) in `std::list` (FIFO) #da (@razredi_vizualizacije).
|
||
|
||
==== DNA Branch
|
||
Veja je struktura, ki vsebuje podatke o:
|
||
|
||
- začetni barvi (`colorX`) [0, 255],
|
||
- spremembi barve (`colorX_change`), za koliko se barva spremeni čez dolžino veje [0, 255],
|
||
- variaciji začetne barve (`colorVar`), za koliko se lahko naključno spremeni začetna barva [-15, -15],
|
||
- začetni debelini (`size`) [2, 20],
|
||
- debelini glede na starša (`sizeParent`) [0.0, 1.0],
|
||
- debelini glede na globino (`sizeLevel`); iz @table_glob_data procent, koliko je podoben predefinirani velikosti [0.0, 1.0],
|
||
- spremembi debeline (`sizeChange`) za končno debelino veje [-5, 5],
|
||
- variaciji debeline (`sizeVar`), za koliko se lahko naključno spremeni začetna debelina [-5, 5],
|
||
- dolžini (`length`) veje [0.5, 1.3],
|
||
- variaciji dolžine (`lengthVar`), za koliko se lahko naključno spremeni dolžina veje [-0.15, 0.15],
|
||
- številu otroki (`branchCount`), koliko vej bo nadaljevalo [2, 3],
|
||
- variaciji kota med vejami (`branchAngleVar`) naključna variacija kota med vejami zato, da ni enakomerno razporejeno [0, 20].
|
||
|
||
#figure(caption: [Globalni podatki])[
|
||
#table(
|
||
columns: 9,
|
||
table.header([Depth], [0], [1], [2], [3], [4], [5], [6], [7]),
|
||
table.hline(),
|
||
[Sizes], [20], [18], [16], [14], [12], [10], [8], [6],
|
||
[Lengths \*], [1/4], [7/40], [], [], [], [], [], [],
|
||
)
|
||
\* Lengths for 0 is 1/4 of length of a canvas next are 70% shorter of previous
|
||
]<table_glob_data>
|
||
|
||
#pagebreak()
|
||
|
||
==== Algoritem
|
||
Algoritem drevo gradi po vejah in ne rekurzivno. V seznamu hrani opise vej, ki jih je še treba izrisati; iz seznama vzame prvi opis, izriše vejo in na njen konec doda opise njenih otrok, dokler seznam ni prazen. Vsaka veja pri tem prevzame nekaj lastnosti od starša (končno debelino in barvo), preostale pa prebere iz gena za svojo globino. Tako je celotno drevo določeno z osmimi geni, po enim za vsako globino, in s tem, kar veje podedujejo od svojih staršev.
|
||
|
||
Začnemo tako, da v seznam damo opis debla, ki ga prikazuje @prvi_drawArgs, in ponavljamo naslednje korake, dokler je v seznamu še kaj.
|
||
#figure(caption: [Prvi DrawArgs])[
|
||
```cpp
|
||
struct DrawArgs
|
||
{
|
||
startPoint : {x: screenWidth/2, y:0},
|
||
angle: 90.0f,
|
||
depth: 0
|
||
};
|
||
```
|
||
]<prvi_drawArgs>
|
||
|
||
+ Korak: Predpostavek, da lahko narišemo drevo, predvidevamo, da imamo strukturo `DNA`
|
||
|
||
+ Korak: Priprava
|
||
|
||
Pridobimo `DrawArgs arg` in `Branch b`
|
||
|
||
```cpp
|
||
DrawArgs arg = list.pop_front();
|
||
Branch b = Dna.branches[argument.depth];
|
||
```
|
||
|
||
+ Korak: Začetna točka
|
||
```cpp
|
||
Vector2 StartPoint = arg.startPoint;
|
||
```
|
||
@viztree0
|
||
+ Korak: Dolžina
|
||
```cpp
|
||
float Len = Lengths[arg.dep] * b.length * (b.lengthVar * randFloat());
|
||
```
|
||
`Lengths` je iz @table_glob_data
|
||
|
||
@viztree1
|
||
+ Korak: Končna točka in naključni kot
|
||
```cpp
|
||
float AngleVar = lerp(b.branchAngleVar, -b.branchAngleVar, randFloat());
|
||
float tmpAng = AngleVar + arg.angle;
|
||
float nx = Len * sin(tmpAng);
|
||
float ny = Len * cos(tmpAng);
|
||
Vector2 EndPoint;
|
||
EndPoint.x = StartPoint.x + nx;
|
||
EndPoint.y = StartPoint.y + ny;
|
||
```
|
||
@viztree2
|
||
+ Korak: Začetna debelina
|
||
```cpp
|
||
float tmp1 = b.size + (b.sizeVar * randFloat());
|
||
float tmp2 = lerp(tmp1 ,arg.parentSize, b.sizeParent);
|
||
float StartSize = lerp(tmp2, Sizes[arg.dep], b.sizeLevel);
|
||
```
|
||
`Sizes` je iz @table_glob_data
|
||
|
||
@viztree3
|
||
|
||
+ Korak: Končna debelina
|
||
```cpp
|
||
float EndSize = StartSize + b.sizeChange;
|
||
```
|
||
@viztree3
|
||
|
||
+ Korak: Začetna barva
|
||
```cpp
|
||
Color StartColor = lerp(b.colorX, arg.parentX , 0.7) + b.colorVar * randFloat();
|
||
```
|
||
@viztree4
|
||
|
||
+ Korak: Končna barva
|
||
```cpp
|
||
Color EndColor = StartColor * b.colorChange * randFloat();
|
||
```
|
||
@viztree4
|
||
|
||
+ Korak: Izris veje
|
||
```cpp
|
||
float fstep = 1.0 / ((Len / sizeStart) * 2.0f);
|
||
for (float i = 0; i < 1; i += fstep)
|
||
{
|
||
Vector2 point = Vector2Lerp(StartPoint, EndPoint, i);
|
||
Color color = ColorLerp(StartColor, EndColor, i);
|
||
int size = Lerp(StartSize, EndSize, i);
|
||
DrawCircleV(point, size, color);
|
||
}
|
||
```
|
||
@viztree5
|
||
|
||
+ Korak: Dodaj otroke v list
|
||
```cpp
|
||
if(arg.dep + 1 > MAX_DEPTH) return;
|
||
float sectors = b.branchCount + 1;
|
||
float degres = 180.0f / sectors;
|
||
for (size_t i = 0; i < b.branchCount; i++)
|
||
{
|
||
float newAngle = arg.angle - 90 + (degres * (i + 1));
|
||
drawCalls.push_back({EndPoint, newAngle, arg.dep + 1, ColorEnd, SizeEnd});
|
||
}
|
||
```
|
||
@viztree6
|
||
|
||
+ Korak: Ponovimo
|
||
|
||
Sedaj gremo spet na Korak: Priprava (@viztree7)
|
||
|
||
#block(breakable: false)[
|
||
#grid(
|
||
columns: 3,
|
||
gutter: 10pt,
|
||
[
|
||
#figure(
|
||
image("assets/vizualizacija_drevo/slika00.png", height: 100pt),
|
||
caption: [Začetna točka],
|
||
)<viztree0>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/vizualizacija_drevo/slika01.png", height: 100pt),
|
||
caption: [Dolžina veje],
|
||
)<viztree1>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/vizualizacija_drevo/slika02.png", height: 100pt),
|
||
caption: [Kot in končna točka],
|
||
)<viztree2>
|
||
],
|
||
|
||
[
|
||
#figure(
|
||
image("assets/vizualizacija_drevo/slika03.png", height: 100pt),
|
||
caption: [Debeline],
|
||
)<viztree3>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/vizualizacija_drevo/slika04.png", height: 100pt),
|
||
caption: [Barve],
|
||
)<viztree4>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/vizualizacija_drevo/slika05.png", height: 100pt),
|
||
caption: [Izris veje],
|
||
)<viztree5>
|
||
],
|
||
)
|
||
#grid(
|
||
columns: 2,
|
||
gutter: 10pt,
|
||
[
|
||
#figure(
|
||
image("assets/vizualizacija_drevo/slika06.png", height: 200pt),
|
||
caption: [Novi otroki],
|
||
)<viztree6>
|
||
],
|
||
[
|
||
#figure(
|
||
image("assets/vizualizacija_drevo/slika07.png", height: 200pt),
|
||
caption: [Ponovimo],
|
||
)<viztree7>
|
||
],
|
||
)
|
||
]
|
||
|
||
|
||
|
||
|
||
|
||
#pagebreak()
|
||
|
||
== OPTIMIZACIJE
|
||
|
||
=== Optimizacija izrisa <optimizacija_izrisa>
|
||
|
||
Sprva se je drevo izrisalo s pomočjo raylib funkcije `DrawLineEx`, drevo se je izrisovalo vsak okvir (frame). Kasneje smo hoteli dodati veje s spremenljivo debelino, najlažja rešitev, ki smo se jo spomnili, je bila, da narišemo krogce s spremenljivim polmerom. To nas je prisililo, da moramo narisati čez 55000 krogov. Z raylibovo funkcijo `DrawCircleV` za risanje krogov je applikacija začela zaostajati (lagged). To smo rešili tako, da najprej drevo narišemo na teksturo, ki je zelo enostavna za izris. To je rešilo večino problemov, občasno se je še vedno pojavil zaostanek (lag spike), ki smo ga rešili tako, da smo omejili število risalnih klicev na okvir in drevo narisali v par okvirjih.
|
||
|
||
#align(center)[
|
||
#figure(caption: [Optimizacije izrisa])[
|
||
#table(
|
||
columns: 5,
|
||
align: horizon,
|
||
table.header(
|
||
[Optimizacija], [Povprečen ms/okvir], [Skupni čas izrisa slike], [Maks ms/okvir po zamenjavi slike], [FPS]
|
||
),
|
||
table.hline(),
|
||
[Izris s črtami], [2], [2], [3], [350],
|
||
[Izris s krogi vsak okvir], [100], [100], [100], [10],
|
||
[Izris s krogi v teksturo], [0.2], [100], [100], [5000],
|
||
[Izris s krogi v teksturo čez več okvirjev], [0.2], [100], [14], [5000],
|
||
)
|
||
]
|
||
]
|
||
|
||
#pagebreak()
|
||
=== Optimizacija DNA menedžerja
|
||
|
||
Na začetku (@dna_manager_v1) je bil DnaManager struktura kazalcev na `Dna`, kar pomeni, da stanja ni bilo mogoče shraniti v datoteko, saj kazalci po ponovnem zagonu niso več veljavni. Zato smo kazalce zamenjali z indeksi (@dna_manager_v2), ki jih je mogoče zapisati; ob tem se je izkazalo še, da je za predpomnilnik ugodno, če so indeksi v seznamu `queued` urejeni naraščajoče.
|
||
|
||
Med razhroščevanjem smo opazili, da sta seznama `queued` in `showed` odveč. Ker osebke prikazujemo in ocenjujemo v enakem vrstnem redu, kot so shranjeni v vektorju, oba seznama vedno vsebujeta strnjen del vektorja, zato ju je mogoče nadomestiti z dvema premikajočima se indeksoma v vektorju osebkov (@dna_manager_v3): pred indeksom `showed` so ocenjeni osebki, med `showed` in `queued` so prikazani in še neocenjeni, za `queued` pa še neprikazani.
|
||
|
||
#align(center)[
|
||
#grid(
|
||
columns: 2,
|
||
gutter: 16pt,
|
||
align: center,
|
||
[
|
||
#figure(caption: [DnaManager v1])[
|
||
```cpp
|
||
struct DnaManagerData
|
||
{
|
||
std::vector<Dna> vector;
|
||
std::list<Dna *> queued;
|
||
std::list<Dna *> showed;
|
||
std::vector<Dna *> liked;
|
||
std::vector<Dna *> disliked;
|
||
}
|
||
```
|
||
]<dna_manager_v1>
|
||
],
|
||
[
|
||
#figure(caption: [DnaManager v2])[
|
||
```cpp
|
||
struct DnaManagerData
|
||
{
|
||
std::vector<Dna> vector;
|
||
std::list<int> queued;
|
||
std::list<int> showed;
|
||
std::vector<int> liked;
|
||
std::vector<int> disliked;
|
||
}
|
||
```
|
||
]<dna_manager_v2>
|
||
],
|
||
)
|
||
]
|
||
|
||
#figure(caption: [DnaManager v3])[
|
||
```cpp
|
||
struct DnaManagerData
|
||
{
|
||
int queued;
|
||
int showed;
|
||
std::vector<Dna> vector;
|
||
std::vector<int> liked;
|
||
std::vector<int> disliked;
|
||
}
|
||
```
|
||
]<dna_manager_v3>
|
||
|
||
|
||
|
||
#pagebreak()
|
||
|
||
= PODOBNOST <poglavje_podobnost>
|
||
Med sejo želimo uporabniku pokazati, kako daleč je evolucija napredovala, hkrati pa potrebujemo mero, s katero lahko delovanje genetskega postopka spremljamo tudi pri razvoju. Za oboje uporabljamo isto količino: *povprečno podobnost med vsemi pari osebkov v trenutni generaciji*. Pri 16 osebkih je to povprečje čez $binom(16, 2) = 120$ parov.
|
||
|
||
Poudariti je treba, kaj ta količina pove in kaj ne. Razdalja med genoma pove, kako podobni sta si sliki, torej kako zelo se je populacija zožila oziroma kam je izbira skonvergirala. Ne pove pa, ali so slike uporabniku dejansko všeč: populacija lahko skonvergira tudi k drevesom, s katerimi uporabnik ni zadovoljen, na primer kadar med prikazanimi osebki ni bilo nobenega, ki bi mu ustrezal. Podobnost je torej *mera konvergence*, ne mera všečnosti. V uporabniškem vmesniku je prikazana kot odstotek "všečnosti", kar je zaradi igrifikacije razumljivo, vsebinsko pa neposrečeno; primernejša oznaka bi bila "ujemanje z vašim izborom" ali "stopnja konvergence".
|
||
|
||
Ker se mera računa po vsaki generaciji in se prikaže uporabniku, mora biti izračunljiva neposredno nad 180-bajtnim genomom, imeti zalogo vrednosti, ki jo je mogoče prikazati kot odstotek, med konvergenco populacije naraščati in se izračunati dovolj hitro, da prehod med generacijama ni opazen. Da bi pokrili različne pristope k merjenju razdalje, smo preučili sedem mer iz treh družin: geometrijske (evklidska razdalja, skalarni produkt, kosinusna podobnost in njena varianta), množične (Jaccardov indeks) ter nizovne oziroma poravnalne (Hammingova razdalja, Levenshteinova razdalja in Needleman-Wunschev algoritem).
|
||
|
||
== Opis mer
|
||
Genom obravnavamo kot zaporedje $n = 180$ bajtov, torej kot vektor celih števil z zalogo vrednosti $[0, 255]$. Vse mere so definirane nad tem zapisom in vrnjeno vrednost normaliziramo na odstotke.
|
||
|
||
=== Geometrijske mere
|
||
*Evklidska razdalja* je najkrajša razdalja med dvema točkama v evklidskem prostoru @wiki_euclidean_distance. Normaliziramo jo z največjo možno razdaljo v prostoru, podobnost pa je njen komplement:
|
||
$
|
||
d(p, q) & = sqrt(sum_(i=1)^n (q_i - p_i)^2) \
|
||
s & = 1 - frac(d(p, q), 255 sqrt(n))
|
||
$
|
||
|
||
*Skalarni produkt* dveh vektorjev vrne skalar @wiki_dot_product; normaliziramo ga z največjim možnim produktom $n dot 255^2$:
|
||
$
|
||
upright(bold(A)) op(dot) upright(bold(B)) & = sum_(i=1)^n A_i B_i \
|
||
s & = frac(upright(bold(A)) op(dot) upright(bold(B)), n dot 255^2)
|
||
$
|
||
|
||
*Kosinusna podobnost* meri kosinus kota med vektorjema in je neodvisna od njune velikosti @wiki_cosine_similarity:
|
||
$ s = frac(upright(bold(A)) op(dot) upright(bold(B)), ||upright(bold(A))|| ||upright(bold(B))||) $
|
||
Ker so vse komponente nenegativne, je kot med vektorjema vedno majhen in mera se že pri naključnih genomih giblje visoko. Zato smo preizkusili tudi *varianto*, pri kateri vrednosti genov najprej preslikamo iz $[0, 255]$ v $[-128, 127]$ in s tem razširimo izhodno območje.
|
||
|
||
=== Množične mere
|
||
*Jaccardov indeks* meri podobnost dveh množic kot razmerje med velikostjo preseka in velikostjo unije @wiki_jaccard_index:
|
||
$ J(A, B) = frac(|A #sym.inter B|, |A #sym.union B|) $
|
||
|
||
=== Nizovne in poravnalne mere
|
||
*Hammingova razdalja* meri število mest, na katerih se zaporedji enake dolžine razlikujeta @wiki_hamming_distance. Ker je pri nas gen en bajt, primerjamo bajte in ne posameznih bitov:
|
||
$
|
||
d(p, q) & = |{i : p_i != q_i}| \
|
||
s & = 1 - frac(d(p, q), n)
|
||
$
|
||
|
||
*Levenshteinova razdalja* je najmanjše število vstavitev, izbrisov in zamenjav, potrebnih za pretvorbo enega zaporedja v drugo @wiki_levenshtein_distance. Računa se z dinamičnim programiranjem in ima časovno zahtevnost $O(n^2)$, kar je pri $n = 180$ opazno počasneje od ostalih mer.
|
||
|
||
*Needleman-Wunschev algoritem* je postopek globalne poravnave zaporedij iz bioinformatike, prav tako zasnovan na dinamičnem programiranju @wiki_needlemanwunsch_algorithm. Vsaki možni poravnavi dodeli oceno glede na izbrane nagrade za ujemanje ter kazni za neujemanje in vrzeli, rezultat pa je poravnava z najvišjo oceno.
|
||
|
||
#align(center)[
|
||
#figure(caption: [Pregled preučenih mer])[
|
||
#table(
|
||
columns: 4,
|
||
align: (left, left, left, left),
|
||
table.header([Mera], [Družina], [Časovna zahtevnost], [Testirana]),
|
||
table.hline(),
|
||
[Evklidska razdalja], [geometrijska], [$O(n)$], [da],
|
||
[Skalarni produkt], [geometrijska], [$O(n)$], [da],
|
||
[Kosinusna podobnost], [geometrijska], [$O(n)$], [da],
|
||
[Kosinusna varianta], [geometrijska], [$O(n)$], [da],
|
||
[Jaccardov indeks], [množična], [$O(n)$], [ne],
|
||
[Hammingova razdalja], [nizovna], [$O(n)$], [da],
|
||
[Levenshteinova razdalja], [poravnalna], [$O(n^2)$], [da],
|
||
[Needleman-Wunschev alg.], [poravnalna], [$O(n^2)$], [ne],
|
||
)
|
||
]<tabela_mere>
|
||
]
|
||
|
||
Razloga, zakaj Jaccardovega indeksa in Needleman-Wunschevega algoritma nismo testirali, sta navedena v @odlocitev_mera.
|
||
|
||
== Testiranje algoritmov
|
||
Mere smo primerjali na sejah evolucije, shranjenih v podatkovni bazi aplikacije. Na voljo smo imeli tri seje; vsaka je bila izpeljana do dvanajste generacije, torej obsega 13 generacij (0--12) in 208 uporabnikovih ocen, skupaj 624 ocen. Vse mere so bile izračunane na istih, že posnetih generacijah, tako da so med seboj neposredno primerljive.
|
||
// TODO: dopolniti, kdo je izvedel te tri seje (avtor / testni uporabniki) -- mentorjevo vprašanje "Kdo je testiral?"
|
||
|
||
V nadaljevanju so prikazani rezultati seje, katere slike vseh generacij so v prilogi. Za to sejo @tabela_vsecki_gen prikazuje tudi, koliko osebkov je uporabnik v posamezni generaciji označil kot všečne, saj je od tega odvisno, katera veja postopka tvorjenja nove generacije se je izvedla (@genetski_algoritem).
|
||
|
||
#align(center)[
|
||
#figure(caption: [Število všečkanih osebkov po generacijah (od 16)])[
|
||
#table(
|
||
columns: 14,
|
||
table.header([Generacija], [0], [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12]),
|
||
table.hline(),
|
||
[Všečkani], [4], [3], [11], [14], [12], [15], [16], [1], [2], [4], [2], [7], [11],
|
||
)
|
||
]<tabela_vsecki_gen>
|
||
]
|
||
|
||
=== Testno okolje
|
||
Algoritmi so bili testirani na računalniku z AMD Ryzen 5 5500U procesorjem in 16 GB rama. Vsak algoritem je bil zagnan petkrat in podatki so povprečje rezultatov.
|
||
|
||
=== Rezultati podobnosti
|
||
|
||
#align(center)[
|
||
#figure(caption: [Rezultati podobnosti])[
|
||
#table(
|
||
columns: 7,
|
||
table.header(
|
||
[Generacija],
|
||
[Evklidska],
|
||
[Skalarni produkt],
|
||
[Kosinusna],
|
||
[Kosinusna variacija],
|
||
[Hamming-ova],
|
||
[Levenshte-inova],
|
||
),
|
||
table.hline(),
|
||
[0], [58.835], [25.4743], [75.0422], [0.19221], [0.449075], [50.3356],
|
||
[1], [63.2906], [27.6056], [80.0648], [22.6274], [22.8889], [61.4676],
|
||
[2], [67.9607], [29.0597], [84.9029], [41.0515], [44.9491], [72.4768],
|
||
[3], [68.5758], [29.181], [85.409], [42.257], [46.75], [73.375],
|
||
[4], [68.7648], [29.1488], [85.5507], [42.8455], [46.8519], [73.4259],
|
||
[5], [69.4333], [29.2939], [86.089], [44.4245], [48.463], [74.2315],
|
||
[6], [68.6623], [28.8901], [85.3302], [41.7158], [46.6667], [73.3333],
|
||
[7], [68.3941], [28.7663], [85.0723], [40.4149], [44.9213], [72.4606],
|
||
[8], [64.988], [28.0012], [82.0021], [28.3094], [27.3796], [63.6898],
|
||
[9], [73.4526], [27.977], [88.825], [57.7922], [59.213], [79.6065],
|
||
[10], [77.0616], [29.2913], [91.6422], [68.0308], [67.3981], [83.6991],
|
||
[11], [82.7646], [31.4961], [95.4701], [81.8052], [81.8981], [90.9491],
|
||
[12], [82.313], [31.8334], [95.2544], [80.7246], [80.7778], [90.3889],
|
||
)
|
||
]
|
||
]
|
||
|
||
#import "@preview/lilaq:0.5.0" as lq
|
||
|
||
#let xs = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
|
||
#let se = (58.835, 63.2906, 67.9607, 68.5758, 68.7648, 69.4333, 68.6623, 68.3941, 64.988, 73.4526, 77.0616, 82.7646, 82.313)
|
||
#let sd = (25.4743, 27.6056, 29.0597, 29.181, 29.1488, 29.2939, 28.8901, 28.7663, 28.0012, 27.977, 29.2913, 31.4961, 31.8334)
|
||
#let scs = (75.0422, 80.0648, 84.9029, 85.409, 85.5507, 86.089, 85.3302, 85.0723, 82.0021, 88.825, 91.6422, 95.4701, 95.2544)
|
||
#let scsv = (0.19221, 22.6274, 41.0515, 42.257, 42.8455, 44.4245, 41.7158, 40.4149, 28.3094, 57.7922, 68.0308, 81.8052, 80.7246)
|
||
#let sh = (0.449075, 22.8889, 44.9491, 46.75, 46.8519, 48.463, 46.6667, 44.9213, 27.3796, 59.213, 67.3981, 81.8981, 80.7778)
|
||
#let sl = (50.3356, 61.4676, 72.4768, 73.375, 73.4259, 74.2315, 73.3333, 72.4606, 63.6898, 79.6065, 83.6991, 90.9491, 90.3889)
|
||
|
||
#align(center)[
|
||
#figure(caption: [Podobnost znotraj generacije po posameznih merah])[
|
||
#lq.diagram(
|
||
legend: (position: (100% + .5em, 0%)),
|
||
height: 200pt,
|
||
width: 300pt,
|
||
xlabel: "Generacija",
|
||
ylabel: "Podobnost v %",
|
||
lq.plot(xs, se, mark: none, label: [Evklidska]),
|
||
lq.plot(xs, sd, mark: none, label: [Skalarni produkt]),
|
||
lq.plot(xs, scs, mark: none, label: [Kosinusna]),
|
||
lq.plot(xs, scsv, mark: none, label: [Kosinusna variacija]),
|
||
lq.plot(xs, sh, mark: none, label: [Hammingova]),
|
||
lq.plot(xs, sl, mark: none, label: [Levenshteinova]),
|
||
)
|
||
]<graf_podobnost>
|
||
]
|
||
|
||
#pagebreak()
|
||
=== Čas računanja podobnosti v μs
|
||
#align(center)[
|
||
#figure(caption: [Čas računanja podobnosti])[
|
||
#table(
|
||
columns: 7,
|
||
table.header(
|
||
[Generacija],
|
||
[Evklidska],
|
||
[Skalarni produkt],
|
||
[Kosinusna],
|
||
[Kosinusna variacija],
|
||
[Hamming-ova],
|
||
[Levenshte-inova],
|
||
),
|
||
table.hline(),
|
||
[0], [91], [41], [117], [181], [87], [105799],
|
||
[1], [60], [40], [78], [305], [250], [100331],
|
||
[2], [61], [40], [78], [121], [105], [97438],
|
||
[3], [66], [40], [81], [124], [106], [97529],
|
||
[4], [60], [40], [78], [127], [108], [96296],
|
||
[5], [62], [39], [85], [131], [104], [96456],
|
||
[6], [61], [40], [81], [125], [106], [96510],
|
||
[7], [61], [40], [81], [125], [103], [97253],
|
||
[8], [61], [40], [81], [125], [78], [97409],
|
||
[9], [60], [40], [82], [125], [103], [99816],
|
||
[10], [62], [40], [81], [128], [81], [98978],
|
||
[11], [68], [40], [81], [126], [58], [98289],
|
||
[12], [61], [39], [88], [130], [60], [99663],
|
||
)
|
||
]
|
||
]
|
||
|
||
#let ts = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
|
||
#let te = (91, 60, 61, 66, 60, 62, 61, 61, 61, 60, 62, 68, 61)
|
||
#let td = (41, 40, 40, 40, 40, 39, 40, 40, 40, 40, 40, 40, 39)
|
||
#let tcs = (117, 78, 78, 81, 78, 85, 81, 81, 81, 82, 81, 81, 88)
|
||
#let tcsv = (181, 305, 121, 124, 127, 131, 125, 125, 125, 125, 128, 126, 130)
|
||
#let th = (87, 250, 105, 106, 108, 104, 106, 103, 78, 103, 81, 58, 60)
|
||
#let tl = (105799, 100331, 97438, 97529, 96296, 96456, 96510, 97253, 97409, 99816, 98978, 98289, 99663)
|
||
|
||
#align(center)[
|
||
#figure(caption: [
|
||
Čas računanja podobnosti. Levenshteinova razdalja je zaradi merila izpuščena iz prikaza; njen čas se giblje med 96 296 μs in 105 799 μs, torej približno tisočkrat nad ostalimi merami.
|
||
])[
|
||
#lq.diagram(
|
||
legend: (position: (100% + .5em, 0%)),
|
||
height: 200pt,
|
||
width: 300pt,
|
||
ylim: (0, 350),
|
||
xlabel: "Generacija",
|
||
ylabel: "Čas v μs",
|
||
lq.plot(ts, te, mark: none, label: [Evklidska]),
|
||
lq.plot(ts, td, mark: none, label: [Skalarni produkt]),
|
||
lq.plot(ts, tcs, mark: none, label: [Kosinusna]),
|
||
lq.plot(ts, tcsv, mark: none, label: [Kosinusna variacija]),
|
||
lq.plot(ts, th, mark: none, label: [Hammingova]),
|
||
)
|
||
]<graf_cas>
|
||
]
|
||
|
||
#pagebreak()
|
||
== Interpretacija konvergence <interpretacija_konvergence>
|
||
Krivulje na @graf_podobnost se med seboj razlikujejo po zalogi vrednosti, njihova oblika pa je enaka, saj vse merijo isti pojav: kako zelo se je populacija zožila. Če jih beremo skupaj s številom všečkov po generacijah (@tabela_vsecki_gen), postane razvidno, da oblike krivulje ne določa zaporedna številka generacije, temveč uporabnikove ocene, saj te izberejo vejo postopka tvorjenja nove generacije.
|
||
|
||
*Naraščanje v generacijah 2--6.* Uporabnik je v teh generacijah označil med 11 in 16 všečkov, zato je bilo staršev veliko, na novo ustvarjenih osebkov pa malo. Populacija se zato hitro poenoti in Hammingova podobnost naraste s približno 45 % na 48 %, kosinusna pa čez 86 %.
|
||
|
||
*Zastoj med generacijama 6 in 7.* V generaciji 6 je bilo všečkanih vseh 16 osebkov. Ker otroci prepišejo samo mesta nevšečnih osebkov, otrok sploh ni bilo in je na populacijo delovala le mutacija treh bajtov na osebek. Podobnost se med tema dvema generacijama praktično ne spremeni (85,3 % proti 85,1 % pri kosinusni meri).
|
||
|
||
*Padec pri generaciji 8.* V generaciji 7 je bil všečen samo en osebek. Postopek je zato uporabil vejo `clone`, ki polovico bajtov otroka nadomesti z naključnimi vrednostmi, in 15 od 16 osebkov naslednje generacije je nastalo na ta način. Podobnost posledično strmo pade, pri Hammingovi meri s 44,9 % na 27,4 %. Padec torej ni napaka meritve, ampak pričakovana posledica robnega primera v postopku.
|
||
|
||
*Strop pri približno 82 %.* Po generaciji 9 podobnost spet naraste in se pri generacijah 11 in 12 ustali okoli 82 % (Hammingova mera). Popolnega ujemanja postopek ne more doseči, ker se mutacija izvede tudi na všečnih osebkih: vsak osebek v vsaki generaciji dobi tri naključne bajte, zato v populaciji vedno ostane nekaj razlik.
|
||
|
||
Iz tega je razvidno, da je mera razdalje uporabna tudi kot diagnostika postopka in ne le kot številka na zaslonu; iz njenega poteka je mogoče razbrati, katera veja postopka se je izvedla in kako močno je vplivala na populacijo. Naravno nadaljevanje tega opazovanja je merjenje hitrosti konvergence pri različnih stopnjah mutacije in različnih velikostih generacije, kar navajamo med predlogi za nadaljnje delo (@zakljucek).
|
||
|
||
#pagebreak()
|
||
== Odločitev <odlocitev_mera>
|
||
Izbrali smo Hammingovo razdaljo. Ustreza vsem štirim kriterijem iz uvoda tega poglavja: računa se neposredno nad bajti genoma, njena zaloga vrednosti je celoten razpon od 0 % do 100 %, med konvergenco narašča, izračun 120 parov pa traja približno 100 μs. Odločilna je bila zaloga vrednosti: pri naključni začetni populaciji se začne pri približno 0 % in se z zoževanjem izbire pomika proti 100 %, zato je uporabniku razumljiva brez dodatne razlage. Kosinusna podobnost je za prikaz manj primerna, ker se že pri naključni populaciji začne pri 75 %, evklidska pri 59 %, skalarni produkt pa se giblje le med 25 % in 32 %. Časov računanja pri odločitvi nismo upoštevali, saj so vse mere razen Levenshteinove pod 0,5 ms, kar je za enkraten izračun ob prehodu med generacijama zanemarljivo; Levenshteinova razdalja je s približno 100 ms na generacijo za prikaz v realnem času neuporabna.
|
||
|
||
Dveh mer nismo testirali:
|
||
|
||
- *Jaccardov indeks* deluje nad množicami unikatnih vrednosti, genom pa je zaporedje, v katerem ista vrednost na dveh različnih mestih pomeni dve različni lastnosti slike. Popolno ujemanje množic zato ne bi pomenilo, da sta sliki enaki.
|
||
- *Needleman-Wunschev algoritem* vrne oceno poravnave, ki je odvisna od izbire kazni in nagrad in nima nevtralne zgornje meje, zato je ni mogoče neposredno prikazati kot odstotek.
|
||
|
||
|
||
#pagebreak()
|
||
|
||
= Google Play Store
|
||
Da lahko objavimo aplikacijo na Google Play Store, potrebujemo Play Console razvijalski račun @web_google_play_console. Koraki za izdelavo računa so zelo enostavni: vpiši potrebne podatke, sprejmi razvojni sporazum in plačaj registracijo. Naši problemi so se začeli z vnosom podatkov, saj niso hoteli sprejeti naše telefonske številke, ker je niso mogli preveriti, ko pa smo sledili korakom za odstranjevaje težav, ki so bili večinoma samo _počakajte en dan in poskusite ponovno_, še vedno ni delovalo. Nato smo kontaktirali njihovo pomoč, ki so nam vrnili podoben odgovor, da naj čakamo. Po tem smo obupali in uporabili drugo telefonsko številko.
|
||
|
||
V naslednjih korakih moramo naložiti zapakirano aplikacijo, dodati opis applikacije, slike delovanja in politiko varstva osebnih podatkov (@privacy_policy). Po tem moramo spraviti aplikacijo čez notranje testiranje, ki je zelo nespecificirano. Generalna ideja naj bi bila, da potrebujemo 12 testerjev, ki naj bi uporabljali aplikacijo vsaj 12 dni, nikjer pa ni omenjeno, koliko časa na dan morajo uporabljati aplikacijo, da se šteje. Par tednov smo s prijatelji poskušali ugotoviti, kdaj postaneš aktiven, ampak smo bili brez uspeha. Nato smo se odločili, da bi pogledali po internetu, kako ta problem rešujejo ostali. Našli smo dve rešitvi. Prva zastonj rešitev je nekaj forumov na spletu, kjer ljudje objavljajo svoje aplikacije in ideja je, da si med sabo pomagajo s tem, da testirajo aplikacije drug drugega. Druga plačljiva, rešitev za katero smo se odločili, je, da najamemo testerja za pribljižno 20 €. S testerjem smo se zmenili, kaj potrebujemo, in po izmenjavi potrebnih podatkv je po dveh tednih aplikacija testirana in lahko nadaljuje na zadnji pregled pred objavo.
|
||
|
||
Ob zadnjem pregledu je postalo zelo naporno. Opis naše aplikacije je navdihnil opis aplikacije Tinder, saj sta aplikaciji konceptno zelo podobni (@zacetni_opis). Takrat so pri Googlu začeli natančno pregledovati aplikacijo, ker do takrat je bilo vsakič, ko smo poslali aplikacijo v pregled, vse odobreno do naslednjega dne, tokrat pa je trajalo nekaj tednov. Njihov odgovor je bil, da opis naše aplikacije ni primeren in krši pravila, čeprav je bil zelo podoben Tindrovemu. Pri tem smo ugotovili, da se je ekipa, ki je to pregledovala, vedla precej pristransko. V skladu z navodili, ki so nam jih poslali, smo popravili vse kršitve pravil. Tako se je ponovilo še nekajkrat, kar je skupaj trajalo skoraj štiri mesece. Zadnja verzija je @koncni_opis.
|
||
|
||
Po vsem tem je aplikacija končno objavljena na Play Store @web_google_treender.
|
||
|
||
|
||
#figure(caption: [Začetni opis])[
|
||
#set align(left)
|
||
|
||
*ROOT FOR LOVE, BRANCH OUT & LEAF A MARK. IT ALL STARTS WITH A SWIPE.*
|
||
|
||
With countless matches and growing, Treender is the top free app for tree enthusiasts and nature lovers. Whether you're looking for a leafy companion, a blossoming friendship, or a deep-rooted relationship, Treender is the place to connect with fellow tree admirers. Our app offers leading safety features to ensure you can explore your love for trees safely.
|
||
|
||
*Come As You Are: Whether you're a mighty oak, a graceful willow, or a playful pine, be true to your roots and find your perfect match.*
|
||
|
||
*Branch Out: Share your interests and discover more about your matches to start meaningful conversations.*
|
||
|
||
*Seek What You're Looking For: Set your relationship goals and find your perfect tree mate on your terms.*
|
||
]<zacetni_opis>
|
||
|
||
#line()
|
||
|
||
#figure(caption: [Končni opis])[
|
||
#set align(left)
|
||
|
||
Welcome to Treender, an innovative undergraduate thesis project that combines the fun of swiping with the beauty of fractal trees. Dive into a world where fractal trees become your potential matches, and your swipes shape their evolution.
|
||
|
||
How It Works:
|
||
|
||
- Swipe Right to Like: Admire a fractal tree? Swipe right to like it and watch it evolve based on your preferences.
|
||
- Swipe Left to Pass: Not feeling a connection? Swipe left to pass and continue your journey through the forest of possibilities.
|
||
- Evolve Your Matches: As you interact with the trees, they adapt and grow, reflecting your unique tastes and preferences.
|
||
- Aim for Perfection: Your goal is to get your match percentage as close to 100% as possible, creating a personalized fractal tree that's uniquely yours.
|
||
|
||
]<koncni_opis>
|
||
|
||
#pagebreak()
|
||
|
||
#text(size: 18pt, weight: "bold")[PRIVACY POLICY]
|
||
|
||
At Treender, we are committed to protecting your privacy and ensuring the security of any data we collect. This Privacy Policy outlines our practices regarding the collection, use, and protection of user data.
|
||
|
||
#text(size: 16pt, weight: "bold")[1 Data Collection]
|
||
|
||
#text(size: 14pt)[1.1 Sensitive Data]
|
||
|
||
Our service/application does not collect any sensitive data about users. Sensitive data includes, but is not limited to:
|
||
|
||
- Personal information (e.g., names, addresses, phone numbers, email addresses)
|
||
- Financial data (e.g., credit card numbers, bank account details)
|
||
- Health information (e.g., medical records, health status)
|
||
|
||
#text(size: 14pt)[1.2 Non-Sensitive Data]
|
||
|
||
Any non-sensitive data collected by Treender is used solely for the purpose of improving our service. This may include:
|
||
|
||
- Usage statistics
|
||
- Performance metrics
|
||
- Anonymous feedback
|
||
|
||
#text(size: 16pt, weight: "bold")[2 Data Sharing]
|
||
|
||
We do not share user data with third parties. Your data remains confidential and is used only to enhance your experience with Treender.
|
||
|
||
#text(size: 16pt, weight: "bold")[3 Security Measures]
|
||
|
||
We take the following security measures to protect any data we collect:
|
||
|
||
- *Access Controls*: Strict access controls are in place to ensure that only authorized personnel can access user data.
|
||
- *Secure Storage*: Data is stored in secure servers with robust physical and digital security measures.
|
||
|
||
#text(size: 16pt, weight: "bold")[4 User Rights]
|
||
|
||
You have the following rights regarding your data:
|
||
|
||
- *Access*: You can request access to the data we hold about you.
|
||
- *Correction*: You can request that we correct any inaccuracies in your data.
|
||
- *Deletion*: You can request that we delete your data from our systems.
|
||
- *Objection*: You can object to the processing of your data for specific purposes.
|
||
|
||
#text(size: 16pt, weight: "bold")[5 Contact Information]
|
||
|
||
If you have any questions or concerns about our Privacy Policy or the data we collect, please contact us at:
|
||
|
||
*Email*: email
|
||
|
||
We value your privacy and are committed to protecting your data. Thank you for using Treender.
|
||
|
||
#line(length: 100%)
|
||
|
||
This Privacy Policy is effective as of February 26, 2025. We reserve the right to update this policy as needed to reflect changes in our practices or legal requirements.
|
||
|
||
#figure(caption: [Privacy Policy])[]<privacy_policy>
|
||
#pagebreak()
|
||
|
||
= UPORABNIŠKE IZKUŠNJE
|
||
|
||
Po tem, ko smo objavili aplikacijo na Play Store, smo prosili prijatelje in sodelavce, naj poskusijo aplikacijo. Med uporabo so naleteli na nekaj pričakovanih in nepričakovanih problemov.
|
||
|
||
== Ni intuitivno, kako uprabljati aplikacijo
|
||
Uporabnikom ni bilo jasno, kako uporabiti aplikacijo, ni jim bilo, jasno da lahko povlečejo sliko levo ali desno, da označijo, ali jim je všeč ali ne. Da rešimo to, lahko ob prvem zagonu aplikacije prikažemo animacijo, kako lahko premikajo sliko po zaslonu.
|
||
|
||
== Nepričakovani rezultati <nepricakovani_rezultati>
|
||
Po razlagi, kako uporabljati aplikacijo, jim ni bilo jasno, zakaj na drevesih in v prikazanem odstotku niso videli sprememb. Glavni razlog je majhno število osebkov na generacijo (16), saj iz 16 binarnih ocen težko izluščimo, katera lastnost slike je uporabniku všeč. Večje generacije med razvojem nismo uporabili, ker traja predolgo, da uporabnik pride skozi generacijo in vidi učinek svojih ocen; kompromis je opisan v @izbira_parametrov.
|
||
|
||
Pokazala se je še ena razlika. Ker smo poznali delovanje postopka, aplikacije med razvojem nismo uporabljali kot uporabnik: namesto celotnega videza slike smo ocenjevali posamezne lastnosti, na primer barvo ali gostoto vej. Nekateri uporabniki so to sami ugotovili in s takim načinom ocenjevanja prišli do vidno lepših dreves, drugi pa ne, kar kaže, da bi aplikacija ta način dela morala nakazati sama.
|
||
|
||
== Moteč rezultat podobnosti <moteca_podobnost>
|
||
Nekaj uporabnikov je sporočilo, da jih je motilo, ker jim ni uspelo doseči 100 %. Vzrok je v postopku: mutacija se izvede tudi na všečnih osebkih, zato se populacija ne more povsem poenotiti in vrednost se ustali okoli 82 % (@interpretacija_konvergence). Moteč je torej tudi način prikaza, saj prikazana vrednost ni ocena všečnosti, ampak mera konvergence populacije, uporabnik pa jo razume kot cilj, ki ga je treba doseči. Rešitev je dvojna: količino poimenovati tako, kot deluje (na primer "ujemanje z vašim izborom"), in prikazano vrednost raztegniti čez celoten razpon do dejansko dosegljivega maksimuma.
|
||
|
||
== Vsiljena barvna paleta <vsiljena_paleta_ref>
|
||
Barve dreves in ozadja so del genoma in so v prvi generaciji naključne, zato uporabnik na začetku ne more vplivati na osnovni videz slik. Če mu prikazane barvne kombinacije ne ustrezajo, ocenjuje slike, med katerimi mu nobena ni všeč, in njegove ocene so za postopek šum in ne signal. Podatki to potrjujejo: v prvih dveh generacijah analizirane seje je bilo všečkanih le 4 oziroma 3 od 16 osebkov (@tabela_vsecki_gen), medtem ko jih je bilo v generacijah 3--6 med 11 in 16.
|
||
|
||
Razlog za tako zasnovo je bil, da naj evolucija zajame celotno sliko; če bi uporabnik barve izbral vnaprej, bi iz iskalnega prostora izpadli geni `colorR`, `colorG`, `colorB`, `colorVar` in `colorSet`, torej približno tretjina genoma, in vpliv evolucije na končni videz bi bil bistveno manjši. Primernejša rešitev, ki je nismo izvedli, je uvodni korak: uporabnik najprej izbere barvno paleto drevesa in ozadje, aplikacija ta del genoma zamrzne, evolucija pa nato deluje na obliki drevesa. Alternativa brez dodatnega koraka je prva generacija z namenoma čim bolj razpršenimi paletami, tako da uporabnik že v prvi generaciji vidi celoten razpon možnih barvnih shem.
|
||
|
||
== Zgodovina
|
||
Uporabniki so želeli zgodovino. To bi bilo dokaj enostavno dodati, saj hranimo celotno stanje aplikacije v sistemu, da lahko stanje preživi izklop aplikacije ampak se med izdelavo nismo spomnili, da bi dodali zgodovino.
|
||
|
||
|
||
#pagebreak()
|
||
|
||
= IZKUŠNJE
|
||
Izkušnje, ki smo jih pridobili med izdelavo aplikacije.
|
||
|
||
== Strežnik in podatkovna baza
|
||
Med izdelavo aplikacije smo izdelali _sistem strežnik in odjemalec_, da smo lahko pridobili podatke o uporabnikih in njihovih preferencah. To nas je naučilo nekaj stvari.
|
||
|
||
- Omeji število prejetih podatkov na povezavo, da senemore nekdo samo povezati in začeti pošiljati naključnih podatkov.
|
||
- Omeji, kdo se lahko poveže z uporabo nekega skrivnostnega ključa ali z registracijo.
|
||
- Uporabi prepovedni sistem, če se odjemalec ne obnaša lepo mu prepovej povezavo na strežnik.
|
||
- Med filtriranjem podatkov v podatkovni bazi nikoli ne briši samo označi, da je izbrisano.
|
||
- Naj odjemalec pošlje vse podatke na enkrat.
|
||
- Imej paritetne kode
|
||
|
||
Naš sistem je bil tako narejen, da je imel vsak odjemalec skrivno številko, ki jo je uporabil pri komunikaciji, ampak smo še vedno naleteli na to, da se je lahko nekdo naključno povezal na strežnik in je zadel število, in ker nismo imeli dobre filtracije podatkov, se je vse, kar nam je poslal, direktno shranjevalo v bazo. Bilo bi dobro, da imamo paritetne kode na koncu sporočila, da vemo, ali je sporočilo validno. Ko nam je zlonamerni odjemalec napolnil bazo, smo se odločili, da bomo odstranili vse podatke, ki ne sledijo pravilni evoluciji, in ker smo imeli napako v kodi, smo zbrisali celotno bazo podatkov. Med testiranjem smo našli tudi par primerov, kjer se sporočila niso prenesla v celoti.
|
||
|
||
#pagebreak()
|
||
== Gradilni sistem <gradilni_sistem>
|
||
Začeli smo z enostavno Makefile datoteko, kjer smo vse enostavno kompilirali skupaj.
|
||
|
||
```Makefile
|
||
gcc -c raylib.c -o raylib.o
|
||
g++ -c main.cpp -o main.o
|
||
g++ main.o raylib.o -o main
|
||
```
|
||
|
||
To je čez čas postalo kar naporno za upravljanje, ko se je število datotek povečevalo in razvijali smo na dveh operacijskih sistemih (Linux in Windows). Potem smo naredili največjo napako. Navdihnil nas je tsoding nob.h @git_nob in odločili smo se da, bomo napisali svojo skripto za gradnjo, ki bo pravilno izbrala pravi prevajalnik g++ za Linux in zig c++ za Windows. To je delovalo precej dobro, vendar smo sčasoma več časa porabili za skripto kot za naš projekt.
|
||
|
||
Prišlo je do točke, kjer:
|
||
- je skripta lahko izvajala ukaze,
|
||
- preverjala, če se je skripta spremenila, in se je nato sama ponovno zgradila,
|
||
- smo lahko dodali inkrementalno gradnjo projekta,
|
||
- je skripta lahko prenesla in kompilirala raylib,
|
||
- smo na koncu celo lahko dodali, da lahko skompilira vse datoteke v direktoriju.
|
||
|
||
Nato smo morali dodati še gradnjo enega programa, kar je bilo mogoče z našo skripto, vendar nas je motilo, koliko časa smo porabili za vzdrževanje skripte. Odločili smo se, da bomo poskusili CMake, ki je prvo gradnjo malo počasneje saj smo morali samo prenesti raylib in druge odvisnosti, vendar je bilo vse ostalo popolno in je preprosto delovalo.
|
||
|
||
|
||
|
||
#pagebreak()
|
||
|
||
= ZAKLJUČEK <zakljucek>
|
||
|
||
V tej diplomski nalogi smo razvili aplikacijo Treender, ki uporabnikom omogoča interaktivno vodenje evolucije fraktalnih dreves z uporabo genetskih algoritmov in preprostih uporabniških gest. Cilj projekta je bil raziskati, kako lahko kombinacija algoritmov in uporabniških ocen ustvarja osebne in dinamične izkušnje.
|
||
|
||
Za razvoj smo uporabljali tehnologije, kot so C++, Raylib in SQLite3, ki so omogočile učinkovito delovanje in vizualizacijo. Ključni izziv je bila optimizacija algoritmov za generiranje in risanje dreves, ki smo ga rešili z risanjem na teksturo in omejevanjem števila risalnih klicev. Ugotovili smo, da je pomembno, da je uporabniški vmesnik intuitiven, saj so uporabniki na začetku težko razumeli osnovne funkcije, kot je ocenjevanje z vlečenjem slike.
|
||
|
||
Za merjenje podobnosti med drevesi smo izbrali Hammingovo razdaljo, ker se računa neposredno nad genomom, pokrije celoten razpon od 0 % do 100 % in je dovolj hitra za izračun ob vsaki novi generaciji. Pri tem smo ugotovili, da ta količina ne meri všečnosti, ampak konvergenco populacije, torej to, kako zelo se je uporabnikova izbira zožila. Prav zato jo je mogoče uporabiti tudi kot diagnostiko postopka: iz poteka krivulje je razvidno, katera veja tvorjenja nove generacije se je izvedla in kako močno je vplivala na populacijo. Objava aplikacije na Google Play Store je zahtevala prilagoditve opisa in politike zasebnosti, da smo ustrezali zahtevam platforme.
|
||
|
||
Projekt je dosegel zastavljene cilje: uporabnikom omogoča, da s 16 potezami na generacijo usmerjajo videz fraktalnih dreves, ne da bi morali svoj okus opisati z besedami ali nastavljati parametre. Hkrati je pokazal tudi omejitve izbrane zasnove. Za nadaljnje delo se kot najbolj obetavni kažejo štirje koraki:
|
||
|
||
- uvodna izbira barvne palete in ozadja, ki odpravi težavo hladnega zagona (@vsiljena_paleta_ref);
|
||
- prilagodljiva stopnja naključnosti, ki je v prvih generacijah večja, da uporabnik hitro vidi celoten razpon možnosti, nato pa se manjša za natančnejše uravnavanje podrobnosti;
|
||
- eksperimentalno določanje velikosti generacije in stopnje mutacije z merjenjem hitrosti konvergence, namesto sedanjih vrednosti, izbranih med razvojem (@izbira_parametrov);
|
||
- zgodovina prikazanih dreves in preimenovanje prikazane podobnosti v skladu s tem, kar dejansko meri.
|
||
#pagebreak()
|
||
|
||
#bibliography("citations.bib", title: [VIRI IN LITERATURA], style: "ieee.csl")
|
||
|