Técnicas avanzadas de optimización en ambientes dinámicos

Resumen

La presente investigación se desarrolla en el contexto de la optimización de problemas dinámicos mediante métodos meta-heurísticos multipoblacionales. Específicamente, las contribuciones se centran en la propuesta de mejoras a enfoques existentes aplicando técnicas de control de parámetros de tipo adaptativas y auto-adaptativas. En ese sentido, los objetivos trazados fueron los siguientes: 1) Proponer un herramienta para gestionar la experimentación en ambientes dinámicos, a partir de una organización adecuada de las medidas de rendimiento en ambientes dinámicos, y la inclusión de pruebas estadísticas no paramétricas. 2) Proponer estrategias adaptativas que mejoren el rendimiento del enfoque PSO multi-enjambre en ambientes dinámicos. 3) Investigar si la auto-adaptación, como técnica de control de parámetros, tiene sentido en ambientes dinámicos. 4) Analizar el rol de la auto-adaptación en ambientes dinámicos cuando es aplicada en distintas partes del algoritmo. En relación al objetivo 1, se desarrolló la herramienta DynOptLab sobre la tecnología Java. Esta herramienta está compuesta por dos parte fundamentales: 1) un framework orientado a objetos que permite la inclusión de problemas, algoritmos y medidas de rendimiento, y 2) una interfaz gráfica de usuario orientada a la gestión y ejecución de experimentos computacionales. En este contexto, se propuso un marco de trabajo para organizar las medidas de rendimientos en ambientes dinámicos basado en cuatro categorías: información del problema, información del algoritmo, tiempo de medición, y función de agregación. Este marco de trabajo fue aplicado para organizar los progresos actuales, y en el diseño de las medidas de rendimiento en el framework de DynOptLab. En relación a la interfaz gráfica se diseñó de manera que el investigador pudiera establecer de manera intuitiva, los factores objeto de estudio (problemas y algoritmos) y las variables de respuesta (medidas de rendimiento). Asimismo, la interfaz gráfica de DynOptLab permite ejecutar los experimentos de manera paralela, y analizar los resultados a partir de: la visualización directa de los resultados, comparaciones entre algoritmos, y la aplicación pruebas estadísticas no paramétricas. Con el objetivo de verificar las funcionalidades de la herramienta propuesta, se diseñó un caso de estudio basado en una investigación de la literatura. Los resultados de esta prueba fueron satisfactorios y permiten concluir que la herramienta propuesta permite una gestión eficiente de la experimentación en ambientes dinámicos. Con respecto al objetivo 2, se desarrolló una revisión a fondo de las propuestas actuales que aplican el paradigma PSO a problemas dinámicos de optimización. A partir de este estudio se pudo comprobar que las variantes multi-poblaciones (multi-enjambre) se encuentran entre las más efectivas para lidiar con problemas dinámicos complejos. En ese sentido, se destaca el algoritmo mQSO, el cual incluye varias poblaciones y una estrategia para la generación de diversidad durante la ejecución denominada enfoque quantum. No obstante los éxitos demostrados por este algoritmo en escenarios dinámicos, en la presente investigación se propusieron dos estrategias adicionales para mejorar su rendimiento. Por un lado, se diseñó una estrategia de diversidad similar al enfoque quantum pero aplicada después de la ocurrencia de un cambio en el ambiente, y por otro, una regla de control difusa para decidir en tiempo de ejecución los enjambres que pueden contribuir al proceso de optimización. Los resultados de los experimentos computacionales demostraron los beneficios de las propuestas. En particular, la estrategia de diversidad resultó efectiva en problemas con funciones pico multimodales, mientras que la regla de control difusa en problemas con funciones pico unimodales. Para cumplir con el objetivo 3 de la investigación, se desarrolló un estudio en profundidad de los progresos actuales relacionados con la aplicación de la auto-adaptación en ambientes dinámicos. A partir de esta revisión se organizaron los trabajos existentes de acuerdo al tipo y alcance de la investigación: trabajos básicos, trabajos teóricos, y trabajos avanzados. En el primer caso se encuentran principalmente las primeros trabajos, y se caracterizan por el estudio de paradigmas auto-adaptativos en ambientes dinámicos. En el segundo caso aparecen los trabajos que analizan teóricamente el comportamiento de modelos auto-adaptativos. Finalmente, en el tercer grupo se encuentran los trabajos más recientes, caracterizados por la inclusión de enfoques de adaptación dinámica en conjunto con algún modelo auto-adaptativo. De manera general, se observó que existen conclusiones divididas en relación al éxito o no de la auto-adaptación en ambientes dinámicos. Asimismo, que son prácticamente inexistentes las investigaciones que apliquen modelos auto-adaptativos directamente a los enfoques de adaptación dinámica. En este contexto, se propuso una estrategia auto-adaptativa para la generación de diversidad durante la ejecución, con el objetivo de investigar si en este caso, la auto-adaptación tiene sentido en ambientes dinámicos. En esencia, la estrategia permite la auto-adaptación de uno de los parámetros del enfoque quantum de mQSO, y fue aplicada en algoritmos multi-poblacionales basados en el paradigma Evolución Diferencial (DE). Los experimentos computacionales desarrollados ermitieron identificar: 1) la mejor combinación de parámetros que definen a la estrategia, y 2) el alto nivel de competitividad de los algoritmos propuestos (comparables y en ocasiones superiores a los de literatura). A partir de estos resultados, la principal conclusión a la que se arribó fue que la auto-adaptación si tiene sentido en ambientes dinámicos. No obstante los resultados del objetivo anterior, resultó de interés analizar con más profundidad el rol de la auto-adaptación en ambientes dinámicos. Este aspecto fue desarrollado a través del objetivo 4. En este sentido, se diseñaron experimentos computacionales orientados a estudiar el rendimiento de 8 algoritmos multi-poblacionales con paradigmas computacionales basados en DE. Estos algoritmos se caracterizaron por la inclusión o no de distintos modelos auto-adaptativos tanto a nivel de paradigma como de enfoque de adaptación dinámica. Los resultados indicaron que la auto-adaptación posee un mayor impacto cuando es aplicada al enfoque de adaptación dinámica considerado. Asimismo, los algoritmos con presencia de modelos auto-adaptativos en ambos niveles resultaron superiores a los que solo aplican auto-adaptación solo a nivel de paradigma. Adicionalmente, con el objetivo de entender mucho mejor estas conclusiones, se propuso una medida que permite cuantificar el grado de adaptabilidad de los algoritmos. Finalmente, la competitividad de los mejores algoritmos estudiados fue analizada en relación a otros de la literatura. En relación a este aspecto, se pudo concluir que nuestros algoritmos alcanzan en general, niveles similares de rendimiento con respecto al resto.