Usefulness of infeasible solutions in evolutionary search: An empirical and mathematical study

When evolutionary algorithms are used to solve constrained optimization problems, the question arises how best to deal with infeasible solutions in the search space. A recent theoretical analysis of two simple test problems argued that allowing infeasible solutions to persist in the population can either help or hinder the search process, depending on the structure of the fitness landscape. We report new empirical and mathematical analyses that provide a different interpretation of the previous theoretical predictions: that the important effect is on the probability of finding the global optimum, rather than on the time complexity of the algorithm. We also test a multiobjective approach to constraint-handling, and with an additional test problem we demonstrate the superiority of this multiobjective approach over the previous single-objective approaches.