American Institute of Mathematical Sciences

Advanced
2011, 1(3): 389-398. doi: 10.3934/naco.2011.1.389

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ź, Poland

Received  May 2011 Revised  August 2011 Published  September 2011

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: stopping criteria., vector optimization, Genetic algorithm, Markov chain.
Mathematics Subject Classification: Primary: 68T20, 90C29; Secondary: 60J20, 68W20, 92D2.
Citation: Marcin Studniarski. Finding all minimal elements of a finite partially ordered set by genetic algorithm with a prescribed probability. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 389-398. doi: 10.3934/naco.2011.1.389
References:
[1]

D. Greenhalgh and S. Marshall, Convergence criteria for genetic algorithms, SIAM J. Comput., 30 (2000), 269-282. doi: 10.1137/S009753979732565X.  Google Scholar

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

[3]

C. R. Reeves and J. E. Rowe, "Genetic Algorithms: Principles and Perspectives: A Guide to GA Theory," Kluwer, Boston, 2003.  Google Scholar

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

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

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

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

[8]

M. D. Vose, "The Simple Genetic Algorithm: Foundations and Theory," MIT Press, Cambridge, Massachusetts, 1999.  Google Scholar

show all references

References:
[1]

D. Greenhalgh and S. Marshall, Convergence criteria for genetic algorithms, SIAM J. Comput., 30 (2000), 269-282. doi: 10.1137/S009753979732565X.  Google Scholar

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

[3]

C. R. Reeves and J. E. Rowe, "Genetic Algorithms: Principles and Perspectives: A Guide to GA Theory," Kluwer, Boston, 2003.  Google Scholar

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

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

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

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

[8]

M. D. Vose, "The Simple Genetic Algorithm: Foundations and Theory," MIT Press, Cambridge, Massachusetts, 1999.  Google Scholar

[1]

Ping-Chen Lin. Portfolio optimization and risk measurement based on non-dominated sorting genetic algorithm. Journal of Industrial & Management Optimization, 2012, 8 (3) : 549-564. doi: 10.3934/jimo.2012.8.549
[2]

Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279
[3]

Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200
[4]

Xian Chen, Zhi-Ming Ma. A transformation of Markov jump processes and applications in genetic study. Discrete & Continuous Dynamical Systems, 2014, 34 (12) : 5061-5084. doi: 10.3934/dcds.2014.34.5061
[5]

Samuel N. Cohen, Lukasz Szpruch. On Markovian solutions to Markov Chain BSDEs. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 257-269. doi: 10.3934/naco.2012.2.257
[6]

Ajay Jasra, Kody J. H. Law, Yaxian Xu. Markov chain simulation for multilevel Monte Carlo. Foundations of Data Science, 2021, 3 (1) : 27-47. doi: 10.3934/fods.2021004
[7]

Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240
[8]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[9]

Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99
[10]

Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[11]

Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial & Management Optimization, 2022, 18 (1) : 1-24. doi: 10.3934/jimo.2020140
[12]

Michael Herty, S. Moutari, M. Rascle. Optimization criteria for modelling intersections of vehicular traffic flow. Networks & Heterogeneous Media, 2006, 1 (2) : 275-294. doi: 10.3934/nhm.2006.1.275
[13]

Jingzhi Tie, Qing Zhang. An optimal mean-reversion trading rule under a Markov chain model. Mathematical Control & Related Fields, 2016, 6 (3) : 467-488. doi: 10.3934/mcrf.2016012
[14]

Ralf Banisch, Carsten Hartmann. A sparse Markov chain approximation of LQ-type stochastic control problems. Mathematical Control & Related Fields, 2016, 6 (3) : 363-389. doi: 10.3934/mcrf.2016007
[15]

Kun Fan, Yang Shen, Tak Kuen Siu, Rongming Wang. On a Markov chain approximation method for option pricing with regime switching. Journal of Industrial & Management Optimization, 2016, 12 (2) : 529-541. doi: 10.3934/jimo.2016.12.529
[16]

Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191
[17]

Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088
[18]

Joseph Geunes, Panos M. Pardalos. Introduction to the Special Issue on Supply Chain Optimization. Journal of Industrial & Management Optimization, 2007, 3 (1) : i-ii. doi: 10.3934/jimo.2007.3.1i
[19]

Pooja Louhan, S. K. Suneja. On fractional vector optimization over cones with support functions. Journal of Industrial & Management Optimization, 2017, 13 (2) : 549-572. doi: 10.3934/jimo.2016031
[20]

Ying Gao, Xinmin Yang, Kok Lay Teo. Optimality conditions for approximate solutions of vector optimization problems. Journal of Industrial & Management Optimization, 2011, 7 (2) : 483-496. doi: 10.3934/jimo.2011.7.483

 Impact Factor: 

Tools

Metrics

  • PDF downloads (57)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy