OPTIMIZACIÓN DE RUTA CORTA USANDO ALGORITMO GENÉTICO GENERACIONAL

Raúl Huarote Zegarra, Hilario Aradiel Castañeda, Jhony Valverde Flores

Resumen


El presente artículo de investigación tiene como objetivo utilizar algoritmo genético generacional, propio de la inteligencia artificial, donde se aprovecha el proceso evolutivo para optimizar el recorrido de los n puntos o nodos, a un coste de computador menor. Una de las ventajas de este método evolutivo es que no compiten todos contra todos, sino que se crea y procesa una porción de la población total, con el objetivo de encontrar la posible mejor ruta, o también llamada búsqueda local. Se ha considerado para el método de la ruleta, cruce por intercambio de 2 puntos, mutación por intercambio y método de parada de acuerdo a la cantidad de generaciones. En un computador de regular característica se logró implementar el algoritmo genético generacional en lenguaje Matlab 8.3, tomando como ejemplo las distancias de cada ciudad. Se obtuvieron como resultados para n puntos o nodos, en cada evaluación, las posibles mejores rutas basándose en el modelo evolutivo. Las pruebas realizadas desde 100 hasta 1000 ciudades resultaron en tiempos de 3,2006 s y 27,924 s, respectivamente. De acuerdo al conjunto de pruebas, demuestra un incremento de manera polinómica de nivel 2; por lo que esta investigación se centra en el incremento de los dos métodos de parada a una secuencia lineal.

Texto completo:

PDF

Enlaces refback

  • No hay ningún enlace refback.


ISSN 2304-8891

Publicación electrónica realizada por el Repositorio Digital de la Universidad Nacional Jorge Basadre Grohmann - © UNJBG 2017