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


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


[1] N. Agmon, Biochemistry 27(1988)3507–3511. · doi:10.1021/bi00409a057
[2] E. Amaldi and S. Nicolis, Stability-capacity diagram of a neural network with Ising bonds, J. Physique 50(1989)2333–2345. · doi:10.1051/jphys:0198900500170233300
[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. · doi:10.1021/bi00695a021
[5] M. Ball and M. Magazine, The design and analysis of heuristics, Networks 11(1981)215–219. · doi:10.1002/net.3230110210
[6] E. Baum, Intractable computations without local minima (reply), Phys. Rev. Lett. 59(1987)374. · doi:10.1103/PhysRevLett.59.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 · doi:10.1017/S0305004100034095
[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 · doi:10.1137/1026105
[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 · doi:10.1016/0377-2217(86)90193-1
[12] S.G. Boxer et al., Nonphotochemical holeburning in a protein matrix: Chlorophyllide in apomyoglobin, J. Chem Phys. 86(1987)2439–2441. · doi:10.1063/1.452092
[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. · doi:10.1126/science.3659921
[15] J.E. Cohen, Threshold phenomena in random structures, Discr. Appl. Math. 19(1988)113–128. · Zbl 0633.05065 · doi:10.1016/0166-218X(88)90008-X
[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. · doi:10.1080/13642818708215326
[20] B. Derrida and O. Golinelli, Barrier heights in the Kauffman model, J. Physique 50(1989)1587. · doi:10.1051/jphys:0198900500130158700
[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 · doi:10.1007/BF01720782
[22] J. Edmonds, Paths, trees and flowers, Can. J. Math. 17(1965)449–467. · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4
[23] R. Elber and M. Karplus, Multiple conformational states of proteins: A molecular dynamics analysis of myoglobin, Science 235(1987)318–321. · doi:10.1126/science.3798113
[24] R. Elber and M. Karplus, A method for determining reaction paths in large molecules, Chem. Phys. Lett. 139(1987)375. · doi:10.1016/0009-2614(87)80576-6
[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. · doi:10.1051/jphys:0199000510130140300
[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. · doi:10.1038/280558a0
[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. · doi:10.1146/annurev.bb.17.060188.002315
[35] H. Frauenfelder et al., Glassy behavior of a protein, Phys. Rev. Lett. 62(1989)1916–1919. · doi:10.1103/PhysRevLett.62.1916
[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. · doi:10.1021/j100366a002
[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. · doi:10.1111/j.1749-6632.1987.tb48730.x
[40] T.R. Gingeras and R.J. Roberts, Science 209(1980)1322. · doi:10.1126/science.6251542
[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. · doi:10.1063/1.452045
[50] A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 29(1987)345–351. · Zbl 0626.68051 · doi:10.1007/BF02239976
[51] T. Hirata, A correlation between theb value and the fractal dimension of earthquakes, J. Geophys. Res. 94(1989)7507–7514. · doi:10.1029/JB094iB06p07507
[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. · doi:10.1016/0004-3702(87)90033-6
[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 · doi:10.1287/moor.2.3.209
[63] R.M. Karp, A patching algorithm for the nonsymmetric traveling-salesman problem, SIAM J. Comput. 8(1979)561–573. · Zbl 0427.90064 · doi:10.1137/0208045
[64] S.A. Kauffman and S. Levin, Towards a general theory of adaptive walks on rugged landscapes, J. Theor. Biol. 128(1987)11–45. · doi:10.1016/S0022-5193(87)80029-2
[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. · doi:10.1016/S0022-5193(89)80019-0
[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. · doi:10.1016/0031-9201(90)90089-G
[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. · doi:10.1103/PhysRevLett.45.68
[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 · doi:10.1126/science.220.4598.671
[71] S. Kirkpatrick and G. Toulouse, Configuration space analysis of traveling salesman problems, J. Physique 46(1985)1277–1292. · doi:10.1051/jphys:019850046080127700
[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 · doi:10.1287/opre.21.2.498
[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. · doi:10.1088/0305-4470/21/6/007
[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. · doi:10.1016/0031-9201(90)90093-D
[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. · doi:10.1016/0375-9601(90)90166-L
[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. · doi:10.1016/0031-9201(90)90092-C
[83] T. Noguti and N. Go, Proteins 5(1989)97. · doi:10.1002/prot.340050203
[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 · doi:10.1016/0167-6377(87)90002-2
[86] R.G. Palmer et al., Models of hierarchically constrained dynamics for glassy relaxation, Phys. Rev. Lett. 53(1984)958. · doi:10.1103/PhysRevLett.53.958
[87] F. Parak et al., J. Mol. Biol. 145(1981)825–833. · doi:10.1016/0022-2836(81)90317-X
[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. · doi:10.1146/annurev.bb.13.060184.001555
[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. · doi:10.1103/PhysRevLett.65.945
[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 · doi:10.1016/0167-8655(90)90010-Y
[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 · doi:10.1007/BF01759051
[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. · doi:10.1103/PhysRevLett.57.1267
[101] G.L. Stebbins and F.J. Ayala, Is a new evolutionary synthesis necessary?, Science 213(1981)967–971. · doi:10.1126/science.213.4511.967
[102] F.H. Stillinger and T.A. Weber, Packing structures and transitions in liquids and solids, Science 225(1984)983. · doi:10.1126/science.225.4666.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. · doi:10.1063/1.2811258
[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. · doi:10.1126/science.2911719
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.