Algoritmo de colonia de hormigas

13

Soy un estudiante que trabaja en un simulador de colonias de hormigas para un proyecto de curso. El algoritmo para ello es (obviamente) un algoritmo de colonia de hormigas. Sé que hay varias formas del algoritmo, pero todas ellas fueron demasiado detalladas matemáticamente para nosotros, así que tomamos un enfoque en el que tenemos:

  • Una hormiga nace en una colonia y debe recolectar alimentos de una fuente para sostener la colonia.
  • Todas las hormigas son similares.
  • El área en la que se mueve la hormiga es una cuadrícula de 1000x1000, por lo que cada punto de la cuadrícula sirve como un punto válido para que ocupe una hormiga. Ahora, todos los algoritmos con los que me he topado implican tratar los vértices y los bordes por separado, pero como estamos restringiendo el movimiento de las hormigas a solo cuatro direcciones (arriba, abajo, izquierda, derecha), creo que no importa dónde pongamos la feromona.
  • Los puntos de la rejilla mencionados anteriormente almacenan la feromona.
  • Una hormiga cae feromona solo si lleva comida.
  • Para una hormiga en una posición (i, j), decide dónde moverse en el siguiente paso teniendo en cuenta las cantidades de feromonas en sus cuatro nodos adyacentes en una fórmula probabilística simple, es decir. la probabilidad de viajar a un nodo viene dada por (cantidad de feromonas en un nodo adyacente particular) / (suma de cantidades de feromonas en 4 nodos adyacentes).
  • Una hormiga no puede regresar a la posición de la que vino. Solo puede hacerlo si está en un sitio que tiene comida o está en su colonia.

Ahora mi preocupación (y lo que realmente está sucediendo en nuestro programa) es que cuando una hormiga PRIMERA alcanza una posición que tiene comida y la recoge, entonces, por la forma en que funciona nuestro algoritmo, ¡puede moverse a cualquier parte! Esto se debe a que solo dejará un rastro de feromonas, una vez que tenga la comida y no antes, y como es la primera hormiga, no hay rastro existente.

Si la hormiga puede moverse a cualquier lugar, las hormigas que alcanzan la fuente de alimento después de que también tenderán a seguirla en su mayor parte. INCLUSO SI no se está moviendo hacia la colonia. Esto anula el propósito de todo el algoritmo.

Así que mis preguntas son

  • ¿Es válida la preocupación anterior? Si no, entonces ¿por qué? Si es así, entonces, ¿cómo lidiar con eso?
  • ¿Necesitamos hacer algunos cambios en nuestra comprensión básica del algoritmo para que realmente funcione?
  • ¿Cuáles son algunas otras cosas sutiles pero importantes que los novatos como yo pueden extrañar en este caso?
pregunta transistor 13.04.2015 - 20:16

2 respuestas

6

No es así como funciona ACO. ACO solo suelta feromonas después de que las hormigas se han movido a través de todos los puntos de la cuadrícula. Luego evalúa algo (quizás el tiempo total de viaje) y luego suelta feromonas para detectar buenas hormigas, y repite.

En general, no se mueven al mismo vértice dos veces, aunque puede personalizar esto para la especificidad de la implementación.

Las feromonas no se eliminan con cada movimiento, se caen después de moverse a todas partes y se evalúa algo para determinar qué hormigas son mejores. Las hormigas que son mejores entonces dejan caer las fereomonas (quizás las mejores hormigas con un 25% de rendimiento).

    
respondido por el enderland 13.04.2015 - 20:49
1

Las implementaciones que he visto de otros, y las que he escrito para mí, siempre han hecho que las hormigas liberen las feromonas en el camino que viajaron para llegar a la comida, una vez que han alcanzado la comida. Es decir, las hormigas marchan de su colonia a la comida siguiendo una caminata aleatoria; los caminos seguidos por las hormigas de la colonia a la comida se marcan utilizando las feromonas solo después de que las hormigas lograron llegar a la comida. El viaje de regreso no se simula explícitamente. En general, varias hormigas siguen su curso antes de que se depositen las feromonas para la iteración actual. Las feromonas se implementan para las rutas exitosas, y comienza una nueva ronda.

Por lo general, las probabilidades de la hormiga de ingresar a un nodo determinado son ponderadas por la cantidad de feromonas multiplicada por cierta medida de "bondad". Por ejemplo, la medida de bondad podría ser algo así como la inversa de la distancia entre la hormiga y el alimento: esto hará que las hormigas intenten avanzar hacia el alimento, independientemente de los depósitos de feromonas anteriores. La bondad podría ponderarse aún más para tener en cuenta otros factores, por ejemplo, Algunos nodos pueden ser más fáciles de atravesar que otros. Y como señala Enderland, normalmente hay algún tipo de "selección" de ruta una vez que todas de las hormigas han realizado sus cursos con éxito, donde solo una parte de las "mejores" rutas se eligen para el depósito de feromonas. Sin embargo, aún debe obtener rutas razonables incluso sin selección, siempre y cuando su elección de "bondad" tenga sentido.

    
respondido por el Eric Greenwood 13.04.2015 - 22:27

Lea otras preguntas en las etiquetas