Local SearchCS472/CS473 — Fall 2005Slide CS472 – Local Search 1Scaling Up• So far, we have considered methods that systematicallyexplore the full search space, possibly using principledpruning (A* etc.).• The current best such algorithms (RBFS / SMA*) canhandle search spaces of up to 10100states→∼500 binary valued variables.• But search spaces for some real-world problems might bemuch bigger — e.g. 1030,000states.• Here, a completely different kind of search is needed.→ Local Search MethodsSlide CS472 – Local Search 2Optimization Problems• We’re interested in the Goal State — not in how to getthere.• Optimization Problem:– State: vector of variables– Objective Function: f : state → – Goal: find state that minimizes objective function• Examples: VLSI layout, job scheduling, map coloring,N-Queens.Slide CS472 – Local Search 3ExampleSlide CS472 – Local Search 4Local 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 thatstate• Generally require a complete state description.Slide CS472 – Local Search 5Hill-Climbing Searchfunction HILL-CLIMBING(problem) returns a solution stateinputs: problem, a problemstatic: current, a nodenext, a nodecurrentMAKE-NODE(INITIAL-STAT E[problem])loop donexta highest-valuedsuccessor of currentif VALUE[next] < VALUE[current] then return currentcurrentnextendSlide CS472 – Local Search 6evaluationcurrentstateSlide CS472 – Local Search 7Hill Climbing Pathologiescurrentstateobjective functionstate spaceglobal maximumlocal maximum"flat" local maximumshoulderSlide CS472 – Local Search 8Improvements to Basic Local SearchIssue: How to move more quickly to successively higherplateaus and avoid getting “stuck” / local minima.Idea: Introduce uphill moves (“noise”) to escape from longplateaus (or true local minima).Strategies :• Multiple runs from randomly generated initial states• Random-restart hill-climbing• Tabu search• Simulated Annealing• Genetic AlgorithmsSlide CS472 – Local Search 9Variations on Hill-Climbing1. random restarts: simply restart at a new randomstate after a pre-defined number of local steps.2. tabu: prevent returning quickly to same state.Implementation: Keep fixed length queue (“tabu list”):add most recent step to queue; drop “oldest” step.Never make step that’s currently on the tabu list.Demo (CS473 Project by Matt Taylor):http : //www.cs.cornell.edu/selman/Demos/index.htmlSlide CS472 – Local Search 10Simulated AnnealingIdea:Use conventional hill-climbing techniques, but occasionallytake a step in a direction other than that in which the rateof change is maximal.As time passes, the probability that a down-hill step is takenis gradually reduced and the size of any down-hill step takenis decreased.Kirkpatrick et al. 1982; Metropolis et al. 1953.Slide CS472 – Local Search 11Simulated Annealing Algorithmcurrent ← initial statefor t ← 1 to inf doT ← schedule[t]if T = 0 then return currentnext ← randomly selected successor of current∆E ← f(next)-f(current)if ∆E>0thencurrent ← nextelse current ← next only with probability e∆E/TSlide CS472 – Local Search 12Genetic 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 standardlocal search.Slide CS472 – Local Search 13Features of evolution• High degree of parallelism• New individuals (“next state / neighboring states”):derived from “parents” (“crossover operation”)genetic mutations• Selection of next generation:based on survival of the fittestSlide CS472 – Local Search 14Genetic AlgorithmsInspired by biological processes that produce genetic changein populations of individuals.Genetic algorithms (GAs) are local search proceduresthat usually the following basic elements:• A Darwinian notion of fitness: the most fit individualshave the best chance of survival and reproduction.• Mating operators:– Parents are selected.– Parents pass their genetic material to children.– Mutation: individuals are subject to random changesin their genetic material.Slide CS472 – Local Search 15General 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 tocompete 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, usingcrossover.• Introduce some noise through random mutations.• Hope that average and maximum fitness (i.e. value to beoptimized) increases over time.Slide CS472 – Local Search 16Genetic algorithms as search• Genetic algorithms are local heuristic search algorithms.• Especially good for problems that have large and poorlyunderstood search spaces.• Genetic algorithms use a randomized parallel beamsearch to explore the state space.• You must be able to define a good fitness function, andof course, a good state representation.Slide CS472 – Local Search 17Binary string representations• Individuals are usually represented as a string over afinite alphabet, usually bit strings.• Individuals represented can be arbitrarily complex.• E.g. each component of the state description is allocateda specific portion of the string, which encodes the valuesthat are acceptable.• Bit string representation allows crossover operation tochange multiple values in the state description.Crossover and mutation can also produce previouslyunseen values.Slide CS472 – Local Search 188-queens State Representationoption 1: 86427531option 2: 111 101 011 001 110 100 010 000Slide CS472 – Local Search 19GA: High-level Algorithm32252124(a)Initial Population(b)Fitness Function(c)Selection(d)Cross−Over(e)Mutation247485523275241124415124242320325432131129%31%26%14%3275241124748552327524112441512432748552247524113275212424415411247524113274815224415417Slide CS472 – Local Search 20Crossover Example+=Slide CS472 – Local Search 21Another ExampleWorld championship chocolate chip cookie recipe.flour sugar salt chips vanilla fitness14 1 2 16 12 4.5 3 1 14 23211814 2.2 2.5 2.5 16 25 4.1