Jednoduchý genetický algoritmus je (jak název napovídá) jednou z nejjednodušších verzí genetického algoritmu.

V jednoduchých genetických algoritmech jsou jednotlivci kódováni jako binární vektor (vektor 0 a 1). Algoritmus pracuje s těmito jedinci a pokouší se simulovat darwinovskou evoluci.

Na začátku je náhodně inicializována skupina jedinců (populace). Poté se algoritmus spustí iterativně (iterace se nazývají generace). V každé iteraci je vyhodnocena kvalita (fitness) každého jednotlivce a je proveden výběr jedinců pro páření, ten vytváří množinu dvojic jedinců, kteří vytvoří nového potomka (mating pool). Poté se na jedince v mating pool aplikují genetické operátory (křížení a mutace), aby se vytvořila množina potomků. Nakonec je populace nahrazena novou populací potomků.

Pseudokód hlavního cyklu evolučního algoritmu je níže.

 evolutionary_algorithm(fitness):
    pop = create_population(POP_SIZE)
    for G in 1..MAX_GEN:
        fits = map(fitness, pop)
        mating_pool = selection(pop, fits)
        offspring = operators(mating_pool)
        pop = offspring
    return pop


Genetické operátory


Existují různé způsoby, jak implementovat genetické operátory, ale ty tradiční jsou tzv. jednobodové křížení a bit-flip mutace. Jednobodové křížení vezme dva rodiče a vytvoří dva potomky. Nejprve vybere náhodný křížící bod u rodičů a první potomek se vytvoří tak, že se vezme počáteční část (před křížícím bodem) jednoho z rodičů a koncová část druhého z rodičů. Ostatní potomci se vytvářejí odebráním zbývajících částí.


Bitová překlopná mutace mění náhodné bity u jednotlivce na jinou hodnotu.


Fitness funkce


Funkce fitness je specifická pro daný problém a hodnotí kvalitu každého jedince. Evoluční algoritmus maximalizuje fitness funkci. Příkladem jednoduchého problému je tzv. OneMAX problém, kde cílem je najít jedince, který obsahuje maximální počet bitů s hodnotou 1. V takovém případě může funkce fitness vrátit počet 1 v jedinci.


Selekce


Selekce v evolučních algoritmech by měla upřednostňovat jedince s lepší fitness, a tím zvyšovat jejich šanci na vytvoření potomka. Opět existuje řada způsobů, jak implementovat selekci, tradiční je ruletová selekce (nebo výběr podle proporcí fitness), kde je pravděpodobnost výběru jednotlivce úměrná jeho jeho (tato selekce vyžaduje, aby byla vždy nezáporná).


Dnešní cvičení


Naším cílem dnes je implementovat jednoduchý genetický algoritmus v programovacím jazyce dle vašeho výběru. Po semináři se s vámi všemi podělím o implementaci Pythonu. Na ostatních letošních seminářích si můžete vybrat, zda chcete pro řešení úkolů použít Python nebo Javu. Popis zdrojových kódů v Javě a implementace obecného evolučního algoritmu je k dispozici na samostatné stránce.
Naposledy změněno: úterý, 8. října 2019, 12.48