Regresar

An Evolutionary Algorithm for Solving Decision Space Constrained Multi-Objective Binary Optimization Problems

Abstract:

In real-world multi-objective optimization problems, it is common to find constraints that limit the feasible space, challenging the solver to explore the infeasible region and find good feasible solutions. Several evolutionary algorithms with various constraint-handling techniques have been proposed over the years. However, most focus on problems with continuous variables and constraints defined over the objective space and might not be suitable for binary problems and constraints defined on the decision space. This work proposes a multi-objective evolutionary algorithm for solving decision space-constrained multi-objective binary optimization problems. The proposed method can switch between a simple evolutionary algorithm, which optimizes constraint violation of infeasible solutions, and a random bit climber, which optimizes the objective functions of feasible solutions. We compare the performance of the proposed algorithm to other state-of-the-art evolutionary algorithms and study its behavior using SAT Constrained MNK-Landscapes. We show that the proposed algorithm can effectively optimize constraint violation of infeasible solutions, quickly find feasible solutions, and performs better than the compared algorithms in highly constrained problems with varying numbers of objectives, epistatic interactions, equality and inequality constraints, and constraint difficulty.