Combining simulated annealing with local search heuristics. (English) Zbl 0851.90097

Martin, Olivier C.; Otto, Steve W.

Ann. Oper. Res. 63, 57-75 (1996).

Summary: We introduce a meta-heuristic to combine simulated annealing with local search methods for CO problems. This new class of Markov chains leads to significantly more powerful optimization methods than either simulated annealing or local search. The main idea is to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima. It makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. We have tested this meta-heuristic for the traveling salesman and graph partitioning problems. Tests on instances from public libraries and random ensembles quantify the power of the method. Our algorithm is able to solve large instances to optimality, improving upon local search methods very significantly. For the traveling salesman problem with randomly distributed cities in a square, the procedure improves on 3-opt by 1.6%, and on Lin-Kernighan local search by 1.3%. For the partitioning of sparse random graphs of average degree equal to 5, the improvement over Kernighan-Lin local search is 8.9%. For both CO problems, we obtain new best heuristics.

MSC:

90C27	Combinatorial optimization
90C35	Programming involving graphs or networks

Keywords:

meta-heuristic; simulated annealing; local search

Software:

TSPLIB

References:

[1]	O. Martin, S.W. Otto and E.W. Felten, Large-step Markov chains for the traveling salesman problem, Complex Syst. 5(1991)299–326. · Zbl 0736.90063
[2]	O. Martin, S.W. Otto and E.W. Felten, Large-step Markov chains for the TSP incorporating local search heuristics, Oper. Res. Lett. 11(1992)219–224. · Zbl 0760.90090
[3]	O.C. Martin and S.W. Otto, Partitioning of unstructured meshes for load balancing, Concurrency: Practice and Experience 7(1995)303–314.
[4]	E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys (eds.),The Traveling Salesman Problem (Wiley, 1984). · Zbl 0563.90075
[5]	M.W. Padberg and G. Rinaldi, A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev. 33(1991)60. · Zbl 0734.90060
[6]	G. Reinelt, TSPLIB–A traveling salesman problem library, ORSA J. Comput. 3(1991)376–384. · Zbl 0775.90293
[7]	S. Lin, Computer solutions of the traveling salesman problem, Bell Syst. Tech. J. 44(1965)2245. · Zbl 0136.14705
[8]	S. Lin and B. Kernighan, An effective heuristic algorithm for the traveling salesman problem, Oper. Res. 21(1973)498. · Zbl 0256.90038
[9]	S. Kirkpatrick, C. Gelatt and M. Vecchi, Optimization by simulated annealing, Science 220(1983)671. · Zbl 1225.90162
[10]	V. Cerny, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, J. Optim. Theory Appl. 45(1985)41. · Zbl 0534.90091
[11]	H. Muhlenbein, M. Georges-Schleuter and O. Kramer, Evolution algorithms in combinatorial optimization, Parallel Comp. 7(1988)65. · Zbl 0646.65054
[12]	J. Hopfield and D. Tank, Neural computation of decisions in optimization problems, Biol. Cybern. 52(1985)141. · Zbl 0572.68041
[13]	D.S. Johnson and L.A. McGeoch, The traveling salesman problem: A case study in local optimization, to appear inLocal Search in Combinatorial Optimization ed. E.H.L. Aarts and J.K. Lenstra (Wiley, New York, 1995).
[14]	F. Barahona and A. Casari, On the magnetisation of the ground states in two-dimenional Ising spin glasses, Comp. Phys. Commun. 49(1988)417. · Zbl 0814.90132
[15]	A. Pothen, H. Simon and K.P. Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Math. Anal. Appl. 11(1990)430–452. · Zbl 0711.65034
[16]	T. Bui, C. Heigham, C. Jones and T. Leighton, Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithms, in:26th ACMIEEE Design Automation Conf. (1989) p. 775.
[17]	D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: An experimental evaluation, part I (graph partitioning), Oper. Res. 37(1989)865–892. · Zbl 0698.90065
[18]	B. Kernighan and S. Lin, An effective heuristic procedure for partitioning graphs, Bell Syst. Tech. J. 49(1970)291. · Zbl 0333.05001
[19]	Z. Li and H.A. Scheraga, Monte Carlo–minimization approach to the multiple-minima problem in protein folding, Proc. Natl. Acad. Sci. 84(1987)6611–6615.
[20]	E.B. Baum, Towards practical ”neural” computation for combinatorial optimization problems, in:Neural Networks for Computing, ed. J. Denker, AIP Conference Proceedings 151 (1986).
[21]	H. Crowder and M.W. Padberg, Solving large-scale symmetric traveling salesman problems to optimality, Manag. Sci. 26(1984)495. · Zbl 0444.90068
[22]	M.W. Padberg and G. Rinaldi, Optimization of a 532-city symmetric traveling salesman problem by branch and cut, Oper. Res. Lett. 6(1987)1–7. · Zbl 0618.90082
[23]	W. Cook, V. Chvátal and D. Applegate, in:TSP 90, ed. R. Bixby, Workshop held at Rice University (1990).
[24]	A.L. Beguelin, J.J. Dongarra, A. Geist, R.J. Manchek and V.S. Sunderam, Heterogeneous network computing, in:SIAM Conf. on Parallel Processing (1993). · Zbl 0800.68178
[25]	J. Dongarra, A. Geist, R. Manchek and V. Sunderam, Integrated PVM framework supports heterogeneous network computing, Comp. Phys. (April 1993). · Zbl 0825.68199
[26]	D. S. Johnson, Local optimization and the traveling salesman problem, in:17th Colloguium on Automata, Language, and Programming (Springer, 1990). · Zbl 0766.90079
[27]	S. Kirkpatrick, Optimization by simulated annealing: Quantitative studies, J. Statist. Phys. 34(1984)975.
[28]	M. Hanan and J.M. Kertzberg, A review of the placement and quadratic assignment problems, SIAM Rev. 14(1972)324. · Zbl 0241.90048
[29]	B.W. Kernighan, Some graph partitioning problems related to program segmentation, Ph.D. Thesis (1969).
[30]	A.E. Dunlop and B.W. Kernighan, A procedure for placement of standard-cell VLSI circuits, IEEE Trans. Comp.-Aided Design CAD-4(1985)92. · Zbl 05447937
[31]	Y. Fu and P.W. Anderson, Application of statistical mechanics to NP-complete problems in combinatorial optimization, J. Phys. A: Math. Gen. 19(1986)1605. · Zbl 0606.05064
[32]	M.K. Goldberg and R. Gardner, On the minimal cut problem, in:Progress in Graph Theory, eds. J.A. Bondy and U.S.R. Murty (1984) p. 295. · Zbl 0559.05059
[33]	M. Berger and S. Bokhari, A partitioning strategy for non-uniform problems on multi-processors, IEEE Trans. Comp. C-36(1987)570.
[34]	C.M. Fiduccia and R.M. Mattheyses, A linear-time heuristic for improving network partitions, in:Proc. 19th Design Automation Workshop (1982) p. 175.