Genetikus algoritmusok

Ez a lecke a Microsoft nyílt forráskódú "AI kezdőknek" (AI For Beginners) tananyagának magyar adaptációja. A genetikus algoritmusok az AI egyik evolúciós megközelítését képviselik. Az alapötlet, hogy egy populáció folyamatos fejlődésének módszereit használjuk fel egy adott probléma optimális megoldásának megtalálására. A módszert 1975-ben John Henry Holland javasolta, és azóta is az egyik legintuitívabb módja annak, hogy egy számítógép ismeretlen, bonyolult keresési térben találjon jó megoldást anélkül, hogy minden lehetőséget végig kellene próbálnia.

A megközelítés lényege, hogy a lehetséges megoldásokat úgynevezett génekként kódoljuk, majd ezekkel a génekkel a biológiai evolúcióhoz hasonló műveleteket végzünk. Két megoldást keresztezhetünk, hogy egy új, remélhetőleg jobb megoldást kapjunk, a gyengébb megoldásokat kiszelektáljuk, a génekbe pedig időnként mutációt viszünk be, hogy a keresés ne ragadjon be egy lokális optimumba.

A módszer négy építőköve

Egy genetikus algoritmus megvalósításához négy dolgot kell meghatároznunk.

• Kódolás. Meg kell találnunk egy módot, ahogyan a probléma egy adott megoldását génként tudjuk reprezentálni, jellemzően egy számsorozat vagy bitvektor formájában.
• Fitneszfüggvény. Egy függvényre van szükség, amely minden génhez egy számot rendel, és megmutatja, mennyire jó az adott megoldás. Minél kisebb az érték, annál jobb a megoldás.
• Keresztezés. Egy mechanizmus, amely két gént kombinál, és belőlük egy új, érvényes megoldást állít elő.
• Mutáció. Egy mechanizmus, amely egy gént kis mértékben megváltoztat, ezzel új variációkat vezetve be a populációba.

A legtöbb esetben mind a keresztezés, mind a mutáció viszonylag egyszerű művelet, hiszen a géneket gyakran csak számsorozatként vagy bitvektorként kell manipulálni.

Hogyan fut le az algoritmus

A konkrét megvalósítás esetenként eltérhet, de az általános menet a következő. Először kiválasztunk egy kezdeti populációt, azaz néhány kezdeti megoldást. Ezután minden lépésben véletlenszerűen eldöntjük, hogy keresztezést vagy mutációt hajtunk végre. Keresztezésnél két gént választunk ki a populációból, kiszámítjuk a keresztezésükből adódó új gént, és ha ez az új megoldás jobb, mint valamelyik szülője, lecseréljük vele a populáció megfelelő tagját. Mutációnál egy véletlenszerűen kiválasztott gént módosítunk kissé. A folyamatot addig ismételjük, amíg a fitneszfüggvény értéke elég kicsivé nem válik, vagy amíg el nem érjük a lépésszám korlátját.

Fontos hangsúlyozni, hogy a genetikus algoritmus nem garantálja a globálisan legjobb megoldást, viszont viszonylag kevés számítási erőforrással is használható, jó minőségű közelítő megoldást ad, ahol a kimerítő keresés túl lassú lenne.

Tipikus alkalmazási területek

A genetikus algoritmusokat elsősorban olyan feladatokra használjuk, ahol rengeteg lehetséges megoldás közül kell egy jót megtalálni, és a keresési tér túl nagy ahhoz, hogy minden kombinációt kipróbáljunk. Jellemző alkalmazási terület az ütemezés optimalizálása, az optimális csomagolás, az optimális vágás, valamint általánosságban a kimerítő keresés felgyorsítása. Ezek a feladatok mind rendelkeznek egy közös tulajdonsággal, egyértelműen meg tudjuk fogalmazni, mi számít jó megoldásnak, de a lehetséges megoldások száma olyan hatalmas, hogy egyenkénti kipróbálásuk kivitelezhetetlen lenne.

Mit érdemes megjegyezni

A genetikus algoritmusok érdekessége, hogy egyszerű implementálni őket, mégis a viselkedésük gyakran nehezen érthető és nehezen jósolható meg előre. A terület a pszichológia és a számítástechnika találkozásából született, és a mai napig aktívan használt eszköz logisztikai, tervezési és keresési problémák megoldására. Az elv szemléletes bemutatása, amikor egy neurális hálót genetikus algoritmussal tanítanak be arra, hogy videojátékokat játsszon, például egy klasszikus platformer szintjeit végigjátssza próba és tévedés útján, generációról generációra javuló teljesítménnyel.

Gyakorlati oldalról a genetikus algoritmus különösen olyan helyzetekben erős, ahol a probléma jól kódolható számsorozatként vagy bitvektorként, de a döntési tér mérete miatt a hagyományos, determinisztikus optimalizálási módszerek túl lassúak vagy egyáltalán nem alkalmazhatók. Egy jó fitneszfüggvény megtervezése gyakran a legnehezebb rész, hiszen ennek kell tömören és pontosan megfogalmaznia, mit is jelent valójában a jó megoldás. Ha a fitneszfüggvény rosszul van megválasztva, az algoritmus akár egészen más irányba is konvergálhat, mint amit eredetileg szerettünk volna elérni, ezért érdemes időt szánni a probléma alapos megfogalmazására, mielőtt a kódolásba kezdenénk.

Gyakorlati kód

Ha szeretnéd saját kezűleg is kipróbálni a genetikus algoritmus működését, a Microsoft eredeti jegyzetfüzete két konkrét példán mutatja be a folyamatot, egy kincsek igazságos elosztásáról szóló feladaton és a klasszikus 8 királynő problémán. Gyakorlati kód a GitHubon.

Forrás

Ez a lecke a Microsoft nyílt forráskódú, MIT licenc alatt elérhető "AI For Beginners" tananyagának magyar adaptációja. Eredeti angol lecke. GitHub. Felhasznált magyar gépi fordítás. GitHub.