Finding all minimal elements of a finite partially ordered set bygenetic algorithm with a prescribed probability

Marcin Studniarski

doi:10.3934/naco.2011.1.389

Article Contents

2011, Volume 1, Issue 3: 389-398. Doi: 10.3934/naco.2011.1.389

This issue Previous Article Some results on $l^k$-eigenvalues of tensor and related spectral radius Next Article An improved targeted climbing algorithm for linear programs

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

Marcin Studniarski^1,

1.
Faculty of Mathematics and Computer Science, University of Łódź, ul. S. Banacha 22, 90-338 Łódź

Received: May 2011

Revised: August 2011

Published: September 2011

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 68T20, 90C29; Secondary: 60J20, 68W20, 92D25.

Citation:

Related Papers

Cited by

References

[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.