Digitális evolúció

Az 1950-60-as években merült fel először az a gondolat, hogy a biológiai evolúció a mérnöki problémákban is felhasználható lehet optimalizációs eszközként. A mesterséges intelligencia kialakulásának kezdeti korszakában a természetes evolúció modellezésére irányuló próbálkozások vezettek el a korai, genetikus algoritmussal rokon stratégiák és módszerek, az evolúciós stratégiák, az evolúciós programozás, majd jóval később a genetikus programozás kialakulásához. A darwini evolúciós elmélet és a genetika alapjait magába építő szigorúan vett genetikus algoritmusok első változatát, az egyszerű genetikus algoritmusokat John Holland, a Michigani Egyetem professzora javasolta 1975-ben. Az azóta eltelt több mint 25-35 év alatt mind a szűkebb értelemben vett genetikus algoritmusok, mind pedig a tágabban értelmezett evolúciós módszerek komoly fejlődésen mentek keresztül, sokféle változatuk alakult ki, és egyre teljesebbé vált a matematikai megalapozásuk is.

A gépszerkesztés alternatívája a mesterséges intelligencia létrehozásában az egyik megközelítés, a biológiai evolúció folyamatának utánzása a számítógépben. A szimulált evolúció eltérő utat kínál a bonyolult hardver és szoftver tervezésére. Olyan utat, ami megkerüli a műszaki tervezés számos problémáját. A szimulált evolúció működését példázzuk egy számokat csökkenő sorrendbe rendező szoftverrel. A szokványos műszaki megközelítés az lenne, hogy egy rendező algoritmus valamelyikének alapján írunk egy programot; de most nézzük azt az esetet, hogy ehelyett hogyan „fejleszthetnénk ki” a szoftvert.

Az első lépés véletlenszerű programok „populációjának” a generálása. Ezt a populációt létrehozhatjuk álvéletlenszám-generátor használatával, amellyel megalkotjuk az utasítások véletlenszerű sorozatát. A folyamat felgyorsítására alkalmazhatjuk a csak a rendezés műveletére használható utasításokat, például az összehasonlító- és csereutasításokat. Az utasításoknak ezek a véletlenszerű sorozatai jelentik a programot. A véletlenszerű populáció mondjuk tízezer ilyen programot fog tartalmazni, melyek mindegyike néhány száz utasítás hosszúságú.

A következő lépésben megvizsgáljuk a populációt, hogy kikeressük közülük a legsikeresebb programokat. Ehhez minden egyes programot le kell futtatnunk, hogy lássuk, melyik rendezi helyesen a próbasorozatot. Minthogy a programok véletlenszerűek, valószínűleg egyik sem állja ki a próbát, de a puszta szerencse némelyiket közelebb viszi a helyes rendezéshez, mint a többieket. Az egyik program például véletlenül a sorozat végére helyezheti az alacsony számokat. Miután a programokat kipróbáljuk egy néhány számból álló sorozaton, minden programhoz egy hozzáillő pontszámot rendelhetünk. A következő lépés az olyan új populációk létrehozása, amelyek a magasra értékelt programok leszármazottai.

Ennek megvalósításához először is töröljük az átlagos pontszámnál kevesebbel rendelkező programokat, hogy csak a legalkalmasabb programok maradjanak életben. Az új populációt úgy hozzuk létre, hogy kisebb véletlenszerű variációkkal másolatokat készítünk a fennmaradó programokról. Ez az eljárás megfelel az aszexuális mutációs reprodukciónak. A másik lehetőség, hogy a következő generáció új programjait az életben maradt programok párosításával „tenyésztjük”. Ez a folyamat pedig a szexuális reprodukciónak felel meg. Ez oly módon vihető végbe, hogy a „szülőprogramok” mindegyikéből utasítássorozatokat kombinálunk a „gyermek” létrehozására. A szülők feltételezhetően azért maradtak fenn, mert hasznosítható utasítássorozatokat tartalmaztak, és így jó esély nyílik rá, hogy a gyermek örökölni fogja szüleitől a leghasznosabb részleteket.

A programok létrejött új generációját ismét ugyanannak az elemző és szelekciós eljárásnak vetjük alá, úgyhogy ismét csak a legalkalmasabb programok maradnak életben és szaporodnak. Egy párhuzamos számítógép néhány másodpercenként hoz létre újabb generációt, így a szelekciós és variációs eljárást sok-sok ezerszer is könnyedén megismételhetjük. A populációk átlagos alkalmassága minden generációval növekszik, azaz a programok egyre alkalmasabbak a rendezésre. Néhány ezer generáció múlva a programok tökéletesen fognak rendezni.

Hillis evolúciós elven kitenyésztett rendező algoritmusa amely 61 összehasonlítással rendez.
Az algoritmus 16 számot rendez növekvő sorba, gyorsabban mint az emberek által addig megalkotott leggyorsabb algoritmus.

Egy kísérletben alkalmazták a szimulált evolúciót, hogy az különleges rendezési feladatok megoldására kifejlesszen egy programot, majd leírták a folyamat működését. A kísérletben előnyben részesítették azokat a programokat, amelyek gyorsan rendezték a próbasorozatokat, így a gyorsabb programoknak nagyobb esélyük volt a fennmaradásra. Ezzel az eljárással igen gyors rendezőprogramok jöttek létre. Az evolúciós folyamatban létrejött programok valamivel gyorsabbnak bizonyultak, mint azok, amelyek algoritmusok alapján íródtak. Gyorsabban rendezték a számokat, mint bármely olyan program, amelyet programozók írtak volna egy ismert algoritmus alapján. Az evolúciós folyamat során létrejött programok esetében az az egyik legérdekesebb mozzanat, hogy nem érthető, hogyan is működnek, hiába vizsgálták meg utasítássorozataikat a leggondosabban. Könnyen lehet, hogy ezek a programok nem megérthetőek, más szóval, nem bonthatjuk a program működését a megérthető részek hierarchiájára.

Matematikai teszteket használtak annak bizonyítására, hogy a kifejlesztett rendezőprogramok tökéletes rendezők. Jobban bízhatunk az őket létrehozó folyamatban, mint a matematikai tesztekben. Mégpedig azért, mert az evolúciós folyamat során kifejlődött rendezőprogramok olyan programok hosszú sorának a leszármazottai, amelyek fennmaradása kizárólag rendezési képességüktől függött.

Az a tény, hogy az evolúciós folyamat során létrejött programok nem mindig megérthetőek, egyes embereket aggodalommal tölt el az alkalmazásuk tekintetében, azonban ez az aggodalom téves feltételezéseken alapul. Ezeknek a feltételezéseknek az egyike, hogy a szigorúan műszaki alapon létrehozott rendszerek mindig jól megérthetőek, ám ez csak a viszonylag egyszerű rendszerek esetében igaz. Például manapság egyetlen személy sem láthat át teljes mértékben egy operációs rendszert. A téves feltételezés az is, hogy a nem megmagyarázható rendszerek kevésbé megbízhatóak. Ha választani lehetne, hogy egy műszakilag tervezett számítógépprogram, illetve egy emberi pilóta által irányított repülőgépen utazzon-e, melyiket választaná? Részemről egészen biztosan az embert választanám, bár fogalmam sincs az emberi pilóta működéséről. Szívesebben vetem a bizalmam abba a folyamatba, amely a pilótát létrehozta. Akárcsak a rendezőprogramok esetében, tudom, hogy a pilóta az életképesnek bizonyult egyedek hosszú sorának a leszármazottja. Ha a repülőgép biztonsága a számok helyes rendezésétől függene, akkor inkább bíznám magam egy evolúciósan kifejlesztett rendezőprogramra, mint egy olyanra, amit egy csapat programozó írt.