Local Search Part I
Why not Classical Search? Classical search can 1) find a path in search space; 2) keep track of previous state
However, => 1) what if we only want to know the final configura on?
but good enough for the purpose 2) what if we do NOT need the best possible solu on?
3) what if we have only limited resources?
Key features of Local Search? trying to find the highest point of an n-dimensional mountain, in the fog, with amnesia
Do NOT keep track of previous states that have been reached (no backtracking)
Look at neighboring states and decide what to do next
Do NOT care whether there may be a be er solu on (terminate if reach peak)
What is the difference between Depends on the eleva on:
Hill-climbing and Steepest descent? - objec ve func on, then Hill-climbing, the goal is to find global maximum/highest peak
- cost, then Steepest descent, the goal is to find the global minimum/lowest valley
Why Local Search? 1. For many problems we do not need the best solu on, or such one is not achievable
2. It operate on complete search problems without keep track of all the states
Ridges
Plateaus: shoulder & flat local max
Not really a mountain, but a
state-space
Sequence of local max that are not
directly connected;
Each local max only has worse
connec ng states;
Common in low-dimensional state
spaces. Hill-climbing - keeps track of one current state (no backtracking)
- does NOT look ahead beyond the immediate neighbors of the current state (greedy)
- on each itera on moves to the neighboring state with highest value
- terminates when a peak is reached
Improved search based on Hill-climbing?
3 1 2
1: current state Hill-climbing: always move to 3, because 3 > 2
Stochas c **: move randomly to 3 or 2, but 3 has higher probability than 2
1/2 me need to look at neighbors First- choice **: if move to 3 first, then move to 3; if move to 2 first, then move to 2.
therefore, save cost
Random-restart **: do a number of ** searches from randomly selected states.
will eventually find the correct solu on If each hill-climbing search has probability of success: p
because goal state will be ini al state Then: solu on will be found on average a er 1/p restarts
Simulated annealing => adds stochas c element to hill climbing, can give op mal solu on in some case.
(hill-climbing + random walk) 1. Move to randomly choice state
1.1 u lity : always move to that state
1.2 u lity : move to that state with probability p < 1
Benefit of Simulated annealing? P(move to a worst state) if the move makes the situa on worst
Parameter of Simulated annealing?
Temperature => P(move to a worst state) (数值调越高越不满足于当前抵达的 peak，继续搜索更远的 peak，
数值接近 0 时，越类似 Hill-Climbing，即找到 peak 就停止搜寻)
Local beam search => provides first approach to the genera on and selec on of states.
1. select k best successors (neighbors) at every step
Stochas c local beam search (select at random, with probability as func on of u lity/fitness if it is stochas c)
1.1 k=1: hill-climbing
1.2 k>=2: parallel hill climbing process
Local search methods are a useful tool because they operate on complete search problems without keeping track of all the states.
, Genetic Algorithms & Practical Problems
(Not Local Search) Gene c algorithms => maintain a large popula on of states and use opera ons to expand the search space.
( crossover and muta on)
‣ Two pairs are selected at random with probability of selec on increasing with fitness.
‣ Crossover point for each pair is chosen at random biggest advantage
(if code is ini ally permuted, then no advantage)
‣ Offspring are created by combining strings at crossover point
‣ Small probability of random muta on
each state rated by
objec ve/fitness func on
What is gene c algorithms? 1. Uphill tendency
(Good applica on requires 2. random explora on
careful engineering of code) 3. exchange of info between search threads
Prac cal Problems
Rules of the game 4(5) queens placed a acking each other, move the queens so no queen a ack another.
Cost: number of pairs of queens a acking each other
Ac on: move one queen per ac on, only up or down ( stays in their column )
4-Queens Problem => Local Search
Ini al state: Cost = 6; available moves = 4(number of queens) * 3(available move for each)
Con nue to move: if two states have the same cost, choose one at random
(*Omi ed because easy) 5-Queens Problem => Gene c Algorithms
Steps:
1. Start with k randomly selected states (popula on)
2. Each state is encoded as a string = > state representa on for ini al: “1111”
(Popula on:21325, 35415, 14255, 15233)
row number of the queens
3. Each state is rated by an objec ve func on (cost/fitness)
(cost(21325) = 4, …2, 2, 3 => total cost of genera on = 4+2+2+3 = 11)
New Popula on:
35233, 15415, 14255, 35415 4. Sample two pairs with probability propor onal to fitness/cost: 1 −
(P(21325) = 1 – 4/11 = 0.636, P(35415) = 1 – 2/11 = 0.818, ….0.818, 0.727)
(Two pairs: 35415- 15233 and 35415- 14255)
Another example:
Count can also be the number of 5. Randomly determine crossover points (2 or 3)
NON-a acking pair depends on need
Then this will give => u lity 6. Combine strings at crossover points
e.g. U( 32431 ) = 7 (35|415-15|233 => 35233-15415) and (35|415-142|55 => 35455-14215)
rela ve probability: 7/54=0.130
7. With a small chance, mutate an element of the offspring Repeat for the next genera on
(35455 => 35415)
=> go back to step 4 and repeat
Why not Classical Search? Classical search can 1) find a path in search space; 2) keep track of previous state
However, => 1) what if we only want to know the final configura on?
but good enough for the purpose 2) what if we do NOT need the best possible solu on?
3) what if we have only limited resources?
Key features of Local Search? trying to find the highest point of an n-dimensional mountain, in the fog, with amnesia
Do NOT keep track of previous states that have been reached (no backtracking)
Look at neighboring states and decide what to do next
Do NOT care whether there may be a be er solu on (terminate if reach peak)
What is the difference between Depends on the eleva on:
Hill-climbing and Steepest descent? - objec ve func on, then Hill-climbing, the goal is to find global maximum/highest peak
- cost, then Steepest descent, the goal is to find the global minimum/lowest valley
Why Local Search? 1. For many problems we do not need the best solu on, or such one is not achievable
2. It operate on complete search problems without keep track of all the states
Ridges
Plateaus: shoulder & flat local max
Not really a mountain, but a
state-space
Sequence of local max that are not
directly connected;
Each local max only has worse
connec ng states;
Common in low-dimensional state
spaces. Hill-climbing - keeps track of one current state (no backtracking)
- does NOT look ahead beyond the immediate neighbors of the current state (greedy)
- on each itera on moves to the neighboring state with highest value
- terminates when a peak is reached
Improved search based on Hill-climbing?
3 1 2
1: current state Hill-climbing: always move to 3, because 3 > 2
Stochas c **: move randomly to 3 or 2, but 3 has higher probability than 2
1/2 me need to look at neighbors First- choice **: if move to 3 first, then move to 3; if move to 2 first, then move to 2.
therefore, save cost
Random-restart **: do a number of ** searches from randomly selected states.
will eventually find the correct solu on If each hill-climbing search has probability of success: p
because goal state will be ini al state Then: solu on will be found on average a er 1/p restarts
Simulated annealing => adds stochas c element to hill climbing, can give op mal solu on in some case.
(hill-climbing + random walk) 1. Move to randomly choice state
1.1 u lity : always move to that state
1.2 u lity : move to that state with probability p < 1
Benefit of Simulated annealing? P(move to a worst state) if the move makes the situa on worst
Parameter of Simulated annealing?
Temperature => P(move to a worst state) (数值调越高越不满足于当前抵达的 peak，继续搜索更远的 peak，
数值接近 0 时，越类似 Hill-Climbing，即找到 peak 就停止搜寻)
Local beam search => provides first approach to the genera on and selec on of states.
1. select k best successors (neighbors) at every step
Stochas c local beam search (select at random, with probability as func on of u lity/fitness if it is stochas c)
1.1 k=1: hill-climbing
1.2 k>=2: parallel hill climbing process
Local search methods are a useful tool because they operate on complete search problems without keeping track of all the states.
, Genetic Algorithms & Practical Problems
(Not Local Search) Gene c algorithms => maintain a large popula on of states and use opera ons to expand the search space.
( crossover and muta on)
‣ Two pairs are selected at random with probability of selec on increasing with fitness.
‣ Crossover point for each pair is chosen at random biggest advantage
(if code is ini ally permuted, then no advantage)
‣ Offspring are created by combining strings at crossover point
‣ Small probability of random muta on
each state rated by
objec ve/fitness func on
What is gene c algorithms? 1. Uphill tendency
(Good applica on requires 2. random explora on
careful engineering of code) 3. exchange of info between search threads
Prac cal Problems
Rules of the game 4(5) queens placed a acking each other, move the queens so no queen a ack another.
Cost: number of pairs of queens a acking each other
Ac on: move one queen per ac on, only up or down ( stays in their column )
4-Queens Problem => Local Search
Ini al state: Cost = 6; available moves = 4(number of queens) * 3(available move for each)
Con nue to move: if two states have the same cost, choose one at random
(*Omi ed because easy) 5-Queens Problem => Gene c Algorithms
Steps:
1. Start with k randomly selected states (popula on)
2. Each state is encoded as a string = > state representa on for ini al: “1111”
(Popula on:21325, 35415, 14255, 15233)
row number of the queens
3. Each state is rated by an objec ve func on (cost/fitness)
(cost(21325) = 4, …2, 2, 3 => total cost of genera on = 4+2+2+3 = 11)
New Popula on:
35233, 15415, 14255, 35415 4. Sample two pairs with probability propor onal to fitness/cost: 1 −
(P(21325) = 1 – 4/11 = 0.636, P(35415) = 1 – 2/11 = 0.818, ….0.818, 0.727)
(Two pairs: 35415- 15233 and 35415- 14255)
Another example:
Count can also be the number of 5. Randomly determine crossover points (2 or 3)
NON-a acking pair depends on need
Then this will give => u lity 6. Combine strings at crossover points
e.g. U( 32431 ) = 7 (35|415-15|233 => 35233-15415) and (35|415-142|55 => 35455-14215)
rela ve probability: 7/54=0.130
7. With a small chance, mutate an element of the offspring Repeat for the next genera on
(35455 => 35415)
=> go back to step 4 and repeat
