}

Algoritmo genetikoak, soluzio egokienaren bila

2008/01/01 Galarraga Aiestaran, Ana - Elhuyar Zientzia Iturria: Elhuyar aldizkaria

Algoritmo genetikoak eboluzio biologikoa imitatzen duten programazio-teknika bat dira, eta ohiko metodoen bitartez askatzen oso zailak edo ezinezkoak diren problemak ebazteko erabiltzen dira. Ez dakite oso ondo zergatik, baina ohiko teknikek huts egiten duten problemetan funtzionatu egiten dute; beraz, gero eta gehiago erabiltzen dira arazo praktikoei irtenbidea emateko.
Algoritmo genetikoak, soluzio egokienaren bila
2008/01/01 | Galarraga Aiestaran, Ana | Elhuyar Zientziaren Komunikazioa

(Argazkia: Artxibokoa)
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.

Algoritmo genetikoen funtzionamenduaren eskema.

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.

Darwinen eboluzioaren teorian oinarritzen dira algoritmo genetikoak.
Artxibokoa
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.

Saltzaile batek hainbat lekutatik igaro behar du eta abiapuntura iritsi, ahalik eta ibilbide egokiena eginez. Horri saltzailearen problema esaten zaio, eta ezin da ebatzi ohiko metodoekin, baina algoritmo genetikoen bidez ondo ebazten da.
Artxibokoa

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.

Ordutegiak diseinatzea benetan konplexua da, eta horretarako primerako tresna dira algoritmo genetikoak.
P. Gene
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.

Algoritmo genetikoak peptidoak diseinatzeko erabiltzen dira, beste aplikazio askoren artean.

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

Mª Teresa Iglesias: "Algoritmo genetikoen helburua ingurura egokitzea da"
Mª Teresa Iglesias Coruñako Unibertsitatek Matematika saileko irakaslea da, eta, duela gutxi, "Matematika ebolutiboak: algoritmo genetikoak" izeneko hitzaldia eman zuen EHUren Zientzia eta Teknologia Fakultatean, "Emakumea, zientziaren berritzaile?" jardunaldien barruan. Hitzaldiaren ondoren, emakume zientzialari berritzaile honekin hitz egiteko aukera izan genuen.
Hitzaldian esan duzunez, algoritmo genetikoak oso onak dira soluzio errazik ez duten problemak ebazteko, nahiz eta berez ez duten maximizatzen beti.
Hori da. Eboluzioak ere ez du maximora jotzen, baizik eta egokitzera. Inguru jakin batera ondo egokitzen diren banakoak sortzen ditu eboluzioak, eta gauza bera egiten dute algoritmo genetikoek. Adibidez, duela mila urteko gizon-emakumeekin alderatuta, haiek baino hobeto moldatzen gara gaurko gizartean, baina ez ginateke hain ondo moldatuko bat-batean garai hartan esnatuko bagina... Algoritmo genetikoek ematen dituzten soluzioak ez dira beti onenak izango, baina egoera jakin batean oso ondo moldatuko dira.
(Argazkia: A. Galarraga)
Gainera, ez dira bakarrik erabiltzen. Normalean, hasieran erabiltzen dira, eta, soluzio nahiko onen multzo bat lortu dutenean, ohiko metodoekin jarraitzen da.
Alabaina, ez dute beti funtzionatzen. Oker ez banago, hori zergatik gertatzen den ikertzen duzu.
Bai, funtzio batzuek ( deceptive functions ) nolabait iruzur egiten diote algoritmoari, eta optimotik urrutiratu egiten dute. Garai batean, uste zen algoritmo genetikoek ez zutela funtzionatzen funtzio horiekin, baina orain ikusten dugu batzuekin baietz eta beste batzuekin ezetz. Zaila da zergatik jakitea, eta gure taldean justu horretan aritzen gara; saiatzen gara argitzen zer ezaugarrik egiten duten funtzio bat algoritmo genetikoen bidez optimizatzen zaila izatea. Eta dagoeneko aurkitu ditugu batzuk.
Edonola ere, oraindik asko dago ikertzeko. Nahiko berriak dira, eta, kasu askotan ondo funtzionatzen dutenez, informatikariek erabili egiten dituzte, nahiz eta oraindik ez dagoen oinarri teoriko sendorik. Oinarri teorikoak lantzea guri dagokigu, ordea, eta horretan ari gara.
Galarraga Aiestaran, Ana
3
238
2008
1
032
Matematika; Eboluzioa
Artikulua
28

Gai honi buruzko eduki gehiago

Elhuyarrek garatutako teknologia