1Local Search/Stochastic Search Today’s Class of Search Problems• Given:– A set of states (or configurations) S = {X1..XM}– A function that evaluates each configuration: Eval(X)• Solve:– Find global extremum: Find X* such that Eval(X*) is greater than all Eval(Xi) for all possible values of XiEval(X)X*2Real-World Examples• VLSI layout: – X = placement of components + routing of interconnections– Eval = Distance between components + % unused + routing lengthPlacementFloorplanningChannel routingCompactionReal-World Examples• Scheduling: Given m machines, n jobs• X = assignment of jobs to machines• Eval = completion time of the n jobs (minimize)• Others: Vehicle routing, design, treatment sequencing, ………TimeMachinesJobs3What makes this challenging?• Problems of particular interest:– Set of configurations too large to be enumerated explicitly– Computation of Eval(.) may be expensive– There is no algorithm for finding the maximum of Eval(.) efficiently– Solutions with similar values of Eval(.) are considered equivalent for the problem at hand– We do not care how we get to X*, we care only about the description of the configuration X* (this is a key difference with the earlier search problems)Example: TSP (Traveling Salesperson Problem)• Find a tour of minimum length passing through each point once36752143675214X1= {1 2 5 3 6 7 4}X2= {1 2 5 4 7 6 3}Eval(X1) > Eval(X2)4367521Example: TSP (Traveling Salesperson Problem)• Configuration X = tour through nodes {1,..,N}• Eval = Length of path defined by a permutation of {1,..,N}• Find X* that realizes the minimum of Eval(X)• Size of search space = order (N-1)!/2 • Note: Solutions for N = hundreds of thousands43675214X1= {1 2 5 3 6 7 4}X2= {1 2 5 4 7 6 3}Eval(X1) > Eval(X2)Example: SAT (SATisfiability) LLLECAEDCEDBDCACBA∨¬∨¬¬∨¬∨¬¬∨∨∨∨¬∨¬∨4truetruetruetruetrueX25falsetruefalsetruetrueX1EvalEDCBA5Example: SAT (SATisfiability) • Configuration X = Vector of assignments of N Boolean variables• Eval(X) = Number of clauses that are satisfied given the assignments in X• Find X* that realizes the maximum of Eval(X)• Size of search space = 2N• Note: Solutions for 1000s of variables and clausesLLLECAEDCEDBDCACBA∨¬∨¬¬∨¬∨¬¬∨∨∨∨¬∨¬∨4truetruetruetruetrueX25falsetruefalsetruetrueX1EvalEDCBAEval(X) = 0Eval(X) = 2Eval(X) = 5Find a configuration in which no queen can attack any other queenExample: N-Queens6Example: N-Queens• Configuration X = Position of the N queens in Ncolumns• Eval(X) = Number of pairs of queens that are attacking each other• Find X* that realizes the minimum: Eval(X*) = 0• Size of search space: order NN• Note: Solutions for N = millionsEval(X) = 0Eval(X) = 2Eval(X) = 5Local Search• Assume that for each configuration X, we define a neighborhood (or “moveset”) Neighbors(X) that contains the set of configurations that can be reached from X in one “move”.1. Xo , Initial state2. Repeat until we are “satisfied” with the current configuration:3. Evaluate some of the neighbors in Neighbors(Xi)4. Select one of the neighbors Xi+15. Move to Xi+17Local Search1. Xo , Initial state2. Repeat until we are “satisfied” with the current configuration:3. Evaluate some of the neighbors in Neighbors(Xi)4. Select one of the neighbors Xi+15. Move to Xi+1The definition of the neighborhoods is not obvious or unique in general. The performance of the search algorithm depends critically on the definition of the neihborhood which is not straightforward in general.Ingredient 1. Selection strategy: How to decide which neighbor to acceptIngredient 2. Stopping conditionSimplest ExampleS = {1,..,100}Neighbors(X) = {X-1,X+1}8Simplest Example• We are interested in the global maximum, but we may have to be satisfied with a local maximum• In fact, at each iteration, we can check only for local optimality• The challenge: Try to achieve global optimality through a sequence of local movesS = {1,..,100}Neighbors(X) = {X-1,X+1}Global optimum Eval(X*) >= Eval(X) for all XsLocal optimum Eval(X*) >= Eval(X) for all Xs in Neighbors(X)Most Basic Algorithm: Hill-Climbing (Greedy Local Search)• X Initial configuration• Iterate:1. E Eval(X)2.N Neighbors(X)3. For each Xiin NEi Eval(Xi)4. If all Ei’s are lower than EReturn XElsei* = argmaxi(Ei) X Xi* E Ei*9More Interesting Examples• How can we define Neighbors(X)?3675214LLLECAEDCEDBDCACBA∨¬∨¬¬∨¬∨¬¬∨∨∨∨¬∨¬∨TSPSATN-QueensIssuesMultiple “poor” local maxima Plateau = constant region of Eval(.)XstartX*Eval(X)Ridge = Impossible to reach X* from Xstartusing uphill moves only10Issues• Constant memory usage• All we can hope is to find the local maximum “closest” to the initial configuration Can we do better than that?• Ridges and plateaux will plague all local search algorithms• Design of neighborhood is critical (as important as design of search algorithm)• Trade-off on size of neighborhood larger neighborhood = better chance of finding a good maximum but may require evaluating an enormous number of moves smaller neighborhood = smaller number of evaluation but may get stuck in poor local maxima11Stochastic Search: Randomized Hill-Climbing• X Initial configuration• Iterate:1. E Eval(X)2. X’ one configuration randomly selected in Neighbors (X)3. E’ Eval(X’)4. If E’ > EX X’E E’Critical change: We no longer select the best move in the entire neighborhoodUntil when?TSP Moves367521436752143675214Select 2 edgesInvert the order ofthe corresponding vertices“2-change” O(N2) neighborhood12367214Select 3 edges“3-change” O(N3) neighborhood…….. k-change853672148567214853167214853672148536724538Hill-Climbing: TSP Example2.1%1.0%3-Opt (Best of 1000)13.71.23.1%2.5%3-Opt3.6%1.9%2-Opt (Best of 1000)1114.9%4.5%2-OptRunning time (N=1000)Running time (N=100)% error from min cost(N=1000)% error from min cost(N=100)Data from: Aarts & Lenstra, “Local Search in Combinatorial Optimization”, Wiley Interscience Publisher13Hill-Climbing: TSP Example• k-opt = Hill-climbing with k-change neighborhood• Some results:– 3-opt better than 2-opt– 4-opt not substantially better given increase in computation time– Use random restart to increase probability of success– Better measure: % away from (estimated) minimum cost2.1%1.0%3-Opt (Best of
View Full Document
Unlocking...