Optimización de ruta corta en el espacio sin corte lineal con algoritmo genético

Abstract

Esta investigación tuvo como objetivo encontrar la ruta más corta de n puntos en el espacio, sin corte o intersección entre las líneas generadas por los caminos. Para lograr esto, se usó el algoritmo genético, donde se aprovechó la ventaja de no competir “todos contra todos”, sino que a partir de una pequeña población puede encontrarse la posible mejor ruta en el espacio, también llamada “búsqueda local”. Para realizar el proceso evolutivo, se consideró el método de la ruleta, cruce por intercambio de 2 puntos, mutación por intercambio y método de parada a la varianza a 25 generaciones. Implementado en Matlab 8.3, se obtuvo como resultado una duración de 24.7 s y 210.6 s, con funciones de adaptación de 0.79 y 0.76, 76 y 206 generaciones a las pruebas realizadas de 10 y 100 puntos, respectivamente. Demostrando que con el algoritmo genético se encontró la posible mejor ruta corta de n puntos en el espacio y que el método de parada ideal para este problema en particular es la varianza, aunque consuma más tiempo frente cantidad de generaciones establecidas.