Az evolúció kiváló szolgálatot tett az élet számára, hiszen a kozmikus skálán szinte csak villanásnyinak tekinthető idő alatt elképzelhetetlenül bonyolult és összetett létformák kialakulását tette lehetővé a legegyszerűbb organizmusokból. Ezt a hihetetlenül erősnek bizonyult technológiát azonban az élet mellett mi magunk is felhasználhatjuk számítástechnikai problémáink megoldására.
Egyáltalán mi az a genetikus algoritmus ?
A feladatmegoldásban használatos lineáris módszerek
mellett egyre több helyen alkalmaznak olyan, egyéb elven alapuló
technológiákat, amelyeket a természet és a biológiai rendszerek
ihlettek. Hogy miről is van szó pontosan ?
Hagyományos megoldásoknál az adott problémára
megpróbálunk matematikai módszereket bevetni, azaz:
képleteket, egyenleteket, matematikai
kifejezéseket fordítunk („helyezünk”) számítógépes
futtatási környezetbe és az algoritmusok egymásra építésével,
valamint a számítógép „hibátlan” kalkulációs
képességével kívánunk eljutni a megoldáshoz.
az informatikai eszközök számítási
gyorsaságával (és így a lehetőségeknek az emberéhez képest rövidebb
idejű végigpróbálásával) igyekszünk megtalálni a megoldást.
Ezek az eljárások nagyobbrészt determinisztikus
(megjósolható számítási és futásidejű) kódokat eredményeznek,
azonban minden feladathoz külön-külön kell „feltalálni”
őket. Például egy statikai jellegű számítást másképp végzünk,
mint mondjuk egy statisztikait, mások az alkalmazott képletek.
Ráadásul, ha kicsit is módosul az alapelv, újra kell őket építenünk,
mert nem adaptív természetűek.
A velük megoldható feladatok
például: szimulációk (gravitáció, részecskeelmélet stb.), jól
modellezhető egyenletrendszerek, könnyen leírható, szövegesen
körbehatárolható területek, matematikai-fizikai számítások.
Az utóbbi időkben nagy
teret hódítottak az alternatív programírási- és feladatmegoldási
módszerek.
I. ábra - Egy szabályozáson alapuló számítógépes rendszer hatásvázlata
A létrejöttük igényét az ösztönözte,
miszerint egyes feladatkörök:
túl általánosak (vagy éppen egyediek), ezért
(még ?) nem létezik rájuk konkrétan megfogalmazható és matematikai
alakban felírható képlet
túl sok ismeretlen van a megoldandó
„egyenletben”
az ismeretlen értékek (változók) közötti
összefüggések is ismeretlenek, vagy nem tudjuk őket körvonalazni
a feladat megoldásához vezető úton túl sok
bemenő értéket kellene megvizsgálni lineáris módszerrel
a bemenő értékek változhatnak, ezért a rendszer
tanulás (alkalmazkodás) nélkül hamar életképtelenné válik
Az alternatív módszerek a
hagyományos technológiákhoz képest merőben eltérő módon működnek:
természettudományos alapokból merítenek ötletet.
Ilyen példának okáért az
idegrendszer működését szimuláló „neurális hálózat”
(„neural network”, „NN”), vagy a cikkünkben
kivesézésre kerülő a „genetikus algoritmus” („genetic
algorithm”, „GA”), de sok más irányzat is létezik
(sejtautomaták, mesterséges intelligencia („AI”), fuzzy
logika stb.).
A velük megoldható feladatok például: vezérlés,
irányítás, optimum számítások, valamint minden olyan terület, amire
nem tudunk egzakt megoldást leképezni (ismeretlenek az
összefüggések), vagy éppen adaptációt igényelnek.
Közös jellemzőik:
általánosak (lehetnek)
lassúak (lehetnek)
nem megjósolható a befejezési idejük (nem
tudjuk kijelenteni, hogy véget értek-e/érnek-e egyáltalán), mivel
összefüggéseik tekintetében nem vagyunk képesek megmondani,
megtaláltuk-e a legoptimálisabb megoldást, sőt, sokszor azt sem
tudjuk lemérni, optimális-e az adott eredmény
különféle állapottereket használva működnek
ezen állapottereket befolyásoljuk egy vagy több
hibaellenőrző és visszaterjesztő algoritmussal
beragadhatnak úgynevezett lokális minimumokba
(részmegoldásokba), ami nem fogja az optimális eredményt
szolgáltatni
más-más belső állapotokat vehetnek fel többszöri futás
esetén.
alapvetően más szemléletet igényelnek mind
kialakításban (tervezés), mind a futtatás során
képesek bizonyos szintű tanulásra
általában valamilyen korrekciós eljárás
(visszacsatolás, visszaterjesztés) és/vagy a várt és kapott
eredmények közötti különbségképzés áll működésük középpontjában
óriási előnyük, hogy párhuzamosíthatóak
szálakkal, gyermek folyamatokkal. Például a genetikus algoritmusnál
azonos felépítésű alrendszereket építhetünk, párhuzamosan együtt
futtatott nagyszámú populációval. Miután az al-populációknak nemigen
kell egymással kommunikálniuk (legfeljebb a ritka „vérfrissítő”
géncsere, vagy egyéb szinkronizálás esetén) nem szükséges
processzoridőt igénylő összehangolásuk. Az elosztott működés (akár
több gép között is) kiválóan megvalósítható. Sőt, tranzakciós
rendszerű, központi adattárban történő tárolás esetén egy-egy
folyamat kiesése esetén más is átveheti a futtatás jogát, ugyanis
maga az algoritmus a teljes rendszer állapotát lementve, majd
visszatöltve probléma nélkül képes folytatni a működését !
az alternatív módszereket kombinálni is lehet.
Például genetikus algoritmussal visszacsatolt neuronhálók is
készíthetőek.
Megjegyzés:
körülbelül úgy kell elképzelni az ilyen jellegű algoritmusok
működését, mint egy hegyvidéken történő túrát, ahol meg kell találjuk
a legalacsonyabb völgyet (és benne az biztonságot nyújtó
menedékházat). A háromdimenziós térben többféle módszerrel tudunk
navigálni. Az első, a lineáris módszer kelettől-nyugatig,
északról-délig fogja kutatni a mélypontot. Esetleg finomít a
megoldáson és csak minden 3. kilométer találkozási pontjain fut
végig... Az alternatív módszerek tudják követni a hegyvonulatokat
és megtalálják a mélypontokat, de azt, hogy mikor, vagy hogy
létezik-e még alacsonyabb szint, azt nem fogják tudni megmondani.
A „neurális hálózat” (vagy neuronhálózat
- röv. NN) az idegrendszert szimulálja:
II. ábra - A neuronháló leképezése
A rendszer a neuronokat és a köztük lévő
kapcsolatokon (nyúlványok) keresztül terjedő idegingerületeket
képezi le digitális formába. Most bővebben nem taglaljuk, csupán
megemlítjük. Ami számunkra fontos, hogy bizonyos közös fogalmak
felmerülnek a genetikus algoritmus kapcsán is (később). Ezek:
lokális minimum, beragadás, visszacsatolás, tanulás (adaptáció).
A „genetikus algoritmus” (röv. GA)
alapelve a természetes kiválasztódás
E módszernél egy populáció egyedei (ezek jelképezik
a különféle megoldásokat) küzdenek a túlélésért. Azonban a túlélést
egy egyed számára nem a „gyorsasága”, „ereje”,
„leleményessége” (lásd mint a természetben), hanem a
feladat megoldásában való eredményessége biztosítja.
Az egyedek szekvenciákkal (génekkel) rendelkeznek
(tulajdonképpen ezekből épülnek fel). A gének írják le külső-belső
állapotukat, „milyenségüket”: ezek a feladatrendszer
leképzésének alapelemei (változók, ismeretlenek stb.). Az egyedek
öröklődési folyamata során a gyermekek e géneket (vagy egyeseket
közülük) fogják továbbvinni.
A módszer alkalmazása során a természetes
kiválasztódás alapelvei érvényesülnek. A „jó” génekkel
rendelkező egyedek gyermekei nagyobb eséllyel fognak hasonlóan jó
génkészletet örökölni, azaz a „jó jót szül”. Ezáltal a
gyermekek a populációban résztvevő „jó” egyedek
részarányát megnövelik, egyre inkább a megoldás felé tolva a
rendszerben a hangsúlyt és a részeredményeket. Az egyedek közül a
gyengébbek (kevésbé eredményesek) elpusztulnak (törlődnek a
populációból).
III. ábra - Az öröklődés folyamata
IV. ábra - Szelekció és túlélés a genetikus algoritmusban
A módszerben először is leképezzük a rendszer
alapelemeit (változók, ismeretlenek, állapottér) génekké, a géneket
pedig szekvenciákká (pl. kromoszómák, génlisták), ezekkel pedig az
egyedeket fogjuk felépíteni. Eze követően meghatározott szabályok (lásd
szelekciós függvény) alapján két véletlenszerűen kiválasztott egyedet
különféle génmanipuláló – örökítő, vagy valamely matematikai
(pl. összegző, kivonó, átlagoló stb.) – műveleteknek vetünk
alá, miknek az eredménye hasonló, vagy épp eltérő génekkel rendelkező
egyedek megszületése lesz. A gyermek egyedek egyes (vagy teljes)
génszakaszaikban szüleik szekvenciáit tartalmazzák (öröklik), míg
másokat mutációval kapnak (amelyet egy arányértékkel, rátával fogunk
determinálni – ezen érték keretein belül az egyedek génkészlete
torzuláson, változáson megy keresztül).
Az egyedek mindegyike rendelkezik egy mutatóval,
amellyel eredményességét mérjük (ezt az algoritmusban éppen a nevével
ellentétes módon számítjuk: egy értékelő függvény hibaértéket
kalkulál az adott egyedre és a rendszer e hibát próbálja majd
minimalizálni).
Például: egy útvonal optimum számító programnál a
kilométerek száma lehet ez a szám. Minél kevesebb utat kell megtenni,
annál jobb az adott megoldás – azaz fordított arányosságról
beszélünk a hibaérték és az eredményesség tekintetében.
E mutató alapján fogunk sorrendet felállítani az
egyedek között és a kevésbé eredményes egyedeket egy elitlista, vagy
limitálási paraméter segítségével kivágjuk (eltávolítjuk) –
ezek elpusztulnak, míg a többi (megfelelően sorba rendezett listában
az lista elején található) egyed a populációban marad, miáltal
is a hibaérték állandóan közelíteni próbál majd az ideális
minimumhoz, amit egy megfelelően felépített rendszernél (vizuálisan)
logaritmikus csökkenéssel lehetne demonstrálni: egy jó (vagy jobb)
eredmény még jobb eredményeket szül és így egyre kisebb részterület
körül fog szóródni a kimenet (a szóródás mértéke egyre csökken –
az egészen (vagy a részben) optimális megoldásig).
