¿Dónde puedo obtener más información sobre la optimización de "colonia de hormigas"?

Question

He estado leyendo cosas aquí y allá durante un tiempo sobre el uso de una "colonia de hormigas". modelo como un enfoque heurístico para optimizar varios tipos de algoritmos. Sin embargo, todavía tengo que encontrar un artículo o libro que analice las optimizaciones de colonias de hormigas de manera introductoria, o incluso con muchos detalles. ¿Alguien puede señalarme algunos recursos donde pueda obtener más información sobre esta idea?

Answer 1

En caso de que sepa alemán (sí, lo siento & # 8230;), un amigo y yo hemos escrito un introducción con código sobre este tema que yo mismo considero bastante aceptable. El texto y el código utilizan el ejemplo de TSP para presentar el concepto.

Incluso si no sabe alemán, eche un vistazo al código y las fórmulas en el texto, esto aún podría servir.

Answer 2

enlace Wikipedia realmente me ayudó a comenzar. Leí el artículo y me puse a codificar. Estaba resolviendo una variación perversa del problema del vendedor ambulante. Es un metaheurístico asombroso. Básicamente, cualquier tipo de problema de búsqueda que se pueda poner en un gráfico (nodos y bordes, simétricos o no) se puede resolver con un ACO.

Esté atento a la diferencia entre los rastros de feromonas globales y locales. Las feromonas locales desalientan a una generación de hormigas a atravesar el mismo camino. Evitan que el modelo converja. Las feromonas globales son atrayentes y deberían enganchar al menos una hormiga por generación. Fomentan caminos óptimos durante varias generaciones.

La mejor sugerencia que tengo es simplemente jugar con el algoritmo. Configure un solucionador de TSP básico y una visualización básica de colonias. Entonces diviértete un poco. Trabajar con hormigas, conceptualmente, es genial. Usted programa sus comportamientos básicos y luego los suelta. Incluso me encariñé con ellos. :)

Los ACO son una forma más codiciosa de algoritmos genéticos. Jugar con ellos. Altere sus comportamientos comunicativos y el comportamiento del paquete. Rápidamente comenzará a ver la programación de red / gráfica de una manera completamente diferente. Ese es su mayor beneficio, no la receta que la mayoría de la gente ve.

Solo tienes que jugar con él para entenderlo realmente. Libros y amperios; Los trabajos de investigación solo dan una comprensión general altísima. Como una bicicleta, solo tienes que empezar a montar. :)

Los ACO, con mucho, son mi abstracción favorita para problemas de gráficos.

Answer 3

National Geographic escribió un artículo interesante hace un tiempo hablando de algunos de las teorías.

Answer 4

El mejor recurso para estos temas es Google scholar . He estado trabajando en algoritmos de optimización de colonias de hormigas durante un tiempo, aquí hay algunos buenos documentos:

• Optimización de colonias de hormigas: una nueva metaheurística
• Optimización de colonias de hormigas: hormigas artificiales como técnica de inteligencia computacional

Solo busque " Ant Colony " en google académico .

Además, busque artículos publicados por Marco Dorigo .

Answer 5

Me sorprende que nadie haya mencionado la biblia de ACO:

Marco Dorigo & amp; Thomas St & # 252; tzle: Optimización de colonias de hormigas

Este libro está escrito por el autor de ACO y es muy legible. Puedes llevarlo a la playa y divertirte leyéndolo. Pero también es el recurso más completo de todos, excelente como referencia al implementar la cosa.

Puede leer algunos extractos en Google Books

Otra gran fuente de sabiduría es la ACO Homepage

Answer 6

Vea, por ejemplo, este artículo en scholarpedia.

También hay discusión aquí en el ¿Cuál es la forma más eficiente de encontrar una ruta a través de un pequeño gráfico mundial? pregunta.

Answer 7

A primera vista, esto parece estar estrechamente relacionado con (o quizás un caso especial de) el Algoritmo de metrópolis . Esa es otra posible dirección para buscar.

Adición: Este archivo PDF incluye una referencia al artículo original de Metropolis de 1953.

Answer 8

Bueno, encontré la página de inicio de Eric Rollins y sus diferentes implementaciones (Haskell, Scala, Erlang, ...) de un algoritmo ACO útil. Y también el libro de Enrique Alba, titulado "Metaheurística paralela: una nueva clase de algoritmos". donde puede encontrar un capítulo completo de explicación sobre los algoritmos ACO y sus diferentes usos.

Hth