×

Theory of genetic algorithms. (English) Zbl 0972.68133

Summary: (i) We investigate spectral and geometric properties of the mutation-crossover operator in a genetic algorithm with general-size alphabet. By computing spectral estimates, we show how the crossover operator enhances the averaging procedure of the mutation operator in the random generator phase of the genetic algorithm. By mapping our model to the multi-set model often investigated in the literature, we compute corresponding spectral estimates for mutation-crossover in the multi-set model.
(ii) Various types of unscaled or scaled fitness selection mechanisms are considered such as proportional fitness selection, rank selection, and tournament fitness selection. We allow fitness selection mechanisms where the fitness of an individual or creature depends upon the population it resides in. We investigate contracting properties of these fitness selection mechanisms and combine them with the crossover operator to obtain a model for genetic drift. This has applications to the study of genetic algorithms with zero or extremely low mutation rate.
(iii) We discuss a variety of convergent simulated-annealing-type algorithms with mutation-crossover as generator matrix.
(iv) The theory includes proof of strong ergodicity for various types of scaled genetic algorithms using common fitness selection methods. If the mutation rate converges to a positive value, and the other operators of the genetic algorithm converge, then the limit probability distribution over populations is fully positive at uniform populations whose members have not necessarily optimal fitness.
(v) In what follows, suppose the mutation rate converges to zero sufficiently slow to assure weak ergodicity of the inhomogeneous Markov chain describing the genetic algorithm, unbounded power-law scaling for the fitness selection is used, mutation and crossover commute, and the fitness function is injective which is a minor restriction in regard to function optimization.
\((\text{v}_{\text{a}})\) If a certain integrable convergence condition is satisfied such that the selection pressure increases fast, then there is essentially no other restriction on the crossover operation, and the algorithm asymptotically behaves as the following take-the-best search algorithm: \((1)\) mutate in every step with rate decreasing to zero, and \((2)\) map any population to the uniform population with the best creature. The take-the-best search algorithm is investigated, and its convergence is shown. Depending upon population-size, the take-the-best search algorithm does or does not necessarily converge to the optimal solution.
\((\text{v}_{\text{b}})\) If population size is larger than length of genome, and a certain logarithmic convergence condition is satisfied such that the selection pressure increases slowly but sufficiently fast, then the algorithm asymptotically converges to the optimal solution.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68W05 Nonnumerical algorithms

Software:

Genocop; Mathematica
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E. H.L.; van Laarhoven, P. J.M., Simulated annealing: an introduction, Statist. Neerlandica, 43, 31-52 (1989) · Zbl 0676.90058
[2] Anily, S.; Federgruen, A., Simulated annealing methods with general acceptance probabilities, J. Appl. Probab., 24, 657-667 (1987) · Zbl 0628.60046
[3] Antonisse, J., A new interpretation of Schema notation that overturns the binary encoding constraint, (Schaffer, J. D., Proceedings of the Third International Conference on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 86-97
[4] Axelrod, R.; Hamilton, W. D., The evolution of cooperation, Science, 211, 1390-1396 (1981) · Zbl 1225.92037
[5] Aytug, H.; Koehler, G. J., Stopping criteria for finite length genetic algorithms, Inform. J. Comput., 8, 183-191 (1996) · Zbl 0864.68091
[6] J.E. Baker, Reducing bias and inefficiency in the selection algorithm, in: J.J. Grefenstette (Eds.), Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlbaum, London, 1987.; J.E. Baker, Reducing bias and inefficiency in the selection algorithm, in: J.J. Grefenstette (Eds.), Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlbaum, London, 1987.
[7] Banzhaf, W.; Francone, F. D.; Nordin, P., The effect of extensive use of the mutation operator on generalization in genetic programming using sparse data sets, (Ebeling, W.; Rechenberg, I.; Schwefel, H. P.; Voigt, H. M., Proceedings of the Fourth International Conference on Parallel Problem Solving from Nature (PPSN96) (1996), Springer: Springer Berlin), 300-309
[8] A.D. Bethke, Genetic algorithms as function optimizers, Ph.D. Dissertation, University of Michigan, Dissertation Abstracts International, 41(9), 3503B, University Microfilms No. 8106101, 1981.; A.D. Bethke, Genetic algorithms as function optimizers, Ph.D. Dissertation, University of Michigan, Dissertation Abstracts International, 41(9), 3503B, University Microfilms No. 8106101, 1981.
[9] Bhattacharyya, S.; Koehler, G. J., An analysis of non-binary genetic algorithms with cardinality
((2^ν\), Complex Systems, 8, 227-256 (1994) · Zbl 0826.68059
[10] Binder, K., Monte Carlo Methods in Statistical Physics (1978), Springer: Springer Berlin
[11] Cerny, V., Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, J. Optim. Theory Appl., 45, 41-51 (1985) · Zbl 0534.90091
[12] Crow, J. F.; Kimura, M., An Introduction to Populations Genetics Theory (1970), Harper & Row: Harper & Row New York · Zbl 0246.92003
[13] Davis, L., Handbook of Genetic Algorithms (1991), Van Nostrand Reinhold: Van Nostrand Reinhold New York
[14] T.E. Davis, Toward an extrapolation of the simulated annealing convergence theory onto the simple genetic algorithm, Ph.D. Dissertation, University of Florida, 1991.; T.E. Davis, Toward an extrapolation of the simulated annealing convergence theory onto the simple genetic algorithm, Ph.D. Dissertation, University of Florida, 1991.
[15] Davis, T. E.; Principe, J. C., A simulated annealing-like convergence theory for the simple genetic algorithm, (Belew, R. K.; Booker, L. B., Proceedings of the Fourth International Conference on Genetic Algorithms ’91 (1991), Morgan Kaufmann: Morgan Kaufmann Los Atlas, CA), 174-181
[16] Davis, T. E.; Principe, J. C., A Markow chain framework for the simple genetic algorithm, Evol. Comput., 1, 3, 269-288 (1993)
[17] K. Deb, D.E. Goldberg, mGA in C: A messy genetic algorithm in C, Dept. of General Engineering, University of Illinois at Urbana-Champaign IlliGAL, Report No. 91008, 1991.; K. Deb, D.E. Goldberg, mGA in C: A messy genetic algorithm in C, Dept. of General Engineering, University of Illinois at Urbana-Champaign IlliGAL, Report No. 91008, 1991.
[18] D.B. Fogel, Evolving artificial intelligence, Ph.D. Dissertation, The University of California, San Diego, 1992.; D.B. Fogel, Evolving artificial intelligence, Ph.D. Dissertation, The University of California, San Diego, 1992.
[19] Fogel, D. B., Asymptotic convergence properties of genetic algorithms and evolutionary programminganalysis and experiments, Cybernet. Systems, 25, 3, 389-407 (1994) · Zbl 0811.68082
[20] Geiringer, H., On the probability theory of linkage in Mendelian heredity, Ann. Math. Statist., 15, 25-57 (1944) · Zbl 0063.01560
[21] Geman, S.; Geman, D., Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images, IEEE Proc. Pattern Anal. Mach. Intell., 6, 721-741 (1984) · Zbl 0573.62030
[22] Gidas, B., Nonstationary Markov chains and convergence of the annealing algorithm, J. Statist. Phys., 39, 73-131 (1985) · Zbl 0642.60049
[23] A.M. Gillies, Machine learning procedures for generating image domain feature detectors, Ph.D. Dissertation, University of Michigan, 1985.; A.M. Gillies, Machine learning procedures for generating image domain feature detectors, Ph.D. Dissertation, University of Michigan, 1985.
[24] Goldberg, D. E., A note on Boltzmann tournament selection for genetic algorithms and population oriented simulated annealing, Complex Systems, 4, 445-460 (1990) · Zbl 0717.68083
[25] Goldberg, D. E., Genetic Algorithms, in Search, Optimization & Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[26] D.E. Goldberg, Genetic Algorithms Tutorial, Genetic Programming Conference, Stanford University, July 13, 1997.; D.E. Goldberg, Genetic Algorithms Tutorial, Genetic Programming Conference, Stanford University, July 13, 1997.
[27] Goldberg, D. E.; Deb, K., A comparative analysis of selection schemes used in genetic algorithms, (Rawlins, G. J.E., Foundations of Genetic Algorithms (1991), Morgan Kaufmann: Morgan Kaufmann Los Altos), 69-93
[28] Goldberg, D. E.; Deb, K.; Korb, B., Messy genetic algorithms revisited: studies in mixed size and scale, Complex Systems, 4, 415-444 (1990) · Zbl 0721.68026
[29] Goldberg, D. E.; Segrest, P., Finite Markov chain analysis of genetic algorithms, (Grefenstette, J. J., Genetic Algorithms and their ApplicationsProceedings of the Second International Conference on Genetic Algorithms ’87 (1987), Lawrence Erlbaum: Lawrence Erlbaum London), 1-8
[30] Greub, W., Linear Algebra (1975), Springer: Springer Berlin · Zbl 0317.15002
[31] Hajec, B., Cooling schedules for optimal annealing, Math. Oper. Res., 13, 311-329 (1988) · Zbl 0652.65050
[32] Hardy, G. H., Mendelian proportions in a mixed population, Science, 28, 49-50 (1908)
[33] Holland, J. H., Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975; Extended new Edition (1992), MIT Press: MIT Press Cambridge
[34] J. Horn, Finite Markov chain analysis of genetic algorithms with niching, Illinois Genetic Algorithms Laboratory Report No. 93002, Dept. of General Engineering, University of Illinois, Urbana-Champaign, 1993.; J. Horn, Finite Markov chain analysis of genetic algorithms with niching, Illinois Genetic Algorithms Laboratory Report No. 93002, Dept. of General Engineering, University of Illinois, Urbana-Champaign, 1993.
[35] Isaacson, D. L.; Madsen, R. W., Markov Chains: Theory and Applications (1961), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[36] Koehler, G. J., A proof of the Vose-Liepins conjecture, Ann. Math. Artificial Intelligence, 10, 408-422 (1994) · Zbl 0857.68047
[37] Koehler, G. J.; Bhattacharyya, S.; Vose, M. D., General cardinality genetic algorithms, Evol. Comput., 5, 4, 439-459 (1998)
[38] Koza, J. R., Genetic Programming (1992), MIT Press: MIT Press Cambridge, MA · Zbl 0850.68161
[39] Koza, J. R., Genetic Programming II (1994), MIT Press: MIT Press Cambridge, MA · Zbl 0850.68160
[40] Lang, S., Linear Algebra (1970), Addison-Wesley: Addison-Wesley Reading, MA
[41] Lang, S., Complex Analysis (1977), Addison-Wesley: Addison-Wesley Reading, MA
[42] Y. Leung, Z.-P. Chen, Z.-B. Xu, K.-S. Leung, Convergence rate for non-binary genetic algorithms with different crossover operators, The Chinese University of Hong Kong, preprint, 1998.; Y. Leung, Z.-P. Chen, Z.-B. Xu, K.-S. Leung, Convergence rate for non-binary genetic algorithms with different crossover operators, The Chinese University of Hong Kong, preprint, 1998.
[43] Mahfoud, S. W., Finite Markov chain models of an alternative selection strategy for genetic algorithms, Complex Systems, 7, 155-170 (1993) · Zbl 0807.92016
[44] Mahfoud, S. W.; Goldberg, D. E., A genetic algorithm for parallel simulated annealing, (Männer, R.; Manderick, B., Parallel Problem Solving from Nature, vol. 2 (1992), Elsevier: Elsevier Amsterdam), 301-310
[45] Maynard Smith, J., Evolutionary Genetics (1989), Oxford University Press: Oxford University Press Oxford
[46] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H., Equations of state calculations by fast computing machines, J. Chem. Phys., 21, 1087-1091 (1953) · Zbl 1431.65006
[47] Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs (1994), Springer: Springer Berlin · Zbl 0818.68017
[48] Mitchell, M., An Introduction to Genetic Algorithms (1996), MIT Press: MIT Press Cambridge, MA
[49] Mitra, D.; Romeo, F.; Sangiovanni-Vincentelli, A., Convergence and finite time behavior of simulated annealing, Adv. Appl. Probab., 18, 747-771 (1986) · Zbl 0604.60067
[50] Nix, A. E.; Vose, M. D., Modeling genetic algorithms with Markov chains, Ann. Math. Artificial Intelligence, 5, 79-88 (1992) · Zbl 1034.68534
[51] C.L. Nehaniv (Ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution, An International Workshop, 21-25 October 1997, Aizu, Japan, Lectures on Mathematics in the Life Sciences Series, vol. 26, American Mathematical Society, Providence, RI, 1999.; C.L. Nehaniv (Ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution, An International Workshop, 21-25 October 1997, Aizu, Japan, Lectures on Mathematics in the Life Sciences Series, vol. 26, American Mathematical Society, Providence, RI, 1999.
[52] Pedersen, G. K.,
((C^*\)-Algebras and Their Automorphism Groups, London Mathematical Society Monographs No. 14 (1979), Academic Press: Academic Press New York · Zbl 0416.46043
[53] J.R. Peck, J.M. Yearsley, D. Waxman, Why do asexual and self-fertilizing populations tend to occur in marginal environments?, in: C.L. Nehaniv (Ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution, An International Workshop, 21-25 October 1997, Aizu, Japan, Lectures on Mathematics in the Life Sciences Series, vol. 26, American Mathematical Society, Providence, RI, 1999, pp. 121-132.; J.R. Peck, J.M. Yearsley, D. Waxman, Why do asexual and self-fertilizing populations tend to occur in marginal environments?, in: C.L. Nehaniv (Ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution, An International Workshop, 21-25 October 1997, Aizu, Japan, Lectures on Mathematics in the Life Sciences Series, vol. 26, American Mathematical Society, Providence, RI, 1999, pp. 121-132. · Zbl 0930.92032
[54] Poli, A.; Langdon, M., Schema theory for genetic programming with one-point crossover and point mutation, Evol. Comput., 6, 3, 231-252 (1998)
[55] J. Roughgarden, Theory of Population Genetics and Evolutionary Ecology, MacMillan, New York, 1976 (Reprinted by Prentice-Hall, Englewood Cliffs, NJ, 1996).; J. Roughgarden, Theory of Population Genetics and Evolutionary Ecology, MacMillan, New York, 1976 (Reprinted by Prentice-Hall, Englewood Cliffs, NJ, 1996).
[56] Rudin, W., Functional Analysis (1973), McGraw-Hill: McGraw-Hill New York · Zbl 0253.46001
[57] Rudolph, G., Convergence analysis of canonical genetic algorithms, IEEE Trans. Neural Networks, 5, 96-101 (1994)
[58] Rudolph, G., An evolutionary algorithm for integer programming, (Davidor, Y.; Schwefel, H.-P.; Männer, R., Proceedings of the Third International Conference on Parallel Problem Solving From Nature (PPSN III) (1994), Springer: Springer Berlin), 139-148
[59] Schaefer, H. H., Banach Lattices and Positive Operators, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen Band 215 (1974), Springer: Springer Berlin
[60] L.M. Schmitt, Mathematica Computation,; L.M. Schmitt, Mathematica Computation,
[61] L.M. Schmitt, C.L. Nehaniv, The linear geometry of genetic operators with applications to the analysis of genetic drift and genetic algorithms using tournament selection, in: C.L. Nehaniv (Ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution, An International Workshop, 21-25 October 1997, Aizu, Japan, Lectures on Mathematics in the Life Sciences Series, vol. 26, American Mathematical Society, Providence, RI, 1999, pp. 147-166.; L.M. Schmitt, C.L. Nehaniv, The linear geometry of genetic operators with applications to the analysis of genetic drift and genetic algorithms using tournament selection, in: C.L. Nehaniv (Ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution, An International Workshop, 21-25 October 1997, Aizu, Japan, Lectures on Mathematics in the Life Sciences Series, vol. 26, American Mathematical Society, Providence, RI, 1999, pp. 147-166. · Zbl 0996.92027
[62] Schmitt, L. M.; Nehaniv, C. L.; Fujii, R. H., Linear analysis of genetic algorithms, Theoret. Comput. Sci., 200, 101-134 (1998) · Zbl 0917.68190
[63] Seneta, E., Non-negative Matrices and Markov Chains. Non-negative Matrices and Markov Chains, Springer Series in Statistics (1981), Springer: Springer Berlin · Zbl 0471.60001
[64] K. Sigmund, The social life of automata, in: C.L. Nehaniv (Ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution, An International Workshop, 21-25 October 1997, Aizu, Japan, Lectures on Mathematics in the Life Sciences Series, vol. 26, American Mathematical Society, Providence, RI, 1999, pp. 133-146.; K. Sigmund, The social life of automata, in: C.L. Nehaniv (Ed.), Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution, An International Workshop, 21-25 October 1997, Aizu, Japan, Lectures on Mathematics in the Life Sciences Series, vol. 26, American Mathematical Society, Providence, RI, 1999, pp. 133-146.
[65] Suzuki, J., A further result on the Markov chain model of genetic algorithms and its application to a simulated annealing-like strategy, (Belew, R. K.; Vose, M. D., Foundations of Genetic Algorithms, vol. 4 (1997), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 53-72
[66] Suzuki, J., A further result on the Markov chain model of genetic algorithms and its application to a simulated annealing-like strategy, IEEE Trans. Systems Man, Cybernet. - Part B, 28, 95-102 (1998)
[67] van der Warden, B. L., Algebra I (Achte Auflage der Modernen Algebra), Heidelberger Taschenbücher Band 12 (1971), Springer: Springer Berlin
[68] M.D. Vose, Formalizing genetic algorithms, in: Proceedings of the IEEE Workshop on Genetic Algorithms, Neural Networks and Simulated Annealing Applied to Problems in Signal and Image Processing, May 1990, Glasgow, UK, 1990.; M.D. Vose, Formalizing genetic algorithms, in: Proceedings of the IEEE Workshop on Genetic Algorithms, Neural Networks and Simulated Annealing Applied to Problems in Signal and Image Processing, May 1990, Glasgow, UK, 1990.
[69] Vose, M. D., Modeling simple genetic algorithms, (Rawlins, G., Foundations of Genetic Algorithms (1991), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 94-101
[70] Vose, M. D.; Liepins, G. E., Punctuated equilibria in genetic search, Complex Systems, 5, 31-44 (1991) · Zbl 0764.68149
[71] Vose, M. D.; Wright, A. H., The simple genetic algorithm and the Walsh transformPart I, theory, Evol. Comput., 6, 3, 253-273 (1998)
[72] Vose, M. D.; Wright, A. H., The simple genetic algorithm and the Walsh transformPart II, the inverse, Evol. Comput., 6, 3, 275-289 (1998)
[73] Weinberg, W., Über Vererbungsgesetze beim Menschen, Zeitschrift für induktive Abstammungs- und Vererbungslehre, 1, 277-330 (1909)
[74] Wolfram, S., Mathematica - A System for Doing Mathematics by Computer (1991), Addison Wesley: Addison Wesley Reading, MA
[75] Wright, S., Statistical genetics and evolution, Bull. Amer. Math. Soc., 48, 223-246 (1942) · Zbl 0063.08326
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.