CS 2710, ISSP 2610 Chapter 4, Part 2 Heuristic Search 1 Beam Search Cheap, unpredictable search For problems with many solutions, it may be worthwhile to discard unpromising paths Greedy best first search that keeps

a fixed number of nodes on the fringe 2 Beam Search def beamSearch(fringe,beamwidth): while len(fringe) > 0: cur = fringe[0] fringe = fringe[1:] if goalp(cur): return cur newnodes = makeNodes(cur, successors(cur)) fringe=sortByH(newnodes, fringe)

fringe = fringe[:beamwidth] return [] 3 Beam Search Optimal? Complete? Hardly! Space? O(b) (generates the successors) Often useful

4 Generating Heuristics Exact solutions to different (relaxed problems) H1 (# of misplaced tiles) is perfectly accurate if a tile could move to any square H2 (sum of Manhattan distances) is perfectly accurate if a tile could move 1 square in any direction 5

Relaxed Problems (cont) If problem is defined formally as a set of constraints, relaxed problems can be generated automatically A tile can move from square A to square B if: A is adjacent to B, and B is blank 3 relaxed problems by removing one or both constraints

Absolver (Prieditis, 1993) 6 Combining Heuristics If you have lots of heuristics and none dominates the others and all are admissible Use them all! H(n) = max(h1(n), , hm(n)) 7

Generating Heuristics Use the solution cost of a subproblem. E.g., get tiles 1 through 4 in the right location, ignoring the others. Pattern databases: store exact solution costs for every possible subproblem instance. The heuristic function looks up the value in the DB DB constructed by searching back from goal and recording cost of each new pattern

Do the same for tiles 5,6,7,8 and take max 8 Other Sources of Heuristics Ad-hoc, informal, rules of thumb (guesswork) Approximate solutions to problems (algorithms course) Learn from experience (solving lots of 8puzzles). Each optimal solution is a learning example (node,actual cost to goal)

Learn heuristic function, E.G. H(n) = c1x1(n) + c2x2(n) x1 = #misplaced tiles; x2 = #adj tiles also adj in the goal state. c1 & c2 learned (best fit to the training data) 9 Remaining Search Types Recall we have Backtracking state-space search Local Search and Optimization Constraint satisfaction search

10 Local Search and Optimization Previous searches: keep paths in memory, and remember alternatives so search can backtrack. Solution is a path to a goal. Path may be irrelevant, if the final configuration only is needed (8queens, IC design, network optimization, ) 11

Local Search Use a single current state and move only to neighbors. Use little space Can find reasonable solutions in large or infinite (continuous) state spaces for which the other algorithms are not suitable 12 Optimization

Local search is often suitable for optimization problems. Search for best state by optimizing an objective function. 13 Visualization States are laid out in a landscape Height corresponds to the objective function value Move around the landscape to find

the highest (or lowest) peak Only keep track of the current states and immediate neighbors 14 Local Search Alogorithms Two strategies for choosing the state to visit next Hill climbing Simulated annealing Then, an extension to multiple

current states: Genetic algorithms 15 Hillclimbing (Greedy Local Search) Generate nearby successor states to the current state based on some knowledge of the problem. Pick the best of the bunch and replace the current state with that one.

Loop 16 Hill-climbing search problems Local maximum: a peak that is lower than the highest peak, so a bad solution is returned Plateau: the evaluation function is flat, resulting in a random walk Ridges: slopes very gently toward a peak, so the search may oscillate from side to side Local maximum

Plateau Ridge 17 Random restart hill-climbing Start different hill-climbing searches from random starting positions stopping when a goal is found If all states have equal probability of

being generated, it is complete with probability approaching 1 (a goal state will eventually be generated). Best if there are few local maxima and plateaux 18 Random restart hill-climbing Hmm If all states have equal probability of being generated, it is complete with probability approaching 1 (a goal state will eventually be

generated). If it is restarted enough times, we considered Well, hill-climbing stops when no neighbors are better than current It stops on a local optimum (whether or not it is a global optimum). So, more iterations does not seem to be the point. 19 Random restart hill-climbing Hmm

If all states have equal probability of being generated, it is complete with probability approaching 1 (a goal state will eventually be generated). Any way to see this as true? R&N,p. 111: A complete local search algorithm always finds a goal if one exists; an optimal algorithm always finds a global minimum/maximum. So, goal means local minimum/maximum 20

Simulated Annealing Based on a metallurgical metaphor Start with a temperature set very high and slowly reduce it. Run hillclimbing with the twist that you can occasionally replace the current state with a worse state based on the current temperature and how much worse the new state is. 21 Simulated Annealing

Annealing: harden metals and glass by heating them to a high temperature and then gradually cooling them At the start, make lots of moves and then gradually slow down 22 Simulated Annealing More formally Generate a random new neighbor

from current state. If its better take it. If its worse then take it with some probability proportional to the temperature and the delta between the new and old states. 23 Simulated annealing Probability of a move decreases with the amount E by which the evaluation is worsened

A second parameter T is also used to determine the probability: high T allows more worse moves, T close to zero results in few or no bad moves Schedule input determines the value of T as a function of the completed cycles 24 function Simulated-Annealing(problem, schedule) returns a solution state inputs:

problem, a problem schedule, a mapping from time to temperature local variables: current, a node next, a node T, a temperature controlling the probability of downward steps current Make-Node(Initial-State[problem]) for t 1 to do T schedule[t] if T=0 then return current next a randomly selected successor of current

E Value[next] Value[current] if E > 0 then current next 25 else current next only with probability eE/T Local Beam Search Keep track of k states rather than just one, as in hill climbing In comparison to beam search we saw earlier, this alg is state-based rather than node-based.

26 Local Beam Search Begins with k randomly generated states At each step, all successors of all k states are generated If any one is a goal, alg halts Otherwise, selects best k successors from the complete list, and repeats 27

Local Beam Search Successors can become concentrated in a small part of state space Stochastic beam search: choose k successors, with probability of choosing a given successor increasing with value Like natural selection: successors (offspring) of a state (organism) populate the next generation according to its value (fitness) 28

Genetic Algorithms Variant of stochastic beam search Combine two parent states to generate successors (sexual versus asexual reproduction) 29 Fun GA (pop, fitness-fn) Repeat new-pop = {} for i from 1 to size(pop):

x = rand-sel(pop,fitness-fn) y = rand-sel(pop,fitness-fn) child = reproduce(x,y) if (small rand prob): child mutate(child) add child to new-pop pop = new-pop Until an indiv is fit enough, or out of time Return best indiv in pop, according to fitness-fn 30 Fun reproduce(x,y)

n = len(x) c = random num from 1 to n return: append(substr(x,1,c),substr(y,c+1, n) 31 Example: n-queens Put n queens on an n n board with no two queens on the same row, column, or diagonal

32 Genetic Algorithms Notes Representation of individuals Classic approach: individual is a string over a finite alphabet with each element in the string called a gene Usually binary instead of AGTC as in real DNA

Selection strategy Random Selection probability proportional to fitness Selection is done with replacement to make a very fit individual reproduce several times Reproduction Random pairing of selected individuals Random selection of cross-over points Each gene can be altered by a random mutation 33

Genetic Algorithms When to use them? Genetic algorithms are easy to apply Results can be good on some problems, but bad on other problems Always good to give a try before spending time on something more complicated 34