Analysis of the (1+1) EA on subclasses of linear functions under uniform and linear constraints

Linear functions have gained great attention in the run time analysis of evolutionary computation methods. The corresponding investigations have provided many effective tools for analyzing more complex problems. So far, the runtime analysis of evolutionary algorithms has mainly focused on unconstrained problems, but problems occurring in applications frequently involve constraints. Therefore, there is a strong need to extend the current analyses and used methods for analyzing unconstrained problems to a setting involving constraints. In this paper, we consider the behavior of the classical (1+1) Evolutionary Algorithm on linear functions under linear constraint. We show tight bounds in the case where the constraint is given by the ONEMAX function and the objective function is given by either the ONEMAX or the BINVAL function. For the general case we present upper and lower bounds. (C) 2018 Elsevier B.V. All rights reserved.