Landscapes, operators and heuristic search

C.R. Reeves

Annals of Operations Research, 1999, vol. 86, issue 0, 473-490

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. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018983524911 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:86:y:1999:i:0:p:473-490:10.1023/a:1018983524911

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018983524911

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().