Algoritmo ebolutibo

Algoritmo ebolutiboak eboluzio biologikoaren postulatuetan oinarritutako konponbide-bilaketa eta optimizazio metodoak dira. Hau da, algoritmo ebolutibo batek eboluzio biologikoan inspiratutako mekanismoak erabiltzen ditu; hala nola, ugalketa, mutazioa, birkonbinazioa eta hautespena.[1] Algoritmo ebolutiboetan konponbide posibleak irudikatzen dituzten erakunde multzoak mantentzen dira, eta ondoren horiek nahastu eta elkarren artean lehiatu egiten dira. Horrela, egokienak direnak denboran zehar gailentzeko gai dira eta gero eta konponbide hobeetarantz eboluzionatuko dute. Beraz, populazioaren bilakaera aipatutako eragileak behin eta berriz aplikatu ondoren gertatzen da.

Algoritmo ebolutiboa eta konputazio ebolutiboa adimen artifizialaren adar bat dira. Batez ere, espazio bilaketa zabalak eta ez-linealak dituzten arazoetan erabiltzen dira, gai direlako irtenbideak arrazoizko denbora batean aurkitzeko, eta beste metodo batzuk, ordea, ez.

Algoritmo ebolutiboek, askotan, konponbide egokiak ematen dituzte arazo mota guztietara hurbiltzeko, idealki ez dutelako hipotesirik egiten sakoneko egoerari buruz.[2] Eboluzio biologikoaren modelora aplikatutako algoritmo ebolutiboetatik datozen teknikak prozesu mikroebolutiboen esplorazioetara eta zelula-prozesuetan oinarritutako planifikazio-ereduetara mugatzen dira. Algoritmo ebolutiboaren aplikazio erreal gehienetan, konplexutasun konputazionala faktore debekatzailea da. Izan ere, konplexutasun konputazional hori gaitasun funtzioaren ebaluazioari zor zaio. Zailtasun hau gainditzeko irtenbideetako bat, gaitasun hurbilketa da. Hala ere, itxuraz erraza den algoritmo ebolutiboak arazo konplexuak konpon ditzake; beraz, baliteke algoritmoaren konplexutasunaren eta arazoaren konplexutasunaren artean lotura zuzenik ez egotea.[3][4][5]

Inplementazioa

[aldatu | aldatu iturburu kodea]

Ondorengoa algoritmo genetiko generiko baten adibidea da.

Lehenengo urratsa: Banakoen hasierako populazioa ausaz sortzea. (Lehen belaunaldia)

Bigarren urratsa: Birsorkuntza urrats hauek errepikatzea amaierara arte.

  1. Biztanle bakoitzaren gaitasunaren ebaluazioa egitea: denbora-muga, lortutako gaitasun nahikoa, etab.
  2. Ugalketarako egokienak diren banakoen hautapena egitea. (Gurasoak)
  3. Birkonbinazio edo gurutzaketa-eragiketen bidez eta baita mutazio-eragiketen bidez ere, banako berriak haztea ondorengoak sortu ahal izateko.

Motak

[aldatu | aldatu iturburu kodea]

Antzekoak diren teknikak, aldiz, desberdinak izan ahal dira irudikapen genetikoan eta inplementazioko beste xehetasun batzuetan.

  • Algoritmo genetikoa: Algoritmo ebolutibo mota ezagunena da. Hauetan, problema baten konponbidea zenbaki-kate moduan bilatzen da,[2] birkonbinazioa eta mutazioa bezalako eragileak aplikatuz; batzuetan eragile bakarra erabiltzen da eta beste batzuetan biak. Algoritmo ebolutibo mota hau optimizazio-arazoetan erabili ohi da.
  • Programazio genetikoa: Konponbideak programa informatikoen formakoak dira eta hauen egokitasuna arazo konputazional bat konpontzeko duten gaitasunaren araberakoa da. Programazio genetikoaren hainbat aldaera daude, hauek dira adibide batzuk: programazio genetiko kartesiarra, programazio genetiko lineala, geneen adierazpenen programazioa, eboluzio gramatikala, adierazpen anitzeko programazioa eta abar.
  • Programazio ebolutiboa: Programazio genetikoaren antzekoa da, baina kasu honetan, programaren egitura finkoa da eta bere parametro numerikoek eboluzionatzeko aukera ematen dute.
  • Estrategia ebolutiboa: Zenbaki errealen bektoreekin lan egiten du konponbideen irudikapen gisa, eta normalean mutazio-tasa automoldagarriak erabiltzen ditu. Metodo hau gehien bat zenbakizko optimizaziorako erabiltzen da; baina, badaude konbinazio zereginetarako aldaera batzuk ere.[6][7]
  • Eboluzio diferentziala: Bektore-diferentzietan oinarritua eta, beraz, zenbakizko optimizazio arazoetarako egokia.
  • Algoritmo koebolutiboa: Algoritmo genetikoen eta estrategia ebolutiboen antzekoa da, baina sortutako konponbideak alderatu egiten dira beste konponbide batzuekin duten interakzioen emaitzen arabera. Bilaketa prozesuan zehar, konponbideek elkarrekin lan egin dezakete edo elkarren artean lehia daitezke. Algoritmo koebolutiboak askotan erabiltzen dira egoera dinamikoa, konplexua edo lehiakorra eskatzen denean.[8][9]

Oinarri teorikoak

[aldatu | aldatu iturburu kodea]

Hurrengo oinarri teorikoak algoritmo ebolutibo guztiei edo ia guztiei aplikatzen zaizkie.

No free lunch teorema

[aldatu | aldatu iturburu kodea]

Optimizazioaren No Free Lunch (NFL) teoremak dio optimizazio-estrategia guztiak eraginkorrak direla optimizazio-arazo guztiak kontuan hartzen direnean. Egoera berean, ez dago algoritmo ebolutiborik funtsean beste bat baino hobea denik; hau bakarrik gerta daiteke arazo guztien multzoa mugatuta dagoenean, hau da, praktikan ezinbestean egiten dena, hain zuzen ere. Beraz, algoritmo ebolutibo bat hobetzeko, nolabait, ezagutza problematikoa ustiatu behar da. Horrela, bi algoritmo ebolutibo alderatzen badira, murrizketa hori inplizitua da. Gainera, algoritmo ebolutibo batek arazoaren ezagutza espezifikoa erabil dezake.[10][11]

Konbergentzia

[aldatu | aldatu iturburu kodea]

Algoritmo ebolutiborako, ondorengoez gain, ondorengo belaunaldia osatzeko gutxienez gurasoen belaunaldiko banakorik onena erabiltzen duten algoritmo ebolutiboen kasuan, konbergentziaren froga orokor bat dago optimo bat izateko baldintzarekin.[12]

Alfabeto birtuala

[aldatu | aldatu iturburu kodea]

Alfabeto birtualen teoriarekin, 1990ean David E. Goldbergek frogatu zuen zenbaki errealak dituen irudikapen edo adierazle bat erabiliz, birkonbinazio-eragile klasikoak erabiltzen dituen algoritmo ebolutibo bat ezin dela iritsi bilaketa-gunearen zenbait eremutara, zenbaki bitarrekin egindako kodifikazioarekin kontrajarriz.[13] Horren ondorioz, irudikapen edo adierazle erreala duten algoritmo ebolutiboek birkonbinaziorako eragile aritmetikoak erabiltzea gomendatzen da. Eragile egokiekin, irudikapen edo adierazle errealak bitarrak baino eraginkorragoak dira.[14][15]

Aplikazioak

[aldatu | aldatu iturburu kodea]

Algoritmo ebolutiboak hainbat arlotan aplika edo erabil daitezke,[5] esaterako: Industrian,[16][17] ingeniaritzan,[2][3][18] programazio konplexuetan,[4][19][20] nekazaritzan,[21] finantzetan,[22][23] ikerketa-jardueretan,[24][25] baita artean ere. Algoritmo ebolutibo bat aplikatzeko, esperientziarik gabeko erabiltzaileak nolabaiteko birplanteamendua egin behar du. Izan ere, zeregin baten planteamenduan algoritmo ebolutibo bat erabiltzea desberdina da metodo zehatz konbentzionalekin alderatuz eta hori ez da ingeniarien edo beste diziplinen ikasketa-planaren parte izaten.

Adibidez, egokitasunaren kalkuluak ez du bakarrik helburua formulatu behar, baizik eta bere bilakuntza-prozesua ere babestu behar du; hasierako kalitate-irizpideen ebaluazio hoberik ez dakarten hobekuntzak sarituz edo, adibidez, programazio-lan batean ahalik eta baliabide gehien erabiltzea saihestu behar bada, langileen hedapena edo energia-kontsumoa, ez da nahikoa gehieneko aprobetxamendua ebaluatzeko. Are gehiago, oraindik onargarria den maila baten beherapenen kopurua eta iraupena ere erregistratu beharko lirateke, benetako gehieneko balioaren azpitik dauden murrizketak saritzeko.[26]

Iruditegia

[aldatu | aldatu iturburu kodea]

[27][28]

A two-population EA search over a constrained Rosenbrock function with bounded global optimum
Bi populazioko algoritmo ebolutibo bilaketa Rosenbrocken funtzio mugatu baten gainean mugatutako optimo globalarekin.
Estimation of distribution algorithm over Keane's function
Keaneren funtzioaren gaineko banaketa-algoritmoaren estimazioa.

Erreferentziak

[aldatu | aldatu iturburu kodea]
  1. ↑ Vikhar, Pradnya A.. (2016-12). Evolutionary algorithms: A critical review and its future prospects. IEEE, 261–265 or.  doi:10.1109/ICGTSPICC.2016.7955308. ISBN 978-1-5090-0467-6. (kontsulta data: 2023-12-03).
  2. ↑ a b c Ghosh, Ashish, ed. (2003). Advances in evolutionary computing: theory and applications ; with 111 tables. Springer ISBN 978-3-540-43330-9. (kontsulta data: 2023-12-03).
  3. ↑ a b (Ingelesez) Slowik, Adam; Kwasnicka, Halina. (2020-08). «Evolutionary algorithms and their applications to engineering problems» Neural Computing and Applications 32 (16): 12363–12379.  doi:10.1007/s00521-020-04832-8. ISSN 0941-0643. (kontsulta data: 2023-12-03).
  4. ↑ a b (Ingelesez) Mika, Marek; Waligóra, Grzegorz; Węglarz, Jan. (2011-06). «Modelling and solving grid resource allocation problem with network resources for workflow applications» Journal of Scheduling 14 (3): 291–306.  doi:10.1007/s10951-009-0158-0. ISSN 1094-6136. (kontsulta data: 2023-12-03).
  5. ↑ a b «Proceedings of IEEE International Conference on Evolutionary Computation» Proceedings of IEEE International Conference on Evolutionary Computation (IEEE) 1996  doi:10.1109/icec.1996.542326. (kontsulta data: 2023-12-03).
  6. ↑ Nissen, Volker; Krause, Matthias. (1994). Reusch, Bernd ed. «Constrained Combinatorial Optimization with an Evolution Strategy» Fuzzy Logik (Springer Berlin Heidelberg): 33–40.  doi:10.1007/978-3-642-79386-8_5, isbn 978-3-642-79386-8. ISBN 978-3-540-58649-4. (kontsulta data: 2023-12-03).
  7. ↑ (Ingelesez) Coelho, V. N.; Coelho, I. M.; Souza, M. J. F.; Oliveira, T. A.; Cota, L. P.; Haddad, M. N.; Mladenovic, N.; Silva, R. C. P. et al.. (2016-12). «Hybrid Self-Adaptive Evolution Strategies Guided by Neighborhood Structures for Combinatorial Optimization Problems» Evolutionary Computation 24 (4): 637–666.  doi:10.1162/EVCO_a_00187. ISSN 1063-6560. (kontsulta data: 2023-12-03).
  8. ↑ Ma, Xiaoliang; Li, Xiaodong; Zhang, Qingfu; Tang, Ke; Liang, Zhengping; Xie, Weixin; Zhu, Zexuan. (2019-06). «A Survey on Cooperative Co-Evolutionary Algorithms» IEEE Transactions on Evolutionary Computation 23 (3): 421–441.  doi:10.1109/TEVC.2018.2868770. ISSN 1089-778X. (kontsulta data: 2023-12-03).
  9. ↑ (Ingelesez) Popovici, Elena; Bucci, Anthony; Wiegand, R. Paul; De Jong, Edwin D.. (2012). Rozenberg, Grzegorz ed. «Coevolutionary Principles» Handbook of Natural Computing (Springer Berlin Heidelberg): 987–1033.  doi:10.1007/978-3-540-92910-9_31. isbn 978-3-540-92910-9.. ISBN 978-3-540-92909-3. (kontsulta data: 2023-12-03).
  10. ↑ Davis, Lawrence, ed. (1991). Handbook of genetic algorithms. (2. [print.]. argitaraldia) Van Nostrand Reinhold ISBN 978-0-442-00173-5. (kontsulta data: 2023-12-03).
  11. ↑ Lienig, Jens; Brandt, Holger. (1994). Davidor, Yuval ed. «An evolutionary algorithm for the routing of multi-chip modules» Parallel Problem Solving from Nature — PPSN III (Springer Berlin Heidelberg) 866: 588–597.  doi:10.1007/3-540-58484-6_301, isbn 978-3-540-58484-1, retrieved 2022-10-18. ISBN 978-3-540-58484-1. (kontsulta data: 2023-12-03).
  12. ↑ Yee Leung; Yong Gao; Zong-Ben Xu. (1997-09). «Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis» IEEE Transactions on Neural Networks 8 (5): 1165–1176.  doi:10.1109/72.623217. ISSN 1045-9227. (kontsulta data: 2023-12-03).
  13. ↑ (Ingelesez) Goldberg, David E.. (1991). Schwefel, Hans-Paul ed. «The theory of virtual alphabets» Parallel Problem Solving from Nature (Springer-Verlag) 496: 13–22.  doi:10.1007/bfb0029726, isbn 978-3-540-54148-6, retrieved 2022-10-22. ISBN 978-3-540-54148-6. (kontsulta data: 2023-12-03).
  14. ↑ Stender, Joachim, ed. (1994). Genetic algorithms in optimisation, simulation, modelling. IOS Press [u.a.] ISBN 978-90-5199-180-2. (kontsulta data: 2023-12-03).
  15. ↑ Michalewicz, Zbigniew. (1996). Genetic Algorithms + Data Structures = Evolution Programs.  doi:10.1007/978-3-662-03315-9. (kontsulta data: 2023-12-03).
  16. ↑ Sanchez, Ernesto; Squillero, Giovanni; Tonda, Alberto. (2012). Industrial Applications of Evolutionary Algorithms. Springer Berlin Heidelberg  doi:10.1007/978-3-642-27467-1. ISBN 978-3-642-27466-4. (kontsulta data: 2023-12-03).
  17. ↑ «Evolutionary algorithms in engineering and computer science: Recent advances in genetic algorithms, evolution strategies, evolutionary programming, genetic programming and industrial applications» Computers & Mathematics with Applications 38 (11-12): 282. 1999-12  doi:10.1016/s0898-1221(99)91189-6. ISSN 0898-1221. (kontsulta data: 2023-12-03).
  18. ↑ (Ingelesez) Gen, Mitsuo; Cheng, Runwei. (1999-12-17). Genetic Algorithms and Engineering Optimization. (1. argitaraldia) Wiley  doi:10.1002/9780470172261. ISBN 978-0-471-31531-5. (kontsulta data: 2023-12-03).
  19. ↑ Dahal, Keshav P., ed. (2007). Evolutionary Scheduling. Springer Berlin Heidelberg  doi:10.1007/978-3-540-48584-1. isbn 978-3-540-48584-1. oclc 184984689. ISBN 978-3-540-48582-7. (kontsulta data: 2023-12-03).
  20. ↑ (Ingelesez) Jakob, Wilfried; Strack, Sylvia; Quinte, Alexander; Bengel, Günther; Stucky, Karl-Uwe; Süß, Wolfgang. (2013-04-22). «Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing» Algorithms 6 (2): 245–277.  doi:10.3390/a6020245. ISSN 1999-4893. (kontsulta data: 2023-12-03).
  21. ↑ Mayer, David G.. (2002). Evolutionary Algorithms and Agricultural Systems. Springer US  doi:10.1007/978-1-4615-1717-7. isbn 978-1-4613-5693-6.. ISBN 978-1-4613-5693-6. (kontsulta data: 2023-12-03).
  22. ↑ Aranha, Claus; Iba, Hitoshi. (2008). Wobcke, Wayne ed. «Application of a Memetic Algorithm to the Portfolio Optimization Problem» AI 2008: Advances in Artificial Intelligence (Springer Berlin Heidelberg) 5360: 512–521.  doi:10.1007/978-3-540-89378-3_52, isbn 978-3-540-89377-6, retrieved 2022-12-23. ISBN 978-3-540-89377-6. (kontsulta data: 2023-12-03).
  23. ↑ Chen, Shu-Heng, ed. (2002). Evolutionary Computation in Economics and Finance. Physica-Verlag HD  doi:10.1007/978-3-7908-1784-3. isbn 978-3-7908-2512-1.. ISBN 978-3-7908-2512-1. (kontsulta data: 2023-12-03).
  24. ↑ «Evolutionary design of an X-band antenna for NASA's Space Technology 5 mission | IEEE Conference Publication | IEEE Xplore» ieeexplore.ieee.org  doi:10.1109/aps.2004.1331834. (kontsulta data: 2023-12-03).
  25. ↑ (Ingelesez) Evolutionary Computation in Bioinformatics. Elsevier 2003  doi:10.1016/b978-1-55860-797-2.x5000-8. isbn 978-1-55860-797-2.. ISBN 978-1-55860-797-2. (kontsulta data: 2023-12-03).
  26. ↑ (Ingelesez) Jakob, Wilfried. (2021). Applying Evolutionary Algorithms Successfully: A Guide Gained from Real-world Applications.  doi:10.5445/ir/1000135763, s2cid 236318422, retrieved 2022-12-23. (kontsulta data: 2023-12-03).
  27. ↑ Simionescu, P.A.; Dozier, G.V.; Wainwright, R.L.. (2006). A Two-Population Evolutionary Algorithm for Constrained Optimization Problems. IEEE, 1647–1653 or.  doi:10.1109/CEC.2006.1688506. ISBN 978-0-7803-9487-2. (kontsulta data: 2023-12-03).
  28. ↑ Simionescu, P.A.; Dozier, G.V.; Wainwright, R.L.. (2006). A Two-Population Evolutionary Algorithm for Constrained Optimization Problems. IEEE, 1647–1653 or.  doi:10.1109/CEC.2006.1688506. ISBN 978-0-7803-9487-2. (kontsulta data: 2023-12-03).

Ikus, gainera

[aldatu | aldatu iturburu kodea]

Kanpo estekak

[aldatu | aldatu iturburu kodea]