Až dosud jsme používali náš jednoduchý rámec pro evoluční algoritmy, kde jsme implementovali vše od nuly. Pokud chcete použít evoluční algoritmy pro něco praktičtějšího, často pomůže použít pokročilejší knihovnu. Dnes si povíme o knihovně deap a o tom, jak ji používat. V této knihovně také implementuji některé úkoly z dřívějších cvičení.

Následující text je v podstatě souhrnem tutoriálu deap, který je k dispozici na webové stránce knihovny.

Fitness a jedinci

Prvním krokem, který musíme udělat při vytváření nového evolučního algoritmu, je definice jedince a fitness. Za tímto účelem obsahuje knihovna deap modul creator . Funkce creator.create() tohoto modulu v zásadě definuje novou třídu s daným názvem, která dědí z dané základní třídy a může také určit vlastní atributy. Například fitness je uložena v jedinci jako instance třídy base.Fitness. Knihovna předpokládá, že fitness vždy vrátí n-tici hodnot (deap je vícerkriteriální, i když máme jen jedno kritérium). Defaultně jsou jedinci řazeni lexikograficky podle hodnot fitness, můžeme určit směr řazení zadáním kladných nebo záporných vah pro každou z fitness funkcí. Pro vytvoření konkrétní třídy pro reprezentaci hodnot fitness, můžeme zavolat

creator.create("FitnessMax", base.Fitness, weights=(1.0,))

toto říká deap, aby vytvořil třídu nazvanou FitnessMax, která dědí z třídy base.Fitness a nastaví váhy na (1.0,) (všimněte si, že to je n-tici s jednou hodnotou). To také znamená, že budeme maximalizovat fitness (váha je kladná). Délka atributu weights by měla být stejná jako počet fitness.

Pro vytvoření třídy pro reprezentaci jedince, můžeme znovu použít creator. Ve většině případů se třída pro jedince dědí ze třídy list a stačí přidat atribut pro fitness (v deap je fitness uložen v každém jednotlivci). Můžeme to udělat zavoláním 

creator.create("Individual", list, fitness=creator.FitnessMax) .

Genetické operátory a selekce

Vytvoření jedince a samotné populace, jakož i specifikace genetických operátorů je obvykle řešeno pomocí toolboxu (instance třídy base.Toolbox). Toolbox obsahuje pouze jednu důležitou metodu - register. register. Metoda zaregistruje metodu v toolboxu. Dostává několik parametrů, první je název, který by metoda měla mít v toolboxu, zbytek je v zásadě předán funkci functools.partial a vytváří metodu samotnou. Deap obsahuje řadu užitečných metod, které lze použít k inicializaci jedince. Samotná inicializace se obvykle provádí ve dvou krocích - nejprve vytvoříme funkci, která vrátí hodnotu (nebo hodnoty) pro jedince, a poté vytvoříme konečného jedince. Například pro vytvoření náhodného jedince, který obsahuje pouze 1 a 0, můžeme provést následující:

toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, 100)

První řádek vytváří samotný toolbox. Druhý definuje funkci, toolbox.attr_bool, která je v zásadě random.randint s parametry 0 a 1. Poslední řádek pak definuje toolbox.individual pomocí tools.initRepeat. Tato funkce má tři parametry - typ jedince, funkci, která vrací jednu hodnotu (pro jeden gen u jedince), a počet hodnot, které by jedinec měl mít (zde 100). V zásadě volá toolbox.attr_bool funkci stokrát a nastaví výsledky jako hodnoty v jedinci.

Populaci můžeme vytvořit stejným způsobem jako jedince - voláme funkci toolbox.individual opakovaně.

toolbox.register("population", tools.initRepeat, list, toolbox.individual)

Všimněte si, že zde jsme neurčili počet opakování, funkce toolbox.population tedy mít jeden argument, který udává velikost populace.

Nejdůležitějším použitím toolboxu je nastavení fitness a genetických operátorů. Fitness je funkce, která dostává jedince a vrací jeho fitness. Například pro OneMAX problém můžeme použít stejnou fitness jako na prvních cvičeních. Musíme pouze vrátit n-tici s jedinou hodnotou namísto pouze té hodnoty (všimněte si čárky na konci řádky return).

def evalOneMax(individual):
    return sum(individual),

Algoritmy implementované v deap pak očekávají, že v toolboxu budou přítomny konkrétní funkce. Pro fitness je funkce obvykle pojmenována evaluate. Genetické operátory se často nazývají mate (crossover) a mutate (mutace), selekce se jmenuje select. Můžeme zaregistrovat všechny:

toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)

Všimněte si, že jsme z použili řadu funkcí z modulu tools - ten obsahuje implementaci mnoha běžných genetických operátorů a selekcí, o kterých jsme se bavili během semestru. Úplný seznam najdete v dokumentaci .

Spuštění algoritmu

Když máme vše připraveno a nastaveno, můžeme spustit náš algoritmus. Většina základních typu evolučních algoritmů je implementována v modulu algorithms . Základní verze, kterou jsme používali, se nazývá eaSimple, můžeme ji spustit jednoduše:

p = toolbox.population(n=300)    
pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=40)

Můžete vidět, že algoritmus vrací konečnou populaci a log. Log v tomto případě bude None, protože jsme nezadali žádné statistiky, které chceme vypočítat. Pokud chceme zaznamenat nějaké statistiky, můžeme algoritmus volat následujícím způsobem:

pop = toolbox.population(n=300)
hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", numpy.mean)
stats.register("std", numpy.std)
stats.register("min", numpy.min)
stats.register("max", numpy.max)
    
pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=40, stats=stats, halloffame=hof, verbose=True)

Třídu tools.Statistics jsme použili k zaznamenání statistik běhu. Funkce použitá jako parametr v konstruktoru určuje, jak získáme hodnotu z jedince. Funkce specifikované v stats.register určují, co se má dělat s hodnotami z všech jedinců v populaci v každé generaci.

Třída tools.HallOfFame je v podstatě archiv nejlepších jedinců nalezených v evoluci. Parametr určuje velikost archivu.

Kromě čtení tohoto textu a tutoriálů ke knihovné také doporučuji podívat se na zdrojové kódy knihovny - implementace jsou obvykle snadno čitelné a srozumitelné, jakmile pochopíte základy knihovny. Mohou být také jednoduše použity jako výchozí bod pro vaši vlastní implementaci různých typů evolučních algoritmů.

Příklady

Připravil jsem tři příklady, které by měly být zhruba na úrovni výchozích verzí zdrojových kódů pro některé problémy, které jsme řešili v minulosti. Můžete je najít na GitHubu jako deap_onemax.py, deap_partition.py a deap_tsp.py. Hlavním cílem je ukázat, jak se jednotlivé algoritmy dají implementovat v deap.

Naposledy změněno: pondělí, 21. prosince 2020, 15.30