When Ants Attack! Ant Algorithms for Subset Selection ProblemsUniversity of Lyon University College Cork Christine Solnon Finbarr Tarrant Derek Bridge
When Ants Attack! Ant Algorithms for Subset Selection Problems
University of Lyon University College Cork Christine Solnon Finbarr Tarrant Derek Bridge
Overview
Ant Algorithms for Best Hamiltonian Path-Finding Problems
Subset Selection Problems
Definitions and examples
Ant-SS, an Ant Algorithm for Subset Selection Problems
Solution construction step
Pheromone updating step
Parameters
Experimental Results
Conclusions
Ant Algorithms
Find solutions or near-solutions to intractable discrete optimization problems
Inspired by the behaviour of real ants
Ants communicate indirectly by laying trails of pheromone
“stigmergy”
Enables the ants to find shortest paths between nest and food
Ant Algorithms
Problem is modelled as a search for a minimum cost path in a graph
Artificial ants complete a series of walks of the graph
Each path corresponds to a potential solution
They deposit pheromone on their path in proportion to its quality
Unlike real ants, typically
the pheromone is deposited on completion of the path
only the best paths receive pheromone (“elitism”)
Ant Algorithms
A B C Τ Τ η η The ants choose between destinations probabilistically based on a combination of
the cumulated pheromone τ, and
an heuristic factor η
Ant Algorithms
The pheromone intensifies search around the most promising paths
But to avoid stagnation, we need techniques to diversify search, e.g:
raise the importance of the heuristic factor
evaporate some pheromone
impose lower and upper bounds on the pheromone (MAX-MIN Ant Systems)
Travelling salesperson problem
Find the minimum length route that:
starts in, e.g., Cork;
visits each town exactly once;
returns to Cork.
And now the bad news...
Time to find shortest route Num of routes,
(n – 1)! ÷ 2 Num of towns,
n 28 21 A 19-digit number 52 mins 3 billion
(10-digit number) 360 microsecs 360 14 7 Nearly 40,000
years A 28-digit number 2 trillion
centuries
The Big Bang is thought to have been approximately 15 billion years ago.
Demo
Best Hamiltonian Path-Finding Problems
Ant algorithms have been used for
Travelling salesperson problems
Quadratic assignment problems
Vehicle routing problems
Permutation constraint satisfaction problems
Characteristics
ants must visit every vertex in the graph
heuristic factor is often inverse of edge cost
Subset Selection Problems
Intuition:
Given a set S, find a subset S’ S
that satisfies certain properties and/or
optimizes some objective function
Example: the multidimensional 0-1 knapsack problem
Choose which objects to put
into the knapsack
but total weight < 15kg
(and perhaps other properties)
and maximise monetary value
Subset Selection Problems
An SS problem may be defined by a triple
(S, Sfeasible, f) where
S is a set of objects;
Sfeasible (S) is a set that contains all feasible subsets of S;
f : Sfeasible is an objective function that associates a real-valued cost f(S’) with every feasible subset of objects S’ Sfeasible.
The goal of an SS problem (S, Sfeasible, f) is to find
S* S such that S* Sfeasible and f(S*) is maximal.
Multidimensional knapsack as a SS Problem
S is the set of objects;
Sfeasible contains every subset that satisfies all the resource constraints, i.e.
Sfeasible = {S’ S | i1..m, jS’, rij < bi} where m is the number of resources,
rij is the consumption of resource i by object j, and bi is the available quantity of resource i;
f returns the total profit, i.e.,
S’Sfeasible, f(S’) = jS’ pj where pj is the profit associated with object j.
Other SS Problems
Maximum Clique
Maximum Boolean Satisfiability
Maximum Constraint Satisfaction
Minimum Vertex Cover
Graph Matching
Edge-Weighted k-Cardinality Tree
Ant-SS
Sfeasibe must be defined in such
a way that feasible subsets can
be constructed incrementally Initialise pheromone
repeat
for each ant k, construct a solution Sk as follows:
Randomly choose a first object oi S
Sk {oi}
Candidates {oj S \ oi | Sk {oj} Sfeasible}
while Candidates
Choose an object oi Candidates with probability p(oi, Sk) based on τ(oi, Sk) and η(oi, Sk)
Sk Sk {oi}
Remove oi from Candidates
Remove from Candidates every object oj such that Sk {oj} Sfeasible
end while
end for
Optionally, apply local search
Update the pheromone
until maximum number of cycles reached or acceptable solution found
Pheromone update
In SS Problems, the order in which objects are selected is not significant
hence rewarding consecutively visited vertices (by placing pheromone on visited edges) is not meaningful
Vertex pheromone strategy
reward solution Sk by associating pheromone with each object oi Sk
Clique pheromone strategy
reward solution Sk by associating pheromone with each pair of different objects (oi, oj) Sk Sk
Vertex Pheromone Strategy
1 2 3 4 5 1 2 3 4 5 The ant’s walk Where pheromone is laid Pheromone is laid on objects
represents the learned desirability of selecting that object
How does this affect candidate selection?
Initialise pheromone
repeat
for each ant k, construct a solution Sk as follows:
Randomly choose a first object oi S
Sk {oi}
Candidates {oj S | Sk {oj} Sfeasible}
while Candidates
Choose an object oi Candidates with probability p(oi, Sk) based on τ(oi, Sk) and η(oi, Sk)
Sk Sk {oi}
Remove oi from Candidates
Remove from Candidates every object oj such that Sk {oj} Sfeasible
end while
end for
Optionally, apply local search
Update the pheromone
until maximum number of cycles reached or acceptable solution found
Vertex Pheromone Strategy: how it affects candidate selection
1 2 3 4 5 1 2 3 4 5 Suppose the ant has selected
objects 1, 2 and 4. The probability of selecting
object 5 is based on
the pheromone on object 5;
the heuristic value of object 5 Τ5 η5
Clique Pheromone Strategy
1 2 3 4 5 1 2 3 4 5 The ant’s walk Where pheromone is laid Pheromone is laid on pairs of objects
represents the learned desirability of selecting one object given that another has been selected
Comments