PA184 ■ Heuristic Search Methods Lecture 2 - Principles of Heuristic Search •Traditional Techniques •Motivation for Heuristic Search •Basic Concepts in Heuristic Search •Description of Seminar Activity 2 Learning outcomes: - appreciate the limitations of some classical search algorithms - understand the key differences between heuristic and classical optimisation methods - describe the key concepts of heuristic search - analyse some representations, fitness functions and greedy algorithms for some COPs University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 1 Traditional Techniques Mathematical Programming Refers to modelling optimisation problems using formulations based on mathematical expressions. Examples of classical models are: - Linear programming (LP) problems - Integer programming (IP) problems - Mixed integer programming (MIP) problems Then, the models are solved with classical techniques such as: - Simplex method - Branch and bound - Branch and cut - Dynamic programming Even with improved versions of the above techniques, solving very large problems might not be practical. University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 2 The general LP formulation has the following elements' - Parameters - Decision variables - Linear objective function - Linear constraints An LP problem induces a search space with feasible and infeasible regions. The goal is to find the optimal solution(s) which are located in the corner points of the feasible region. Maximise Z — cyxx + c2x2 +... cnxn subject to constraints Xi + a22X2 . " a2nXn — b2 am1 X1 + am 2 X2 + QmnXn — bm Xy > 0, x2 > 0... Xn > 0 University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 3 The linear conditions and non-integral requirements of LP models allow to establish optimality conditions exploited by solvers. This does not happen with IP,BIP, MIP models. 6 5 4 3 2 0 (1) optimal solution (in a corner point) / (4) 1 1 \ (2) x1 1 2 3 Maximise Z = 5 x1 + 4 x2 subject to 6x1 + 4x2 < 24 (1) x1 + 2 x2 < 6 (2) x2 - x1 < 1 (3) x2 < 2 (4) x1 > 0, x2 > 0 LP solution: x1 = 3.0 x2 = 1.5 Z = 21.0 IP solution: x1 = 4 x2 = 0 Z = 20 University of Nottingham School of Computer Science 456 Heuristic Search Methods Dr Dario Landa- Silva 4 1 Branch and Bound (B&B) seeks to reduce the search space explored by eliminating non-attractive alternative solutions. Two aspects are important to make B&B an efficient search method: - Branching strategy ■ Depth-first (branch and backtrack) ■ Breadth-first ■ Based on increasing order of cost - Quality of bounds (for pruning the tree) ■ Based on explored complete solutions ■ Based on relaxations (LP, Lagrangean, etc.) ■ Heuristics to generate bounds Also, problem-domain knowledge can be incorporated to make B&B more efficient for some specific problems through improvements in the branching technique and computation of tighter bounds. University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 5 An illustration of B&B Max Z = 9 x1 + 5 x2 + 6 x3 + 4 x4 s.t. 6x1 + 3x2 + 5x3 + 2x4 < 10 (1) x3 + x4 < 1 (2) - x1 + x3 < 0 (3) - x2 + x4 < 0 (4) x1, x2, x3, x4 e {0,1} B:bound S: solution B=0 0 Vx3 B=9 0 B=0 s1 s2 s3 s4 s5 s6 s7 Z=0 Inf. Inf. Inf. Z=5 Z=9 Inf. University of Nottingham School of Computer Science (2,3)/ V4) QV (1,2,4W (1) s8 s9 s10 s11 s12 s13 s14 s15 Inf. Z=9 Inf. Inf. Inf. Z=14 Inf. Inf. (1,2) Inf. Heuristic Search Methods Dr Dario Landa- Silva 6 Dynamic Programming (DP) seeks to solve the problem in stages by breaking down the problem into simpler problems. DP is a systematic procedure to determine the optimal combination of decisions that generates an optimal solution given as the overall optimal policy. DP algorithms are designed specifically for the problem in hand. The key ingredients of a dynamic programming approach are: - Stages - States - Decisions - Policies - Cost (state-state) University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 7 Motivation for Heuristic Search Real-world Optimisation Problems Real-world optimisation problems (combinatorial or continuous) are difficult to solve for several reasons: - Size of the search space is very large (exhaustive search impractical) - Simplified models are needed to facilitate an answer - Difficult to design an accurate evaluation function - Existence of large number of constraints - Difficult to collect accurate data - Human limitations to construct solutions University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 8 Size of the Search Space | S | In both continuous and combinatorial problems, | S | depends on the number of variables and their number of permissible values. 22 20 f (x, y) = x • expv s.t. 0 < x < 10 and 0 < y < 15 10.0 10 50 Minimise Z = XZ cjxj j=1 i=1 10 subject to ^xj = 1 for i = 1...50 (1) University of Nottingham School of Computer Science j=1 50 X tjXj < Tj for j = L..10(2) xj = 1 if task i assigned to worker j, 0 otherwise wl X3 Heuristic Search Methods Dr Dario Landa- Silva 9 Problem vs. Model A solution is only a solution in terms of the model used to represent the problem. Most times, assumptions have to be made to simplify the complexity of real-world problems. Constraints Hard constraints must be satisfied for a solution to be feasible. Soft constraints are not mandatory but desirable conditions in good quality solutions. University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 10 Example 2.1. Consider the following variant of the GAP (generalised assignment problem): Given n tasks, m workers, cij- is cost of assigning task i to worker j. Worker j has limited time available Tj. Worker j takes tj time to complete task i. Each task is assigned to exactly one worker. A worker can undertake more that one task depending on Tj. No worker can have more than k tasks assigned. If possible, each worker in the subset Wshould have ppercent of their available time free and each worker in Wmust not have only one task assigned. The set TL of large tasks should be uniformly distributed among all workers. The set D of'new' workers should not be assigned more than htasks. Assign all the tasks to the workers so that the total cost is minimised without exceeding Tj for any worker. How many hard constraints? How many soft constraints? University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 11 Basic Concepts in Heuristic Search Solution Representation •Different representations (encodings) for the same problem. •Defines the size of the search space. •An appropriate encoding (creativity?) is crucially important. Objective •Minimise or maximise or find one solution? Evaluation Function (fitness function) •Maps the representation of a solution to a numeric value that indicates the quality of the solution. •Exact or approximate evaluation? •Differentiate between feasible and infeasible solutions. University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 12 Search Problem Given search space S and a set of feasible solutions F c S, a search problem is to find a solution x e S such that: fitness_function(x) < fitness_function(y) Vy e F Two solutions x,y are said to be neighbours if they are 'close' to each other in the sense that the distance between their corresponding encodings or representations is within a certain limit. Some search algorithms work with complete solutions, i.e. try to go from the current solution to a better one. Example: neighbourhood search Other search algorithms work with partial solutions, i.e. construct a complete solution step by step. Example: greedy algorithms University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 13 Example 2.2. Consider a symmetric n-city TSP over a complete graph. Representation Evaluation Function Objective Neighbour Solutions permutation of integers 1 to n e.g. 13546278 total number of permutations : n! ignoring symmetric tours: — e.g. 13546278 = 87264531 2 (n -1)! ignoring shifted identical tours:--— e.g. 13546278 = 54627813 2 S is set of solutions and a solution s = c1c2c3 — cn then f(s) = d (q, + d (c2, c3) + — d (cn-1, cn) + d (cn, find s g S such that f (s) < f (s') Vs'g S i.e. find a tour with the minimum length 2 - opt move: interchanges 2 non - adjacent edges current: 13546278 neighbours: 13246578, 13746258, 13586274, etc. 2 - rightinsert move: moves a city 2 positions to the right current: 13546278 neighbours :15436278, 13542768, etc. University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 14 Example 2.2 (cont.) Greedy Algorithm 1 1. Select random starting city 2. Proceed to nearest unvisited city 3. Repeat step 2 until all cities are visited 4. Return to starting city Greedy Algorithm 2 1. Find shortest edge (ci,cj) and add cities ci,cj to the tour 2. Select next chapest edge (cr,ct) (making sure no city is visited more than once) 3. Add cities cr,ct to the tour 4. Repeat steps 2-3 until a tour is formed University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 15 Integrating Classical Methods and Heuristics Classical Optimization Method V • Use a classical method as part of a multi-stage approach in order to solve a part of the problem. • Embed a classical method within a heuristic approach. • Embed a heuristic approach within a classical method. • Cross-fertilization by incorporating an ingredient of a classical method into a heuristic approach. University of Nottingham Heuristic Search Methods 16 School of Computer Science Dr Dario Landa- Silva Additional Reading Chapters 1-4 of (Michalewicz,2004) D. Landa-Silva, F. Marikar, K. Le (2009). Heuristic approach for automated shelf space allocation. Proceedings of the 2009 ACM Symposium on Applied Computing (SAC 2009), Vol. 2, ACM press, 922-928. E. K. Burke, J.D. Landa Silva (2004). The design of memetic algorithms for scheduling and timetabling problems. In: Recent Advances in Memetic Algorithms, Studies in Fuzziness and Soft Computing, Vol. 166, Springer, 289-312. University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 17 Seminar Activity 2 The purpose of this seminar activity is to achieve an understanding of solution representation, greedy algorithms and neighbourhoods within the context of heuristic search. For the GAP described in Lecture 1, do the following: 1. Write the corresponding mathematical programming model. 2. For the variant of Example 2.1, indicate how the soft constraints are incorporated into the model. 3. Describe 2 or 3 alternative solution representation schemes. 4. Describe 1 or 2 greedy algorithms that can be used to generate solutions to the problem. 5. Describe some neighbourhood moves that can be used to generate neighbouring candidate solutions from a given solution X. University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 18