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 äärmiselt virgutav ja mul oleks vale jätta need teadmised ja põnevus endale.

Püüdes proovida 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.

Venus-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.

Hiljuti 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. Eesmärk on tõhusal viisil leida optimaalseid lahendusi rasketele, 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 pikkuse 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 eesmärgiga saada kätte (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 tulemus, protsess, mis ei tea ette, mis oleks ideaalne 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 lahendamisele, 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 kombinatoorne optimeerimine.

Saame selle probleemi jaoks kvaliteetsete lahenduste pakkumiseks geneetilisi algoritme kasutada palju madalamate kuludega kui primitiivsemad probleemide lahendamise tehnikad, näiteks ammendav otsing, mis eeldaks kõigi võimalike lahenduste kasutamist.

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 annab uue põlvkonna võimalikke lahendusi, mis teoreetiliselt peaksid olema eelneva põlvkonna täiendused.

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 algpopulatsioonis oleksid lahendused loodud juhuslikult määratud geenidega.

2. Paigutage elanikkonna lahendused sobivuse järgi (fikseeritumate 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 või ä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 omavahel, 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 abil määratakse kindlaks, millise vanema geeni järglased pärandavad, 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. – 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, see tähendab, et see on optimaalne lahendus, mis tähendab, et ei ole vaja jätkata algoritmiga ja toota järgmisi põlvkondi.

2. Kohalik optimaalne

Mõnel juhul, kui algoritmi parameetrid pole mõistlikud, võib populatsioon kalduda enneaegse lähenemise poole vähem optimaalse lahenduse osas, mis ei ole globaalne optimaalsus, millest me järel oleme, 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 seatud geneetilise sordiga ja pärast seda ei oleks populatsioonis uusi jooni. See takistaks tõsiselt looduse probleemide lahendamise võimalusi ja maapealne elu ei saaks keskkonnaga vähemalt kohaneda, vähemalt mitte füüsiliselt.

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 tõenäosust, 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 ninasarvikute 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 inbreedid võõrad. Ü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' sisendumine tähendab sisuliselt väga sarnase geneetilise struktuuriga lahenduste aretamist, mis õnneks ei anna sel juhul järglasi, kellel oleks eelsoodumus mingite füüsiliste kõrvalekallete tekkeks. Kuid kui populatsioon 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.

Seitsmekasvatus 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 tõuaretusprobleeme 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 küsimusi, taotlusi või geneetilisi mutatsioone, palun lisage 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.