Az evolúció számítógépes tudománya: Bevezetés a genetikai algoritmusokba

Fotó: Hal Gatewood az Unsplash-en

Számítógépes tudósként érdekli az evolúció és a biológiai folyamatok, a genetikai algoritmusok témája, és tágabb értelemben az evolúciós számítás az, ami számomra egy édességbolt egy ötévesnek: Heaven. Az a puszta lehetőség, hogy kettő érdekemet ilyen zökkenőmentesen egyesíthetem, rendkívül izgalmas volt, és helytelen lenne, ha ezeket az ismereteket és izgalmakat magamnak tartanám.

Tehát annak érdekében, hogy kipróbáljam néhány eddigi tanulmányomat, és megosszam az eredményeimet a világ többi részével, úgy döntöttem, hogy sorozatot készítek erről a témáról.

Ebben a bejegyzésben röviden bemutatom a genetikai algoritmusokat, és elmagyarázom, hogy azok miként utánozzák ugyanazokat a természetes folyamatokat, amelyek a Földön több milliárd évig zajlottak.

Élet a földön

Az elmúlt 3,5 milliárd év során az anya természet, az apai idő, az evolúció és a természetes szelekció együttműködtek együtt, hogy előállítsák az élet minden speciális formáját, amelyeket ma a földön látunk: mint például a húsevő Venus Flytrap növény; az óceánban élő atlanti repülõ halak; echolokációt használó denevérek; hosszú nyakú zsiráfok; szupergyors gepárd, táncoló mézelő méhek; és természetesen, a tiéd, az utcai intelligens Homo sapiens.

A Venus Flytrap húsevő növény, amely elsősorban rovarokra és pókokra táplálkozik.Egyes denevérek echolokációt használnak a navigáláshoz és a ragadozások vadászatához, és a közhiedelemmel ellentétben a denevérek valójában nem vakok; A Repülő Róka néven ismert denevéreknek jobb látása van, mint az embereknek.A repülő halak nem repülhetnek ugyanúgy, mint a madarak, ezek a halak azonban erőteljes, önjáró ugrásokat hajthatnak végre a vízből, ahol hosszú szárnyaszerű uszonyuk lehetővé teszi számottevõ távolságok elcsúszását a víz felszínén.

Mondanom sem kell, hogy a földi élet az egyik, ha nem a legsikeresebb kísérlet, amelyet valaha is végeztünk univerzumunkban; és e kísérlet lenyűgöző eredményei alapján egyértelmű, hogy az evolúció egyértelműen valamire vonatkozik.

Az utóbbi időben mi emberek - mint a folyamat sok végtermékeinek egyike - rájöttünk, hogy ki is használhatjuk ezt a leleményes megközelítést a progresszív problémamegoldásban, és az 1950-es évek óta a számítógépes tudós, a genetikusok, a matematikusok és a biológusok megpróbálták utánozni ezeket a biológiai folyamatokat számítógépes szimulációk végrehajtásával. A nehéz és nem triviális problémák optimális megoldásának hatékony előállítása céljából.

A vak órák

Az egyik első olyan könyv, amellyel találkoztam, felkeltette érdeklődését az evolúciós biológia iránt, a The Blind Watchmaker, készítette Richard Dawkins. Ebben a könyvben Richard Dawkins elmagyarázza, hogy az összetett mechanizmusok, például az echolocation (egy folyamat, amelyet a denevérek a navigációhoz, vadászathoz és takarmányozáshoz használnak, bio-szonár néven is ismertek), összetett szerkezetek, mint például a pókhálók (amelyeket a pókok használnak áldozataik vonzására és elkapására), és az olyan összetett hangszerek, mint az emberi szem (az a két gömb alakú tárgy, amelyet jelenleg a cikk elolvasásához használnak) egyszerűen több ezer, ha nem több millió éves evolúció és adaptáció eredménye.

Az emberi szem fokozatos fejlődése. Ami az egyszerű fényérzékeny sejtekből indult ki, összetett eszközgé alakult, amelyet gyakran teljesen magától értetődőnek tekintünk. Az első állatok, amelyek bármi hasonlóra emlékeztettek, körülbelül 550 millió évvel ezelőtt éltek. És az egyik tudós számításai szerint csak 364 000 évbe telik, amíg a kameraszerű szem fényérzékeny tapaszból fejlődik ki.

Annak ellenére, hogy ezek a természeti csodák azt a benyomást keltik, hogy a célból építették őket (azaz egy tudatos „alkotó”), valójában csak a próbálkozás és a hiba iterációinak iterációinak eredményei, amelyek a - a szelekciós nyomás megváltozása (vagyis az éghajlat, az élőhely vagy a ragadozók vagy ragadozók viselkedésének és képességeinek megváltozása). Tehát, bár úgy néznek ki és viselkedhetnek, mint a pontos, előre gondolkodó mérnökök eredménye, valójában egy teljesen vak folyamat eredménye, egy olyan folyamat, amely előre nem tudja, mi lenne a tökéletes „megoldás”.

Mik a genetikai algoritmusok és miért van szükségük rájuk?

A genetikai algoritmusok az alapvető biológiai folyamatokon alapuló, az optimalizálás és a keresés problémáinak kiváló minőségű megoldásait generáló technika. Ezeket az algoritmusokat olyan helyzetekben használják, ahol a lehetséges megoldási tartomány nagyon nagy, és ahol a problémamegoldás alapvető megközelítései, mint például a kimerítő keresés / brutális erő, túl sok időt és energiát igényelnek.

Az utazó eladó probléma a következő kérdést teszi fel: „A városok listája és az egyes várospárok közötti távolságok alapján mi a legrövidebb út, amely meglátogatja az egyes városokat és visszatér az eredeti városba?” Ez egy NP-nehéz probléma a kombinatorikus optimalizálás.

A genetikai algoritmusok segítségével kiváló minőségű megoldásokat kínálhatunk erre a problémára, sokkal alacsonyabb költségek mellett, mint az primitívebb problémamegoldó technikák, mint például a kimerítő keresés, amely megköveteli, hogy minden lehetséges megoldást átmutasson.

Hogyan működnek a genetikai algoritmusok?

Egy algoritmus úgy működik, hogy több lépésben iterál, egészen addig, amíg el nem éri az előre meghatározott végpontot. A genetikai algoritmus minden egyes ismétlése a lehetséges megoldások új generációját eredményezi, amelyeknek elméletileg javulást kell mutatniuk az előző generációhoz képest.

A lépések a következők:

1. Hozzon létre egy N lehetséges megoldás kezdeti populációját (az ősi leves)

Az algoritmus első lépése egy olyan kezdeti megoldáscsoport létrehozása, amely a 0. generációban alapoldatként szolgál. Ebben a kezdeti populációban minden egyes megoldás tartalmaz egy kromoszómakészletet, amely egy géngyűjteményből áll, ahol minden gén a probléma egyik lehetséges változójához van hozzárendelve. Fontos, hogy a kezdeti populációban a megoldásokat véletlenszerűen hozzárendelt génekkel hozzák létre, hogy magas szintű genetikai variációt kapjunk.

2. Helyezze a populáció megoldásait fitnesz alapján (a legmegfelelőbb túlélése, 1. rész).

Ebben a lépésben az algoritmusnak képesnek kell lennie annak meghatározására, hogy mi teszi az egyik megoldást jobban „illeszkedőnek”, mint egy másik megoldást. Ezt a fitnesz funkció határozza meg. A fitnesz funkció célja a megoldások genetikai életképességének felmérése a populáción belül, a lista elejére helyezve azokat, akiknek a legelőnyösebb, legkedvezőbb és kiemelkedő genetikai tulajdonságai vannak.

Az utazó eladó probléma esetén a fitnesz funkció a megoldás által megtett teljes távolság kiszámítása lehet. Ahol egy rövidebb távolság megegyezik a magasabb fitnesszel.

3. Vegye ki a gyengébb oldatokat (a legmegfelelőbb túlélése, 2. rész)

Ebben a lépésben az algoritmus eltávolítja a kevésbé megfelelő megoldásokat a populációból. A „legmegfelelőbb” nem feltétlenül jelenti a legerősebbet, a leggyorsabbat vagy a legerősebbet, amint azt az emberek általában feltételezik. A legeredményesebb túlélése egyszerűen azt jelenti, hogy minél jobban felszerelt szervezet él a környezetében, annál valószínűbb, hogy elég hosszú ideig él, hogy géneit reprodukálja és a következő generációra terjessze.

A 3. és 4. lépést együttesen szelekciónak nevezzük.

4. Az erősebb megoldások tenyésztése (a legmegfelelőbb túlélése, 3. rész)

A fennmaradó oldatokat ezután párosítják egymással az utódok párosítása és szaporítása céljából. E folyamat során, a legalapvetőbb formájában, minden szülő génjeinek egy% -át (a természetben ez egy 50/50 felosztás) ad hozzá minden utódhoz, ahol P1 (G)% + P2 (G)% = 100 %. Crossover néven ismert annak meghatározása, hogy melyik szülői gént öröklik-e az utódok.

5. Mutálja az utódok géneit (mutáció)

Az utódok az „anya” gének százalékát és az „apák” gének százalékát tartalmazzák, és alkalmanként ezeknek egy vagy több génnek „mutációja” lesz. A mutáció lényegében genetikai rendellenesség, másolási hiba, mely miatt az utódok egy vagy több génje különbözik a szüleitől örökölt génektől. A genetikai algoritmusokban egyes esetekben a mutáció növeli az utódok fitneszét, más esetekben csökkenti azt.

Fontos megjegyezni, hogy nem szükséges mutációt végezni minden utóddal, a kívánt mutációs gyakoriság is lehet az algoritmus paramétere.

A genetikai algoritmusokban a szelekciót, a kereszteződést és a mutációt genetikai operátoroknak nevezik.

6. Felmondás

A 2–5. Lépést egy előre meghatározott végpontig megismételjük. Ez a végpont lehet a következők egyikének:

  1. Elérte a maximális idő / erőforrás-elosztást.
  2. Rögzített generációk száma telt el.
  3. Az uralkodó megoldás alkalmasságát egyetlen jövő generáció sem haladhatja meg.

A megoldások konvergenciája

1. Globális optimális

Ideális esetben a legmegfelelőbb megoldás a lehető legmagasabb fitneszértékkel rendelkezik, vagyis ez lesz az optimális megoldás, azaz nincs szükség az algoritmus folytatására és további generációk előállítására.

2. Helyi optimális

Bizonyos esetekben, ha az algoritmus paraméterei nem ésszerűek, a populáció hajlamos egy korai konvergenciára egy kevésbé optimális megoldás felé, amely nem az általunk követett globális optimum, hanem egy helyi. Itt lehet az algoritmus folytatása és további generációk előállítása hiábavaló.

Globális optimális és helyi optimális

Mi történne, ha nem lenne mutáció?

Első pillantásra a mutációk a folyamat szükségtelen, irreleváns részének tűnhetnek. De a véletlenszerűség ezen alapvető aspektusa nélkül a természetes szelekcióval történő evolúció teljesen a kezdeti populáció által meghatározott genetikai változatra korlátozódna, és utána nem kerülne új vonások bevezetése a populációba. Ez súlyosan akadályozná a természet problémamegoldó képességeit, és a földi élet nem lenne képes alkalmazkodni a környezetéhez, legalábbis fizikailag nem.

Ha ez történt a genetikai algoritmusunkban, akkor a szimuláció egy pontján a lakosság jövő generációi nem tudnák feltárni a megoldási tér egy részét, amelyet elődeik nem fedeztek fel. A mutációk nélküli szimuláció súlyosan korlátozná a populáción belüli genetikai variációt, és a legtöbb esetben - a kezdeti populációtól függően - megakadályozná, hogy elérjük a globális optimumot.

Mutációk nélkül nem lennének mutánsok, és mutánsok nélkül nem lenne az X-men franchise.

Mi történne, ha a lakosság mérete nem lenne elég nagy?

Nemrég jártam a Plettenbergben található Jukani Vadvédelmi Szentélyben, ahol kiváltságom volt egy fehér tigrisvel találkozni. Igazán fenséges állat volt. Nagy volt, vadul nézett ki, és szintén 80% -ban vak volt, és az évek múlásával egyre rosszabb lett.

Miért vak volt? Mert a beltenyésztés generációinak terméke. Ezeket a fehér tigriseket csak akkor állítják elő, ha két tigrist, amelyek recesszív génszabályozó kabátszínt hordoznak, együtt neveltetik. Így annak érdekében, hogy biztosítsák e tigrisek fogságban való folytatódását, az emberek nagyon korlátozott populáción belül tenyésztették ezeket a tigriseket annak érdekében, hogy megmutassák őket cirkuszokban, felvonultassák őket állatkertekbe, vagy háztartási háziállatként tarthassák őket.

A beltenyésztés egyik negatív hatása azonban az, hogy szigorúan korlátozza a fajon belüli genetikai variációt, ami fokozatosan növeli annak esélyét, hogy a káros recesszív tulajdonságok átkerülnek az utódokra.

A fehér tigris, akivel 2019 áprilisában találkoztam a Jukani Vadvédelmi Szentélyben. Fenségesnek tűnik, de szenved.

A beltenyésztés még a természetben is komoly problémát jelenthet. Az elmúlt néhány évtizedben a Dél-Afrikában az orrszarvú-populációt jelentős mértékben befolyásolták az orvvadászat, és ha a populáció mérete eléri a elég alacsony számot, ez azt jelentené, hogy ezen veszélyeztetett orrszarvú-fajok genetikai sokféleségének fenntartása rendkívül nehéz. Tehát még akkor is, ha az orvvadászat nem vezet teljesen kihaláshoz, akkor a beltenyésztés ezt is eredményezheti.

Fotó: redcharlie az Unsplash-en.

Természetesen az emberek nem idegenek a beltenyésztéshez. A saját fajunkon belüli folyamatos beltenyésztés egyik híres eredménye a spanyol II. Károly (Carlos).

„II. Habsburg spanyol király, spanyol király szomorúan elbomlott egy hatalmas rágcsálós fejjel. Habsburg állkapuja annyira kiállt, hogy két fogsorja nem tudott találkozni; nem tudta rágni. A nyelve olyan nagy volt, hogy alig tudott beszélni. Szelleme hasonlóan le van tiltva. ”

II. Habsburg király, Spanyolország. Apja az anyja nagybátyja volt, Károst pedig fiává tetve, unokaöccse, és unokatestvére.

A genetikai algoritmusunkban a „beltenyésztés” lényegében olyan megoldások tenyésztését jelenti, amelyek nagyon hasonló genetikai felépítéssel rendelkeznek, amely szerencsére ebben az esetben nem eredményezne utódokat, amelyek hajlamosak lennének bármilyen fizikai rendellenességre. De ha a populáció nagyon kicsi, és ha az összes megoldás genetikai felépítése nagyon hasonló, akkor a lakosság jövő generációinak alkalmassága súlyosan korlátozott lesz. Ez azt jelenti, hogy sokkal hosszabb időt vehet igénybe a globálisan optimális megoldás megismerése, ha egyáltalán oda is eljutunk.

A beltenyésztés nem mindig rossz dolog, csak attól függ, hogy a szimuláció melyik szakaszában tartózkodik. A szimuláció nagyon előrehaladott szakaszaiban, mivel a népesség egy globális / helyi optima felé halad, nyilvánvalóan nagyon nehéz elkerülni a beltenyésztetést, mert bizonyos esetekben sok domináns megoldás nagyon hasonló lesz egymáshoz, és így sok genetikai tulajdonsággal rendelkeznek.

Csomagolás

Rendben, ennek le kell fednie az alapokat. Ha bármilyen kérdése, kérése vagy genetikai mutációja van a hozzájáruláshoz, kérjük, hagyjon megjegyzést alább.

A következő bejegyzésben néhány kódot vizsgálunk meg, amikor megnézzük, hogy a fentebb vázolt genetikai operátorok hogyan játszanak ki a programozás világában. Használtam a Ruby programozási nyelvet a szoftveres szimulációhoz, amelyen dolgoztam, és megmutatom, hogy a genetikai algoritmus csak néhány generáció alatt előállíthat egy előre meghatározott szót vagy kifejezést a teljes és teljes hamisság kezdeti gyűjteményéből. Az összes kódot a Github tárolja.