Evolucijski algoritam
![](http://178.128.105.246/host-http-upload.wikimedia.org/wikipedia/commons/e/e7/Dawkins-Weasel.png)
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čki metaheuristički optimizacijski algoritam 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.
Slijedi primjer generičkog genetskog algoritma s jedinstvenim ciljem:
Prvi korak: Nasumično generiramo početnu populaciju jedinki. (Prva generacija)
Drugi korak: Ponavljamo sljedeće regeneracijske korake do završetka optimizacije:
- Procijenjujemo fitnes svake jedinke u populaciji (uz kriterij vremenskog ograničenja, postignutog dovoljnog fitnesa itd.)
- Selektiramo najsposobnije jedinke za reprodukciju. Te jedinke predstavljaju roditelje novoj generaciji.
- Razmnožavamo nove jedinke koristeći operacije križanja i mutacije kako bi stvorili potomstvo.
- Zamijenimo jedinke s najmanjom sposobnošću preživljavanja (fitnesom) u postojećoj generaciji populacije s novim jedinkama potomcima.
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.
import random
def generate_random_sequence(goal, characters):
sequence = ""
for i in range(len(goal)):
sequence += characters[random.randint(0, len(characters)-1)]
return sequence
def get_score(sequence, goal):
score = 0
for i in range(len(goal)):
if goal[i] == sequence[i]:
score += 1
return score
def mutate_sequence(sequence, characters):
result = ""
for i in range(len(sequence)):
if random.randint(0, 100) <= 5:
result += characters[random.randint(0, len(characters)-1)]
else:
result += sequence[i]
return result
def get_sequence_mutations(sequence, characters):
sequence_list = []
for i in range(100):
sequence_list.append(mutate_sequence(sequence, characters))
return sequence_list
def get_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)
for seq in sequence_list:
similarity_factor = get_score(seq, goal)
if similarity_factor > best_similarity_factor:
best_similarity_factor = similarity_factor
best_seq = seq
return best_seq
def main():
goal = "METHINKS IT IS LIKE A WEASEL"
characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
generations = 0
current_sequence = generate_random_sequence(goal, characters)
print("Generation", generations, ":", current_sequence)
while current_sequence != goal:
current_sequence = get_mutated_sequence(
current_sequence, goal, characters)
generations += 1
print("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]
Rojni algoritmi koji uključuju:
- 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.
-
EA pretraga s dvije populacije preko ograničene Rosenbrockove funkcije s ograničenim globalnim optimumom.
-
EA pretraga s dvije populacije preko ograničene Rosenbrockove funkcije . Globalni optimum nije ograničen.
-
EA pretraga ograničene optime Simionescuove funkcije s dvije populacije.
- ↑ 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
- ↑ Advances in evolutionary computing : theory and applications. Springer. Berlin. 2003. ISBN 3-540-43330-9
- ↑ Advances in evolutionary computing : theory and applications. Springer. Berlin. 2003. ISBN 3-540-43330-9
- ↑ 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.
- ↑ J. Clune, C. Ofria, and R. T. Pennock, "How a generative encoding fares as problem-regularity decreases", in PPSN (G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, eds.), vol. 5199 of Lecture Notes in Computer Science, pp. 358–367, Springer, 2008.
- ↑ Ferreira, C., 2001. "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems". Complex Systems, Vol. 13, issue 2: 87–129.
- ↑ 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
- ↑ Gent, Edd. 13. travnja 2020. Artificial intelligence is evolving all by itself. Science | AAAS (engleski). Inačica izvorne stranice arhivirana 16. travnja 2020. Pristupljeno 16. travnja 2020.
- ↑ Simionescu, P.A. 2004. Constrained optimization problem solving using estimation of distribution algorithms (PDF): 1647–1653. Pristupljeno 7. siječnja 2017. journal zahtijeva
|journal=
(pomoć)
- Ashlock, D. (2006), Evolucijsko računanje za modeliranje i optimizaciju, Springer,ISBN 0-387-22196-4 .
- Bäck, T. (1996), Evolucijski algoritmi u teoriji i praksi: Evolucijske strategije, Evolucijsko programiranje, Genetički algoritmi, Oxford Univ. Pritisnite.
- Bäck, T., Fogel, D., Michalewicz, Z. (1997), Priručnik evolucijskog računanja, Oxford Univ. Pritisnite.
- Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetsko programiranje - uvod, Morgan Kaufmann, San Francisco
- Eiben, AE, Smith, JE (2003), Uvod u evolucijsko računanje, Springer.
- Holland, JH (1992), Prilagodba u prirodnim i umjetnim sustavima, Sveučilište Michigan Press, Ann Arbor
- 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 ]
- Price, K., Storn, RM, Lampinen, JA, (2005). "Diferencijalna evolucija: praktični pristup globalnoj optimizaciji", Springer.
- Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (doktorska disertacija). Pretisnuo Fromman-Holzboog (1973).
- Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (doktorska disertacija). Pretisnuo Birkhäuser (1977).
- Simon, D. (2013): Evolucijski algoritmi za optimizaciju Arhivirana inačica izvorne stranice od 10. ožujka 2014. (Wayback Machine), Wiley.
- Računalna inteligencija: metodološki uvod Krusea, Borgelta, Klawonna, Moewesa, Steinbrechera, održanog, 2013, Springer,ISBN 978-1-4471-5012-1
- Rahman, Rosshairy Abd. 2017. Shrimp Feed Formulation via Evolutionary Algorithm with Power Heuristics for Handling Constraints. Complexity. 2017: 1–12