Algoritmo genetiko

Informatika eta ikerketa operatiboan algoritmo genetiko bat algoritmo ebolutiboen klase handienari dagokion hautespen naturalaren prozesuan inspiratutako metaheuristiko bat da. Algoritmo genetikoak, oro har, kalitate handiko soluzioak sortzeko erabiltzen dira optimizazio eta bilaketa-problemetan. Hori lortzeko, biologian inspiratutako eragileak erabiltzen dituzte, hala nola mutazioa, gurutzaketa eta hautaketa. Aplikazioen adibide batzuk dira, besteak beste, erabaki-zuhaitzak optimizatzea errendimendua hobetzeko, sudoku puzzleak ebaztea, hiperparametroen optimizazioa, eta abar.

Metodologia

Optimizazio problemak

Algoritmo genetiko batean, optimizazio problema baten erantzun hautagaien populazio bat erantzun hobeagoetarantz eboluzionatzen da. Soluzio hautagarri bakoitzak propietate multzo bat du (kromosomak edo genotipoak) zeinak aldatu eta mutatu daitezke. Tradizionalki, soluzioak bitarrean errepresentatzen dira, 0 eta 1eko segidetan, baina beste kodetze batzuk ere posible dira.

Eboluzioa normalean ausaz sortutako banakoen populazio batetik abiarazten da. Prozesu iteratiboa da, non iterazio bakoitzeko populazioari belaunaldi deritzon. Belaunaldi bakoitzean, populazioko banako bakoitzaren egokitasuna ebaluatzen da. Egokitasuna, normalean, ebazten ari den problemaren helburu-funtzioaren balioa da. Banako egokienak oraingo populaziotik estokastikoki hautatuak dira, eta banako bakoitzaren genoma aldatzen (birkonbinatuta eta behar bada, mutatuta) da, belaunaldi berri bat sortzeko. Soluzio hautagaien belaunaldi berria algoritmoaren hurrengo iterazioan erabiltzen da. Orokorrean, algoritmoa amaitzen da belaunaldi kopuru maximo bat sortu denean edo populazioarentzako egokitasun maila egokia lortu denean.

Algoritmo genetiko tipiko batek hau behar du:

1.     Soluzio espazioaren errepresentazio genetiko bat,

2.     Egokitasun funtzio bat soluzio espazioa ebaluatzeko.

Soluzio hautagaiak errepresentatzeko era estandarra biten arraya da. Errepresentazio genetiko hauek erabilerrazak egiten dituen propietate nagusia da beraien atalak erraz lerrokatzen direla, tamaina finkoa baitute. Horrek gurutzaketa operazioak egitea errazten du. Tamaina aldakorra duten errepresentazioak ere erabili daitezke, baina gurutzaketaren inplementazioa konplexuagoa da hauekin. Zuhaitz motako errepresentazioak programazio genetikoan esploratzen dira eta programazio ebolutiboan grafo motakoak.

Behin errepresentazio genetikoa eta egokitasun funtzioa definituta, algoritmo genetiko batek populazio bat abiarazten du eta, ondoren, hura hobetzen du mutazio, gurutzaketa, inbertsio eta aukeraketa/hautapen operadoreen aplikazio errepikakorraren bidez.

Hasieraketa

Biztanleriaren tamaina arazoaren izaeraren araberakoa da, baina normalean, ehunka edo milaka soluzio hasieratzen dira. Askotan hasierako populazioa ausaz aukeratzen da, soluzio guztien (bilaketa espazio) eremu osoan. Batzuetan, soluzioak hasieratu egiten dira erantzun optimoa lortzea probableagoa den zonaldeetan.

Aukeraketa

Belaunaldi bakoitzean uneko biztanleriaren zati bat belaunaldi berri bat sortzeko aukeratuak izaten dira. Hurrengo biztanleria sortzeko banakoen hautaketa helburu funtzio baten arabera egiten da, non helburu funtzioa gehiago hobetzen duten banakoek (soluzio onenak) probabilitate gehiago duten hautatuak izateko. Zenbait aukeraketa-metodok banako guztien egokitasuna neurtzen dute, helburu funtzioaren bidez, eta banako onenak aukeratzen dituzte. Beste metodo batzuk populazioaren ausazko lagin bat besterik ez dute ebaluatzen, aurreko prozesuak denbora asko behar izan baitezake.

Helburu funtzioa hautazko soluzioen kalitatea neurtzen du eta problemaren menpekoa da beti. Adibidez, Bizkar-zorroaren buruketan objektu guztien balioa maximizatu nahi da, gaitasun finkoko motxila batean jar daitezkeenak. Soluzio baten irudikapen bat bit zerrenda bat izan daiteke, non bit bakoitzak beste objektu bat irudikatzen duen, eta bit baten balioak (0 edo 1) adierazten du objektua motxilan dagoen ala ez. Horrelako irudikapen orok ez du balio, objektuen tamainak zorroaren gaitasuna gaindi baitezake. Soluzioaren egokitasuna objektu guztiek motxilan duten balioen batura da, bit zerrenda egokia bada, edo 0.

Problema batzuetan, zaila edo are ezinezkoa da helburu funtzioa definitzea. Kasu hauetan, simulazio bat erabil daiteke fototipo baten egokitasun-balioa zehazteko (adibidez, fluidoen dinamika konputazionala erabiltzen da forma fenotipo gisa kodetuta duen ibilgailu baten aire-erresistentzia zehazteko), edo algoritmo genetiko interaktiboak ere erabiltzen dira.

Eragile genetikoak

Hurrengo pausua aukeratutakoetatik hurrengo belaunaldiko populazioa sortzea da, operadore genetikoen konbinazio baten bidez: gurutzaketa eta mutazioa.

Soluzio berri bat sortzeko bi "guraso" soluzio aukeratzen dira, aurreko pausuko aukeratuak izan direnetatik. Soluzio berri honek, "haurra", lehen aipatutako metodoak erabilita: gurutzaketa eta mutazioa, normalean, bi gurasoen ezaugarri asko partekatuko ditu. Haur berri bakoitzeko guraso bikote berri bat aukeratzen da. Prozesu hau errepikatu egiten da tamaina aproposeko biztanleria berria lortu arte. Haurren sorkuntzan guraso bikote bat erabiltzea ugalketa metodoan du oinarri, baina, guraso bat baino gehiago erabili daitezke prozesu honetan ere.

Prozesu honen ondorioa hasierak biztanleriaren desberdina den populazio batean da. Eskuarki, populazioaren batez besteko egokitasuna areagotu egingo da prozesu honen bidez, lehen belaunaldiko soluziorik onenak bakarrik aukeratzen baitira eta baita soluzio ez hain onak. Soluzio ez hain onak sartzeak hurrengo belaunaldiaren aniztasun handiagoa bermatzen du.

Hainbat hiperparametroren doikuntza egitea merezi du lan egiten ari garen problemari egokitzeko, hala nola, mutazio-probabilitatea, gurutzaketa-probabilitatea eta biztanleria-tamaina. Gurutzaketa-tasa altuegiak algoritmo genetikoaren konbergentzia azkartu dezake. Mutazio tasa oso txikiak isurketa genetikoa ekar dezake eta altuegiak konponbide onak galtzea ekar dezake, hautespen elitista erabiltzen ez bada. Biztanleriaren tamaina egoki batek arazoaren aniztasun genetiko nahikoa bermatzen du, baina baliabide konputazional alferrik galtzea ekar dezake, behar baino balio handiagoa emanez gero.

Heuristikoak

Goiko eragileez gain, beste heuristiko batzuk erabil daitezke kalkuluak arinago edo sendoago egiteko.

Bukaera

Belaunaldi prozesu hau bukatze kondizio bat betetzen den arte errepikatzen da. Bukatze kondizio ohiko batzuk hauek dira:

• Soluzio bat aurkitu da irizpide minimoa betetzen duena.
• Finkatutako belaunaldi kopuru maximora ailegatu da.
• Gehieneko aurrekontura (konputazio denbora/dirua) iritsi da.
• Soluzio hoberenaren egokitasuna plateau batera iristen ari da edo iritsi da eta hurrengo iterazioek ez dute emaitza hobeak lortuko.
• Eskuzko ikuskapena.
• Goikoen konbinazioak.

Historia

1950. urtean, Alan Turingek “ikasten duen makina” proposatu zuen, eboluzioaren printzipioekin paraleloa izango zena. Eboluzioaren ordenagailu bidezko simulazioa 1954an hasi zen, Nils Aall Barricelliren lanarekin, zeinak Institute for Advanced Study-n ordenagailua erabiltzen zuen Princetonen. Bere 1954ko argitalpena ez zen asko nabaritu. 1957tik aurrera, Alex Fraser Australiar genetistak loci anitzeko organismoen hautaketa artifizialaren simulazioari buruzko artikulu batzuk argitaratu zituen, ezaugarri neurgarri bat kontrolatuz. Hasiera horietatik aurrera, biologoen eboluzioaren ordenagailu bidezko simulazioa ohikoagoa egin zen 1960ko hasieran, eta metodoak Fraser eta Burnell (1970) eta Crosby (1973) liburuetan deskribatu ziren. Fraserren simulazioek algoritmo genetiko modernoen funtsezko elementu guztiak biltzen zituzten. Gainera, Hans-Joachim Bremermannek hainbat artikulu argitaratu zituen hirurogeiko hamarkadan, eta horiek ere optimizazio-arazoak konpontzeko, soluzioen populazioak erabiltzen zituzten, birkonbinazio, mutazio eta hautaketaren mende zeudenak. Bremermannen ikerketak algoritmo genetiko modernoen elementuak ere barne hartu zituen. Beste aitzindari nabarmenenak Richard Friedberg, George Friedman eta Michael Conrad dira. Lehenengo artikulu asko Fogelek (1988) berrinprimatu ditu.

Barricellik 1963an kontatu(report) zuen lanean joko sinple bat jokatzeko gaitasunaren eboluzioa simulatu zuen arren, eboluzio artifiziala ez zen oso ezaguna bihurtu Ingo Rechenberg eta Hans-Paul Schwefelen 1960ko hamarkadan eta 1970eko hasieran egin zuten lana arte. Rechenbergen taldea gai izan zen eboluzio-estrategien bidez ingeniaritzako arazo konplexuak konpontzeko. Beste ikuspegi bat Lawrence J. Fogelen programazio ebolutiboko teknika izan zen, adimen artifiziala sortzeko proposatu zena. Programazio ebolutiboak, hasiera batean, egoera finituko makinak erabiltzen zituen inguruneak iragartzeko, eta bariazioa eta hautaketa erabiltzen zituen logika prediktiboak optimizatzeko. Algoritmo genetikoak, bereziki, ezagun egin ziren John Henry Hollandek hirurogeita hamarreko hamarkadaren hasieran egindako lanaren bidez, eta bereziki Adaptation in Natural and Artificial Systems (1975) liburuaren bidez. Bere lana automata zelularren ikasketekin hasi zen, Hollandek eta bere Michigango Unibertsitateko ikasleek gidatuta. Hollandek hurrengo belaunaldiaren kalitatea iragartzeko egitura formalizatu bat sortu zuen, Hollanden eskema teorema bezala ezagutzen dena. 80ko hamarkadaren erdialdean, Algoritmo Genetikoei buruzko Nazioarteko Konferentzia lehen aldiz antolatu zen, Pittsburghen (Pennsylvania).

Mugak

Besteak beste, honako hauek aipa ditzakegu:

• Konplexutasun handiko problemetarako, ebaluazio-funtzioa garestiegia izan daiteke denborari eta baliabideei dagokienez. Adibidez, badira zenbait kasu bizitza errealean iterazio batek proposatutako soluzioaren simulazio bat birsortzeko egun asko behar izan daitezkeenak eta prozesamendu eta lotutako baliabide asko kontsumitu ditzaketenak.
• Kasu batzuetan, ebaluaziorako erabiltzen diren parametroen arabera, algoritmoa ez da soluzio optimo batera iritsiko, edo konbergentzia goiztiar batera iritsiko litzateke, emaitza ez-egokiekin (konbergentzia goiztiarrak esan nahi du konbergentzia optimo lokal batean edo puntu arbitrario batean egiten duela, epe luzeko emaitzei eraginez).
• Ez dute eskalagarritasun ona konplexutasunarekin; adibidez, aldagai, osagai edo elementu askok osatutako sistemetan, haien bilaketa-espazioa modu esponentzialean hazten da, besteak beste, sor daitezkeen erlazioengatik. Beraz, adibidez, aireontzi baten diseinuaren problema irudikapen sinpleetan banakatu behar da, profil aerodinamiko gisa, elementuen birkonbinazioak norbanakoaren errendimendua kaltetu dezakeela kontuan hartuta.
• Irtenbide "onena" beste irtenbide batzuekin alderatuta bakarrik da, eta, beraz, ez dago oso argi noiz gelditu behar den, ez baitago soluzio espezifikorik.
• Ez da gomendagarria Zuzena/Okerra bezalako soluzio sinpleak bilatzen dituzten problemetarako erabiltzea, algoritmoak nekez konbergituko baitu eta emaitza ausaz aukeratzea bezain baliagarria izango baita.
• Diseinuak, egokitasun-funtzioa sortzeak eta mutazio-irizpideak hautatzeak, besteak beste, nolabaiteko trebetasuna eta arazoaren ezagutza behar dute emaitza onak lortzeko.

Aplikazioak

• Diseinu automatizatua, materialen diseinuari eta automobilen osagaien helburu anitzeko diseinuari buruzko ikerketa barne: talken aurreko portaera hobea, pisua aurreztea, aerodinamika hobetzea, etab.
• Industria-ekipamenduaren diseinu automatizatua.
• Finantza-sektoreko merkataritza-sistemen diseinu automatizatua.
• Zuhaitz filogenetikoak eraikitzea.
• Edukiontzien karga optimizatzea.
• Urak banatzeko sistemen diseinua.
• Zirkuitu inprimatuen topologien diseinua.
• Sare konputazionalen topologien diseinua.
• Joko-teorian, orekak ebaztea.
• Geneen adierazpenaren analisia.
• Roboten portaera ikastea.
• Logika lausoko arauak ikastea.
• Hizkuntza-azterketa, gramatika-indukzioa barne, eta lengoaia naturalak prozesatzeko beste alderdi batzuk, hala nola zentzu-anbiguotasuna ezabatzea.
• Komunikazio-sare mugikorren azpiegitura.
• Egitura molekularrak optimizatzea.
• Irizpide anitzeko produkzioaren plangintza.
• Iragarpena.
• Algoritmo genetikoak aplikatzea preso iteratuaren dilemari.
• Datuak konprimitzeko sistemak optimizatzea, adibidez, waveletak erabiliz.
• Proteinen tolesturaren iragarpena.
• Sareak optimizatzea.
• RNAren egitura iragartzea.
• Bioinformatikan, sekuentzien lerrokatze anizkoitza.
• Aplikazioak prozesu industrialen plangintzan.
• Sistema biologikoak deskribatzeko eredu matematikoak ahalik eta hobeto hautatzeko.
• Hondakin solidoak maneiatzea.
• Software-ingeniaritza.
• Unibertsitate handietan ordutegiak eraikitzea, klase-gatazkak saihestuz.
• Bidaiariaren problema.
• Programetan akatsak aurkitzea.
• Energia elektrikoaren ekoizpena eta banaketa optimizatzea.
• Sare geodesikoen diseinua (diseinu-arazoak).
• Egitura zibiletan izandako kalteak kalibratzea eta detektatzea.
• Izar-sistema konplexuetako izar-populazioak kalkulatzea.

Bibliografia

• Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Genetic Programming - An Introduction. San Francisco, CA: Morgan Kaufmann. ISBN 978-1558605107.
• Carmona, Enrique; Fernández, Severino (2020). Fundamentos de la Computación Evolutiva. Marcombo. ISBN 978-8426727558.
• Eiben, Agoston; Smith, James (2003). Introduction to Evolutionary Computing. Springer. ISBN 978-3540401841.
• Fraser, Alex S. (1957). "Simulation of Genetic Systems by Automatic Digital Computers, I. Introduction." Australian Journal of Biological Sciences. 10: 484-491.
• Goldberg, David (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley Professional. ISBN 978-0201157673.
• Goldberg, David (2002). The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983.
• Fogel, David. Evolutionary Computation: Toward the New Philosophy of Machine Intelligence (3rd ed.). Piscataway, NJ: IEEE Press. ISBN 978-0471669517.
• Hingston, Philip; Barone, Luigi; Michalewicz, Zbigniew (2008). Design by Evolution: Advances in Evolutionary Design. Springer. ISBN 978-3540741091.
• Holland, John (1992). Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press. ISBN 978-0262581110.
• Koza, John (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press. ISBN 978-0262111706.
• Michalewicz, Zbigniew (1996). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag. ISBN 978-3540606765.
• Mitchell, Melanie (1996). An Introduction to Genetic Algorithms Cambridge, MA: MIT Press. ISBN 9780585030944.
• 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.
• Schmitt, Lothar M; Nehaniv, Chrystopher L; Fujii, Robert H (1998), Linear analysis of genetic algorithms, Theoretical Computer Science 208: 111-148
• Vose, Michael (1999). The Simple Genetic Algorithm: Foundations and Theory. Cambridge, MA: MIT Press. ISBN 978-0262220583.

Ikus, gainera

• Algoritmo ebolutibo
• Neurona-sare artifizial
• Adimen artifizial
• Algoritmo

Kanpo estekak

• Datuak: Q187787