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. 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. 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.      

 Inplementazioa 
Ondorengoa algoritmo genetiko generiko baten adibidea da.

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

Bigarren urratsa: Birsorkuntza urrats hauek errepikatzea amaierara arte.

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

 Motak 
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, 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.
 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.

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

 No free lunch teorema 
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.
 Konbergentzia 
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.

 Alfabeto birtuala 
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. 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.

 Aplikazioak 
Algoritmo ebolutiboak hainbat arlotan aplika edo erabil daitezke, esaterako: Industrian, ingeniaritzan, programazio konplexuetan, nekazaritzan, finantzetan, ikerketa-jardueretan, 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.

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

 Erreferentziak 

 Ikus, gainera 
 Algoritmo

 Kanpo estekak 
Algoritmo ebolutiboen historiaren eta zaporeen ikuspegi orokorra.
Scholarpediako algoritmo ebolutiboei buruzko artikulua.
Konputazio ebolutiboko algoritmo baten adibidea.

Kategoria: Algoritmoak
Kategoria:Konputazio ebolutiboa
Kategoria:Zibernetika