Zorizko instantzia uniformeak sortzen al dira optimizazio konbinatorioan?

• Autores: Josu Ceberio Uribe , Borja Calvo Molinos , Alexander Mendiburu Alberro , José Antonio Lozano Alonso
• Localización: Ekaia: Euskal Herriko Unibertsitateko zientzi eta teknologi aldizkaria, ISSN 0214-9001, Nº. 34, 2018, págs. 261-277
• Idioma: euskera
• DOI: 10.1387/ekaia.18877
• Títulos paralelos:
  • Do we generate instances uniformly at random in combinatorial optimization?
• Enlaces
  • Texto completo
• Resumen
  • euskara

    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.

  • English

    In evolutionary computation, it is common practice to use sets of instances as test-beds for evaluating and comparing the performance of new optimisation algo-rithms. In some cases, real-world instances are available, and, thus, they are used to constitute the experimental benchmark. Unfortunately, this is not the general case. Due to the difficulties for obtaining real-world instances, or because the optimisation problems defined in the literature are not exactly as those defined in the industry, practition-ers are forced to create artificial instances. In this paper, we study some aspects related to the random generation of artificial instances. Particularly, we elaborate on the as-sumption that states that sampling uniformly at random in the space of parameters is equivalent to sampling uniformly at random in the space of functions. Illustrated with some experiments, we prove that for some type of algorithms this assumption does not hold.