PA184 ■ Heuristic Search Methods Session April 2010 Dr Dario Landa-Silva dario.landasilva@nottingham.ac.uk http://www.cs.nott.ac.uk/~jds/ Lecture 1 - Introduction • Overview of the Module •An Insight into Heuristics •Description of Seminar Activity 1 Learning outcomes: understand purpose/scope/administration of the module; understand the role of heuristic search in continuous an combinatorial problems; describe main ideas that have contributed to the progress of heuristic search. University of Nottingham Heuristic Search Methods 1 School of Computer Science Dr Dario Landa- Silva Overview of the Module Aim of the Module Achieve an understanding of modern heuristic search techniques with emphasis in tackling search and optimisation problems. Heuristic Search and Optimisation refers to a set of computational techniques that aim to find good quality solutions to very difficult problems in search, optimisation, design, etc. while consuming a reasonable amount of computational resources. Heuristic methods are AI inspired approaches and are related both to computer science and operations research. Heuristic methods have been successfully applied to many problems in different areas including: engineering, management, finance, planning and scheduling, medicine, biology, automated navigation, image processing, robotics, art design, etc. University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 2 Module Contents Various heuristic methods are studied while covering important issues such as working principles, design and implementation, parameter tuning, experimental testing, etc. •Introduction •Principles of Heuristic Search •Local Search • Meta-heuristics •Evolutionary Algorithms • Constraint Handling •Evaluating Heuristic Performance •Hybrid Heuristics •Software Libraries for Heuristics •New Ideas and Future Research University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 3 Teaching Activities •2 hr Lecture (tutor-led) including Seminar activity (students-led). •Notes for the lectures are available at request. •Students are also expected to take notes in class. •The seminars are designed to promote an interactive learning environment. The purpose of the seminars are to discuss issues studied in class, report progress and interchanges ideas about the coursework, etc. •During some of the seminars, students will be asked to give a short presentation about a given topic or engage in discussions about additional reading material. Reading List ElGhazali Talbi. Metaheuristics-' From Design to Implementation. Wiley, 2009. Zbigniew Michalewicz, David B Fogel. How to solve it '-modern heuristics, 2nd ed. Springer, 2004. University of Nottingham Heuristic Search Methods 4 School of Computer Science Dr Dario Landa- Silva Other Resources •Research articles •Software libraries •Research seminars Assessment The module is assessed by examination and coursework •Examination: Focused on the principles of heuristic search (70%). •Coursework: Implementation of heuristic search methods (15%). •Report: Progress report on implementation of coursework and the seminar activities (15%). Deadlines: •Examination: TBA •Coursework and Report: 4 June 2010 University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 5 An Insight Into Heuristics Describing Heuristics A heuristic search method is a technique that seeks good quality (i.e. near optimal) solutions at a reasonable computation time but that is not able to guarantee either feasibility or optimality. There is a range of heuristic methods including: simple constructive heuristics, local search, meta-heuristics, hyper-heuristics, hybrids, evolutionary methods, etc. Societies and Publications •Related conferences include: CEC, GECCO, HM, MIC, PPSN, SLS •Related journals include: Applied soft computing, Evolutionary computation, Evolutionary intelligence, IEEE Trans. on EC, Intl. journal of meta-heuristics, Journal of heuristics, Memetic computing, Swarm intelligence and others. University of Nottingham Heuristic Search Methods 6 School of Computer Science Dr Dario Landa- Silva Concepts in Heuristic Search •Decision variables •Parameters •Objective function • Constraints •Feasible/Infeasible solutions •Search space (continuous/discrete) •Fitness landscape • Optimal solutions (local and global) •Near-optimal solutions •Bounds and gaps •Reasonable computational resources •Termination criteria • Continuous function optimisation • Complexity of problems and algorithms • Combinatorial optimisation University of Nottingham Heuristic Search Methods 7 School of Computer Science Dr Dario Landa- Silva Continuous Search Problems Decision variables can take fractional values (i.e. also integers). Continuous optimisation involves finding the exact values for the variables in a function so that the function value is optimised while the constraints are satisfied. Examples of (nonlinear) continuous search problems: f(x) = x6 -136x5 + 6800x4 -155000*3 +1570000xx - 5000000x s.t. 0 < x < 50 University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 8 Examples of (nonlinear) continuous search problems: 2 2 \ 20 f (x, y) = x • v s.t. 0 < x < 10 and 0 < y < 15 10.0 f (x, y) = S7w( x) + S7w( y) s.t. - 2 < x, y < 2 University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 9 Combinatorial Search Problems Decision variables only take discrete values (i.e. only integers and/or binary values). Combinatorial optimisation involves finding a setting for a discrete set of entities so that an objective function is optimised while the constraints are satisfied. Examples of combinatorial search problems: Travelling Salesman Problem (TSP). Given n cities with given distance dij between cities i and j. Find a tour to visit all the cities starting and finishing in the same point so that the total travelled distance is minimised. The 532-city TSP instance by Shen Lin of AT&T University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 10 Examples of combinatorial search problems: Generalised Assignment Problem (GAP). 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. Assign all the tasks to the workers so that the total cost is minimised without exceeding Tjfor any worker. 1 2 ... n 1 6/4 2/5 ... 6/3 6 2 6/2 2/3 ... 2/7 8 ... 3/3 1/5 ... 6/4 ... m 8/4 1/7 . 8/6 15 i =1...n University of Nottingham School of Computer Science j=1...m Heuristic Search Methods Dr Dario Landa- Silva 11 Sketch of the search space for a 5-city TSP instance •There are 5 decision variables xvx2,...x5 •A solution (tour) is a permutation of length equal to 5 •There are 5! = 120 different permutations (not all different tours) x1 CI C2 x2 C3 x2 X3 ) [X0 ( X3 ) ( X3 J ( X3 ) (X3 ) ( X3 ✓ I \ / 1 \ ✓ , \ ' i S ' i ^ ' i ^ C2/ C4 VC5 ( X0 ( X4 A A / \ / \ C2/ \C4 C1/C3 C4 C2 00 A / \ ' Cl I \C5 00 C4 x2 University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva C5 x2 ft C1 C2 C3 C4 x3 x3 x3 x3 12 Progress on Heuristic Search A heuristic is a 'rule of thumb' based on domain knowledge from a particular application, that gives guidance in the solution of a problem (Oxford Dictionary of Computing). A meta-heuristic is a iterative master process that guides and modifies the operations of subordinate heuristics to efficiently produce high-quality solutions (Voss et al. 1999). Constructive heuristics Cooperative Process (also competition) 4 Hybrid and Self-adaptation Neighbourhood Search Iterative Improvement Evolution Process (competition,recombination) i-s. Random 1-v> Restart Non-improving/Infeasible Solutions Accepted (probability, memory. threshold) Heuristics + Exact Methods Parallelism, Bio-inspired, etc. i-s. Automated 1- Desing University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 13 Additional Reading Section 13.1 of (Hillier and Frederick, 2005). Sections 1.1-1.3 of (Talbi, 2009). Silver, E. A. (2004). An overview of heuristic solution methods. Journal of the operational research society, 55, 936-956. Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM computing surveys, 35(3), 268-308. Hertz, A. and Widmer, M. (2003). Guidelinesfortheuseofmeta-heuristics in combinatorial optmization. European journal of operational research, 151(2), 247-252. The TSP website: http://www.tsp.gatech.edu/index.html University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 14 Seminar Activity 1 The purpose of this seminar activity is to achieve an understanding of the main concepts in heuristic search listed in slide 7 and other additional concepts identified during the reading. Students are asked to prepare a few-pages written report or few-slides or to describe and illustrate the main concepts in heuristic search. For this, in addition to this lecture notes, the suggested reading materials in the previous slide will be useful. Students will be asked to present and/or discuss their work in the seminar. In addition, please read the following article which then will be used during the seminar to further discuss the role of heuristic methods on solving the problem described in that article. Myers, D.C. and Mohite, M. (2009). Locating automated external defibrillators in a university community. Journal of the operational research society, 60, 869-872. University of Nottingham School of Computer Science Heuristic Search Methods Dr Dario Landa- Silva 15