Maximizing population diversity in single-objective optimization
Tamara Ulrich, Lothar Thiele · 2011
Typically, optimization attempts to find a solution which minimizes the given objective function. But often, it might also be useful to obtain a set of structurally very diverse solutions which all have acceptable objective values. With such a set, a decision maker would be given a choice of solutions to select from. In addition, he can learn about the optimization problem at hand by inspecting the diverse close-to-optimal solutions. This paper proposes NOAH, an evolutionary algorithm which solves a mixed multi-objective problem: Determine a maximally diverse set of solutions whose objective values are below a provided objective barrier. It does so by iteratively switching between objective value and set-diversity optimization while automatically adapting a constraint on the objective value until it reaches the barrier. Tests on an nk-Landscapes problem and a 3-Sat problem as well as on a more realistic bridge construction problem show that the algorithm is able to produce high quality solutions with a significantly higher structural diversity than standard evolutionary algorithms.