Article ID: | iaor20012442 |
Country: | United Kingdom |
Volume: | 6 |
Issue: | 6 |
Start Page Number: | 557 |
End Page Number: | 570 |
Publication Date: | Nov 1999 |
Journal: | International Transactions in Operational Research |
Authors: | Preux Ph., Talbi E.-G. |
Keywords: | metaheuristics |
Metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. However, the choice of a particular algorithm to optimize a certain problem is still mainly driven by some sort of devotion of its author to a certain technique rather than by a rationalistic choice driven by reason. Hybrid algorithms have shown their ability to provide local optima of high quality. Hybridization of algorithms is still in its infancy: certain combinations of algorithms have experimentally shown their performance, though the reasons of their success is not always really clear. In order to add some rationale to these issues, we study the structure of search spaces and attempt to relate it to the performance of algorithms. We wish to explain the behavior of search algorithms with this knowledge and provide guidelines in the design of hybrid algorithms. This paper briefly reviews the current knowledge we have on search spaces of combinatorial optimization problems. Then, we discuss hybridization and present a general classification of the way hybridization can be conducted in the light of our knowledge of the structure of search spaces.