Estrategia de enfriamiento adaptativo para el algoritmo del recocido simulado

Résumé

El Recocido Simulado es una de las más importantes meta-heurísticas o algoritmos generales de optimización combinatoria existentes, siendo bien conocidas sus propiedades de convergencia hacia soluciones de alta calidad, aunque con un elevado coste computacional. Esto ha dado origen a numerosos trabajos de investigación sobre aceleración de la convergencia del algoritmo, especialmente en el tratamiento del parámetro de temperatura, mediante lo que se conoce como programas o estrategias de enfriamiento. Esta tesis tiene como objetivo diseñar una estrategia de enfriamiento adaptativo para el algoritmo del recocido simulado con el fin de reducir su coste computacional manteniendo la calidad de las soluciones. Para ello, en primer lugar se ha elaborado un estudio comparativo del comportamiento del recocido simulado respecto a varias estrategias de enfriamiento distintas, incluyendo la clásica propuesta por Kirkpatrick, Gelatt y Vecchi [KIRK83], así como otras más recientes. La nueva estrategia de enfriamiento propuesta se basa en el ajuste dinámico óptimo de dos parámetros de control del algoritmo: el valor inicial de la temperatura y el factor de decremento de la temperatura tras cada ciclo de enfriamiento. En el análisis práctico del nuevo algoritmo se usan dos problemas clásicos de optimización combinatoria: el problema del viajante comercial y el problema de la asignación cuadrática, evaluando el comportamiento de la estrategia de enfriamiento tanto respecto a la eficiencia temporal, como a la calidad de las soluciones. Adicionalmente, se propone como ejemplo de aplicación práctica del nuevo algoritmo un problema de optimización de ámbito empresarial: La selección óptima de carteras de inversión.