Genetické algoritmy: podstata, popis, příklady, aplikace

Myšlenka genetických algoritmů (GA) se objevila již dávno (1950-1975), ale stala se skutečným předmětem studia pouze v posledních desetiletích. D. Holland byl považován za průkopníka v této oblasti, který si vypůjčil hodně genetiky a přizpůsobil ji počítačům. GA jsou široce používány v systémech umělé inteligence, neuronových sítích a optimalizačních problémech.

Evoluční vyhledávání

Modely genetických algoritmů byly vytvořeny na základě evoluce metody volně žijících živočichů a náhodného hledání. Současně je náhodné hledání implementací nejjednodušší evoluční funkce - náhodných mutací a následného výběru.

Z matematického hlediska evoluční hledání znamená nic víc než přeměnu existující konečné sady řešení na novou. Funkcí odpovědnou za tento proces je genetické vyhledávání. Hlavní rozdíl tohoto algoritmu od náhodného hledání je aktivní využití informací shromážděných během iterací (opakování).

Proč potřebujeme genetické algoritmy

GA má tyto cíle:

• vysvětlit adaptační mechanismy jak v přírodním prostředí, tak v intelektuálně-výzkumném (umělém) systému;
• modelování evolučních funkcí a jejich aplikace pro efektivní hledání řešení nejrůznějších problémů, zejména optimalizačních.

V současné době může být podstata genetických algoritmů a jejich modifikovaných verzí nazývána hledáním účinných řešení s ohledem na kvalitu výsledku. Jinými slovy, nalezení nejlepší rovnováhy mezi výkonem a přesností. K tomu dochází díky známému paradigmu "přežití nejschopnějšího jedince" v nejistých a nejasných podmínkách.

Vlastnosti GA

Uvádíme hlavní rozdíly GA od většiny jiných metod nalezení optimálního řešení.

• práce s parametry úkolu, kódované určitým způsobem, a ne přímo s nimi;
• hledání řešení se nevyskytuje stanovením počáteční aproximace, nýbrž v množině možných řešení;
• s využitím pouze objektivní funkce, aniž by se uchýlil k jeho derivacím a úpravám;
• aplikace pravděpodobnostního přístupu k analýze namísto striktně deterministického.

Kritéria výkonnosti

Genetické algoritmy provádějí výpočty na základě dvou podmínek:

1. Proveďte zadaný počet iterací.
2. Kvalita nalezeného řešení splňuje požadavky.

Pokud je splněna jedna z těchto podmínek, genetický algoritmus přestane provádět další iterace. Navíc použití GA v různých oblastech prostoru řešení jim umožňuje najít mnohem lepší nová řešení, která mají vhodnější hodnoty cílové funkce.

Základní terminologie

Vzhledem k tomu, že GA je založena na genetice, většina terminologie odpovídá. Každý genetický algoritmus funguje na základě počátečních informací. Soubor počátečních hodnot je populace ^{t t} = {n ₁ , n ₂ , ..., n _n }, kde n _i = {r ₁ , ..., r _v }. Budeme podrobněji zkoumat:

• t je číslo iterace. t ₁ , ..., t _k - znamená iteraci algoritmu od čísla 1 do k, a při každé iteraci je vytvořena nová populace řešení.
• n je velikost populace ^Pt .
• ₁ , ..., п _i - хромосома, особь, или организм. n ₁ , ..., n _i - chromozom, jednotlivec nebo organismus. Chromosom nebo řetězec je kódovaná sekvence genů, z nichž každá má sekvenční číslo. Je třeba mít na paměti, že chromozom může být zvláštní případ jednotlivce (organismu).
• r _v jsou geny, které jsou součástí kódovaného řešení.
• Lokus je sekvenční číslo genu v chromozomu. Allele je hodnota genu, která může být číselná i funkční.

Co znamená "kódované" v kontextu GA? Obvykle je každá hodnota zakódována na základě abecedy. Nejjednodušším příkladem je konverze čísel z desetičlenného číselného systému na binární reprezentaci. Tedy abeceda je reprezentována jako množina {0, 1} a číslo 157 ₁₀ bude kódováno chromozomem 10011101 ₂ , sestávajícím z osmi genů.

Rodiče a potomci

Rodiče jsou prvky vybrané v souladu s danou podmínkou. Například často je tento stav nehodou. Vybrané prvky způsobené operacemi křížení a mutace dávají vzniknout novým, nazývaným potomci. Proto rodiče při realizaci jedné iterace genetického algoritmu vytvářejí novou generaci.

Konečně, vývoj v tomto kontextu bude střídání generací, z nichž každá nová se odlišuje sadou chromozomů, a to kvůli lepší kondici, tj. Vhodnějšímu dodržování stanovených podmínek. Obecné genetické pozadí v procesu evoluce se nazývá genotyp a tvorba spojení organismu s vnějším prostředím se nazývá fenotyp.

Fitness funkce

Kouzlo genetického algoritmu ve funkci fitness. Každý jedinec má svou vlastní hodnotu, kterou lze naučit pomocí funkce adaptace. Jeho hlavním úkolem je vyhodnotit tyto hodnoty pro různé alternativní řešení a zvolit to nejlepší. Jinými slovy, nejschopnější.

V optimalizačních problémech se funkce fitness nazývá cíl, v teorii řízení se nazývá chyba, v teorii her je funkcí hodnoty a tak dále. Co přesně bude reprezentováno jako funkce adaptace závisí na problému, který má být vyřešen.

Nakonec lze konstatovat, že genetické algoritmy analyzují populaci jedinců, organismů nebo chromozomů, z nichž každá je reprezentována kombinací genů (soubor některých hodnot) a hledá optimální řešení, které mezi sebou přeměňují jedince obyvatelstva.

Odchylky v jednom směru jednotlivých prvků v obecném případě jsou v souladu s běžným zákonem o distribuci veličin. Současně GA poskytuje dědičnost vlastností, z nichž nejvhodnější jsou fixní, čímž poskytuje nejlepší populaci.

Základní genetický algoritmus

Postupně rozkládáme nejjednodušší (klasické) GA.

1. Inicializace počátečních hodnot, tj. Definice primární populace, soubor jedinců, se kterými se evoluce projeví.
2. Stanovení primární způsobilosti každého jednotlivce v populaci.
3. Zkontrolujte podmínky ukončení iterací algoritmu.
4. Použití funkce výběru.
5. Použití genetických operátorů.
6. Vytvoření nové populace.
7. Kroky 2-6 se opakují v cyklu, dokud není splněna nezbytná podmínka, po které se objeví výběr nejvhodnějších osob.

Pojďme si krátce projít trochu zřejmými částmi algoritmu. Existují dvě podmínky pro ukončení:

1. Počet iterací.
2. Kvalita řešení.

Genetickými operátory jsou operátory mutace a operátor přechodu. Mutace změní náhodné geny s jistou pravděpodobností. Pravděpodobnost mutace má zpravidla nízkou číselnou hodnotu. Promluvme si o postupu genetického algoritmu "crossing". Vyskytuje se podle následující zásady:

1. Pro každý pár rodičů obsahujících L geny _je náhodně vybrán přechodový bod Tsk _i .
2. První potomka je složena spojením [1; Tsk _i ] genů prvního rodiče [Tsk _{i + 1} ; L] genů druhého rodiče.
3. Druhý potomk je složen v opačném směru. Nyní k genům druhého rodiče [1; Tsk _i ] přidává geny prvního rodiče do pozic [Tsk _{i + 1} ; L].

Triviální příklad

Problém řešíme pomocí genetického algoritmu, který používá příklad hledání jedince s maximálním počtem jednotek. Nechte jednotlivce sestávat z 10 genů. Primární populaci přidělujeme ve výši osmi osob. Je zřejmé, že nejlepší osobou by měla být 1111111111. Vyrovnejme rozhodnutí GA.

• Inicializace. Vyberte 8 náhodných jednotlivců:

• Posouzení způsobilosti. Je zřejmé, že v našem genetickém algoritmu bude fitness funkce F počítat počet jednotek v každém jednotlivci. Proto máme:

Tabulka ukazuje, že jednotlivci 3 a 7 mají největší počet jednotek, a proto jsou nejvhodnějšími členy populace k vyřešení problému. Vzhledem k tomu, že v současné době neexistuje řešení požadované kvality, algoritmus nadále funguje. Je nutné provést výběr jednotlivců. Pro snadné vysvětlení nechte výběr být náhodný a získáme vzorek jedinců {n ₇ , n ₃ , n ₁ , n ₇ , n ₃ , n ₇ , n ₄ , n ₂ } - to jsou rodiče pro novou populaci.

• Použití genetických operátorů. Zjednodušeně předpokládáme, že pravděpodobnost mutací je 0. Jinými slovy, všech 8 jedinců předává své geny tak, jak jsou. Pro křížení vytvoříme dvojice jednotlivců náhodně: (n ₂ , n ₇ ), (n ₁ , n ₇ ), (n ₃ , n ₄ ) a (n ₃ , n ₇ ). Stejným náhodným způsobem jsou vybrány body přechodu pro každý pár:

• Kompilace nové populace sestávající z potomků:

• Odhadujeme vhodnost každého jednotlivého nového obyvatelstva:

Další akce jsou zřejmé. Nejzajímavější v GA je, když odhadujeme průměrný počet jednotek v každé populaci. V první populaci bylo v průměru 5 375 jednotek u každého jednotlivce, v populaci potomků - 6,25 jednotek na osobu. A takový rys bude pozorován, i když během mutací a překročení je ztracena osoba s největším počtem jednotek v první populaci.

Implementační plán

Vytvoření genetického algoritmu je poměrně komplikovaným úkolem. Zaprvé uvedeme plán v podobě kroků, po kterém podrobněji prozkoumáme každý z nich.

1. Definice reprezentace (abeceda).
2. Definice operátorů náhodných změn.
3. Definice přežití jednotlivců.
4. Generace primární populace.

První fáze říká, že abeceda, ve které budou zakódovány všechny prvky množiny řešení nebo populace, musí být dostatečně flexibilní, aby bylo možné současně provést nezbytná náhodná permutace a vyhodnotit vhodnost elementů, primárních i těch, které prošly změnami. Je matematicky stanoveno, že pro tyto účely nelze vytvořit ideální abecedu, a proto je její kompilace jedním z nejtěžších a nejdůležitějších kroků k zajištění stabilního fungování GA.

Rovněž je obtížné definovat výkazy změn a vytvářet potomky. Existuje mnoho operátorů, kteří jsou schopni provést požadované akce. Například je z biologie známo, že každý druh se může rozmnožovat dvěma způsoby: sexuálně (křížením) a asexuální (mutací). V prvním případě si rodiče vyměňují genetický materiál, ve druhém dochází k mutacím, určeným vnitřními mechanismy těla a vnějším vlivem. Kromě toho mohou být použity reprodukční modely, které neexistují ve volné přírodě. Používejte například geny tří nebo více rodičů. Podobně překročení mutace v genetickém algoritmu může zahrnovat různorodý mechanismus.

Volba metody přežití může být extrémně zavádějící. V genetickém algoritmu pro chov je mnoho způsobů. A jak ukazuje praxe, pravidlo "přežití nejschopnějších" není vždy nejlepší. Při řešení složitých technických problémů se často ukazuje, že nejlepší řešení pochází z množství středních nebo dokonce horších. Proto je často akceptováno používání pravděpodobnostního přístupu, který uvádí, že nejlepší řešení má větší šanci na přežití.

Poslední etapa poskytuje flexibilitu algoritmu, který nikdo jiný nemá. Počáteční populace řešení může být definována buď na základě jakýchkoli známých údajů nebo zcela náhodným způsobem jednoduše přeskupením genů uvnitř jedinců a vytvořením náhodných jedinců. Je však vždy zapotřebí pamatovat na to, že účinnost algoritmu závisí na počáteční populaci.

Účinnost

Účinnost genetického algoritmu zcela závisí na správnosti kroků popsaných v plánu. Zvláště důležitým faktorem je vytvoření primární populace. Existuje mnoho přístupů k tomuto. Popisujeme několik:

1. Vytvoření úplné populace, která bude zahrnovat nejrůznější možnosti pro jednotlivce v dané oblasti.
2. Náhodná tvorba jednotlivců založená na všech platných hodnotách.
3. Dot náhodné vytvoření jednotlivců, když mezi přijatelnými hodnotami je vybrán rozsah pro generaci.
4. Kombinace prvních tří způsobů vytvoření populace.

Můžeme tedy konstatovat, že účinnost genetických algoritmů závisí do značné míry na zkušenostech programátora v této věci. To je jak nevýhoda genetických algoritmů, tak jejich výhoda.