Evolutsiooni arvutiteadus: sissejuhatus geneetilistesse algoritmidesse

Foto autor Hal Gatewood saidil Unsplash

Olles arvutiteadlane, kes on huvitatud evolutsioonist ja bioloogilistest protsessidest, geneetiliste algoritmide ja laiemalt evolutsiooniarvestusest, on minu jaoks see, mis on kommipood 5-aastasele inimesele: Taevas. Pelgalt võimalus suhelda kaks oma huvi nii sujuvalt on olnud ülimalt virgutav ja mul oleks vale jätta need teadmised ja põnevus endale.

Püüdes katsetada mõnda oma senist õpet ja jagada oma järeldusi muu maailmaga, otsustasin kokku panna selleteemalised artiklid.

Selles postituses annan põgusa sissejuhatuse geneetilistesse algoritmidesse ja selgitan, kuidas need jäljendavad samu looduslikke protsesse, mis Maal on toimunud miljardeid aastaid.

Elu Maal

Viimase 3,5 miljardi aasta jooksul on ema loodus, isa aeg, evolutsioon ja looduslik valik teinud koostööd kõigi nende eriliste eluvormide valmistamiseks, mida me tänapäeval maa peal näeme: näiteks lihasööja Venus Flytrapi taim; ookeanis elavad atlandi lendavad kalad; ehholokatsiooni kasutavad nahkhiired; pika kaelaga kaelkirjakud; ülikiire gepardid, tantsivad mesilased; ja muidugi, teie siiralt, tänava nutikas Homo sapiens.

Venuse kärbseseen on lihasööja taim, mis toitub peamiselt putukatest ja ämblikulaadsetest.Mõned nahkhiired kasutavad saagil navigeerimiseks ja jahipidamiseks ehholokatsiooni ning vastupidiselt levinud arvamusele pole nahkhiired tegelikult pimedad; nahkhiirte liik, keda tuntakse kui lendavaid rebaseid, on tegelikult parema nägemisega kui inimesed.Lendavad kalad ei saa lennata samamoodi kui linnud, kuid need kalad suudavad veest jõulisi iseliikuvaid hüppeid teha, kui nende pikad tiibukesed uimed võimaldavad neil libiseda märkimisväärse vahemaa tagant veepinna kohal.

Ütlematagi selge, et elu Maal on üks, kui mitte kõige edukamaid katseid, mis meie universumis kunagi läbi viidud; ning selle katse muljetavaldavate tulemuste põhjal on selge, et evolutsioon on selgelt millegi peal.

Viimasel ajal mõistsime meie, inimesed - vaid üks selle protsessi paljudest lõpptoodetest -, et saaksime ka seda geniaalset lähenemisviisi progressiivsel probleemide lahendamisel ära kasutada ning alates 1950. aastatest on arvutiteadlased, geneetikud, matemaatikud ja bioloog püüdnud matkivad neid bioloogilisi protsesse arvutisimulatsioonide rakendamise kaudu. Selle eesmärk on tõhusal viisil leida optimaalseid lahendusi keerulistele, mitte triviaalsetele probleemidele.

Pime kellassepp

Üks esimesi raamatuid, millega ma kokku sattusin ja mis minu arengu evolutsioonibioloogia vastu huvi äratas, oli Richard Dawkinsi kirjutatud The Blind Watchmaker. Selles raamatus selgitab Richard Dawkins, kuidas keerulised mehhanismid nagu ehholokatsioon (protsess, mida nahkhiired kasutavad navigeerimiseks, jahipidamiseks ja söödaks, nimetatakse ka bioloogiliseks sonariks), keerulised struktuurid nagu ämblikuvõrgud (mida ämblikud kasutavad saagiks ja saagi püüdmiseks) ja keerulised instrumendid nagu inimsilm (need kaks sfäärilist objekti, mida te praegu selle artikli lugemiseks kasutate) on lihtsalt tuhandete, kui mitte miljonite aastate evolutsiooni ja kohanemise tulemus.

Inimsilma järkjärguline areng. Mis algas lihtsate valgustundlike rakkudena, kujunes keerukaks instrumendiks, mida võtame sageli täiesti enesestmõistetavana. Esimesed loomad, kellel midagi silma jäi, elasid umbes 550 miljonit aastat tagasi. Ja ühe teadlase arvutuste kohaselt kuluks kaamerasarnase silma valgustundlikust plaastrist väljaarenemiseks vaid 364 000 aastat.

Isegi kui need looduse imed jätavad mulje, et need on ehitatud otstarbelt (st teadliku „tegija” poolt), on need tegelikult lihtsalt katse-eksituse iteratsioonide iteratsioonide tulemus, mis on komplekteeritud - muutuv selektsioonisurve (st kliima, elupaiga või kiskjate või röövloomade käitumise ja võimete muutus). Ehkki nad võivad välja näha ja käituda täpse, tulevikku suunatud mõtteviisi tulemusena, on need tegelikult täiesti pimeda protsessi tagajärg, protsess, mis ei tea ette, milline oleks täiuslik „lahendus”.

Mis on geneetilised algoritmid ja miks me neid vajame?

Geneetilised algoritmid on tehnika, mida kasutatakse kvaliteetsete lahenduste genereerimiseks optimeerimiseks ja probleemide otsimiseks, mis põhinevad fundamentaalsetel bioloogilistel protsessidel. Neid algoritme kasutatakse olukordades, kus võimalik lahenduslahendus on väga suur ja kus põhimõttelisemad lähenemisviisid probleemide lahendamiseks, näiteks ammendav otsing / jõuline jõud, kulutaksid liiga palju aega ja vaeva.

Reisimüüja probleem küsib järgmist küsimust: "Milline on linnade loetelu ja iga linnapaari vaheline kaugus, siis milline on kõige lühem marsruut, mis külastab iga linna ja naaseb lähtelinna?" See on NP-raske probleem kombinatoorse optimeerimise osas.

Selle probleemi jaoks kvaliteetsete lahenduste pakkumiseks saame kasutada geneetilisi algoritme, palju odavamalt kui primitiivsemad probleemilahendusmeetodid, näiteks põhjalik otsing, mis nõuaks kõigi võimalike lahenduste otsimist.

Kuidas geneetilised algoritmid töötavad?

Algoritm töötab itereerides läbi mitmeid samme, kuni see jõuab etteantud lõpp-punktini. Iga geneetilise algoritmi iteratsioon loob uue põlvkonna võimalikke lahendusi, mis teoreetiliselt peaks olema eelneva põlvkonna täienduseks.

Sammud on järgmised:

1. Koostage N võimaliku lahendi esialgne populatsioon (ürgne supp)

Algoritmi esimene samm on luua esialgne lahendusrühm, mis toimib 0. põlvkonnas baaslahendusena. Selles algses populatsioonis sisaldab iga lahendus kromosoomide komplekti, mis koosneb geenide kogumist, kus iga geen on määratud ühe võimaliku probleemi muutujaga. Suure geneetilise varieeruvuse saavutamiseks on oluline, et algpopulatsiooni lahendused luuakse juhuslikult määratud geenidega.

2. Paigutage elanikkonna lahendused sobivuse järgi (kõige kindlam ellujäämine, 1. osa).

Selles etapis peab algoritm suutma kindlaks teha, mis muudab ühe lahenduse rohkem sobivaks kui teine. Selle määrab sobivusfunktsioon. Sobivusfunktsiooni eesmärk on hinnata lahenduste geneetilist elujõulisust populatsioonis, asetades kõige paremad, soodsamad ja paremad geneetilised omadused need, kes on nimekirja tipus.

Reisimüüja probleemi korral võiks sobivusfunktsioon olla lahenduse läbitud kogupikkuse arvutamine. Kus lühem vahemaa võrdub kõrgema sobivusega.

3. Kustutage nõrgemad lahendused (kõige kindlam ellujäämine, 2. osa)

Selles etapis eemaldab algoritm populatsioonist vähem sobivad lahendused. „Kõige tugevam” ei tähenda tingimata kõige tugevamat, kiiremat ega ägedamat, nagu inimesed tavaliselt kipuvad arvama. Kõige tugevama ellujäämine tähendab lihtsalt seda, et mida paremini varustatud organism peab oma keskkonnas ellu jääma, seda tõenäolisem on, et ta elab piisavalt kaua, et paljuneda ja levida oma geenid järgmisele põlvkonnale.

3. ja 4. etappi nimetatakse ühiselt valimiseks.

4. Aretage tugevamaid lahendusi (kõige kindlam ellujäämine, 3. osa)

Seejärel paaritatakse ülejäänud lahused üksteisega, et järglasi paaritada ja paljundada. Selle protsessi käigus paneb iga vanem oma põhivormil% oma geenidest (looduses on see jagatud 50/50) igale järglasele, kus P1 (G)% + P2 (G)% = 100 %. Protsessi, mille käigus otsustatakse, millised vanemate geenid järglased pärivad, nimetatakse ristandiks.

5. Mutate järglaste geene (mutatsioon)

Järglased sisaldavad protsenti ema geenidest ja protsenti isade geenidest ning aeg-ajalt toimub ühe või mitme geeni "mutatsioon". Mutatsioon on sisuliselt geneetiline kõrvalekalle, kopeerimisviga, mille tõttu üks või mitu järglase geeni erinevad geenidest, mille ta oma vanematelt pärandas. Geneetilistes algoritmides suurendab mutatsioon mõnel juhul järglaste sobivust, muudel juhtudel vähendab seda.

Oluline on märkida, et iga järglasega ei pea mutatsiooni olema, vajalik mutatsiooni sagedus võib olla ka algoritmi parameeter.

Geneetilistes algoritmides tuntakse selektsiooni, ristumist ja mutatsiooni geneetiliste operaatoritena.

6. Lõpetamine

2. kuni 5. sammu korratakse kuni eelnevalt määratud lõpp-punktini. See lõpp-punkt võib olla üks järgmistest:

  1. Maksimaalne aja- / ressursijaotus on saavutatud.
  2. Fikseeritud arv põlvkondi on möödunud.
  3. Ükski tulevane põlvkond ei saa domineeriva lahenduse sobivusest üle olla.

Lahenduste lähenemine

1. Globaalne optimaalsus

Ideaalses olukorras on kõige optimaalsemal lahendusel kõrgeim sobivusväärtus, st see on optimaalne lahendus, mis tähendab, et pole vaja jätkata algoritmiga ja toota uusi põlvkondi.

2. Kohalik optimaalne

Mõnel juhul, kui algoritmi parameetrid ei ole mõistlikud, võib populatsioon kalduda enneaegse lähenemise poole vähem optimaalse lahenduse osas, mis ei ole globaalne optimaalsus, mida me järgime, vaid pigem kohalik. Kunagi siin võib algoritmi jätkamine ja edasiste põlvkondade tootmine olla mõttetu.

Globaalne ja kohalik optimaalne

Mis juhtuks, kui mutatsioone ei oleks?

Esmapilgul võivad mutatsioonid tunduda protsessi tarbetu, tähtsusetu osa. Kuid ilma selle juhuslikkuse põhimõttelise aspektita piirduks loodusliku valiku teel evolutsioon täielikult algpopulatsiooni poolt seatud geneetilise sordiga ja pärast seda ei oleks populatsioonis uusi jooni. See takistaks tõsiselt looduse probleemide lahendamise võimet ja maapealne elu ei suudaks vähemalt keskkonnaga "kohaneda" oma keskkonnaga.

Kui see oleks nii meie geneetilise algoritmi puhul, siis ei saaks meie simulatsiooni mingil hetkel tulevased elanikkonna põlvkonnad uurida osa lahendusruumist, mida nende eelkäijad ei uurinud. Mutatsioonideta simulatsioon piiraks populatsiooni geneetilisi variatsioone tõsiselt ja enamikul juhtudel - sõltuvalt algpopulatsioonist - takistaksime meil kunagi saavutamast globaalset optimaalsust.

Ilma mutatsioonideta poleks meil mutante ja ilma mutantideta poleks meil X-Meni frantsiisi.

Mis juhtuks, kui rahvaarv ei oleks piisavalt suur?

Olin hiljuti Jukani looduskaitsealal Plettenbergis, kus mul oli au kohtuda valge tiigriga. Ta oli tõeliselt majesteetlik loom. Ta oli suur, ta näis metsik ja lisaks oli ta 80% pime ning aastatega aina hullemaks muutumas.

Miks ta pime oli? Sest ta on põlvkondade siseringide toode. Neid valgeid tiigreid toodetakse ainult siis, kui koos kasvatatakse kaks tiigrit, mis kannavad retsessiivset geeni, mis kontrollib karva värvi. Niisiis, et tagada nende tiigrite jätkamine vangistuses, on inimesed aretanud neid tiigreid väga piiratud populatsioonis, et neid siis näidata tsirkuses, parodeerida loomaaedades või hoida neid koduloomadena.

Kuid üks tõuaretusest tulenevatest negatiivsetest mõjudest on see, et piirate tugevalt liigi geneetilist varieeruvust, mis suurendab järk-järgult võimalust, et kahjulikud retsessiivsed omadused kanduvad järglastele edasi.

Valge tiiger, keda kohtasin Jukani eluslooduse pühapaigas aprillis 2019. Ta näeb välja majesteetlik, kuid kannatab.

Isegi looduses võib tõuaretus olla endiselt tohutu probleem. Viimase paarikümne aasta jooksul on Lõuna-Aafrika ninasarvik populatsiooni salaküttimise tõttu märkimisväärselt mõjunud ning kui populatsiooni suurus jõuab piisavalt madalale, tähendaks see, et nende ohustatud ninasarviku liikide geneetilise mitmekesisuse säilitamine oleks äärmiselt keeruline. Nii et isegi kui salaküttimine ei vii neid täielikult väljasuremiseni, võib sissetungimine seda teha.

Foto redcharlie saidil Unsplash.

Muidugi pole inimestel sisserändamine võõras. Üks kuulus tulemus meie oma liigi pidevas aretuses on Charles II (Carlos) Hispaania II.

Hispaania Habsburgide kuningas Carlos II oli kahjuks tohutu väärarenguga mandunud. Tema Habsburgi lõualuu seisis nii palju, et tema kaks hammaste rida ei saanud kohtuda; ta ei suutnud närida. Tema keel oli nii suur, et ta vaevalt oskas rääkida. Tema intellekt oli samamoodi puudega. ”

Hispaania Habsburgide kuningas Charles II. Tema isa oli ema onu, kes tegi Charlesist nende poja, õepoja ja esimese nõbu.

'Geneetilise algoritmi' sisendus 'tähendab sisuliselt väga sarnase geneetilise ülesehitusega lahenduste aretamist, mis õnneks ei anna sel juhul järglasi, kellel oleks eelsoodumus mingite füüsiliste kõrvalekallete tekkeks. Kuid kui elanikkond on väga väike ja kui kõigil lahendustel on väga sarnane geneetiline struktuur, on elanikkonna tulevaste põlvkondade sobivus tõsiselt piiratud. See tähendab, et globaalselt optimaalse lahenduse leidmine võib võtta palju kauem aega, kui me sinna üldse jõuame.

Seitsmeliiklus ei ole alati halb asi, see sõltub lihtsalt sellest, millises simulatsiooni etapis te viibite. Simulatsiooni väga edasijõudnute etappide ajal, kui elanikkond koondub globaalse / kohaliku optimaalsuse poole, on ilmselgelt väga raske sissetungimist vältida, kuna , mõnel juhul on paljud domineerivad lahendused üksteisega väga sarnased ja jagavad seega paljusid samu geneetilisi tunnuseid.

Pakkimine üles

Hea küll, see peaks hõlmama põhitõdesid. Kui teil on lisaküsimusi, taotlusi või geneetilisi mutatsioone, jätke kommentaar allpool.

Järgmises postituses käsitleme mõnda koodi, kui vaatame, kuidas mängib iga ülaltoodud geneetiline operaator programmeerimise maailmas. Ma kasutasin tarkvara modelleerimiseks Ruby programmeerimiskeelt, mille kallal töötasin, ja näitan selles, kuidas vaid mõne põlvkonna jooksul suudab geneetiline algoritm toota etteantud sõna või fraasi täieliku ja täieliku hiilguse esialgsest kogust. Kogu kood hostitakse Githubis.