Constraint handling techniques used with evolutionary algorithms. analysis and applica-tion

Authors

  • Ольга В’ячеславівна Єгорова Cherkasy state technological university Shevchenko str., 460 Cherkasy, Ukraine, 18006, Ukraine

DOI:

https://doi.org/10.15587/1729-4061.2012.4009

Keywords:

Constraint satisfaction problems, optimization, constrained optimization methods

Abstract

The analysis of evolutionary techniques for constraint satisfaction problem solving is executed.Their advantages and disadvantages have been defined

Author Biography

Ольга В’ячеславівна Єгорова, Cherkasy state technological university Shevchenko str., 460 Cherkasy, Ukraine, 18006

Postgraduate student

Department of information technologies design

References

  1. Coello Coello, C. A. Theoretical and numerical constraint-handling tech-niques used with evolutionary algorithms: А survey of the state of the art [Теxt] / C. A. Coello Coello // Computer Methods in Applied Mechanics and Engineer-ing. – Vol. 191, № 11-12. – 2002. – Р. 1245-1287.
  2. Субботін, С. О. Подання й обробка знань у системах штучного інте-лекту та підтримки прийняття рішень [Текст] : навчальний посібник / С. О. Субботін. – Запоріжжя : ЗНТУ, 2008. – 341 с.
  3. Weise, T. Global optimization algorithms – Theory and application [Elec-tronic resource] / T. Weise. – Available at : www/ URL: http://it-weise.de/projects/book.pdf/ – 26.06.2009 p. – Title on a display.
  4. Brownlee, J. Clever algorithms: Nature-inspired programming recipes [Теxt] / J. Brownlee. – Melbourne : LuLu, 2011. – 436 p.
  5. Kramer, O. A review of constraint-handling techniques for evolution strategies [Теxt] / O. Kramer // Applied computational Intelligence and Soft Computing. – Vol. 2010. – 2010. – 11 p.
  6. Homaifar, S. Constrained optimization via genetic algorithms [Text] / H. Y. Lai, X. Qi // Simulation. –1994. – Vol. 62, № 4. – Р. 242-254.
  7. Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Pro-grams. – New York : Springer-Verlag Berlin Heidelberg, 1996. – 391 p.
  8. Morales, A. K. A universal eclectic genetic algorithm for constrained optimization [Text] / A. K. Morales, C. V. Quezada // Proceedings 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT’98), September 1998 Aachen. – Aachen : Verlag Mainz, 1998. – P. 518-522.
  9. Hofrmeister, F. Problem-independent handling of constraints by use of metric penalty functions [Text] / F. Hofrmeister, J. Sprave // Proceedings of the Fifth Annual Conference on Evolutionary Programming (EP’96), February 1996 San Diego, California / editors: L. J. Fogel, P. J. Angeline, T. Bäck. – San Diego, California : The MIT Press, 1996. – P. 289-294.
  10. Schütz, M. Application of partially mixed-integer evolution strategies with mutation rate pooling [Text] / M. Schütz, J. Sprave // Proceedings of the Fifth Annual Conference on Evolutionary Programming (EP’96), February 1996 San Diego, California / editors : L. J. Fogel, P. J. Angeline T. Bäck. – San Diego : The MIT Press, 1996. – P. 345-354.
  11. Joines, J. On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GAs [Text] / J. Joines, C. Houck // Proceedings of the first IEEE Conference on Evolutionary Computation, 27-29 June 1994 Orlando, Florida / editor D. Fogel. – Orlando: IEEE Press, 1994. – Р. 579-584.
  12. Kazarlis, S. Varying fitness functions in genetic algorithms: studying the rate of increase of the dynamic penalty terms [Text] / S. Kazarlis, V. Petridis // Parallel problem solving from nature V–PPSN V, 1998 Amsterdam / editors: A. E. Eiben, T. Bäck, M. Schoenauer, H.-P. Schwefel. – Amsterdam : Springer-Verlag, 1998. – Р. 211-220.
  13. Michalewicz, Z. Evolutionary optimization of constrained problems [Text] / Z. Michalewicz, N. F. Attia // Pro¬ceedings of the 3rd Annual Conference on Evolutionary Programming, 1994 / editor : A. V. Sebald, L. J. Fogel. – World Scientific Publishing, River Edge, NJ, 1994. – P. 98-108.
  14. Skalak, S. C. Annealing a genetic algorithm over con¬straints [Electronic resource] / S. C. Skalak, R. Shonkwiler, S. Babar, M. Aral. – Available at : www/ URL: http://vlead.mech.virginia.edu/publications/shenkpaper
  15. /shenkpaper.htinl/ – 24.04.2012 p. – Title on a display.
  16. Bean, J. C. A dual genetic algorithm for bounded integer programs [Electronic resource] / J. C. Bean, A. B. Hadj-Alouane. – Available at : www/ URL: http://ioe.engin.umich.edu/techrprt/pdf/TR92-53.pdf/ – 24.04.2012 p. – Title on a display.
  17. Hadj-Alouane, A. B. A genetic algorithm for the multiple-choice integer program [Text] / A. B. Hadj-Alouane, J. C. Bean // Operations research. – 1997. – № 45. – Р. 92-101.
  18. Smith, A. E. Genetic optimization using a penalty function [Text] / A. E. Smith, D. M. Tate // Proceedings of the Fifth International Conference on Genetic Algorithms, July 1993 San Mateo, California / editor : S. Forrest. – San Mateo : Morgan Kaufmann Publishers, 1993. – Р. 499-503.
  19. Coit, D. W. Penalty guided genetic search for reliability design optimization [Text] / D.W. Coit, A. E. Smith // Com¬puters and Industrial Engi-neering. – 1996. – Vol. 30, № 4. – Р. 895-904.
  20. Coit, D. W. Adaptive penalty methods for genetic optimization of constrained combinatorial problems [Text] / D. W. Coit, A. E. Smith, D. M. Tate // INFORMS Journal on Computing. – 1996. – Vol. 8, № 2. – P.173-182.
  21. Yokota, T. Optimal design of system reliability by an improved genetic algorithm [Text] / T. Yokota, M. Gen, K. Ida, T. Taguchi // Transactions of Institute оf Electronics, Information and Computer Engineering. – 1995. – J78-A(6). – Р. 702-709.
  22. Gen, M. A Survey of penalty techniques in genetic algorithms [Text] / M. Gen, R. Cheng // Proceedings of 1996 the International Conference on Evolutionary Computation, 20-22 May 1996 Nagoya / editors : T. Fukuda, T, Furuhashi. – Nagoya : IEEE, 1996. – P. 804-809.
  23. Gen, M. Optimal design of system reliability using interval pro-gramming and genetic algorithms [Text] / M. Gen, R. Cheng // Computers and Industrial Engineering. – 1996. – Vol. 31, № 1. – Р. 237-240.
  24. Rasheed, K. An adaptive penalty approach for constrained genetic-algorithm optimization [Text] / K. Rasheed // Proceedings of the Third Annual Genetic Programming Conference, 1998 San Francisco, California / editors : J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, R. L. Riolo. – San Francisco : Morgan Kauf-mann Publishers, 1998. – P. 584-590.
  25. Coello Coello, C. A. Use of a self-adaptive penalty approach for engineering optimization problems [Text] / C. A. Coello Coello //Computers in Industry. – 2000. – Vol. 41, № 2. – Р. 113-127.
  26. Wu, B. Fuzzy penalty approach for constrained function optimization with evolutionary algorithms [Electronic resource] / B. Wu, X. Yu. – Available at : www/ URL: http://cs.cinvestav.mx/~constraint/papers/wu-b01.pdf/ – 24.04.2012 p. – Title on a display.
  27. Le Riche, R. G. A segregated genetic algorithm for constrained structural optimization [Text] / R. G. Le Riche, C. Knopf-Lenoir, R. T. Haftka // Proceedings of the Sixth International Conference on Genetic Algorithms, July 1995 San Mateo, California / editor : L. J. Eshelman. – San Mateo : Morgan Kaufmann Publishers, 1995. – Р. 558-565.
  28. Davis, L. Handbook of genetic algorithms [Теxt] / L. Davis. – New York : Van Nostrand Reinhold, 1991. – 385 р.
  29. Bean, J. C. Genetics and random keys for sequencing and optimization [Electronic resource] / J. C. Bean. – Available at : www/ URL: http://deepblue.lib.umich.edu/bitstream/2027.42/3481/5/ban1152.0001.001.pdf/ – 24.04.2012 p. – Title on a display.
  30. Bean, J. C. Genetics and random keys for sequencing and optimization [Теxt] / J. C. Bean // ORSA Journal on Computing. – 1994. – Vol. 6, № 2. – Р. 154-160.
  31. Kowalczyk, R. Constraint consistent genetic algorithms [Теxt] / R. Kowalczyk // Proceedings of the 1997 IEEE Conference on Evolutionary Computation, April 1997 Indianapolis. – Indianapolis : IEEE, 1997. – P. 343-348.
  32. Schoenauer, M. Evolutionary computation at the edge of feasibility [Теxt] / M. Schoenauer, Z. Michalewicz // Proceedings of the Fourth Conference on Parallel Problem Solving from Nature, September 1996 Berlin / editors : H.-M. Voigt, W. Ebeling, I. Rechenberg, H.-P. Schwefel. – Berlin : Springer-Verlag, 1996. – P. 245-254.
  33. Palmer, C. C. Representing trees in genetic algorithms [Теxt] / C. C. Palmer, A. Kershenbaum // Proceedings of the First IEEE Conference on Evolutionary Computation, 27-29 June 1994 Orlando. – Piscataway : IEEE Press, 1994. – P. 379-384.
  34. Koziel, S. Evolution algorithms, homomorphous mapping, and con-strained parameter optimization [Теxt] / S. Koziel, Z. Michalewicz // Evolution Computation. – 1999. – Vol. 7, № 1. – Р. 19-44.
  35. Michalewicz, Z. How to solve it: Modern Heuristics [Теxt] / Z. Micha-lewicz, D. B. Fogel. – Berlin : Springer, 2000. – 467 p.
  36. Michalewicz, Z. Genocop III: A co-evolutionary algorithm for numerical optimiza¬tion with nonlinear constraints [Text] / Z. Michalewicz, G. Nazhiyath // Proceedings of the Second IEEE International Conference on Evo-lutionary Computation, 29 November – 01 Decenber 1995 Perth / editor : D. B. Fogel. – Piscataway : IEEE Press, 1995. – Р. 647-651.
  37. Michalewicz, Z. Evaluation of paths in evolutionary planner/navigator [Text] / Z. Michalewicz, J. Xiao // Proceedings of the 1995 International Workshop on Biologically Inspired Evolutionary Systems, May 1995 Tokyo. – Tokyo, 1995. – Р.45-52.
  38. Orvosh, D. Using a genetic algorithm to optimize problems with feasibility contraints [Text] / D. Orvosh, L. Davis // Proceedings of the First IEEE Conference on Evolutionary Computation, June 1994 Orlando. – Orlando : IEEE Press, 1994. – Р. 548-553.
  39. Mühlenbein, H. Parallel genetic algorithms in combinatorial optimiza-tion [Text] / H. Mühlenbein // Computer Science and Operations Research / edi-tors : O. Balci, R. Sharda, S. Zenios. – New York : Pergamon Press, 1992. – Р. 441-456.
  40. Paredis, J. Co-evolutionary constraint satisfaction [Теxt] / J. Paredis // Proceedings of the 3rd Conference on Parallel Problem Solving from Nature. – London : Springer Verlag, 1994. – Vol. 866, № 2. – Р. 46-55.
  41. Powell, D. Using genetic algorithms in engineering design optimi-zation with non¬linear constraints [Теxt] / D. Powell, M. M. Skolnick // Pro-ceedings of the Fifth International Conference on Genetic Algorithms, July 1993 San Mateo, California / editor : S. Forrest. – San Mateo : University of Illinois at Urbana-Champaign, Morgan Kaufmann Publishers. – P. 424-431.
  42. Deb, K. An efficient constraint handling method for genetic algorithms [Теxt] / K. Deb // Computer Methods in Applied Mechanics and Engineering. – 2000. – Vol. 186, № 2-4. – Р. 311-338.
  43. Parmee, I. C. The development of a directed genetic search technique for heavily constrained design spaces [Теxt] / I. C. Parmee, G. Purchase // Adaptive Computing in Engineering Design and Control-’94, 21-22 September 1994 Plymouth / editor : C. Parme. – Plymouth : University of Plymouth, 1994. – Р. 97-102.
  44. Surry, P. D. The COMOGA method: constrained optimisation by multi-objective genetic algorithms [Теxt] / P. D. Surry, N. J. Radcliffe // Control and Cybernetics. – 1997. – Vol. 26, № 3. – Р. 391-412.
  45. Coello Coello, C. A. Treating constraints as objectives for single-objective evolutionary optimization [Теxt] / Carlos A. Coello Coello // Engineering Optimization. – 2000. – Vol. 32, № 3. – Р. 275-308.
  46. Camponogara, E. A genetic algorithm for constrained and mul-tiobjective optimization [Теxt] / E. Camponogara, S. N. Talukdar // 3rd Nordic Workshop on Genetic Algorithms and Their Applications (3NWGA), August 1997 Vaasa / editor : J. T. Alander. – Vaasa : University of Vaasa, 1997. – P. 49-62.
  47. Schoenauer, M. Constrained GA optimization [Теxt] / M. Schoe-nauer, S. Xanthakis // Pro¬ceedings of the Fifth International Conference on Genetic Algorithms, July 1993 San Mateo, California / editor : S. Forrest. – San Mateo : Morgan Kauffman Publishers, 1993. – P. 573-580.
  48. Adeli, H. Augmented Lagrangian genetic algorithm for structural optimization [Text] / H. Adeli, N.-T. Cheng // Journal of Aerospace Engineering.–1994. – Vol. 7, № 1. – Р. 104-118.
  49. Powell, M. J. D. A method for nonlinear constraints in minimization problems [Text] / M. J. D. Powell // Optimization / editor : R. Fletcher. – New York : Academic Press, 1969. – P. 283-298.
  50. Kim, J.-H. Evolutionary programming techniques for constrained optimization problems [Text] / J.-H. Kim, H. Myung // IEEE Transactions on Evolutionary Computation. – 1997. – № 1. – Р.129-140.
  51. Myung, H. Hybrid interior-lagrangian penalty based evolutionary optimization [Text] / H. Myung, J.-H. Kim // Proceedings of the Seventh Anual Conference on Evolutionary Programming, 25-27 March 1998 San Diego / edi-tors : V. W. Porto, N. Saravanan, D. Waagen, A.E. Eiben. – San Diego : Springer, 1998. – Р. 85-94.
  52. Maa, C. A two-phase optimization neural network / C. Maa, M. Shanblatt // IEEE Transactions on Neural Networks. – 1992. – Vol. 3, № 6. – Р.1003-1009.
  53. Belur,S. V. CORE: Constrained optimization by random evolution [Text] / S. V. Belur// Late Breaking Papers at the Genetic Programming Conference, July 1997 Stanford University, California / editor : J. R. Koza. – Stanford University: Stanford Bookstore, 1997. – Р. 280-286.
  54. Le, T. V. A Fuzzy evolutionary approach to constrained optimization problems [Text] /T. V. Le // Proceedings of the Second IEEE Conference on Evolutionary Computation, November 1995 Perth. – Perth : IEEE, 1995. – Р. 274-278.

Downloads

Published

2012-06-01

How to Cite

Єгорова, О. В. (2012). Constraint handling techniques used with evolutionary algorithms. analysis and applica-tion. Eastern-European Journal of Enterprise Technologies, 3(4(57), 19–26. https://doi.org/10.15587/1729-4061.2012.4009

Issue

Vol. 3 No. 4(57) (2012): Mathematics and cybernetics - fundamental and applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2014 Ольга В’ячеславівна Єгорова

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.