Konputazio ebolutiboan, algoritmoek optimizazio-problemen gainean duten errendimendua ebaluatzeko ohikoa izaten da problema horien hainbat instantzia erabiltzea.
Batzuetan problema errealen instantziak eskuragarri daude, eta beraz, esperimentaziorako instantzien multzoa hortik osatzen da. Tamalez, orokorrean, ez da hori gertatzen. Instantziak eskuratzeko zailtasunak direla tarteko, ikertzaileek instantzia artizialak sortu behar izaten dituzte, ahal den neurrian, problema errealek dituzten ezaugarriak kontuan izanik.
Ezinezkoa denean ordea, ohikoa da instantzia artifizialak sortzeko, horiek osatzen dituzten parametroak uniformeki ausaz lagintzea. Helburua, instantzien espazioaren eredugarria den instantzia-lagin uniforme bat lortzea da. Alabaina, prozedura hori zuzena izateko, uniformeki ausaz lagintzea parametroen espazioan eta uniformeki ausaz lagintzea instantzien/helburu-funtzioen espazioan baliokideak izan behar dira.
Instantziei dagokienez, uniformeki ausaz esaten denean, optimizazioaren ikuspegitik bi egoera bereizi ditzakegu, soluzioa bilatzeko erabiltzen duten algoritmo motaren arabera. Alde batetik, soluzio bakoitzari dagokion helburu-funtzioaren balioa modu esplizituan kontuan hartzen duten algoritmoak ditugu. Beste aldetik, soluzioei dagokien helburu-funtzioaren balioen konparazioa bakarrik erabiltzen duten algoritmoak daude (A soluzioa B soluzioa baino txarragoa denetz, alegia).
Lehenengo taldeari dagokionez, edozein problema kontsideratuz gero, bereizi daitezkeen helburu-funtzio kopurua infinitua da, hau da, instantzia osatzen duten parametroei balioak aldatuz lortzen ditugun instantzia guztiak ezberdinak dira. Aldiz, bigarren taldeari dagokionez, funtzio kopurua nitua da; Izan ere, talde horretako algoritmoek, funtzioak bilaketa-espazioko soluzio guztien rankingak bezala ikusten dituzte. Beraz, n tamainako edozein problema batentzat, sortu daitezkeen ranking kopurua |Ω| ! da (Ω bilaketa-espazioko soluzio guztien multzoa da).
Azterketa aurrera eramateko konbinatoriako hiru permutazio problema ezagun aukeratu ditugu: ordenazio linealaren problema (LOP), esleipen-problema koadratikoa (QAP) eta Permutation owshop scheduling problem (PFSP). Problema horietan Ω-k n tamaina- ko permutazio guztiak biltzen ditu, hau da, n!. Aurreko hiru problema horietaz baliaturik, instantziak parametro-espazioan edo ranking-espazioan uniformeki ausaz lagintzea berdinak diren edo ez aztertuko dugu.
Horretarako, problema bakoitzaren 105 instantzia sortuko ditugu (n = 3 tamainako instantziak) horiek osatzen dituzten parametroak [0; 100] tartean uniformeki laginduz. Jarraian, instantzia bakoitzari dagokion soluzio-rankinga kalkulatuko dugu, eta azkenik ranking bakoitza zenbat alditan errepikatuta agertzen den zenbatuko dugu.
Emaitzetatik hainbat ondorio interesgarri atera ditzakegu. LOParen kasuan ranking guztiak sortzea, hau da, (3!)!=720 ranking, ezinezkoa da. Problema horretan, soluzio onenaren alderantzizkoa, soluzio txarrena da, eta beraz sortu daitezkeen rankingak simetrikoak izan behar dute. Ondorioz, (3!)! ranking posibleetatik, gutxi batzuk sortu daitezke bakarrik (egindako esperimentazioan, 48 ranking). LOParekin jarraituz, rankingen agerpen-kopurua ez dela uniformea ikusi dugu. Ez hori bakarrik, beraien agerpen-probabilitatearen arabera rankingak, multzokatu egin daitezke.
Rankingen agerpen-probabilitatearen eta haien zailtasunarekin inguruko aipamenen bat egiteko asmotan, LOPan ikusi ditugun rankingak aztertu ditugu duten optimo lokal kopurua aztertuaz. Emaitzen arabera, ranking-multzo berean dauden ranking guztiek optimo lokal kopuru bera dute, eta soluzio rankingean posizio berdinetan daude kokatuta.
PFSP eta QAPari dagokienez, problema horiek ez dira LOPa batezbesteko murriztaileak, eta beraz, n = 3 kasurako, ranking guztiak agertu dira. Baina, n = 4, kasurako, (4!)! ranking sortu al daitezke? Lan honetan agertu diren galdera guztiek etorkizunerako ikerketa ildo interesgarri bat proposatzen dute.
Artikuluaren fitxa
- Aldizkaria: Ekaia
- Zenbakia: Ekaia 34
- Artikuluaren izena: Zorizko instantzia uniformeak sortzen al dira optimizazio konbinatorioan?
- Laburpena: Konputazio ebolutiboan, algoritmoek optimizazio-problemen gainean duten errendimendua ebaluatzeko, ohikoa izaten da problema horien hainbat instantzia erabiltzea. Batzuetan, problema errealen instantziak eskuragarri daude, eta beraz, esperimentaziorako instantzien multzoa hortik osatzen da. Tamalez, orokorrean, ez da hori gertatzen: instantziak eskuratzeko zailtasunak direla tarteko, ikerlariek instantzia artifizialak sortu behar izaten dituzte. Lan honetan, instantzia artifizialak uniformeki zoriz sortzearen inguruko aspektu batzuk izango ditugu aztergai. Zehazki, bibliografian horrenbestetan onetsi den ideia bati erreparatuko diogu: Instantzien parametroen espazioan zein helburu-funtzioen espazioan uniformeki zoriz lagintzea baliokideak dira. Exekutatu ditugun esperimentuen arabera, baliokidetasuna kasu batzuetan ez dela betetzen frogatuko dugu, eta beraz, sortzen diren instantziek espero diren ezaugarriak ez dituztela erakutsiko dugu.
- Egileak: Josu Ceberio, Borja Calvo, Alexander Mendiburu, Jose Antonio Lozano.
- Argitaletxea: UPV/EHUko argitalpen zerbitzua.
- ISSN: 0214-9001
- Orrialdeak: 261-277
- DOI: 10.1387/ekaia.18877
Egileez
Josu Ceberio, Borja Calvo, Jose Antonio Lozano UPV/EHUko Informatika fakultateko Konputazio Zientziak eta Adimen Artiziala Sailean dabiltza eta Alexander Mendiburu Konputagailuen Arkitektura eta Tekonologia Sailean.
Ekaia aldizkariarekin lankidetzan egindako atala.
