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.
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
Inﬂuence 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.