Jednoduchý genetický algoritmus

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

V jednoduchých genetických algoritmech jsou jedinci 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 jedince a je proveden výběr jedinců pro páření, který vytvoří množinu dvojic jedinců (mating pool) – ti vytvoří nové potomky. 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čů. Druhý potomek se vytvoří ze zbývajících částí.

Bit-flip mutace mění náhodné bity u jedince 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 jedince úměrná jeho fitness (tato selekce vyžaduje, aby byla fitness vždy nezáporná).

Dnešní cvičení

Naším cílem dnes je implementovat jednoduchý genetický algoritmus v Pythonu. Po semináři se s vámi podělím o ukázkovou implementaci. Pro řešení úkolů v tomto semestru budeme používat Python.