Abstract
Heuristic search methods have been increasingly applied to combinatorial optimizationproblems. While a specific problem defines a unique search space, different “landscapes”are created by the different heuristic search operators used to search it. In this paper, asimple example will be used to illustrate the fact that the landscape structure changes withthe operator; indeed, it often depends even on the way the operators are applied. Recentattention has focused on trying to better understand the nature of these “landscapes”. Recentwork by Boese et al. [2] has shown that instances of the TSP are often characterised by a“big valley” structure in the case of a 2‐opt exchange operator, and a particular distancemetric. In this paper, their work is developed by investigating the question of how landscapeschange under different search operators in the case of the n/m/P/C max flowshop problem.Six operators and four distance metrics are defined, and the resulting landscapes examined.The work is further extended by proposing a statistical randomisation test to provide anumerical assessment of the landscape. Other conclusions relate to the existence of ultra‐metricity,and to the usefulness or otherwise of hybrid neighbourhood operators.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
P. Baldi and E.B. Baum, Caging and exhibiting utrametric structures, in: Neural Networks for Computing, ed. J. Denker, American Institute of Physics, 1986.
K.D. Boese, A.B. Kahng and S. Muddu, A new adaptive multi-start technique for combinatorial global optimizations, Operations Research Letters 16(1994)101-113.
F. Glover and M. Laguna, Tabu search, in: Modern Heuristic Techniques for Combinatorial Problems, ed. C.R. Reeves, Blackwell Scientific, Oxford, 1993, chapter 3. (Recently re-issued (1995) by McGraw-Hill, London.)
C. Höhn and C.R. Reeves, The crossover landscape for the onemax problem, in: Proceedings of the 2nd Nordic Workshop on Genetic Algorithms and their Applications, ed. J. Alander, University of Vaasa Press, Vaasa, Finland, 1996, pp. 27-43.
C. Höhn and C.R. Reeves, Are long path problems hard for genetic algorithms?, in: Parallel Problem-Solving from Nature — PPSN IV, eds. H.-M. Voigt, W. Ebeling, I. Rechenberg and H.-P. Schwefel, Springer, Berlin, 1996, pp. 134-143.
D.S. Johnson, Local optimization and the traveling salesman problem, in: Automata, Languages and Programming, Lecture Notes in Computer Science 443, eds. G. Goos and J. Hartmanis, Springer, Berlin, 1990, pp. 446-461.
M.G. Kendall, Rank Correlation Methods, Charles Griffin, London, 1962.
S. Kirkpatrick and G. Toulouse, Configuration space analysis of travelling salesman problems, J. Physique 46(1985)1277-1292.
B.F.J. Manly, Randomization and Monte Carlo Methods in Biology, Chapman and Hall, London, 1991.
N. Mantel, The detection of disease clustering and a generalized regression approach, Cancer Research 27(1967)209-220.
O. Martin, S.W. Otto and E.W. Felten, Large step Markov chains for the TSP incorporating local search heuristics, Operations Research Letters 11(1992)219-224.
C.R. Reeves and T. Yamada, Distance measures in the permutation flowshop problem, Technical Report, School of Mathematical and Information Sciences, Coventry University, UK, 1997.
E. Taillard, Benchmarks for basic scheduling problems, European Journal of OR 64(1993) 278-285.
T. Yamada and R. Nakano, Scheduling by genetic local search with multi-step crossover, in: Parallel Problem-Solving from Nature — PPSN IV, eds. H.-M. Voigt, W. Ebeling, I. Rechenberg and H.-P. Schwefel, Springer, Berlin, 1996, pp. 960-969.
G. Zweig, An effective tour construction and improvement proedure for the traveling salesman problem, Operations Research 43(1995)1049-1057.
Rights and permissions
About this article
Cite this article
Reeves, C. Landscapes, operators and heuristic search. Annals of Operations Research 86, 473–490 (1999). https://doi.org/10.1023/A:1018983524911
Issue Date:
DOI: https://doi.org/10.1023/A:1018983524911