Ugrás a tartalomhoz

Genetikus algoritmus

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

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

[szerkesztés]

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

[szerkesztés]

A genetikus algoritmusok sokfélék lehetnek, de az alábbi részeket mindig tartalmazzák:

Inicializáció

[szerkesztés]

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

[szerkeszté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 fitnesz fü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

[szerkeszté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

[szerkeszté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

[szerkesztés]
  • Á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