LIBRARY REPOSITORY

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

Show simple item record

dc.contributor.author Enríquez Aranda, Sergio es_MX
dc.date.accessioned 2016-06-14T16:01:18Z
dc.date.available 2016-06-14T16:01:18Z
dc.date.issued 2009-06
dc.identifier.other 318629
dc.identifier.uri http://hdl.handle.net/11317/584
dc.description Tesis (maestría en ciencias exactas, sistemas de la información: área de inteligencia artificial)--Universidad Autónoma de Aguascalientes. Centro de Ciencias Básicas. es_MX
dc.description.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. es_MX
dc.format pdf
dc.language es
dc.publisher Universidad Autónoma de Aguascalientes es_MX
dc.publisher Universidad Autónoma de Aguascalientes es_MX
dc.subject Algoritmos es_MX
dc.subject Análisis númerico es_MX
dc.title Metaheurística evolutiva híbrida para la minimización de cruces de las aristas en el dibujado de grafos es_MX
dc.type Tesis es_MX


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Repository


Advanced Search

Browse

My Account