Solución TSP: algoritmo de colonia de hormigas
Explicación detallada del principio y aplicación del algoritmo de colonia de hormigas
Principio y aplicación del algoritmo de colonia de hormigas 1 - Computación natural e inteligencia de enjambre
p>1. La optimización de colonias de hormigas (ACO) es un algoritmo de inteligencia de enjambre. Consiste en un grupo de individuos inteligentes o no inteligentes (Agentes), que exhiben un comportamiento inteligente a través de la cooperación mutua. resolviendo así problemas Los problemas complejos ofrecen nuevas posibilidades.
2. Es un algoritmo biónico inspirado en el comportamiento de búsqueda de alimento de las hormigas en la naturaleza. (Hormiga artificial; Experimento de puente doble)
3. Mecanismo operativo: cuando más y más hormigas pasan por un camino determinado, más y más rastros de feromonas quedarán atrás. Las hormigas posteriores elegirán la probabilidad de este camino. es mayor, lo que aumenta la intensidad de la feromona de este camino, y la intensidad de la feromona atraerá a más hormigas, formando así un mecanismo de retroalimentación positiva.
4. Dos principios importantes en el proceso de europeización del algoritmo de colonias de hormigas:
?a. Las reglas de selección para que las hormigas transfieran rutas entre muchos caminos.
b. Reglas globales de actualización de feromonas. La esencia de la actualización de feromonas es que las hormigas artificiales simulan cambios en la cantidad de feromonas reales en función de las feromonas dejadas y evaporadas por las hormigas reales en los bordes visitados, de modo que se puedan mejorar más las mejores soluciones. Esto forma el mecanismo de retroalimentación positiva del aprendizaje por refuerzo autocatalítico (ARL).
1. Descripción: El número de hormigas m; la matriz de feromonas entre ciudades; la ruta más corta BestLength de cada iteración de m ants la mejor ruta BestTour; Cada hormiga tiene: una tabla de acceso prohibido (Tabu), que se utiliza para almacenar las ciudades que han sido visitadas; una tabla de acceso permitido (Permitido), que se utiliza para almacenar las ciudades que aún son accesibles. Se utiliza una matriz (Delta) para almacenar las feromonas que libera en los caminos por los que pasa durante el ciclo (o iteración).
2. Probabilidad de transición de estado: durante el proceso de búsqueda, las hormigas calcularán la probabilidad de transición de estado en función de la cantidad de información de cada ruta y la información heurística de la ruta. La probabilidad de transición de estado de la hormiga k del elemento (ciudad) i al elemento (ciudad) j en el momento t:
τij (t): la cantidad de información en la ruta (i, j) en este momento . ηij=1/dij: función heurística.
α es el factor heurístico de la información, que representa la importancia relativa de la trayectoria y refleja el papel de la información acumulada por las hormigas en el movimiento de las hormigas. Cuanto mayor es el valor, más probable es que las hormigas. Si eligen los caminos recorridos por otras hormigas, más fuerte será la colaboración entre las hormigas.
β es el factor heurístico esperado, que indica la importancia relativa de la visibilidad y refleja la información heurística utilizada por las hormigas en su elección de caminos. durante su movimiento ( El papel en i, j). Cuanto mayor sea su valor, más cerca estará la probabilidad de transición de estado de este estado a la regla codiciosa;
3. Regla de actualización de feromonas:
ρ representa el coeficiente de volatilización de feromonas Δτij (t; ) representa el incremento actual de feromonas en la ruta (i, j) en el bucle, tiempo inicial Δτij(t)=0.
4. Tres métodos para calcular el incremento de feromonas:
Diferencia: El primer método utiliza información global y se actualiza después de caminar. Tanto el segundo como el tercer método utilizan información local. Generalmente se utiliza el primer método.
5. Diagrama de flujo en TSP