Potpuni ispis nakon pokretanja programa poznatog pod nazivomDawkinsova lasica koji evoluira 100 jedinki po generaciji s 5% vjerojatnoti pojave mutacije prilikom kopiranja svakog pojedinog slova. Samo najsposobnija jedinka/string je prikazan po svakoj generaciji. Možete primijetiti da u osmoj generaciji 25. znak, koji je bio točno pogođen (A), postaje ponovo netočan znak (I). Program ne "zaključava" točno pogođene znakove, nego pri svakoj iteraciji mjeri koliko je cijeli string blizu stringu znakova ciljne fraze.
U računalnoj inteligenciji (CI),evolucijski algoritam (EA) je generičkimetaheurističkioptimizacijskialgoritam zasnovan napopulacijama i podvrsta je evolucijskog računarstva.[1] EA koristi mehanizme nadahnutebiološkom evolucijom, poputreprodukcije,mutacije,rekombinacije iselekcije. Kandidati rješenja problema optimizacije igraju ulogu pojedinih organizama tj. jedinki u populaciji, a funkcijasposobnosti preživljavanja, ili kraće fitnesa, određuje kvalitetu svakog od ponuđenih rješenja u pojedinoj generaciji. Pokretanjem računanja nakon apliciranja gore navedenih operatora nastupaEvolucija populacije rješenja.
Evolucijski algoritmi često jako dobro izvršavaju zadaće pronalaženja aproksimativnih rješenja svih vrsta problema jer u idealnom slučaju inicijalno ne pretpostavljaju osnovni krajolik fitnesa tj.adaptivni krajolik. Tehnike evolucijskih algoritama primijenjene na modeliranje biološke evolucije uglavnom su ograničene na istraživanjamikroevolucijskih procesa i modela planiranja temeljenih na staničnim procesima. U većini stvarnih primjena računska složenost EA algoritama je ograničavajući faktor za raširenost primjene ovakve vrste računalne optimizacije.[2] Spomenuta razmjerno velika računska složenost uglavnom je rezultat složenog računanja funkcije sposobnosti preživljavanja tj. fitnes funkcije. Jedan od načina da se ta složenost umanji je korištenje tehnika zaaproksimaciju fitnes funkcije. Svejedno, ipak je poznato da naizgled jako jednostavan evolucijski algoritam često može riještiti i vrlo složene probleme tako da je moguće da ne mora postojati izravna i čvrsta veza između složenosti samog problema i složenosti potrebnog evolucijskog mehanizma da se problem riješi.
Dobar primjer evolucijskog tj. genetičkog algoritma je takozvanaDawkinsova lasica poznata i pod nazivomWeasel program.Richard Dawkins ga je opisao u svojoj knjiziSlijepi urar a od tada se često koristi kao ilustracija mogućnosti genetskih algoritama.
importrandomdefgenerate_random_sequence(goal,characters):sequence=""foriinrange(len(goal)):sequence+=characters[random.randint(0,len(characters)-1)]returnsequencedefget_score(sequence,goal):score=0foriinrange(len(goal)):ifgoal[i]==sequence[i]:score+=1returnscoredefmutate_sequence(sequence,characters):result=""foriinrange(len(sequence)):ifrandom.randint(0,100)<=5:result+=characters[random.randint(0,len(characters)-1)]else:result+=sequence[i]returnresultdefget_sequence_mutations(sequence,characters):sequence_list=[]foriinrange(100):sequence_list.append(mutate_sequence(sequence,characters))returnsequence_listdefget_mutated_sequence(sequence,goal,characters):sequence_list=get_sequence_mutations(sequence,characters)best_seq=sequence_list[0]best_similarity_factor=get_score(best_seq,goal)forseqinsequence_list:similarity_factor=get_score(seq,goal)ifsimilarity_factor>best_similarity_factor:best_similarity_factor=similarity_factorbest_seq=seqreturnbest_seqdefmain():goal="METHINKS IT IS LIKE A WEASEL"characters="ABCDEFGHIJKLMNOPQRSTUVWXYZ "generations=0current_sequence=generate_random_sequence(goal,characters)print("Generation",generations,":",current_sequence)whilecurrent_sequence!=goal:current_sequence=get_mutated_sequence(current_sequence,goal,characters)generations+=1print("Generation",generations,":",current_sequence)main()
Ono što je posebno zanimljivo je to da se procjenjuje da bi i najmoćnijim konvencionalnimsuperračunalima današnjicebrute force nasumičnim algoritmom trebalo nekoliko milijuna milijuna godina da ispravno pogode zadani niz od 28 znakova, dok je vaše obično kućno računalo koristeći gore opisani genetski algoritam sposobno pogoditi zadani niz u nekoliko sekundi. Na taj način najbolje ilustriramo razliku između nasumičnog procesa pogađanja i evolucije koja je pokretana također nasumičnimmutacijama, ali je istovremeno vođena ne-nasumičnim mehanizmomprirodne selekcije.
Slične tehnike razlikuju se u reprezentaciji gena i ostalim detaljima implementacije te u prirodi primjene na pojedinu vrstu problema:
Genetski algoritam - ovo je najpopularnija vrsta EA. Rješenje problema traži se u obliku nizova brojeva (tradicionalno binarnih, premda su najbolji prikazi obično oni koji odražavaju prirodu problema koji se rješava),[3] primjenom operatora kao što su rekombinacija i mutacija (ponekad jedan, ponekad oba). Ova vrsta EA često se koristi za rješavanje problemaoptimizacije .
Genetsko programiranje - Ovdje su rješenja u obliku računalnih programa, a njihov fitnes je određen sposobnošću rješavanja zadanog računalnog problema.
Evolucijsko programiranje - slično genetskom programiranju, ali je struktura programa fiksna te je dopušten razvoj njegovih numeričkih parametara.
Programiranje ekspresije gena - Poput genetskog programiranja, GEP također evoluira računalne programe, ali istražuje sustav genotip-fenotip, gdje su računalni programi različitih veličina kodirani u linearne kromosome fiksne duljine.
Strategija evolucije - Radi s vektorima realnih brojeva koji predstavljaju rješenja i obično koristi stope samoadaptirajuće mutacije.
Neuroevolucija - Slično genetskom programiranju, ali genomi predstavljaju umjetne neuronske mreže opisujući strukturu i težinu neuronskih veza. Kodiranje genoma može biti izravno ili neizravno.
Učenje sustava klasifikatora - ovdje je rješenje skup klasifikatora (pravila ili uvjeta). Michigan-LCS evoluira na razini pojedinačnih klasifikatora, dok Pittsburgh-LCS koristi populacije skupova klasifikatora. U početku su klasifikatori bili samo binarni, ali sada uključuju realne brojeve kao i neuronske mreže. Fitnes se obično određuje putem snage povratne mreže ili se točnost temelji na mašinskom učenju.
Moguće ograničenje mnogih evolucijskih algoritama je to što u njima nedostaje jasnarazlika između genotipa i fenotipa. U prirodi, oplođena jajna stanica prolazi kroz složeni proces poznat kaoembriogeneza kako bi poprimila oblik odraslogfenotipa. Vjeruje se da ovo neizravnokodiranje genetsku pretragu čini robusnijom (npr. smanjuje vjerojatnost fatalnih mutacija), a također može poboljšatievolubilnost organizma.[4] Takvo neizravno (tj. generativno ili razvojno) kodiranje također omogućava procesu evolucije iskorištavanje regularnosti u okolišu.[5] Nedavni radovi na poljuumjetne embriogeneze tj. proučavanja umjetnih razvojnih sustava nastoje riješiti ove probleme. I programiranje putem ekspresije gena uspješno istražuje vezu genotip-fenotip, gdje se genotip sastoji od linearnih multigenih kromosoma fiksne duljine, a fenotip se sastoji od više stabala ekspresije ili računalnih programa različitih veličina i oblika.[6]
Optimizacija kolonije mrava - Na temelju spoznaja o mravljem istraživanju terena potpomognutim feromonskom komunikacijom kako bi se stvorili utabani putovi. Primarno pogodan za kombinatornu optimizaciju i probleme sgrafovima .
Runner-root algoritam (RRA) nadahnut je funkcijom klica i korijena biljaka u prirodi[7]
Algoritam umjetne košnice - Temelji se na ponašanju pčela kod potrage za hranom. Prvenstveno predlagan za korištenje u numeričkoj optimizaciji i proširen za korištenje u rješavanju kombinatornih, ograničenih i višeciljnih problema optimizacije.
Algoritam pčela temelji se na ponašanju pčela medonoša. Primijenjen je u mnogim aplikacijama kao što su usmjeravanje i raspoređivanje.
Kukavičja pretraga nadahnuta je mračnim parazitizmom vrste pticakukavice. Ova tehnika također koristiLévyjeve letove pa je stoga pogodna za rješavanje problema globalneoptimizacije.
Elektronska optimizacija - Na temelju ponašanja toka elektrona kroz grane električnog kruga s najmanjim električnim otporom.[8]
Particle Swarm optimizacija - Na temelju spoznaja o ponašanju životinja koje stvarajujato. Također prvenstveno pogodan za problemenumeričke optimizacije .
Google je 2020. izjavio da njihov AutoML-Zero može uspješno poptpuno samostalno otkriti tj. izumiti klasične algoritme poput koncepta neuronskih mreža.[9]
↑Vikhar, P. A. 2016. Evolutionary algorithms: A critical review and its future prospects.Proceedings of the 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC): 261–265
↑G.S. Hornby and J.B. Pollack. "Creating high-level components with a generative representation for body-brain evolution".Artificial Life, 8(3):223–246, 2002.
↑F. Merrikh-Bayat, "The runner-root algorithm: A metaheuristic for solving unimodal and multimodal optimization problems inspired by runners and roots of plants in nature",Applied Soft Computing, Vol. 33, pp. 292–303, 2015
↑Khalafallah Ahmed. 1. svibnja 2011. Electimize: New Evolutionary Algorithm for Optimization with Application in Construction Engineering.Journal of Computing in Civil Engineering.25 (3): 192–201
Michalewicz Z., Fogel DB (2004.). Kako to riješiti: Moderna heuristika, Springer.
Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, solved with the evolution of algorithms". 2010 IEEE Peta međunarodna konferencija o bio-nadahnutom računanju: teorije i primjene (BIC-TA). str. 298–302. doi : 10.1109 / BICTA.2010.5645312. ISBN Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, solved with the evolution of algorithms". Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, solved with the evolution of algorithms". S2CID 16875144 .
Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). Terenski vodič za genetsko programiranje. Lulu.com, slobodno dostupan s Interneta. ISBN Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). izvornika 27. svibnja 2016. Pristupljeno 05.03.2011. [ izvor koji je sam objavio ]
.gif)
.gif)
