Search Methods in Artificial Intelligence PDF

Search Methods in Artificial Intelligence Escaping Local Optima Deterministic Local Search Deepak Khemani Plaksha University Search Methods in A...

Search Methods in Artificial Intelligence Escaping Local Optima Deterministic Local Search Deepak Khemani Plaksha University Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Hill Climbing – a constant space algorithm Recap HC only looks at local neighbours of a node. It’s space requirement is thus constant! A vast improvement on the exponential space for BFS and DFS HC only moves to a better node. It terminates if it cannot. Consequently the time complexity is linear. It’s termination criterion is different. It stops when no better neighbour is available. It treats the problem as an optimization problem. However, it is not complete, and may not find the global optimum which corresponds to the solution! Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Steepest gradient ascent Recap Hill Climbing (for a maximization problem) Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University May end on a local maximum Recap Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University 8-puzzle: A Solution Recap 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 5 7 5 7 6 5 7 6 5 6 5 6 4 5 6 4 5 6 4 5 6 4 8 6 4 8 4 8 4 7 8 4 7 8 7 8 7 8 7 8 hHamming =4 hHamming = 3 hHamming =4 hHamming =4 hHamming =3 hHamming =2 hHamming =1 hHamming = 0 hManhattan = 5 hManhattan = 4 hManhattan = 5 hManhattan = 4 hManhattan = 3 hManhattan = 2 hManhattan = 1 hManhattan = 0 Manhattan distance Hamming distance A local minimum A plot of heuristic value along the solution path Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Escaping local optima Given that it is difficult to define heuristic functions that are monotonic and well behaved the alternative is to look for algorithms that can do better than Hill Climbing. We look at three deterministic methods next, and will look at randomized methods later First we look at searching in the solution space or plan space Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Solution Space Search By solution space search we mean a formulation of the search problem such that when we find the goal node we have the solution and we are done. We do not have to reconstruct the path. Configuration problems fall easily into this category. Every node in the search space is a candidate solution. A candidate is a solution if it satisfies the goal description. Note: Planning problems can be solved with solution space search too. Then we say we are searching in the plan space. Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Synthesis vs. Perturbation Synthesis methods are constructive methods. Starting with the initial state we build the solution piece by piece. a b c d e f a b c d e f a b c d e f 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 1 2 3 4 56 The index i A representation: [a, c, e, b, f, d] The column in the ith row Perturbation: Permuting the list results in new candidates Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University The SAT problem Given a Boolean formula made up of a set of propositional variables V= {a, b, c, d, e, … } each of which can be true or false, or 1 or 0, to find an assignment for the variables such that the given formula evaluates to true or 1. For example, F = ((aV~e) Ù (eV~c)) É (~cV~d) can be made true by the assignment {a=true, c=true, d=false, e=false} amongst others. Very often SAT problems are studied in the Conjunctive Normal Form (CNF). For example, the following formula has five variables (a,b,c,d,e) and six clauses. (bV~c) Ù (cV~d) Ù (~b) Ù (~aV~e) Ù (eV~c) Ù (~cV~d) Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Solution Space Search and Perturbative methods The Solution Space is the space of candidate solutions. A search method generates the neighbours of a candidate by applying some perturbation to the given candidate MoveGen function = neighbourhood function A SAT problem with N variables has 2N candidates - where each candidate is a N bit string of 0s and 1s When N= 7, a neigbourhood function may change one bit. 1011010 0011010 1111010 1001010 1010010 1011110 1011000 1011011 Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University  The Travelling Salesperson Problem (TSP) is considered by many to be the holy grail of computer science Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University The Traveling Salesman Problem (TSP) Given a set of cities and given a distance measure between every pair of cities, the task is to find a Hamiltonian cycle, visiting each city exactly once, having least cost. When the underlying graph is not completely connected we can add the missing edges with very high cost. - then every permutation is a candidate The TSP is NP-hard. A collection of problems from various sources and problems with known optimal solutions is available at TSPLIB http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University TSP : Greedy Constructive Methods An example where it does not work à Nearest Neighbour Heuristic Start at some city. Move to nearest neighbour as long as it does not close the loop prematurely Variations: Extend the partial tour at either end. Greedy Heuristic Sort the edges Add shortest available edge to the tour as long as it does not close the loop prematurely Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University TSP : Greedy Constructive Methods Nearest Neighbour Heuristic Start Start at some city. Move to nearest neighbour as long as it does not close the loop prematurely An example run à Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University TSP : Greedy Constructive Methods Some early edges…. Greedy Heuristic Sort the edges Add shortest available edge to the tour as long as it does not close the loop prematurely Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Savings Heuristic The Savings Heuristic starts with (n-1) tours of length 2 anchored on a base vertex and performs (n-2) merge operations to construct the tour. Remove two edges connected to the base vertex from two loops and add an edge to connect the two hanging vertices. The two edges are chosen such that there is maximal savings of (total) cost in the resulting graph. Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University The constructive algorithms in action Tours found by some heuristic constructive algorithms. Figure taken from http://www.research.att.com/~dsj/chtsp/ Page not found from the link Greedy Tour Nearest Neighbour Tour Savings Tour Optimal Tour Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Solution space : Perturbation operators In the 2-city-exchange the twoshaded cities exchange their position in the path/order representation. The new tour has the dashed edges instead of the four broken ones in the linear order. The two cities can be selected in nC2 ways Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Two Edge Exchange In the 2-edge-exchange the tour is altered as shown. The two edges can be selected in nC2 ways Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Three-edge Exchange In 3-edge-exchange three edges are removed and replaced by other edges. This can be done in four ways. The three edges can be selected in nC3 ways. The 2-city exchange is one case of the 4-edge exchange. Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Computational Complexity Both the SAT and the TSP problems are hard problems Both have huge search spaces – hence local search! SAT is NP-Complete: requires exponential time to solve can be verified in polynomial time TSP is NP-Hard: requires factorial time to solve cannot be verified easily Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Exploding Search Spaces N Candidates in SAT: 2N Candidates in TSP: N! Ratio 1 2 1 0.5 2 4 2 0.5 3 8 6 0.75 4 16 24 1.5 5 32 120 3.75 6 64 720 11.25 7 128 5040 39.38 8 256 40,320 157.5 50 1,125,899,906,842,624 3.041409320×1064 3×1049 100 1.267650600 ×1030 9.332621544×10157 10127 Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Worst case time to solve SAT with 50 variables N SAT: 2N TSP (brute force): N! Ratio 50 1,125,899,906,842,624 3.041409320×1064 3×1049 Inspecting a million nodes a second: 1,125,899,906 seconds Assuming a 100 seconds in a minute: 11258999 minutes Assuming a 100 minutes in an hour: 112589 hours Assuming a 100 hours in a day: 1125 days Assuming a 1000 days in a year: 1.1 year Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Worst case time to solve SAT with 100 variables N SAT: 2N TSP (brute force): N! Ratio 100 1.267650600 ×1030 9.332621544×10157 10127 Inspecting a million nodes a second: 1.27×1024 seconds Assuming a 100 seconds in a minute: 1.27×1022 minutes Assuming a 100 minutes in an hour: 1.27×1020 hours Assuming a 100 hours in a day: 1.27×1018 day Assuming a 1000 days in a year: 1.27×1015 years Given a 100 years in a century: 1.27×1013 centuries 12700000000000 centuries! Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Escaping local optima Given that it is difficult to define heuristic functions that are monotonic and well behaved the alternative is to look for algorithms that can do better than Hill Climbing. We look at another deterministic method next, and will look at randomized methods later First we look at searching in the solution space or plan space Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Hill Climbing – a local search algorithm Recap Move to the best neighbour if it is better, else terminate Hill Climbing N ß Start newNode ß best(moveGen (N)) While newNode is better than N Do N ß newNode newNode ß best(moveGen (N)) endWhile return N End In practice sorting is not needed, only the best node Algorithm Hill Climbing Hill Climbing EXPLOITS the gradient or h(N) Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Exploration Escaping local optima calls for loosening the shackles of the heuristic function. The gradient leads to the local optimum. One needs a tendency of EXPLORATION too Exploitation pulls the search along the gradient Exploration leads it away from the trodden path We look at approaches to add exploration to search Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Beam Search Look at more than one option at each level. After all computer memory is becoming For a beam width b, look at best b options. cheaper Beam Search with beam width = 2 Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Beam Search for SAT (b V ~c) Ù (c V ~d) Ù (~b) Ù (~a V ~e) Ù (e V ~c) Ù (~c V ~d) 3 11111 h(n) = number of clauses satisfied A maximizing problem 4 01111 3 10111 3 11011 4 11101 3 11110 11111 00111 01011 01101 01110 01101 10101 11001 11111 11100 3 4 4 5 3 * 5 4 4 3 4 11101 00101 01001 01111 01100 11101 00101 01001 01111 01100 4 5 5 4 4 4 5 5 4 4 Beam Search with width = 2 fails to solve the SAT problem starting with 11111. Starting with a value 3 the solution should be reached in 3 steps, because it is Hill Climbing. In fact the node marked * leads to a solution in three steps. Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Different neighbourhood functions Consider a SAT problem with 5 variables. We can try different neighbourhood functions. Let Ni stand for a neighbourhood function that flips i bits. Consider N1 and N2 01111 10111 11011 11101 11110 N1 has 5 neighbours 11111 N2 has 10 neighbours 11100 11010 10110 01110 11001 10101 01101 10011 01011 00111 Let N12 stand for changing 1 or 2 bits. This will have 15 neighbours We can devise more and more dense neighbourhood functions with the most dense being N1-n where n is the number of variables, and N1-n stands for changing any of 1 to n bits. Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Effect of density on performance of Hill Climbing Hill Climbing Inspect all neighbours Move to the best neighbour if it is better than current node Hill climbing gets stuck on a local optimum when none of the neighbours is better than the current node The denser the neighbourhood the less likely this is, but the denser the neighbourhood the more the number of neighbours that has to be inspected at each step Observe that N1-n has 2n neighbours ! Inspecting them amounts to brute force search Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Variable Neighbourhood Descent VariableNeighbourhoodDescent() 1 node ¬ start 2 for i ¬ 1 to n 3 do moveGen ¬ MoveGen(i) 4 node ¬ HillClimbing(node, moveGen) 5 return node The algorithm assumes that the function moveGen can be passed as a parameter. It assumes that there are N moveGen functions sorted according to the density of the neighbourhoods produced. The hope is that most of the “climbing” will be done with sparser neighbourhood functions. Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Best Neighbour– a variation of Hill Climbing Move to the best neighbour anyway Best Neighbour N ß Start bestSeen ß N Until some termination criterion N ß best(moveGen (N)) IF N better than bestSeen bestSeen ß N return bestSeen End Observe: Algorithm needs external criterion to terminate Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Getting off a Local Optima Can Best Neighbour find a path to a better optimum? Algorithm Best Neighbour does get off the optimum BUT Moves right back in the next cycle! Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Tabu Search – not allowed back immediately Move to the best neighbour anyway, Best Neighbour N ß Start but only if it is not tabu bestSeen ß N Until some termination criterion N ß best(allowed(moveGen (N)) IF N better than bestSeen bestSeen ß N return bestSeen End The word tabu comes from the Tongan word to indicate things that cannot be touched because they are sacred. - Wikipedia Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Tabu Search for SAT When N= 7, the neigbourhood function N1 changes one bit. 1011010 0011010 1111010 1001010 1010010 1011110 1011000 1011011 Maintain a memory array M that keeps track of how many moves ago a bit was changed Initially M = 0 0 0 0 0 0 0 A tabu tenure tt defines the window within which any bit cannot be changed Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Tabu Search: an illustration (let tt=2) 1011010 Initially M = 0 0 0 0 0 0 0 1001010 Change bit 3: M = 0 0 2 0 0 0 0 Cannot change bit 3 for 2 cycles 1001000 Change bit 6: M = 0 0 1 0 0 2 0 0001000 Change bit 1: M = 2 0 0 0 0 1 0 A tabu tenure tt defines the window within which any bit cannot be changed Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Tabu Search – ASPIRATION criterion Move to the best neighbour anyway, Best Neighbour N ß Start but only if it is not tabu bestSeen ß N Until some termination criterion N ß best(allowed(moveGen (N)) IF N better than bestSeen bestSeen ß N return bestSeen End If a tabu move results in a node that is better than bestSeen then make an exception for it (that is, add it to allowed set). Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Tabu Search: driving search into newer areas Maintain a frequency array F that keeps track of how many times a bit was changed Initially F = 0 0 0 0 0 0 0 Let F = F1 F2 F3 F4 F5 F6 F7 Penalize each move by a factor proportional to frequency. Let nodei be generated by changing the ith bit eval(nodei) ß eval(nodei) - Fi - for a maximization problem Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University The solution space for a 4 variable SAT problem 0100 1100 MoveGen = N1 1110 0110 1111 0111 1101 0101 1001 0001 1011 0011 1010 0010 0000 1000 Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University A formula with 6 clauses F = (aÚ¬b)Ù(¬aÚbÚc)Ù(¬cÚd)Ù(d)Ù(¬aÚbÚd)Ù(¬aÚ¬d) h = number of satisfied clauses 0100 1100 4 1110 5 4 0110 3 1111 5 0111 5 1101 5 0101 1001 5 4 0001 1011 6 5 0011 1010 6 3 0010 4 3 0000 1000 5 Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Gradients and ridges F = (aÚ¬b)Ù(¬aÚbÚc)Ù(¬cÚd)Ù(d)Ù(¬aÚbÚd)Ù(¬aÚ¬d) h = number of satisfied clauses 0100 1100 4 1110 5 a ridge 4 0110 one of multiple best 3 1111 5 neighbours 0111 5 1101 unique best 5 neighbour 0101 1001 5 4 0001 1011 6 5 0011 1010 6 3 0010 4 3 0000 1000 5 Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Maxima: global and local F = (aÚ¬b)Ù(¬aÚbÚc)Ù(¬cÚd)Ù(d)Ù(¬aÚbÚd)Ù(¬aÚ¬d) h = number of satisfied clauses 0100 1100 4 1110 5 local maximum 4 0110 3 1111 global maximum 5 0111 5 1101 5 0101 1001 5 4 0001 1011 6 5 0011 1010 6 3 0010 4 3 0000 1000 5 Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Tabu Search F = (aÚ¬b)Ù(¬aÚbÚc)Ù(¬cÚd)Ù(d)Ù(¬aÚbÚd)Ù(¬aÚ¬d) h = number of satisfied clauses 0100 1100 4 1110 5 4 Starting from here Tabu Search 0110 3 1111 traverses one of the three 5 possible routes along the ridges 0111 5 1101 to reach the goal. 5 0101 It can escape from local optima. 5 1001 4 0001 1011 6 5 0011 1010 6 3 0010 4 3 0000 1000 5 Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University Iterated Hill Climbing F = (aÚ¬b)Ù(¬aÚbÚc)Ù(¬cÚd)Ù(d)Ù(¬aÚbÚd)Ù(¬aÚ¬d) h = number of satisfied clauses 0100 1100 4 1110 5 Hill Climbing reaches solution from here 4 0110 3 1111 5 What is the sanctity of the start node? 0111 Why not choose different starting points? 5 1101 5 Watch this space… 0101 1001 5 4 0001 1011 6 5 0011 1010 6 3 0010 4 3 0000 1000 5 Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University  End Deterministic Local Search Next Randomized Algorithms Search Methods in Artificial Intelligence Deepak Khemani, Plaksha University