Algoritmo genetikoak, soluzio egokienaren bila

Naturan, hasieran dagoen populazioa aldatzen joaten da denborarekin. Belaunaldiz belaunaldi, okerren moldatzen diren banakoak desagerrarazi egiten dituzte zenbait faktorek; ondo egokitzen direnak, aldiz, iraun egiten dute. Hortaz, populazioaren barruan, onenen proportzioa handitu egiten da. Hala ere, litekeena da itxuraz hain ona ez den baten batek ere irautea, bestelako estrategia bat duelako edo zoriz. Eta besteekin gurutzatu liteke, gainerako kideak elkarrekin gurutzatzen diren bezala. Horrenbestez, baliteke ustez txarra zen banakoaren ezaugarria hurrengo belaunaldian azaltzea, beste kide batzuetan.

Noizean behin, beste aldagai bat ere azaltzen da: mutazioa. Nahiz eta ez den oso maiz agertzen, eragina du populazioaren kideen ezaugarrietan. Gurutzaketen, mutazioen eta onenen alde egiten duten eragileen eraginez, denbora igarotzen denean, ingurura ondoen egokitutako kideek osatzen dute populazioa.

Hori azaldu zuen, gutxi gorabehera, Darwinek espezieen eboluzioaren teorian, eta horixe bera egiten dute algoritmo genetikoek. Hasierako populazioa problema batek izan ditzakeen ebazpenek osatzen dute. Ebazpen edo soluzio posible horiek ausaz aukeratzen dira, eta kromosoma deitzen zaie. Kromosoma bakoitzak dituen alderdi desberdinei, berriz, gene deitzen zaie.

Hautagaiak izanda gero, haien egokitasuna neurtzen duen funtzio bat aplikatzen zaie. Normala den bezala, hautagai gehienak desegokiak dira, baina beste batzuek, nola edo hala, funtzionatu egiten dute, eta iraun egiten dute.

Aurrera egin duten hautagaiak ugaldu egiten dira, eta elkarrekin gurutzatzen dira. Hortaz, hurrengo belaunaldian, batzuek hainbat kopia dituzte, eta beste batzuk nahastu egin dira. Gainera, gutxi batzuk ez dira aurrekoen berdin-berdinak: mutatu egin dira; hau da, generen bat aldatu egin zaie, ausaz.

Sortu den belaunaldia desberdina da aurrekoaren aldean, eta hautagai horien egokitasuna ere neurtzen da. Hala, aurrekoak baino hobeak ez diren hautagaiak baztertu egiten dira; gelditzen direnak hasierakoak baino soluzio hobeak dira. Haiek berriro ugaltzen dira, eta gurutzaketak gertatzen dira, eta baita mutazioak ere. Hautagai berriak ebaluatu, eta berriro onenak aukeratzen dira; prozesua behin eta berriro egiten da, ehun edo mila aldiz. Azkenean lortzen den populazioa problemaren soluzio oso onez osatuta dago.

Zenbakiak, letrak eta zuhaitzak

Algoritmo genetikoak lanean hasterako, problemaren ebazpen posibleak kodetu behar dira, ordenagailuak prozesatzeko modua izan dezan. Aukera bat kate bitarretan kodetzea da: 1ez eta 0z osatutako kateak dira, eta katearen leku bakoitzean dagoen digituak ebazpenaren aspektu baten balioa adierazten du.

Zenbaki osoen edo hamarrenen kateen bidezkoa da kodetzeko beste modu bat. Aurrekoan bezala, leku bakoitzean dagoen zenbakiak ebazpenaren alderdi jakin baten balioa adierazten du. Kode bitarrarekin baino zehaztasun eta konplexutasun handiagoa lortzen da, bi zenbaki erabiltzeak baino gutxiago mugatzen duelako. Bestalde, zenbakien ordez, letrak ere erabil daitezke hautagaiak kodetzeko.

Hiru metodo horiekin, oso erraza da hautagaien artean gurutzaketak eta mutazioak ausaz egingo dituzten eragiketak definitzea; erraza da 0 bat dagoen lekuan 1 bat jartzea, edo alderantziz; zenbaki bati balore bat gehitzea edo kentzea; edo letra baten lekuan beste bat jartzea.

Horiez gain, kodetzeko beste era batzuk ere badaude, hala nola zuhaitzen bidez egiten dena. Datuak adarkatuta irudikatzen dira, eta aldaketak adabegien balorea aldatuz egiten dira, edo zuhaitzaren adar batzuk beste batzuekin ordezkatuz.

Hautaketa eta aldaketa

Era batera zein bestera kodetu, hurrengo belaunaldirako kopiatu behar diren banakoak nola aukeratu programatu behar da. Hautespena era askotara egin daiteke, eta, normalean, era bat baino gehiago erabiltzen dira batera. Horietako bat hautespen elitista da; alegia, belaunaldi bakoitzeko onenak hautatzea da. Beste modu bat gaitasunaren araberakoa da: zenbat eta gaitasun handiagoa izan, orduan eta aukera gehiago hautatua izateko.

Horiez gain, populazioaren dibertsitatea bermatzeko, erruleta-gurpila erabil daiteke: hautagai bakoitzari erruletaren zati bat dagokio; zenbat eta gaitasun handiagoa izan, orduan eta zati handiagoa egokitzen zaio hautagaiari. Gurpila biratuta, zati handia dutenek hautatuak izateko aukera handiagoa dute, baina gerta liteke gaitasun eskasa duen hautagai bati egokitzea hurrengo belaunaldirako aukeratua izatea. Horri esker bermatzen da hurrengo belaunaldia berdinegia ez izatea.

Hori bermatzeko beste modu bat da gaitasun-mailaren araberako taldeak egitea eta talde bakoitzeko onena aukeratzea; hartara, gaitasun txikia dutenen taldeko onenak aurrera egingo luke. Taldeak ausaz ere egin daitezke, eta gero elkarren artean lehiatzera behartu; txapelketan irabazle ateratzen direnak pasatzen dira hurrengo belaunaldira.

Hautatzeko beste metodo batzuk ere badaude: hautespen mailakatua, hierarkikoa... Edonola ere, hurrengo belaunaldiko hautagaiak batez beste aurrekoak baino hobeak izatea da helburua. Horrez gain, hurrengo belaunaldirako aukeratzen diren hautagaiei aldaketa batzuk egiten zaizkie ausaz, banako hobeak azalduko diren itxaropenarekin.

Aldaketak egiteko bi bide daude: mutazioa eta gurutzaketa. Alderdi jakin bat, gene bat, aldatzea da mutazioa. Gurutzaketa, berriz, kodearen zati bat beste hautagai batekin trukatzea da. Horrela sortzen den 'umeak' bi 'gurasoen' ezaugarriak ditu nahasian. Ugalketa sexualean aitaren eta amaren kromosomen artean gertatzen den errekonbinazioaren parekoa da, beraz.

Aldeko eta kontrako

Hautespena, mutazioa eta gurutzaketa erabilita, belaunaldiz belaunaldi, problemaren soluziora gerturatzen joaten dira algoritmo genetikoak. Kasu askotan, algoritmo genetikoa ez da nahikoa izango problema askatzeko, baina soluzio nahiko onak eman ditzake, eta, amaierako populazio horri ohiko metodoak aplikatuta, soluzio onena lor daiteke.

Algoritmo genetikoen abantailetako bat da 'itsuak' direla; hau da, ez dakitela ezer ebatzi behar duten problemaz. Beharbada, abantaila baino gehiago desabantaila dirudi, baina oso ona da, ez baitu hasieratik baztertzen itxura txarra duen hautagairik. Gainera, gurutzaketari eta mutazioari esker, soluzio harrigarriak sortzen dira. Nolabait esateko, aurreiritziek ez diete eragiten algoritmo genetikoei; aurrera egitea bakarrik axola zaie.

Horrez gain, paraleloan egiten dute lan; alegia, hainbat bidetatik jotzen dute aldi berean. Algoritmo gehienak seriean lan egiten dute, eta aldi bakoitzeko norabide batean bakarrik egin dezakete aurrera. Bide okerra hartu dutela konturatutakoan, lan guztia bertan behera utzi, eta berriro hasi behar dute. Algoritmo genetikoek, ordea, ez dute arazo hori, eta, gainera, bereziki eraginkorrak dira soluzio posible asko dituzten problemak ebazten.

Abantaila gehiago ere badituzte, baina baita eragozpen batzuk ere. Lehenengoa da zaila dela problemaren definizioa idaztea. Hautagaiak kodetzea ez da erraza, eta, batzuetan, asko kostatzen da gaitasuna neurtzen duen funtzioa idaztea. Populazioaren neurria, mutazioen eta gurutzaketen maiztasuna, eta hautespenaren mota eta indarra ere oso faktore garrantzitsuak dira algoritmo genetikoetan, eta, ez badira ondo diseinatzen, ez dute aurrera egiten.

Aplikazioak

Mugak dituzten arren, era askotako problemak ebazteko erabiltzen dira; besteak beste, akustikakoak, ingeniaritza aeroespazialekoak, astronomia eta astrofisikakoak, kimikakoak, finantza-merkatukoak, jokoetakoak, geofisikakoak, materialen ingeniaritzakoak, matematikakoak, biologia molekularrekoak, telekomunikazioetakoak...

Adibidez, 2002an Japoniako Kobe Unibertsitateko ikertzaileek algoritmo genetikoak erabili zituzten musika-areto bat diseinatzeko. Zapata-kaxa baten itxurako areto batetik abiatu ziren, eta, akustika onena lortzeko izan behar zituen parametroak definitu zituzten. Algoritmoak bi emaitza eman zituen, biak ere hosto-itxurakoak, eta biek ere akustika zoragarria dute nonbait. Ikertzaileen esanean, Vienako Grosser Musikvereinsaal-aren parekoak dira; munduko onenaren parekoak, beraz.

NASAk, berriz, ontziak diseinatzeko erabili ditu, baina baita nano zuriak aztertzeko eta ordutegiak diseinatzeko ere. Hain zuzen ere, ordutegiak egiteko oso eraginkorrak dira algoritmo genetikoak, enpresetan, aireportuetan zein eskoletan.

Eskoletan, esaterako, arazo handia izaten da ordutegi egokia egitea. Gela bakoitzeko irakasle bat behar da, eta irakasle batek ezin du bi gelatan egon aldi berean. Noski, irakasle bakoitzak bere gaia eman behar du, eta, agian, gai batzuk hobe da ordu batean ematea eta ez bestean (ez da komeni matematika, fisika eta halakoak azken orduan jartzea). Gainera, kontuan izan behar dira irakasleen nahiak edo beharrak ere. Hainbeste faktore izan behar direnez kontuan, zentro handietan izugarri zaila da ordutegia egiteko programa on bat lortzea. Bada, algoritmo genetikoak primerakoak dira horretarako.

Adituek ez dute zalantzarik: nahiko berriak diren arren (lehenengoak 1960ko hamarkadan azaldu ziren), garapen azkarra izan dute, eta, Mª Teresa Iglesias matematikariaren esanean, "ez dago geldiaraziko dituenik".