U računalnoj inteligenciji (CI), evolucijski algoritam (EA) je generički metaheuristički optimizacijskialgoritam zasnovan na populacijama i podvrsta je evolucijskog računarstva.[1] EA koristi mehanizme nadahnute biološkom evolucijom, poput reprodukcije, mutacije, rekombinacije i selekcije. Kandidati rješenja problema optimizacije igraju ulogu pojedinih organizama tj. jedinki u populaciji, a funkcija sposobnosti 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 nastupa Evolucija 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živanja mikroevolucijskih 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 za aproksimaciju 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 takozvana Dawkinsova lasica poznata i pod nazivom Weasel program. Richard Dawkins ga je opisao u svojoj knjizi Slijepi 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 konvencionalnim superračunalima današnjice brute 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čnim mutacijama, ali je istovremeno vođena ne-nasumičnim mehanizmom prirodne 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 problema optimizacije .
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.
Diferencijalna evolucija - Temelji se na vektorskim razlikama i stoga je prvenstveno pogodan za probleme numeričke optimizacije.
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 jasna razlika između genotipa i fenotipa. U prirodi, oplođena jajna stanica prolazi kroz složeni proces poznat kao embriogeneza kako bi poprimila oblik odraslog fenotipa. Vjeruje se da ovo neizravno kodiranje genetsku pretragu čini robusnijom (npr. smanjuje vjerojatnost fatalnih mutacija), a također može poboljšati evolubilnost 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 polju umjetne 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 s grafovima .
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 ptica kukavice. Ova tehnika također koristi Lévyjeve letove pa je stoga pogodna za rješavanje problema globalne optimizacije.
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 stvaraju jato. Također prvenstveno pogodan za probleme numerič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]
Računalne simulacije Tierra i Avida pokušavaju modelirati makroevolucijsku dinamiku.
↑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 ]