Adaptación de visibilidad en la optimización de colonias de hormigas para resolver el problema del vendedor viajero
Autores: Shahadat, Abu Saleh Bin; Akhand, M. A. H.; Kamal, Md Abdus Samad
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Adaptación de visibilidad en la optimización de colonias de hormigas para resolver el problema del vendedor viajero
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Optimización de colonias de hormigas
Aco
Problema del viajante de comercio
Tsp
Visibilidad adaptativa
Algoritmo bioinspirado
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 24
Citaciones: Sin citaciones
La optimización de colonias de hormigas (ACO) es un algoritmo práctico y bien estudiado inspirado en la biología para generar soluciones factibles a problemas de optimización combinatoria como el Problema del Viajante de Comercio (TSP). ACO se inspira en el comportamiento de búsqueda de las hormigas, donde una hormiga selecciona la siguiente ciudad a visitar según la feromona en el rastro y la heurística de visibilidad (inversa de la distancia). ACO asigna una mayor deseabilidad heurística a la ciudad más cercana sin considerar el problema de regresar a la ciudad inicial o punto de partida una vez que se han visitado todas las ciudades. Este estudio propone un método mejorado basado en ACO, llamado ACO con Visibilidad Adaptativa (ACOAV), que adopta inteligentemente una fórmula generalizada de la heurística de visibilidad asociada con la ciudad de destino final. ACOAV utiliza una nueva métrica de distancia que incluye la proximidad y el destino eventual para seleccionar la siguiente ciudad. Incluir el destino en la métrica reduce el costo del recorrido porque dicha adaptación ayuda a evitar el uso de enlaces más largos al regresar a la ciudad de inicio. Además, se incorporan actualizaciones parciales de soluciones individuales y operaciones de búsqueda local 3-Opt en el ACOAV propuesto. ACOAV se evalúa en un conjunto de 35 instancias de referencia de TSP y se compara rigurosamente con ACO. ACOAV genera mejores soluciones para TSP que ACO, mientras que requiere menos tiempo de computación; tales logros dobles indican la eficacia de las técnicas de adopción individual en ACOAV, especialmente en AV y actualización parcial de soluciones. El rendimiento de ACOAV también se compara con otros diez métodos bioinspirados de vanguardia, incluidos varios métodos basados en ACO. De estas evaluaciones, se encuentra que ACOAV es el mejor para 29 instancias de TSP de 35; entre ellas, se han logrado soluciones óptimas en 22 instancias. Además, las pruebas estadísticas que comparan el rendimiento revelaron la importancia del ACOAV propuesto sobre los métodos bioinspirados considerados.
Descripción
La optimización de colonias de hormigas (ACO) es un algoritmo práctico y bien estudiado inspirado en la biología para generar soluciones factibles a problemas de optimización combinatoria como el Problema del Viajante de Comercio (TSP). ACO se inspira en el comportamiento de búsqueda de las hormigas, donde una hormiga selecciona la siguiente ciudad a visitar según la feromona en el rastro y la heurística de visibilidad (inversa de la distancia). ACO asigna una mayor deseabilidad heurística a la ciudad más cercana sin considerar el problema de regresar a la ciudad inicial o punto de partida una vez que se han visitado todas las ciudades. Este estudio propone un método mejorado basado en ACO, llamado ACO con Visibilidad Adaptativa (ACOAV), que adopta inteligentemente una fórmula generalizada de la heurística de visibilidad asociada con la ciudad de destino final. ACOAV utiliza una nueva métrica de distancia que incluye la proximidad y el destino eventual para seleccionar la siguiente ciudad. Incluir el destino en la métrica reduce el costo del recorrido porque dicha adaptación ayuda a evitar el uso de enlaces más largos al regresar a la ciudad de inicio. Además, se incorporan actualizaciones parciales de soluciones individuales y operaciones de búsqueda local 3-Opt en el ACOAV propuesto. ACOAV se evalúa en un conjunto de 35 instancias de referencia de TSP y se compara rigurosamente con ACO. ACOAV genera mejores soluciones para TSP que ACO, mientras que requiere menos tiempo de computación; tales logros dobles indican la eficacia de las técnicas de adopción individual en ACOAV, especialmente en AV y actualización parcial de soluciones. El rendimiento de ACOAV también se compara con otros diez métodos bioinspirados de vanguardia, incluidos varios métodos basados en ACO. De estas evaluaciones, se encuentra que ACOAV es el mejor para 29 instancias de TSP de 35; entre ellas, se han logrado soluciones óptimas en 22 instancias. Además, las pruebas estadísticas que comparan el rendimiento revelaron la importancia del ACOAV propuesto sobre los métodos bioinspirados considerados.