Swarm Intelligence

Swarm Intelligence for  Optimisation Problems ACAT 2002 Moscow Bruce Denby LISIF, Paris, France   [email protected]

 

Sylvie Le Hégarat CETP, Vélizy, France [email protected]

Introduction • In 1959 entomologist Pierre­Paul Grassé  showed that the behaviour of certain species of  mound­building termites could be explained by  a set of simple rules                   termite mound:

 

 

Nest Building Algorithm: Bellicositermes Natalensis • • • •

Make masticated pulp balls and carry them about Drop them on raised, open areas when possible Sniff out existing piles and stick yours on top If tower gets too high: – Go elsewhere if no other pile  in sniffing distance – Else, attach ball in direction  of nearest neighbouring pile

➨  Result : complex termite nest structures  

 

Swarm Intelligence • Scientists have found similar behaviours in other  social insects as well:  bees, wasps, ants…                                             Honeybee ‘Figure 8’                                                  Waggle Dance                                          ­ Waggle axis codes                                                   direction w/resp to sun                                                ­ Length and intensity                                                  of waggle codes                                                  distance to nectar source  

 

Swarm Intelligence • Since the early 1990’s, a significant amount of  work has been done using social insect­inspired  algorithms to solve both ‘toy’ and ‘real’  problems • There are yearly international conferences on  swarm intelligence of various types ­ e.g.  ANTS'2002 ­ From Ant Colonies to Artificial  Ants: Third International Workshop on Ant  Algorithms, Brussels, 11­14 Sept. 2002  

 

Swarm Intelligence • Applications:  TSP, quadratic assignment, graph  colouring, optimisation, network routing, cluster  finding, job scheduling, search engines, load  balancing, etc.     • Much of the work was performed using variants  of Ant Colony Optimisation (ACO) • ACO researchers:  Schoonderwoerd, Holland,  Dorigo, di Caro, Bonabeau, Théraulauz,  Deneuborg, etc. ...  

 

Ant Colony Optimisation • The most straightforward analogy of ACO is in  ‘routing’ problems • While searching for food, ants deposit trails of  pheromones which attract other ants

 

 

Ant Colony Optimisation • Shorter paths to food are traversed more quickly  and have a better chance of being reinforced by  other ants before the volatile pheromones  evaporate • Using pheromones and random search procedures  the colony thus rapidly finds the shortest paths to  food • Illustrative Example:  ACO for Routing in a  Satellite Network (E. Sigel, B. Denby, S. Le Hégarat,  to appear in Annals of Telecommunications, 2002)  

 

ACO Routing for a Satellite Network • di Caro, Dorigo, and others  showed that ACO gives good  performance for routing in  large scale telecom and  computer networks • We adapted the ‘Dorigo’ algorithm to routing  in a network of 72 LEO satellites • ACO was found to give performance superior   to a ‘standard’ routing algorithm, SPF  

The Satellite Network Model • 72 LEO satellites in 9 orbits of radius 1603 km • 50 o equatorial inclination; min. elevation 17.5 o • Orbital period 118.5 minutes; satellite footprint 5100  km diameter • Each satellite has 155 Mbits/s up & downlink  transceivers and four 155.5 Mbits/s bi­directional  intersatellite links (ISL) to communicate with 2 nearest  inter­ and intra­orbit neighbors.  • Earth's surface (Mercator projection) divided in 12 ×  24 grid with a single gateway handling all the traffic of  the cell    

 

 

The Traffic Model 12 10 8 traffic (% of the 6 whole day traffic) 4

voice

2 0

0

5

10 15 time (h)

20

25

5.5 5 4.5 4 3.5 3 2.5 2 1.5 1 0.5

data 0

5

   10

  15 time (h)

20

Temporal dependence of voice and data traffic expressed as a percentage versus time of day over 24 hours.  

 

25

Traffic Levels for Gateways: Projection 2005 60

30

latitude (degrees)

0

­30

­60

­90 ­180

­120

­60

0

60

120

180

longitude (degrees)

Grey scale:  1: 0.41 call/s, 2: 1.62 call/s, 3: 4.06 call/s,      4: 8.12  call/s,  5:  24.1 call/s, 6: 48.4   call/s, 7: 60.6 call/s, 

Communication Establishment Probabilities destination →

North America

Europe

Asia

South America

Africa

Oceania

North America

85 (74)

4 (18)

4 (2)

3 (2)

2 (2)

2 (2)

Europe

4 (24)

85 (68)

4 (2)

3 (2)

3 (2)

1 (2)

Asia

5 (24)

5 (18)

83 (52)

1 (2)

2 (2)

4 (2)

South America

7 (24)

7 (18)

2 (2)

81 (52)

2 (2)

1 (2)

Africa

5 (24)

7 (18)

4 (2)

2 (2)

81 (52)

1 (2)

Oceania

5 (24)

2 (18)

7 (2)

1 (2)

1 (2)

84 (52)

source

Values for voice (data) as a function of geographic  location of source and destination nodes.  Percentages  sum to 100% left to right.  

 

Simulation Scenarios I

II

III

traffic model

system voice load (Gbits/s)

low

2.24

data sessions per hour per gateway 50000

normal

2.24

intermed.

IV

V

packets % of 10× per data augmented session data sessions

VI

VII

system data load (Gbits/s)

system total load (Gbits/s)

2000

­

1.08

3.32

100000

2000

­

2.15

4.39

2.24

100000

3000

­

3.23

5.47

high

2.24

100000

4000

­

4.30

6.54

packet

­

100000

4000

­

4.30

4.34

bursty I

2.24

100000

2000

10

2.15

4.39

bursty II

2.24

100000

2000

50

2.15

4.39

bursty III

2.24

100000

2000

75

2.15

4.39

 

 

Baseline Ant Routing Algorithm • Once every 100 ms, each satellite node emits an  ant with a random destination. • The ant follows the routing tables to the  destination, except for a 1% ‘exploration’  probability, waiting in queues and memorising  trip times en route. • When the destination is reached, it follows the  same path back, jumping all queues, and updating  routing tables along the way.   

 

Ts, Ti, Tj, Tk Ts, Ti, Tj

Tj →d ∀d

P i

s    d

T

{T}

s  

 d

P T

{T}  

s

T

d

k

{T}

±δPjdk(Tj­Td, Tj→d) (Tj­Td) j

s   d

Ts

T

Pjdn ∀d;n∈Nj

d s   

d

s   

P d s   

Ts, Ti

P s   d

Ant Routing Algorithm: Conceptual

KEY:

s   d

:  s→d  ant

:  update

{Tj →d ∀d}:  mean j→d trip time table {Pjdn ∀d; n∈Nj}:  node j routing table

           for destination d, neighborhood N

j

Ant Routing Table Update  Algorithm • First calculate r = min{T/(); 1} where T is  the current ant trip time and  is the mean  time for the path in question • Next, modify the probability of the link that is  part of the ant's path according to       Pant ISL = Pant ISL + (1­r)(1­ Pant ISL) • and decrement the other three ISL's as            PISL(i) = PISL(i) ­ (1­r) PISL(i)  

 

Improvements to Baseline ACO • Two  generic  improvements  to  'baseline'  ACO  are cited in the literature: • Replacing  r  by  a  so­called  'squashed'  value  rs  (s here was chosen to be 0.2). • Using  the  'fuzzy'  routing  technique  of  the  ant  packets for normal data packets as well.

• Results presented are 'squashed'/'fuzzy' ACO  • Improvement  with  ‘fuzzy’  routing  is  not  without  cost,  as  it  leads  to  increased  packet  fragmentation  

 

Geographic distribution of packet delays 60

30

latitude (degrees)

packet delays (ms)

0

­30

­60

­90 ­180

­120

­60

0

longitude (degrees)

60

120

180

Values for 'normal' traffic &'baseline' ACO, midnight at int’l dateline.    

Dijkstra Algorithm for Comparison • Dijkstra finds the absolute shortest path  according to some cost function involving  propagation delays and queue lengths.  • It assumes global, instantaneous knowledge and  is not realisable. • Our version of Dijkstra ignored queue lengths  and thus corresponds to a true absolute minimum  (though unrealisable) delay, i.e., propagation  delay only.     

 

SPF Algorithm for Comparison • Each satellite sends a list of its queue lengths to  every node in the network once per second.  • The receiving node then updates its routing table  based on this delayed information, using Dijkstra  shortest path with a cost function  cost = tpropagation + 0.6×tqueue + 0.4×queue • The SPF update rate chosen gives an average  routing bandwidth of about 408 kbits/s, i.e.,  roughly twice that of ACO (230.4 kbits/s).  

 

90th  percentile  packet  delays  (s)

SPF ANT DIJKSTRA

a) 'low' time (s)

90th  percentile  packet  delays  (s)

 

time (s)

c)  'intermediate'

time (s)

b) 'normal'

 

d) 'high'

time (s)

90th  percentile  packet  delays  (s)

SPF ANT DIJKSTRA

e) 'packet'

f) 'bursty I'

time (s) 90th  percentile  packet  delays  (s)  

time (s)

g) 'bursty II' time (s)

h) 'bursty III'  

time (s)

Main Results • ACO satellite network routing gives near  optimal packet delay distributions  • ACO mean packet delays tens to hundreds of  milliseconds lower than link state alg. SPF over  a wide range of traffic conditions • Additional routing bandwidth introduced by  ACO is 230.4 kbits/s, negligible compared to the  system load of several Gbits/s, and about half  that of SPF in these simulations (408 kbits/s)  

 

‘Nature­Inspired’ Algorithms • A number of other modern optimisation and/or  computing techniques are modelled upon  natural phenomena: • Simulated Annealing / Annealing of crystalline  structures • Genetic/Evolutionary Algorithms / Evolution  in living systems • Neural Networks / Animal nervous systems • Agent­based systems / Social interactions  

 

Simulated Annealing • Analogy  between  thermodynamic  behaviour  of solids and large combinatorial optimisation  problems • A  heated  solid  melts  and  particles  take  random  configurations;  then,  the  temperature  is  slowly  decreased  to  let  them  arrange  themselves in a state of minimal energy • If  temperature  is  decreased  too  quickly,  the  solid  freezes  into  a  meta­stable  state  rather  than into the ground state.    

Simulated Annealing • Modelled using a Boltzmann distribution with a  ‘temperature’ parameter, T :         where Ei is the energy of the system in state i, kB  the Boltzmann constant and Z(T) a normalisation  factor • Transition i → j accepted if ∆Uij = Ei­Ej < 0, or, if  ∆Uij > 0, with probability  

 

Simulated Annealing • At high T almost all modifications accepted,  while at low T only small jumps accepted.  • Simulated annealing is a stochastic relaxation  algorithm which in theory enables to reach  global optimality • Applications: as optimisation of NP­hard  problems, integrated circuit routing, image  processing  

 

Genetic/ Evolutionary Algorithms

• Each individual is a point in solution space • Population made to evolve by applying operators  for crossover (→ inherited traits), mutation (new  behaviours), and selection (survival of the fittest) • Key Issues: – – – – –

 

Genome: how are individuals coded? How is the initial population determined? How is the ‘fitness function’ defined? How are crossover and mutation implemented?  What is the selection mechanism (top 5?, best only?)  

Genetic/Evolutionary Algorithms • These types of strategies have been applied to  everything imaginable, but most often ‘academic’  problems: knapsack problem, graph problems, set  covering, noisy function evaluation • The high computational complexity makes ‘real­ world’ applications difficult for the moment • Some (M. Sipper, D. Mange, U. Tangen...)  propose evolutionary hardware (FPGA…) to help  overcome this problem    

 

Neural Networks • Feed forward networks are good for pattern  recognition and are used in a wide variety of  applications from particle physics to finance

• Recurrent (feedback) networks have been used  with success in industrial control applications  

 

Agent­Based Computing • « An autonomous agent is a system situated  within and a part of an environment that senses  that environment and acts on it, over time, in  pursuit of its own agenda and so as to effect  what it senses in the future. »                              Stan Franklin and Art Graesser                              Institute for Intelligent Systems                              University of Memphis  

 

Common properties that make agents  different from conventional programs

from : « A gentle introduction to agents and their applications »,  by Michael Weiss, MITEL Corp.

• Agents are autonomous, that is they act on behalf  of the user  • Agents contain some level of intelligence, from  fixed rules to learning engines that allow them to  adapt to changes in the environment  •  Agents don't only act reactively, but sometimes  also proactively   

 

Properties of agents, cont’d. • Agents have social ability, that is they  communicate with the user, the system, and  other agents as required  • Agents may also co­operate with other agents  to carry out more complex tasks than they  themselves can handle  • Agents may move from one system to another  to access remote resources or even to meet  other agents   

 

Reactive Agents • Reactive agents do not have internal symbolic  models, but react to the current state of the  environment  • They are simple and interact with others in  simple ways  • Complex patterns of behaviour can emerge  from these interactions  • Benefits: robustness, fast response time  • Challenges: how to debug them?   

 

Mobile Agents • Can migrate from one machine to another  • Execute in platform­independent environment  • Advantages:  – Reduced communication cost – Asynchronous computing 

• Applications:  – Distributed information retrieval  – Telecommunication network routing   

 

We may conclude that ‘ants’ are  reactive, mobile, multi­agent  systems

 

 

Careful, ‘agent’ doesn’t mean the same thing to all people!!    

Why ‘Nature­inspired’ Algorithms? • They work • We might not otherwise have thought them up • The underlying physical model acts as a guide  and gives us the confidence to try them • The introduction of randomness clearly plays a  role in simulated annealing and in several  aspects of genetic algorithms (initial state,  mutations, crossover…)  

 

Why ­ Distributed Computing? • The distributed nature of the algorithm is a  factor in neural networks (distributed  information storage) and agent­based models  (distributed problem solving) – Grassé postulated that the termites’ depositing  pheromones amounted to leaving environmental  markers which could be combined with those of other  agents to obtain more ‘global’ information – This he called ‘stigmergy’ (cf. stigma: mark)  

 

Why ­ Emergent Property? • The complex final states of swarm systems  recall the attractor states found in cellular  automata and recurrent neural network systems • Some would say that swarm intelligence is an  emergent property of multi­agent systems in  the same way that an avalanche is an emergent  property of a pile of individual snowflakes  

 

Why ­ Self Organisation? • Self­organisation is an important aspect of  agent­based systems – In simulated annealing and genetic algorithms,  an ‘omniscient’ judge accepts or rejects  subsequent steps – In ACO, shorter paths are automatically  selected since faster ants refresh the  pheromones more quickly   

 

Conclusions • We’ve visited several ‘Nature­inspired’  algorithms  • What’s new here are the ACO­like ones • Is ‘Agent­Based Computing’ poised to become  the ‘Neural Networks’ of the 2000’s? • Will Ants help find the Higgs?  

 

Conclusions • ACO adapts well to network­like structures  ­ those with inherent distributed computing  ­ while ACO simulations take forever (like  genetic alg.) • One could imagine applications in 

 

– Online control (machines, networks, etc.) – Anything resembling image processing – Iterative data analysis tasks ­ track  reconstruction, clustering ­ where some  optimisation takes place