Semestrální práce

Genetické algoritmy

 

 

Petr Pošík, 5/18

20.2.2000

Katedra kybernetiky

Fakulta elektrotechnická

České vysoké učení technické Praha

xposik@rtime.felk.cvut.cz, posa@volny.cz

Úvod

V každodenním životě se často setkáváme se složitými problémy, které vyžadují nalézt řešení. Toto řešení by navíc nemělo být ledajaké, ale v jistém smyslu také optimální (nebo alespoň blízké optimálnímu). Na většinu problémů se dá obecně pohlížet jako na problémy optimalizační, které se dají převést na vyhledávání optima v jisté množině potenciálních řešení. Této množině možných řešení se říká stavový prostor a řešení úlohy se tak vlastně transformuje na prohledávání stavového prostoru. Kvalita jednotlivých řešení se ohodnocuje pomocí kriteriální ztrátové funkce. Problém je, že i úlohy, které lidskému uchu nezní příliš složitě, mají většinou velký počet potenciálních řešení (NP-obtížné nebo NP-úplné problémy). Metody, pomocí nichž se žádaná řešení dají nalézt, jsou důležitou oblastí zkoumání vědní disciplíny zvané umělá inteligence.

Pro jednodušší úlohy se používají metody, jejichž chování by se dalo nazvat deterministickým - tzn., že na stejně zadaný problém se stejnými počátečními podmínkami zareagují vždy stejně a naleznou vždy stejné řešení. Význačným představitelem této skupiny metod jsou metody gradientní, jejichž postup při prohledávání stavového prostoru spočívá v tom, že se v každém kroku snaží přejít na nejlepší řešení nalezené v jistém okolí řešení současného. Jejich výhodou je, že vždy naleznou takové řešení, které je na jistém okolí nejlepší (naleznou extrém ztrátové funkce) - nikde ale není zaručeno, že toto řešení je nejlepší v celém stavovém prostoru (hlavně u složitějších, multimodálních ztrátových funkcí). Takto nalezené řešení je ve valné většině případů pouze suboptimálním řešením daného problému a gradientní algoritmus není schopen bez změny počátečních podmínek sám od sebe najít řešení jiné – lepší (ve smyslu ztrátové funkce).

Z toho důvodu bylo nutno vyvinout metody, ve kterých se jistým způsobem uplatňuje náhoda – metody, které nevynechávají pokud možno žádnou oblast stavového prostoru a které jsou samy od sebe schopné “vymanit se ze spárů suboptimálního řešení”. Za tuto kladnou vlastnost ovšem musíme zaplatit tím, že jejich chování je do značné míry chaotické (stejně zadaný problém se stejnými počátečními podmínkami vede pokaždé na zcela odlišný postup hledání řešení a často také na jiné nalezené řešení – i když třeba stejně dobré). Jejich vlastnosti lze popsat pouze pravděpodobnostně, tedy jako jakési “průměrné chování”, od kterého se však chování skutečné může značně lišit. Volbou počtu ohodnocených řešení (prvků stavového prostoru) však můžeme odchylku chování (pravděpodobnost chyby) učinit tak malou, jak chceme.

Mezi tyto metody patří např. simulované žíhání a genetické algoritmy (GA), kterým se věnuje tato práce.

 

Genetické algoritmy

Proč právě “genetické” algoritmy?

Genetické algoritmy se snaží napodobit vývoj takovým způsobem, jakým probíhá v přírodě. Jako teoretický podklad či vzor si berou Mandelovu teorii genetiky a Darwinovu teorii přirozené selekce. V krátkosti – Darwinova teorie říká v podstatě to, že rychlejší, silnější a inteligentnější jedinci mají větší šanci na přežití v dynamickém a neustále se měnícím prostředí, než jiní jedinci – pomalejší, slabší a hloupější. Tito “horší” jedinci ve svém prostředí přežívají spíše díky tomu, že mají štěstí, než díky svým vlastnostem. Proto se reprodukce (vytváření další generace) zúčastňují také, avšak v menší míře, než jedinci “lepší”. Georg Mendel zase objevil mechanismus přenosu charakterových vlastností z rodiče na potomka. Později se ukázalo, že za jednotlivé vlastnosti jsou zodpovědné geny, které jsou uspořádány lineárně v chromozomech.

GA používají také výrazové prostředky převzaté z těchto biologických disciplín. Mluvíme o jednotlivcích (nebo o genotypech, chromozomech, strukturách či řetězcích) v populaci. (Pro potřeby GA se většinou dělá určité zjednodušení: každý biologický jedinec má obyčejně více druhů chromozomů – zde se předpokládají jedinci s jediným chromozomem, proto je možné oba pojmy “sjednotit”. Existují ale také implementace GA s diploidními jedinci – s jedinci se dvěma chromozomy.) Chromozomy jsou dále tvořeny lineárně uspořádanými geny (jinak také rysy, vlastnostmi či dekodéry). Stav genu reprezentujícího určitou vlastnost (např. barvu vlasů) může nabývat několika hodnot, kterým se říká alely. Každý chromozom reprezentuje jedno potenciální řešení problému. Význam a výklad formátu chromozomů – jeho fenotyp – je plně v rukou uživatele. Proces evoluce jedné populace pak odpovídá prohledávání stavového prostoru.

Vlastnosti GA

Prohledávání stavového prostoru obvykle vyžaduje vyvážení dvou (zřejmě protichůdných) požadavků: zaměření prohledávání do slibných oblastí (exploitation) a co nejúplnější prohledání celého stavového prostoru (exploration). Gradientní metody (Hillclimbing) jsou příkladem technik, které důkladně prohledávají okolí nejlepšího dosud nalezeného řešení; na druhou stranu ale úplně ignorují prohledávání zbytku stavového prostoru. Náhodné prohledávání je zase typickým příkladem technik, které prohledávají stavový prostor ignorujíc přitom jeho slibné oblasti.

GA jsou prohledávací metody pro obecné použití (nejsou závislé na typu řešeného problému), u nichž se dá nastavením parametrů upravit rovnováha mezi zaměřením na slibné oblasti a prohledáním co největší části stavového prostoru. Obou těchto vlastností GA používají ke svému prospěchu.

Mnoho výzkumníků i praktiků z velice rozmanitých oborů lidské činnosti si oblíbilo GA. Jejich popularita pramení z jejich vlastností:

Patří do třídy stochastických algoritmů a přesto se velice liší od náhodných prohledávacích metod. Kombinují totiž elementy řízeného i stochastického prohledávání. Další důležitou vlastností GA je, že pracují s celou populací potenciálních řešení – ostatní metody pracují vždy pouze s jedním bodem stavového prostoru, s jediným řešením. Tato populace podstupuje simulovanou evoluci: v každé generaci se “lepší” jedinci množí, zatímco “horší” odumírají. Rozlišení mezi “horší” a “lepší” provádí již výše zmíněná kriteriální ztrátová (ohodnocovací) funkce, která zastupuje v GA roli životního prostředí jedinců.

K řešení určitého problému pomocí GA (nebo jakýmkoli jiným EA) je třeba splnit následující požadavky:

Struktura GA

Běh každého GA se řídí podle následujícího jednoduchého předpisu (P(k) je množina jedinců obhospodařovaných GA v k-té generaci):

k = 0
Inicializace P(k)
Ohodnocení P(k)
Opakuj
| k = k+1
| Selekce P(k) z jedinců v P(k-1)
| Rekombinace P(k)
| Ohodnocení P(k)
Dokud není splněna terminální podmínka

Za krokem Rekombinace P(k) se vlastně skrývá uplatnění dvou genetických operátorů – křížení a mutace. Podívejme se teď na jednotlivé kroky GA podrobněji.

Stavební bloky (Building Blocks), schéma-teorém

V souvislosti s chromozomy u GA se často hovoří o tzv. stavebních blocích. Lze vypozorovat, že mezi přibližně stejně dobrými jedinci v populaci existuje podobnost v tom smyslu, že tito jedinci obsahují na některých svých pozicích stejné bity. Jinými slovy lze říct, že kvalitu jedince hodně ovlivní obsazení určitých konkrétních pozic, zatímco na obsazení ostatních pozic záleží méně. Dobré obsazení těchto konkrétních pozic pak lze nazývat stavebním blokem (dobrý řetězec je pak tvořen dobrými stavebními bloky).

Podobnostmi mezi řetězci se zabývá hypotéza o schématech. Narozdíl od řetězců, které jsou tvořeny pouze abecedou obsahující dva prvky {0,1}, má abeceda schémat navíc ještě jeden prvek - *. Tvoří ji tedy množina {0,1,*}. Pokud se ve schématu objeví symbol *, pak schéma reprezentuje všechny řetězce, které na tomto místě obsahují jakýkoli konkrétní symbol a shodují se v ostatních pozicích se schématem. Pokud tedy schéma obsahuje n symbolů *, pak v případě binární abecedy reprezentuje 2n řetězců.

Každému schématu se přiřazuje jeho řád o(H), což je počet specifických pozic (0 nebo 1) ve schématu. Schéma řádu o(H) obsahuje L-o(H) symbolů *, kde L je délka schématu. Takové schéma tedy pokrývá 2L-o(H) řetězců.

Definiční délka schématu (H) je největší vzdálenost dvou specifických symbolů ve schématu. Schémata řádu 0 a 1 (neobsahují žádný nebo pouze jeden konkrétní symbol) mají definiční délku 0.

Celkový vliv genetických operátorů na schémata vyjadřuje tzv. schéma-teorém:

,

kde jednotlivé symboly mají následující význam:

počet řetězců v populaci odpovídajících schématu H v čase t (v t-té generaci)
kvalita schématu
střední kvalita populace
pravděpodobnost křížení
pravděpodobnost mutace
definující délka schématu
L délka schématu
o(H) řád schématu

Jednotlivé členy v závorce odpovídají postupně selekci, křížení a mutaci, které budou popsány v následujících odstavcích.

Rozborem schéma-teorému (ale i pomocí jednoduché logiky) lze určit, že stavební bloky chromozomů tvoří krátká nadprůměrná schémata nízkého řádu. Krátká proto, aby s co největší pravděpodobností nebyla porušena křížením, a nízkého řádu, aby co nejpravděpodobněji přežila uplatnění mutace.

Selekce

Operátor selekce je vlastně realizací Darwinovy teorie přirozeného výběru. Modeluje princip přežití nejlepšího jedince. Vybírá z populace “lepší” jedince, kteří se pak účastní rekombinace (tvorby potomků). Nejedná se ale o jednoduché vybrání N nejlepších jedinců z populace – selekce musí zaručit i to, že se rekombinace může zúčastnit i nejhorší z jedinců v populaci. To je zaručeno pravděpodobnostními mechanismy výběru jedinců – ke každému chromozomu je na základě jeho kvality (kterou získáme ohodnocovací funkcí) určitým způsobem přiřazena pravděpodobnost jeho přežití. Způsob výpočtu pravděpodobnosti přežití jedince je závislý na použité selekční metodě.

  1. Ruletová selekce (Roulette-wheel selection)
    Pravděpodobnost přežití jedince je přímo úměrná jeho kvalitě. Rozhodnutí, zda jedinec přežije a objeví se i v další generaci, se dá představit jako náhodný pokus, ve kterém točíme ruletovým kolem (odtud i název metody) a vybíráme vždy toho jedince, na něhož padne kulička. Přitom platí, že čím je jedinec kvalitnější, tím více ruletových políček zabírá.
    Toto selekční schéma s sebou ale nese i řadu problémů: má potíže se škálováním, zvládá pouze maximalizační problémy, způsobuje velké vzorkovací chyby a pro správnou funkci vyžaduje relativně velké populace. Pro nápravu těchto vlastností byla vyvinuta další selekční schémata.

  2. Pořadová selekce (Rank selection)
    Pravděpodobnost přežití jedince nesouvisí přímo s jeho kvalitou, ale s jeho umístěním v posloupnosti, kde jsou chromozomy seřazeny podle své kvality. Předpokládejme například, že máme populaci o dvou chromozomech A a B, které byly ohodnoceny f(A)=1 a f(B)=99. Ruletová selekce jim přiřadí pravděpodobnosti přežití p(A)=0.01 a p(B)=0.99. Pořadová selekce je nejprve uspořádá podle velikosti poř(A)=1, poř(B)=2 a nad tímto pořadím už probíhá ruletová selekce. Výsledkem je tedy p(A)=0.33 a p(B)=0.66. Takovýto postup odstraňuje problémy se škálováním (omezuje předčasnou konvergenci), odstraňuje problémy se vzorkováním u malých populací a zvládá maximalizační i minimalizační problémy.

  3. Zbytkový stochastický výběr (Reminder stochastic sampling)
    Jedná se o další modifikaci ruletové selekce. Pro všechny jedince v populaci se vypočítá pravděpodobnost jejich přežití. Na základě této pravděpodobnosti se spočítá počet kopií každého jedince v nové populaci: n(i)=p(i)*PopSize (počet kopií i-tého jedince je pravděpodobnost jeho přežití násobená velikostí populace). Tento počet je ale obecně reálné číslo – každý jedinec se zkopíruje pouze tolikrát, kolik udává celá část n(i). Zbytek, tj. součet desetinných částí všech n(i), udává počet ještě neobsazených míst v nové generaci. Na rozdělení těchto míst se už aplikuje klasická ruletová selekce. I tato metoda napravuje vliv malé populace.

  4. Turnajová selekce (Tournament selection)
    Tato metoda již není úpravou ruletové selekce, využívá jiného principu. Pro obsazení každého jedince v nové generaci se PopSize-krát uspořádá turnaj. Ze staré generace se náhodně vybírají n-tice chromozomů a do nové generace se vkládají vždy nejlepší jedinci z těchto n-tic. Volbou n se dá také ovlivňovat selekční tlak (čím větší n, tím větší selekční tlak). V krajním případě, kdy n = PopSize, by byla nová generace tvořena ze samých nejlepších jedinců generace (předčasná konvergence).

  5. Elitismus
    Elitismus sám o sobě vlastně není selekčním schématem. Je to jen jakási volba, kterou se dají rozšířit ostatní selekční mechanismy. Pokud se jakékoli selekční schéma označí za elitistické, znamená to, že n nejlepších jedinců je v každé generaci bezprostředně zkopírováno do generace následující. Výhodou této volby je, že se nemusí zvlášť udržovat dosud nejlepší nalezené řešení (BSF – best-so-far), protože nemůže během vývoje vlivem náhodných jevů odumřít.

Křížení (Crossover)

Křížení je reprodukční operátor, který vlastně simuluje náhodnou výměnu informací obsažených v rodičích při vytváření nového potomka. Jeho působením by se měly vyvíjet lepší chromozomy (jedinci složení z lepších stavebních bloků).

Křížení může být jednobodové, dvoubodové nebo vícebodové. Body, ve kterých dochází ke křížení, se volí náhodně. Volbou n bodů křížení se oba rodiče rozdělí na n+1 částí. Vlastní křížení probíhá tak, že do prvního potomka se zkopírují např. liché části z prvního rodiče a sudé z druhého. U druhého potomka je tomu opačně. Četnost křížení se volí nastavením pravděpodobnosti křížení, což je jeden ze základních parametrů GA (typicky se volí přibližně 0.75). Zvětšením pravděpodobnosti křížení se ale zvětší nejen rekombinace stavebních bloků, ale také pravděpodobnost, že budou zničeni i dobří jedinci. Optimální hodnota závisí na konkrétním řešeném problému a stanovuje se empiricky.

Mezi další varianty křížení patří rovnoměrné a informované křížení. Rovnoměrné křížení je vlastně n-bodové křížení, u něhož se nevolí n bodů, ale u každého bitu se náhodně rozhoduje s pravděpodobností 0.5, do kterého z potomků bude patřit. Bylo pozorováno, že pomocí křížení se dosahuje rychlejšího prohledávání než pomocí mutace (viz.dále) při použití ztrátových funkcí, které berou v úvahu nelineární vztahy mezi jednotlivými bity řetězců. Pokud je pravděpodobnost, že ke křížení dojde za určitým bitem, závislá na pozici v řetězci, říkáme, že operátor křížení má polohové zaměření. Pokud rozdělení počtu bitů prohozených operátorem křížení není rovnoměrné, říkáme, že křížení má distribuční zaměření. Jednobodové křížení má maximální polohové a minimální distribuční zaměření, zatímco u rovnoměrného křížení je to naopak. Jedno a dvoubodové křížení zachovávají velké množství stavebních bloků, ale v homogenní populaci generují málo odlišné jednotlivce. Rovnoměrné křížení naproti tomu prohazuje bity nezávisle na jejich pozici a zachovává tak pouze menší množství stavebních bloků. Proto se doporučuje používat u menších populací, kde zaručuje prohledání větší oblasti stavového prostoru. Ve velkých populacích, kde se rozmanitost chromozomů (jejich umístění ve stavovém prostoru) zajišťuje spíše jejich počtem, je vhodnější dvoubodové křížení.

Mutace (Mutation)

Na mutaci se obvykle pohlíží jako na méně důležitý, druhořadý reprodukční operátor, který dokáže vrátit nazpět neuváženě ztracené hodnoty genů (alely), zabraňuje předčasné konvergenci a poskytuje možnosti náhodného prohledávání v blízkém okolí “zkonvergované” populace (blízké okolí je třeba chápat jako množinu jednotlivců, kteří se liší od jedinců v populaci změnou v minimálním počtu bitů). Umožňuje GA dostat se z lokálního extrému kriteriální funkce. V některých implementacích se dokonce dynamicky mění podle míry konvergence populace.

Jak často dojde k uplatnění tohoto operátoru určuje pravděpodobnost mutace. Ta se typicky nastavuje na hodnotu velice malou (1% i méně) a je dalším ze základních parametrů GA. Vlastní mutace probíhá ve své základní podobě tak, že se procházejí všechny bity v populaci a s pravděpodobností PM je jejich hodnota změněna na opačnou. Průměrně je tedy změněna hodnota bitů, přičemž všechny mutace se mohou vyskytnout v 1 až nmut chromozomech.

Pokud se pravděpodobnost mutace nastaví velká, ztrácí se výhody GA a prohledávání stavového prostoru přechází v prohledávání náhodné.

Výzkumy ukazují, že u malých populací by měla být nastavená velká pravděpodobnost mutace a opačně. Dá se to vysvětlit tím, že u malých populací tak mutace napomáhá k prohledání větší části stavového prostoru, zatímco u velkých populací je velikost prohledaného stavového prostoru zaručena velikostí populace.

Nahrazovací strategie (Replacement strategies)

Často opomíjeným parametrem GA jsou také nahrazovací strategie. Po selekci se z rodičů pomocí reprodukčních operátorů vytvoří sada potomků, které by měly být součástí nově tvořené generace. Které jedince v populaci ale nahradit nově vytvořenými? Existuje mnoho přístupů. Jeden z nich využívá tzv. nepřekrývajících se populací – tzn., že každá generace je zcela a úplně tvořena novými jedinci, kteří jsou potomky jedinců z generace minulé. Pokud se ale použije překrývajících se populací, je třeba rozhodnout, které jedince “odepsat” a nahradit je nově vzniklými. Potomci mohou např. nahradit své vlastní rodiče, nejhorší nebo náhodně vybrané jedince z populace nebo třeba jedince, kterým jsou nejvíce podobné – to často závisí na konkrétní implementaci. Někdy se také nově vygenerovaní jednotlivci prostě připojí k populaci, z níž jsou potom odebráni nejhorší jedinci, čímž populace opět získá svou původní velikost. Nové chromozomy se tedy do nové generace mohou nebo nemusí dostat – to záleží na jejich kvalitě. Nahrazovací strategie také souvisí s druhy GA, které budou popsány v článku 2.4.

Ohodnocovací funkce (Objective Function)

Ohodnocovací funkce je vlastně jediný element GA, který je zcela a beze zbytku v moci uživatele. Měla by jí být věnována velká pozornost, protože je to právě ona, která řídí celý proces evoluce. Pomocí ní se určuje kvalita jedince (schopnost přežití v okolním prostředí) – ať už přímo nebo nepřímo přes škálovací funkci.


Typy GA

  1. Jednoduchý GA (Simple GA - SGA)
    Tento algoritmus popsal Goldberg ve své knize. Používá nepřekrývající se populace a volitelně i elitismus. V každé generaci vytváří algoritmus zcela novou populaci jedinců. Jako terminální podmínka se dá použít konvergence populace. Úplné konvergence (neboli nulového rozptylu) se díky náhodným procesům dosahuje velice těžko, proto se populace považuje za zkonvergovanou, pokud rozptyl klesne pod jistou prahovou hodnota rozptylu. Samozřejmě lze použít i jiné terminální podmínky – např. počet generací.

  2. GA se stálým stavem (Steady-State GA)
    Tento algoritmus je podobný algoritmu popsanému DeJongem. Používá překrývající se populace – tzn., že uživatel musí určit, kolik potomků se má generovat (jak velká část populace se má nahrazovat). Pro tuto část populace je třeba zvolit také způsob, jakým se mají vybrat jedinci k nahrazení - je třeba vybrat nahrazovací strategii. Je možné použít stejné typy terminálních podmínek jako u SGA.

  3. Inkrementální GA
    Jedná se o variantu předchozího typu GA. Také používá překrývající se populace, ale pouze s velice malým překrytím. Typicky se v každé generaci vytvoří pouze jeden nebo dva potomci. I zde je třeba určit nahrazovací strategii. Nejčastěji se nahrazují nejhorší jedinci v populaci.

  4. Mikro GA (GA)
    Nevýhodou SGA je časová náročnost, která je způsobená nutností ohodnocení všech členů populace v každé generaci. Jednou z možností, jak tuto nevýhodu odstranit, je použít GA. Jedná se o variantu GA s velice malou populací. Ukazuje se, že GA se dostává do oblasti blízké optimu rychleji než SGA.
    Oproti SGA používá
    GA mnohem menší populace – typicky o 5 jedincích. Je obecně známo, že obyčejné GA s malými populacemi nevykazují dostatečně dobré chování díky nedostatku informací ke zpracování a předčasné konvergenci k suboptimálnímu řešení. Klíčem k úspěšnému prohledání stavového prostoru i s takto malou populací je pravidelné zavádění nových jedinců do populace. U tohoto typu GA se téměř vždy volí elitistická selekce.
    Cílem
    GA je nalezení optimálního řešení v co nejkratším čase, nikoli jeho “průměrné” chování. Jako míru kvality tohoto typu GA je proto třeba brát BSF a žádné jiné statistické “průměrovací” míry.

  5. GA se stochastickým kódováním (Stochastic GA)
    Tento algoritmus se uplatňuje hlavně při optimalizačních úlohách s velkým počtem parametrů. Tyto úlohy mívají obvykle velice obsáhlý stavový prostor, jehož prohledání by trvalo neúnosně dlouho. Je proto třeba napřít úsilí do slibných oblastí stavového prostoru, zatímco v méně slibných ho omezit, nikoli však úplně zrušit. To je zajištěno dynamickým kódováním řetězců, které nepředstavují konkrétní řešení daného problému, ale prohledávané regiony stavového prostoru. Každý region je charakterizován normálním Gaussovým rozložením s vektorem středních hodnot a s variační maticí. Vektor středních hodnot udává očekávané hodnoty parametrů v prohledávaném regionu, zatímco variační matice udává pravděpodobnost nalezení optimálního řešení v určité oblasti prohledávaného regionu. V průběhu evoluce se pak mění právě popis rozdělení, tj. střední hodnoty a variační matice, čímž se celá rozdělení (prohledávané regiony) posouvají do slibnějších oblastí stavového prostoru.

  6. Nalezení většího počtu extrémů – Niching
    Předpokládáme-li dostatečně dlouhou dobu běhu GA, všichni jedinci se po určité době budou nalézat v okolí globálního extrému, odkud čas od času některý chromozom “uteče” vlivem náhodných jevů (mutace). Pokud ale chceme nalézt větší počet řešení, je třeba zajistit, aby GA obhospodařoval stabilní populace na okolí několika extrémů. To provádí technika zvaná Niching (od Niche – nika, výklenek), která zajišťuje jakousi “normalizaci” kvality jedinců na různě dobrých extrémech. Vytváří vlastně různé životní podmínky (upravuje výstupy z ohodnocovací funkce) pro jedince nacházející se blízko různých extrémů. V každém tomto výklenku (upraveném životním prostředí okolo některého extrému) se vyvíjí část populace. Počet jedinců v té které části populace je vlastně jinou mírou kvality extrému, který tato část populace obývá. Při určování kvality jedinců v populaci se pak výstup ohodnocovací funkce upravuje podle příslušnosti k určitému výklenku, a to nepřímo úměrně – čím vyšší kvalita extrému, tím více se sníží ohodnocení jedinců. Tím se vlastně vyrovnají “výšky” extrémů, což umožní vývoj stabilních populací na několika z nich, protože jedinci ze všech výklenků budou mít přibližně stejnou šanci na přežití.
    Příslušnost jedince k výklenku určuje buď míra s vlastnostmi vzdálenosti (časově a výpočetně náročnější určení) nebo “značka”, která je součástí chromozomu, ale neúčastní se evoluce.

Práce s omezeními

Omezením není myšleno určení rozsahu každého z parametrů. Určení rozsahu parametrů vymezuje vlastně stavový prostor úlohy – n-rozměrný interval (hyperkrychli), ve které GA vyhledává řešení. Problémy nastanou až tehdy, když je obor přípustných řešení podmnožinou prohledávacího prostoru. To se může stát např. tehdy, když jsou jednotlivé parametry optimalizované pomocí GA na sobě vzájemně závislé. Co pak udělat s jedinci, kteří vzniknou působením rekombinačních operátorů, ale přitom představují nepřípustná řešení?

Používají se v zásadě tři postupy, jak se s takovými omezeními vypořádat.

  1. Pokutové funkce
    Nevyhovující řešení je ponecháno v populaci, ale záměrně se prohlásí za velice málo kvalitní, takže v dalším běhu GA samo “odumře”. Tato metoda je velice jednoduchá, ale efektivně pracuje pouze u slabých omezení, kde poměr počtu přípustných řešení ku počtu prvků prohledávaného prostoru není příliš malý. Pokud je totiž většina vygenerovaných řešení přípustná, pak malé množství nepřípustných řešení se v každé generaci opravdu eliminuje. Pokud by byla ale většina vygenerovaných nepřípustná, pak je velká šance, že tato nepřípustná řešení budou přežívat i do dalších generací.

  2. Dekodéry a opravné algoritmy
    Na nelegální jedince se snažíme uplatnit speciální postupy, kterými by se jednotlivci “legalizovali”. Tyto postupy obyčejně vyžadují transformaci genotypu na fenotyp a bývají výpočetně velice nákladné.
    Existují dvě varianty těchto postupů:
    OPRAVA fyzické nahrazení nevyhovujícího jedince v populaci nejbližším vyhovujícím (ve smyslu nějaké metriky). Tato náhrada se pak účastní další evoluce.
    DEKÓDOVÁNÍ nepřípustný jedinec zůstane v populaci a účastní se další evoluce. Pro určení jeho kvality se ale použije ohodnocení nejbližšího přípustného řešení


  3. Problémově závislá reprezentace, speciální rekombinační operátory
    Ideálním řešením problému s omezeními by bylo, kdyby se povedlo najít takovou reprezentaci řešení úlohy, jejíž každá instance by byla řešením přípustným. Jinou možností je najít takové rekombinační operátory, které by generovaly pouze přípustná řešení. Nalezení jednoho ani druhého však není obecně jednoduchou úlohou (spíš naopak) a často se oba přístupy kombinují. Takto sestavený GA je pak ale specifický pro jeden konkrétní typ úlohy.