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.
12 Odpovědí
6278 Zhlédnutí