[CZ] Hromádky I - Fitness a selekce

Na dnešních cvičeních se podíváme na složitější úlohu. Budeme řešit problém loupežníků - ti naloupili spoustu zlatých věcí a chtějí si je mezi sebe rozdělit tak, aby všichni měli věci stejné hodnoty (zajímá je jen váha zlata, které mají). Rozdělují tedy svůj lup na několik (v zadání 10) stejných hromádek s cílem minimalizovat rozdíl mezi nejtěžší a nejlehčí hromádkou.

Z pohledu informatiky se jedná o zobecnění optimalizační verze partition problému (máme 10 podmnožin místo 2) a o tom je známo, že jeho optimalizační varianta je NP-těžká.

Evoluční algoritmus pro hromádky

Evoluční algoritmy se obecně dají dobře použít právě na podobně problémy, kde máme dobře specifikované kritérium, které chceme optimalizovat a zároveň nemáme vhodný algoritmus speciálně pro tento problém.

Musíme se ale zamyslet nad několika věcmi:

Jakým způsobem budeme reprezentovat jedince? Na vstupu dostáváme seznam vah jednotlivých předmětů, musíme vymyslet, jak reprezentovat jejich rozdělení na 10 hromádek. Nabízí se např. možnost mít v jedinci 10 seznamů, ve kterých budou jednotlivé předměty. To by ale znamenalo napsat speciální operátory. Mnohem jednodušší možnost je použít jedince, který bude obsahovat vektor čísel od 0 do 9 stejně dlouhý, jako je seznam vah předmětů. Na pozici i potom bude napsáno číslo hromádky na kterou patří předmět i-tý předmět.

Jak budeme počítat fitness? Spočítat rozdíl mezi nejtěžší a nejlehčí hromádkou je snadné, ale dá se tohle číslo použít jako fitness? Chceme přeci tento rozdíl minimalizovat, fitness se ale maximalizuje. Musíme tedy fitness počítat nějak jinak. Jsou jednoduché metody, jak z minimalizace udělat maximalizaci. Jedna z nich je přidat před funkci minus. To ale narazí na problém v ruletové selekci (ta nezvládá zápornou fitness). Potřebujeme tedy nějakou jinou transformaci - můžeme např. odečíst rozdíl mezi nejtěžší a nejlehčí hromádkou od nějakého velkého čísla. Nebo spočítat 1/rozdíl. A nebo zkuste něco úplně jiného. Je vůbec rozdíl mezi nejtěžší a nejlehčí hromádkou dobrý základ? Nenašlo by se něco lepšího, citlivějšího, co dá algoritmu více informací?

Jaké použijeme operátory? Když se rozhodneme pro kódování jedince, je třeba k němu ještě zvolit operátory. Pro jedince jako vektor čísel můžeme klidně použít jednobodové křížení z minula a mutaci, která nahradí některé pozice náhodnými čísly ze správného rozsahu, je to vlastně obdoba bit-flip mutace z minula.

Jaké použijeme selekce? Použité selekce hodně závisí na použité fitness funkci. Zatím známe jen ruletovou selekci a když se zamyslíme jak funguje, tak si všimneme, že hodně závisí na konkrétní hodnotě fitness funkce. Pokud bychom například měli všechny jedince s fitness mezi 0 a 1, tak jedinec s fitness 0.1 má oproti jedinci s fitness 1.0 desetkrát menší šanci být vybrán. Když ale ke všem jedincům přičteme nějakou konstantu, řekněme 1000, tak potom mají oba skoro stejnou šanci na výběr. Naproti tomu existuje ještě např. turnajová selekce, která porovná fitness dvou jedinců a vybere s velkou pravděpodobností (třeba 80%) toho s větší fitness. Té potom přičtení konstanty ke všem jedincům nevadí. Dokonce jí ani nevadí záporná hodnota fitness funkce. To ale neznamená, že je vždy lepší než ruleta. Závislosti rulety na hodnotách fitness lze využít. Můžeme fitness vhodně naškálovat a tím zvýraznit rozdíly, které nám připadají důležité. Podobně se dá i měnit síla selekce.

Dnešní zdrojové kódy

Implementace algoritmu v Pythonu je jednoduchá (soubor partition.py). Jedinec je reprezentovaný jako seznam čísel od 0 do 9 (viz funkce create_ind). Fitness se počítá jako převrácená hodnota rozdílu mezi nejlehčí a nejtěžší hromádkou (viz funkce fitness).

Implementace evolučního algoritmu je ve funkci evolutionary_algorithm, která jako parametry očekává počáteční populaci, maximální počet generací, genetické operátory (jako funkce/callable s jedním parametrem - populace - vracející novou populaci), rodičovskou selekci a případně strukturu pro logování.

Váhy předmětů jsou v souborech inputs/partition-easy.txt a inputs/partition-hard.txt. Oba obsahují váhy 500 předmětů, u toho prvního lze najít rozdíl 0 u druhého je optimum kolem 2. 

Při implementaci jsem použil jednu méně známou knihovnu v Pythonu - functools, konkrétně potom funkci functools.partial, která jako parametr dostane funkci a některé její argumenty a vrátí funkci, která se chová stejně jako zadaná funkce s některými parametry nastavenými napevno (má tedy pouze zbytek parametrů). To se dá velmi dobře použít např. pro implementaci operátorů, které typicky mají řadu parametrů (např. pravděpodobnost aplikování), které je ale potřeba nastavit jen jednou. Pomocí functools.partial se z této funkce s několika parametry vytvoří funkce s jedním parametrem, kterou algoritmus očekává jako genetický operátor.

Samotné genetické operátory jsou implementované ve dvou krocích - jako funkce, která aplikuje daný operátor na dva (křížení) nebo jednoho (mutace) jedince a jako druhá funkce, která dostane tuto funkci jako parametr a aplikuje ji na celou populaci (viz např. dvojici funkcí crossover a one_pt_cross).