TESIS MAESTRÍA
Algoritmo de aceptación por umbral con aplicación de búsqueda local híbrida para el emparejamiento de peso máximo en un grafo.
Yessica Yazmín Calderón Segura
En este trabajo de investigación se desarrollaron cinco
estructuras de vecindad para el problema de emparejamiento de peso máximo, donde
cada una fue aplicada a una búsqueda local y a una búsqueda local iterada con la
finalidad de mejorar el desempeño del problema tratado. Una vez que se determinó
la mejor estructura de vecindad, se
implementó el algoritmo de aceptación por umbral, en donde se llevó a cabo un
análisis de sensibilidad para obtener la sintonización de todos los parámetros
de control del algoritmo. Una vez sintonizado el algoritmo, se llevó a cabo el
análisis de eficiencia y eficacia del algoritmo de aceptación por umbral con
búsqueda local híbrida para el problema de emparejamiento de peso máximo. El
análisis experimental realizado demostró que la estructura de vecindad con un
par aleatorio aplicada al algoritmo de aceptación por umbral es de mayor calidad
que la estructura de vecindad híbrida tanto en eficiencia como en eficacia.