actas del x congreso español - upcommons.upc.edu

Actas del X Congreso Español

sobre Metaheurísticas,

Algoritmos Evolutivos y Bioinspirados

MAEB 2015

Editadas por:

Francisco Chávez de la ORafael M. Luque Baena

Francisco LunaFrancisco Fernández de Vega

Mérida - Almendralejo4, 5 y 6 de febrero de 2015

Edita: Francisco Chávez de la O, Rafael M. Luque-Baena, Francisco Luna, Francisco Fernández de VegaCentro Universitario de MéridaUniversidad de Extremadura

Derechos reservados

c� Los autores

Diseño de cubierta: Cayetano Cruz García

ISBN: 978-84-697-2150-6

iv

Comité Organizador

Cayetano Cruz GarcíaUniversidad de Extremadura

Josefa Díaz ÁlvarezUniversidad de Extremadura

Francisco Chávez de la OUniversidad de Extremadura

Francisco Fernández de VegaUniversidad de Extremadura

Francisco LunaUniversidad de Extremadura

Rafael M. Luque-BaenaUniversidad de Extremadura

v

Comité Director

Enrique AlbaUniversidad de Málaga

Abraham DuarteUniversidad Rey Juan Carlos

Francisco Fernández de VegaUniversidad de Extremadura

José Antonio GámezUniversidad de Castilla-La Mancha

Francisco HerreraUniversidad de Granada

J. Ignacio HidalgoUniversidad Complutense de Madrid

César HervásUniversidad de Cordoba

Rafael MartíUniversidad de Valencia

Juan Julián MereloUniversidad de Granada

José A. MorenoUniversidad de La Laguna

Luciano SánchezUniversidad de Oviedo

vii

Comité de Programa

Jesús Aguilar, Universidad Pablo de OlavideEnrique Alba, Universidad de MálagaCarlos Andrés Romano, U. Politécnica de ValenciaAda Álvarez, Universidad Autónoma de Nuevo LeónRamón Álvarez-Valdés, Universidad de ValenciaLourdes Araujo, Universidad Nacional a DistanciaJaume Bacardit, University of NottinghamJulio R. Banga, CSICJoaquín Bautista, Universidad Politécnica de CataluñaJosé Manuel Benítez, Universidad de GranadaChristian Blum, Universidad Politécnica de CataluñaRafael Caballero, Universidad de MálagaVicente Campos, Universitat de ValènciaJorge Casillas, Universidad de GranadaPedro A. Castillo Valdivieso, Universidad de GranadaFrancisco Chicano, Universidad de MálagaFrancisco Chávez, Universidad de ExtremaduraCarlos A. Coello Coello, CINVESTAV - IPNÁngel Corberán, Universidad de ValenciaOscar Cordón, Universidad de GranadaCarlos Cotta, Universidad de MálagaAntonio Córdoba, Universidad de SevillaBernabé Dorronsoro, Universidad de LuxemburgoAbraham Duarte, Universidad Rey Juan CarlosRichard Duro, Universidad da CoruñaAdenso Díaz, Universidad de OviedoJosé Egea, Universidad Politécnica de CartagenaFrancisco Javier Elorza, U. Politécnica de MadridAntonio J. Fernández, Universidad de MálagaFrancisco Fernández, Universidad de ExtremaduraMiguel Frade, Instituto Politécnico de LeiriaMario Garcia, Instituto Politécnico de TijuanaMaribel García Arenas, Universidad de GranadaEduardo García Pardo, Universidad Rey Juan CarlosCarlos García, Universidad de CórdobaNicolás García, Universidad de CórdobaSalvador García, Universidad de JaénRaúl Giraldez, Universidad Pablo de OlavideJosé Luís González-Velarde, Inst. Tec. de MonterreyAntonio González, Universidad de GranadaPedro González, Universidad de JaénJosé Antonio Gutiérrez, Universidad de CórdobaJosé Antonio Gámez, U. de Castilla-La ManchaJuan A. Gómez Pulido, Universidad de ExtremaduraFrancisco Herrera, Universidad de GranadaCesar Hervás, Universidad de CórdobaJosé Ignacio Hidalgo, U. Complutense de MadridMaría José del Jesús, Universidad de JaénAngel A. Juan, Universitat Oberta de CatalunyaManuel Laguna, Universidad de ColoradoDario Landa Silva, University of NottinghamHelena Ramalhinho Lourenco, U. Pompeu Fabra

José Antonio Lozano, Universidad del País VascoManuel Lozano, Universidad de GranadaFrancisco Luna, Universidad de MálagaGabriel J. Luque, Universidad de MálagaRafael M. Luque-Baena, Universidad de ExtremaduraLuís Magdalena, European Centre for Soft ComputingRafael Martí, Universitat de ValènciaFrancisco Martínez, Universidad de CórdobaBelén Melián, Universidad de La LagunaAlexander Mendiburu, Univ. del País VascoJulián Molina, Universidad de MálagaJ. Marcos Moreno, Universidad de La LagunaJosé A. Moreno, Universidad de La LagunaAntonio J. Nebro, Universidad de MálagaJulio Ortega, Universidad de GranadaDomingo Ortiz, Universidad de CórdobaLuis de la Ossa, Universidad de Castilla-La ManchaJosé Otero, Universidad de OviedoJoaquín Pacheco, Universidad de BurgosJuan J. Pantrigo, Universidad Rey Juan CarlosFrancisco Parreño, Universidad de Castilla-La ManchaDavid Pelta, Universidad de GranadaAntonio Peregrín, Universidad de HuelvaJosé Miguel Puerta, U. de Castilla-La ManchaCynthia Pérez, Tecnológico de SinaloaM. Elena Pérez, Universidad de ValladolidJuan R. Rabuñal, Universidad da CoruñaIgnacio Requena, Universidad de GranadaJosé Riquelme, Universidad de SevillaJose Luís Risco-Martín, U. Complutense de MadridVíctor Rivas, Universidad de JaénRubén Ruiz, Universidad Politécnica de ValenciaRoger Ríos, Universidad Autónoma de Nuevo LeónSancho Salcedo, Universidad de AlcaláRoberto Santana, Universidad Politécnica de MadridAntonio Sanz Montemayor, U. Rey Juan CarlosThomas Stützle, Université Libre de BruxellesYago Sáez, Universidad Carlos III de MadridAna María Sánchez, Universidad de GranadaLuciano Sánchez, Universidad de OviedoLeonardo Trujillo, Instituto Tecnológico de TijuanaÁngel Udías, Universidad Rey Juan CarlosMiguel A. Vega Rodríguez, U. de ExtremaduraSebastián Ventura, Universidad de CórdobaJosé Luís Verdegay, Universidad de GranadaGabriel Villa, Universidad de SevillaPedro Villar, Universidad de GranadaJuan Villegas, Universidad Autónoma MetropolitanaGabriel Winter, U. de las Palmas de Gran CanariaAmelia Zafra, Universidad de Córdoba

ix

Índice General

Sesión general

Planificación de celdas de reporte con el algoritmo SPEA2Víctor Berrocal-Plaza, Miguel A. Vega-Rodríguez, Juan M. Sánchez-Pérez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Algoritmo Genético con Diversificación Voraz y Equilibrio entre Exploración y ExplotaciónAndrés Herrera-Poyatos, Francisco Herrera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Introducing Mixtures of Generalized Mallows in Estimation of Distribution AlgorithmsJosian Santamaría, Josu Ceberio, Alexander Mendiburu, Roberto Santana, José A. Lozano . . . . . . . . . . . . . . . . . . . . 19

Un Algoritmo Evolutivo para la Reducción de Tiempos de Viaje y Emisiones Utilizando PanelesLEDDaniel H. Stolfi, Enrique Alba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Algoritmo memético basado en regiones con archivo externo para optimización multimodalBenjamin Lacroix, Daniel Molina, Francisco Herrera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

El problema de los cortafuegos. Resultados con métodos heurísticos y con programación linealenteraCarlos García-Martínez, Christian Blum, Francisco Javier Rodríguez, Manuel Lozano . . . . . . . . . . . . . . . . . . . . . . . . . 43

Estudio preliminar sobre visualización y clasificación de la calidad de la emisión de sonido en elClarineteFrancisco Fernández de Vega, Francisco Chávez de La O, Carlos M. Fernandes, Antonio Mora, J.J. Merelo . . . . 51

Generación de Secuencias de Pruebas Funcionales con Algoritmos Bio-inspiradosJavier Ferrer, Peter M. Kruse, Francisco Chicano, Enrique Alba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Ajuste Probabilístico de Modelos de Glucosa obtenidos mediante Gramáticas EvolutivasJ. Ignacio Hidalgo, Rafael Villanueva, José Manuel Colmenar, José L. Risco-Martín, Esther Maqueda, JuanCarlos Cortés, Almudena Sánchez, Marta Botella, José Antonio Rubio, Juan Lanchares, Óscar Garnica, AlfredoCuesta, Francisco Santonja, Iván Contreras, José Manuel Velasco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

Una Metaheurística Multiarranque para el Problema de la Partición Entera Común MínimaManuel Lozano, Francisco Javier Rodríguez, Carlos García-Martínez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Beam Search para la búsqueda de caminos en redes complejas con entidades semánticasFrancisco Vélez, Enrique Herrera-Viedma, Óscar Cordón . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

Registrado evolutivo de fragmentos craneales en 3D mediante Scatter SearchEnrique Bermejo, Alejandro León, Sergio Damas, Óscar Cordón . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

A Comparison of Estimation of Distribution Algorithms for the Linear Ordering ProblemJosu Ceberio, Alexander Mendiburu, José A. Lozano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

xiii

Algoritmo de aprendizaje de redes bayesianas basado en algoritmos de colonias de hormigas ymodelos sustitutos con estructura de árbolJuan Ignacio Alonso-Barba, Luis de La Ossa, José A. Gámez, José Miguel Puerta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

Generación de reglas difusas tipo TSK-1 basada en el principio apriori derivando el sistema dereglas mediante búsqueda localJavier Cózar, Luis de la Ossa, José A. Gámez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Modelo de Reglas de Asociación para el Diagnóstico de Prestaciones en el Servicio Público deEmpleo EstatalJosé Antonio Sánchez, José M. Luna, Sebastián Ventura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Algoritmos Heurísticos al Problema de Máxima Diversidad de Mínima SumaAnna Martínez Gavara, Vicente Campos, Manuel Laguna, Rafael Martí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

Un procedimiento basado en GRASP para un problema de asignación de equipos médicos dediagnóstico en una red de hospitales públicosRodolfo Mendoza Gómez, Roger Z. Ríos Mercado, Karla B. Valenzuela Ocaña . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

Un método multi-arranque aleatorizado para un problema de diseño de una red de caminos yubicación de maquinaria y patios forestales con consideraciones ambientalesAna L. González-Estrada, Roger Z. Ríos Mercado, Óscar A. Aguirre-Calderón . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

Análisis del espacio de funciones aditivamente descomponibles para dimensiones pequeñasJosé A. Lozano, Iván Sánchez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

Un enfoque multiobjetivo para la planificación multinivel de lotes de trabajos en sistemas distri-buidosSantiago Iturriaga, Bernabé Dorronsoro, Andrei Tchernykh, Sergio Nesmachnow, Pascal Bouvry . . . . . . . . . . . . . . 157

Optimizando el gasto de energía en redes de sensores con la utilización del conformado de hazJuan Carlos González-Macías, Francisco Luna, Rafael M. Luque-Baena, Juan F. Valenzuela-Valdés, Pablo Padilla

165

Estudio preliminar del rendimiento de familias de algoritmos multiobjetivo en diseño arquitectónicoAurora Ramírez, José-Raúl Romero, Sebastián Ventura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

Predicción a muy corto plazo de series temporales de volumen de tráfico rodado mediante co-evolución de RBFNsVíctor Rivas, Elisabet Parras-Gutiérrez, Antonio Fernández Ares, Pedro A. Castillo, Pedro García-Fernández,Maribel García Arenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

Implementación de algoritmos meméticos con capacidad de auto-generación sobre CouchBDManuel García García, Mariela Nogueira, Carlos Cotta Porras, Antonio J. Fernández-Leiva, J.J. Merelo . . . . . . 189

SIPESCA-B: presentando un benchmark de series temporales de datos reales para la prediccióndel tráficoPedro A. Castillo, Antonio Fernández Ares, Maribel García Arenas, Antonio Mora, Pablo García Sánchez, VíctorRivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

Interpolación espacial para la predicción de la radiación solar mediante gradient tree boostingRicardo Aler, José M. Valls, Inés M. Galván . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

Un algoritmo de colonias de abejas artificiales para el problema de agrupación de máxima diver-sidadFrancisco Javier Rodríguez Díaz, Manuel Lozano, Carlos García-Martínez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

Algoritmo evolutivo para optimizar ensembles de clasificadores multi-etiquetaJosé M. Moyano, Eva Gibaja, Alberto Cano, José M. Luna, Sebastián Ventura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

xiv

Optimización de la deconvolución de perfiles de difracción mediante algoritmos evolutivosSidolina Pereira Dos Santos, Juan Antonio Gómez Pulido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

Optimización Multi-objetivo del Consumo de Energía y Tiempo de Ejecución en una MemoriaCache de primer nivel para Sistemas EmpotradosJosefa Díaz-Álvarez, José Manuel Colmenar, José L. Risco-Martín, Juan Lanchares . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

Sesión especial: Metaheurísticas en Empresas y ProducciónOrganizadores: Joaquín Bautista, Óscar Cordón, Sergio Damas

Aplicación de metaheurísticas en la optimización de pasos superiores de carreterasJosé V. Martí, Víctor Yepes, Tatiana García-Segura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

Algoritmos GRASP para el equilibrado de líneas con riesgo ergonómico mínimoJoaquín Bautista, Rocío Alfaro, Cristina Batalla, Sara Llovera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

Aplicación de Técnicas de Inteligencia Computacional a un Sistema de Ciberseguridad CorporativaPaloma de Las Cuevas, Antonio Mora, J.J. Merelo, Pedro A. Castillo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

A Refined GRASP Algorithm for the Extended Car Sequencing ProblemElvira Laković, Manuel Chica, Sergio Damas, Joaquín Bautista, Óscar Cordón . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

Sesión especial: Metaheurísticas en logística portuaria y problemas afinesOrganizadores: Belén Melián, J. Marcos Moreno

Un Problema Real de Planificación de Rutas de Vehículos con IntermodalidadJesica de Armas, Belén Melián, Julio Brito, Eduardo Lalla Ruiz, Christopher Expósito Izquierdo . . . . . . . . . . . . . . 273

Búsqueda por Entornos Variables para el Problema de Asignación de AtraquesEduardo Lalla Ruiz, Christopher Expósito Izquierdo, Jesica de Armas, Belén Melián, J. Marcos Moreno-Vega . . 281

Modelos y algoritmos para el problema de la asignación de atraques en una terminal de contene-doresJuan Francisco Correcher, Pablo Froján, Ramón Álvarez-Valdés, Gerasimos Koulouris, José Manuel Tamarit . . 289

Un GRASP reactivo para el problema de planificación de la estibaFrancisco Parreño, Ramón Álvarez-Valdés, Dario Pacino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

Planificación de rutas para productos perecederos utilizando un híbrido GRAP-VNSJulio Brito, Airam Expósito, José Andrés Moreno Pérez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .305

Modelado del transbordo de contenedores en una terminal marítima de contenedoresChristopher Expósito Izquierdo, Jesica de Armas, Eduardo Lalla Ruiz, Belén Melián, J. Marcos Moreno-Vega . . 313

Sesión especial: Metodologías y Herramientas Software para la Investigaciónsobre Metaheurísticas

Organizadores: Francisco Chicano, Gabriel Luque

Using the Page Trend Test to Analyze the Convergence of Evolutionary AlgorithmsJoaquín Derrac, Sheldon Hui, Ponnuthurai Nagaratnam Suganthan, Salvador García, Francisco Herrera . . . . . . . 321

xv

Teoría del valor extremo como criterio de parada en la optimización heurística de puentesVíctor Yepes, José V. Martí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329

Descomposición en Landscapes Elementales del Problema de Diseño de Redes de Radio con Apli-cacionesFrancisco Chicano, Franco Arito, Enrique Alba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

Optimización Multi-objetivo Basada en Preferencias para la Planificación de Proyectos SoftwareRubén Saborido, Francisco Chicano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

Describiendo experimentos de optimización con MOEDLJosé Antonio Parejo Maestre, Sergio Segura, Antonio Ruiz-Cortés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .353

Optimización de Problemas Multiobjetivo de Ingeniería Civil con jMetalAntonio J. Nebro, Gustavo R. Zavala, Juan J. Durillo, Francisco Luna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .361

Sesión especial: Metaheurísticas, Algoritmos Evolutivos y Bioinspirados en Bio-informática

Organizadores: Miguel A. Vega-Rodríguez, Sergio Santander-Jiménez, ÁlvaroRubio-Largo, David L. González-Álvarez

Análisis Comparativo de Implementaciones del Algoritmo Multiobjective Artificial Bee Colonypara Reconstrucción FilogenéticaSergio Santander-Jiménez, Miguel A. Vega-Rodríguez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369

Docking Inter/Intra-Molecular Mediante Metaheurísticas Multi-objetivoEsteban López-Camacho, María Jesús García Godoy, José García-Nieto, Antonio J. Nebro, José F. AldanaMontes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

Ruteo de Micro-fluidos en Biochips Digitales: Un enfoque basado en Colonia de HormigasCarlos Mendoza, Eduardo Szaran, Diego Pedro Pinto Roa, Carlos Brizuela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385

Sesión especial: Búsqueda dispersa y re-encadenamiento de trayectoriasOrganizadores: Manuel Laguna, Rafael Martí

Búsqueda dispersa para un problema de localización de concentradoresRafael Martí, Ángel Corberán, Juanjo Peiró . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

Búsqueda dispersa aplicada al problema del paso de bandaJesús Sánchez-Oro, Abraham Duarte, Rafael Martí, Manuel Laguna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

Sesión especial: Simheurísticas en Logística, Transporte, y ProducciónOrganizadores: Ángel A. Juan, Javier Faulin, Helena Ramalhinho Lourenço

Técnicas estadísticas aplicadas a la selección de valores para parámetros de metaheurísticasLaura Calvet, Ángel A. Juan, Carles Serrat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

Tamaño y Composición de Flotas de Vehículos en Problemas de Rutas con Retorno: Un MétodoHeurístico con Aleatoriedad SesgadaJavier Belloso, Ángel A. Juan, Javier Faulín . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417

xvi

Un algoritmo basado en aleatorización sesgada para la recolección eficiente de residuos en ciudadesinteligentesAljoscha Gruler, Christian Fikar, Ángel A. Juan, Patrick Hirsch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423

Resolviendo el problema de rutas de vehículos con criterio medioambiental mediante una búsquedatabúSergio Úbeda, Javier Faulin, Adrián Serrano, Francisco Arcelus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429

Network design considering risk aversionLuis Cadarso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437

Uso combinado de métodos exactos con heurística aleatorizada para la programación y enruta-miento de servicios médicos domiciliariosCarlos Quintero-Araujo, Andrés F. Torres-Ramos, Edgar H. Alfonso-Lizarazo, Lorena S. Reyes-Rubiano, ÁngelA. Juan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441

Sesión especial: Desarrollo de videojuegos y software de entretenimientoOrganizadores: Antonio J. Fernández, Antonio Mora, Raúl Lara

Diseño de un Simulador de Bajo Coste para Vehículos Aéreos no TripuladosVíctor Rodríguez-Fernández, Héctor Menéndez, David Camacho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447

Desarrollo de un Bot Evolutivo Interactivo para Unreal Tournament 2004José Luis Jiménez López, Antonio J. Fernández-Leiva, Antonio Mora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455

Optimización en videojuegos: retos para la comunidad científicaRaúl Lara Cabrera, Mariela Nogueira, Carlos Cotta, Antonio J. Fernández-Leiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463

Diseño de bots competitivos para un juego de estrategia en tiempo real usando programacióngenética: análisis de funciones de fitnessAntonio Fernández Ares, Pablo García Sánchez, Antonio Mora, Pedro A. Castillo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471

Videojuegos Serios en Educación Infantil y PrimariaRafael Prieto de Lope, Daniel Díaz Salas, Jahiel Jerónimo, Nuria Medina Medina, Carlos García Cruz . . . . . . . . 479

Diseño de la experimentación para evaluar la efectividad de Behavior BricksIsmael Sagredo-Olivenza, Pedro Pablo Gómez-Martín, Marco Antonio Gómez-Martín, Pedro A. González-Calero487

RPG Quest Generation using a Search-based Approach and Partial Ordering PlanningÁlvaro Gutiérrez, José M. Peña, Luis Peña, Antón Planells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495

Sesión especial: Algoritmos paralelosOrganizadores: Enrique Alba, Francisco Luna

Comunicación eficiente entre vehículos aplicando un algoritmo multi-objetivo paraleloJamal Toutouh, Enrique Alba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503

Integrando ECJ con HadoopFrancisco Chávez de La O, Daniel Lanza, Francisco Fernández de Vega, Gustavo Olague, Leonardo Trujillo . . . . 511

Planificación multiobjetivo de viajes compartidos en taxis utilizando un micro algoritmo evolutivoparaleloRenzo Massobrio, Óscar Gabriel Fagúndez de Los Reyes, Sergio Nesmachnow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519

xvii

Un SMS-EMOA paralelo para resolver un problema real de ingeniería civilFrancisco Luna, Gustavo R. Zavala, Antonio J. Nebro, Juan J. Durillo, Carlos A. Coello Coello . . . . . . . . . . . . . . .527

Sesión especial: Algoritmos multiobjetivoOrganizadores: Enrique Alba, Mariano Luque

Un Nuevo Algoritmo Evolutivo en Programación Multiobjetivo para Aproximar el Frente Óptimode ParetoMariano Luque, Ana B. Ruiz, Rubén Saborido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535

Paginación gaussiana en áreas de registro. Análisis de rendimiento multi-objetivoVíctor Berrocal-Plaza, Miguel A. Vega-Rodríguez, Juan M. Sánchez-Pérez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543

Cooperación paralela para selección multiobjetivo de características en problemas de dimensiónelevadaDragi Kimovski, Julio Ortega, Andrés Ortiz, Raúl Baños . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551

Aplicación de algoritmos evolutivos multiobjetivo al diseño de circuitos integrados: criterios dedetenciónElisenda Roca, Rafael Castro-López, Francisco V. Fernández . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559

Reconocimiento de punto láser en sistemas de interacción mediante algoritmos multiobjetivosFrancisco Chávez de La O, Eddie Clemente, Daniel Hernández, Francisco Fernández de Vega, Gustavo Olague .567

Algoritmos evolutivos para un modelo multi-objetivo de selección de carteras con restricción decardinalidadEnriqueta Vercher, José D. Bermúdez, Rubén Saborido, Ana B. Ruiz, Mariano Luque . . . . . . . . . . . . . . . . . . . . . . . . . 575

Sesión especial: Metaheurísticas y soft computing en contextos complejosOrganizadores: José Luis Verdegay, David A. Pelta

Criterios de inversión y evaluación de la responsabilidad social mediante Soft ComputingClara Calvo, Carlos Ivorra, Vicente Liern, Blanca Pérez-Gladish . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581

RankFSP: Procedimiento de Búsqueda del Pescador aplicado al Aprendizaje de la Ordenación enRecuperación de InformaciónÓscar Alejo, Juan M. Fernández-Luna, Juan F. Huete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589

Una herramienta para la experimentación y análisis estadístico en ambientes dinámicosPavel Novoa-Hernández, Carlos Cruz Corona, David Pelta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597

Comparación de algoritmos metaheurísticos en la resolución del problema de planificación de rutasde camiones y remolques con restricciones difusasIsis Torres Pérez, Alejandro Rosete Suárez, Carlos Cruz Corona, José Luis Verdegay . . . . . . . . . . . . . . . . . . . . . . . . . . 605

Comparativa de algoritmos de inserción para un DVRPTWAlondra De Santiago, Belén Melián, Ada Álvarez, Francisco Ángel-Bello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .613

Optimización de Sistemas Basados en Reglas Difusas para la predicción de congestión a corto plazoPedro López, Enrique Onieva, Asier Perallos, Laura Arjona, Eneko Osaba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621

xviii

Sesión especial: Búsqueda de Vecindad VariableOrganizadores: Abraham Duarte, Eduardo G. Pardo

BVNS para el problema del bosque generador k-etiquetadoSergio Consoli, Nenad Mladenovic, José Andrés Moreno Pérez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629

Búsqueda de Vecindad Variable Básica para la minimización del tiempo máximo en el Problemadel Empaquetamiento de PedidosBorja Menéndez Moreno, Eduardo García Pardo, Abraham Duarte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637

Mejorando la eficiencia de sistemas embebidos utilizando estrategias paralelas de búsqueda devecindad variableJesús Sánchez-Oro, Abraham Duarte, Rafael Martí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645

Variantes de VNS para el Problema de Dispersión Max-MeanFrancisco Gortázar, Rubén Carrasco, An Thanh Pham, Micael Gallego, Abraham Duarte . . . . . . . . . . . . . . . . . . . . . . 653

Búsqueda de vecindad variable para problemas de programación entera no lineaJosé A. Egea, Julio Sáez-Rodríguez, Julio R. Banga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659

Sesión especial: Algoritmos evolutivos y creatividadOrganizadores: Francisco Fernández de Vega

Diseñando Problemas Sintéticos de Clasificación con Superficie de Aptitud DeceptivaEnrique Naredo, Leonardo Trujillo, Francisco Fernández de Vega, Sara Silva, Pierrick Legrand . . . . . . . . . . . . . . . . 667

Incluyendo el elitismo en el modelo creativo mediante algoritmos evolutivos desconectadosLilian Navarro Moreno, Francisco Fernández de Vega, Cayetano Cruz García . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675

Sesión especial: Análisis y reconocimiento de patrones basado en modelos yalgoritmos bio-inspirados

Organizadores: Leonardo Trujillo, Gustavo Olague

Algoritmo Masivamente Paralelo Inspirado en el Modelo de la Corteza Visual Artificial para elReconocimiento de ObjetosBenjamín Hernández, Gustavo Olague, Daniel Hernández, Eddie Clemente, Andersen Herrera . . . . . . . . . . . . . . . . . 683

Detección de objetos en imágenes naturales utilizando el paradigma de la programación cerebralcon un enfoque multiobjetivoEddie Clemente, Gustavo Olague, Daniel Hernández, José Luis Briseño, José Mercado . . . . . . . . . . . . . . . . . . . . . . . . 691

Algoritmo híbrido de enjambre de luciérnagas y aceptación por umbrales para diseño de vigasTatiana García-Segura, Víctor Yepes, José V. Martí, Julián Alcalá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699

Modelo Computacional para la Detección de Zonas Reactivas en Concreto Tratado con Acetatode UraniloCecilia Olague, Gustavo Olague, José Antonio Pérez, Eddie Clemente, Gilberto Wenglas . . . . . . . . . . . . . . . . . . . . . . . 707

Programación Cerebral para el Seguimiento de Objetos Basado en la Atención VisualDaniel Hernández, Gustavo Olague, Eddie Clemente, José Luis Briseño, Paul Llamas . . . . . . . . . . . . . . . . . . . . . . . . . 715

xix

Sesión especial: Procesamiento de imágenes y vídeoOrganizadores: Enrique Domínguez, Esteban Palomo, Rafael M. Luque-Baena

Selección del espacio de color para video-segmentacion mediante redes neuronales autorganizadasRafael M. Luque-Baena, Esteban J. Palomo, Ezequiel López-Rubio, Enrique Dominguez, Francisco Javier López-Rubio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723

Reconocimiento de rostros a partir de la propia imagen usando técnica CBIRCesar Benavides-Alvarez, Juan Villegas-Cortez, Graciela Román-Alonso, Carlos Aviles Cruz . . . . . . . . . . . . . . . . . . 733

Sesión especial: Computación evolutiva y bioinspirada aplicada a problemas deagrupación y clustering

Organizadores: David Camacho, Sancho Salcedo, Antonio Portilla

Algoritmo K-means adaptativo para clustering basado en grafosGema Bello Orgaz, Héctor Menéndez, David Camacho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 741

Análisis de Tendencias Espacio-Temporales de Temperatura en Europa mediante ClusterizaciónAcoplada a DatosMihaela Chidean, Jesús Muñoz-Bulnes, Eduardo Del Arco, Julio Ramiro-Bargueno, Antonio Caamaño-Fernández,Sancho Salcedo-Sanz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749

Índice de autores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757

xx

Tecnicas estadısticas aplicadas a la seleccionde valores para parametros de metaheurısticas

Laura Calvet1, Angel A. Juan1, Carles Serrat2

Resumen— La mayorıa de metaheurısticas incluyendiversos parametros que influyen en la calidad de susolucion. A pesar de esto, el Problema de Seleccionde Valores para Parametros no fue formalmente estu-diado hasta finales del siglo pasado, y aun hoy en dıa,muchos investigadores siguen sin utilizar un procedi-miento cientıfico para resolverlo. Escoger unos valo-res adecuados suele ser una tarea ardua que requie-re tiempo. En las ultimas decadas, el interes por es-te problema ha crecido, dando lugar a varios enfo-ques. Sin embargo, no hay ninguna metodologıa am-pliamente acceptada por la comunidad cientıfica. Estetrabajo aporta una revision de los enfoques, y propo-ne una metodologıa basada en tecnicas de Clusteriza-cion y Diseno de Experimentos. Con tal de ilustrar suaplicacion y mostrar su validez, esta es utilizada paraseleccionar valores para los parametros de un algo-ritmo hıbrido desarrollado para resolver el Problemade Rutas de Vehıculos con Multiples Almacenes, ydescrito en [12].

Palabras clave— Seleccion de valores para parame-tros, ajuste de parametros, clusters, diseno de expe-rimentos, algoritmos hıbridos

I. Introduccion

Actualmente, las metaheurısticas estan presentes enuna gran variedad de sectores estrategicos para laeconomıa. Su amplia aceptacion se debe a su capa-cidad para encontrar soluciones satisfactorias en untiempo razonable a problemas complejos de optimi-zacion tan relevantes como el Problema de Rutascon Vehıculos Capacitados o el Problema de Locali-zacion de Instalaciones. El uso de estos metodos seha extendido durante las ultimas tres decadas [21].La mayorıa de ellos estan inspiradas en la naturaleza,incluyen componentes estocasticos, y tienen diversosparametros [3].

A pesar del gran numero de investigaciones basa-das en metaheurısticas que demuestran la influenciade los parametros de las mismas en las solucionesobjetivas obtenidas [1, 2, 6, 18], el Problema de Se-leccion de Valores para Parametros (PSP, por sussiglas en ingles, Parameter Setting Problem) no fueestudiado en profundidad hasta finales del siglo XX.En [6], los autores exponen que en el pasado losinvestigadores ejecutaban sus algoritmos con diver-sos conjuntos de valores y simplemente selecciona-ban aquellos que proporcionaban mejores resultados.Otro procedimiento muy utilizado era el de seleccio-nar los mismos valores que otros autores habıan de-terminado que eran adecuados para problemas simi-

1. Universitat Oberta de Catalunya.aaaaE-mail: {lcalvetl, ajuanp}@uoc.edu

2. Universitat Politecnica de Catalunya.aaaaE-mail: [email protected]

lares. Estas observaciones se basan en el estudio dealgoritmos evolutivos, los cuales suelen tener muchosparametros y cuentan con una comunidad cientıficamuy activa. Sin embargo, estas afirmaciones se hanextrapolado al conjunto de metaheurısticas [2, 18].

El PSP se define formalmente como la busquedade un conjunto de parametros θ en el espacio deparametros Θ que proporcione resultados satisfacto-rios considerando un conjunto dado de instancias I,en un tiempo t normalmente limitado (t ≤ T ). Re-solver este problema suele ser una tarea complicadaya que requiere tiempo, el resultado depende no solode la metaheurıstica sino tambien del problema, ylos parametros pueden interaccionar [15].

Aunque aun hay muchos autores que no incluyenen sus publicaciones la metodologıa seguida para se-leccionar valores para los parametros de sus algorit-mos, hay un interes creciente en esta cuestion. Prue-ba de ello son los artıculos [8, 10, 14], que adviertende su importancia a la hora de hacer reproducibleslas metodologıas y dotar a los practicantes de to-das las herramientas necesarias para poder aplicarmetaheurısticas de manera eficiente.

En la literatura destacan dos enfoques que recogenlas principales metodologıas propuestas para resol-ver el PSP [6]: las Estrategias de Control de Parame-tros (PCS, Parameter Control Strategies) y las Es-trategias de Ajuste de Parametros (PTS, ParameterTuning Strategies). El primer enfoque se caracterizapor la adaptacion de parametros durante la resolu-cion de una instancia. En cambio el segundo grupode estrategias, basandose en la idea de robustez [22],asume que existe un conjunto de valores de parame-tros que manteniendose fijo durante la ejecucion delalgoritmo, proporciona resultados satisfactorios paraun conjunto de instancias.

Durante la ultima decada ha ganado protagonismoun tercer enfoque que incluye Estrategias de Ajus-te de Parametros basado en Caracterısticas de Ins-tancias (IPTS, Instance-specific Parameter TuningStrategies). Este combina elementos de los dos an-teriores: mantiene los valores de los parametros fijosdurante la resolucion pero los adapta a cada instan-cia en funcion de las caracterısticas de esta.

El objetivo de este artıculo es el de contribuir ala literatura centrada en el PSP mediante una com-paracion de los dos principales enfoques, analizandolos casos en que ofrecen mejores resultados y tam-bien sus limitaciones, y una detallada descripciondel enfoque mas reciente. Con el fin de ilustrarlo, seintroducen las principales investigaciones llevadas a

X Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB 2015)

409

cabo. Tambien se muestra una aplicacion de una me-todologıa que sigue el enfoque PTS a un algoritmohıbrido utilizado para resolver el Problema de Rutasde Vehıculos con Multiples Almacenes.

El artıculo se organiza de la siguiente manera. Enla seccion 2 se analizan en mas profundidad los di-ferentes enfoques presentados. La seccion 3 describelas principales contribuciones que se han hecho hastala fecha adoptando el enfoque IPTS. A continuacion,en la seccion 4 se expone una metodologıa que sigueel enfoque PTS, e incluye tecnicas de Clusterizaciony de Diseno de Experimentos, y se muestra la apli-cacion a un algoritmo concreto. En la seccion 5 seproponen algunas lıneas generales de trabajo futu-ro. Finalmente, la seccion 6 presenta las principalesconclusiones.

II. Enfoques existentes

A. Estrategias de Control de Parametros

Este enfoque propone la adaptacion dinamica de losparametros a medida que avanza la resolucion de unainstancia. En la mayorıa de casos, esto se consigueintegrando en el algoritmo principal un mecanismoque actualiza los valores en funcion de informacionque se obtiene durante la busqueda de una solucionsatisfactoria.

Con tal de ilustrar este enfoque se introduce unode los primeros trabajos [1]. En el se propone unaBusqueda Tabu para resolver el Problema de Asig-nacion Cuadratica. Su principal aportacion es la deadaptar la longitud de la lista tabu de manera quese incremente cuando las soluciones se repitan, lo-grando ası diversificar la busqueda y evitar quedarseatrapado en un optimo local. De igual modo, la lon-gitud se reduce en regiones donde no se repiten lassoluciones, y por lo tanto, puede ser conveniente in-tensificar la busqueda.

Hay tres tipos de control [6]: determinista, adapta-tivo y auto-adaptativo. El primero se asocia a estra-tegias que alteran el valor de un parametro de mane-ra determinista, basandose generalmente en el tiem-po de ejecucion transcurrido. Por control adaptativose entiende aquel que utiliza informacion que se ge-nera durante la busqueda para determinar la direc-cion y magnitud del cambio en el valor del parame-tro. El control auto-adaptativo se aplica en Algorit-mos Evolutivos, consiste en codificar los parametrosen los cromosomas, de esta manera los valores masadecuados estaran ligados a los individuos mas ap-tos, que tendran mas probabilidades de sobrevivir ytener descendencia que propague estos valores.

Este enfoque ha sido muy estudiado en el contex-to de Algoritmos Evolutivos. Una revision generalpuede encontrarse en [11], donde se ofrecen dos ra-zones para utilizar estas estrategias con un controladaptativo: (1) A medida que la resolucion del pro-blema de optimizacion avanza, es posible acumularinformacion sobre el fitness landscape y utilizarla pa-

ra obtener un resultado mejor; (2) La mayorıa delos metodos de optimizacion no exactos evolucionandesde una busqueda global difusa a una local. Dadoque esta evolucion es determinada por parametros,es posible utilizar la informacion obtenida durantela resolucion de una instancia para escoger el gradode intensificacion o diversificacion en un momentoconcreto.

Hoy en dıa, este es el enfoque mas investigado. De-bido a que adapta los parametros de manera dinami-ca y especıfica para cada instancia, ofrece resultadoscompetitivos. En contrapartida, requiere la modifi-cacion del algoritmo principal para acoplar un me-canismo de control y, como consecuencia de este me-canismo, el tiempo computacional necesario para re-solver una instancia puede verse incrementado. Esimportante remarcar que el aprendizaje adquiridomientras se resuelve una instancia no es utilizado ala hora de analizar una nueva instancia.

En general, se recomienda el uso de este enfoquesi el tiempo disponible lo permite, especialmente sise considera que la instancia que se quiere resolvertiene un fitness landscape con cambios bruscos.

B. Estrategias de Ajuste de Parametros

Este grupo de estrategias mantiene un conjunto devalores de parametros fijo durante la resolucion deuna instancia. En el caso de tener diversas instanciasde un mismo problema se suele seguir este procedi-miento:

1. Seleccionar un subconjunto representativo deinstancias;

2. Para cada instancia del subconjunto, encon-trar un conjunto de valores de parametros queproporcione resultados satisfactorios; y

3. Agregar los conjuntos de valores para obteneruno solo.

En este procedimiento se asume que aunque el con-junto de valores de parametros optimo para cadainstancia pueda ser diferente, sera similar en el casode instancias con caracterısticas parecidas, y que unconjunto de valores de parametros podra ser calcu-lado de manera que proporcione resultados satisfac-torios para el conjunto de instancias.

La obtencion de un conjunto de valores de parame-tros para una instancia dada se suele hacer con tecni-cas estadısticas (Diseno de Experimentos y Regre-sion, principalmente) y de optimizacion. Un ejemplode metodologıa que usa tecnicas clasicas de estadısti-ca y es frecuentemente citada se describe en [4]. Ini-cialmente, se selecciona un subconjunto representa-tivo de instancias. Despues, se escoge un rango devalores posibles para cada parametro. Seguidamen-te, para cada instancia del subgrupo se implementaun diseno factorial y se guardan las soluciones obje-tivas que se obtienen al resolver la instancia utilizan-do los valores indicados por el diseno en el algoritmodesarrollado. Con estos datos, se aproxima la super-ficie de respuesta y se aplica el metodo de maximapendiente para encontrar una solucion. Finalmente,

Simheurísticas en Logística, Transporte, y Producción

410

el promedio de los conjuntos de valores de parame-tros obtenidos para cada instancia del subconjuntorepresentativo es calculado. Esta metodologıa es pro-bada en dos heurısticas aplicadas a dos variantes delProblema de Ruteo con Vehıculos Capacitados.

Una completa revision de la literatura es presen-tada en [2, 18].

El enfoque PTS es el mas facil de implementar unavez se ha escogido el conjunto de valores de parame-tros a utilizar, simplemente se introduce en el algorit-mo y se ejecuta. Sin embargo, encontrar un conjuntode valores adecuado puede requerir tiempo y conoci-mientos de estadıstica. En este enfoque, se aprendede un subconjunto de instancias y este conocimien-to sirve para resolver todo el conjunto. Teniendo encuenta este hecho y que el algoritmo principal no esmodificado, este enfoque suele considerarse el masrapido.

Es conveniente el uso de estas estrategias en el casode querer resolver muchas instancias con un fitnesslandscape similar y relativamente plano.

C. Estrategias de Ajuste de Parametros basado enCaracterısticas de Instancias

Al igual que el enfoque PTS, el IPTS mantiene losvalores de los parametros fijos. Si bien, es mas fle-xible ya que permite ajustar estos valores para cadainstancia. Los pasos a seguir son los siguientes:

1. Elegir las caracterısticas de las instancias quese utilizaran para recomendar valores para losparametros, y escoger un subconjunto repre-sentativo de instancias;

2. Para cada instancia del subconjunto, calcularlas caracterısticas seleccionadas y determinarun conjunto de valores de parametros que pro-porcione resultados satisfactorios; e

3. Implementar un mecanismo capaz de apren-der valores adecuados para los parametros enfuncion de las caracterısticas de las instancias,a partir de los datos obtenidos en el paso pre-vio.

Aunque habıa anteriormente algunos trabajos conuna metodologıa que seguıa los pasos descritos, elmarco fue presentado en la tesis de Ries [18]. La au-tora utilizo tecnicas de Logica Difusa para llevar acabo el aprendizaje. Una aportacion importante deltrabajo es la consideracion tanto de la solucion ob-jetiva como del tiempo computacional empleado, yaque en algunos casos el investigador o practicanteesta interesado en obtener una solucion rapidamen-te aunque eso implique que la calidad de la mismadisminuya. Esta metodologıa fue aplicada a un Algo-ritmo Genetico y a un Algoritmo de Busqueda LocalGuiada para resolver el Problema del Viajante.

Las principales ventajas que tiene este enfoque esque no es necesario modificar el algoritmo principaly permite adaptar los parametros a cada instancia.Un paso esencial es la seleccion de las caracterısti-cas, estas deben ser faciles y rapidas de calcular, einfluir en la relacion entre valores de parametros y

calidad de la solucion. Un aspecto a tener en cuentaes que cualquier mecanismo de aprendizaje necesi-ta un numero relativamente elevado de instancias aanalizar en detalle para poder extraer informacion, yhay que considerar la posibilidad de sobreajuste. Porello, es necesario tener conocimientos de estadıstica.

D. Comparacion

Los enfoques mencionados tienen caracterısticasmuy diferentes que hacen que no haya ninguno quepueda considerarse el mejor, sino que cada uno pue-de ser recomendable en funcion de diversos factores.Concretamente, dependera del numero de instanciasa resolver, de los fitness landscapes, del tiempo dis-ponible, y de los conocimientos de programacion yde estadıstica del investigador, entre otros.

La Figura 1 muestra las caracterısticas que com-parten los diferentes enfoques.

Fig. 1. Enfoques para resolver el PSP.

III. Ejemplos de estrategias de ajuste deparametros basado en caracterısticas

de instancias

En esta seccion se describen las contribuciones masimportantes del enfoque IPTS. Este es relativamentenuevo y ha sido poco estudiado a pesar de su eleva-do potencial. La Figura 2 muestra el procedimientogeneral de las metodologıas que siguen este enfoque.

A. Regresion para predecir el tiempo computacionalen funcion de caracterısticas y parametros

El siguiente ejemplo esta basado en [9]. Los autoresanalizan el Problema de Satisfacibilidad Booleanacon los algoritmos Novelty+ y SAPS, los cuales sonprobabilistas e incompletos. Inicialmente, metodosde regresion son aplicados para predecir estadısti-cos suficientes que caracterizen las distribuciones deltiempo computacional que requieren los algoritmosanalizados. Las variables explicativas son un conjun-to de caracterısticas de las instancias y los valores delos parametros. Una vez estimada una funcion de re-gresion, se calculan los valores de los parametros queresultan en un menor tiempo computacional para lascaracterısticas de una instancia dada.

B. Diseno de Experimentos y Redes Neuronales

La contribucion [5] propone resolver el PSP median-te herramientas clasicas de estadıstica. Primero, se


411

Fig. 2. Esquema del enfoque IPTS.

utilizan tecnicas de Diseno de Experimentos para se-leccionar un conjunto de valores de parametros queproporcione un resultado satisfactorio para cada unade las instancias de un subgrupo. Posteriormente,una Red Neuronal es entrenada con las instanciasanalizadas, sus caracterısticas, y los conjuntos de va-lores de parametros obtenidos en el paso anterior, detal manera que sea capaz de recomendar conjuntospara instancias nuevas.

C. Sistema Bayesiano de Razonamiento basado enCasos

Este ejemplo esta descrito en [17]. Los autores pre-sentan un sistema basado en Redes Bayesianas. Ca-da una de ellas se construye para una instancia enconcreto, con informacion de las caracterısticas de lamisma, los conjuntos de valores de parametros con-siderados y variables que miden la calidad de la solu-cion encontrada para cada conjunto. Estas redes per-miten inferir el mejor conjunto de valores de parame-tros para cada instancia. Como marco integrador delas diferentes redes, se utiliza la metodologıa de Ra-zonamiento basado en Casos. De esta manera, cuan-do se considera una instancia nueva, el sistema bus-ca la red asociada a la instancia con caracterısticasmas similares y, basandose en esa red, propone uno omas conjuntos de valores (en funcion de la fiabilidadde cada conjunto). Finalmente, una vez la instancianueva ha sido resuelta con los conjuntos de valorespropuestos, sus caracterısticas, estos conjuntos, y lacalidad de las soluciones encontradas son introduci-dos en el sistema.

IV. Aplicacion

En esta seccion se propone una metodologıa para re-solver el PSP dados un algoritmo parametrico y ungrupo de instancias. Esta metodologıa esta basadaen el enfoque PTS y utiliza tecnicas de Clusteriza-cion [7] y Diseno de Experimentos [16]. Se analizasu aplicacion a un algoritmo hıbrido para resolver elProblema de Rutas de Vehıculos con Multiples Al-macenes desarrollado por Juan et al. [12].

A. Metodologıa

Inicialmente, se agrupan las diferentes instancias enclusters. El objetivo de este paso es identificar las

instancias que muestran una relacion similar entrevalores de parametros y calidad de la solucion en-contrada.

A continuacion, se escoge una instancia represen-tativa de cada cluster.

Para cada instancia seleccionada, se obtiene unconjunto de valores de parametros que ofrezca resul-tados satisfactorios mediante tecnicas de Diseno deExperimentos. Es necesario antes seleccionar los ran-gos de valores en los cuales se estima que estan losconjuntos de valores de parametros asociados a losmejores resultados, para acotar el espacio de parame-tros. Esto se puede conseguir realizando un estudiopiloto para definir las regiones mas prometedoras. Enel caso de tener rangos iniciales muy amplios, pue-de ser beneficiosa la aplicacion secuencial de disenosque vayan reduciendo el espacio de parametros ana-lizado y centrandose en los valores que proporcionenmejores resultados.

En el ultimo paso, cada conjunto de valores ob-tenido para una instancia representativa se utilizapara resolver todas las instancias del mismo cluster.

La Figura 3 esquematiza los pasos descritos.La principal ventaja de esta metodologıa es que

introduce mas flexibilidad que las que siguen el enfo-que PTS tradicional, ya que la clusterizacion permiteutilizar un conjunto de valores por cluster. Ademas,es mas rapida y facil de implementar que las meto-dologıas que siguen el enfoque PCS ya que no hacefalta modificar el algoritmo principal, solo se anali-zan en profundidad un subconjunto de las instancias,y los algoritmos de Clusterizacion suelen ser rapidospara un numero relativamente pequeno de observa-ciones. Aunque no tiene tanta flexibilidad como lasmetodologıas del enfoque IPTS, evita un proceso deaprendizaje menos directo que requiere de conoci-mientos estadısticos y de bastantes observaciones engeneral.

B. Caso de estudio

La metodologıa descrita ha sido probada en unalgoritmo hıbrido que combina la metaheurısticaBusqueda Local Iterada con aleatorizacion sesgadapara resolver el Problema de Rutas de Vehıculos conMultiples Almacenes [12]. Concretamente, se anali-zan los siguientes parametros del algoritmo:


412

Fig. 3. Pasos de la metodologıa propuesta.

bM: un parametro de una distribuciongeometrica que influye en la asignacion declientes a uno de los almacenes.bR: un parametro de una distribuciongeometrica que se utiliza para seleccionar losejes que forman las rutas.

Estos parametros pueden tomar valores entre 0 y 1.Las instancias consideradas son las que fueron uti-

lizadas en [12].

C. Implementacion

Todas las ejecuciones del algoritmo se realizaron 7veces, con semillas diferentes. Los valores que seguardaron fueron las medianas, una medida facil decalcular y robusta.

Inicialmente, se resolvieron las instancias con 10conjuntos de valores de parametros generados alea-toriamente. Las soluciones objetivas obtenidas paracada instancia fueron reescaladas para obtener valo-res en el rango [0, 1]. Estos datos fueron utilizadospara generar los clusters de instancias mediante elalgoritmo k-medoids, el cual determina tambien unainstancia representativa de cada cluster. El criterioque se uso para escoger el numero de clusters fue elbasado en average silhouettes [19]. La Tabla 1 mues-tra los clusters obtenidos. Las instancias que mos-traron poca variabilidad no fueron analizadas, paracentrar la atencion en aquellos casos en los que sepodıa mejorar notablemente la solucion objetiva.

Seguidamente, para cada instancia seleccionada,se realizaron 25 ejecuciones considerando 5 valoresequidistantes entre 0 y 1 para cada parametro. Seacoto el espacio de parametros a las regiones masprometedoras (mınimo un 5 % del area total). Pos-teriormente, se aplicaron dos disenos factoriales de3 niveles secuencialmente. El conjunto de valores deparametros que reporto el mejor resultado fue final-mente seleccionado (ver Tabla 2).

D. Resultados

La Tabla 3 incluye los resultados obtenidos con losconjuntos de valores de parametros proporcionadospor la metodologıa presentada (R) y con los conjun-tos propuestos en [12] (RJ), y las diferencias entreambos.

TABLA I

Clusterizacion de las instancias.

Instanciarepresentativa

Cluster

p01 p01p07 p04, p07, p11,

p18, pr02, pr05,pr09

p09 p03, p09, pr04,pr10

p19 p19p22 p22p23 p20, p23pr06 p05, p06, p08,

p10, p15, pr01,pr03, pr06,pr07, pr08

TABLA II

Conjuntos de valores para parametros propuestos.

Instanciarepresentativa

bM bR

p01 0.513 0.501p07 0.001 0.372p09 0.283 0.283p19 0.443 0.378p22 0.001 0.231p23 0.449 0.250pr06 0.500 0.231

El promedio de las diferencias fue de -0.184 %. Seaplico la prueba de los rangos con signo de Wilcoxonpara comparar las series de resultados. El p-valor fuede 0.934.

Estos valores indican que los resultados obtenidoscon los valores de parametros propuestos por la me-todologıa presentada son mejores en promedio. Sinembargo, el p-valor no permite afirmar que la dife-rencia entre las medianas de las series sea estadısti-camente significativa.


413

TABLA III

Resultados obtenidos.

Instancia R RJ Gap (%)

p01 585.000 593.829 -1.509p03 644.464 649.229 -0.739p04 1022.085 1024.473 -0.234p05 760.341 764.325 -0.524p06 882.827 880.418 0.273p07 899.709 906.395 -0.743p08 4440.534 4438.407 0.048p09 3920.743 3923.248 -0.064p10 3706.763 3705.012 0.047p11 3598.972 3592.891 0.169p15 2573.393 2573.393 0.000p18 3831.996 3835.388 -0.089p19 3883.686 3883.686 0.000p20 4080.348 4091.482 -0.273p22 5808.738 5806.480 0.039p23 6134.441 6145.576 -0.181pr01 861.319 861.319 0.000pr02 1330.495 1331.543 -0.079pr03 1813.634 1814.452 -0.045pr04 2084.843 2089.785 -0.237pr05 2379.075 2379.797 -0.030pr06 2709.792 2713.593 -0.140pr07 1109.235 1109.235 0.000pr08 1680.896 1678.872 0.120pr09 2148.216 2153.317 -0.237pr10 3016.255 3028.606 -0.409

V. Lıneas futuras de investigacion

La investigacion llevada a cabo entorno al PSP esrelativamente nueva y de creciente interes dada lapopularidad de las metaheurısticas en nuestra so-ciedad. Es por eso que hay un elevado numero deposibles lıneas de investigacion.

Una de las mas interesantes en el caso del enfoqueIPTS es la de estudiar el uso de tecnicas de estadısti-ca diferentes a las utilizadas hasta el momento (Re-gresion no lineal o no parametrica, diferentes tiposde Redes Neuronales, Arboles de Regresion, SupportVector Machine, etc). Muchas de estas tecnicas soncomunmente utilizadas en un problema que muestrasimilitudes con el analizado, el Problema de Selec-cion de Algoritmos [13, 20], que consiste en escogerde una cartera de algoritmos, el mas adecuado parauna instancia concreta en funcion de sus caracterısti-cas. Para resolverlo es tambien necesario un analisisdetallado de un subgrupo de instancias y un procesode aprendizaje con el fin de poder obtener recomen-daciones para instancias nuevas. Los dos problemaspersiguen obtener mejores resultados con algoritmosexistentes. Su estudio puede llevar a un mejor enten-dimiento del funcionamiento de las metaheurısticasutilizadas actualmente.

Otra lınea a considerar es la de incluir mas me-

canismos de aprendizaje en las metodologıas que si-guen el enfoque PCS para facilitar la resolucion denuevas instancias basandose en resoluciones previasde instancias del mismo problema, lo cual podrıa dis-minuir el tiempo computacional requerido. Con elmismo objetivo, tambien serıa posible construir unmecanismo que resolviese instancias del mismo pro-blema en paralelo, compartiendo informacion entrelos mismos.

Finalmente, es importante incidir en la utilidadque podrıan proporcionar comparaciones objetivasde los diferentes enfoques respecto a la calidad delas soluciones encontradas y el tiempo empleado. Engeneral, los autores suelen reportar el tiempo compu-tacional requerido por su algoritmo para resolver unainstancia, pero en el caso de ser necesaria una selec-cion de parametros previa, el tiempo dedicado no esfacilitado, aunque este suele ser significante.

VI. Conclusiones

Este trabajo ha presentado y comparado los diferen-tes enfoques para resolver el Problema de Seleccionde Valores para Parametros de metaheurısticas. Seha incidido en las Estrategias de Ajuste de Parame-tros basado en Caracterısticas de Instancias, el en-foque mas nuevo. Estas estrategias utilizan un con-junto de valores de parametros que depende de lascaracterısticas de la instancia a resolver, basandoseen una fase previa de aprendizaje con un conjunto deinstancias. Este enfoque es especialmente recomen-dable en el caso de tener un numero elevado de ins-tancias a resolver. En comparacion con el enfoque deEstrategias de Control de Parametros, el cual adap-ta dinamicamente los parametros durante la resolu-cion de una instancia, el enfoque analizado evita laintroduccion de mecanismos de control en el algorit-mo, y aprovecha el conocimiento adquirido durantela resolucion de otras instancias. Por otro lado, el en-foque de Estrategias de Ajuste de Parametros, quepropone utilizar un unico conjunto de valores fijo pa-ra resolver un conjunto de instancias de un mismoproblema, es bastante rıgido y requiere un algoritmorobusto.

Ademas, en este trabajo hemos introducido unanueva metodologıa simple y general, que sigue el en-foque de Estrategias de Ajuste de Parametros, aun-que con mas flexibilidad, ya que utiliza tecnicas deClusterizacion y asigna un conjunto de valores deparametros a cada cluster. Estas tecnicas son intuiti-vas y faciles de implementar con software estadıstico.La metodologıa propuesta tambien incluye metodosde Diseno de Experimentos, comunmente utilizadospara seleccionar valores para los parametros de me-taheurısticas.

Agradecimientos

Este trabajo ha sido parcialmente financiado porel Ministerio Espanol de Economıa y Competitivi-dad (TRA2013-48180-C3-3-P), y por el Programa


414

Iberoamericano de Ciencia, Tecnologıa y Desarro-llo (CYTED2010-511RT0419), en el contexto delprograma Smart Logistics & Production del IN3(http://dpcs.uoc.edu)

Referencias

[1] R. Battiti, G. Tecchiolli, The Reactive Tabu Search, OR-SA Journal on Computing, 6(2), pp. 126-140, 1994.

[2] M. Birattari, Tuning Metaheuristics: A machine learningperspective, Springer, 2005.

[3] I. Boussaıd, J. Lepagnot, P. Siarry, A survey on opti-mization metaheuristics, Information Sciences, 237, pp.82-117, 2013.

[4] S. P. Coy, B. L. Golden, G. C. Runger, E. A. Wasil, UsingExperimental Design to Find Effective Parameter Settingfor Heuristics, Journal of Heuristics, 7, pp. 77-97, 2000.

[5] E. Dobslaw, A Parameter Tuning Framework for Me-taheuristics Based on Design of Experiments and Artifi-cial Neural Networks, in Proceedings of the InternationalConference on Computer Mathematics and Natural Com-puting, Rome, Italy, 2010.

[6] A. E. Eiben, R. Hinterding, Z. Michalewicz, ParameterControl in Evolutionary Algorithms, IEEE Transactionson Evolutionary Computation, 3(2), pp. 124-141, 1999.

[7] T. Hastie, R. Tibshirani, J. Friedman, The elements ofstatistical learning, 2th edition, Springer, 2009.

[8] J. Hooker, Testing heuristics: We have it all wrong, Jour-nal of Heuristics, 1, pp. 33-42, 1996.

[9] F. Hutter, Y. Hamadi, H. H. Hoos, K. Leyton-Brown, Per-formance Prediction and Automated Tuning of Rando-mized and Parametric Algorithms, in Proceedings of the12th International Conference on Principles and Practiceof Constraint Programming, pp. 213-228, Nantes, France,2006.

[10] D. Johnson, A Theoretician’s Guide to the ExperimentalAnalysis of Algorithms, in Proceedings of the 5th and 6th

DIMACS Implementation Challenges, pp. 215-250, RhodeIsland, United States, 2002.

[11] K. D. Jong, Parameter Setting in EAs: a 30 Year Pers-pective, in Parameter Setting in Evolutionary Algorithms,ed. F. J. Lobo, C. F. Lima, Z. Michalewicz, pp. 1-18,Springer, 2007.

[12] A. Juan, I. Pascual, D. Guimarans, B. Barrios, Com-bining Biased Randomization with Iterated Local Searchfor solving the Multi-Depot Vehicle Routing Problem, In-ternational Transactions in Operational Research, DOI:10.1111/itor.12101, 2014.

[13] J. Y. Kanda, A. C. P. L. F. de Carvalho, E. R. Hrusch-ka, C. Soares, Using meta-learning to recommend meta-heuristics for the travelling salesman problem, in Procee-dings of the International Conference on Computer Mat-hematics and Natural Computing, Rome, Italy, 2010.

[14] A. Løkketangen, The importance of being careful, inProceedings of the International Conference on MachineLearning and Applications and Workshops, pp. 346-351,Honolulu, Hawaii, United States, 2007.

[15] E. Montero, M. C. Riff, B. Neveu, A beginner’s guide totuning methods, Applied Soft Computing, 17, pp. 39-51,2014.

[16] D. C. Montgomery, Design and analysis of experiments,8th edition, John Wiley & Sons, 2012.

[17] R. Pavon, F. Dıaz, R. Laza, V. Luzon, Automatic para-meter tuning with a Bayesian case-based reasoning sys-tem, Expert Systems with Applications, 36, pp. 3407-3420, 2009.

[18] J. Ries, Instance-Based Flexible Parameter Tuning forMeta-Heuristics using Fuzzy-Logic, PhD thesis, Univer-sity of Portsmouth, 2009.

[19] P. J. Rousseuw, Silhouettes: a Graphical Aid to the In-terpretation and Validation of Cluster Analysis, Compu-tational and Applied Mathematics, 20, pp. 53-65, 1987.

[20] K. A. Smith-Miles, Towards Insightful Algorithm Selec-tion For Optimisation Using Meta-Learning Concepts, inProceedings of the IEEE International Joint Conferenceon Neural Networks, pp. 4118-4124, Hong Kong, China,2008.

[21] E-G. Talbi, Metaheuristics: from design to implementa-tion, John Wiley & Sons, 2009.

[22] A. Viana, J. P. Sousa, M. A. Matos, Constraint OrientedNeighbourhoods - A New Search Strategy in Metaheuris-tics, Operations Research / Computer Science Interfaces,32, pp. 389-414, 2005.


415


416

actas del x congreso español - upcommons.upc.edu

Documents