Evolucioni algoritam

S Vikipedije, slobodne enciklopedije

U veštačkoj inteligenciji, evolucijski algoritam (EA) je podskup evolucijskog računarstva, generičkih metaheuristika za optimizaciju zasnovanih na populaciji. EA koristi algoritme zasnovane na biološkoj evoluciji, kao što su reprodukcija, mutacija, rekombinacija i selekcija. Rešenje optimizacionog problema je jedna individua iz populacije, a fitnes funkcija određuje kvalitet rešenja (pogledaj funkciju gubitka). Evolucija populacije se odigrava nakon ponovne primene gorenavedenih operacija. Veštačka evolucija (VE) opisuje proces koji obuhvata pojedinačne evolucione algoritme.

Evolucioni algoritmi često aproksimiraju rešenja za sve vrste problema zato što ne prave nikakve pretpostavke o osnovi fitnes područja; ova opštost se pokazuje uspesima algoritama u mnogim poljima, kao što su inžinjerstvo, umetnost, biologija, ekonomija, marketing, genetika, operaciona istraživanja, robotika, društvenim naukama, fizici, politici i hemiji.[1]

Tehnike iz evolucionih algoritama koje se primenjuju u modeliranju biološke evolucije su uglavnom ograničene na istraživanje mikroevolucionarnih procesa i planiranju modela zasnovanih na ćelijskim procesima. Kompjuterske simulacije Tiera i Avida pokušavaju da modeluju mikroevolucionarna kretanja.

U većini realnih primena EA, kompleksnost algoritma je najveći problem. Zapravo, složenost je velika zbog kompleksne fitnes funkcije. Fitnes aproksimacije su jedne od mogućih rešenja za ovaj problem. Međutim, naizgled prost EA može da reši veoma složene probleme; stoga, ne postoji direktna veza izmedju složenosti algoritma i složenosti problema.

Moguće ograničenje mnogih evolucijskih algoritama je njihov nedostatak razlike između genotipa i fenotipa. U prirodi, oplođena jajna ćelija prolazi kroz složen proces poznat kao embriogeneza da bi postala zreo fenotip. Za ovakvo indirektno kodiranje se veruje da čini genetska istraživanja robustnijim (npr. Da smanji verovatnoću smrtonosnih mutacija), i takođe može poboljšati evolutivnost organizama.[2][3] Takva indirektna (zvana geretarivna ili razvojna) kodiranja omogućavaju evoluciji da iskoristi pravilnosti u okruženju.[4] Skorošnja istraživanja na polju veštačke embriogeneze, tj. razvoja veštačkih razvojnih sistema, nastoje da odgovore na ove zabrinutosti. Genetsko programiranje uspešno istražuje genotip-fenotip sistem, gde se genotip sastoji od linearnih multigenetskih hromozoma fiksne dužine a fenotip se sastoji od više ekspresionih stabala ili kompjuterskih programa različite veličine i oblika.[5]

Implementacija bioloških procesa[uredi | uredi izvor]

  1. Generiši početnu populaciju individua nasumično (prva generacija)
  2. Izračunaj adaptivnu vrednost svake od individua u toj populaciji.
  3. Ponavljaj ovo generisanje do kraja (vremensko ograničenje, postignuta dovoljna adaptivna vrednost, itd):
    1. Izaberi individue sa najboljom adaptnivnom vrednošću za reprodukciju (roditelje)
    2. Kreiraj nove individue na osnovu roditelja pomoću operacija ukrštanja i mutacije i tako stvori potomstvo.
    3. Izračunaj adaptivnu vrednost novih individua.
    4. Zameni najmanje fit populaciju sa novim individuama.

Vrste evolucijskih algoritama[uredi | uredi izvor]

Slične tehnike se razlikuju u detaljima implementacije i prirodi određenih problema.

  • Genetički algoritam - Ovo je najpopularniji tip EA. Traži rešenje u vidu niske brojeva (obično binarnih, iako je najbolje da se predstave tako da odražavaju nešto o rešenju problema), primenom operatora kao sto su rekombinacija i mutacija (nekada jedan, nekada oba). Ova vrsta EA se najčešće koriste u problemima optimizacije.
  • Genetičko programiranje - Ovde su rešenja predstavljena kompjuterskim programima, a njihov fitnes je određen njihovom sposobnosti da reše neki problem.
  • Evolucijsko programiranje - Slično genetičkom programiranju, samo što je struktura problema fiksna i njeni numerički parametri mogu da evoluiraju.
  • Genetsko ekspresiono programiranje - Kao i genetičko programiranje, kod GEPa se takođe razvija kompjuterski program ali on istražuje genotip-fenotip sistem, gde su programi različitih veličina kodirani linearnim hromozomima fiksne dužine.
  • Evoluciona strategija - Radi sa vektorima realnih brojeva kao reprezentacije rešenja, i obično koristi samo-prilagodivu brzinu mutacije.
  • Diferencijalna evolucija - Zasnovana na vektoru razlika i zbog toga se uglavnom koristi za probleme numeričke optimizacije.
  • Neuroevolucija - Slično genetičkom programiranju s tim što su genomi reprezentacija neuralnih mreža opisujući strukturu i težinu konekcije. Kodiranje genoma može biti direktno ili indirektno.
  • Sistemi za klasifikaciju učenja - Ovde su rešenja klasifikacije (pravila ili uslovi). Mičigen-LCS radi sa pojedinačnim klasifikatorima dok Pitsburg-LCS koristi setove klasifikatora populacije. Prvobitno, klasifikatori su bili samo binarni, ali sada sadrže pravu, neuronsku mrežu ili S-izraz. Fitnes je određen snagom ili tačnošću zasnovanom na pojačanom učenju.

Povezane tehnike[uredi | uredi izvor]

Tehnike roja, uključujući:

  • Optimizaciju mravlje kolonije - Zasnovane na ideji mrava koji traže put između svoje kolonije i izvora hrane. Primarno se koristi za kombinatorne optimizacije i probleme grafova.
  • Algoritam korena je inspirisan ulogom korena biljaka u prirodi.[6]
  • Algoritam kolonije pčela - Zasnovan na ponašanju pčela u potrazi za hranom. Primarno predložen za numeričke optimizacije a kasnije proširen da rešava kombinatorne probleme, ograničene probleme i probleme sa više ciljeva.
  • Pčelinji algoritam - takođe zasnovan na ponašanju pčela u potrazi za hranom. Koristi se za probleme rutiranja i raspoređivanja aktivnosti.
  • Algoritam kukavice - zasnovan na parazitizmu kukavica. Koristi Levijeve letove, i zbog toga je dobar za globalne probleme optimizacije.
  • Algoritam Roj čestica - Zasnovan ponašanju životinja u krdima. Takođe se primarno koristi za probleme numeričke optimizacije.

Druge metaheurističke metode zasnovane na populaciji[uredi | uredi izvor]

  • Prilagodljiva dimenzionalna pretraga - Algoritam prolagodljive dimenzionalne pretrage se razlikuje od metaheurističkih tehnika zasnovanih na prirodi u smislu da ne koristi bilo koju metaforu kao osnovni princip za njegovo sprovođenje. Umesto toga koristi jednostavnu metodologiju zasnovanu na ažuriranju koeficijenta dimenzionalne pretrage (KDP) u svakoj iteraciji.[7]
  • Algoritam Svitac - inspirisan ponašanjem svitaca, koji se privlače međusobno trepćućim svetlom. Ovo je posebno korisno za multimodalnu optimizaciju.
  • Harmonija pretraga - Zasnovana na ideji ponašanja muzičara u potrazi za boljom harmonijom. Ovaj algoritam je pogodan za kombinatorne optimizaije i optimizacije parametara.
  • Gausova adaptacija - Zasnovana na teoriji informacija, adaptivnoj vrednošću i entropiji. Koristi se za maksimizaciju prinosa za proizvodnju. Na primer, pogledati entropiju u termodinamici i teoriji informacija.
  • Memetički algoritam - Hibridna forma metoda zasnovanih na populaciji. Inspirisan Dokinsovim pojmom mema, obično ima oblik algoritma zasnovanog na populaciji uparen sa pojedinačnim postupcima učenja sposobnim za obavljanje lokalnih preciziranja. Naglšava eksploataciju znanja specifičnih za problem, i pokušava da organizuje lokalnu i globalnu pretragu na sinergičan način.

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ Carlos M. Fonseca (1995). „An Overview of Evolutionary Algorithms in Multiobjective Optimization”. Evolutionary Computation. 3 (1): 1—16. doi:10.1162/evco.1995.3.1.1. 
  2. ^ 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.
  3. ^ Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. "Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding" Arhivirano na sajtu Wayback Machine (3. јун 2016). Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009. Trondheim, Norway.
  4. ^ 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. стр. 358–367, Springer, 2008.
  5. ^ Ferreira, C., 2001. Gene Expression Programming: A New Adaptive Algorithm for Solving Problems. Complex Systems, Vol. 13, issue 2: 87-129.
  6. ^ 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. стр. 292–303, 2015
  7. ^ Hasançebi, O., Kazemzadeh Azad, S. (2015), Adaptive Dimensional Search: A New Metaheuristic Algorithm for Discrete Truss Sizing Optimization, Computers and Structures, 154, 1-16.

Литература[uredi | uredi izvor]

  • Ashlock, D. , Evolutionary Computation for Modeling and Optimization, Springer, . 2006. ISBN 978-0-387-22196-0.
  • Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press.
  • Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation, Oxford University Press.
  • Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetic Programming - An Introduction, Morgan Kaufmann, San Francisco
  • Eiben, A.E., Smith, J.E. (2003), Introduction to Evolutionary Computing, Springer.
  • Holland, J. H. (1975), Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor
  • Michalewicz Z., Fogel D.B. (2004). How To Solve It: Modern Heuristics, Springer.
  • Benkő A., Dósa G., Tuza Z. (2010), Bin Packing/Covering with Delivery, Solved with the Evolution of Algorithms, Proc. 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA (2010). str. 298-302.
  • Poli, R., Langdon, W. B., McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4.
  • Price, K., Storn, R.M., Lampinen, J.A., (2005). "Differential Evolution: A Practical Approach to Global Optimization", Springer.
  • Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
  • Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
  • Simon, D. (2013): Evolutionary Optimization Algorithms Arhivirano na sajtu Wayback Machine (10. март 2014), Wiley.
  • Computational Intelligence: A Methodological Introduction by Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, Springer, . 2013. ISBN 9781447150121.


Evolucioni algoritam na Vikimedijinoj ostavi.
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Еволуциони_алгоритам&oldid=27673561”