A TERMÉSZET A KÓD

írta Daniel Shiffman

Üdvözöljük
Köszönetnyilvánítás
Elhivatottság
Előszó
Bevezetés
1. Vektorok
2. Erők
3. Oszcilláció
4. Részecske rendszerek
5. Fizikai könyvtárak
6. Autonóm ügynökök
7. Cellular Automata
8. Fraktálok
9. A kód evolúciója
10. Ideghálózatok
További irodalom
Index

Daniel Shiffman

9. fejezet A kód alakulása

"Az a tény, hogy az élet szinte semmiből alakult ki, körülbelül 10 milliárd évvel azután, hogy az univerzum szó szerint semmiből alakult ki, annyira megdöbbentő tény, hogy mérges lennék, ha szavakkal próbálkoznék igazsággal." - Richard Dawkins

Vegyünk egy pillanatot arra, hogy visszagondoljunk egy egyszerűbb időszakra, amikor megírta első feldolgozási vázlatait, és az élet ingyenes és könnyű volt. Mi a programozás egyik alapfogalma, amelyet valószínűleg az első vázlatokban használt, és továbbra is újra és újra használ? Változók. A változók lehetővé teszik az adatok mentését és újrafelhasználását egy program futása közben. Ez természetesen nem újdonság számunkra. Valójában messze túlhaladtunk egy csak egy vagy két változóval rendelkező vázlaton, és tovább léptünk a bonyolultabb adatstruktúrákhoz - olyan változókhoz, amelyek egyedi típusokból (objektumokból) készülnek, amelyek mind az adatokat, mind a funkciókat tartalmazzák. Megalkottuk a saját mozgatóink és részecskéink, járműveink, sejtjeink és fáink világát.

A könyv egyes példáiban inicializálni kell ezen objektumok változóit. Talán egy csomó részecskét készített véletlenszerű színekkel és méretekkel, vagy egy listát a járművekről, amelyek mind ugyanabban az x, y helyen kezdődnek a képernyőn. De ahelyett, hogy „intelligens tervezőként” járnánk el és véletlenszerűség vagy átgondolt megfontolás alapján hozzárendelnénk tárgyaink tulajdonságait, hagyhatjuk, hogy a természetben megtalálható folyamat - az evolúció - helyettünk döntsön.

Gondolhatunk-e egy objektum változóira, mint annak DNS-ére? Készíthetnek-e tárgyak más tárgyakat, és átadhatják-e DNS-jüket egy új generációnak? Fejlődhet-e a szimulációnk?

A válasz ezekre a kérdésekre igen. Végül is nem lennénk képesek szembesülni magunkkal a tükörben, mint a kódolók természete, anélkül, hogy a természetben megtalálható egyik legerősebb algoritmikus folyamat szimulációjával foglalkoznánk. Ez a fejezet a biológiai evolúció mögött meghúzódó elvek vizsgálatát és annak megtalálását kínálja, hogy miként alkalmazhatók ezek az elvek a kódban.

9.1 Genetikai algoritmusok: A tényleges események ihlették

Fontos számunkra a fejezet céljainak tisztázása. Nem fogunk elmélyülni a genetika és az evolúció tudományában, ahogy az a való világban történik. Nem fogunk Punnett négyzeteket készíteni (sajnálom, hogy csalódást okozzak), és nem kerül sor a nukleotidok, a fehérjeszintézis, az RNS és más, az evolúció tényleges biológiai folyamataival kapcsolatos témák megvitatására. Ehelyett megvizsgáljuk a darwini evolúciós elmélet mögött meghúzódó alapelveket, és kidolgozzuk az ezen elvek által inspirált algoritmusok sorozatát. Nem érdekel annyira az evolúció pontos szimulációja; inkább az evolúciós stratégiák szoftverekben történő alkalmazásának módszerei érdekelnek.

Ez nem azt jelenti, hogy egy nagyobb tudományos mélységű projektnek nem lenne értéke, és arra biztatom az e témában különös érdeklődéssel rendelkező olvasókat, hogy vizsgálják meg a további evolúciós jellemzőkkel ellátott példák bővítésének lehetőségeit. Mindazonáltal a dolgok kezelhetősége érdekében ragaszkodunk az alapokhoz, amelyek bonyolultak és izgalmasak lesznek.

A „genetikai algoritmus” kifejezés egy specifikus algoritmust jelent, amelyet sajátos módon hajtanak végre bizonyos típusú problémák megoldására. Míg maga a formális genetikai algoritmus szolgál majd az ebben a fejezetben létrehozott példák alapjaként, nem kell aggódnunk az algoritmus tökéletes pontosságú megvalósítása miatt, tekintettel arra, hogy kódunkban az evolúciós elméletek kreatív felhasználását keressük. Ez a fejezet a következő három részre oszlik (az elsőre fordított idő nagy részével).

Hagyományos genetikai algoritmus. Kezdjük a hagyományos számítástechnikai genetikai algoritmussal. Ezt az algoritmust olyan problémák megoldására fejlesztették ki, amelyekben a megoldási tér olyan hatalmas, hogy egy „durva erő” algoritmus egyszerűen túl sokáig tart. Itt egy példa: Számra gondolok. Egy és egymilliárd közötti szám. Mennyi időbe telik, amíg kitalálja? A probléma „durva erővel” történő megoldása minden lehetséges megoldás ellenőrzésének folyamatát jelenti. Ez egy? Kettő? Három? Négy? És így és így tovább. Bár a szerencse itt játszik szerepet, nyers erővel gyakran türelmesen várakozhatunk éveken keresztül, miközben Ön egymilliárdig számít. Mi lenne azonban, ha meg tudnám mondani, hogy jó vagy rossz válasz volt-e? Meleg vagy hideg? Nagyon meleg? Forró? Szuper, nagyon hideg? Ha meg tudná értékelni, hogy egy találgatás mennyire alkalmas, akkor más számokat is választhat, amelyek közelebb vannak ehhez a találgatáshoz, és gyorsabban megkapja a választ. A válaszod fejlődhet.

Interaktív kiválasztás. Miután létrehoztuk a hagyományos informatikai algoritmust, megvizsgáljuk a genetikai algoritmusok vizuális művészetek egyéb alkalmazási lehetőségeit. Az interaktív szelekció valaminek (gyakran számítógép által létrehozott képnek) a felhasználói interakció révén történő fejlesztésének folyamatára utal. Tegyük fel, hogy belép egy múzeumi galériába, és tíz festményt lát. Interaktív kiválasztással kiválaszthatja kedvenceit, és lehetővé teszi egy algoritmikus folyamat során, hogy új festményeket hozzon létre (vagy "fejlesszen") az Ön preferenciái alapján.

Ökoszisztéma-szimuláció. A hagyományos informatikai genetikai algoritmus és az interaktív szelekciós technika az, amit valószínűleg megtalál, ha online keres, vagy a mesterséges intelligenciáról szóló tankönyvet olvas. De mint hamarosan látni fogjuk, nem igazán szimulálják az evolúció folyamatát, ahogy az a való világban történik. Ebben a fejezetben olyan technikákat is szeretnék feltárni, amelyek az ál-élőlények ökoszisztémájában az evolúció folyamatának szimulálására szolgálnak. Hogyan találkozhatnak egymással a képernyőn mozgó tárgyaink, párosodhatnak és továbbadhatják génjeiket egy új generációnak? Ez közvetlenül vonatkozna az egyes fejezetek végén felvázolt ökoszisztéma-projektekre.

9.2 Miért érdemes genetikai algoritmusokat használni?

Míg az evolúciós folyamatok számítógépes szimulációi az 1950-es évekig nyúlnak vissza, manapság genetikai algoritmusoknak (más néven „GA” -nak) gondolunk sokat John Holland, a Michigani Egyetem professzora fejlesztette ki, akinek Adaptation in Natural and A mesterséges rendszerek úttörő szerepet játszottak a GA kutatásban. Ma több genetikai algoritmus egy szélesebb kutatási terület része, amelyet gyakran "evolúciós számítástechnikának" neveznek.

A hagyományos genetikai algoritmus szemléltetése érdekében majmokkal kezdjük. Nem, nem evolúciós őseink. Kezdjük néhány kitalált majommal, akik a billentyűzeten csapkodnak, azzal a céllal, hogy gépeljék ki Shakespeare teljes műveit.

A „végtelen majomtételt” a következőképpen fogalmazzák meg: Egy majom, amely véletlenszerűen nyomja meg a kulcsokat az írógépen, végül Shakespeare teljes műveit írja be (végtelen ideig). Ennek az elméletnek az a problémája, hogy annak a valószínűsége, hogy az említett majom valóban beírja Shakespeare-t, olyan alacsony, hogy még ha az a majom is az Ősrobbanásnál kezdődött, hihetetlen valószínűtlen, hogy ezen a ponton még Hamletet is megkapnánk.

Vegyünk egy George nevű majmot. George csak huszonhét karaktert tartalmazó, csökkentett írógéppel gépel: huszonhat betű és egy szóköz. Tehát annak a valószínűsége, hogy George megüt egy adott kulcsot, minden huszonhét.

Vegyük fontolóra a „hogy vagy nem ez a kérdés” kifejezést (leegyszerűsítjük az eredeti „Legyen, vagy ne legyen: ez a kérdés” helyett). A kifejezés 39 karakter hosszú. Ha George gépelni kezd, akkor az esélye, hogy az első karaktert jobbra kapja, 27-ből 1-re esik. Mivel valószínűsége, hogy a második karaktert is megkapja, 1-ből 27-re esik, 1-nél 27-ből * 27 esélye van az első leszállására két karakter helyes sorrendben - ami közvetlenül a Bevezetésben az "esemény valószínűségéről" folytatott tárgyalásunkból következik. Ezért annak valószínűsége, hogy George beírja a teljes kifejezést:

(1/27) szorozva önmagával 39-szer, azaz (1/27) 39

ami 1-nek felel meg a 66,555,937,033,867,822,607,895,549,241,096,482,953,017,615,834,735,226,163 esélyével a helyrehozáshoz!

Mondanom sem kell, hogy még ennek az egyetlen kifejezésnek a megütése, nem is beszélve egy egész darabról, nagyon valószínűtlen. Még akkor is, ha George számítógépes szimuláció, és másodpercenként egymillió véletlenszerű kifejezést tud beírni, ahhoz, hogy George 99% -os valószínűséggel végső soron helyrehozza a helyzetét, 9 719 096 182 010 563 073 1225 591 133 903 305 625 605 017 évet kellene begépelnie. (Ne feledje, hogy a világegyetem életkorát csupán 13 750 000 000 évre becsülik.)

Ezeknek a kimutathatatlanul nagy számoknak nem az a célja, hogy fejfájást okozzon, hanem annak demonstrálása, hogy a nyers erő algoritmusa (minden lehetséges véletlenszerű mondat beírása) nem ésszerű stratégia a véletlenszerű eléréshez a „lenni vagy nem lenni. kérdés". Adjon meg genetikai algoritmusokat, amelyek megmutatják, hogy még mindig véletlenszerű kifejezésekkel indulhatunk, és a szimulált evolúció révén megtalálhatjuk a megoldást.

Most érdemes megjegyezni, hogy ez a probléma (érje el a „lenni vagy nem lenni az a kérdés” kifejezést) nevetséges. Mivel tudjuk a választ, csak be kell írnunk. Itt van egy feldolgozási vázlat, amely megoldja a problémát.

Mindazonáltal a lényeg itt az, hogy egy probléma megoldása ismert válasz segítségével lehetővé teszi számunkra, hogy könnyen teszteljük a kódunkat. Miután sikeresen megoldottuk a problémát, magabiztosabbnak érezhetjük magunkat abban, hogy genetikai algoritmusokat használunk néhány tényleges hasznos feladat elvégzéséhez: ismeretlen válaszokkal kapcsolatos problémák megoldásához. Tehát ez az első példa nem szolgál valódi céllal, csak a genetikai algoritmusok működésének bemutatásán. Ha teszteljük a GA eredményeket az ismert válasz alapján, és azt kapjuk, hogy „legyünk vagy ne legyünk”, akkor sikerült megírnunk genetikai algoritmusunkat.

9.1. Gyakorlat

Hozzon létre egy vázlatot, amely véletlenszerű karakterláncokat generál. Tudnunk kell, hogyan kell ezt megtenni a hamarosan követendő genetikai algoritmus-példa megvalósításához. Mennyi időbe telik, amíg a Processing véletlenszerűen generálja a „cat” karakterláncot? Hogyan lehet ezt adaptálni egy véletlenszerű terv előállításához a Processing alakrajzoló funkcióinak felhasználásával?

9.3 Darwini természetes szelekció

Mielőtt elkezdenénk járni a genetikai algoritmuson, szánjunk egy percet arra, hogy leírjuk a darwini evolúció három alapelvét, amelyekre a szimulációnk végrehajtása során szükség lesz. Ahhoz, hogy a természetes szelekció a természetben is előforduljon, mindhárom elemnek jelen kell lennie.

Átöröklés. Olyan folyamatnak kell lennie, amelynek során a gyerekek megkapják szüleik tulajdonságait. Ha a lények elég sokáig élnek ahhoz, hogy szaporodjanak, akkor vonásaikat a lények következő generációja továbbadja gyermekeiknek.

Variáció. A populációban különféle jellemzőknek vagy eszközöknek kell lenniük, vagy a variáció bevezetésének eszközével. Tegyük fel például, hogy van egy olyan bogárpopuláció, amelyben az összes bogár pontosan egyforma: azonos színű, azonos méretű, azonos szárnyfesztávolságú, minden ugyanaz. A lakosságban mindenféle változatosság nélkül a gyerekek mindig azonosak lesznek a szülőkkel és egymással. A tulajdonságok új kombinációi soha nem fordulhatnak elő, és semmi sem alakulhat ki.

Kiválasztás. Léteznie kell egy olyan mechanizmusnak, amely révén a populáció egyes tagjainak lehetőségük van szülőknek lenni és genetikai információikat átadni, mások pedig nem. Ezt általában „a legjobbak túlélésének” nevezik. Tegyük fel például, hogy a gazellák lakosságát minden nap oroszlánok üldözik. A gyorsabb gazellák nagyobb eséllyel kerülik el az oroszlánokat, ezért nagyobb valószínűséggel élnek tovább, és esélyük van arra, hogy szaporodjanak és továbbadják génjeiket gyermekeiknek. A fittest kifejezés azonban kissé félrevezető lehet. Általában úgy gondolunk rá, hogy nagyobbat, gyorsabbat vagy erősebbet jelent. Bár ez egyes esetekben előfordulhat, a természetes szelekció azon az elven működik, hogy egyes tulajdonságok jobban alkalmazkodnak a lény környezetéhez, és ezért nagyobb a túlélés és a szaporodás valószínűsége. Semmi köze ahhoz, hogy egy adott lény „jobb” (elvégre ez egy szubjektív kifejezés) vagy „fizikailag alkalmasabb”. Például tipizáló majmaink esetében a „fittebb” majom az, amelyik a „lenni vagy nem lenni” -hez közelebbi kifejezést írt be.

Ezután át szeretném járni a genetikai algoritmus elbeszélését. Ezt a gépelési majom kontextusában fogjuk megtenni. Maga az algoritmus két részre oszlik: az inicializálás feltételrendszere (azaz a Processing beállítása ()) és a lépések, amelyeket újra és újra ismételnek (azaz a Processing sorsolása ()), amíg a helyes válaszra nem jutunk.

9.4 A genetikai algoritmus, I. rész: Népesség létrehozása

A tipizáló majom példával összefüggésben létrehozzuk a kifejezések sokaságát. (Ne feledje, hogy a „kifejezés” kifejezést meglehetősen lazán használjuk, egy karakterláncot jelent.) Ez felveti a kérdést: Hogyan hozzuk létre ezt a sokaságot? Itt van a darwini elv variáció vonatkozik. Tegyük fel, hogy az egyszerűség kedvéért megpróbáljuk továbbfejleszteni a „macska” kifejezést, és hogy három mondatból állunk.

Persze, a fenti három mondatban sokféle változatosság van, de próbáld meg a karaktereket mindenféleképpen keverni, és soha nem fogsz macskát kapni. Itt nincs elég változatosság az optimális megoldás kialakításához. Ha azonban több ezer, véletlenszerűen generált mondatnyi populációnk lenne, valószínű, hogy a populáció legalább egy tagjának első karaktere lesz egy c, másodiknak az a, a másodiknak pedig egy a. Nagy populáció nagy valószínűséggel elegendő változatosságot biztosít számunkra a kívánt kifejezés előállításához (és az algoritmus 2. részében lesz még egy lehetőségünk még nagyobb variáció bevezetésére, ha eleve nincs elég). Tehát részletesebben leírhatjuk az 1. lépés leírását, és azt mondhatjuk:

Hozzon létre véletlenszerűen generált elemek sokaságát.

Ez újabb fontos kérdést vet fel. Mi az az elem maga? A fejezet példáinak áttekintése során többféle forgatókönyvet fogunk látni; képpopulációnk vagy járműpopulációnk lehet à la 6. fejezet. A kulcs és az a rész, amely ebben a fejezetben új számunkra az, hogy a populáció minden tagjának van virtuális „DNS” -je, tulajdonságok halmaza (nevezhetjük őket "géneknek"), amelyek leírják, hogy egy adott elem hogyan néz ki vagy hogyan viselkedik. Például a gépelő majom esetében a DNS egyszerűen karakterlánc.

A genetika területén fontos különbség van a genotípus és a fenotípus fogalmak között. A tényleges genetikai kód - esetünkben maga a digitális információ - egy elem genotípus. Ez adódik nemzedékről nemzedékre. A fenotípus, azonban annak az adatnak a kifejezése. Ez a megkülönböztetés kulcsfontosságú abban, hogy miként fogja használni a genetikai algoritmusokat saját munkájában. Melyek a tárgyak a világotokban? Hogyan tervezed meg az objektumok genotípusát (az egyes objektumok tulajdonságainak tárolására szolgáló adatstruktúrát), valamint a fenotípust (mit használsz ezeknek a változóknak a kifejezésére?) Ezt folyamatosan a grafikus programozás során végezzük. A legegyszerűbb példa valószínűleg a szín.

Mint láthatjuk, a genotípus a digitális információ. Minden szín egy változó, amely egy egész számot tárol, és úgy döntünk, hogy ezt az egészet színként fejezzük ki. De az, hogy miként választjuk az adatok kifejezését, önkényes. Más megközelítésben használhattuk volna az egész számot a vonal hosszának, az erő súlyának stb. Leírására.

A majom-tipizálási példánkban az a szép, hogy nincs különbség a genotípus és a fenotípus között. Maga a DNS adat karakterlánc, és az adatok kifejezése éppen ez a karakterlánc.

Végül befejezhetjük ennek az első lépésnek a megvitatását, és részletesebben leírhatjuk annak leírását, mondván:

Hozzon létre N elem populációját, mindegyik véletlenszerűen generált DNS-sel.

9.5 A genetikai algoritmus, II. Rész: Kiválasztás

Itt alkalmazzuk a darwini szelekció elvét. Ki kell értékelnünk a népességet, és meg kell határoznunk, hogy mely tagok alkalmasak arra, hogy a következő generáció szülőként válasszanak. A kiválasztás folyamata két lépésre osztható.

1) Értékelje az erőnlétet.

A genetikai algoritmusunk megfelelő működéséhez meg kell terveznünk az úgynevezett a-t fitnesz funkció. A függvény egy numerikus pontszámot fog készíteni a populáció adott tagjának alkalmasságának leírására. A valós világ természetesen egyáltalán nem így működik. A lények nem kapnak pontszámot; egyszerűen túlélik vagy sem. De a hagyományos genetikai algoritmus esetében, ahol egy probléma optimális megoldását próbáljuk kialakítani, képesnek kell lenniünk az adott lehetséges megoldás numerikus értékelésére.

Vizsgáljuk meg jelenlegi példánkat, a gépelési majmot. Ismét egyszerűsítsük a forgatókönyvet, és mondjuk, hogy megpróbáljuk kifejleszteni a „macska” szót. A lakosságnak három tagja van: kunyhó, autó és doboz. Az autó nyilvánvalóan a legalkalmasabb, tekintve, hogy két helyes karaktere van, a kunyhónak csak egy, a doboznak pedig nulla. És itt van a fitnesz funkciónk: