Abstract
Based on the analogy between mathematical optimization and molecular evolution and on Eigen's quasi-species model of molecular evolution, an evolutionary algorithm for combinatorial optimization has been developed. This algorithm consists of a versatile variation scheme and an innovative decision rule, the essence of which lies in a radical revision of the conventional philosophy of optimization: A number of configurations of variables with better values, instead of only a single best configuration, are selected as starting points for the next iteration. As a result the search proceeds in parallel along a number of routes and is unlikely to get trapped in local optima. An important innovation of the algorithm is introduction of a constraint to let the starting points always keep a certain distance from each other so that the search is able to cover a larger region of space effectively. The main advantage of the algorithm is that it has more chances to find the global optimum and as many local optima as possible in a single run. This has been demonstrated in preliminary computational experiments.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Beenker GFM, Claasen TACM, Hermens PCW (1985) Binary sequences with maximally flat amplitude spectrum. Philips J Res 40:289–304
Bibricher CK, Eigen M, Luce R (1981a) Product analysis of RNA generated de novo by Q β replicase. J Mol Biol 148:369–390
Biebricher CK, Eigen M, Luce R (1981b) Kinetic analysis of template-instructed and de novo RNA synthesis by Q β replicase. J Mol Biol 148:391–410
Bremermann HJ (1962) Optimization through evolution and recombination. In: Yovits MC, Goldstein GD, Jacobi GT (eds) Self-organizing systems. Spartan, Washington, D.C., pp 93–106
Eigen M (1971) Self-organization of matter and the evolution of biological molecules. Naturwissenschaften 58:465–523
Eigen M (1985) Macromolecular evolution: Dynamical ordering in sequence space. Ber Bunsenges Phys Chem 89:658–667
Eigen M (1986) The physics of molecular evolution. Chem Scr 26B:13–26
Eigen M, Schuster P (1977) The hypercycle — a principle of natural self-organization. Part A: Emergence of the hypercycle. Naturwissenschaften 64:541–565
Eigen M, Schuster P (1978a) The hypercycle — a principle of natural self-organization. Part B: The abstract hypercycle. Naturwissenschaften 65:7–41
Eigen M, Schuster P (1978b) The hypercycle — a principle of natural self-organization. Part C: The realistic hypercycle. Naturwissenschaften 65:341–369
Golay MJE (1982) The merit factor of long low autocorrelation binary sequences. IEEE, Trans Inform Theory IT-28:543–549
Hamming RW (1980) Coding and information theory. Prentice Hall, Englewood Cliffs, NJ
Holland JH (1975) Adaption in natural and artificial systems. University of Michigan, Ann Arbor
Hopfield JJ (1982) Neural networks and physical systems with emergent collective computational abilities. Proc Natl Acad Sci USA 79:2554–2558
Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680
Kramer FR, Mills Dr, Cole PE, Nishihara T, Spiegelman S (1974) Evolution in vitro: sequence and phenotype of a mutant RNA resistant to ethidium bromide. J Mol Biol 89:719–736
Mills DR, Peterson RL, Spiegelman S (1967) An extracellular Darwinian experiment with a self-duplicating nucleic acid molecule. Proc Natl Acad Sci USA 58:217–224
Rechenberg I (1973) Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution, Frommann-Holzboog, Stuttgart
Schuster P (1986) The physical basis of molecular evolution. Chem Scr 26B:27–41
Schuster P, Sigmund K (1985) Dynamics of evolutionary optimization. Ber Bunsenges Phys Chem 89:668–682
Schwefel HP (1977) Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie, Birkhäuser, Basel
Sherrington D, Kirkpatrick S (1975) Solvable model of a spinglass. Phys Rev Lett 35:1792–1796
Spiegelman S (1970) The development and use of an extracellular RNA replicating system. In: The Harvey Lectures, Series 64, Academic Press, New York London, pp 1–67
Sumper M, Luce R (1975) Evidence for de novo production of self-replicating and environmentally adapted RNA structures by bacteriophage Q β replicase. Proc Natl Acad Sci USA 72:162–166
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wang, Q. Optimization by simulating molecular evolution. Biol. Cybern. 57, 95–101 (1987). https://doi.org/10.1007/BF00318719
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00318719