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

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.
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. doi: 10.1137/S009753979732565X.

[2]

G. J. Koehler, S. Bhattacharya and M. D. Vose, General cardinality genetic algorithms,, Evol. Comput., 5 (1998), 439. 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, (2003).

[4]

G. Rudolph and A. Agapie, Convergence properties of some multi-objective evolutionary algorithms,, in:, (2000), 1010. 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. doi: 10.1162/1063656043138941.

[6]

M. Studniarski, Stopping criteria for a general model of genetic algorithm,, in:, (2009), 173.

[7]

M. Studniarski, Stopping criteria for genetic algorithms with application to multiobjective optimization,, in, (2010), 697. doi: 10.1007/978-3-642-15844-5_70.

[8]

M. D. Vose, "The Simple Genetic Algorithm: Foundations and Theory,", MIT Press, (1999).

show all references

References:
[1]

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

[2]

G. J. Koehler, S. Bhattacharya and M. D. Vose, General cardinality genetic algorithms,, Evol. Comput., 5 (1998), 439. 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, (2003).

[4]

G. Rudolph and A. Agapie, Convergence properties of some multi-objective evolutionary algorithms,, in:, (2000), 1010. 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. doi: 10.1162/1063656043138941.

[6]

M. Studniarski, Stopping criteria for a general model of genetic algorithm,, in:, (2009), 173.

[7]

M. Studniarski, Stopping criteria for genetic algorithms with application to multiobjective optimization,, in, (2010), 697. doi: 10.1007/978-3-642-15844-5_70.

[8]

M. D. Vose, "The Simple Genetic Algorithm: Foundations and Theory,", MIT Press, (1999).

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

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

[4]

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

[5]

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

[6]

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

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

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Caiping Liu, Heungwing Lee. Lagrange multiplier rules for approximate solutions in vector optimization. Journal of Industrial & Management Optimization, 2012, 8 (3) : 749-764. doi: 10.3934/jimo.2012.8.749

[16]

Xinmin Yang. On symmetric and self duality in vector optimization problem. Journal of Industrial & Management Optimization, 2011, 7 (3) : 523-529. doi: 10.3934/jimo.2011.7.523

[17]

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

[18]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457

[19]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-24. doi: 10.3934/jimo.2018077

[20]

Lin Xu, Rongming Wang. Upper bounds for ruin probabilities in an autoregressive risk model with a Markov chain interest rate. Journal of Industrial & Management Optimization, 2006, 2 (2) : 165-175. doi: 10.3934/jimo.2006.2.165

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]