L7 - Swarm Optimisation : Ant Colony Flashcards
Define Swarm Intelligence
Refers to the phenomenon that natural swarms of animals, such as ants and birds, act more intelligently than any individual of the swarm.
Define what is meant by individuals in a Swarm, and what they are capable of doing…
They are single units that make up the swarm, and alone they are incapable of doing ( or doing efficiently ) some task X.
Define what is meant by a Swarm, and how it improves on individuality…
A swarm is a group of individuals that act more intelligently than any one individual. This is known as the Emergent Property.
Swarms consist of individuals making simple, local interactions which collectively acts as a method for making complicated, intelligent decisions.
What is an Emergent Property?
The property of a swarm that means the swarm can do a task X more efficiently than any individual of the swarm.
Explain how ant scavenging behaviour is an example of a swarm with the emergent property.
Individually, ants can’t find a close to optimal route to the food source. However, as a swarm, the emergent property enables them to find an solution ( path ) to the food that is leaning towards optimum.
Explain how Ant Colony Optimisation works?
This is an algorithm based on ants behaviour of finding the optimal route to food source.
Ants use stigmergy via a pheromone to lay down scents on the paths to a food source. The paths accumulate the pheromone over time. Ants are drawn to paths with the strongest pheromone, an the paths that are travelled in quicker shuttles are logically shorter, thus accumulate pheromones quicker. This results in ants naturally converging to taking the shorter path to the food source.
Define Stigmergy… What are the 2 types?
The process of indirect communication between individuals via communication with the environment.
Sematonic : Action of the agent is directly related to solving the problem, and the behaviour of the agent influences the behaviour of the other agents. For example, an ant might position itself in a way to motivate other ants to take a certain action.
Sign-based : Action of agent is not directly related to solving the problem, and the action effects the environment. For example, ants releasing pheromones when moving.
What type of stigmergy do ants use for establishing optimal route to a food source?
Sign based stigmergy.
Give the basic idea for using ACO to solve the TSP…
- Ants move between nodes in the graph.
- A solution is a unique path of the ant
- After a path ( solution ) is established, the strength of the solution is established via a pheromone weight.
- Probability of other ants taking this path is based on the solution strength ( pheromone weight ).
