Sex and death: towards biologically inspired heuristics for constraint handling

ABSTRACT

Constrained continuous optimization is still an interesting field of research. Many heuristics have been proposed in the last decade. Most of them are based on penalty functions. Here, we experimentally investigate the two constraint handling heuristics proposed by Kramer and Schwefel. The two sexes evolution strategy (TSES) is inspired by the biological concept of sexual selection and pairing. The death penalty step control evolution strategy (DSES) is based on the controlled reduction of a minimum step size depending on the distance to the infeasible search space. These two methods are able to overcome the problem of premature mutation strength reduction, a result of the self-adaptation mechanism of evolution strategies in constrained environments. All methods are experimentally evaluated on a couple of typical constrained test problems. These experiments offer recommendations for the TSES population ratios and the speed of the ε-reduction process of the DSES.

REFERENCES

• 1: J. C. Bean and A. B. Hadj-Alouane. A Dual Genetic Algorithm for Bounded Integer Programs. Technical report, Department of Industrial and Operations Engineering, The University of Michigan, 1992.
• 2: S. V. Belur. CORE: Constrained Optimization by Random Evolution. In J. R. Koza, editor, Late Breaking Papers at the Genetic Programming 1997 Conference, pages 280--286, Stanford University, California, Juli 1997. Stanford Bookstore.
• 3: Hans-Georg Beyer , Hans-Paul Schwefel, Evolution strategies –A comprehensive introduction, Natural Computing: an international journal, v.1 n.1, p.3-52, May 2002 [doi>10.1023/A:1015059928466]
• 4: J. Brest, V. Žumer, and M. S. Maučec. Self-adaptive Differential Evolution Algorithm in Constrained Real-Parameter Optimization. In The 2006 IEEE Congress on Evolutionary Computation CEC2006, pages 919--926. IEEE Press, 2006.
• 5: C. A. Coello Coello. Treating Constraints as Objectives for Single-Objective Evolutionary Optimization. Engineering Optimization, 32(3):275--308, 2000.
• 6: Carlos A. Coello Coello, Use of a self-adaptive penalty approach for engineering optimization problems, Computers in Industry, v.41 n.2, p.113-127, March 2000 [doi>10.1016/S0166-3615(99)00046-9]
• 7: C. A. Coello Coello. Theoretical and Numerical Constraint Handling Techniques used with Evolutionary Algorithms: A Survey of the State of the Art. Computer Methods in Applied Mechanics and Engineering, 191(11-12):1245--1287, Januar 2002.
• 8: K. Deb. An Efficient Constraint Handling Method for Genetic Algorithms. Computer Methods in Applied Mechanics and Engineering, 186(2/4): 311--338, 2001.
• 9: A. Fiacco and G. McCormick. The sequential unconstrained minimization technique for nonlinearprogramming -a primal-dual method. Mgmt. Sci., 10:360 --366, 1964.
• 10: F. Hoffmeister and J. Sprave. Problem-independent handling of constraints by use of metric penalty functions. In L. J. Fogel, P. J. Angeline, and T. B äck, editors, Proceedings of the Fifth Annual Conference on Evolutionary Programming (EP'96), pages 289--294, San Diego, California, Februar 1996. The MIT Press.
• 11: A. Homaifar, S. H. Y. Lai, and X. Qi. Constrained Optimization via Genetic Algorithms. Simulation, 62(4):242--254, 1994.
• 12: F. Jiménez and J. L. Verdegay. Evolutionary techniques for constrained optimization problems. In H. -J. Zimmermann, editor, 7th European Congress on Intelligent Techniques and Soft Computing (EUFIT '99), Aachen, 1999. Verlag Mainz.
• 13: J. Joines and C. Houck. On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GAs. In D. Fogel, editor, Proceedings of the ?rst IEEE Conference on Evolutionary Computation, pages 579--584, Orlando, Florida, 1994. IEEE Press.
• 14: S. Koziel and Z. Michalewicz. Evolutionary Algorithms, Homomorphous Mappings, and Constrained Parameter Optimization. Evolutionary Computation, 7:19--44, 1999.
• 15: O. Kramer , H.-P. Schwefel, On three new approaches to handle constraints within evolution strategies, Natural Computing: an international journal, v.5 n.4, p.363-385, November 2006 [doi>10.1007/s11047-006-0001-x]
• 16: A. Kuri-Morales and C. V. Quezada. A Universal Eclectic Genetic Algorithm for Constrained Optimization. In Proceedings 6th European Congress on Intelligent Techniques & Soft Computing, EUFIT '98, pages 518--522, Aachen, September 1998. Verlag Mainz.
• 17: J. Liang, T. P. Runarsson, E. Mezura-Montes, M. Clerc, P. Suganthan, C. A. C. Coello, and K. Deb. Problem De?nitions and Evaluation Criteria for the CEC 2006 Special Session on Constrained Real-Parameter Optimization. In Technical Report, Singapore, 2006. Nanyang Technological University.
• 18: Zbigniew Michalewicz , David B. Fogel, How to solve it: modern heuristics, Springer-Verlag New York, Inc., New York, NY, 2000
• 19: E. M. Montes and C. A. Coello Coello. A simple multi-membered evolution strategy to solve constrained optimization problems. IEEE Transactions on Evolutionary Computation, 9:1--17, February 2005.
• 20: Jan Paredis, Co-evolutionary Constraint Satisfaction, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.46-55, October 09-14, 1994
• 21: I. C. Parmee and G. Purchase. The development of a directed genetic search technique for heavily constrained design spaces. In I. C. Parmee, editor, Adaptive Computing in Engineering Design and Control, pages 97--102, Plymouth, UK, 1994. University of Plymouth.
• 22: David Powell , Michael M. Skolnick, Using Genetic Algorithms in Engineering Design Optimization with Non-Linear Constraints, Proceedings of the 5th International Conference on Genetic Algorithms, p.424-431, June 01, 1993
• 23: Rodolphe Le Riche , Catherine Knopf-Lenoir , Raphael T. Haftka, A Segregated Genetic Algorithm for Constrained Structural Optimization, Proceedings of the 6th International Conference on Genetic Algorithms, p.558-565, July 15-19, 1995
• 24: Marc Shoenauer , Spyros Xanthakis, Constrained GA Optimization, Proceedings of the 5th International Conference on Genetic Algorithms, p.573-580, June 01, 1993
• 25: Hans-Paul Paul Schwefel, Evolution and Optimum Seeking: The Sixth Generation, John Wiley & Sons, Inc., New York, NY, 1993
• 26: Patrick D. Surry , Nicholas J. Radcliffe , Ian D. Boyd, A Multi-objective Approach to Constrained Optimisation of Gas Supply Networks: the COMOGA Method, Selected Papers from AISB Workshop on Evolutionary Computing, p.166-180, April 03-04, 1995

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

General Terms:
Algorithms, Experimentation

Keywords:
constrained real parameter optimization, evolution strategies