Generalized incremental orthant search: towards efficient steady-state evolutionary multiobjective algorithms: towards efficient steady-state evolutionary multiobjective algorithms

Some of the modern evolutionary multiobjective algorithms have a high computational complexity of the internal data processing. To further complicate this problem, researchers often wish to alter some of these procedures, and to do it with little effort.

The problem is even more pronounced for steady-state algorithms, which update the internal information as each single individual is computed. In this paper we explore the applicability of the principles behind the existing framework, called generalized offline orthant search, to the typical problems arising in steady-state evolutionary multiobjective algorithms.

We show that the variety of possible problem formulations is higher than in the offline setting. In particular, we state a problem which cannot be solved in an incremental manner faster than from scratch. We present an efficient algorithm for one of the simplest possible settings, incremental dominance counting, and formulate the set of requirements that enable efficient solution of similar problems. We also present an algorithm to evaluate fitness within the IBEA algorithm and show when it is efficient in practice.