Imagenetics: Dokumentace (EVO projekt)

Tato stránka popisuje a dokumentuje Imagenetics, projekt do předmětu EVO.

Autor: Ondřej Žižka, xzizka06

Zadání

Zadáním projektu bylo:

Vytvořit systém pro evoluční návrh obrázků s grafickým rozhraním	splněno
Kandidátní obrázky má ohodnocovat manuálně uživatel podle svého estetického citu	splněno
V chromozomu má být zakódován předpis pro generování obrázku	splněno

Genetika

Cíl tohoto projektu byl od běžných aplikací genetických algoritmů zvláštní v tom, že fitness funkce nebyla dána výpočtem - předpisovou funkcí, ale estetickým cítěním uživatele. Uživatel v každé generaci ohodnotí jedince podle toho, jak se mu líbí, přičemž nelze spolehnout na plánovitý úsudek.

Z toho plyne:

• K dispocici bude nedeterministické hodnocení, které nenese příliš informací o kvalitě celé populace.
• Nejlépe hodnocení jedinci mohou mít geneticky "blízko" k těm špatně hodnoceným: u dvacátého jedince (obrázku) může uživatele jednoduše přestat bavit hodnotit další obrázky, proto je nechá neohodnocené; to se rovná ponechání nejhoršího možného hodnocení (nulová pochvala).
• Na evoluci bude prostor pouze několika málo generací, řádově maximálně desítky. Většinu lidí (včetně autora) přestane bavit hodnotit dvacet jedinců nejpozději po několika desítkách generací.
• Hodnocení pravděpodobně nebude vykazovat korelaci s prvky obrázku.

Řešení:

• Co nejlépe využít informaci, kterou nás uživatel obdařil. Budeme předpokládat, že obrázek, který už jednou ohodnotil dobře, se mu líbí trvaleji (tzn. i v dalších kolech).
• Neohodnocené obrázky opustíme jako nehezké a budeme se věnovat těm pochváleným. Tím by se však velice brzy z populace ztratila diverzita. Na vytvoření dostatečně odlišných jedinců nestačí mutace - pokud by byla úroveň mutace dost velká na to, aby vytvořila vizuálně odlišný obrázek, potomci by se od rodičů lišili příliš - někdy až k nepoznání. Změna by tak byla příliš veliká na to, aby se zachovaly rysy toho, co se uživateli líbílo u rodičů. Je proto nutné do populace neustále dodávat "svěží vítr", zde v podobě zcela náhodně vygenerovaných jedinců v každé generaci.
• Na druhou stranu z důvodu nutnosti rychlého vývoje není možné nastavit malou úroveň mutace; je třeba aspoň taková, aby se z jedné generace na druhou z rodičů vygenerovaly obrázky dostatečně odlišné na to, aby postihly oblast, která by potenciálně mohla obsahovat směr estetického vkusu uživatele. Např. posun od červené k vínové barvě, posun od čtverce k protáhlému obdélníku, otočení o 30 stupňů apod.
• Původně byl záměr implementovat přenášení hodnocení z obrázku na obrázek, a to takto:

  Z uživatelem oceněných jedinců se vyjme chromozom a jeho jednotlivé geny se hledají v generaci u ostatních jedinců. Jedincům, kteří obsahují podobný gen, je přidána část hodnocení oceněného jedince.

  Od tohoto záměru však bylo upuštěno, protože při prvních pokusech vyšlo najevo, že uživateli se nelíbí konkrétní fenotypový projev genu, ale jejich celková harmonie, podobně jako se posluchači hudby nelíbí jednotlívé tóny, ale harmonie jejich sledu.

• Nemá smysl provádět pokusy s různými modely a principy křížení. Výše uvedené potvrzuje, že nejvhodnějším přístupem je analýza jevů jako je estetický cit uživatele, zkoumání, co dělá hezký obrázek hezkým, atd, čímž odvodíme nejlepší způsob vzniku nové generace.

Fitness funkce

Na základě výše shrnuté analýzy byla fitness funkce určena takto:

Každý jedinec bude mít fitness points, tedy jakési dosažené skóre. To si bude pamatovat v průběhu života. Body získává, když uživatel kladně ohodnotí obrázek, který jedinec představuje. Body ubývají s každou další generací po konstatním množství. Takto zůstávají oblíbení (vícekrát ocenění) jedinci stále v populaci, zatímco jednorázově kladně ohodnocení časem uvolní místo lepším jedincům.

Potomci dědí část skóre po rodičích. Je pravděpodobné, že potomek po dvou lépe hodnocených rodičích se uživateli líbí více než potomek po hůře hodnocených rodičích. Potomek dědí od každého z rodičů konstantní podíl skóre, maximálně polovinu, jinak by byl ihned po vzniku lepší než oba rodiče, což není žádoucí.

Selekce

Selekce byla podřízena typu úlohy. Jak bylo uvedeno výše, bohužel si nemůžeme dovolit ztrácet vzácné informace od uživatele a vybírat na základě principů typu ruleta či turnaj. Musíme vybírat maximálně po vůli uživatele. Jako způsob selekce byl proto vybrán ten nejjednodušší, tedy seřazení sestupně podle fitness a vybrání prvních X nejlepších.

Jako rodiče pro potomky do další generace je vybrán určitý díl populace. Pro každého z nich je určen bod křížení, který si dále pamatuje. Potom jsou vytvořeni potomci křížením dvojic rodičů klasickým jednobodovým křížením - navzájem se "prohodí" části od bodu křížení ke kraji.

Potom je původní populace zredukována na několik nejlepších jedinců, kteří postupují do další generace. Předpokládáme, že uživatel chce obrázky, které se mu líbily, vidět i v další generaci. Také je nejspíš chce vidět v nezměněné podobě, proto neprojdou mutací - prostor změnám dáme v potomcích.

Na potomky vzniklé křížením aplikujeme mutaci. Síla mutace musí být vyvážená, viz výše.

Nakonec je populace doplněna na původní počet několika jedinci, kteří jsou vygenerování náhodně. Tento krok je důležitý, neboť obrázky jsou natolik rozmanité, že bez náhodně vygenerovaných jedinců by se vývoj populace zacyklil v obměňování stále stejných prvků, jen tu a tam pozměněných mutací. Náhodně generovanými jedinci dáváme uživateli šanci "zatáhnout" do populace (a tím mezi potenciální rodiče) nové prvky, které vnesou do obrázků podle jeho estetického cítění žádoucí efekt.

Implementace

Aplikace Imagenetics je napsána v jazyce Java pro platformu J2SE s využitím objektových principů jazyka. Ve stručnosti:

Třídy implementující GA

Třída Population představuje populaci s kolekcí jedinců a dále vlastnostmi populace, jako např. parametry selekce a parametry mutace, počet uběhlých generací. Dále poskytuje operace nad populací, zejména křížení, selekci a mutaci.

Třída Individual implementuje jedince s chromozomem (kolekcí genů). Poskytuje operace nad jedicem - úpravu fitness, mutaci, a statické metody pro vytvoření jedince na základě chromozomu či náhodně.

Třída Primitive představuje jednotlivé prvky obrázku, zároveň tvoří jeden gen. Obsahuje zejména vlastnosti a operace pro křížení a mutaci, a dále metody implementačního charakteru, používané pro vykreslování. Používá pomocnou třídu Gene pro reprezentaci genů.

Třídy zajišťující grafické rozhraní

Třída Imagenetics je hlavní třídou programu a obsahuje formulář hlavního okna.

Třídy ControlPanel a GalleryPanel vykreslují prvky hlavního okna - ovládací panel a galerii obrázků.

Třída IndividualPanel zajišťuje funkčnost jednotlivých prvků v galerii; je GUI analogií jedince. Umožňuje jedince ohodnotit comboboxem. Dále vykresluje jeho fitness zeleným pruhem nad obrázkem a stáří šedým pruhem po straně.

Třída ImagePanel zobrazuje obrázek sestávající z řady primitiv popsaných geny jedince.

Výsledky

Podařilo se vytvořit program demonstrující aplikaci genetických algoritmů na vývoj obrázků. S minimem informace od uživatele se daří přizpůsobovat vzhled obrázků jeho preferencím, i když v míře omezené možnostmi vykreslování danými knihovnou Swing.

Nakonec několik obrázků z praxe:

První generace. Pochválili jsme obrázky, které se nám líbí.

Druhá generace. Je vidět, jak se populace seřadila podle fitness. Objevil se první zkřížený jedinec bez mutací, náhodou zrovna pouhá kopie - bod křížení u druhého rodiče byl na kraji.

Pátá generace - již jsou zřetelně vidět jedinci vzniklí křížením zejména prvního, třetího a čtvrtého rodiče.