Multi-start Methods

Rafael Martí (), Jose A. Lozano (), Alexander Mendiburu () and Leticia Hernando ()
Additional contact information
Rafael Martí: University of Valencia, Statistics and Operations Research Department
Jose A. Lozano: University of the Basque Country, Intelligent Systems Group, Department of Computer Science and Artificial Intelligence
Alexander Mendiburu: University of the Basque Country, Intelligent Systems Group, Department of Computer Architecture and Technology
Leticia Hernando: University of the Basque Country, Intelligent Systems Group, Department of Computer Science and Artificial Intelligence

Chapter 6 in Handbook of Heuristics, 2018, pp 155-175 from Springer

Abstract: Abstract Multi-start procedures were originally conceived as a way to exploit a local or neighborhood search procedure, by simply applying it from multiple random initial solutions. Modern multi-start methods usually incorporate a powerful form of diversification in the generation of solutions to help overcome local optimality. Different metaheuristics, such as GRASP or tabu search, have been applied to this end. This survey briefly sketches historical developments that have motivated the field and then focuses on modern contributions that define the current state of the art. Two classical categories of multi-start methods are considered according to their domain of application: global optimization and combinatorial optimization. Additionally, several methods are reviewed to estimate the number of local optima in combinatorial problems. The estimation of this number can help to establish the complexity of a given instance, and also to choose the most convenient neighborhood, which is especially interesting in the context of multi-start methods. Experiments on three well-known combinatorial optimization problems are included to illustrate the local optima estimation techniques.

Keywords: Metaheuristics; Multi-start methods; Local optima estimation (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:sprchp:978-3-319-07124-4_1

Ordering information: This item can be ordered from
http://www.springer.com/9783319071244

DOI: 10.1007/978-3-319-07124-4_1

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().