An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search. (English) Zbl 0775.90292

Moscato, Pablo

Ann. Oper. Res. 41, No. 1-4, 85-121 (1993).

MSC:

90C27	Combinatorial optimization
90-08	Computational methods for problems pertaining to operations research and mathematical programming

References:

[1]	N. Agmon, Biochemistry 27(1988)3507–3511.
[2]	E. Amaldi and S. Nicolis, Stability-capacity diagram of a neural network with Ising bonds, J. Physique 50(1989)2333–2345.
[3]	E. Amaldi, E. Mayoraz and D. de Werra, Discrete optimization problems in neural network design, DMA preprint, EPF-Lausanne, Switzerland (August 1990). · Zbl 0801.68148
[4]	R.H. Austin et al., Biochemistry 14(1975)5355–5373.
[5]	M. Ball and M. Magazine, The design and analysis of heuristics, Networks 11(1981)215–219.
[6]	E. Baum, Intractable computations without local minima (reply), Phys. Rev. Lett. 59(1987)374.
[7]	J. Beardwood, J.H. Halton and J.M. Hammersley, The shortest path through many points, Proc. Cambridge Philos. Soc. 55(1959)299–327. · Zbl 0118.35601
[8]	T.L. Blundell and L.N. Johnson,Protein Chrystallography (Academic Press, New York, 1976).
[9]	H. Bohr and S. Brunak, A traveling salesman approach to protein conformation, Complex Syst. 3(1989)9–28. · Zbl 0724.92008
[10]	E. Bonomi and J.L. Lutton, TheN-city traveling salesman problem and the Metropolis algorithm, SIAM Rev. 26(1984)551–568. · Zbl 0551.90095
[11]	E. Bonomi and J.L. Lutton, The asymptotic behavior of quadratic sum assignment problems: A statistical mechanics approach, Eur. J. Oper. Res. 26(1986)295–300. · Zbl 0598.90065
[12]	S.G. Boxer et al., Nonphotochemical holeburning in a protein matrix: Chlorophyllide in apomyoglobin, J. Chem Phys. 86(1987)2439–2441.
[13]	B. Braschi, Solving the traveling salesman problem with simulated annealing techniques on a concurrent supercomputer, Report RR 752-I, TIM3-INPG Grenoble, France (November, 1988).
[14]	B.F. Campbell, M.R. Chance and J.M. Friedman, Science 238(1987)373–376.
[15]	J.E. Cohen, Threshold phenomena in random structures, Discr. Appl. Math. 19(1988)113–128. · Zbl 0633.05065
[16]	J.P. Cohoon et al., Punctuated equilibria: A parallel genetic algorithm, in:Proc. 2nd Int. Conf. on Genetic Algorithms and their Applications, ed. J.J. Grefenstette (Lawrence Erlbaum Associates, Hillsdale, NJ, 1987) pp. 148–154.
[17]	W. Conover,Practical Nonparametric Statistics (Wiley, New York, 1980).
[18]	B. Derrida and H. Flyvbjerg, Multivalley structure in Kauffman’s model: Analogy with spin glasses, J. Phys. A Math. Gen. 19(1986)L1003.
[19]	B. Derrida, Valleys and overlaps in Kauffman’s model, Philos. Magazine B 56(1987)917.
[20]	B. Derrida and O. Golinelli, Barrier heights in the Kauffman model, J. Physique 50(1989)1587.
[21]	D. de Werra and A. Hertz, Tabu search techniques: A tutorial and an application to neural networks, OR Spektrum 11(1989)131–141. · Zbl 0672.90089
[22]	J. Edmonds, Paths, trees and flowers, Can. J. Math. 17(1965)449–467. · Zbl 0132.20903
[23]	R. Elber and M. Karplus, Multiple conformational states of proteins: A molecular dynamics analysis of myoglobin, Science 235(1987)318–321.
[24]	R. Elber and M. Karplus, A method for determining reaction paths in large molecules, Chem. Phys. Lett. 139(1987)375.
[25]	N. Eldredge and S.J. Gould, Punctuated equilibria: An alternative to phyletic gradualism, in:Models of Paleobiology, ed. T.J.M. Schopf (Freeman, Cooper and Co., 1972) pp. 82–115.
[26]	C.N. Fiechter, A parallel tabu search algorithm for large traveling salesman problems, preprint ORWP 90/1, EPF-Lausanne, Switzerland (February 1990).
[27]	W. Fontana, W. Schnabl and P. Schuster, Physical aspects of evolutionary optimization and adaptation, Phys. Rev. A40(1989)3301–3321.
[28]	J.F. Fontanari and R. Meir, Overlap distribution in the binary perceptron; A numerical study, Division of Chemistry preprint, CalTech, Pasadena, CA (1989).
[29]	J.F. Fontanari and R. Köberle, Landscape statistics of the binary perceptron, J. Physique 51(1990)1403–1413.
[30]	G.C. Fox and D. Walker, Concurrent computers in science, CalTech Concurrent Computation Program Report 646, CalTech, Pasadena, CA (1988).
[31]	G.C. Fox et al.,Solving Problems on Concurrent Processors, vol. 1 (Prentice Hall, Englewood Cliffs, NJ, 1988).
[32]	H. Frauenfelder, G.A. Petsko and D. Tsernoglou, Nature 280(1979)558–563.
[33]	H. Frauenfelder, in:Structure and Motion: Membranes, Nucleic Acids, and Proteins, ed. E. Clementi et al. (Adenine, Guilderland, NY, 1985) p. 205.
[34]	H. Frauenfelder, F. Parak and R.D. Young, Ann. Rev. Biophys. Biophys. Chem. 17(1988)451–479.
[35]	H. Frauenfelder et al., Glassy behavior of a protein, Phys. Rev. Lett. 62(1989)1916–1919.
[36]	H. Frauenfelder, P.J. Steinbach and R.D. Young, Conformational relaxation in proteins, Chem. Scripta 29A(1989)145–150.
[37]	H. Frauenfelder, Proteins – Paradigms of complex systems, in:Proc. 25th Anniversary Conf. on Frontiers in Physics, High Technology and Mathematics, ed. H.A. Cerdeira and S.O. Lundqvist, Miramare, Trieste, Italy (World Scientific, Singapore, 1990).
[38]	H. Frauenfelder et al., Proteins and pressure, J. Phys. Chem. 94(1990)1024–1037.
[39]	H. Frauenfelder, Function and dynamics of myoglobin, in:Perspectives in Biological Dynamics and Theoretical Medicine, reprinted from Annals of the New York Academy of Sciences, vol. 504(1990) pp. 151–167.
[40]	T.R. Gingeras and R.J. Roberts, Science 209(1980)1322.
[41]	F. Glover, Tabu search. Part I, ORSA J. Comput. 1(1989)190–206.
[42]	F. Glover, Candidate list strategies and tabu search, CAAI Research Report, University of Colorado, Boulder, CO, (July 1989).
[43]	F. Glover, Tabu search. Part II, ORSA J. Comput. 2(1990) 4–32.
[44]	F. Glover, Tabu search for nonlinear and parametric optimization, paper presented at the EPFL Seminar on OR and AI Search Methods for Optimization Problems (November 1990).
[45]	F. Glover, private communication (3 May, 1991).
[46]	V.I. Goldanskii, Dokl. Akad. Nauk. SSSR 272(1983)978–981.
[47]	D.E. Goldberg,Genetic Algorithms in Search, Optimization and Machine Learning (Addison Wesley, Reading, MA, 1989). · Zbl 0721.68056
[48]	G.S. Grest et al., Monte Carlo and mean field slow cooling simulations for spin glasses: Relation to NP-completeness, in:Heidelberg Colloquium in Glassy Dynamics, Lecture Notes in Physics, Vol. 275, ed. J.L. van Hemmen and I. Morgenstern (Springer, Berlin, 1987)307–324.
[49]	R. Hall and P.G. Wolynes, The aperiodic crystal picture and free energy barriers in glasses, J. Chem. Phys. 86(1987)2943.
[50]	A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 29(1987)345–351. · Zbl 0626.68051
[51]	T. Hirata, A correlation between theb value and the fractal dimension of earthquakes, J. Geophys. Res. 94(1989)7507–7514.
[52]	G.W. Hoffmann et al., TheN-dimensional network, in:Theoretical Immunology, Part 2, ed. A.S. Perelson (Addison-Wesley, Redwood City, CA, 1988).
[53]	T. Hogg, The dynamics of complex computational systems, in:Complexity, Entropy, and the Physics of Information, ed. W.H. Zurek (Addison-Wesley, Redwood City, CA, 1990).
[54]	J.H. Holland,Adaptation in Natural and Artificial Systems (University of Michigan Press, Ann Arbor, 1975). · Zbl 0317.68006
[55]	B.A. Huberman and M. Kerszberg, Ultradiffusion: the relaxation of hierarchical systems, J. Phys. A18(1985)L331-L336.
[56]	B.A. Huberman and T. Hogg, Complexity and adaptation, Physica 22D(1986)376–384.
[57]	B.A. Huberman and T. Hogg, Phase transitions in artificial intelligence systems, Art. Int. 33(1987)155–171.
[58]	B.A. Huberman (ed.),The Ecology of Computation (North-Holland, Amsterdam, 1988). · Zbl 0800.68012
[59]	B.A. Huberman, The performance of cooperative processes, Physica D42(1990)38–47.
[60]	J.S. Judd,Neural Network Design and the Complexity of Learning (MIT Press, Cambridge, MA, 1990).
[61]	J.O. Kephart, T. Hogg and B.A. Huberman, Dynamics of computational ecosystems, Phys. Rev. A40(1989)404–421.
[62]	R.M. Karp, Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane, Math. Oper. Res. 2(1977)209–224. · Zbl 0391.90091
[63]	R.M. Karp, A patching algorithm for the nonsymmetric traveling-salesman problem, SIAM J. Comput. 8(1979)561–573. · Zbl 0427.90064
[64]	S.A. Kauffman and S. Levin, Towards a general theory of adaptive walks on rugged landscapes, J. Theor. Biol. 128(1987)11–45.
[65]	S.A. Kauffman and E.D. Weinberger, The NK model of rugged fitness landscapes and its application to maturation of the immune response, J. Theor. Biol. 141(1989)211–245.
[66]	S.A. Kauffman, Adaptation on rugged fitness landscapes, in:Lectures in the Sciences of Complexity, ed. D. Stein (Addison-Wesley, Redwood City, CA, 1989) pp. 527–618.
[67]	V.I. Keilis-Borok, Introduction: Non-linear systems in the problem of earthquake prediction, Phys. Earth Planet. Interiors 61(1990)1–7.
[68]	H. Keller and P.G. Debrunner, Evidence for conformational and diffusion mean square displacements in frozen aqueous solution of oxymyoglobin, Phys. Rev. Lett. 45(1980)68–71.
[69]	M. Kimura,The Neutral Theory of Molecular Evolution (Cambridge University Press, New York, 1983).
[70]	S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing, Science 220(1983)671–680. · Zbl 1225.90162
[71]	S. Kirkpatrick and G. Toulouse, Configuration space analysis of traveling salesman problems, J. Physique 46(1985)1277–1292.
[72]	W. Koehler, J. Friedrich and H. Scheer, Conformational barriers in low-temperature proteins in glasses, Phys. Rev. A37(1988)660–662.
[73]	E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys,The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley-Interscience, Chichester, 1985). · Zbl 0562.00014
[74]	S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling salesman problem, Oper. Res. 21(1973)498–516. · Zbl 0256.90038
[75]	B. Manderick, M. de Weger and P. Spiessens, The genetic algorithm and the structure of the fitness landscape, in:Proc. 4th Int. Conf. on Genetic Algorithms, ed. R.K. Belew and L.B. Booker, San Diego, CA (Morgan Kaufmann, San Mateo CA, 1991) pp. 143–150.
[76]	E.N. Miranda and N. Parga, Ultrametricity in the Kauffman model: A numerical test, J. Phys. A: Math. Gen. 21(1988)357.
[77]	S.A. Molchanov, V.P. Pisarenko and A. Ya. Reznikova, Multiscale models of failure and percolation, Phys. Earth Planet. Interiors 61(1990)36–43.
[78]	P. Moscato, On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms, CalTech Concurrent Computation Program Report 826, CalTech, Pasadena, CA (1989).
[79]	P. Moscato and J.F. Fontanari, Stochastic versus deterministic update in simulated annealing, Phys. Lett. A 146(1990)204–208.
[80]	P. Moscato and M.G. Norman, A ”memetic” approach for the traveling salesman problem. Implementation of a computational ecology for combinatorial optimization on message-passing systems, in preparation.
[81]	F. Mosteller and R. Rourke,Sturdy Statistics (Addison-Wesley, Reading, MA, 1973).
[82]	G.S. Narkunskaya and M.G. Shnirman, Hierarchical model of defect development and seismicity, Phys. Earth Planet. Interiors 61(1990)29–35.
[83]	T. Noguti and N. Go, Proteins 5(1989)97.
[84]	M.G. Norman and P. Moscato, A competitive-cooperative approach to complex combinatorial search, CalTech Concurrent Computation Program, Report C3P-790, Pasadena, CA (1989); selected work for theProc. 20th Joint Conf. on Informatics and Operations Research (20th JAIIO), Buenos Aires, Argentina, (August 1991) pp. 3.15–3.29.
[85]	M. Padberg and G. Rinaldi, Optimization of 532-city symmetric TSP, Oper. Res. Lett. 6(1987)1–7. · Zbl 0618.90082
[86]	R.G. Palmer et al., Models of hierarchically constrained dynamics for glassy relaxation, Phys. Rev. Lett. 53(1984)958.
[87]	F. Parak et al., J. Mol. Biol. 145(1981)825–833.
[88]	N. Parga, Overlap distributions and taxonomy analysis of spin-glass states with equal weights, J. Physique 48(1987)449.
[89]	G.A. Petsko and D. Ringe, Ann. Rev. Biophys. Bioeng. 13(1984)331–371.
[90]	R. Pfaffenberger and J. Patterson,Statistical Methods (Irwin, Homewood, IL, 1981). · Zbl 0392.90001
[91]	K. Rose, E. Gurewitz and G.C. Fox, Statistical mechanics and phase transitions in clustering, Phys. Rev. Lett. 65(1990)945–948.
[92]	K. Rose, E. Gurewitz and G.C. Fox, A deterministic annealing approach to clustering, Pattern Recognition Lett. 11(1990)589–594. · Zbl 0800.68817
[93]	D. Sankoff and J.B. Kruskal (eds.),Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison (Addison-Wesley, Reading, MA, 1983). · Zbl 0512.68048
[94]	J. Skorin-Kapov, Tabu search applied to the quadratic assignment problem, ORSA J. Comput. 2(1990)33–45. · Zbl 0752.90054
[95]	R.F. Smalley, Jr. et al., A fractal approach to the clustering of earthquakes: Application to the seismicity of the New Hebrides, Bull. Seismol. Soc. America 77(1987)1368–1381.
[96]	S.A. Solla, G.B. Sorkin and S.R. White, Configuration space analysis for optimization problems, in:Disordered Systems and Biological Organization, ed. E. Bienenstock, NATO ASI Series Vol. F20 (1985).
[97]	G.B. Sorkin, Efficient simulated annealing on fractal energy landscapes, Algorithmica 6(1991)367–418. · Zbl 0728.90073
[98]	G.B. Sorkin, Theory and practice of simulated annealing in fractal landscapes, Ph.D. Thesis, University of California, Berkeley, CA (1991). · Zbl 0728.90073
[99]	C.M. Soukolis, K. Levin and G.S. Grest, Irreversibility and metastability in spin-glasses. I. Ising model, Phys. Rev. B28(1983)1495.
[100]	V. Srajer, K.T. Schomacker and P.M. Champion, Spectral broadening in biomolecules, Phys. Rev. Lett. 57(1986)1267–1270.
[101]	G.L. Stebbins and F.J. Ayala, Is a new evolutionary synthesis necessary?, Science 213(1981)967–971.
[102]	F.H. Stillinger and T.A. Weber, Packing structures and transitions in liquids and solids, Science 225(1984)983.
[103]	G. Toulouse, Theory of the frustration effect in spin glasses: I, Commun. Phys. 2(1977)115.
[104]	G. Toulouse, How ”frustration” set in, Physics Today 42(1989)97.
[105]	M.S. Waterman, Bull. Math. Biol. 46(1984)473–500.
[106]	D. Whitley, T. Starkweather and D’Ann Fuquay, Scheduling problems and traveling salesman: The genetic edge recombination operator, in:Proc. 3rd Int. Conf. on Genetic Algorithms, ed. J.D. Schaffer, Fairfax, VA (Morgan Kaufmann, San Mateo CA, 1989) pp. 133–140.
[107]	K. Wuthrich, Science 234(1989)45–50; Accounts Chem. Res. 22(1989)36–44.