Swarm Intelligence: Concepts and Applications

Swarm

Intelligence

Outline

•

Background

o

What is a Swarm Intelligence (SI)?

o

Examples from nature

o

Origins and Inspirations of SI

•

Ant Colony Optimization

•

Particle Swarm Optimization

What is a Swarm?

•

A loosely structured collection of interacting

agents

o

Agents:

•

Individuals that belong to a group (but are not necessarily

identical)

•

They contribute to and benefit from the group

•

They can recognize, communicate, and/or interact with each

other

•

The instinctive perception of swarms is a group

of agents in motion – but that does not always

have to be the case.

•

A swarm is better understood if thought of as

agents exhibiting a collective behavior

Swarm Intelligence (SI)

•

An artificial intelligence (AI) technique based

on the collective behavior in decentralized,

self-organized systems

•

Generally made up of agents who interact

with each other and the environment

•

No centralized control structures

•

Based on group behavior found in nature

Examples of Swarms in

Nature:

•

Classic Example:  Swarm of Bees

•

Can be extended to other similar systems:

o

Ant colony

•

Agents: ants

o

Flock of birds

•

Agents: birds

o

Traffic

•

Agents: cars

o

Crowd

•

Agents: humans

o

Immune system

•

Agents: cells and molecules

Two Common SI

Algorithms

 Inspiration from swarm intelligence has led to some

highly successful optimisation algorithms.

o

Ant Colony (-based) Optimisation 

– a way to solve

optimisation problems based on the way that ants

indirectly communicate directions to each other

.

o

Particle Swarm Optimisation 

— a   different way to

solve optimisation problems, based on the

swarming behaviour of several kinds of organisms.

Biologically Inspired

Computation

Ant Colony Optimisation

Ant Colony

Optimization (ACO)

•

The study of artificial systems modeled after

the behavior of real ant colonies and are

useful in solving discrete optimization problems

•

Introduced in 1992 by Marco Dorigo

o

Originally called it the Ant System (AS)

o

Has been applied to

•

Traveling Salesman Problem (and other shortest path

problems)

•

Several NP-hard Problems

•

It is a population-based metaheuristic used to

find approximate solutions to difficult

optimization problems

Overview

Overview

“

Ant Colony Optimization (ACO)

studies artificial systems that take

inspiration from the 

behavior of

real ant colonies

 and which are

used to solve discrete

optimization problems.”

-Source: ACO website, http://iridia.ulb.ac.be/~mdorigo/ACO/about.html

Artificial Ants

•

A set of software agents

•

Stochastic

•

Based on the pheromone model

o

Pheromones are used by real ants to mark paths.  Ants follow

these paths (i.e., trail-following behaviors)

•

Incrementally build solutions by moving on a

graph

•

Constraints of the problem are built into the

heuristics of the ants

A key concept:  Stigmergy

Stigmergy

 is:

indirect communication via interaction with the environment

.

•

A problem gets solved bit by bit ..

•

Individuals communicate with each other in the above way, affecting what

each other does on the task.

•

Individuals leave 

markers

 or 

messages

 – these don’t solve the problem in

themselves, but they affect other individuals in a way that helps them solve

the problem …

Naturally Observed Ant Behavior

All is well in the world of the ant.

Naturally Observed Ant Behavior

Oh no!

 An obstacle has blocked our path!

Naturally Observed Ant Behavior

Where do we go? Everybody, flip a coin.

Naturally Observed Ant Behavior

Shorter path reinforced.

Stigmergy in Ants

Ants are behaviorally unsophisticated, but

collectively they can perform complex tasks.

Ants have 

highly developed

sophisticated

sign

-

based

stigmergy

o

They communicate using pheromones;

o

They 

lay trails of pheromone

 that can be followed

by other ants.

•

If an ant has a 

choice of two pheromone trails

to follow, one to the NW, one to the NE, but the

NW one is 

stronger

 – which one will it follow?

Pheromone Trails

Individual ants lay pheromone trails while travelling

from the nest, to the nest or possibly in both

directions.

The pheromone trail gradually evaporates over time.

But pheromone trail strength accumulate with

multiple ants using path.

Initial state:

no ants

Ant Colony Optimisation

Algorithms: Basic Ideas

Ants are 

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 pheromone trail affects behaviour of other ants by

`stigmergy

’ …

Using ACO

•

The optimization problem must be written in the form

of a path finding problem with a weighted graph

•

The artificial ants search for “good” solutions by

moving on the graph

o

Ants can also build infeasible solutions – which could be helpful in solving

some optimization problems

•

The metaheuristic is constructed using three

procedures:

o

ConstructAntsSolutions

o

UpdatePheromones

o

DaemonActions

Construct

Ants

Solutions

•

Manages the colony of ants

•

Ants move to neighboring nodes of the graph

•

Moves are determined by stochastic local decision

policies based on pheromone t

r

ails and heuristic

information

•

Evaluates the current partial solution to determine the

quantity of pheromones the ants should deposit at a

given node

Update

Pheromones

•

Process for modifying the pheromone trails

•

Modified by

o

Increase

•

Ants deposit pheromones on the nodes (or the edges)

o

Decrease

•

Ants don’t replace the pheromones and they evaporate

•

Increasing the pheromones increases the

probability of paths being used (i.e., building

the solution)

•

Decreasing the pheromones decreases the

probability of the paths being used (i.e.,

forgetting)

Daemon

Actions

•

Used to implement larger actions that require

more than one ant

•

Examples:

o

Perform a local search

o

Collection of global information

Applications Of ACO

•

Vehicle routing with time window constraints

•

Network routing problems

•

Assembly line balancing

•

Heating oil distribution

•

Data mining

E.g. A 4-city TSP

A

B

C

D

Pheromone

 Ant

AB: 10,   AC: 10,   AD, 30,    BC, 40,    CD 20

Initially, random levels of pheromone are scattered on the edges

E.g. A 4-city TSP

A

B

C

D

Pheromone

 Ant

AB: 10,   AC: 10,   AD, 30,    BC, 40,    CD 20

An ant is placed at a random node

E.g. A 4-city TSP

A

B

C

D

Pheromone

 Ant

AB: 10,   AC: 10,   AD, 30,    BC, 40,    CD 20

The ant decides where to go from that node,

based on probabilities

calculated from:

  - pheromone strengths,

  - next-hop distances.

Suppose this one chooses BC

E.g. A 4-city TSP

A

B

C

D

Pheromone

 Ant

AB: 10,   AC: 10,   AD, 30,    BC, 40,    CD 20

 The ant is now at C, and has a `tour memory’ = {B, C} – so he cannot

 visit B or C again.

Again, he decides next hop

(from those allowed) based

on pheromone strength

and distance;

suppose he chooses

CD

E.g. A 4-city TSP

A

B

C

D

Pheromone

 Ant

AB: 10,   AC: 10,   AD, 30,    BC, 40,    CD 20

 The ant is now at D, and has a `tour memory’ = {B, C, D}

There is only one place he can go now:

E.g. A 4-city TSP

A

B

C

D

Pheromone

 Ant

AB: 10,   AC: 10,   AD, 30,    BC, 40,    CD 20

So, he has nearly finished his tour, having gone over the links:

BC, CD, and DA.

E.g. A 4-city TSP

A

B

C

D

Pheromone

 Ant

AB: 10,   AC: 10,   AD, 30,    BC, 40,    CD 20

So, he has nearly finished his tour, having gone over the links:

BC, CD, and DA. AB is added to complete the round trip.

Now, pheromone on the tour

is increased, in line with the

fitness of that tour.

E.g. A 4-city TSP

A

B

C

D

Pheromone

 Ant

AB: 10,   AC: 10,   AD, 30,    BC, 40,    CD 20

Next, pheromone everywhere

is decreased a little, to model

decay of trail strength over

time

E.g. A 4-city TSP

B

C

D

Pheromone

 Ant

AB: 10,   AC: 10,   AD, 30,    BC, 40,    CD 20

We start again, with another ant in a random position.

Where will he go?

 Next  , the actual algorithm

and variants.

A

The 

The 

ACO

ACO

 algorithm for the TSP

 algorithm for the TSP

We have a TSP, with 

n

 cities.

   1. We place some ants at each city. Each ant then does

this:

•

 It makes a complete tour of the cities, coming back to its starting city, using

a 

transition rule

 to decide which links to follow. By this rule, it chooses each

next-city at random, but based partly by the pheromone levels existing at

each path, and based partly by 

heuristic information

.

    2. When all ants have completed their tours.

Global  Pheromone Updating

 occurs.

•

The current pheromone levels on all links are reduced (I.e. pheromone levels

decay over time).

•

Pheromone is lai

d

 (belatedly) by each ant as follows: it places pheromone

on all links of its tour, with strength depending on how good the tour was.

The 

The 

ACO

ACO

 algorithm for the TSP

 algorithm for the TSP

[a simplified version with all essential details]

[a simplified version with all essential details]

We have a TSP, with 

n

 cities.

   1. We place some ants at each city. Each ant then does

this:

•

 It makes a complete tour of the cities, coming back to its starting city, using

a 

transition rule

 to decide which links to follow. By this rule, it chooses each

next-city at random, but biased partly by the pheromone levels existing at

each path, and biased partly by 

heuristic information

.

    2. When all ants have completed their tours.

Global  Pheromone Updating

 occurs.

•

The current pheromone levels on all links are reduced (I.e. pheromone levels

decay over time).

•

Pheromone is lain (belatedly) by each ant as follows: it places pheromone

on all links of its tour, with strength depending on how good the tour was.

   Then we go back to 1 and repeat the whole process

many times, until we reach a termination criterion.

ACO Algorithm

Set all parameters and initialize the pheromone trails

Loop

Sub-Loop

Construct solutions based on the state transition rule

Apply the online pheromone update rule

Continue until all ants have been generated

Apply Local Search

Evaluate all solutions and record the best solution so far

Apply the offline pheromone update rule

Continue

 until the stopping criterion is reached

41

ACO System, cont.

•

Often applied to TSP (Travelling Salesman

Problem):  shortest path between n nodes

•

Algorithm in Pseudocode:

o

Initialize

 Trail

o

Do While

 (Stopping Criteria Not Satisfied) – Cycle Loop

•

Do Until

 (Each Ant Completes a Tour) – Tour Loop

•

Local Trail Update

•

End Do

•

Analyze Tours

•

Global Trail Update

o

End Do

Ant Systems Algorithm for TSP

Initialize

Place each ant in a randomly chosen city

Choose NextCity(For Each Ant)

more cities

 to visit

For Each Ant

Return to the initial cities

Update pheromone level using the tour cost for each ant

Print Best tour

yes

No

Stopping

criteria

yes

No

43

44

45

46

47

48

C

h

a

r

a

c

t

e

r

i

s

t

i

c

s

o

f

t

h

e

a

l

g

o

r

i

t

h

m



A

n

a

n

t

i

s

a

s

o

l

u

t

i

o

n

.



S

o

l

u

t

i

o

n

s

(

a

n

t

s

)

a

r

e

a

t

d

i

f

f

e

r

e

n

t

p

l

a

c

e

s

i

n

t

h

e

s

o

l

u

t

i

o

n

s

p

a

c

e

.



H

o

w

t

h

e

y

c

h

a

n

g

e

i

s

b

a

s

e

d

o

n

t

h

e

p

r

o

b

a

b

i

l

i

t

y

o

f

c

h

a

n

g

i

n

g

t

o

a

d

i

f

f

e

r

e

n

t

s

c

h

e

d

u

l

e

.



A

n

a

n

t

c

o

m

p

l

e

t

e

s

i

t

s

t

o

u

r

a

f

t

e

r

s

e

l

e

c

t

i

o

n

a

c

h

o

i

c

e

f

o

r

e

a

c

h

s

t

a

n

d

.



U

t

i

l

i

t

i

e

s

(

o

b

j

e

c

t

i

v

e

f

u

n

c

t

i

o

n

v

a

l

u

e

s

)

o

f

e

a

c

h

t

o

u

r

a

r

e

c

a

l

c

u

l

a

t

e

d

.



P

h

e

r

o

m

o

n

e

l

e

v

e

l

s

a

r

e

u

p

d

a

t

e

d

a

f

t

e

r

a

l

l

o

f

t

h

e

a

n

t

s

h

a

v

e

c

o

m

p

l

e

t

e

d

a

l

l

o

f

t

h

e

i

r

t

o

u

r

s

.

A

n

t

C

o

l

o

n

y

O

p

t

i

m

i

z

a

t

i

o

n

C

h

a

r

a

c

t

e

r

i

s

t

i

c

s

o

f

t

h

e

a

l

g

o

r

i

t

h

m

T

h

e

p

r

o

b

a

b

i

l

i

t

y

o

f

m

o

v

i

n

g

f

r

o

m

P

o

i

n

t

A

t

o

P

o

i

n

t

B

d

e

p

e

n

d

s

o

n

t

h

e

a

t

t

r

a

c

t

i

v

e

n

e

s

s

o

f

t

h

e

m

o

v

e

a

n

d

t

h

e

t

r

a

i

l

l

e

v

e

l

.

A

t

t

r

a

c

t

i

v

e

n

e

s

s

-

a

n

a

p

r

i

o

r

i

d

e

s

i

r

a

b

i

l

i

t

y

(

t

y

p

i

c

a

l

l

y

b

a

s

e

d

o

n

t

h

e

i

n

v

e

r

s

e

d

i

s

t

a

n

c

e

)

o

f

t

h

e

m

o

v

e

.

T

r

a

i

l

l

e

v

e

l

-

a

n

a

p

o

s

t

e

r

i

o

r

i

,

c

o

m

p

u

t

e

d

a

t

t

r

a

c

t

i

v

e

n

e

s

s

.

T

h

i

s

i

s

c

o

m

p

u

t

e

d

a

f

t

e

r

a

n

a

n

t

c

o

m

p

l

e

t

e

s

a

s

o

l

u

t

i

o

n

,

i

n

c

r

e

a

s

i

n

g

o

r

d

e

c

r

e

a

s

i

n

g

t

h

e

d

e

s

i

r

a

b

i

l

i

t

i

e

s

o

f

c

o

m

p

o

n

e

n

t

s

o

f

a

s

o

l

u

t

i

o

n

.

A

n

t

C

o

l

o

n

y

O

p

t

i

m

i

z

a

t

i

o

n

A

B

C

?

C

h

a

r

a

c

t

e

r

i

s

t

i

c

s

o

f

t

h

e

a

l

g

o

r

i

t

h

m

A

m

o

u

n

t

s

o

f

p

h

e

r

o

m

o

n

e

s

a

r

e

u

p

d

a

t

e

d

a

f

t

e

r

a

s

o

l

u

t

i

o

n

h

a

s

b

e

e

n

g

e

n

e

r

a

t

e

d

.

(

1

-

p

)

p

r

i

o

r

p

h

e

r

o

m

o

n

e

+



p

h

e

r

o

m

o

n

e

W

h

e

r

e

:

p

=

a

c

o

e

f

f

i

c

i

e

n

t

r

e

l

a

t

e

d

t

o

t

h

e

e

v

a

p

o

r

a

t

i

o

n

r

a

t

e

.

i

f

A



B

p

a

t

h

i

s

u

s

e

d

,

p

h

e

r

o

m

o

n

e

l

e

v

e

l

s

i

n

c

r

e

a

s

e



p

h

e

r

o

m

o

n

e

=

Q

/

L

k

W

h

e

r

e

:

Q

=

a

c

o

n

s

t

a

n

t

L

k

=

s

o

l

u

t

i

o

n

l

e

n

g

t

h

(

q

u

a

l

i

t

y

)

E

l

s

e

p

h

e

r

o

m

o

n

e

l

e

v

e

l

s

d

e

c

r

e

a

s

e

,

s

i

n

c

e

i

n

t

h

i

s

c

a

s

e



p

h

e

r

o

m

o

n

e

=

0

A

n

t

C

o

l

o

n

y

O

p

t

i

m

i

z

a

t

i

o

n

A

B

C

?

A

d

v

a

n

t

a

g

e

s

:

•

I

t

i

s

i

n

t

u

i

t

i

v

e

t

o

b

i

o

l

o

g

i

c

a

l

l

y

-

m

i

n

d

e

d

p

e

o

p

l

e

,

m

i

m

i

c

k

i

n

g

n

a

t

u

r

e

.

•

T

h

e

s

y

s

t

e

m

i

s

b

u

i

l

t

o

n

p

o

s

i

t

i

v

e

f

e

e

d

b

a

c

k

(

p

h

e

r

o

m

o

n

e

a

t

t

r

a

c

t

i

o

n

)

a

n

d

n

e

g

a

t

i

v

e

a

t

t

r

a

c

t

i

v

e

n

e

s

s

(

p

h

e

r

o

m

o

n

e

e

v

a

p

o

r

a

t

i

o

n

)

.

•

P

h

e

r

o

m

o

n

e

e

v

a

p

o

r

a

t

i

o

n

h

e

l

p

s

a

v

o

i

d

c

o

n

v

e

r

g

e

n

c

e

t

o

a

l

o

c

a

l

o

p

t

i

m

a

.

D

i

s

a

d

v

a

n

t

a

g

e

s

:

•

F

o

r

r

o

u

t

i

n

g

p

r

o

b

l

e

m

s

i

t

m

a

y

m

a

k

e

m

o

r

e

s

e

n

s

e

,

b

u

t

f

o

r

h

a

r

v

e

s

t

s

c

h

e

d

u

l

i

n

g

p

r

o

b

l

e

m

s

,

i

t

r

e

q

u

i

r

e

s

a

c

o

n

c

e

p

t

u

a

l

l

e

a

p

o

f

f

a

i

t

h

.

•

F

i

n

e

-

t

u

n

i

n

g

t

h

e

s

e

n

s

i

t

i

v

e

p

a

r

a

m

e

t

e

r

s

m

a

y

r

e

q

u

i

r

e

s

i

g

n

i

f

i

c

a

n

t

e

f

f

o

r

t

.

A

n

t

C

o

l

o

n

y

O

p

t

i

m

i

z

a

t

i

o

n

N

e

c

e

s

s

a

r

y

p

a

r

a

m

e

t

e

r

s

1

)

T

h

e

i

n

i

t

i

a

l

p

o

p

u

l

a

t

i

o

n

o

f

a

n

t

s

(

a

n

a

n

t

c

y

c

l

e

)

.

2

)

T

h

e

t

o

t

a

l

n

u

m

b

e

r

o

f

t

o

u

r

s

.

3

)

T

h

e

e

v

a

p

o

r

a

t

i

o

n

r

a

t

e

.

4

)

T

h

e

a

m

o

u

n

t

o

f

p

h

e

r

o

m

o

n

e

a

p

p

l

i

e

d

t

o

a

s

e

c

t

i

o

n

o

f

a

c

y

c

l

e

o

r

s

o

l

u

t

i

o

n

.

5

)

T

h

e

c

o

n

s

t

a

n

t

Q

.

A

n

t

C

o

l

o

n

y

O

p

t

i

m

i

z

a

t

i

o

n

Methodology

The transition rule

is the amount of pheromone currently on the path that goes

   directly from city 

i

to city 

j

.

is the heuristic value of this link – in the classic TSP

   application, this is chosen to be 1/distance(

i

,

j

)  -- 

i

.e. the shorter

   the distance, the higher the heuristic value.

is the probability that ant  

k 

will choose the link that goes

           from 

i

 to 

j

State Transition Probability

:

Where our ant is at city 

i

, 

and 

j

is a city as yet unvisited on its

tour, and the summation is over all of 

k

’s unvisited cities

Generate initial ants

Assess the quality of the

ant tours

For all ants,

develop an ant tour

Stop and report

the best solution

found during search

      Has the

  best solution

been improved?

  Have we

reached the

  stopping

  criteria?

No

Save best solution

Yes

Change probabilities of

pieces of each

potential tour

Yes

No

B

a

s

i

c

P

r

o

c

e

s

s

A

n

t

C

o

l

o

n

y

O

p

t

i

m

i

z

a

t

i

o

n

Update pheromone levels

A 

A 

simple

simple

 TSP example

 TSP example

A

E

D

C

B

d

A

B

=

1

0

0

;

d

B

C

=

6

0

…

;

d

D

E

=

1

5

0

Iteration 1

Iteration 1

A

E

D

C

B

Iteration 2

Iteration 2

A

E

D

C

B

Iteration 3

Iteration 3

A

E

D

C

B

Iteration 4

Iteration 4

A

E

D

C

B

Iteration 5

Iteration 5

A

E

D

C

B

E

n

d

o

f

F

i

r

s

t

R

u

n

A

l

l

a

n

t

s

d

i

e

N

e

w

a

n

t

s

a

r

e

b

o

r

n

S

a

v

e

B

e

s

t

T

o

u

r

(

S

e

q

u

e

n

c

e

a

n

d

l

e

n

g

t

h

)

67

ACO algorithms for TSP

•

Ant System

•

Elitist Ant System

•

Rank-based Ant System

•

Ant Colony System

•

MAX-MIN Ant System

68

Ant System: Pheromone

initialization

•

Pheromone initialization

Τ

ij

 = m 

/

 C

nn

,

where:



m – number of ants



C

nn

 – path length of nearest-neighbor algorithm

69

Ant System: Tour construction

•

Ant 

k

 is located in city 

i

•

       is the neighborhood of city 

i

•

Probability to go to city 

:

70

Tour construction: comprehension

•

α

 = 0 – greedy algorithm

•

β

 = 0 – only pheromone is at work



quickly leads to stagnation

71

Ant System: update pheromone

trails

 – 

evaporation

Evaporation for all connections

∀

(

i

, 

j

) 

∈ 

L

:

τ

ij

← (1 – 

ρ

) 

τ

ij

,

ρ 

∈

[0, 1] – evaporation rate

Prevents convergence to suboptimal solutions

72

Ant System: update pheromone

trails

 – 

deposit

•

T

k

– path of ant 

k

•

C

k

 – length of path T

k

•

Ants deposit pheromone on visited arcs:

73

Elitist Ant System

•

Best-so-far ant deposits pheromone on each

iteration:

74

Rank-based Ant System

•

Another improvement over AS.

•

Each ant deposits an amount of pheromone

that decreases with its rank.

•

In each iteration, only the best (w-1) ranked ants

and the best-so-far ant are allowed to deposit

pheromone.

75

MAX-MIN Ant System

1.

Only iteration-best or best-so-far ant deposits

pheromone

2.

Pheromone trails are limited to the interval [

τ

min,

τ

max

]

76

Ant Colony System

•

Differs from Ant System in three points:



More aggressive tour construction rule



Only best ant evaporates and deposits pheromone



Local pheromone update

77

Ant Colony System

1.

Tour Construction

2.

 Local pheromone update:

τ

ij

 ← (1 – 

ξ

)

τ

ij

 + 

ξτ

0

,

A

n

t

-

Q

&

A

n

t

C

o

l

o

n

y

S

y

s

t

e

m

(

A

C

S

)

Local Updating

  (Online Updating)

Global Updating

  (Offline Updating)

Exploitation

Exploration

Not just for TSP of course

ACO is naturally applicable to any sequencing

problem, or indeed 

any

 problem

All you need is some way to represent solutions to the

problem as paths in a network.

E.g.

Single machine scheduling with due-dates

These jobs have to be done; their length represents

the time they will take.

A

B

C

D

E

E.g.

Single machine scheduling with due-dates

These jobs have to be done; their length represents

the time they will take.

A

B

C

D

E

Each has a `due date’, when it needs to be finished

3pm

3:30pm

5pm

4pm

4:30pm

E.g.

Single machine scheduling with due-dates

These jobs have to be done; their length represents

the time they will take.

A

B

C

D

E

Each has a `due date’, when it needs to be finished

3pm

3:30pm

5pm

4pm

4:30pm

Only one `machine’ is

available to process these jobs,

so can do just one at a time.

[e.g. machine might be

human tailor, photocopier,

Etc …]

An example schedule

A due 3pm

B – 3:30

C - 5pm

D – 4pm

E -4:30

2 pm

3 pm

5 pm

4 pm

6 pm

A is 10min late                          Fitness might be average lateness;

B is 40min late                           in this case 46min

C is 20min early (lateness = 0)

D is 90min late                           or fitness could be Max lateness,

E is 90min late                           in this case 90min

Another schedule

A due 3pm

B – 3:30

C - 5pm

D – 4pm

E -4:30

2 pm

3 pm

5 pm

4 pm

6 pm

A is 70min late                          Fitness might be average lateness;

B is 30min early (0 lateness)                    in this case again 46min

C is 60min late

D is 50min late                           or fitness could be Max lateness,

E is 50min late                           in this case 70min

Applying ACO to this

problem

Just like with the TSP, each ant finds paths in a

network, where, in this case, each job is a node.

Also, no need to return to start node – path is

complete when every node is visited.

A

B

C

D

Initially, random levels of pheromone are scattered on the edges,

an ant starts at a 

Start

 node (so the first link it chooses defines

the first task to schedule on the machine); as before it uses a

transition rule

to take one step at a time, biased by pheromone levels,

and also a heuristic score, each time choosing the next machine

to schedule.

E

Start

•

http://iridia.ulb.ac.be/dorigo/ACO/ACO.htm

l

See here if you’re very interested in ACO:

ACO is a thriving and maturing research area – it has its own

conferences. It gets very good results on some difficult problems.

Following the above link will help you find examples.

ACO research and practice tends to concentrate on:

•

 hybridisation with other methods; e.g. it is common to

  improve an individual ant’s solution by local search, and then

  lay pheromone.

•

 New and adaptive ways to control the relative influence of

  heuristics, pheromone strength and pheromone decay.

Resources



Ant Colony Optimization

 by Marco Dorigo and Thomas

St

ϋ

tzle, The MIT Press, 2004



Swarm Intelligence

 by James Kennedy and Russell Eberhart

with Yuhui Shi, Morgan Kauffmann Publishers, 2001



Advances in Applied Artificial Intelligence

 edited by John

Fulcher, IGI Publishing, 2006



Data Mining: A Heuristic Approach

 by Hussein Abbass,

Ruhul Sarker, and Charles Newton, IGI Publishing, 2002



“Ant Colony Optimization” Curatored by Marco Dorigo,

http://www.scholarpedia.org/article/Ant_Colony_Optimizat

ion



“Ant Colony Optimization”  by Marco Dorigo,

http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.htm;



“Particle Swarm Optimization”

http://www.swarmintelligence.org



“Swarm Intelligence”

http://en.wikipedia.org/wiki/Swarm_intelligence



Picture of Flik, http://www.pixar.com