  An important benefit of multi-objective search is that it maintains a diverse
population of candidates, which helps in deceptive problems in particular. Not
all diversity is useful, however: candidates that optimize only one objective
while ignoring others are rarely helpful. This paper proposes a solution: The
original objectives are replaced by their linear combinations, thus focusing
the search on the most useful tradeoffs between objectives. To compensate for
the loss of diversity, this transformation is accompanied by a selection
mechanism that favors novelty. In the highly deceptive problem of discovering
minimal sorting networks, this approach finds better solutions, and finds them
faster and more consistently than standard methods. It is therefore a promising
approach to solving deceptive problems through multi-objective optimization.
