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.
Tartalomjegyzé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.
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. Ezeket az operátorokat általában véletlenszerűen alkalmazzák.
Kiválasztás [szerkeszté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 [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
 |
Ez az informatikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |
