Desarrollo de un software de aplicación de algorítmos genéticos al problema de la diligencia

Abstract

El trabajo de tesis consiste en la construcción de un software implementando un AG, para resolver el problema de la diligencia (PD') así como de la evaluación del conjunto de resultados que reporte el mismo, dividiéndose ésta en evaluación de precisión y de eficacia del algoritmo. En la primera evaluación se pone a prueba un conjunto de valores para los parámetros del AG y en la segunda se confronta el AG con los mejores parámetros elegidos con los algoritmos analíticos Dijkstra y Floyd. Al aplicar pruebas estadísticas a un nivel de confianza del 95% resultó que los mejores parámetros para precisión del AG son: 200 individuos, 100 iteraciones, 90% de cruzamiento, 5% de mutación. Para determinar cuál es el algoritmo que consume menos tiempo, nuevamente se realizaron pruebas estadísticas a un nivel de confianza del 95%, donde se determinó que el algoritmo de Dijkstra es el que mejor resuelve el problema. Además, parece interesante hacer notar que uno de los valores que no fueron muy significativos con respecto a los resultados estadísticos fue el porcentaje de la cantidad de aristas que se trazaron en cada problema y esto se debe a que en el caso de los algoritmos analíticos exploran en todas las alternativas, y en el caso del algoritmo genético utiliza igual número de bits para resolver el problema. Es importante mencionar que el AG tiene como principal ventaja con respecto a los algoritmos analíticos que puede hallar soluciones alternativas.