Algoritmo genético para el problema del viajante de comercio con operador de cruce de ciclos modificado
Autores: Abid, Hussain; Yousaf Shad, Muhammad; M., Nauman Sajid; Ijaz, Hussain; Alaa, Mohamd Shoukry; Showkat, Gani
Idioma: Inglés
Editor: Hindawi
Año: 2017
Acceso abierto
Artículo científico
Categoría
Ingeniería y Tecnología
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 14
Citaciones: Sin citaciones
Los algoritmos genéticos son técnicas evolutivas utilizadas con fines de optimización según la idea de la supervivencia del más apto. Estos métodos no aseguran soluciones óptimas; sin embargo, dan una buena aproximación generalmente en el tiempo. Los algoritmos genéticos son útiles para problemas NP-duros, especialmente el problema del viajante de comercio. El algoritmo genético depende de los criterios de selección y de los operadores de cruce y mutación. Para abordar el problema del viajante de comercio mediante algoritmos genéticos, existen varias representaciones como la binaria, la de caminos, la de adyacencia, la ordinal y la matricial. En este artículo, proponemos un nuevo operador de cruce para el problema del viajante de comercio para minimizar la distancia total. Este enfoque se ha vinculado con la representación del camino, que es la forma más natural de representar un recorrido legal. También se reportan resultados computacionales con algunos métodos tradicionales de representación de recorridos como los cruces parcialmente mapeados y de orden junto con el nuevo operador de cruce de ciclos para algunas instancias de referencia de TSPLIB y se encuentran mejoras.
Descripción
Los algoritmos genéticos son técnicas evolutivas utilizadas con fines de optimización según la idea de la supervivencia del más apto. Estos métodos no aseguran soluciones óptimas; sin embargo, dan una buena aproximación generalmente en el tiempo. Los algoritmos genéticos son útiles para problemas NP-duros, especialmente el problema del viajante de comercio. El algoritmo genético depende de los criterios de selección y de los operadores de cruce y mutación. Para abordar el problema del viajante de comercio mediante algoritmos genéticos, existen varias representaciones como la binaria, la de caminos, la de adyacencia, la ordinal y la matricial. En este artículo, proponemos un nuevo operador de cruce para el problema del viajante de comercio para minimizar la distancia total. Este enfoque se ha vinculado con la representación del camino, que es la forma más natural de representar un recorrido legal. También se reportan resultados computacionales con algunos métodos tradicionales de representación de recorridos como los cruces parcialmente mapeados y de orden junto con el nuevo operador de cruce de ciclos para algunas instancias de referencia de TSPLIB y se encuentran mejoras.