Classical swarm intelligence Flashcards
Explain the binary bridge experiment
The binary bridge experiment is a biological model for Argentine ants. The ants are situated on one side of a canyon, a food source on the other and a bridge with two paths connect them.
When the ants walk across the bridge they deposit pheromones that dictates where other ants will walk by a given likelihood. This means that they all eventually converge on taking one path, but some still might use the path with less pheromones. The likelihood is directly correlated to the pheromone concentration.
- when paths are equal length they converge to a random path
- when one path is longer they converge to the shorter because of higher pheromone concentration
- when a shorter path is added after the long is established as path, they might end up on using the shorter by chance and eventually build up enough pheromones to redirect, or they just continue using the longer path
a) Explain the ant colony optimization metaheuristic algorithm
b) What type of problems are ACO especially applicable to?
c) Name one of these problems
a)
- Set parameters to initialize pheromone trails
- Ants walk along edges, guided by pheromone concentraitions
- Update pheromones based on trail length and number of ants on said trail
b) ACO is good for combinatorial organization problems
c) One example is the Traveling salesman problem (TSP)
Explain the pheromone update rule in AS
Ants walk a path and each trail in that path calculates how much pheromone should be deposited. Based on formula
T
Explain the transition rule (probability of going to node j) in AS
The transition rule is a probability based on length of trail and amount of pheromones on trail. Pheromones times by the inverse of the length divided by the sum of all options (directions). This gives
a) Explain the Canonical Particle Swarm optimization metahueristic algorithm
b) What type of problems are PSO especially applicable to?
a) What is taxis?
b) Explain how taxis could be an inspiration for swarm robotics
a) A taxis is an innate behavioral response and is the movement of an organism in response to a stimulus. F.ex. thermo-, photo- or chemotaxis
b) As in E.coli algorithm, or beeclust. Because the movement (emergent behavior) is useful for search when the gradient is not easily calculated.
What is Artificial Potential Field?
APFs are repulsive force fields created around obstacles and perimeter of an environment. Agents sense this forcefield and calculates potential field force to avoid areas or objects. Can be tuned on-line.
