Transcript Swarm2

Swarm Intelligence
Ant Colony Optimization
Tyrel Russell
Tyler Pierce
Ravi Jaswal
Pat Herbert
Presentation Objectives
•
•
•
•
•
•
•
•
Brief Introduction to Research
People Involved
Applications of ACO
Describe our Programs Concepts
Show simulation
Discuss Results
Improvements and Optimizations
Questions & Discussion
Swarm Intelligence
• What is it ?
• The property of a system where the
collective behaviors of unsophisticated
agents interacting locally with
environmental cause coherent functional
global patterns to emerge.
Swarm Intelligence
• Why is it Useful?
• Provides a basis with which it is possible
to explore collective or distributed problem
solving without centralized control or the
provision of a global model.
Our Objectives
• To simulate an ant colony
• Ants search for food and bring the food
back to the nest.
• Ants secrete pheromones and follow
pheromone trails from the nest to the food
• Ants who lose pheromone trails are lost
and will randomly move.
• Using Ant Colony Optimization algorithms
to try and find optimal food searches.
Ant Colony Optimization
History
The concept of is a fairly new concept to AI. The first ACO system was
introduces by Marco Dorigo in 1992 at IRIDIA at Universite Libre de
Bruxelles.
The first algorithm was called Ant System(AS) upon which we closely
based our algorithm.
Problems Looked at
•
•
•
•
•
•
Traveling Salesman problem
Quadratic assignment problem
Job-shop scheduling problem
Vehicle routing problem
Graph Coloring
Sequential ordering problem
Different Algorithms
• Modifications were made to the Ant System
algorithm in an attempt to improve the efficiency.
• New algorithms are:
– ANTS which improves the heuristic computation
– Max-Min Ant System allows only ants who find the
best solution to update pheromone
– Fast Ant uses no heuristic
– Hybrid Ant System which has a modified local
optimization
– Ant-Q which is similar to Q-learning
Applications of ACO
• Connection-oriented networks routing
• Connectionless networks routing
Similar Applications
• Evolutionary Computation
– Similar to population based incremental learning
• Neural Networks
–
–
–
–
Evaporation  a (learning rate)
Pheromone Trail  synaptic strength
Add pheromone  reinforce synaptic strength
Evaporate pheromone  reduce the synaptic
strength
Swarm Intelligence
Our Application
We found that the ants scattered in a
concentric pattern. This behaviour is to be
expected as it takes time to further
increase the pheromone level farther from
the nest.
Structure of Program
• Our program is structured over a graph of
connected edges and nodes. The nodes
are arranged in a square to resemble a
grid. Each of the nodes are connected to
each of their Neighbours.
Transition Formula
•
aik(t) = [Tik(t)]α[Nik]β
Σ[Tik(t)]α
For all k εN
α – increase in α increases the chance you take the right path
β – increases the effect of the heuristic value
Q – heuristic constant
Nest
??
?
??
?
Nest
Graphical User Interface
Probability Variables
Values of the constants can be
changed within the text fields
Main Variables
Domain Settings
Level Indicators
Control Buttons
Statistics Field
Results
Food Brought Back Vs. Cycles
Food Saturation at 1%
400
350
Food Brought Back
300
Evaporation 0.60
250
Evaporation 0.70
Evaporation 0.80
200
Evaporation 0.90
Evaporation 0.95
150
Evaporation 0.99
100
50
0
0
1000
2000
3000
Cycles
4000
5000
6000
Food Brought Back Vs. Cycles
Food Saturation at 5%
900
800
700
Food Brought Back
600
Evaporation 0.60
Evaporation 0.70
500
Evaporation 0.80
Evaporation 0.90
400
Evaporation 0.95
300
200
100
0
0
1000
2000
3000
Cycles
4000
5000
6000
Food Brought Back Vs. Cycles
Food Saturation at 20%
1400
1200
Food Brought Back
1000
Evaporation 0.60
800
Evaporation 0.70
Evaporation 0.80
Evaporation 0.90
600
Evaporation 0.95
400
200
0
0
1000
2000
3000
Cycles
4000
5000
6000
Improvements & Optimizations
• Ant Cooperation
– Multiple ants cooperate to bring food back to
the nest
– Smarter Ants
– Constant pheromones around Nest
– Better Heuristic
– Start Ants at Random Locations