Local SearchScaling Up • So far, we have considered methods that systematically explore the full search space, possibly using principled pruning (A* etc.). • The current best such algorithms (RBFS / SMA*) can handle search spaces of up to 10100 states → ~ 500 binary valued variables. • But search spaces for some real-world problems might be much bigger - e.g. 1030,000 states. • Here, a completely different kind of search is needed. → Local Search MethodsOptimization Problems • We're interested in the Goal State - not in how to get there. • Optimization Problem: - State: vector of variables - Objective Function: f: state → - Goal: find state that maximizes or minimizes the objective function • Examples: VLSI layout, job scheduling, map coloring, N-QueensRepresentations for 8Q problemHeuristic for 8Q problem?Heuristic for 8Q problem?Local Search Methods • Applicable to optimization problems. • Basic idea: - use a single current state - don't save paths followed - generally move only to successors/neighbors of that state • Generally require a complete state description.Hill-Climbing Search function HILL-CLIMBING ( ) returns a solution state inputs: , a problem static: , a node MAKE-NODE(INITIAL-STATE[ ])loop do a highest-valued succeproblemproblemcurrentcurrent problemnext ssor of if VALUE[next] < VALUE[current] then return endcurrentcurrentcurrent nextCurrent State EvaluationHill Climbing Pathologies Objective function Shoulder Global Maximum Local Maximum “flat” local maximum State Space Value of current solutionLocal Maximum ExampleNeutral “Sideways” moves Take new state even if not strictly better (just equal) Allows exploring plateaus …But can get into cyclesNeutral “Sideways” moves 8Q problem without sideways Stuck 86% time 4 steps to succeed 3 to get stuck 8Q problem with sideways Succeeds 94% time 21 steps to succeed 64 to get stuckRandom restarts Random restarts: Simply restart at a new random state after a pre-defined number of steps. Is it worth it? If probability of success is p, then Expected number of trials to success is 1/pNeutral “Sideways” moves 8Q problem without sideways Stuck 86% time 4 steps to succeed 3 to get stuck 8Q problem with sideways Succeeds 94% time 21 steps to succeed 64 to get stuck A = With Sideways B = Without SidewaysNelder-Mead (Simplex) Method • Reflect the point with the highest WSS through centroid (center) of the simplex • If this produces the lowest WSS (best point) expand the simplex and reflect further • If this is just a good point start at the top and reflect again • If this the highest WSS (worst point) compress the simplex and reflect closer http://www.boomer.org/c/p3/c11/c1106.htmlhttp://paula.univ.gda.pl/~dokgrk/simplex.htmlContingency plans • In cases where future states are unknown (stochasticity, unobsrvability) we resort to searching for policies rather than solutions – A policy will decides what to do given perceptions • Optimal policy will make good decisions – Natural Evolution generated brains that can make “good” decisions in real timeImprovements to Basic Local Search Issue: How to move more quickly to successively higher plateaus and avoid getting “stuck” local maxima. Idea: Introduce downhill moves (“noise”) to escape from long plateaus (or true local maxima). Strategies: • Random-restart hill-climbing => Multiple runs from randomly generated initial states • Tabu search • Simulated Annealing • Genetic AlgorithmsLocal Beam Search Local Beam Search: Run the random starting points in parallel, always keeping the k most promising states current ← k initial states for t ← 1 to infinity do new ← expand every state in current if f(best-in-new) < f(best-in-current) then return best-in-current current ← best k states in newRidgesSimulated Annealing Idea: Use conventional hill-climbing techniques, but occasionally take a step in a direction other than that in which the rate of change is maximal. As time passes, the probability that a down-hill step is taken is gradually reduced and the size of any down-hill step taken is decreased. Kirkpatrick et al. 1982; Metropolis et al.1953.Simulated Annealing Algorithm current ← initial state for t ← 1 to infinity do T ← schedule[t] if T = 0 then return current next ← randomly selected successor of current ∆E ← f(next) – f(current) if ∆E > 0 then current ← next else current ← next only with probability e∆E/TGenetic Algorithms • Approach mimics evolution. • Usually presented using a rich (and different) vocabulary: fitness, populations, individuals, genes, crossover, mutations, etc. • Still, can be viewed quite directly in terms of standard local search.Genetic Algorithms: Recombination Objective function Shoulder Global Maximum Local Maximum “flat” local maximum State Space Value of current solutionGenetic Algorithms Inspired by biological processes that produce genetic change in populations of individuals. Genetic algorithms (GAs) are local search procedures that usually the following basic elements: • A Darwinian notion of fitness: the most fit individuals have the best chance of survival and reproduction. • “Crossover” operators: - Parents are selected. - Parents pass their genetic material to children. • Mutation: individuals are subject to random changes in their genetic material.Features of Evolution • High degree of parallelism (many individuals in a population) • New individuals (“next state / neighboring states”): Derived by combining “parents” (“crossover operation”) Random changes also happen (“mutations”) • Selection of next generation: Based on survival of the fittest: the most fit parents tend to be used to generate new individuals.General Idea • Maintain a population of individuals (states / strings / candidate solutions) • Each individual is evaluated using a fitness function, i.e. an objective function. The fitness scores force individuals to compete for the privilege of survival and reproduction. • Generate a sequence of generations: - From the current generation, select pairs of individuals (based on fitness) to generate new individuals, using crossover. • Introduce some noise through random mutations.