Genetikus algoritmus

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.

Kiválasztás

Minden sikeres generációban a jelenlegi populáció egy része kiválasztásra kerül szaporodásra. Általában fitnesz alapján történik, ahol a fittebb egyedek (a fitneszfüggvény szerint) valószínűbben kerülnek kiválasztásra. Bizonyos metódusok minden egyed fitnesz-ét megnézik és választják ki a legjobbat, de más metódusok csak néhány, véletlen példányt néznek meg, mert a teljes folyamat túl hosszú lenne.

A fitness függvény a példány minőségét méri. A függvény mindig probléma függő.

Néhány problémánál nehéz, akár lehetetlen definiálni a fitnesz számolás műveletét; ilyenkor a példány fenotípusát is használhatjuk, vagy akár interaktív kiválasztást is használhatunk.

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 előállítani. Ezeket az operátorokat általában véletlenszerűen alkalmazzák.

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.

További információk

• Álmos Attila – Dr. Horváth Gábor – Dr. Várkonyiné dr. Kóczy Annamária – Győri Sándor: Genetikus algoritmusok, Typotex Kiadó 2003. ISBN 978-963-9326-45-3