Wk 4-5 Swarm Intelligence (ACO)

Question 1

Swarm Intelligence

Answer 1

Each element of the swarm has its own simple
behaviour, and a set of rules for interacting with
its fellows, and with the environment.

There is no central
controller.

Question 2

Deneubourg et al (1989) Double Bridge Experiment

Answer 2

◼ Ants observed over time
◼ To begin with - random choices of path
◼ Later, one path taken by most ants

2nd experiment
◼ shortest path selected by most ants

Question 3

Stigmergy

Answer 3

indirect communication via interaction with the
environment

-Sematonic
-Sign-based

Question 4

Sematonic stigmergy

Answer 4

The actions of an agent directly impact problem-solving and influence the behavior of other agents. ( example position itself in a place )

It describes a decentralized coordination mechanism where agents communicate and coordinate their actions indirectly through modifications they make to their shared environment.

Question 5

Sign-based stigmergy

Answer 5

The actions of agents in sign-based stigmergy directly modify the environment by leaving signs, markers, or signal but these actions are not directly related to problem-solving activities.

Question 6

Ants

Answer 6

sophisticated sign-based stigmergy:
– They communicate using pheromones;
– They lay trails of pheromone that can be followed by other ants.

Question 7

Pheromone Trails

Answer 7

Individual ants lay pheromone trails while travelling.

The pheromone trail gradually evaporates over time.

The trail strength accumulates with multiple ants
using the same path as Ants prefer paths with more pheromone on them.

Question 8

Ant Colony Optimisation Algorithms

Answer 8

Ants = agents that move along between nodes in a graph

They choose where to go based on pheromone strength

An ant’s path represents a specific candidate solution.

When an ant has finished a solution, pheromone is laid on its path,according to quality of solution.

This affects behaviour of other ants by `stigmergy’

Question 9

probabilistic state transition rule

Answer 9

for each ant the transition from city I to j at iteration t depends on :
- if the city has been visited already
- local hearistic ( 1/d_ij) desirability of visiting j while in i
- global amount of pheromone on the trail

Question 10

Updtae rule

Answer 10

• after the tour each ant k lays pheromone on its path
• phermone is Q/L (fitness) quantity / length of path ?
• pheromone evaporates (1-p)*t t = n tour at this iteration

Question 11

Ant colony optimization algorithms variants:

Answer 11

Basic Ant System (AS) (1996) original

Variants update the pheromone trails differently :
– Max-Min Ant System ( using only the best ants)
– Elitist Rank Ant System (the best n ants)