University of Nottingham School of Computer Science 1Heuristic Search Methods Dr Dario Landa- Silva Lecture 8 – Hybrid Heuristics •Hybrids of SA, TS and GA •Types of Hybrid Heuristics •Examples of Hybrid Heuristics Learning outcomes: − Understand the principles and motivations for hybrid heuristics. − Recognise the different ways in which hybrid heuristics have been designed and classified. − Describe the architecture and rationale for some examples of hybrid heuristic methods. PA184 - Heuristic Search Methods University of Nottingham School of Computer Science 2Heuristic Search Methods Dr Dario Landa- Silva Hybrids of SA, TS and GA Three classic and very representative examples of heuristic and evolutionary search procedures are: − Simulated Annealing (SA) − Tabu Search (TS) − Genetic Algorithms (GA) Combinations of the above techniques were among the first hybrid heuristic algorithms proposed in the literature. A good example is the hybrid approach proposed in: Bennett L. Fox. Integrating and accelerating tabu search, simulated annealing and genetic algorithms. Annals of operations research, Vol. 41, pp. 47-67, 1993. Typically, hybrid algorithms seeks to combine the strengths form different methods while counteracting their weaknesses and produce a method that has the key strategies needed in heuristic search. University of Nottingham School of Computer Science 3Heuristic Search Methods Dr Dario Landa- Silva Key strategies needed in heuristic search Heuristic Search Initialisation of Solutions Objective Function Evaluation Test Feasibility (repair if required) Generate Candidate SolutionsIntensification Diversification University of Nottingham School of Computer Science 4Heuristic Search Methods Dr Dario Landa- Silva Generate initial solution x Set best solution so far xbest = x Set current temperature T = T0 Explore N(x) and select one neighbour solution x’  N(x) Improving candidate solution? fitness(x’)  fitness (x) ? Calculate acceptance probability PA Stopping condition true? Output xbest no no yes x = x’ If fitness(x) > fitness(xbest) then xbest = x r = random [0,1] If PA  r then x = x’ Update temperature T according to the Cooling Schedule yes Simulated Annealing Population Genetic operators Memory structures Strategic oscillation University of Nottingham School of Computer Science 5Heuristic Search Methods Dr Dario Landa- Silva Generate initial solution x Set best solution so far xbest = x Initialise the Tabu List Explore N(x) and select one neighbour solution x’  N(x) no no yes x = x* If fitness(x) > fitness(xbest) then xbest = x yes Intensification Strategies Diversification Strategies Is the candidate solution x’ Tabu? Does x’ satisfy Aspiration Criteria? Add candidate solution x’ to set X’ Is the candidate set X’ complete? yes no Select best candidate solution x*X’ fitness(x*)  fitness (x) ? yes Update Tabu List, Aspiration Criteria, Intensification and Diversification strategies Stopping condition true? yes no Output xbest no Tabu Search Genetic operators Population Probabilistic acceptance University of Nottingham School of Computer Science 6Heuristic Search Methods Dr Dario Landa- Silva Create population of solutions (representation) Evaluate the fitness of each individual in the population Select parent individuals and apply crossover operators to generate offspring Select surviving individuals for the next generation (evaluate fitness) Stopping condition true? Output best solution yes no Select individuals and apply mutation operators Genetic Algorithm Local search heuristics Strategic oscillation Memory structures University of Nottingham School of Computer Science 7Heuristic Search Methods Dr Dario Landa- Silva Types of Hybrid Heuristics Preux and Talbi (1999) proposed the following classification of hybrid evolutionary algorithms. Hybrid EA Sequential Parallel Synchronous Asynchronous Homogeneous Heterogeneous Global FunctionalPartial University of Nottingham School of Computer Science 8Heuristic Search Methods Dr Dario Landa- Silva Example 8.1 A parallel asynchronous heterogeneous functional hybrid algorithm in the classification of Preux and Talbi (1999) can be illustrated as follows. TS TS TS TS... Parallel Tabu Search Control and communication medium Memory Solutions Genetic algorithm (diversification task) Solves timetabling problem Generates solutions in unexplored areas Note: these algorithms are also called cooperative meta-heuristics in recent literature. University of Nottingham School of Computer Science 9Heuristic Search Methods Dr Dario Landa- Silva Later, Talbi (2002) proposed a similar classification of hybrid meta- heuristics. Hybrid Meta-heuristics Low-level High-level Relay Co-evolutionary Homogeneous Heterogeneous Relay Co-evolutionary Global Partial General Specialist University of Nottingham School of Computer Science 10Heuristic Search Methods Dr Dario Landa- Silva Example 8.2 The following are some hybrid heuristics that have been proposed in the literature and can be classified according to the above taxonomies. Population Selection for reproduction Crossover (greedy heuristic) Mutation (tabu search) Selection for survival Hybrid 1 Greedy heuristic (population) Genetic algorithm (best individual) Tabu search (best solution) Hybrid 2 constructive heuristics improving heuristics destructive heuristics solutions Hybrid 3 University of Nottingham School of Computer Science 11Heuristic Search Methods Dr Dario Landa- Silva The number of articles and books describing some sort of hybrid algorithm involving heuristic methods is very large. Because heuristic methods are ‘general’ search approaches, the are almost no limits in the way hybrid algorithms can be conceived, depending almost entirely on the designer’s ability. These are just two examples of simple hybrid meta-heuristic methods: Thiemo Krink, Morten, Lovbjerg. The lifecycle model: combining particle swarm optimisation, genetic algorithms and hill climbers. In: Proceedings of the 7th International Conference on Parallel Problem Solving from Nature (PPSN VII), LNCS, Vol. 2439, pp. 621-630, Springer-Verlag, 2002. Dario Landa-Silva, Joe Henry Obit. Evolutionary Non-Linear Great Deluge for University Course Timetabling. In: Proceedings of the 2009 International Conference on Hybrid Artificial Intelligence Systems (HAIS 2009). LNAI, Vol. 5572, pp. 269-276, Springer-Verlag, 2009. Examples of Hybrid Heuristics University of Nottingham School of Computer Science 12Heuristic Search Methods Dr Dario Landa- Silva Example 8.3 The lifecycle model: combining particle swarm optimisation, genetic algorithms and hill climbers PSO particles GA individuals Stochastic Hill Climbers PSO Stage Xi is the particle’s position Vi is the particle’s velocity Pi is the particle’s best Pg is the global best position Xi = Xi + Vi Vi = calculated based on Inertia, current position, particle’s best, global best position and random factors. GA Stage Binary tournaments Arithmetic crossover Non-uniform mutation Elitism Stochastic HC Stage Neighbour Xn replaces Xc with some probability given by: p = 1/(1+exp((f(Xn)f(Xc))/T)) where T is a constant  10 University of Nottingham School of Computer Science 13Heuristic Search Methods Dr Dario Landa- Silva Example 8.4 An evolutionary non-linear great deluge. University of Nottingham School of Computer Science Prioritise penalised schedule days - badly scheduled days will be repaired first Neighbourhood moves to repair schedule Strategies implemented: - best of x swaps in an individual schedule - multi-neighbourhood search to select best move according to violations - accept non-improving moves as in Great Deluge 14Heuristic Search Methods Dr Dario Landa- Silva Example 8.5 Squeaky wheel optimisation (SWO) approach University of Nottingham School of Computer Science 15Heuristic Search Methods Dr Dario Landa- Silva Additional Reading Bennett L. Fox. Integrating and accelerating tabu search, simulated annealing and genetic algorithms. Annals of operations research. 41, 47-67, 1993. Fred Glover, LJames P. Kelly, Manuel Laguna. Genetic algorithms and tabu search: hybrids for optimization. Computers and operations research, 22(1), 111-134, 1995. Ph. Preux, E.-G. Talbi. Towards hybrid evolutionary algorithms. International Transactions in Operational Research, 6, 557-570 , 1999. E.-G. Talbi. A taxonomy of hybrid metaheuristics. Journal of heuristics, 8, 541-564, 2002. Günther R. Raidl. A unified view of hybrid metaheuristics. In; Proceedings of the 3rd International Workshop on Hybrid Metaheuristics (HM 2006), LNCS, Vol. 40-30, pp. 1-12, 2006.