Article Contents
Article Contents

# Finding all minimal elements of a finite partially ordered set by genetic algorithm with a prescribed probability

• For a general Markov chain model of genetic algorithm, we establish an upper bound for the number of iterations which must be executed in order to find, with a prescribed probability, an optimal solution in a finite multiobjective optimization problem.
Mathematics Subject Classification: Primary: 68T20, 90C29; Secondary: 60J20, 68W20, 92D25.

 Citation:

•  [1] D. Greenhalgh and S. Marshall, Convergence criteria for genetic algorithms, SIAM J. Comput., 30 (2000), 269-282.doi: 10.1137/S009753979732565X. [2] G. J. Koehler, S. Bhattacharya and M. D. Vose, General cardinality genetic algorithms, Evol. Comput., 5 (1998), 439-459.doi: 10.1162/evco.1997.5.4.439. [3] C. R. Reeves and J. E. Rowe, "Genetic Algorithms: Principles and Perspectives: A Guide to GA Theory," Kluwer, Boston, 2003. [4] G. Rudolph and A. Agapie, Convergence properties of some multi-objective evolutionary algorithms, in: "Proceedings of the 2000 Congress on Evolutionary Computation: CEC00" (eds. A. Zalzala et al.), Vol. 2, IEEE Press, Piscataway (NJ), (2000), 1010-1016.doi: 10.1109/CEC.2000.870756. [5] J. E. Rowe, M. D. Vose and A. H. Wright, Structural search spaces and genetic operators, Evol. Comput., 12 (2004), 461-493.doi: 10.1162/1063656043138941. [6] M. Studniarski, Stopping criteria for a general model of genetic algorithm, in: "Twelfth National Conference on Evolutionary Computation and Global Optimization" (ed. J. Arabas), Zawoja, Poland, (2009), 173-181. [7] M. Studniarski, Stopping criteria for genetic algorithms with application to multiobjective optimization, in "Parallel Problem Solving from Nature -- PPSN XI" (eds. R. Schaefer et al.), Part I, Lect. Notes Comput. Sc. 6238, (2010), 697-706.doi: 10.1007/978-3-642-15844-5_70. [8] M. D. Vose, "The Simple Genetic Algorithm: Foundations and Theory," MIT Press, Cambridge, Massachusetts, 1999.