Genetikus algoritmus

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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

Inicializáció[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

  • Á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