Genetikus algoritmusok alatt olyan keresési technikák egy osztályát értjük, melyekkel optimumot vagy egy adott tulajdonságú elemet lehet keresni. A genetikus algoritmusok speciális evolúciós algoritmusok, technikáikat az evolúcióbiológiából kölcsönözték.
Módszertan
A genetikus algoritmusokat számítógépes szimulációkkal implementálják. A keresési tér elemei alkotják a populáció egyedeit, melyeket keresztezni (más szóval rekombinálni) és mutálni lehet, így új egyedek hozhatók létre. A keresési téren értelmezett célfüggvényt ebben a kontextusban szokásos fitness függvénynek is nevezni. A genetikus algoritmus működése során egyrészt új egyedeket hoz létre a rekombináció és a mutáció operátorokkal, másrészt kiszűri a rosszabb fitness függvény értékkel rendelkező egyedeket és eltávolítja a populációból. Egyes esetekben az ilyen algoritmusok konvergálnak az optimumhoz.
Részei
A genetikus algoritmusok sokfélék lehetnek, de az alábbi részeket mindig tartalmazzák:
Inicializáció
A kezdeti populációt legegyszerűbb véletlenszerűen generálni. A populáció mérete a probléma természetétől függ, de leggyakrabban néhány száz vagy néhány ezer egyedből áll. Hagyományosan az egyedek a keresési téren egyenletesen oszlanak el, viszont egyes esetekben olyan részeken több egyedet generálnak, ahol sejthető az optimum.
Szaporítás
Egyedekből újabb egyedeket a kétoperandusú keresztezés (vagy rekombináció) művelettel, és az egyoperandusú mutáció művelettel lehet. Ezeket az operátorokat általában véletlenszerűen alkalmazzák.
Kiválasztás
Az egyedek generálása után kiválasztásra (idegen szóval szelekcióra) kerül sor. A kiválasztás lehet determinisztikus vagy stochasztikus. Az első esetben szigorúan az egy adott küszöbértéknél jobb fitness értékű egyedek maradnak fenn, a stochasztikus kiválasztásnál a rosszabb fitness értékkel rendelkező egyedek közül is néhány fennmarad. A stochasztikus megoldás népszerűbb, mert elkerülhető vele a lokális optimumhoz való konvergencia.
Leállás
A genetikus algoritmusok rendszerint addig futnak, amíg egy leállási feltétel nem teljesül. Gyakori leállási feltételek a következők:
- Adott generációszám elérése.
- Ha a legjobb egyed fitness értéke már nem javul jelentős mértékben egy-egy iterációval.
