A genetikus algoritmusok olyan speciális algoritmusok (adaptív heurisztikus keresés), amik bizonyos jól behatárolt problémák megoldását sok esetben optimálisan (de nem feltétlenül a legjobban) elvégzik. Charles Darwin óta sokan úgy gondolják 🙂 hogy az evolúció létezik, és az evolúció adta az ötletet ennek az algoritmusnak a különböző variációinak a létrehozásához is.
Egy fokkal bonyolultabb példa, másik hasonló példa.
Röviden (és esetenként nem teljesen szakmai nyelven) szeretném bemutatni, miről is van szó..
Legyen a példánk egy versenypálya, amin végig kell menjen egy versenyautó teljesen egyedül (esetleg hozzátehetjük, hogy a lehető legjobb időt elérve, de egyelőre elégedjünk meg ennyivel: menjen végig).
Adott helyen vannak az adott tulajdonságú (hossz, irány, szög) kanyarok, egyenesek, amik pedig (a verseny alatt legalábbis) sosem változnak és feltesszük azt is, hogy nem lesz sem versenytárs, sem egyéb dolog (madár, ember, mentőautó) a pályán az autóval egidejűleg.
Első lépésben létrehozunk sok (legyen a példánkban 1000) versenyautót, őket betesszük a rajtvonal mögé (kezdeti populáció = 1000).
Minden egyed (hasonlóan az állatvilágban a példányokhoz) rendelkezik induló tulajdonságokkal (génkészlettel), amik kismértékben eltérnek egymásétól. Például végsebesség, kanyarodási sebesség és hajlandóság, kanyarodási irány véletlenszerűsége stb.
Elindítjuk ezt a kezdeti populációt egy versenyen, majd kiválasztjuk belőlük az első 500 legjobb helyezést elérőt – aki a legtovább ért a pályán. Első alkalommal (szinte) 0 az esélye, hogy bármelyik versenyzőnk végigmegy a pályán, és az is, hogy ugyanarra megy, ugyanott esik ki (köszönhetően a kismértékben eltérő génkészletnek). Az első 500 helyezett (továbbjutók) kiválasztása úgynevezett fittnesz függvény segítségével történik. Ezt a függvényt megfelelően kell definiálni, hiszen a jól megválasztott függvény adja meg, milyen problémát is szeretnénk megoldani. Például itt a feltétel a „legmesszebre jutás” hiszen teljesíteni akarjuk a pályát.
A kiválasztás után az első 500 versenyzőt „szaporítjuk”, azaz újabb egyedeket hozunk létre párok tulajdonságainak vegyítésével, illetve a véletlent is szokás ebben az esetben használni.
A „szaporítás” eredményeként ismét 1000 egyed fog indulni a következő versenyen.
Addig ismételjük ezeket a lépéseket – kiválasztást, szaporítást, futtatást – amíg nem lesz egy generáció, akinek egy vagy több egyede át nem lépi végre a célszalagot.
Fontos, hogy az algoritmusnak adjunk leállási feltételt, ami lehet adott generációszám elérése, vagy a probléma megoldása, azaz a cél elérése, esetünkben a célszalag átlépése.
Természetesen ennél sokkal szakmaibban (és bonyolultabban) is le lehet írni, itt most igyekeztem leegyszerűsíteni, amit lehet.
Használhatunk ilyen algoritmust tervezésben (CAD), hálózati eszközök tervezésében, ipari folyamatok szabályozásánál, játékokban, termelési/pénzügyi/logisztikai folyamatokban stb. a lehetőségek száma szinte határtalan. Fontos tudni, hogy nem mindig a legjobb, optimális megoldást találjuk meg, de sokszor „elég jót”!
Amennyiben szeretnél a saját folyamataidra egy módszertant – akár genetikus algoritmust – bevezetni, vagy van egy ötleted: keress fel bátran.