Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2018 | OriginalPaper | Chapter

6. Multi-start Methods

Authors: Rafael Martí, Jose A. Lozano, Alexander Mendiburu, Leticia Hernando

Published in: Handbook of Heuristics

Publisher: Springer International Publishing

share
SHARE

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.
Literature
1.
go back to reference Albrecht A, Lane P, Steinhofel K (2008) Combinatorial landscape analysis for k-SAT instances. In: IEEE congress on evolutionary computation, CEC 2008, Hong Kong. IEEE World congress on computational intelligence, pp 2498–2504 Albrecht A, Lane P, Steinhofel K (2008) Combinatorial landscape analysis for k-SAT instances. In: IEEE congress on evolutionary computation, CEC 2008, Hong Kong. IEEE World congress on computational intelligence, pp 2498–2504
2.
go back to reference Albrecht A, Lane P, Steinhofel K (2010) Analysis of local search landscapes for k-SAT instances. Math Comput Sci 3(4):465–488 MathSciNetCrossRef Albrecht A, Lane P, Steinhofel K (2010) Analysis of local search landscapes for k-SAT instances. Math Comput Sci 3(4):465–488 MathSciNetCrossRef
3.
go back to reference Beausoleil R, Baldoquin G, Montejo R (2008) A multi-start and path relinking methods to deal with multiobjective knapsack problems. Ann Oper Res 157:105–133 MathSciNetCrossRef Beausoleil R, Baldoquin G, Montejo R (2008) A multi-start and path relinking methods to deal with multiobjective knapsack problems. Ann Oper Res 157:105–133 MathSciNetCrossRef
4.
go back to reference Boese K, Kahng A, Muddu S (1994) A new adaptive multi-start technique for combinatorial global optimisation. Oper Res Lett 16:103–113 CrossRef Boese K, Kahng A, Muddu S (1994) A new adaptive multi-start technique for combinatorial global optimisation. Oper Res Lett 16:103–113 CrossRef
5.
go back to reference Braysy O, Hasle G, Dullaert W (2004) A multi-start local search algorithm for the vehicle routing problem with time windows. Eur J Oper Res 159:586–605 MathSciNetCrossRef Braysy O, Hasle G, Dullaert W (2004) A multi-start local search algorithm for the vehicle routing problem with time windows. Eur J Oper Res 159:586–605 MathSciNetCrossRef
6.
go back to reference Chao A (1984) Nonparametric estimation of the number of classes in a population. Scand J Stat 11(4):265–270 MathSciNet Chao A (1984) Nonparametric estimation of the number of classes in a population. Scand J Stat 11(4):265–270 MathSciNet
7.
go back to reference Chao A, Bunge J (2002) Estimating the number of species in a stochastic abundance model. Biometrics 58(3):531–539 MathSciNetCrossRef Chao A, Bunge J (2002) Estimating the number of species in a stochastic abundance model. Biometrics 58(3):531–539 MathSciNetCrossRef
8.
9.
go back to reference Crowston WB, Glover F, Thompson GL, Trawick JD (1963) Probabilistic and parametric learning combinations of local job shop scheduling rules. Technical report 117, Carnegie-Mellon University, Pittsburgh Crowston WB, Glover F, Thompson GL, Trawick JD (1963) Probabilistic and parametric learning combinations of local job shop scheduling rules. Technical report 117, Carnegie-Mellon University, Pittsburgh
10.
go back to reference Dhouib S, Kharrat A, Chabchoub H (2010) A multi-start threshold accepting algorithm for multiple objective continuous optimization problems. Int J Numer Methods Eng 83:1498–1517 MathSciNetCrossRef Dhouib S, Kharrat A, Chabchoub H (2010) A multi-start threshold accepting algorithm for multiple objective continuous optimization problems. Int J Numer Methods Eng 83:1498–1517 MathSciNetCrossRef
11.
go back to reference Eremeev AV, Reeves CR (2002) Non-parametric estimation of properties of combinatorial landscapes. In: Cagnoni S, Gottlieb J, Hart E, Middendorf M, Raidl G (eds) Applications of evolutionary computing. Lecture notes in computer science, vol 2279. Springer, Berlin/Heidelberg, pp 31–40 CrossRef Eremeev AV, Reeves CR (2002) Non-parametric estimation of properties of combinatorial landscapes. In: Cagnoni S, Gottlieb J, Hart E, Middendorf M, Raidl G (eds) Applications of evolutionary computing. Lecture notes in computer science, vol 2279. Springer, Berlin/Heidelberg, pp 31–40 CrossRef
12.
go back to reference Eremeev AV, Reeves CR (2003) On confidence intervals for the number of local optima. In: Proceedings of EvoWorkshops 2003, Essex, pp 224–235 Eremeev AV, Reeves CR (2003) On confidence intervals for the number of local optima. In: Proceedings of EvoWorkshops 2003, Essex, pp 224–235
13.
go back to reference Essafi M, Delorme X, Dolgui A (2010) Balancing lines with CNC machines: a multi-start and based heuristic. CIRP J Manuf Sci Technol 2:176–182 CrossRef Essafi M, Delorme X, Dolgui A (2010) Balancing lines with CNC machines: a multi-start and based heuristic. CIRP J Manuf Sci Technol 2:176–182 CrossRef
14.
go back to reference Feo T, Resende M (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8:67–71 MathSciNetCrossRef Feo T, Resende M (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8:67–71 MathSciNetCrossRef
16.
go back to reference Fleurent C, Glover F (1999) Improved constructive multi-start strategies for the quadratic assignment problem using adaptive memory. INFORMS J Comput 11:198–204 MathSciNetCrossRef Fleurent C, Glover F (1999) Improved constructive multi-start strategies for the quadratic assignment problem using adaptive memory. INFORMS J Comput 11:198–204 MathSciNetCrossRef
17.
go back to reference Glover F (2000) Multi-start and strategic oscillation methods – principles to exploit adaptive memory. In: Laguna M, Gonzalez-Velarde J (eds) Computing tools for modeling optimization and simulation. Kluwer Academic, Boston, pp 1–25 Glover F (2000) Multi-start and strategic oscillation methods – principles to exploit adaptive memory. In: Laguna M, Gonzalez-Velarde J (eds) Computing tools for modeling optimization and simulation. Kluwer Academic, Boston, pp 1–25
18.
19.
go back to reference Grundel D, Krokhmal P, Oliveira C, Pardalos P (2007) On the number of local minima for the multidimensional assignment problem. J Combin Optim 13:1–18 MathSciNetCrossRef Grundel D, Krokhmal P, Oliveira C, Pardalos P (2007) On the number of local minima for the multidimensional assignment problem. J Combin Optim 13:1–18 MathSciNetCrossRef
20.
go back to reference Hagen L, Kahng A (1997) Combining problem reduction and adaptive multi-start: a new technique for superior iterative partitioning. IEEE Trans CAD 16:709–717 CrossRef Hagen L, Kahng A (1997) Combining problem reduction and adaptive multi-start: a new technique for superior iterative partitioning. IEEE Trans CAD 16:709–717 CrossRef
21.
22.
go back to reference Hernando L, Mendiburu A, Lozano JA (2013) An evaluation of methods for estimating the number of local optima in combinatorial optimization problems. Evol Comput 21(4):625–658 CrossRef Hernando L, Mendiburu A, Lozano JA (2013) An evaluation of methods for estimating the number of local optima in combinatorial optimization problems. Evol Comput 21(4):625–658 CrossRef
23.
go back to reference Hickernell F, Yuan Y (1997) A simple multistart algorithm for global optimization. OR Trans 1:1–11 Hickernell F, Yuan Y (1997) A simple multistart algorithm for global optimization. OR Trans 1:1–11
24.
go back to reference Hu X, Shonkwiler R, Spruill M (1994) Random restarts in global optimization. Ga Inst Technol 1:1–10 Hu X, Shonkwiler R, Spruill M (1994) Random restarts in global optimization. Ga Inst Technol 1:1–10
25.
go back to reference Kan AR, Timmer G (1987) Stochastic global optimization methods (Part II): multi level methods. Math Program 39:57–78 CrossRef Kan AR, Timmer G (1987) Stochastic global optimization methods (Part II): multi level methods. Math Program 39:57–78 CrossRef
26.
go back to reference Kan AR, Timmer G (1998) Global optimization. In: Kan R, Todds (eds) Handbooks in operations research and management science. North Holland, Amsterdam, pp 631–662 Kan AR, Timmer G (1998) Global optimization. In: Kan R, Todds (eds) Handbooks in operations research and management science. North Holland, Amsterdam, pp 631–662
27.
go back to reference Kaucic M (2013) A multi-start opposition-based particle swarm optimization algorithm with adaptive velocity for bound constrained global optimization. J Glob Optim 55:165–188 MathSciNetCrossRef Kaucic M (2013) A multi-start opposition-based particle swarm optimization algorithm with adaptive velocity for bound constrained global optimization. J Glob Optim 55:165–188 MathSciNetCrossRef
28.
go back to reference Lan G, DePuy G (2006) On the effectiveness of incorporating randomness and memory into a multi-start metaheuristic with application to the set covering problem. Comput Ind Eng 51:362–374 CrossRef Lan G, DePuy G (2006) On the effectiveness of incorporating randomness and memory into a multi-start metaheuristic with application to the set covering problem. Comput Ind Eng 51:362–374 CrossRef
29.
go back to reference Martí R, Reinelt G, Duarte A (2012) A benchmark library and a comparison of heuristic methods for the linear ordering problem. Comput Optim Appl 51(3):1297–1317 MathSciNetCrossRef Martí R, Reinelt G, Duarte A (2012) A benchmark library and a comparison of heuristic methods for the linear ordering problem. Comput Optim Appl 51(3):1297–1317 MathSciNetCrossRef
30.
go back to reference Martí R, Resende M, Ribeiro C (2013) Multi-start methods for combinatorial optimization. Eur J Oper Res 226(1):1–8 MathSciNetCrossRef Martí R, Resende M, Ribeiro C (2013) Multi-start methods for combinatorial optimization. Eur J Oper Res 226(1):1–8 MathSciNetCrossRef
31.
go back to reference Mayne DQ, Meewella C (1988) A non-clustering multistart algorithm for global optimization. In: Bensoussan A, Lions J-L (eds) Analysis and optimization of systems. Lecture notes in control and information sciences. Springer, Berlin/New York, pp 111–117 MATH Mayne DQ, Meewella C (1988) A non-clustering multistart algorithm for global optimization. In: Bensoussan A, Lions J-L (eds) Analysis and optimization of systems. Lecture notes in control and information sciences. Springer, Berlin/New York, pp 111–117 MATH
32.
go back to reference Mezmaz M, Melab N, Talbi E (2006) Using the multi-start and island models for parallel multi-objective optimization on the computational grid. In: Second IEEE international conference on e-science and grid computing, Amsterdam CrossRef Mezmaz M, Melab N, Talbi E (2006) Using the multi-start and island models for parallel multi-objective optimization on the computational grid. In: Second IEEE international conference on e-science and grid computing, Amsterdam CrossRef
33.
go back to reference Moreno J, Mladenovic N, Moreno-Vega J (1995) An statistical analysis of strategies for multistart heuristic searches for p-facility location-allocation problems. In: Eighth meeting of the EWG on locational analysis Lambrecht Moreno J, Mladenovic N, Moreno-Vega J (1995) An statistical analysis of strategies for multistart heuristic searches for p-facility location-allocation problems. In: Eighth meeting of the EWG on locational analysis Lambrecht
34.
go back to reference Muth JF, Thompson GL (1963) Industrial scheduling. Prentice-Hall, Englewood Cliffs Muth JF, Thompson GL (1963) Industrial scheduling. Prentice-Hall, Englewood Cliffs
35.
go back to reference Patterson R, Pirkul H, Rolland E (1999) Adaptive reasoning technique for the capacitated minimum spanning tree problem. J Heuristics 5:159–180 CrossRef Patterson R, Pirkul H, Rolland E (1999) Adaptive reasoning technique for the capacitated minimum spanning tree problem. J Heuristics 5:159–180 CrossRef
36.
go back to reference Reeves C, Aupetit-Bélaidouni M (2004) Estimating the number of solutions for SAT problems. In: Yao X, Burke E, Lozano J, Smith J, Merelo-Guervós J, Bullinaria J, Rowe J, Tino P, Kabán A, Schwefel HP (eds) Parallel problem solving from nature – PPSN VIII. Lecture notes in computer science, vol 3242. Springer, Berlin/Heidelberg, pp 101–110 Reeves C, Aupetit-Bélaidouni M (2004) Estimating the number of solutions for SAT problems. In: Yao X, Burke E, Lozano J, Smith J, Merelo-Guervós J, Bullinaria J, Rowe J, Tino P, Kabán A, Schwefel HP (eds) Parallel problem solving from nature – PPSN VIII. Lecture notes in computer science, vol 3242. Springer, Berlin/Heidelberg, pp 101–110
37.
go back to reference Resende M, Ribeiro C (2010) Greedy randomized adaptive search procedures: advances and applications. In: Gendreau M, Potvin JY (eds) Handbook of metaheuristics, 2nd edn. Springer, New York, pp 293–319 Resende M, Ribeiro C (2010) Greedy randomized adaptive search procedures: advances and applications. In: Gendreau M, Potvin JY (eds) Handbook of metaheuristics, 2nd edn. Springer, New York, pp 293–319
39.
go back to reference Taillard E, Badeau P, Gendreau M, Guertin F, Potvin J (1997) A tabu search heuristic of the vehicle routing problem with time windows. Transp Sci 31:170–186 CrossRef Taillard E, Badeau P, Gendreau M, Guertin F, Potvin J (1997) A tabu search heuristic of the vehicle routing problem with time windows. Transp Sci 31:170–186 CrossRef
40.
go back to reference Tu W, Mayne R (2002) An approach to multi-start clustering for global optimization with non-linear constraints. Int J Numer Methods Eng 53:2253–2269 MathSciNetCrossRef Tu W, Mayne R (2002) An approach to multi-start clustering for global optimization with non-linear constraints. Int J Numer Methods Eng 53:2253–2269 MathSciNetCrossRef
41.
go back to reference Ugray Z, Lasdon L, Plummer J, Glover F, Kelly J, Martí R (2007) Scatter search and local NLP solvers: a multistart framework for global optimization. INFORMS J Comput 19(3):328–340 MathSciNetCrossRef Ugray Z, Lasdon L, Plummer J, Glover F, Kelly J, Martí R (2007) Scatter search and local NLP solvers: a multistart framework for global optimization. INFORMS J Comput 19(3):328–340 MathSciNetCrossRef
42.
go back to reference Ugray Z, Lasdon L, Plummer J, Bussieck M (2009) Dynamic filters and randomized drivers for the multi-start global optimization algorithm MSNLP. Optim Methods Softw 24:4–5 MathSciNetCrossRef Ugray Z, Lasdon L, Plummer J, Bussieck M (2009) Dynamic filters and randomized drivers for the multi-start global optimization algorithm MSNLP. Optim Methods Softw 24:4–5 MathSciNetCrossRef
43.
go back to reference Villegas J, Prins C, Prodhon C, Medaglia A, Velasco N (2010) GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots. Eng Appl Artif Intell 23:780–794 CrossRef Villegas J, Prins C, Prodhon C, Medaglia A, Velasco N (2010) GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots. Eng Appl Artif Intell 23:780–794 CrossRef
Metadata
Title
Multi-start Methods
Authors
Rafael Martí
Jose A. Lozano
Alexander Mendiburu
Leticia Hernando
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_1

Premium Partner