Integrating Pseudo-Boolean Constraint Reasoning
in Multi-Objective Evolutionary Algorithms
Abstract
Constraint-based reasoning methods thrive in solving problem instances with a tight solution space.
On the other hand, evolutionary algorithms are usually effective when it is not hard to satisfy the problem constraints. This dichotomy has been observed
in many optimization problems. In the particular
case of Multi-Objective Combinatorial Optimization (MOCO), new recently proposed constraintbased algorithms have been shown to outperform
more established evolutionary approaches when a
given problem instance is hard to satisfy. In this paper, we propose the integration of constraint-based
procedures in evolutionary algorithms for solving
MOCO. First, a new core-based smart mutation operator is applied to individuals that do not satisfy
all problem constraints. Additionally, a new smart
improvement operator based on Minimal Correction Subsets is used to improve the quality of the
population. Experimental results clearly show that
the integration of these operators greatly improves
multi-objective evolutionary algorithms MOEA/D
and NSGAII. Moreover, even on problem instances
with a tight solution space, the newly proposed algorithms outperform the state-of-the-art constraintbased approaches for MOCO