Genetikus algoritmus

Mi ez?

A természetes evolúciót játékként lehet modellezni, amelyben a jól játszó szervezet jutalma a genetikai anyagának utódai számára történő továbbadása és a folyamatos túlélés.^[2] A természetes evolúcióban az, hogy egy egyed mennyire jól teljesít, attól függ, hogy kivel dolgozik együtt és kivel versenyez, valamint a környezettől. A genetikai algoritmusok a természetes szelekció szimulációja egy optimalizálási probléma megoldási jelöltjeinek (kromoszómák, egyedek, élőlények vagy fenotípusok) populációján.

A jelölteket értékelik és keresztezik, hogy jó megoldásokat találjanak. Az ilyen megoldások sok időt vehetnek igénybe, és egy ember számára nem nyilvánvalóak. Egy evolúciós fázis véletlenszerűen generált lényekből álló populációval indul. Minden egyes generációban a populáció minden egyedének fitneszét értékelik. Néhányat véletlenszerűen kiválasztanak az aktuális populációból (fittségük alapján), és módosítják (újrakombinálják és esetleg véletlenszerűen mutálják), hogy új populációt alkossanak. A ciklus ezzel az új populációval megismétlődik. Az algoritmus vagy egy meghatározott számú generáció elteltével, vagy a populáció jó fittségi szintjének elérése után ér véget. Ha az algoritmus a generációk maximális számának elérése miatt fejeződik be, az nem feltétlenül jelenti azt, hogy jó fitneszszintet értünk el.

Ennek programozása számítógépen

Az álkód a következő:

1. Inicializálás: Nagyon gyakran ezek véletlenszerű értékeket kapnak.
2. Értékelés: A pontszám egy szám lesz, amely megadja, hogy az adott megoldás mennyire jól oldja meg a problémát.
3. A következő lépések addig futnak, amíg a megállási követelmény nem teljesül:
1. Kiválasztás: Válassza ki a megoldásokat/egyéneket a következő iterációhoz.
2. Rekombináció: Kombinálja a kiválasztott megoldásokat
3. Mutáció: Véletlenszerűen változtatja meg az újonnan létrehozott megoldásokat
4. Értékelés: Alkalmazza a fitneszfüggvényt, lásd a 2. lépést.
5. Ha a megállási követelmény nem teljesül, kezdje újra a kiválasztási lépéssel.

Példa

A fenti leírás elvont. Egy konkrét példa segít.

Alkalmazások

Általában

A genetikai algoritmusok jól oldanak meg olyan problémákat, mint a menetrendkészítés és az ütemezés. A mérnöki tudományokban is alkalmazzák őket. Gyakran használják globális optimalizálási problémák megoldására.

Általános szabályként a genetikai algoritmusok hasznosak lehetnek olyan problématerületeken, amelyek összetett fitnesz-tájképpel rendelkeznek, mivel a keverés célja, hogy a populációt eltávolítsa a lokális optimumoktól, amelyekben egy hagyományos hegymászó algoritmus megrekedhet. Az általánosan használt keresztezési operátorok nem képesek megváltoztatni semmilyen egységes populációt. A mutáció önmagában biztosíthatja a teljes genetikai algoritmus folyamatának ergodicitását (Markov-láncnak tekintve).

Példák a genetikus algoritmusok által megoldott problémákra: a napfény napkollektorokba történő elvezetésére tervezett tükrök, az űrben a rádiójelek vételére tervezett antennák, számítógépes figurák járási módszerei, aerodinamikai testek optimális tervezése összetett áramlási mezőkben.

Algoritmus-tervezési kézikönyvében Skiena azt tanácsolja, hogy a genetikai algoritmusokat ne alkalmazzuk semmilyen feladatra: "Elég természetellenes az alkalmazásokat olyan genetikai operátorok segítségével modellezni, mint a mutáció és a keresztezés a bitsorozatokon. Az álbiológia egy újabb komplexitási szintet ad a probléma és Ön közé. Másodszor, a genetikai algoritmusok nagyon sokáig tartanak a nem triviális problémákon. [...] Az evolúcióval való analógia - ahol a jelentős fejlődéshez több millió évre van szükség [sic] - nagyon is helyénvaló lehet. [...] Soha nem találkoztam olyan problémával, amelynek megoldására a genetikai algoritmusok tűntek volna számomra a megfelelő megoldásnak. Továbbá, soha nem láttam olyan számítási eredményeket, amelyekről genetikai algoritmusok alkalmazásával számoltak volna be, és amelyek kedvező benyomást tettek volna rám. Maradjon a szimulált lágyításnál a heurisztikus keresési voodoo szükségleteihez."

Társasjátékok

A társasjátékok nagyon fontos részét képezik a genetikai algoritmusok játékelméleti problémákra alkalmazott területének. A számítógépes intelligenciával és a játékokkal kapcsolatos korai munkák nagy része a klasszikus társasjátékokra, például a tic-tac-toe-ra irányult,^[3] sakk és dáma.^[4] A társasjátékokat ma már a legtöbb esetben a számítógép a legjobb embernél magasabb szinten tudja játszani, még vak kimerítő keresési technikákkal is. A gó ez alól a tendencia alól figyelemre méltó kivétel, és eddig ellenállt a gépi támadásoknak. A legjobb számítógépes Go játékosok ma már egy jó kezdő játékos szintjén játszanak.^[5][6] A Go stratégiája állítólag nagymértékben a mintafelismerésre támaszkodik, és nem csak a logikai elemzésre, mint a sakkban és más, bábutól függetlenebb játékokban. A jó minőségű megoldások megtalálásához szükséges hatalmas hatékony elágazási tényező erősen korlátozza a lépéssorozat keresésén belül használható előretekintést.

Számítógépes játékok

A genetikai algoritmus számítógépes játékokban használható mesterséges intelligencia létrehozására (a számítógép játszik Ön ellen). Ez reálisabb játékélményt tesz lehetővé; ha egy emberi játékos megtalálja a lépések olyan sorozatát, amely mindig sikerre vezet, még akkor is, ha különböző játékokban megismétlődik, akkor nem maradhat kihívás. Ezzel szemben, ha egy tanulási technika, például egy genetikus algoritmus a stratéga számára el tudja kerülni a múltbeli hibák ismétlődését, a játék játszhatósága nagyobb lesz.

A genetikai algoritmusokhoz a következő részekre van szükség:

• Módszer a kihívás ábrázolására a megoldás szempontjából (pl. katonák irányítása egy támadásban egy stratégiai játékban).
• Egy fitnesz- vagy értékelési függvény egy példány minőségének meghatározására (pl. az ellenfélnek egy ilyen támadás során okozott kár mérése).

A fitneszfüggvény elfogadja egy entitás mutált példányát, és méri annak minőségét. Ez a függvény a problématerülethez van igazítva. Sok esetben, különösen a kódoptimalizálással kapcsolatos esetekben a fitneszfüggvény egyszerűen egy rendszeridőzítési függvény lehet. A genetikai reprezentáció és a fitneszfüggvény meghatározása után a genetikai algoritmus a fent leírtak szerint kezdeti jelölteket instanciál, majd a mutációs, keresztezési, inverziós és szelekciós operátorok ismétlődő alkalmazásával (a problématartománynak megfelelően meghatározottak szerint) javít.

Korlátozások

A genetikai algoritmus használatának vannak korlátai az alternatív optimalizációs algoritmusokkal szemben:

• Az összetett problémák ismételt fitneszfüggvény-kiértékelése gyakran a mesterséges evolúciós algoritmusok legkorlátozóbb szegmense. Az összetett problémák optimális megoldásának megtalálása gyakran nagyon költséges fitneszfüggvény-kiértékeléseket igényel. A valós problémák, például a szerkezeti optimalizálási problémák esetében egyetlen függvény kiértékelése több órától akár több napig tartó teljes szimulációt is igényelhet. A tipikus optimalizálási módszerek nem tudnak megbirkózni az ilyen típusú problémákkal. Gyakran közelítést kell alkalmazni, mivel a pontos megoldás kiszámítása túl sok időt vesz igénybe. A genetikus algoritmusok néha különböző közelítő modelleket kombinálnak az összetett valós problémák megoldásához.
• A genetikai algoritmusok nem skálázódnak jól. Azaz, ahol a mutációnak kitett elemek száma nagy, ott gyakran exponenciálisan nő a keresési tér mérete. Ez rendkívül megnehezíti a technika alkalmazását olyan problémákra, mint például egy motor, egy ház vagy egy repülőgép tervezése. Ahhoz, hogy a genetikai algoritmusokat ilyen problémáknál használni lehessen, a lehető legegyszerűbb reprezentációra kell bontani őket. Emiatt látjuk, hogy az evolúciós algoritmusok motorok helyett ventilátorlapátok terveit, részletes építési tervek helyett épületformákat, teljes repülőgép-tervek helyett pedig szárnyprofilokat kódolnak. A komplexitás másik problémája az a kérdés, hogy hogyan védjük meg a jó megoldásokat reprezentáló evolúciós részeket a további romboló mutációtól, különösen akkor, ha a fitneszértékelésük megköveteli, hogy jól kombinálódjanak más részekkel.
• A "jobb" megoldás csak más megoldásokhoz képest létezik. Ennek eredményeképpen a megállási kritérium nem minden problémánál egyértelmű.
• Számos probléma esetén a genetikai algoritmusok hajlamosak arra, hogy a probléma globális optimuma helyett inkább a lokális optimumok vagy akár tetszőleges pontok felé konvergáljanak. Ez azt jelenti, hogy az algoritmus nem "tudja, hogyan" áldozza fel a rövid távú alkalmasságot a hosszabb távú alkalmasság érdekében. Ennek valószínűsége a fitneszfüggvény alakjától függ: bizonyos problémák esetében könnyű megtalálni a globális optimumot, más problémák esetében a függvénynek könnyebb lehet a lokális optimumokat megtalálni. Ez a probléma csökkenthető más fitneszfüggvény alkalmazásával, a mutációs ráta növelésével, vagy olyan szelekciós technikák alkalmazásával, amelyek változatos megoldások populációját tartják fenn. A sokféleség fenntartásának egyik gyakori technikája a "niche penalty" alkalmazása: a kellően hasonló egyedek (niche-sugár) bármely csoportjához büntetést adnak, amely csökkenti az adott csoport képviseletét a következő generációkban, lehetővé téve más (kevésbé hasonló) egyedek megtartását a populációban. Ez a trükk azonban nem biztos, hogy hatékony, a probléma tájképétől függően. Egy másik lehetséges technika az lenne, ha a populáció egy részét egyszerűen véletlenszerűen generált egyedekkel helyettesítenénk, amikor a populáció nagy része túlságosan hasonló egymáshoz. A sokféleség azért fontos a genetikai algoritmusokban (és a genetikai programozásban), mert egy homogén populáció keresztezése nem eredményez új megoldásokat. Az evolúciós stratégiákban és az evolúciós programozásban a sokféleség nem lényeges, mert nagyobb mértékben támaszkodnak a mutációra.
• A dinamikus adathalmazokon való működés nehéz, mivel a genomok már korán elkezdenek konvergálni olyan megoldások felé, amelyek a későbbi adatokra már nem feltétlenül érvényesek. Számos módszert javasoltak már ennek orvoslására azáltal, hogy valamilyen módon növelik a genetikai diverzitást és megakadályozzák a korai konvergenciát, vagy a mutáció valószínűségének növelésével, amikor a megoldás minősége csökken (úgynevezett kiváltott hipermutáció), vagy azzal, hogy időnként teljesen új, véletlenszerűen generált elemeket vezetnek be a génállományba (úgynevezett véletlen bevándorlók). Az evolúciós stratégiák és az evolúciós programozás ismét megvalósítható az úgynevezett "vesszőstratégiával", amelyben a szülők nem maradnak fenn, és az új szülők csak az utódok közül kerülnek kiválasztásra. Ez dinamikus problémák esetén hatékonyabb lehet.
• A genetikai algoritmusok nem tudnak hatékonyan megoldani olyan problémákat, amelyekben az egyetlen alkalmassági mérőszám egyetlen helyes/helytelen mérőszám (mint például a döntési problémák), mivel nincs mód a megoldáshoz való konvergálásra (nincs megmászandó hegy). Ezekben az esetekben a véletlenszerű keresés ugyanolyan gyorsan találhat megoldást, mint a GA. Ha azonban a helyzet lehetővé teszi, hogy a siker/hiányos kísérletet megismételjük, és (esetleg) különböző eredményeket kapunk, akkor a sikerek és a kudarcok aránya megfelelő fitneszmértéket biztosít.
• Bizonyos optimalizálási problémák és problémapéldák esetében más optimalizálási algoritmusok a konvergencia sebessége szempontjából hatékonyabbak lehetnek, mint a genetikai algoritmusok. Az alternatív és kiegészítő algoritmusok közé tartoznak az evolúciós stratégiák, az evolúciós programozás, a szimulált lágyítás, a Gauss-adaptáció, a hegymászás és a rajintelligencia (pl.: hangyatelep-optimalizálás, részecske-raj optimalizálás), valamint az egészértékű lineáris programozáson alapuló módszerek. A genetikai algoritmusok alkalmassága a probléma ismeretének mennyiségétől függ; a jól ismert problémákra gyakran jobb, speciálisabb megközelítések léteznek.

Történelem

1950-ben Alan Turing egy "tanuló gépet" javasolt, amely párhuzamosan működne az evolúció elveivel. Az evolúció számítógépes szimulációja már 1954-ben megkezdődött Nils Aall Barricelli munkájával, aki a New Jersey állambeli Princetonban működő Institute for Advanced Study-ban használta a számítógépet. Az 1954-es publikációját nem vették széles körben észre. 1957-től kezdődően Alex Fraser ausztrál kvantitatív genetikus egy sor publikációt tett közzé olyan szervezetek mesterséges szelekciójának szimulációjáról, amelyekben több lókusz szabályoz egy mérhető tulajdonságot. E kezdetekből kiindulva az evolúció biológusok általi számítógépes szimulációja az 1960-as évek elején vált egyre gyakoribbá, és a módszereket Fraser és Burnell (1970), valamint Crosby (1973) könyveiben írták le. Fraser szimulációi a modern genetikai algoritmusok minden lényeges elemét tartalmazták. Emellett Hans-Joachim Bremermann az 1960-as években publikált egy sor olyan tanulmányt, amely szintén egy rekombináción, mutáción és szelekción átesett, optimalizációs problémák megoldását végző populációt fogadott el. Bremermann kutatásai a modern genetikai algoritmusok elemeit is magukban foglalták. További említésre méltó korai úttörők közé tartozik Richard Friedberg, George Friedman és Michael Conrad. Számos korai tanulmányt Fogel (1998) közöl újra.

Bár Barricelli az 1963-ban bejelentett munkájában egy egyszerű játék képességének evolúcióját szimulálta, a mesterséges evolúció Ingo Rechenberg és Hans-Paul Schwefel 1960-as években és az 1970-es évek elején végzett munkája nyomán vált széles körben elismert optimalizálási módszerré - Rechenberg csoportja képes volt komplex mérnöki problémákat megoldani evolúciós stratégiák segítségével. Egy másik megközelítés Lawrence J. Fogel evolúciós programozási technikája volt, amelyet mesterséges intelligencia előállítására javasoltak. Az evolúciós programozás eredetileg véges állapotú gépeket használt a környezet előrejelzésére, és variációt és szelekciót alkalmazott az előrejelző logikák optimalizálására. A genetikai algoritmusok különösen John Holland munkássága révén váltak népszerűvé az 1970-es évek elején, különösen az Adaptation in Natural and Artificial Systems (1975) című könyve révén. Munkája a celluláris automatákkal kapcsolatos tanulmányokból indult ki, amelyeket Holland és tanítványai a Michigani Egyetemen végeztek. Holland bevezetett egy formalizált keretrendszert a következő generáció minőségének előrejelzésére, amely Holland séma-tételként ismert. A GA-kkal kapcsolatos kutatások nagyrészt elméleti jellegűek maradtak egészen az 1980-as évek közepéig, amikor a pennsylvaniai Pittsburghben megrendezték az Első Nemzetközi Genetikai Algoritmus Konferenciát.