Příspěvky

31

Vývoj / Re:Cartesian genetic programming - pomoc

« kdy: 26. 12. 2019, 20:24:55 »

Nevadí, i tak děkuji za vynaloženou snahu, obávám se, že mi nic jiného nezbude, než to opravdu probrat s garantem po svátcích :/

Tohle fakt neznam. Podle tohodle popisu nerozumim tomu, co se deje s ne-nejlepsima jedincema z predchozi generace. Zahodi se? Tj. kazda dalsi generace vychazi jenom z toho jednoho nejlepsiho jedince? To by mi prislo hodne divny a nedivil bych se, ze to nekonverguje...

Ano, také se mi to moc nezdá, ale pokud nevznikl někde informatický šum, tak to tak bude. Vždy se vybere nejlepší jedinec z těch řekněme 5 a ten se dál mutuje, s tím, že to stále může být ten stejný obvod, co byl jako první.

(osobně si to představuji jako, že zkouším náhodně mutovat tak dlouho až se mi to podaří na tom mém daném obvodě a najdu tak řešení. plus mínus autobus a slon k tomu )

Popravde, z toho popisu uplne presne nerozumim tomu kodovani a nemam ted uplne cas se nad tim hloubeji zamyslet. Mas teda matici 5x5, na kazde pozici je nejaka logicka funkce a ty funkce muzou byt mezi sebou libovolne propojeny? Pricemz do nekterych obvodu vubec nevede cesta ze vstupu, coz je zamer ("geny bez exprese").  Chapu to spravne?

Pokud jo, je tohle cesta, kterou ti doporucil garant, popr. kterou jsi nasel v literature? Prijde mi to totiz (na prvni pohled) docela neprakticky - mas obrovskej stavovej prostor (relativne velkej genom), pricemz velky oblasti prostoru budou z hlediska fitness ekvivalentni (mutace v neexpresivni casti genomu). Samo tohle mi prijde, ze celkem logicky vede na strasne pomalou konvergenci. Kdybych mel tohle napsat, ciste od stolu bych zvolil kratkej genom s daleko mensim procentem neexpresivnich genu - treba dva chromozomy, v jednom seznam funkci, ve druhym seznam jejich propojeni. Krizeni pak samozrejme jenom mezi prislusnymi chromozomy. Pak by totiz treba pro tu 5-bitovou paritu stacil kratkej genom, kterej by se mel najit relativne rychle... Ten pristup s matici mi prijde zvlastni.

Ale to ber jako ciste laickej udiv, bez toho, abych mel konkretne tohle CGP nastudovany. Jestli se to pouziva, tak to urcite nejakou logiku ma. Ale mozna to ma taky svoje specificky problemy, ktery musis holt umet resit S tim fakt nepomuzu, to by mel ten, kdo ti to doporucil...

https://imgur.com/IKgtvgv takto zhruba vypadá pro představu ta má matice a logické hradla. Parita 5 jde realizovat pomocí 4 hradel XOR. A stavový prostor je opravdu obrovský, zde právě CGP naráží. Při velkém počtu vstupů a výstupů už to nalézt trvá až moc dlouho a je to relativně známý problém, nicméně stále taková 3 bitová sčítačka jde najít řekněme v řádech minut, násobička v řádech nízkých desítek. Používají se i různé optimalizace, že se sleduje, tam kde se mutuje, nebo lepší zakódování, atd. (to jen tak mimo pro info).


Osobně mi tento "lambda algoritmus" taky lehce smrdí... a celou dobu jsem v hlavě měl představu spíše toho, že tam budu dělat nějaký výběr ruletou, případně elitismus apod. Ale bylo mi to tak něják doporučeno, tak jsem to přijal jako dobrou radu...


Menší odbočka a "pochlubení se" pokud jsem hledal náhodně, tak paritu 5 mi to našlo asi za 5 sekund v průměru, když jsem si dostatečně pohrál s parametry, jako velikost matice, mutace, výběr po křížení, ... a pro paritu 9 jsem se dostal na nízké řády desítek sekund, což mi stále dává jistý pocit, "že to už musí snad fungovat, jen to bude prkotina".

32

Vývoj / Re:Cartesian genetic programming - pomoc

« kdy: 26. 12. 2019, 18:22:01 »

Díky za takový "sloh" Nevěděl jsem jak moc konkrétně můj dotaz položit.

Ano, nedaří se mi konvergovat k řešení (párkrát ano, ale to bylo bych řekl zanedbatelné procento odhadem 5% úspěšnost třeba? a to přisuzuji spíše dobrému RNG).

O evolučních algoritmech mám pár knížek přečteno, včetně bakalářských/diplomových prací, asi bych měl zmínit, že toto dělám jako svoji bakalářku, a chtěl jsem se pohnout přes Vánoce, tudíž nechci nikoho moc otravovat a už jsem to i řešil se svým garantem. Tím nechci říct, že se v tomto oboru vyznám. Rád si zopakuji, třeba mi něco uniklo/unikne.

1. Fitness funkce mi počítá rozdílné bity. Ta by měla být v pořádku, protože jak jsem zmiňoval v prvním příspěvku, tak "něco" mi to našlo a metodu co mám i na tisk bitů, tak seděla na bit přesně (referenční vstupy-výstupy byly stejné jako moje vstupy-výstupy). Nejlepší fitness je tedy 0 (žádný rozdíl bitů), zkoušel jsem i opačný přístup, kdy počítám jestli bity sedí, ale problém přetrval.

2. Při CGP se výhradně údajně používá pouze mutace. Tento algoritmus mi byl doporučen garantem a ještě jedním člověkem na fakultě, nicméně jsem jej někde zahlédnul i v literatuře (mohu hodit odkaz na bakalářskou práci, kde je přímo popsána podobná práce a algoritmus je tam taky). Údajně občas je problém porovnání kdy ostrá rovnost nestačí, ale je potřeba dát rovno větší/menší, ale i zde jsem nenašel žádný rozdíl...

Popis tohoto "lambda algoritmu"
(mutace je 100 % jinak by to nemělo smysl, mutace tedy může být: negativní, neutrální, pozitivní)
Lambda = 5

1. Vygeneruje se lambda + 1 náhodných obvodů, ty se ohodnotí a vybere se ten nejlepší.
2. Z nejlepšího obvodu se vygeneruje lambda obvodů, provede se mutace a ohodnocení.
3. Zjištění nejlepšího obvodu z generace.
4. Pokud není dosažena ukončující podmínka, tj. našel se cílový obvod nebo se překročil maximální počet generací běhu, tak se pokračuje bodem 2.


Zkusím zhruba popsat moji implementaci, která je:

Mám třídu, která je obvod, každá takováto třída má v sobě matici buněk. Buňka je komponenta, která v sobě má vstup1, vstup2, výstup, funkce daného hradla (and, xor, nor, ...).

Pro ukázku jak vypadá zakódování:

{počet vstupů, počet výstupů, x, y matice, hradlo vstupy, hradlo výstupy, počet funkcí}([idx hradla], vstup1, vstup2, funkce) ... (výstupní hradlo - "drát")

{5,1,5,5,2,1,6}([5]3,0,2)([6]2,3,5)([7]1,3,5)([8]1,4,5)([9]0,3,1)([10]2,5,2)([11]2,7,3)([12]5,4,4)([13]6,5,4)([14]2,3,2)([15]0,2,2)([16]3,12,0)([17]7,6,0)([18]9,12,1)([19]10,8,2)([20]10,11,4)([21]5,8,3)([22]9,14,4)([23]10,10,1)([24]13,0,5)([25]20,1,0)([26]17,13,2)([27]0,10,0)([28]15,9,5)([29]16,2,5)(19)

(je to posunuto o 5, protože vstupy se berou také jako "hradla")

Evaluaci dělám tak, že jedu touto maticí vždy se podívám na vstupy a nad tím udělám danou funkci, to je můj výstup (toto se děje paralelní simulací -> bitset, který nad celým vektorem bitů udělá v jednom taktu celou funkci např. AND, díky tomuto se to velmi urychlí, kdy se nemusí dělat bit po bitu).

Fitness kouká na výstup u dané komponenty (zde 19) a porovnává s referenčním výstupem. Nula je v mém případě perfektní plně funkční obvod. (for cyklus přes všechny bity)

Mutaci mám udělanou tak, že mám nějakou šanci (0-100 %), pokud to tam "padne", tak se zmuteje 50:50 "drát" nebo funkce v hradle. Komponenta se vybírá náhodně.

Křížení je jako vstup dvou obvodů, kde se náhodně vybere bod křížení a vrátí se potomek.

Algoritmus jsem již popsal nahoře. Nejlepší obvod vybírám tak, že využívám std::min_element z C++.

Při puštění CGP si nechávám tisknout po 10 000 generací stav nejlepší fitness obvodu, kde mi to vesměs stagnuje, sem tam malý "záchvěv", ale ani po půl hodině mi není schopný najít 5 bitovou paritu. Zde počet generací byl už někde v miliardách, když "vím", že na bitovou paritu stačí řekněme maximálně pár milionů generací (povětšinou).

Teď jsem si uvědomil, že jsem nenapsal, odkud beru bity na porovnání. Mám soubor pro každý obvod co hledám (5/9 bit parita, 3/4 bit sčítačka, 4/6 násobička). Sloupce jsou vstup 1, 2, ... a výstup obdobně.

Ukázka parity:
00000 : 0
00001 : 1
01001 : 0
...

Předem děkuji a doufám, že to půjde pochopit z toho co jsem napsal a nebude to moc velký guláš
Případně jakýkoliv dotaz nebo nejasnost rád zodpovím.

33

Vývoj / Cartesian genetic programming - pomoc

« kdy: 26. 12. 2019, 01:57:44 »

Zdravíčko vespolek, snažím se naprogramovat CGP v C++, resp. se snažím najít obvody, kde na vstupu mám vstupy v bitech a výstup taky v bitech (pravdivostní tabulka vesměs), problém je v tom, že se mi nedaří najít žádné obvody, které by fungovaly...

Když jsem zkoušel jen tak náhodně kombinovat obvody pomocí mutace/křížení, tak jsem našel i například i paritu 9 a pro 3-bit sčítačku (úplnou) jsem byl mimo jen na pár bitů z 256, problém, ale je v tom, že pokud to mám dělat podle ES algoritmu (vygenerovat lambda obvodů a z nich vybrat nejlepší a následně ho mutovat lambda-krát, opět vybrat nejlepší a ten znovu mutovat, tak dlouho dokud se nenajde obvod), takto mi "nic nefunguje" a nevím si rady.

Ideální by bylo, kdyby byl někdo ochotný se mnou prodiskutovat v čem by mohl být problém, případně se podívat na můj hovnokód