TESIS MAESTRÍA
Solución al Problema del árbol de Expansión Mínima aplicando Recocido Simulado con Búsqueda Tabú
Beatriz Martínez Bahena
En este trabajo de investigación se desarrolló un algoritmo de Recocido Simulado con Lista Tabú para tratar instancias del problema del árbol de Expansión Mínima. Se generó una estructura de vecindad híbrida, con la finalidad de mejorar el desempeño del algoritmo. Se utilizó una metodología de sintonización, la cual permitió realizar el análisis de sensibilidad de los parámetros de control del algoritmo Recocido Simulado, lo que permite trabajar al algoritmo con mejor desempeño tanto en eficiencia como en eficacia. El análisis de resultados se llevó a cabo en base a pruebas de eficiencia y eficacia de las estructuras de vecindad propuestas, ejecutándose éstas en un algoritmo de búsqueda local iterada. Los resultados del análisis mostraron que la estructura híbrida es la que trabaja con mejor eficacia y en eficiencia fue competitiva, en base a estos resultados se implementó la estructura híbrida en el algoritmo de Recocido Simulado. También se aplicó a esta meta heurística una lista tabú, lo que permitió mejorar aún más la eficacia del mismo al incrementar el tamaño de la lista tabú y de igual manera se generó un aumento en la eficiencia. Las pruebas experimentales se realizaron tomando cuatro instancias del problema del árbol de expansión mínima generadas de forma aleatoria. Las pruebas experimentales del algoritmo fueron realizadas en equipo del laboratorio de Optimización del CIICAp.