Ba al dago matematikaririk Marten?

Gorka Kobeaga eta María Merino

2015eko irailaren 29an egunkari guztietako lehen orrialdean ikusi genuen Marte. Orduan, MRO zundak antzemandako aztarna beltzak gatz hidratatuak direla baieztatu zituen NASAk. Horrek, Lurretik kanpora bizirik badagoen – edo inoiz izan den – galdera berriz ekarri du ahora. Orain arte, bizia garatzeko ura beharrezkotzat jo izan da, nahiz eta ez diren beste aukera batzuk baztertu, eta aspaldiko galdera honi erantzun bat emateko itxaropena berpiztu da.

Ez da lehenengo aldia aurten Marte egunkarietan azaltzen zaiguna. Hilabete batzuk lehenago, Martxoaren 24an, planeta gorriaren esplorazioan beste pausu bat eman zen, maratoi baten luzerako pausu bat alegia. Lehenengo aldiz astroibilgailu batek, Opportunity deiturikoak, lasterketa hau osatzen duten 42.195 kilometroak egin zituen, horretarako hamarkada bat behar izan zituelarik.

Urte hauetan astroibilgailuek jasotako ebidentzia geologikoek erakusten digute Marten ura egon izan bazela urte luzez. Hasierako helburuak zaharkituta, 2014an jakitera eman zen, ibilgailu hauen gaur egungo helburu nagusia gure alboko planetan bizia inoiz eman baden zehaztea dela.

Marteren gainazala lurraren zati lehorraren adinakoa izanik, izango ahal gara gai, urtean batezbesteko 4 km egiten duten astroibilgailu gutxi batzuekin, bizitzaren inguruko ikerketarako lekukoak biltzeko? Ezbairik gabe, ibilbide aproposa aukeratzea ezinbestekoa da misioaren arrakastatsua izateko. Matematikariak hurrengo problemara garamatza:

Zein da astroibilgailu batek egin behar duen ibilbidea, froga eta ebidentzien laginak aurkitzeko probabilitatea handitzeko?

Ezohiko problema bat badirudi ere, lurtarrok, sarritan aurkitzen gara antzerako problemen aurrean:

• Nori ez zaio gertatu hainbat errekadu egin behar eta dendak ixtear egotea. Errekadu horiei lehentasun bat jartzen diegu, eta zein ordenetan egingo ditugun erabaki behar izaten dugu, kontuan izanda hauen arteko distantzia, daukagun denbora eta lehentasunezko gauzak.
• Era berean, toki berri bat bisitatzera goazenean, bisitaren iraupenaren barruan, sarritan jarduera guztiak ezin ikusi izaten ditugu. Orduan, iraupen hau eta gure lehentasunak kontuan izanik, zein ibilbide egingo dugun erabaki behar izaten dugu, bidaia gure gustukoena izateko asmoz.
• Are gehiago, enpresa munduan, eguneroko efizientzia handiagotzeko premiaz, mota honetako problemak agertzen dira sarri. Adibidez, hornitzaile lanetan aritzen den enpresa batek, bere bezeroen premiak ahalik eta egokien betetzeko, banaketa lanetan aritzen diren kamioek egingo duten ibilbidea erabaki behar izaten du.

Ibilbidearen distantzia, edo denbora, batek mugatuta leku desberdinetan eginbehar desberdinak ditugunean eta hauen gaineko lehentasunak ditugunean, Orientazio Problemaren (Orienteering Problem) aurrean gaudela esaten da.

Optimizazio problema mota honetako adibiderik zaharrena, eta seguruenik famatuena, saltzaile ibiltariaren problema da, TSP izenekoa. Problema hauek konplexutasun konputazionalaren teorian NP-gogorrak deitzen dira. Problema honen zailtasuna, leku kopurua handitzean problemaren tamaina, ibilbide posibleen multzoa, esponentzialki hasten dela da. Are gehiago, matematika eta konputazioko ikerkuntzarako erronka da. Hori dela eta, ebazteko metodo zehatzak zein algoritmo heuristikoak gaur egun inplementatzen eta hobetzen ari dira; eraginkortasuna, kostua eta soluzioaren kalitatearen arteko oreka bilatuz, emaitza ahalik eta hoberenak denbora lehiakorrean aurkitzeko.

Amu lez erabilitako artikulu honen izenburura itzuliz, eta Marten aurkikuntza matematikorik egiteko asmorik gabe, helarazi nahi genuke Matematika edonon dagoela, bizitzan eta ikerkuntzan aurrerapausoak egiten laguntzeko prest.

Artikuluaren fitxa

• Aldizkaria: Ekaia
• Zenbakia: 28
• Artikuluaren izena:Orientazio problema eta algoritmo genetikoak.
• Laburpena: Artikulu hau UPV/EHUko Modelizazio eta Ikerkuntza Matematikoa, Estatistika eta Konputazioa izeneko masterrean Gorka Kobeagak defendatutako master amaierako lanean oinarrituta dago. Orientazio Problemaren (OP) aurkezpena eta ebazpen ebolutiboaren analisia du helburu. Saltzaile Ibiltariaren problema ezagunaren aldaera berezi bat da OP. Optimizazio Konbinatorioko problema honen aplikazioak eta modelizazioak aurkezten dira. OPren konputaziozko konplexutasuna dela eta, Concorde TSP solver erabiltzen duen algoritmo genetiko bat diseinatu eta inplementatu da. Gainera, herri kopuruarekiko eta distantzia mugarekiko portaera eta prozedura genetikoen parametroekiko konbergentzia aztertu da. Euskal Autonomia Erkidegoko eta literatura zientifikoko datu-baseak erabili dira.

• Egileak: Gorka Kobeaga Urriolabeitia eta Maria Merino Maestre
• Argitaletxea: UPV/EHUko argitalpen zerbitzua
• ISSN: 0214-9001
• Orrialdeak: 183-209
• DOI: 10.1387/ekaia.14540

Egileez:

Gorka Kobeaga doktoretza ikaslea da Basque Center for Applied Mathematics ikerketa zentroan. María Merino Ikerkuntza Operatiboa arloko ikertzailea eta Euskal Herriko Unibertsitateko irakaslea da.

Ekaia aldizkariarekin lankidetzan egindako atala.