Chromozom (genetický algoritmus) - Chromosome (genetic algorithm)

v genetické algoritmy, a chromozóm (někdy také nazývané a genotyp) je sada parametrů, které definují navrhované řešení problému, který se snaží vyřešit genetický algoritmus. Soubor všech řešení je znám jako populace.^[1] Chromozom je často reprezentován jako binární tětiva, ačkoli celá řada dalších datové struktury jsou také používány.

Design chromozomu

Konstrukce chromozomu a jeho parametry jsou nezbytně specifické pro problém, který má být vyřešen. Tradičně jsou chromozomy reprezentovány v binárním formátu jako řetězce 0s a 1s, jsou však možná i jiná kódování;^[2] lze použít téměř jakoukoli reprezentaci, která umožňuje, aby bylo řešení reprezentováno jako řetězec konečné délky.^[3] Nalezení vhodné reprezentace problémové domény pro chromozom je důležitým hlediskem, protože dobrá reprezentace usnadní hledání omezením prostoru vyhledávání; podobně, horší zastoupení umožní větší prostor pro vyhledávání.^[4] The mutace operátor a crossover operátor zaměstnaný genetickým algoritmem musí také vzít v úvahu design chromozomu.

Příklad 1: binární reprezentace

Předpokládejme, že problém je najít celočíselnou hodnotu ${ displaystyle x}$ mezi 0 a 255, které poskytují maximální výsledek pro ${ displaystyle f (x) = x ^ {2}}$. Možná řešení tohoto problému jsou celá čísla od 0 do 255, která mohou být reprezentována jako 8místné binární řetězce. Jako náš chromozom tedy můžeme použít 8místný binární řetězec. Pokud daný chromozom v populaci představuje hodnotu 155, jeho chromozom by byl 10011011.

Všimněte si, že toto není typ problému, který je obvykle řešen genetickým algoritmem, protože může být triviálně vyřešen pomocí numerických metod; slouží pouze jako jednoduchý příklad.

Příklad 2: řetězcová reprezentace

Realističtější problém, který bychom možná chtěli vyřešit, je problém obchodního cestujícího. V tomto problému hledáme uspořádaný seznam měst, jehož výsledkem je nejkratší cesta pro prodavače. Předpokládejme, že existuje šest měst, která budeme nazývat A, B, C, D, E a F. Dobrý design pro náš chromozom může být uspořádaný seznam, který chceme vyzkoušet. Příkladem chromozomu, se kterým se můžeme v populaci setkat, může být DFABEC.

Výběr, křížení a mutace

V každé generaci genetického algoritmu jsou vybrány dva rodičovské chromozomy na základě jejich hodnot fitness; tyto chromozomy jsou používány operátory mutace a křížení k produkci dvou potomků chromozomů pro novou populaci.^[3]

Reference