Transcript Overview of meta

G5BAIM
Artificial Intelligence Methods
Dr. Rong Qu
Overview of meta-heuristics
Overview

Local search based approach




Simulated Annealing
Tabu Search
Variable neighbourhood search, etc
Population based approach



Genetic algorithms
Evolutionary algorithms
Ant Algorithms, etc
Local Search Based - Simulated
Annealing

Overall idea


Accept worse moves by a probability to
escape from local optima
Probability of accepting worse moves
controlled by temperature in a cooling
schedule
Local Search Based - Simulated
Annealing

Cooling schedule





Starting temperature
Final temperature
Temperature decrement
Iterations at each temperature
P = exp ^ (-c/t)


Difference in solution quality
Current system temperature
Local Search Based - Simulated
Annealing

Search of SA


Higher chance of accepting worse moves
at the beginning
Lower probability of accepting worse
moves at the end of search
Local Search Based - Tabu Search


Proposed independently by Glover
(1986) and Hansen (1986)
Overall idea

to avoid entrapment in cycles by forbidding
or penalizing moves which take the
solution, in the next iteration, to points in
the solution space previously visited (hence
tabu).
Local Search Based - Tabu Search

Use past experience (memory) in
current decision making

Recency



Tabu list (short term memory)
Tabu tenure
Frequency

Elite solutions (long term memory)


Intensification
Diversification
Local Search Based - Tabu Search


Aspiration: accept better moves even
they are tabu-ed
Search of TS


Prohibit loops in the search
Explore new regions in the search space
Population Based - Evolutionary
Algorithms



Based on survival of the fittest
A population of candidate solutions
(chromosomes)
Evolve by reproduction operators



Crossover (different types)
Mutation (different types)
Evaluate each offspring & Selection on
the population
Population Based - Evolutionary
Algorithms


Schema theorem: theoretical
background
Genetic Algorithms vs. Evolutionary
Strategies

Crossover and mutation
Population Based - Ant Algorithms



These algorithms are very new (Dorigo,
1996) and is still very much a research area
Ants are practically blind but they still
manage to find their way to and from food.
How do they do it?
There is a population of ants, with each ant
finding a solution and then communicating
with the other ants
Population Based - Ant Algorithms


Ant algorithms are population based, in
this sense, similar to Genetic
Algorithms.
The probability of an ant following a
certain route is a function, not only of
the pheromone intensity but also a
function of what the ant can see
(visibility)
G5BAIM
Artificial Intelligence Methods
Dr. Rong Qu
Overview of meta-heuristics