Alternative Techniques to Handle Constraints using Evolutionary Algorithms

Project Description

We are studying the use of techniques that make unnecessary the use of the traditional penalty factors to handle constraints in an optimization problem. There are 3 main paths of research that we are interested to explore:

Use of techniques based in the immune system
Use of self-adaptive penalties
Use of multiobjective optimization techniques

A full description of the project may be found here (in Spanish).

Acknowledgments

This project has current support from CONACyT through grant No. I-29870 A.

Current Progress

The Principal Investigator (P.I.) has developed two new constraint-handling techniques for evolutionary-based approaches. The first is based on the idea of self-adaptation and it consists on a traditional penalty function that uses: a) the number of constraints violated and b) the total amount of constraint violation accumulated. These 2 values are combined using two penalty factors that are self-adapted by the genetic algorithm itself using co-evolution. Two populations are used such that one optimizes the original objective function whereas the other tries to find the optimum penalty factors to be used.

The second technique uses a population-based evolutionary multiobjective optimization approach to handle constraints. All constraints are handled by individual (and independent) sub-populations, and an extra sub-population is used to handle the original (unconstrained) objective function. The idea is to devote only a small portion of the total population to satisfy each of the constraints and then combine this partially feasible solutions so that we approach the feasible region.

Both approaches have produced good results in several engineering optimization problems (see details in the publications indicated below), but several issues still remain to be solved such as efficiency (minimize the total number of fitness function evaluations), speed of convergence, etc.

Research Opportunities

Anyone interested in this project may collaborate in one or more of the following activities (at least two Masters thesis may be produced out of this project) :

Implementing the existing techniques for constraint-handling in the context of numerical optimization. All of them must be implemented in the same platform to allow a fair comparison. The resulting system will be made public domain. (Undergraduate student required)
Develop a set of test functions that include: linear and non-linear constraints, equality and inequality constraints, discrete and continuous variables, search spaces of low and high dimensionality, disjoint feasible regions, non-convex search spaces, small feasible regions within a large search space, real-world problems where constraints are generated by a (black box) module and can not be defined in algebraic form. (Masters student required)
Define a set of performance measures that allow a fair comparison of the different constraint-handling techniques under study. We aim at measuring not only the number of fitness function evaluations (the typical measure of performance), but also certain aspects of convergence, such as the way and speed at which a technique approaches the feasible region and its robustness. (Masters student required)
Evaluation of the existing techniques using the platform developed in the first point and the test functions defined in the second. The performance measure under study will be those from the third point. (Masters student required)
Development of new constraint-handling techniques based on the experience obtained from the experiments performed. The paths of research of main interest are those mentioned above. (Masters student required)

Interested students, please contact Dr. Carlos A. Coello Coello.

Related Publications

Coello, Carlos A. Treating Constraints as Objectives for Single-Objective Evolutionary Optimization, Engineering Optimization, Vol. 32, No. 3, pp. 275-308, February 2000 .
Coello, Carlos A. Use of a Self-Adaptive Penalty Approach for Engineering Optimization Problems, Computers in Industry, Vol. 41, No. 2, pp. 113-127, January 2000 .
Coello, Carlos A. The use of a multiobjective optimization technique to handle constraints, CIMAF'99, La Habana, Cuba, Proceedings of the Second International Symposium on Artificial Intelligence, Adaptive Systems, Edited by Alberto A. Ochoa Rodríguez, Marta R. Soto Ortiz and Roberto Santana Hermida, La Habana, Cuba, pp. 251-256, March 1999.
Coello Coello, Carlos A. A Survey of Constraint Handling Techniques used with Evolutionary Algorithms, Technical Report Lania-RI-99-04, Laboratorio Nacional de Informática Avanzada, 1999.
Coello Coello, Carlos A. Self-Adaptive Penalties for GA-based optimization, 1999 Congress on Evolutionary Computation, Washington, D.C., Vol. 1, pp. 573-580, IEEE Service Center, July 1999

.
Coello, Carlos A. Constraint-handling through a multiobjective optimization technique, Proceedings of the 1999 Genetic and Evolutionary Computation Conference (GECCO'99). Workshop Program, Edited by Annie S. Wu, Orlando, Florida, USA, pp. 117--118, July 1999.
Coello, Carlos A. Constraint-Handling Through a Multi-Objective Optimization Technique, Smart Engineering System Design: Neural Networks, Fuzzy Logic, Evolutionary Programming, Data Mining, and Complex Systems (ANNIE'99), Edited by Cihan H. Dagli, Anna L. Buczak, Joydeep Ghosh, Mark J. Embrechts and Okan Ersoy, pp. 1021--1026, Vol. 9, November 1999.
Coello Coello, Carlos A. and Mezura Montes, Efrén, Uso de Auto-Adaptación para Manejar Restricciones con un Algoritmo Genético, Segundo Encuentro Nacional de Computación, Taller de Aprendizaje, Pachuca, Hidalgo, 12-15 de septiembre de 1999.