GA a predčasná konvergence

• Předčasná konvergence - výpočet konverguje příliš rychle k nějakému neoptimálnímu řešení

• Co způsobuje předčasnou konvergenci?

– příliš velký selekční tlak - přílišné upřednostňování několika výjimečných jedinců na úkor zbytku populace

– nedostatečná velikost populace - optimální velikost populace roste exponenciálně (!) s velikostí řešeného problému

– obsah počáteční populace

– špatně navržené genetické operátory - nutná rovnováha mezi prohledáváním (exploration) a zachováním důležitých stavebních bloků (exploration)

– klamnost - nadprůměrná schémata pokrývající falešný extrém

Gentické algoritmy s omezenou konvergencí

• Genetic Algorithms with Limited Convergence (GALCO)

• Idea – neřešit, co dělat v případě, kdy nám už populace zkonvergovala ale naopak určit maximální povolenou míru konvergence a zajistit, že nebude během výpočtu překročena

nepřipustit možnost, že by nějaký gen (stavební blok) zcela převládl v populaci

GALCO cont.

• Celkový genotyp populace – limit na konvergenci v rámci sloupců populace

• Jednotlivé geny mohou na dané pozici převládnout maximálně o hodnotu C – parametr konvergence

i-tá pozice v chromozomu = sloupec populace

.

.

.

...

...

...

...

...

...

...

chromozomy

GALCO Algorithm

Step 1 Generate an initial population

Step 2 Choose parents

Step 3 Create offspring using the 2-point crossover

Step 4 Insert the offspring into the population according to the following ruleif(max(child1, child2) > max(parent1, parent2))then replace both parents with the childrenelse{ find(current_worst) replace_with_mask(child1, current_worst) find(current_worst) replace_with_mask(child2, current_worst)}

Step 5 if (not finished) then goto Step 2

Replace_with_mask operator

for(i=0; i<chrom_length; i++){

change = child.genes[i] – current_worst.genes[i]

if (PopSize/2 – C < conv[i] + change < PopSize/2 + C ) then{

conv[i] = conv[i] + change

current_worst.genes[i] = child.genes[i]

}

}

• Slučuje chromozomy potomka a nejhoršího jedince v populaci

– Pokud na dané pozici nedojde k překročení povolené míry konvergence, tak se použije bit z potomka, jinak z nejhoršího jedince

– Vektor conv[] – maska, určující, z kterého jedince bude daný bit použit

Výsledky experimentů na známých úlohách

Pokrytí více extrémů

Rozdělení populace po 50 000 iterací

24-18-19-19-20

Rozdělení populace po 500 000 iterací

26-16-22-17-19

GALCO - poznámky

• Typ inkrementálního GA

• Generuje nová řešení i po nalezení globálního optima

• Pkřížení = 1.0

• Pmutace = 0.0

• Vystačí si s menšími velikostmi populace než klasický GA

– důležité z hlediska efektivnosti výpočtu

Další přístupy

• Duální GA

• Messy GA

• Selective X-over

Duální Genetické Algoritmy

• Idea – zavedením redundance do genetického kódu se zvýší diversita populace

• Meta-gen připojen ke každému chromozomu

• Meta-gen řídí interpretaci chromozomu– 0 ... přímá– 1 ... Invertovanáv populaci mohou být 2 jedinci s totálně opačným

genotypem ale se stejným fenotypem

• Operátor zrcadlení – invertuje celý chromozom

bity kódující parametry řešení1/0

Vazba stavebních bloků (linkage)

• Pevná – kompaktní stavební bloky

• Volná – roztroušené stavební bloky (snadno porušitelné)

...

Messy Genetic Algorithms

• Idea – nešlechtit přímo celé chromozomy, namísto toho hledat slibná schémata (resp. stavební bloky) a postupně z nich budovat řetězce rostoucí délky

• Podobně jako v přírodě, kde vývoj začal od nejjednodušších forem života k vyšším a složitějším, které od nich přebíraly to dobré

• Od 1-buněčných organismů k Homo sapiens s genetickou výbavou kolem 2.000.000 genů

Messy GA - representation

• Reprezentace - řetězce dvojic (jméno, hodnota) proměnné délky

underspecification – nejsou definovány všechny bity

• bere se např. první hodnota zleva (first-come-first-served)

overspecification – některý bit má v řetězci vícenásobnou definici

• na neúplné řetězce lze nahližet jako na schémata

• Přípustné řetězce pro 4-bitový problém:

{(1, 0) (2, 0) (4, 1) (4, 0)} 001

{(1, 1) (3, 0) (4, 0) (2, 1) (4, 1) (3, 1)}

Výpočet fitness neúplného řetězce

• Průměrování– několikrát se náhodně doplní nespecifikované bity a vezme

se průměrná fitness takto dolepených chromozomů

– příliš evlký rozptyl nepřesné

• Competitive templates1. Pomocí metody hill-climbing se najde lokální optimum

2. Neúplné schéma se doplní bity z tohoto lokálního optima

3. Pokud schéma vylepší lokální optimum, stává se toto schéma novým lokálním optimem

Funkční schéma Messy GA

1. Inicializace počáteční poplace – uplný výčet schémat řádu k

2. Primordinal fáze – naplnění populace slibnými schématy

• pouze selekce a kopírování jedinců

• v určitých intervalech půlení populace

3. Juxtapositional fáze – vzájemná rekombinace schémat

• selekce + cut & splice operátor

{(2, 0) (3, 0) (1, 1) (4, 1) (6, 0)} {(2, 0) (3, 0) (1, 1)}

{(4, 1) (6, 0)}

{(3, 1) (2, 0) (1, 1)} + {(4, 1) (6, 0)} {(3, 1) (2, 0) (1, 1) (4, 1) (6, 0)}

Slabiny Messy GA

• Jak volit k ?– Velice konkrétní apriorní znalost o řešené úloze

• Inicializace počáteční populace a její proveditelnost– l ... délka chromozomu

– k ... velikost minimálních (fundamentálních) schémat

– velikost populace n=2k(lk)

Př: l=30, k=3 n = 32 480

l=64, k=8 n 1012

Pravděpodobnostně úplná inicializace

• Populace inicializována řetězci o délce

k << l’< l

– řetězce pokrývají mnoho schémat řádu k

• Odhad n’tak, že každé schéma řádu k bude v populaci

• Parazitující bity – poškozují dobrá schémata obsažená v delších řetězcích

– building-block filtering – náhodné ořezávání bitů

• Př: Klamný problém l=150, k=5

– normálně by potřebovali n = 18.931.200.960

Selective X-over

• Idea – převzít od každého rodiče jen to dobré

• Dceřinný chromozom se buduje bit po bitu

–výsledek je nezávislý na struktuře st. bloků (délce, řádu)

• U každého bitu se rozhodujeme podle pravidla:

i-tý bit se vezme z toho rodiče, u kterého změna daného bitu způsobí menší zlepšení (nebo větší škody) než u rodiče druhého

– rozhodujeme se na základě vyšetření okolí rodič. chromozomů

Selective X-over (cont.)

02468

1012141618202224262830

0000

1000

0100

0010

0001

0011

0101

0110

1001

1010

1100

1110

1101

1011

0111

1111

string

fitn

ess

Poznámky k Selective X-over

• Klamné problémy

+ optimálně nastavený stavební blok již nemůže být rozbit – platí pouze u klamných problémů

- špatně se nastavují opt. st. Bloky

• Obecně – pokud jsou nějaké interakce mezi bity, tak to už nemusí fungovat

• Mnoho výpočtů navíc – O(PopSizelchrom)