Region-based memetic algorithms for global and multimodal continuous optimisation

Resumen

Esta tesis se centra en el estudio y el diseño de algoritmos meméticos (AMs) para optimización continua. Esta investigación se inicia con el estudio de la cooperación entre los componentes de búsqueda global (BG) y la búsqueda local (BL) del AM, y conduce a la propuesta de una nueva estrategia de nichos denominada estrategia de nichos basada en regiones (region-based niching). A partir de dicha propuesta de nichos, se han desarrollado una nueva familia de AMs, denominados AMs basados en regiones. La originalidad de esta estrategia se basa en dividir el espacio de búsqueda en hipercubos de igual tamaño denominados regiones que definen los límites de cada nicho. Cuando es incluído dentro de un AM, se mantiene de tal modo la diversidad que se garantiza una más adecuada exploración del espacio de búsqueda. El objetivo es ofrecer una más controlada separación entre el componente de BL y el de BG para mantener las tareas de exploración y explotación lo más separadas posibles, y mejorar así la eficiencia de la búsqueda. Cuando se incluye dentro del AM, esta estrategia al ofrecer una separación más clara entre exploración y explotación: - Se fuerza al algoritmo de búsqueda global a realizar una búsqueda entre regiones para garantizar que el espacio de búsqueda global se explora suficientemente. - Al forzar al algoritmo de exploración local a realizar la búsqueda intra-region (dentro de cada región) se asegura que las regiones más prometedoras identificadas por la BG sean explotadas de forma adecuada. AM basado en regiones ha sido aplicado a dos tipos de problemas: - Problemas de optimización global, en los que se busca identificar un único óptimo global de la función objetivo. Los resultados ofrecidos para este tipo de problemas muestran ser muy competitivos con las técnicas del estado-del-arte. - Problemas de optimización multimodal, en los que se busca identificar y preserver múltiples óptimos globales de la función objetivo, es decir, obtener un conjunto amplio de soluciones satisfactorias. La definición de nichos mediante regiones permiten incluir en nuestro modelo un archivo compuesto por un índice de regiones excluídas de seguir explorándose, reduciendo el espacio de búsqueda y por tanto mejorando la eficiencia de la misma. El algoritmo resultante ofrece una mejor exploración y resultados con mayor precisión que algoritmos existentes.