The COMOGA Method: Constrained Optimisation by Multi-Objective Genetic Algorithms
Patrick D. Surry, Nicholas J. Radcliffe · 1997
This paper describes a novel method for attacking constrained opti- misation problems with evolutionary algorithms, and demonstrates its effective- ness over a range of problems. COMOGA (Constrained Optimisation by Multi- Objective Genetic Algorithms) combines two evolutionary techniques for multi- objective optimisation with a simple regulatory mechanism to produce a constrained optimisation method. It shares the universal applicability of penalty-function ap- proaches, but requires significantly fewer free control parameters. COMOGA takes a dual perspective, considering a constrained optimisation problem sometimes as a constraint satisfaction problem, and sometimes as an un- constrained optimisation problem. These two formulations are treated simultane- ously, using a single population, by basing each selection decision on the basis of either constraint violation or function value. A simple adaptive feedback mech- anism couples the two formulations by adjusting the relative likelihood of these choices. Unlike penalty function approaches, COMOGA dynamically adapts the emphasis placed on constraint satisfaction and objective function value as the op- timisation proceeds, usually yielding final populations which are both feasible and highly fit. COMOGA has been successfully applied to real industrial problems with com- parable performance to highly tuned penalty function approaches. On a test suite of constrained problems previously studied by Michalewicz, application of CO- MOGA required minimal effort but proved superior to all previous evolutionary methods known to have been applied; indeed it was the only method which found feasible solutions in every run for every problem.