Prírodou inšpirované algoritmy

Koevolúcia

Koevolúcia

Existuje tu viacero populácií jedincov, pričom jedince jednej populácie kódujú celé riešenie problému. Všetky ostatné populácie sú pomocné, pomáhajú základnej populácii nájsť riešenie. Môžu kódovať niečo úplne iné, resp. takisto môžu kódovať riešenie. Medzi populáciami dochádza k vzájomnej interakcii, jedince jednej populácie nepriamo ovplyvňujú jedince druhej. Niekoľko spôsobov koevolúcie:

Parazitická koevolúcia

Vychádza z biologickej predstavy súžitia organizmov a parazitov. Organizmus sa musí voči parazitovi brániť, vyvíja si metódy obrany, a parazit musí vymýšľať nové a nové spôsoby útoku. Jednu populáciu predstavujú riešenia - "organizmy". Druhú populáciu "parazity". Obe populácie sa vyvíjajú a vzájomne sa ovplyvňujú vhodnosťou. Vhodnosť "organizmu" je daná tým, ako sa vie ubrániť, a vhodnosť "parazitov" tým, koľko jedincov sa im nie je schopných brániť.

Koevolučné zdieľanie

Snaží sa nájsť viacero riešení naraz. Vychádza z ekonomickej metafory. Jednu z populácií tvoria spotrebitelia a druhú obchodníci. Obe populácie kódujú riešenie problému. Spotrebitelia sa snažia ísť do oblasti s vyššou vhodnosťou (k čo najlepším obchodníkom) a kde je menej zákazníkov, aby sa im ušiel tovar (rozliezanie sa zákazníkov po priestore). Obchodník je tým lepší, čím lepší spotrebitelia k nemu chodia. V oblasti, kde je veľa obchodníkov, majú títo menej zákazníkov, preto sa takisto ako zákazníci rozliezajú po priestore. Na vývoj populácie sa použijú rôzne princípy, takže bude mať zmysel vymieňanie genetického materiálu medzi populáciami.

Koevolúcia pre viackriteriálne problémy

Aplikácia multikriteriálnych problémov na teóriu hier. Riešenie problému predstavuje celá hra, súbor kariet všetkých hráčov. Na ťahu je vždy jeden z hráčov, pričom sa snaží zlepšovať svoju pozíciu (zlepšovanie podľa jedného kritéria). Takto to pokračuje až do dosiahnutia rovnováhy v rámci všetkých hráčov. Existuje toľko populácií, koľko je častí riešenia, pričom v rámci každej populácie sa optimalizuje len jedna časť riešenia a ostatné sú fixované. Po čase si každá populácia obnovuje fixnú časť podľa toho, aké najlepšie riešenia našli zvyšné populácie.

Koevolúcia pre problémy s ohraničeniami

Jednu populáciu tvoria kandidáti na riešenie a druhú populáciu jedince predstavujúce ohraničenia. Táto druhá populácia sa nemení, je to tzv. pseudopopulácia, mení sa len vhodnosť ohraničení, ktorá je daná počtom riešení nespĺňajúcich dané ohraničenie. Populácia riešení sa vyvíja normálne, pričom ich vhodnosť je daná počtom splnených vybratých ohraničení. Výber ohraničení je na základe ich vhodnosti. Pri vývoji jedincov sa ohraničenia postupne delia na ľahšie a ťažšie (splní ho menej jedincov). Výsledným riešením je jedinec, ktorý splní všetky, aj ťažké ohraničenia.