×

A new adaptive multi-start technique for combinatorial global optimizations. (English) Zbl 0812.90126

Summary: We analyze relationships among local minima for the traveling salesman and graph bisection problems under standard neighborhood structures. Our work reveals surprising correlations that suggest a globally convex, or “big valley” structure in these optimization cost surfaces. In conjunction with combinatorial results that sharpen previous analyses, our analysis directly motivates a new adaptive multi-start paradigm for heuristic global optimization, wherein starting points for greedy descent are adaptively derived from the best previously found local minima. We test a simple instance of this method for the traveling salesman problem and obtain very significant speedups over previous multi-start implementations.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ackley, D. H., A Connectionist Machine for Genetic Hillclimbing (1987), Kluwer: Kluwer Dordrecht
[2] Bacci, S.; Parga, N., Ultrametricity, frustration and the graph colouring problem, J. Phy. A: Math. General, 22, 3023-3032 (1989)
[3] Baum, E. B., Toward practical ‘neural’ computation for combinatorial optimization problems, (Denker, J., Neural Networks for Computing (1986), American Institute of Physics)
[4] Bentley, J. L., Fast algorithms for geometric traveling salesman problems, ORSA J. Comput., 4, 387-411 (1992) · Zbl 0758.90071
[5] Boese, K. D.; Kahng, A. B., Best-so-far vs. where-you-are: implications for optimal finite-time annealing, Systems Control Lett. (1994), to appear · Zbl 0791.90048
[6] Boese, K. D.; Kahng, A. B.; Muddu, S., On the big valley and adaptive multi-start for discrete global optimizations, (Technical Report TR-930015 (1993), UCLA CS Department)
[7] Bollobas, B., Random Graphs (1985), Academic Press: Academic Press New York · Zbl 0567.05042
[8] Bui, T. N.; Chaudhuri, S.; Leighton, F. T.; Sipser, T., Graph bisection algorithms with good average case behavior, Combinatorica, 2, 171-191 (1987)
[9] Hu, T. C.; Klee, V.; Larman, D., Optimization of globally convex functions, SIAM J. Control Optim., 27, 1026-1047 (1989) · Zbl 0686.52006
[10] Johnson, D. S., Local optimization and the traveling salesman problem, (Proc. 17th Internat. Coll. on Automata, Languages and Programming (1990)), 446-460 · Zbl 0766.90079
[11] Johnson, D. S.; Aragon, C. R.; McGeoch, L. A.; Schevon, C., Optimization by simulated annealing: an experimental evaluation, Part I, graph partitioning, Oper. Res., 37, 865-892 (1989) · Zbl 0698.90065
[12] D.S. Johnson and E.E. Rothberg, “Asymptotic experimental analysis of the Held-Karp lower bound for the traveling salesman problem”, (to appear).; D.S. Johnson and E.E. Rothberg, “Asymptotic experimental analysis of the Held-Karp lower bound for the traveling salesman problem”, (to appear). · Zbl 0845.90123
[13] Kauffman, S.; Levin, S., Toward a general theory of adaptive walks on rugged landscapes, J. Theoret. Biol., 128, 11-45 (1987)
[14] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[15] Kirkpatrick, S.; Toulouse, G., Configuration space analysis of traveling salesman problems, J. de Phys., 46, 1277-1292 (1985)
[16] Lawler, E. L.; Lenstra, J. K.; Rinnooy-Kan, A.; Shmoys, D., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985), Wiley: Wiley New York · Zbl 0562.00014
[17] Mezard, M.; Parisi, G., A replica analysis of the traveling salesman problem, J. Phys., 47, 1285-1296 (1986)
[18] Mühlenbein, H., Parallel genetic algorithms, population genetics and combinatorial optimization, (Proc. Internat. Conf. on Genetic Algorithms (1989)), 416-421 · Zbl 0722.92010
[19] Mühlenbein, H.; Georges-Scheuter, M.; Krämer, O., Evolution algorithms in combinatorial optimization, Parallel Comput., 7, 65-85 (1988) · Zbl 0646.65054
[20] Papadimitriou, C., The complexity of the Lin-Kernighan heuristic for the traveling salesman problem, SIAM J. Comput., 21, 450-465 (1992) · Zbl 0761.68048
[21] Solla, S. A.; Sorkin, G. B.; White, S. R., Configuration space analysis for optimization problems, (Bienenstock, E.; etal., Disordered Systems and Biological Organization (1986), Springer: Springer Berlin), 283-292 · Zbl 1356.90126
[22] Sorkin, G. B., Efficient simulated annealing on fractal energy landscapes, Algorithmica, 6, 367-418 (1991) · Zbl 0728.90073
[23] G.B. Sorkin (1993), personal communication.; G.B. Sorkin (1993), personal communication.
[24] Sourlas, N., Statistical mechanics and the traveling salesman problem, Europhys. Lett., 2, 919-923 (1986)
[25] Ulder, N. L.J.; Aarts, E. H.L.; Bandelt, H.-J.; van Laarhoven, P. J.M.; Pesch, E., Genetic local search algorithms for the traveling salesman problem, (Schwefel, H.-P.; Männer, R., Parallel Problem Solving from Nature (1990), Springer: Springer Berlin), 109-116
[26] Wei, Y. C.; Cheng, C. K., A two-level two-way-partitioning algorithm, (Proc. IEEE Internat. Conf. on Computer-Aided Design (1990)), 516-519
[27] Weinberger, E., Correlated and uncorrelated fitness landscapes and how to tell the difference, Biol. Cybernet., 63, 325-336 (1990) · Zbl 0703.92016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.