Resumen de Diseño, implementación y evaluación de nuevos algoritmos evolutivos para problemas dinámicos
Yesnier Bravo
Los problemas de optimización dinámicos (DOP) están fuera del alcance del algoritmo evolutivo (EA) estándar debido al problema de la convergencia , en la medida en que convergen a un único punto del espacio de búsqueda, ellos pierden la diversidad necesaria para reaccionar y adaptarse después de un cambio en el problema. Pero a pesar de no estar directamente enfocados en problemas dinámicos, los EA también ofrecen muchas ventajas (simplicidad, robustez, paralelismo natural, etc.) que se pueden aprovechar en optimización dinámica si se diseñan métodos eficientes y eficaces para eliminar tales limitaciones. Esta es la motivación principal de los investigadores en el campo de la optimización dinámica evolutiva (EDO) y de la presente tesis doctoral.
Esta investigación abordó el diseño, implementación y evaluación de nuevos AE para DOP, explorando y contribuyendo en la tres grandes áreas de desafíos actuales: ● Estudios metodológicos, ● Creación de fundamentos y ● Aplicaciones a problemas dinámicos reales.
En primer lugar, estudiamos los algoritmos paralelos distribuidos (dEA). Dicho modelo descentraliza la población en islas que evolucionan en paralelo e intercambian información mediante migraciones . Hemos demostrado cómo diferentes políticas de migración pueden ayudar a diseñar mejores dEA, capaces de lograr un equilibrio entre la convergencia (adaptarse rápidamente a los movimientos de los óptimos) y la especiación (búsqueda de múltiple subóptimos al mismo tiempo). Con ello se confirma la importancia de perseguir múltiples valores subóptimos en la optimización dinámica. Además, los resultados presentados en estos estudios cierran algunas brechas en la comprensión del comportamiento de dEA y, en general, todos los enfoques multi-poblacionales para DOP que intercambian algún tipo de información entre las subpoblaciones.
También desde el desafío metodológico, estudiamos otro de los métodos muy utilizados para enfrentarse a DOP, los métodos que usan memoria global , con el fin de almacenar soluciones que luego son usadas para perseguir el óptimo. Dos aspectos claves en el diseño de estos métodos son el reemplazo y la recuperación de las soluciones de la memoria. Nuestro estudio, basado en un número representativo de criterios, de forma independiente y combinados también, descubrió cuál la efecto de cada estrategia en el rendimiento del EA en DOP. Cuando se probaron varias estrategias combinadas (muy común en esquemas de memoria reciente) se demostró que el orden en que se combinan las estrategias de memoria es importante. Especialmente la contribución a la diversidad de la memoria resultó ser una prioridad en el diseño de algoritmo, en contraposición con algunas implementaciones existentes. Estas implementaciones pudieran ahora beneficiarse de nuestro estudio para diseñar mejores algoritmos basados en memoria.
En esta tesis doctoral también desarrollamos fundamentos teóricos, enfrentando otro de los desafíos actuales en EDO. Nosotros redefinimos el concepto de takeover time , una métrica muy usada para medir presión selectiva en optimización estática, que no tenía una noción clara EDO. Esto es porque el takeover time depende directamente de la mejor solución de la población y, en un DOP, la “mejor solución” cambia continuamente. No solo definimos el concepto de takeover time , también desarrollamos modelos matemáticos para calcular su valor, siendo esto otra de las cuestiones de investigación que nos planteamos. Nuestros modelos tienen en cuenta tanto características del EA como del DOP. Lo cual tiene mucha aplicación en EDO, como herramienta para conocer mejor los métodos actuales y cómo influyen sus parámetros y los del problema en el rendimiento de estos.
Los modelos de takeover time propuestos permiten diseñar nuevos métodos adaptativos, capaces de ajustar el comportamiento del algoritmo de acuerdo con la dinámica de cambio experimentada. De hecho, en nuestra investigación no solo definimos el concepto y proponemos modelos de takeover para DOP, sino que también los usamos para construir un nuevo EA para EDO, denominado meEAμm . Este algoritmo se basa en los modelos de takeover para ajustar el operador de mutación y así controlar la convergencia del del EA a lo largo de la ejecución, adaptándose a distintos periodos y severidades de cambio en un DOP. Los resultados han validado las ventajas del nuevo algoritmo sobre el método de generar diversidad después de un cambio.
Por último, también en esta tesis abordamos el tercer gran desafío en EDO, relacionado con el desarrollo de aplicaciones para DOP reales de nuestras ciudades. Por un lado, hemos desarrollado el sistema HITUL, para la optimización de los semáforos de una ciudad. Este problema es inherentemente dinámico, por los continuos cambios de la intensidad vehicular en la red de carreteras. No obstante, en este primer acercamiento no aplicamos directamente los nuevos algoritmos propuestos, sino que está más relacionado con el trabajo futuro, que en gran medida ya se ha iniciado para seguir trabajando en las líneas de impacto claras de aplicación real que se derivan de esta tesis.
Además, iniciamos la implementación de una plataforma para la resolución de problemas DOP reales de transportación y movilidad inteligente y abordamos el uso del vehículo compartido en tiempo real (c arpooling dinámico). Este sistema facilita compartir un automóvil con otras personas que viajan en la misma dirección, y ayudan así a reducir los atascos y las emisiones de CO 2 al reducir el número de coches en la red vial. La aplicación que estamos desarrollando asigna personas y vehículos de forma óptima, en un contexto inherentemente dinámico de la demanda de pasajeros. En esta investigación en curso hacemos una interpretación de algunas fundamentos desarrollados como parte de nuestra investigación y que tienen una aplicación directa en escenarios reales, tales como la noción de takeover time .
En resumen, hemos trabajado durante el tiempo de tesis en dotar a la investigación y a los resultados software de un realismo y usabilidad reales. Esto no es visible en publicaciones aún, pero nos está permitiendo desarrollar una aplicación para posible transferencia al mercado industrial en el dominio de la movilidad inteligente en entornos urbanos. Este trabajo futuro es ya una realidad hoy en día al momento de la defensa, arrojando resultados de mucho interés.
Esperamos en poco tiempo tras la defensa de esta tesis doctoral estar en condiciones de explotar esto, ya que algunas empresas están interesadas en tal producto, permitiendo una transferencia universidad-empresa y teoría-práctica ideal como punto final a todo este trabajo.
