OPTIMISED SEARCH HEURISTICS A MAPPING OF PROCEDURES AND COMBINATORIAL OPTIMISATION PROBLEMS
OPTIMISED SEARCH HEURISTICS:
A MAPPING OF PROCEDURES AND COMBINATORIAL OPTIMISATION PROBLEMS
Susana Fernandes
Universidade do Algarve, Faro, Portugal
sfer@ualg.pt
Helena R. Lourenço
Universitat Pompeu Fabra, Barcelona, Spain
helena.ramalhinho@econ.upf.es
Abstract
Recently hybrid metaheuristics have been design to find solutions for combinatorial optimisation problems. We focus on hybrid procedures that combine local search based metaheuristics with exact algorithms of the operations research field. We present a mapping that outlines the metaheuristic and exact procedures used, the way they are related and the problems they have been applied to.
1. Introduction
Recently a new type of algorithms, called hybrid metaheuristics, has been design to find solutions for combinatorial optimisation problems. Under the name of hybrid metaheuristics there are a huge variety of different types of procedures. They vary according to the algorithms combined, the level of hybridisation, the order of execution, the control strategy adopted, etc…(Raidl 2006). See the surveys of (Blum et al. 2005), (Cotta 1998), (Cotta et al. 2005), (Dumitrescu et al. 2003), (El-Abd et al. 2005), (Puchinger et al. 2005) and (Talbi 2002) for overviews of different angles.
In this research we are particularly interested in hybrid procedures that combine local search based metaheuristics with exact algorithms of the operations research field. We name them Optimised Search Heuristics (OSH). We present how this kind of procedures has been applied to combinatorial optimisation problems. We start by comparing and examining the correspondences of two existent classifications of such procedures and transform the more general one adding a new item and renaming other. To stress the distribution of these applications over the different problems of combinatorial optimisation, we then group the problems following a classification of NP optimisation problems, and outline the heuristic and exact techniques used together. We also present a very brief abstract of each referenced paper, outlining problems, procedures and type of combination used.
热门文档