2nd Order Swarm Intelligence - David Sousa-Rodrigues

1 downloads 202 Views 2MB Size Report
tradi onal ACS. – Tradi onal posi ve reinforcement pheromone. – Use of Nega ve Pheromone. • Marker for forbidden p
2nd  Order  Swarm  Intelligence   Vitorino  Ramos,  David  Rodrigues+,  and  Jorge  Louçã     HAIS  2013,  Salamanca   September  11-­‐13,  2013   hHp://goo.gl/OXc0Oh     +  The  Open  University,  UK  –  [email protected]  

Outline   •  Present  an  algorithm  that  is  an  extension  to   Ant  Colony  System   •  Use  of  non-­‐entry  signal  via  a  negaSve   pheromone.   •  Use  of  2  pheromones  improves  quality  of   results  

Ant  Colony  OpSmisaSon   •  ProbabilisSc  technique   •  Searching  for  OpSmal  Path  in  the  graph   (Based  on  the  behaviour  of  ants  seeking  a   path  between  colony  and  source  of  food)   •  Mata-­‐heurisSc  opSmisaSon  

ACO  Concept     •  Ants  navigate  from  nest  to  food  source.   Blindly!   •  Shortest  path  is  discovered  via  pheromone   trails  deposited  by  other  ants.   •  Each  ant  moves  stochasScally   •  Pheromone  is  deposited  on  path   •  More  pheromone  implies  higher  probability  of   path  being  followed.  

ACO  IllustraSon  

TSP  Problem   •  A  Salesman  must  visit  N  ciSes,  passing   through  each  city  only  once,  and  returning  to   the  start  city.   •  The  cost  of  the  transportaSon  between  all   ciSes  is  known   •  The  ObjecSve  is  to  choose  the  order  of  the   tour  so  the  total  cost  is  minimum.  

History   •  Ant  System  developed  by  Marco  Dorigo  (1992,   PhD  thesis)   •  Max-­‐Min  Ant  System  by  Hoos  and  Stützle   (1996)   •  Ant  Colony  by  Gambardella,  Dorigo  (1997)  

Biology  Findings  of  non-­‐entry  singals   •  Pharaoh's  ants  (Monomorium  pharaonis)   deposit  a  pheromone  as  a  'no  entry'  signal  to   mark  unrewarding  foraging  paths.   [Robinson,  2005,  2007;  Grüter  2012]  

nd 2  Order  Swarm  Intelligence  

•  Double  Pheromone  Model  on  top  of   tradiSonal  ACS.   –  TradiSonal  posiSve  reinforcement  pheromone   –  Use  of  NegaSve  Pheromone   •  Marker  for  forbidden  paths   •  Forbidden  paths  are  obtained  from  the  worse  ant  tour   of  each  iteraSon   •  This  Blockade  isn’t  permanent  as  the  pheromone   evaporates.  

State  TransiSon  Rule  

State  TransiSon  Rule  

Global  UpdaSng  Rule  

Local  UpdaSng  Rule  

nd 2  Order  Reasoning  

nd 2  Order  Response  Maps  

nd 2  Order  AS  Results  

Influence  of  NegaSve  Pheromone  

kroA100.tsp  with  negaSve  pheromone   performs  beHter  

NegaSve  Pheromone  Also  is  important   for  bigger  problems.  

NegaSve  pheromone  can’t  dominate   the  pheromone  maps.  

Take  Home  Message   •  From  Biology  Findings:  use  of  negaSve   pheromone  as  non-­‐entry  signal   •  New  algorithm  based  on  ACS  with  minimal   changes  to  tradiSonal  algorithm   •  BeHer  results  (faster  convergence  to  good   results/  faster     •  ApplicaSon  to  Dynamical  problems  for  faster   tracking  of  the  soluSons.