## Předběžné měření vlivu reprezentace jedinců

Petr Hašlar, 2006

(Aktualizováno ke dni 19/12/06)

### Tabulka globálních parametrů:

velikost elity | 5% velikosti populace
počet jedinců v klání | 3
pravděpodobnost mutace | 5%

### Použité reprezentace jedinců:

- linearizovaná matice okolí každé buňky automatu + seed
- vektor pravidel pro přechod každé buňky automatu do dalšího stavu + seed

### Výsledky měření:

Po řadě testů jsem se rozhodl při měření vlivu konkrétních parametrů simulace nastavit hodnoty ostatních parametrů přibližně na polovinu jejich měřeného rozsahu.

Ke stejnému závěru jsem dospěl i intuitivně ještě před začátkem měření. Pokud bych použil nejmenší hodnoty z měřeného rozsahu, tak bych bez důkladnější znalosti vlivu ostatních parametrů mohl simulaci zbytečně přiškrtit. Obdobná situace by nastala v případě příliš vysokých hodnot s tím rozdílem, že by se vliv hodnoty měřeného parametru mohl přestat viditelně projevovat.

V tabulce je vždy uvedena zdatnost (pokrytí) nejlepšího jedince z poslední generace a počet prozkoumaných jedinců (v případě genetiky se jedná o jejich maximální počet). Genetika má navíc v závorce uvedeno zlepšení oproti počáteční generaci.

#### Vliv velikosti populace

bench: c880, počet generací: 70, počet vektorů: 40

typ jedince / velikost populace | 50 | 150 | 250 | 350 | 500
matice (genetika) | 88.96 (0.4%), 3500 | 89.39 (1.3%), 10500 | 89.81 (1.7%), 17500 | 89.60 (1.0%), 24500 | 90.23 (2.0%), 35000
matice (náhodně) | 89.39, 3733 | 90.02, 11139 | 89.60, 18699 | 90.23, 26353 | 90.23, 39578
pravidla (genetika) | 90.76 (4.0%), 3500 | 91.40 (3.4%), 10500 | 90.98 (2.8%), 17500 | 91.93 (3.2%), 24500 | 91.83 (3.0%), 35000
pravidla (náhodně) | 89.81, 3546 | 90.34, 10781 | 90.02, 17846 | 90.55, 23701 | 90.87, 33056

bench: c2670, počet generací: 70, počet vektorů: 40

typ jedince / velikost populace | 50 | 150 | 250 | 350 | 500
matice (genetika) | 77.32 (2.0%), 3500 | 78.27 (2.2%), 10500 | 77.79 (1.3%), 17500 | 77.54 (0.8%), 24500 | 78.45 (1.0%), 35000
matice (náhodně) | 76.99, 3288 | 78.49, 11700 | 77.87, 18676 | 78.96, 27646 | 78.70, 42129
pravidla (genetika) | 77.79 (1.6%), 3500 | 78.74 (2.6%), 10500 | 79.51 (2.3%), 17500 | 82.38 (5.7%), 24500 | 83.04 (5.9%), 35000
pravidla (náhodně) | 77.90, 3661 | 77.58, 10816 | 78.74, 18396 | 79.00, 25201 | 77.79, 35628

#### Vliv počtu generací

bench: c880, velikost populace: 250, počet vektorů: 40

typ jedince / počet generací | 30 | 50 | 70 | 90 | 150
matice (genetika) | 89.70 (0.6%), 7500 | 90.13 (0.7%), 12500 | 90.76 (1.9%), 17500 | 90.66 (2.3%), 22500 | 91.08 (3.0%), 37500
matice (náhodně) | 89.70, 8786 | 90.55, 13337 | 90.45, 19287 | 90.66, 24561 | 90.23, 39713
pravidla (genetika) | 90.66 (2.7%), 7500 | 92.25 (3.1%), 12500 | 90.98 (3.0%), 17500 | 91.08 (1.9%), 22500 | 91.51 (3.8%), 37500
pravidla (náhodně) | 90.23, 7471 | 89.70, 12392 | 90.45, 18275 | 91.19, 22126 | 90.76, 38497

bench: c2670, velikost populace: 250, počet vektorů: 40

typ jedince / počet generací | 30 | 50 | 70 | 90 | 150
matice (genetika) | 78.05 (1.5%), 7500 | 78.16 (0.7%), 12500 | 77.87 (1.7%), 17500 | 77.36 (0.7%), 22500 | 78.27 (1.7%), 37500
matice (náhodně) | 77.50, 8653 | 77.90, 14270 | 79.87, 18361 | 78.67, 27053 | 78.01, 42379
pravidla (genetika) | 78.87 (2.9%), 7500 | 81.29 (1.7%), 12500 | 80.27 (3.2%), 17500 | 82.20 (6.0%), 22500 | 80.12 (3.9%), 37500
pravidla (náhodně) | 77.32, 8075 | 78.30, 12924 | 78.89, 17951 | 78.12, 22869 | 77.83, 37334

#### Vliv počtu generovaných testovacích vektorů

bench: c880, velikost populace: 250, počet generací: 70

typ jedince / počet vektorů | 20 | 30 | 40 | 50 | 60
matice (genetika) | 86.62 (5.3%), 17500 | 87.90 (1.8%), 17500 | 90.34 (2.5%), 17500 | 91.30 (1.7%), 17500 | 92.46 (1.0%), 17500
matice (náhodně) | 84.29, 19898 | 87.79, 18493 | 90.34, 18806 | 91.40, 19014 | 92.57, 18127
pravidla (genetika) | 87.05 (5.2%), 17500 | 89.17 (2.7%), 17500 | 91.30 (3.2%), 17500 | 92.46 (3.3%), 17500 ( | 93.31 (2.3%), 17500
pravidla (náhodně) | 83.86, 17022 | 88.22, 18039 | 90.34, 17898 | 92.04, 18750 | 93.21, 17719

bench: c2670, velikost populace: 250, počet generací: 70

typ jedince / počet vektorů | 20 | 30 | 40 | 50 | 60
matice (genetika) | 72.33 (1.3%), 17500 | 75.36 (1.1%), 17500 | 77.58 (1.9%), 17500 | 79.21 (0.3%), 17500 | 79.87 (0.6%), 17500
matice (náhodně) | 72.63, 22461 | 75.68, 18079 | 78.49, 20039 | 81.40, 21960 | 81.00, 19574
pravidla (genetika) | 74.23 (3.4%), 17500 | 78.30 (3.7%), 17500 | 78.70 (2.8%), 17500 | 79.90 (1.6%), 17500 | 82.82 (4.0%), 17500
pravidla (náhodně) | 72.44, 18946 | 76.99, 16633 | 79.69, 21395 | 79.07, 18419 | 81.00, 17805

### Předběžný závěr:

Z výše uvedených výsledků je patrné, že maticová reprezentace automatu nepřináší prakticky žádné zlepšení oproti náhodnemu přístupu. To si vysvětluji poměrne velkou časovou náročností vyhodnocování automatu pro složitější benchmarky s vetším počtem vstupů.

V případě reprezentace automatu pomocí pravidel program pracuje s podstatně kratšími chromosomy, jejichž velikost řádově odpovídá velikosti automatu (v předchozím případě se jednalo o její kvadrát). To se pak ve výsledku pozitivně projevilo i na kvalitě nalezených řešení.

Použití jiného generátoru pseudonáhodných čísel bohužel nepřineslo takové zlepšení kvality, jaké jsem si od něj sliboval. Vzhledem k faktu, že v drtivé většině případů si z vygenerovaného čísla stejně beru jen jeden bit, bych od další změny generátoru nečekal nijak zvlášť odlišné chování. Přesto mám už pro měření připraveny další generátory a jejich výsledky zde průběžně vystavím.

V další fázi jsem zkoušel optimalizovat především ty části kódu, které se vykonávají při vyhodnocování jedince a upravil jsem je tak, že obsahují jak původní, obecnou cestu pro libovolný počet genů, tak cestu optimalizovanou pro čistě binární chromosom. Tyto úpravy však přinesly jen zanedbatelné zlepšení.

Zajímavé je, že výše uvedené změny zmenšily rozdíl dosahované kvality řešení mezi evolucí a náhodným přístupem. Ten je za současného stavu zanedbatelný, avšak stále zůstává konsistentní. V průběhu testování jsem si všiml, že se v poslední třetině generací jen zřídkakdy zlepšuje řešení. To mě přivedlo na myšlenku, že by populace mohla za určitých podmínek rychle degenerovat. Zkusím to ověřit sledováním průměrné zdatnosti populace a současně implementuji další varianty cross-over: uniform a multi-point.

Zatím se mi použití GA jeví jako výhodné i přes relativně malé zlepšení oproti náhodnému přístupu. Rozdíl výsledků obou reprezentací skýtá naději, že další optimalizací implementace GA se nám podaří rozdíl mezi oběma přístupy výrazněji zvětšit.

### Dodatek

V následujících tabulkách je uveden počet neodhalených chyb.

#### Vliv typu generátoru pseudonáhodných čísel

generátor: Mersenne Twister, typ jedince: pravidla, křížení: one-point, počet generací: 20

typ benchmarku / velikost populace | 50 | 100 | 200
c2670 (4000 vekt.) [LFSR: 320, 1737s] | 323 (avg. 327) [282s] | 259 (avg. 345) [574s] | 325 (avg. 337) [329s]
c2670 (10000 vekt.) [LFSR: 321, 307s] | 319 (avg. 332) [688s] | 271 (avg. 328) [1383s] | 273 (avg. 358) [2826s]
c7552 (5000 vekt.) [LFSR: 416, 1373s] | 419 (avg. 425) [444s] | 407 (avg. 409) [903s] | 405 (avg. 427) [1782s]
c7552 (10000 vekt.) [LFSR: 362, 2604s] | 368 (avg. 371) [835s] | 370 (avg. 374) [1747s] | 373 (avg. 403) [3502s]
c3540 (1000 vekt.) [LFSR: 168, 48s] | 162 (avg. 163) [52s] | 163 (avg. 166) [107s] | 161 (avg. 163) [218s]
c3540 (2000 vekt.) [LFSR: 147, 80s] | 145 (avg. 146) [75s] | 144 (avg. 150) [153s] | 144 (avg. 152) [319s]

generátor: RanrotW, typ jedince: pravidla, křížení: one-point, počet generací: 20

typ benchmarku / velikost populace | 50 | 100 | 200
c2670 (4000 vekt.) [LFSR: 320, 1737s] | 327 (avg. 337) [286s] | 326 (avg. 334) [597s] | 323 (avg. 405) [1135s]
c2670 (10000 vekt.) [LFSR: 321, 307s] | 278 (avg. 337) [683s] | 270 (avg. 320) [1368s] | 266 (avg. 359) [2814s]
c7552 (5000 vekt.) [LFSR: 416, 1373s] | 411 (avg. 411) [438s] | 396 (avg. 401) [973s] | 392 (avg. 469) [2070s]
c7552 (10000 vekt.) [LFSR: 362, 2604s] | 382 (avg. 387) [1013s] | 360 (avg. 393) [2073s] | 371 (avg. 430) [4315s]
c3540 (1000 vekt.) [LFSR: 168, 48s] | 168 (avg. 170) [62s] | 164 (avg. 165) [125s] | 161 (avg. 165) [253s]
c3540 (2000 vekt.) [LFSR: 147, 80s] | 146 (avg. 146) [90s] | 144 (avg. 147) [188s] | 145 (avg. 150) [371s]

generátor: MotherOfAll, typ jedince: pravidla, křížení: one-point, počet generací: 20

typ benchmarku / velikost populace | 50 | 100 | 200
c2670 (4000 vekt.) [LFSR: 320, 1737s] | 323 (avg. 327) [338s] | 321 (avg. 323) [771s] | 273 (avg. 388) [1416s]
c2670 (10000 vekt.) [LFSR: 321, 307s] | 316 (avg. 320) [810s] | 263 (avg. 391) [1356s] | 263 (avg. 289) [2701s]
c7552 (5000 vekt.) [LFSR: 416, 1373s] | 421 (avg. 422) [465s] | 413 (avg. 421) [885s] | (avg. ) []
c7552 (10000 vekt.) [LFSR: 362, 2604s] | 376 (avg. 380) [816s] | 373 (avg. 374) [1785s] | (avg. ) []
c3540 (1000 vekt.) [LFSR: 168, 48s] | 168 (avg. 178) [53s] | 163 (avg. 165) [102s] | (avg. ) []
c3540 (2000 vekt.) [LFSR: 147, 80s] | 144 (avg. 144) [74s] | 143 (avg. 144) [146s] | (avg. ) []

Tímto testem jsem chtěl především zjistit minimální použitelnou velikost populace pro různé benchmarky. Z výsledků se mi jeví jako vhodné v dané situaci nepřekračovat cca 150 jedinců--pro větší populace je nárůst času potřebného k simulaci evoluce neúměrný vzhledem ke zlepšení kvality řešení.

Během měření jsem si všiml, že i když se zdatnost nejlepšího jedince v populaci zlepšuje jen velice pozvolna, průměrná zdatnost velice rychle konverguje k této hodnotě. V řadě případů populace navíc podle všeho zcela degeneruje tak, že obsahuje pouze kopie nejlepšího jedince. Od přibližně desáté generace se už řešení v naprosté většině případů nezlepší a ke konci evoluce průměrná zdatnost populace osciluje kolem této hodnoty. Podle mého názoru je už při stávající implementaci zbytečné prodlužovat délku simulace.

#### Vliv typu operace křížení

generátor: MotherOfAll, typ jedince: pravidla, křížení: uniform, počet generací: 20

typ benchmarku / velikost populace | 50 | 100 | 200
c2670 (4000 vekt.) [LFSR: 320, 1737s] | 289 (avg. 421, rand. 325) [345s] | 322 (avg. 421, rand. 321) [688s] | 264 (avg. 422, rand. 278) [1227s]
c2670 (10000 vekt.) [LFSR: 321, 307s] | 295 (avg. 415, rand. 318) [677s] | 288 (avg. 413, rand. 308) [1382s] | 262 (avg. 414, rand. 259) [2712s]
c7552 (5000 vekt.) [LFSR: 416, 1373s] | 408 (avg. 475, rand. 416) [450s] | 404 (avg. 480, rand. 413) [934s] | 404 (avg. 477, rand. 401) [1899s]
c7552 (10000 vekt.) [LFSR: 362, 2604s] | 353 (avg. 433, rand. 372) [821s] | 357 (avg. 435, rand. 353) [1720s] | 366 (avg. 436, rand. 364) [3391s]
c3540 (1000 vekt.) [LFSR: 168, 48s] | 167 (avg. 194, rand. 166) [50s] | 162 (avg. 195, rand. 163) [105s] | 155 (avg. 194, rand. 163) [215s]
c3540 (2000 vekt.) [LFSR: 147, 80s] | 144 (avg. 155, rand. 144) [74s] | 145 (avg. 156, rand. 143) [151s] | 144 (avg. 156, rand. 143) [316s]

V tomto případě máme větší 'štěstí' na pěkné výsledky zejména u prvního benchmarku. Pro ověření, že se skutečně jedná o vliv použitého typu křížení a ne o náhodu, bude ale ještě potřeba provést další měření. Zajímavé je také to, že je průměrná zdatnost populace na konci evoluce jen o něco málo lepší než na jejím počátku. V průběhu samotné evoluce pak můžeme sledovat celkem znatelné výkyvy na obě strany.