Metaheurística evolutiva híbrida para la minimización de cruces de las aristas en el dibujado de grafos

Abstract

La presente tesis muestra la implementación de diferentes metaheurísticas para el dibujado de grafos en el plano, con el propósito de lograr de manera eficiente, la minimización de los cruces de las aristas en el dibujado del grafo. Las aristas del grafo son líneas rectas. Entre las metaheurísticas utilizadas para lograr la minimización de cruces se encuentran el AGS (Algoritmo Genético Simple), el AEDMU (Algoritmo de Estimación de la Distribución Marginal Univariada) y el EC (Escalador de Colinas), así mismo, se realizaron cambios en el diseño original de las metaheurísticas buscando mejorar los resultados en la minimización. Dentro de la aportación que la presente tesis a dado a la investigación es un algoritmo híbrido llamado HUx que es una combinación entre el algoritmo AEDMU y el EC. El HUx ha demostrando ser más eficiente en la búsqueda de la solución óptima, que en nuestro caso es, aquel dibujado que tenga el número mínimo de cruces de las aristas del grafo, que el ECE, el AEDMU y los AGS. La medición de los resultados fue hecha utilizando diferentes grafos planares (con cero cruces entre sus aristas) y no planares (con al menos un cruce entre sus aristas), que fueron los sujetos de medición a los que se les aplicó las diferentes metaheurísticas. La calidad y la frecuencia de aparición de las soluciones óptimas registradas por el algoritmo HUx, fueron superiores a las registradas por los algoritmos contra los cuales se hizo esta medición y que forman parte del estado del arte, dentro del campo de dibujado de grafos. Cabe mencionar que en cada uno de los casos estudiados, la metaheurística híbrida HUx siempre encuentra el optimo para los grafos de prueba, además, la frecuencia de aparición del optimo es un 25% mayor que el segundo mejor algoritmo de todos los estudiados. Para la visualización de los grafos se desarrolló una interfase gráfica propia llamada MinX la cual muestra el resultado de cada grafo obtenido por las metaheurísticas implementadas en esta tesis.