Prírodou inšpirované algoritmy

Problémy s ohraničeniami

Problémy s ohraničeniami

Priestor riešení obsahuje časti, ktoré sú neprípustné ako riešenia daného problému. Neprípustné riešenia sa môžu objavovať jednak pri prvotnej inicializácii populácie a jednak pri aplikácií genetických operátorov, pričom je potrebné zabezpečiť, aby výsledné riešenie bolo z množiny prípustných. Možné prístupy riešenia:

• Penalizačné funkcie: Umožňujú prechádzať aj cez zakázané regióny, pričom ku vhodnosti jedincov sa pridáva penalizačná funkcia, penalizujúca jedincov zakázanej oblasti. Možno ich použiť len na problémy, pri ktorých sa dá určiť vhodnosť aj v zakázanej oblasti. Nastavenie samotnej penalizácie býva problém. Pri veľmi veľkej penalizácii, ak je väčšina jedincov v zakázanej oblasti, akonáhle vznikne nepenalizovaný jedinec, všetko ťahá k nemu, stáva sa superjedincom. Naopak pri slabej penalizácii, nedostatočnej, môže konvergovať k bodu v zakázanej oblasti. Preto sa používa napr. smrteľná penalizácia, kde najhorší z dovolených má vyššiu vhodnosť ako najlepší zo zakázaných, resp. mierna penalizácia, ktorá je tesne nad hraničnou, pod ktorou by vždy skonvergoval do zakázanej oblasti.
• Dekódery: Pracujú len s prípustnými riešeniami. Dekóder každému genotypu priradzuje len prípustný fenotyp. Genotypy sa neobmedzujú. Toto sa však nedá robiť všeobecne, návrh dekóderu je doménovo závislý a často tak zložitý, že by znamenal vyriešenie celého problému.
• Opravné procedúry: Sú veľmi podobné dekóderom. Na rozdiel od nich sa však použijú len na neprípustné body, ktoré modifikujú na prípustné. Nie sú až tak doménovo závislé, je možné použiť aj náhodnú zmenu zložiek riešenia (slepé prehľadávanie).
• Špecializované algoritmy (dedikované): Prispôsobené konkrétnemu riešenému problému tak, aby bolo zaručené, že jedince zakázanej oblasti nevzniknú. Ide o prispôsobenie genetických operátorov.

Najjednoduchšie je nerobiť nič a spoľahnúť sa, že algoritmus skonverguje správne, najideálnejší spôsob by bol dedikovaný algoritmus, no najpoužívanejšia je penalizácia.