Un algoritmo de optimización de colonia de hormigas adaptativo para resolver el problema del viajante de comercio a gran escala
Autores: Tang, Kezong; Wei, Xiong-Fei; Jiang, Yuan-Hao; Chen, Zi-Wei; Yang, Lihua
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
Categoría
Matemáticas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 32
Citaciones: Sin citaciones
El algoritmo de colonia de hormigas enfrenta problemas de catástrofe dimensional al resolver el problema del viajante de comercio a gran escala, lo que conduce a una calidad de solución insatisfactoria y a una velocidad de convergencia. Para resolver este problema, se propone una optimización de colonia de hormigas adaptativa para el problema del viajante de comercio a gran escala (AACO-LST). Primero, AACO-LST mejora la regla de transferencia de estado para que se ajuste de forma adaptativa con la evolución de la población, acelerando así su velocidad de convergencia; luego, se utiliza el operador 2-opt para optimizar localmente la parte de las rutas de hormigas mejoradas para mejorar aún más la calidad de la solución del algoritmo propuesto. Finalmente, las reglas de actualización de feromonas adaptativas construidas pueden mejorar significativamente la eficiencia de búsqueda y evitar que el algoritmo caiga en soluciones óptimas locales o estancamientos prematuros. La simulación basada en 45 instancias del problema del viajante de comercio muestra que AACO-LST mejora la calidad de la solución en un 79% en comparación con el sistema de colonia de hormigas (ACS), y en comparación con otros algoritmos, el PE de AACO-LST no es más del 1% y el no es más del 2%, lo que indica que AACO-LST puede encontrar soluciones de alta calidad con alta estabilidad. Finalmente, se probó la velocidad de convergencia del algoritmo propuesto. Los datos muestran que la velocidad promedio de convergencia de AACO-LST es más del doble que la del algoritmo de comparación. El código relevante se puede encontrar en la página de inicio de nuestro proyecto.
Descripción
El algoritmo de colonia de hormigas enfrenta problemas de catástrofe dimensional al resolver el problema del viajante de comercio a gran escala, lo que conduce a una calidad de solución insatisfactoria y a una velocidad de convergencia. Para resolver este problema, se propone una optimización de colonia de hormigas adaptativa para el problema del viajante de comercio a gran escala (AACO-LST). Primero, AACO-LST mejora la regla de transferencia de estado para que se ajuste de forma adaptativa con la evolución de la población, acelerando así su velocidad de convergencia; luego, se utiliza el operador 2-opt para optimizar localmente la parte de las rutas de hormigas mejoradas para mejorar aún más la calidad de la solución del algoritmo propuesto. Finalmente, las reglas de actualización de feromonas adaptativas construidas pueden mejorar significativamente la eficiencia de búsqueda y evitar que el algoritmo caiga en soluciones óptimas locales o estancamientos prematuros. La simulación basada en 45 instancias del problema del viajante de comercio muestra que AACO-LST mejora la calidad de la solución en un 79% en comparación con el sistema de colonia de hormigas (ACS), y en comparación con otros algoritmos, el PE de AACO-LST no es más del 1% y el no es más del 2%, lo que indica que AACO-LST puede encontrar soluciones de alta calidad con alta estabilidad. Finalmente, se probó la velocidad de convergencia del algoritmo propuesto. Los datos muestran que la velocidad promedio de convergencia de AACO-LST es más del doble que la del algoritmo de comparación. El código relevante se puede encontrar en la página de inicio de nuestro proyecto.