DISEÑO DE UN NUEVO ALGORITMO OPTIMIZADOR BASADO EN EL ANÁLISIS DE LAS MEJORES CARACTERÍSTICAS Y OPERADORES DE MÚLTIPLES ALGORITMOS METAHEURÍSTICOS

Abstract

El constante desarrollo de nuevos algoritmos metaheurísticos ha llevado a una saturación en el campo de la búsqueda estocástica. Actualmente, existen cientos de algoritmos diferentes que pueden utilizarse para resolver cualquier problema. Para obtener un buen rendimiento, todo método metaheurístico necesita abordar un equilibrio satisfactorio entre la exploración y la explotación del espacio de búsqueda. Aunque la exploración y la explotación representan dos conceptos fundamentales en la metaheurística, las principales cuestiones sobre su combinación y equilibrio aún no se han comprendido del todo. La mayoría de los análisis existentes sobre técnicas metaheurísticas consideran únicamente la comparación de sus resultados finales, lo que no permite evaluar la naturaleza de un buen o mal equilibrio. Este trabajo presenta un análisis experimental que evalúa cuantitativamente el equilibrio entre exploración y explotación de varios de los algoritmos metaheurísticos más importantes y conocidos. En el estudio se utiliza una medida de diversidad dimensional para evaluar el equilibrio de cada esquema, considerando un conjunto representativo de 42 problemas de referencia que implican funciones multimodales, unimodales, compuestas y desplazadas. Como resultado, el análisis proporciona varias observaciones que permiten entender cómo afecta este equilibrio a los resultados en cada tipo de funciones, y qué equilibrio está produciendo mejores soluciones. De manera consecuente, mediante el análisis de la topología de las funciones de prueba actuales, se ha propuesto un índice empírico para evaluar la capacidad de exploración de los algoritmos metaheurísticos. El índice considera el número de veces que las soluciones de un enfoque metaheurístico alcanzan la región donde se encuentra el óptimo global. En el método propuesto, una solución ha alcanzado esta región si su valor de fitness supera el límite de fitness del óptimo local más significativo contenido en la función objetivo. Para probar su eficacia, se han comparado 11 algoritmos metaheurísticos en sus capacidades de exploración en funciones de optimización multimodales y desplazadas. Los resultados de la prueba permitieron una comparación directa del rendimiento de exploración entre las distintas metodologías, al tiempo que proporcionaron más información sobre el funcionamiento interno de los algoritmos probados. Inesperadamente, los resultados también desenmascararon un defecto preocupante que contienen muchos de ellos, el cuál es estudiado. Finalmente, en base al conocimiento generado en los análisis previos, se diseñan nuevos operadores de movimiento y se implementa en el algoritmo de Evolución Diferencial. El nuevo esquema integra un conjunto de operadores que analizan los efectos de exploración y explotación durante su funcionamiento. Con estos operadores, el nuevo método obtiene importantes conocimientos sobre la diversidad de su población durante su evolución. En estas condiciones, el método propuesto puede reducir su población cuando la diversidad es demasiado baja para reducir su coste computacional y mejorar sus capacidades de búsqueda simultáneamente. Para probar las nuevas incorporaciones, el algoritmo propuesto ha sido probado en un conjunto de 29 funciones complejas y dos problemas de diseño de trayectorias interplanetarias. El resultado de las pruebas demuestra un rendimiento muy mejorado en comparación con el algoritmo original de Evolución Diferencial, algunas de sus variantes más exitosas y otros algoritmos.