Un estudio de las técnicas de híbridación y su aplicación al diseño de algoritmos evolutivos

Resumen

Cualquier algoritmo de búsqueda esta inherentemente limitado si una clase lo suficientemente amplia de problemas es considerada, Como resultado se comprueba que es necesario incluir conocimiento del problema dentro del algoritmo de optimización si se desea que este se comporte de manera adecuada en diferentes dominios. Esta inclusión de conocimiento del problema se denomina hibridación, presentándose una visión dicotómica de la misma. Así, se distingue entre hibridación fuerte (adición de conocimiento en el interior del algoritmo) e hibridación débil (combinación de diferentes algoritmos de búsqueda). Estos modelos de hibridación se formalizan mediante los conceptos de sistema adaptativo y sistema adaptativo granulado respectivamente. Un análisis de la potencia computacional de ambos sistemas demuestra que ambos tienen la misma potencia expresiva, proponiéndose emplear hibridación fuerte en primera instancia y usar la hibridación débil como mecanismo adicional para mejorar el rendimiento de algoritmos híbridos fuertes. El proceso de diseñar un algoritmo híbrido fuerte es caracterizado como un problema de optimización combinatoria, demostrándose que su resolución es NP-dura. Por ello se proponen dos heurísticos de diseño: emplear operadores que manipulen formas de baja varianza en su adecuación y usar representaciones no homogéneas. Del mismo modo, se proponen dos heurísticos para la definición de algoritmos híbridos débiles: la combinación de búsquedas heterogéneas débilmente acopladas y la recombinación óptima de formas. Todos los heurísticos presentados son evaluados sobre una serie de casos de estudio que cubren un amplio rango de problemas. Un último aspecto considerado es la detección del estancamiento del algoritmo, la cual se enfoca mediante un criterio probabilístico que estudia la topología del espacio de búsqueda mediante un algorítmo de escalada estocástica inversa.