Računarska evolucija: uvod u genetske algoritme

Fotografija Hal Gatewood na Unsplash

Budući da je računalni znanstvenik zainteresiran za evoluciju i biološke procese, tema genetskih algoritama i šire, evolucijsko računanje je za mene ono što trgovina slatkišima predstavlja petogodišnjaku: Nebo. Sama mogućnost da uspijem spojiti svoja dva interesa na tako neprimjeren način bila je izuzetno uzbudljiva i bilo bi pogrešno da sve to znanje i uzbuđenje zadržim za sebe.

Dakle, u pokušaju da testiram neka svoja dosadašnja učenja i podijelim svoja saznanja sa ostatkom svijeta, odlučio sam sastaviti niz članaka o ovoj temi.

U ovom ću postu dati kratki uvod u genetske algoritme i objasniti kako oni oponašaju iste prirodne procese koji se odvijaju na Zemlji već milijarde godina.

Život na Zemlji

Tijekom proteklih 3,5 milijardi godina, majka priroda, vrijeme oca, evolucija i prirodna selekcija surađivale su zajedno u proizvodnji svih specijaliziranih oblika života koje danas vidimo na zemlji: poput biljke mesožderke Venere Flytrap; atlantska leteća riba koja živi u oceanu; šišmiši koji koriste eholokaciju; žirafe s dugim vratima; super brzi gepardi, plešuće mede; i naravno, vaš doista, ulični pametni Homo sapiens.

Muha iz Venere je mesožderka biljka koja se prvenstveno goji insektima i paukovima.Neki šišmiši koriste eholokaciju za navigaciju i lov na plijen, suprotno uvriježenom mišljenju, šišmiši zapravo nisu slijepi; vrsta šišmiša poznata kao Leteće lisice zapravo imaju bolji vid od ljudi.Leteće ribe ne mogu letjeti na isti način kao ptice. Međutim, ove ribe mogu napraviti snažne, samohodne skokove iz vode, gdje im dugačka peraja poput krila omogućavaju da klize po većoj udaljenosti iznad vodene površine.

Nepotrebno je reći da je život na Zemlji jedan, ako ne i najuspješniji eksperiment ikad izveden u našem svemiru; i sudeći po impresivnim rezultatima ovog eksperimenta, jasno je da je evolucija očito na nečemu.

Nedavno smo ljudi - samo jedan od mnogih krajnjih proizvoda ovog procesa - shvatili da također možemo iskoristiti taj genijalan pristup progresivnom rješavanju problema, a od 1950-ih, računalni znanstvenik, genetičari, matematičari i biolog, pokušali su oponašaju ove biološke procese primjenom računalnih simulacija. S ciljem stvaranja optimalnih rješenja za teške, nevivijalne probleme, na učinkovit način.

Slijepi satnik

Jedna od prvih knjiga na koju sam naišla pobudila je moje zanimanje za polje evolucijske biologije Richard Sleep, Richard Dawkins. U ovoj knjizi Richard Dawkins objašnjava kako složeni mehanizmi poput eholokacije (proces koji šišmiši koriste za navigaciju, lov i stočnu hranu, poznat i kao bio-sonar), složene strukture poput paukova mrežica (koje pauci koriste da privuku i uhvate svoj plijen) i složeni instrumenti poput ljudskog oka (ona dva sferna objekta koja trenutno koristite za čitanje ovog članka) jednostavno su rezultat tisuće, ako ne i milijuna godina evolucije i prilagodbe.

Progresivna evolucija ljudskog oka. Ono što je počelo kao jednostavne fotoosjetljive stanice, evoluiralo je u složen instrument koji često u potpunosti uzimamo zdravo za gotovo. Prve životinje s bilo čim sličnim okom živjele su prije oko 550 milijuna godina. I prema proračunu jednog znanstvenika, trebalo bi samo 364.000 godina da se oko nalik kameri razvija od flastera osjetljivog na svjetlo.

Iako ova čuda prirode ostavljaju dojam da su izgrađena s ciljem iz pokretanja (tj. Svjesnog 'tvorca'), zapravo su samo rezultat iteracija ponavljanja pokušaja i pogreške, sjedinjenih s uvijek - mijenjajući selekcijski pritisak (tj. promjenu klime, staništa ili ponašanja i sposobnosti grabežljivaca ili plijena). Iako mogu izgledati i ponašati se kao rezultat preciznog, naprednog inženjeringa, oni su zapravo rezultat potpuno slijepog procesa, procesa koji unaprijed ne zna što bi bilo savršeno „rješenje“.

Što su genetski algoritmi i zašto su nam potrebni?

Genetski algoritmi su tehnika koja se koristi za generiranje visokokvalitetnih rješenja za optimizaciju i probleme pretraživanja, a temelje se na temeljnim biološkim procesima. Ovi se algoritmi koriste u situacijama kada je mogući raspon rješenja vrlo velik i gdje bi osnovni pristupi rješavanju problema poput iscrpne potrage / grube sile zahtijevali previše vremena i truda.

Problem trgovca putnikom postavlja sljedeće pitanje: "S obzirom na popis gradova i udaljenosti između svakog para gradova, koja je najkraća moguća ruta koja posjeti svaki grad i vrati se u matični grad?" kombinatorna optimizacija.

Možemo koristiti genetske algoritme za pružanje kvalitetnih rješenja za ovaj problem po mnogo nižoj cijeni od primitivnijih tehnika rješavanja problema, poput iscrpne pretrage, koja će zahtijevati da provedete kroz sva moguća rješenja.

Kako djeluju genetski algoritmi?

Algoritam djeluje iteriranjem kroz više koraka, sve dok ne dostigne unaprijed određenu krajnju točku. Svaka iteracija genetskog algoritma stvara novu generaciju mogućih rješenja koja bi, u teoriji, trebala biti poboljšanje u odnosu na prethodnu generaciju.

Koraci su sljedeći:

1. Stvorite početnu populaciju od N moguća rješenja (iskonska juha)

Prvi korak algoritma je stvoriti početnu skupinu rješenja koja služe kao osnovna rješenja u generaciji 0. Svako rješenje u ovoj početnoj populaciji nosit će skup kromosoma, koji se sastoje od kolekcije gena, gdje je svaki gen dodjeljuje se jednoj od mogućih varijabli problema. Važno je da rješenja u početnoj populaciji budu stvorena slučajno dodijeljenim genima kako bi se postigla visoka razina genetičke varijacije.

2. Rješenja stanovništva rangirati po kondiciji (preživljavanje najjačih, 1. dio).

U ovom koraku algoritam treba biti u mogućnosti odrediti što jedno rješenje više 'stane' u odnosu na drugo rješenje. To se određuje fitness funkcijom. Cilj fitnes funkcije je procijeniti genetsku održivost otopina unutar populacije, stavljajući one s najviše održivih, povoljnih i superiornih genetskih svojstava na vrh popisa.

U problemu s prodavačem putovanja, fitness funkcija može biti izračun ukupne udaljenosti koju rješenje prođe. Tamo gdje kraća udaljenost odgovara većoj kondiciji.

3. Izbaci slabija rješenja (opstanak najprikladnijih, 2. dio)

U ovom koraku, algoritam uklanja manje prikladna rješenja iz populacije. "Prilagodniji" ne znači nužno najjače, najbrže ili najžešće, kako to ljudi obično pretpostavljaju. Preživljavanje najspremnijih jednostavno znači da što je bolje opremljen organizam za opstanak u svom okruženju, veća je vjerojatnost da će živjeti dovoljno dugo da se razmnožavaju i šire svoje gene na sljedeće generacije.

Koraci 3 i 4 zajedno su poznati kao odabir.

4. Uzgajati jača rješenja (preživljavanje najprikladnijih, 3. dio)

Preostala rješenja zatim se međusobno uparuju kako bi se udarilo i reproduciralo potomstvo. Tijekom ovog procesa, u svom najosnovnijem obliku, svaki roditelj će pridonijeti% svog gena (u prirodi je to razdvajanje 50/50) svakom svom potomstvu, gdje je P1 (G)% + P2 (G)% = 100 %. Proces utvrđivanja koji će od roditelja gene naslijediti potomstvo poznat je kao crossover.

5. Mutirati gene potomstva (mutacije)

Potomstvo će sadržavati postotak gena "majke" i postotak "očevih" gena, a povremeno će doći do "mutacije" jednog ili više tih gena. Mutacija je u osnovi genetska abnormalnost, pogreška kopiranja koja uzrokuje da se jedan ili više gena potomstva razlikuje od gena koje je naslijedila od svojih roditelja. U genetskim algoritmima, u nekim će slučajevima mutacija povećati tjelesnu sposobnost potomstva, u drugim će je smanjiti.

Važno je napomenuti da ne treba biti mutacija sa svakim potomstvom, potrebna frekvencija mutacije također može biti parametar algoritma.

U genetskim algoritmima selekcija, crossover i mutacija poznati su kao genetski operatori.

6. Prekid

Koraci 2 do 5 ponavljat će se sve do unaprijed definirane točke prekida. Ova krajnja točka može biti jedno od sljedećeg:

  1. Dostignuto maksimalno raspoređivanje vremena / resursa.
  2. Prošao je fiksni broj generacija.
  3. Usposobljenost dominantnog rješenja ne može nadmašiti nijedna buduća generacija.

Konvergencija rješenja

1. Globalni optimum

U idealnoj situaciji, najprikladnije rješenje imat će najveću moguću vrijednost fitnesa, tj. To će biti optimalno rješenje, što znači da neće biti potrebe nastaviti s algoritmom i proizvoditi nove generacije.

2. Lokalni optimum

U nekim slučajevima, ako parametri algoritma nisu razumni, populacija može težiti preuranjenoj konvergenciji na manje optimalno rješenje, što nije globalni optimum koji tražimo, već lokalni. Jednom ovdje, nastavljanje algoritma i stvaranje daljnjih generacija može biti uzaludno.

Globalni optimum vs lokalni optimum

Što bi se dogodilo ako ne bi bilo mutacija?

Na prvi pogled mutacije se mogu činiti nepotrebnim, nebitnim dijelom postupka. Ali bez ovog temeljnog aspekta slučajnosti, evolucija prirodnom selekcijom bila bi u potpunosti ograničena na genetsku raznolikost koju je postavila početna populacija, a nakon toga ne bi bilo novih osobina unesenih u populaciju. To bi ozbiljno spriječilo mogućnosti prirode da riješe probleme, a život na zemlji se ne bi mogao "prilagoditi" okolišu, barem ne fizički.

Da je to slučaj u našem genetskom algoritmu, u nekom trenutku naše simulacije, buduće generacije stanovništva ne bi mogle istraživati ​​dio prostora rješenja koji njihovi prethodnici nisu istraživali. Simulacija bez ikakvih mutacija ozbiljno bi ograničila genetsku varijaciju unutar populacije, a u većini slučajeva - ovisno o početnoj populaciji - spriječila bi nas da ikada postignemo globalni optimum.

Bez mutacija ne bismo imali mutante i bez mutanata ne bismo imali franšizu X-men.

Što bi se dogodilo ako veličina stanovništva nije bila dovoljno velika?

Nedavno sam bio u svetištu divljih životinja Jukani u Plettenbergu, gdje sam imao privilegiju da upoznam bijelog tigra. Bio je uistinu veličanstvena životinja. Bio je velik, izgledao je jezivo, a bio je i 80% slijep i postajao je progresivno gori kako su godine prolazile.

Zašto je bio slijep? Jer on je proizvod generacija inbreedinga. Ove bijele tigrove proizvode se samo ako se dva uzgajaju tigrovi koji nose boju dlake koja kontrolira recesivni gen. Stoga, kako bi osigurali nastavak tih tigrova u zatočeništvu, ljudi su uzgajali ove tigra u vrlo ograničenoj populaciji kako bi ih mogli prikazati u cirkusima, parirati u zoološkim vrtovima ili ih držati kao kućne ljubimce.

Ali jedan od negativnih učinaka inbridinga je da ozbiljno ograničavate genetičke varijacije unutar vrste, što progresivno povećava šansu da štetne recesivne osobine pređu na potomstvo.

Bijeli tigar kojeg sam sreo u svetištu divljih životinja Jukani u travnju 2019. Izgleda veličanstveno, ali pati.

Čak i u divljini inbreeding još uvijek može biti velik problem. Tijekom posljednjih nekoliko desetljeća, populacija nosoroga u Južnoj Africi bila je znatno pod utjecajem krivolova, a ako veličina populacije dostigne dovoljno nizak broj, to bi značilo da bi održavanje genetske raznolikosti tih ugroženih vrsta nosoroga bilo izuzetno teško. Dakle, čak i ako ih krivolov ne vodi u potpunosti do izumiranja, inbreeding bi mogao.

Fotografiju redcharlie na Unsplash-u.

Naravno, ljudima nije stranac inbreeding. Jedan poznati rezultat kontinuiranog križanja unutar vlastite vrste je Španjolski Charles (Carlos) II.

"Španjolski habsburški kralj Carlos II. Bio je na žalost degeneriran s ogromnom nesretnom glavom. Njegova čeljust Habsburga toliko je stajala da mu se dva zuba nisu mogla sastati; nije se mogao žvakati. Jezik mu je bio toliko krupan da se jedva mogao progovoriti. I njegov je intelekt bio onemogućen. "

Španjolski kralj Habsburg kralj Karlo II. Otac mu je bio ujak majke, što je od Charlesa postao njihov sin, veliki nećak i prvi rođak.

"Inbreeding" u našem genetskom algoritmu u osnovi znači uzgoj rješenja koja imaju vrlo sličnu genetsku strukturu, što, na sreću, u ovom slučaju ne bi rezultiralo potomstvom s predispozicijom za bilo kakve fizičke abnormalnosti. Ali ako je populacija vrlo mala i ako sva rješenja imaju vrlo sličnu genetsku strukturu, tada će sposobnost budućih generacija biti ozbiljno ograničena. Znači da bi moglo potrajati mnogo duže da se globalno optimalno rješenje postigne ako uopće i stignemo tamo.

Inbreeding nije uvijek loša stvar, samo ovisi u kojoj fazi simulacije se nalazite. U vrlo naprednim fazama simulacije, kako se populacija konvergira prema globalnom / lokalnom optima, očito je vrlo teško izbjeći inbreeding, jer , u nekim će slučajevima mnoga dominantna rješenja biti vrlo slična jedna drugoj, i time će dijeliti puno istih genetskih osobina.

Završavati

U redu, to bi trebalo pokriti osnove. Ako imate bilo kakvih pitanja, zahtjeva ili genetskih mutacija za doprinos, ostavite komentar u nastavku.

U sljedećem ćemo postu istražiti neki kod dok ćemo gledati kako se svaki od gore opisanih genetskih operatora igra u svijetu programiranja. Koristio sam programski jezik Ruby za simulaciju softvera na kojem sam radio, a u njemu pokazujem kako u samo nekoliko generacija genetski algoritam može proizvesti unaprijed definiranu riječ ili frazu iz početne zbirke cjelovitih i krajnjih besmislica. Sav se kod nalazit na Githubu.