Soft computing en problemas de optimización dinámicos

• Autores: Jenny Fajardo Calderín
• Directores de la Tesis: Antonio David Masegosa Arredondo (dir. tes.) , David Alejandro Pelta Mochcovsky (dir. tes.)
• Lectura: En la Universidad de Granada ( España ) en 2015
• Idioma: español
• Tribunal Calificador de la Tesis: José Luis Verdegay Galdeano (presid.) , María Teresa Lamata Jiménez (secret.) , César Hervás Martínez (voc.) , Dagoberto Castellanos Nieves (voc.) , Enrique Onieva Caracuel (voc.)
• Enlaces
  • Tesis en acceso abierto en: DIGIBUG
• Resumen

  • La presente investigación se centra en el estudio, diseño y evaluación de esquemas de portafolio basados en metaheurísticas para abordar problemas de optimización dinámicos de tipo combinatorio. Se tuvieron en cuenta las ideas de adaptación, cooperación y aprendizaje que consideramos indispensables en este contexto. En ese sentido los objetivos planteados fueron:

    - Realizar un estudio en profundidad en el ámbito de la Soft Computing, de cara a identificar las técnicas que se utilizan para resolver problemas de optimización dinámicos, incluyendo las diferentes posibilidades de hibridación de técnicas.

    - Diseñar un portafolio de algoritmos que integre técnicas de adaptación, cooperación y aprendizaje, para resolver problemas de optimización dinámicos.

    - Validar el funcionamiento del portafolio de algoritmos con respecto a algoritmos del estado del arte sobre problemas de optimización dinámicos combinatorios de prueba y reales.

    - Proponer una librería de software para facilitar la reutilización y aplicación de metaheurísticas en la resolución de problemas de optimización estacionarios y dinámicos.

    Para alcanzar estos objetivos se propusieron, por un lado un portafolio de algoritmos que incorpora mecanismos de aprendizaje, y por otro, una batería de experimentos sobre problemas dinámicos de optimización, para validar su funcionamiento.

    La primera contribución de la tesis consiste en un portafolio de algoritmos, que dispone de un conjunto de metaheurísticas. En cada iteración selecciona cuál de ellas aplicar mediante un enfoque basado en créditos que actúa como un esquema de aprendizaje. Los experimentos se realizaron sobre cinco problemas "artificiales" a los que se les indujo dinamismo mediante el operador XOR, para diferentes escenarios de severidad y frecuencia de cambio. Los objetivos de la experimentación fueron evaluar el rendimiento del portafolio con diferentes esquemas de aprendizaje; evaluar el rendimiento de los algoritmos individuales que componen el portafolio, frente al propio portafolio; y finalmente, comparar la mejor variante de aprendizaje del portafolio con dos algoritmos de la literatura que han mostrado un muy buen rendimiento en estos problemas. Los resultados del método propuesto fueron significativamente mejores en la mayoría de los problemas, lo que demuestra que el enfoque del portafolio de algoritmos con un esquema de aprendizaje simple, proporciona buenos resultados para resolver PODs.

    Por otro lado, se aplicó el portafolio al problema de máxima cobertura dinámico (DMCLP). Dicho problema tiene como objetivo encontrar la ubicación de instalaciones que maximiza la demanda cubierta, es decir, la demanda que se encuentra dentro de un determinado tiempo o distancia de cobertura. Partiendo de la variante clásica de DMCLP se definieron dos variantes nuevas: DMCLP-AC y DMCLP-LocF, las cuales consisten en incorporar costos por apertura/cierre de instalaciones de un periodo a otro y en fijar la ubicación de las instalaciones a lo largo del tiempo, respectivamente.

    Para la resolución de estos problemas se empleó un portafolio compuesto por tres métodos de Recocido Simulado propuestos en la literatura, y que habían reportado muy buenos resultados. En la experimentación, se comparó el portafolio con los algoritmos individuales que lo componen y de forma general, se pudo concluir que el portafolio fue mejor que los métodos individuales en cada una de las instancias de prueba utilizadas. Cabe destacar que los resultados del portafolio de algoritmos para las tres variantes del DMCLP muestran que este tipo de esquemas son capaces de crear sinergias entre los métodos que lo componen.

    Por último, todos los algoritmos, métodos y problemas utilizados durante el desarrollo de la tesis se incorporaron en una librería de software llamada BiCIAM, que incluye diferentes algoritmos para resolver problemas de optimización tanto mono-objetivo como multi-objetivo, y tanto estáticos como dinámicos. BiCIAM le permite a los investigadores centrarse en el diseño del problema y el análisis de los resultados, reduciendo el esfuerzo de programación. Además dispone de una gran cantidad de algoritmos ya implementados, por lo que disminuye el nivel de conocimiento requerido a la hora de realizar un estudio en esta temática.