A new Co-evolutionary Algorithm Based on Constraint Decomposition
Emmanuel Kieffer, Grégoire Danoy, Pascal Bouvry, Anass Nagih · 2017
Handling constraints is not a trivial task in evolutionary computing. Even if different techniques have been proposed in the literature, very few have considered co-evolution which tends to decompose problems into easier sub-problems. Existing co-evolutionary approaches have been mainly used to separate the decision vector. In this article we propose a different co-evolutionary approach, referred to as co-evolutionary constraint decomposition algorithm (CCDA), that relies on a decomposition of the constraints. Indeed, it is generally the conjunction of some specific constraints which hardens the problems. The proposed CCDA generates one sub-population for each constraint and optimizes its own local fitness. A sub-population will first try to satisfy its assigned constraint, then the remaining constraints from other sub-populations using a cooperative mechanism, and finally the original objective function. Thanks to this approach, sub-populations will have different behaviors and solutions will approach the feasible domain from different sides. An exchange of information is performed using crossover between individuals from different sub-populations while mutation is applied locally. Promising mutated features are then transmitted through mating. The proposed CCDA has been validated on 8 well-known benchmarks from the literature. Experimental results show the relevance of constraint decomposition in the context of co-evolution compared to state-of-the-art algorithms.