Transcript 5. Advanced Search Algorithms - Computing Science

Chapter 5.
Advanced Search
Fall 2011
Comp3710 Artificial Intelligence
Computing Science
Thompson Rivers University
Course Outline


Part I – Introduction to Artificial Intelligence
Part II – Classical Artificial Intelligence


Knowledge Representation
Searching




Knowledge Represenation and Automated Reasoning





Search Methodologies
Advanced Search
Genetic Algorithms (relatively new study area)
Propositinoal and Predicate Logic
Inference and Resolution for Problem Solving
Rules and Expert Systems
Part III – Machine Learning
Part IV – Advanced Topics
TRU-COMP3710
Advanced Search
2
Chapter Objectives





Given a contraint satisfaction algorithm, define variables and
constraints.
Use of Most-Constrained Variable and Most-Constraining Variable
heuristics for the 8-queens problem and the map coloring problem.
Use of Least-Constraining Variable heuristic for the 8-queens problem
and the map coloring problem.
Use of Heuristic Repair for the 8-queens problem.
...
TRU-COMP3710
Advanced Search
3
Chapter Outline
1.
Constraint Satisfaction Search




2.
Forward Checking
Most-Constrained Variable First
Least-Constraining Variable First
Heuristic Repair
Combinatorial Optimization Problems


How to use greedy approach – Local Search
How to improve local search





TRU-COMP3710
Exchanging Heuristic
Iterated Local Search
Simulated Annealing
Parallel Search
Genetic Algorithms for Search
Advanced Search
4
1. Constraint Satisfaction Problems



Put n queens on an n × n board with no two queens on the same row,
column, or diagonal
[Q] How to solve?
[Q] Which one do we need to move first?
TRU-COMP3710
Heuristic Search
5



Combinatorial optimization problems involve assigning values to a
number of variables.
A constraint satisfaction problem (CSP) is a combinatorial
optimization problem with a set of constraints.
Example: The 8-queens problem


Eight queens must be placed on
a chess board in such a way that
no two queens are on the same
diagonal, row, or column
[Q] How to model the constraints?



8 variables, a through h
Each variable can have a value 1 to 8.
The values must satisfy the constraints.
[Q] Meaning is?
TRU-COMP3710
Advanced Search
6



Combinatorial optimization problems involve assigning values to a
number of variables.
A constraint satisfaction problem (CSP) is a combinatorial
optimization problem with a set of constraints.
Example: The 8-queens problem



[Q] How to solve?
[Q] Can be solved using search?




Eight queens must be placed on
a chess board in such a way that
no two queens are on the same
diagonal, row, or column
DFS? A*?
What kind of search tree?
Huge space: ???
With many variables it is essential to use heuristics.
TRU-COMP3710
Advanced Search
7
1.1 Forward Checking


Huge search tree
[Q] Do we have to visit any choice (, i,e., state or node in the search,)
that conflicts with constraints?



To delete, from the set of possible future choices, any that have been
rendered impossible by placing the queen on that square
If placing a queen on the board results in removing all remaining squares,
then backtracking immediately.
How about to use heuristics?


Most-Constrained Variable First
Lease-Constraining Variable First
TRU-COMP3710
Advanced Search
8
1.2 Most-Constrained Variables



Most-Constrained Variable First heuristic
At each stage of the search, this heuristic involves working with the
variable that has the least possible number of valid choices.
In the example of the 8-queens problem,
assigning a value to 8 variables,
a through h







a = 1; b = 3; c = 5, then
d has 3 choices.
e has 3 choices.
f has 1 choice.
g has 3 choices.
h has 3 choices.
The next move is
to place a queen in column f, not d.
TRU-COMP3710
Advanced Search
9


What if there are ties?
Then, most-constraining variable heuristic for breaking the tie.


To assign a value to the variable that places the greatest number of
constraints on future variables.
E.g., map coloring problem with only 3 colors
What is the next choice?
TRU-COMP3710
Advanced Search
10
1.3 Least-Constraining Variables


Instead of the previous two heuristics – most-constrained variable first
and most-constraining variable to break ties,
Least-Constraining Variable First heuristic




To assign a value to a variable that leaves the greatest number of choices
for other variables.
More intuitive
This heuristic makes n-queens problems with extremely large values of
n, e.g., 1000, quite solvable.
Can you try with n=8?
TRU-COMP3710
Advanced Search
11
1.4 Heuristic Repair


A heuristic method for solving CSPs.
Generate a possible solution (randomly, or using a heuristic to generate
a position that is close to a solution), and then make small changes to
bring it closer to satisfying constraints.
TRU-COMP3710
Advanced Search
12
Heuristic Repair for the 8-Queens Problem


Initial state – one queen is conflicting with another.
We’ll now move that queen to the square with the fewest conflicts.
TRU-COMP3710
Advanced Search
13

Second state – now the queen on the f column is conflicting, so we’ll
move it to the square with fewest conflicts.
TRU-COMP3710
Advanced Search
14
Units
TRU-COMP3710
Advanced Search
15
2. Combinatorial Optimization Problems




[Wikipedia] In applied mathematics and theoretical computer
science, combinatorial optimization is a topic that consists of finding
an optimal object from a finite set of objects.
In many such problems, exhaustive search is not feasible. It operates
on the domain of those optimization problems, in which the set
of feasible solutions is discrete or can be reduced to discrete, and in
which the goal is to find the best solution.
Some common problems involving combinatorial optimization are
the traveling salesman problem ("TSP") and the minimum spanning
tree problem ("MST").
Combinatorial optimization is a subset of mathematical
optimization that is related to operations research, algorithm theory,
and computational complexity theory. It has important applications in
several fields, including artificial intelligence, machine learning,
mathematics, auction theory, and software engineering.
TRU-COMP3710
Advanced Search
16
Units

[Q] How to solve combinatorial optimization problems?


From greedy approach – local search
To advanced local search algorithms
TRU-COMP3710
Advanced Search
17
2.1 Local Search



Like heuristic repair, local search methods start from a random
state, and make small changes (improvement) until a goal state is
achieved.
Most local search methods are susceptible to local maxima, like hillclimbing.
Local search methods are known as metaheuristics. Here are very
important local search methods.





Simulated annealing
Genetic algorithms
Colony optimization
Neural networks
We will discuss some ideas of how to improve local search in the
following slides.
TRU-COMP3710
Advanced Search
18
Initial
state
A bit better
state
Cumulative improvement
A bit better
state
How to solve?
A bit better
state
TRU-COMP3710
Susceptable to local maxima
Advanced Search
19
How to Improve Local Search

[Q] Any good idea?
1.
Keep cumulative improvement
Give more diversity while keeping stability
Give some random walks
2.
3.
TRU-COMP3710
Advanced Search
Units
20
2.2 Exchanging Heuristics



A simple local search method.
Heuristic repair is an example of an exchanging heuristic.
Involves exchanging one or more variables at each step by giving them
different values




Exchanging variables until the new state becomes better
Repeat this step until a solution is found
A k-exchange involves swapping the values of k variables.
Can be used to solve the traveling salesman problem.
TRU-COMP3710
Advanced Search
21
Units
Initial
state
A bit
A better
bit better
state
state
Cumulative improvement
Ramdom choice -> Diversity
A bit
A better
bit better
state
state
A bit
A better
bit better
state
state
TRU-COMP3710
Advanced Search
22
2.3 Iterated Local Search


Units
A local search is applied repeatedly from different initial states.
Useful in cases where the search space is extremely large, and
exhaustive search will not be possible.
TRU-COMP3710
Advanced Search
23
2.4 Simulated Annealing


A method based on the way in which metal is heated and then cooled
very slowly in order to make it extremely strong.
Aims at obtaining a minimum value for some function of a large
number of variables.


This value is known as the energy of the system.
Based on metropolis Monte Carlo Simulation.

Simple Monte Carlo Simulation: a method of learning information about
the shape of a search space.


TRU-COMP3710
E.g., a square partially contained within a circle.
How to identify what proportion of the square is within
the circle?
By random sampling
Advanced Search
24

Algorithm:





A random initial state is selected
A small random change is made.
To select a new state that makes a small change to the current state
If this change lowers the system energy, it is accepted.
If it increases the energy, it may be accepted, depending on a probability
called the Boltzmann acceptance criteria:

TRU-COMP3710
e(-dE/T) , where
T is the current temperature, and
dE is the increase in energey that has been produced by moving the previous
state to the new state.
Advanced Search
25

e(-dE/T) , where
T is the current temperature, and
dE is the increase in energey that has been produced by moving the previous
state to the new state.
1
P
0.8
0.6
0.4
0.2
0



T (decreasing)
To determine whether to move to a higher energy state or not,
if a random number within (0, 1) < the probability above, then move.
When the process starts, T is high, meaning increases in energy are
relatively likely to happen.
Over successive iterations, T lowers and increases in energy become
less likely.
TRU-COMP3710
Advanced Search
26
Initial
state
Ramdom choice -> better diversity
A bit
A better
bit better
A bit better
A bit worse
A bit better
state
state
state
state state
Cumulative improvement
A bitA worse
bit better
A bit worse A bit better
state
state
state
state
Diversity is gradually becoming less effective.
-> better stability
A bit
A better
bit better
state
state
TRU-COMP3710
Advanced Search
27
Units

[Q] Why is Simulated Annealing good?




Because the energy of the system is allowed to increase by using random
selection, simulated annealing is able to escape from local minima.
Simulated annealing is a widely used local search method for solving
problems with very large numbers of variables.
For example: scheduling problems, traveling salesman, placing VLSI
(chip) components.
[Q] How to improve?

Combination of iterated local search and simulated annealing?
TRU-COMP3710
Advanced Search
28
2.5 Parallel Search


Units
Some search methods can be easily split into tasks which can be solved
in parallel.
-> improved diversity
Important concepts to consider are:




Divide and conquer?
Task distribution
Load balancing
Tree ordering
TRU-COMP3710
Advanced Search
29
2.6 Genetic Algorithms

A method based on biological evolution.
Create chromosomes which represent possible solutions to a problem.
The best chromosomes in each generation are bred with each other to
produce a new generation.
Much more detail on this later.

A form of local search, which has









Cumulative improvement
Better diversity
Better stability
Randomness
Quick searching
Advanced form of the combination of iterated local search and
simulated annealing
TRU-COMP3710
Advanced Search
30

Start with k randomly generated states (population) – 1st generation



Next generation




A state is represented as a string over a finite alphabet (often a string of 0s
and 1s) (encoding)
Evaluation function (fitness function). Higher values for better states.
A successor state is generated by combining two parent states.
Produce the next generation of states by selection according to the
evaluation with fitness function, crossover, and mutation.
Next generation
…
TRU-COMP3710
Advanced Search
31

How to represent the left individual (, i.e., state)?



32752411
TRU-COMP3710
(3, 1, 7, 5, 8, 6, 4, 6)
Fitness function: number of non-attacking pairs
of queens (min = 0, max = 8 × 7/2 = 28). The
larger, the better, in this example.
[Q] fitness values of the next states?
24748552
Advanced Search
32748552
32
32752411
24748552
32748552
The fitness value: 23
The fitness value: 24
The fitness value: 23
TRU-COMP3710
Advanced Search
33
Units
Can you evaluate them?



Fitness function: number of non-attacking pairs of queens (min = 0,
max = 8 × 7/2 = 28)
24/(24+23+20+11) = 31%
23/(24+23+20+11) = 29% etc
TRU-COMP3710
Advanced Search
34