Soft Computing en problemas de optimización dinámicos

Abstract

La presente investigaci´on se centra en el estudio, dise˜no y evaluaci´on de esquemas de portafolio basados en metaheur´ısticas para abordar problemas de optimizaci´on din´amicos de tipo combinatorio. Se tuvieron en cuenta las ideas de adaptaci´on, cooperaci´on y aprendizaje que consideramos indispensables en este contexto. En ese sentido los objetivos planteados fueron: Realizar un estudio en profundidad en el ´ambito de la Soft Computing, de cara a identificar las t´ecnicas que se utilizan para resolver problemas de optimizaci´on din´amicos, incluyendo las diferentes posibilidades de hibridaci´on de t´ecnicas. Dise˜nar un portafolio de algoritmos que integre t´ecnicas de adaptaci´on, cooperaci´on y aprendizaje, para resolver problemas de optimizaci´on din´amicos. Validar el funcionamiento del portafolio de algoritmos con respecto a algoritmos del estado del arte sobre problemas de optimizaci´on din´amicos combinatorios de prueba y reales. Proponer una librer´ıa de software para facilitar la reutilizaci´on y aplicaci´on de metaheur ´ısticas en la resoluci´on de problemas de optimizaci´on estacionarios y din´amicos. 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´amicos de optimizaci´on, para validar su funcionamiento. La primera contribuci´on de la tesis consiste en un portafolio de algoritmos, que dispone de un conjunto de metaheur´ısticas. En cada iteraci´on selecciona cu´al de ellas aplicar mediante un enfoque basado en cr´editos que act´ua 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´on 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´etodo 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´o el portafolio al problema de m´axima cobertura din´amico (DMCLP). Dicho problema tiene como objetivo encontrar la ubicaci´on 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´asica 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´on de las instalaciones a lo largo del tiempo, respectivamente. Para la resoluci´on de estos problemas se emple´o un portafolio compuesto por tres m´etodos de Recocido Simulado propuestos en la literatura, y que hab´ıan reportado muy buenos resultados. En la experimentaci´on, se compar´o el portafolio con los algoritmos individuales que lo componen y de forma general, se pudo concluir que el portafolio fue mejor que los m´etodos 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´etodos que lo componen. Por ´ultimo, todos los algoritmos, m´etodos 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´on tanto mono-objetivo como multi-objetivo, y tanto est´aticos como din´amicos. BiCIAM le permite a los investigadores centrarse en el dise˜no del problema y el an´alisis de los resultados, reduciendo el esfuerzo de programaci´on. Adem´as 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´atica.