Efficient Hill-Climber for Multi-Objective Pseudo-Boolean Optimization
This work addresses a computational bottleneck for researchers in multi-objective optimization, though it is incremental as it builds on prior single-objective results.
The paper tackles the problem of efficiently finding improving moves in multi-objective pseudo-Boolean optimization by extending a constant-time method from single-objective to multi-objective cases, specifically applied to NK and Mk Landscapes.
Local search algorithms and iterated local search algorithms are a basic technique. Local search can be a stand along search methods, but it can also be hybridized with evolutionary algorithms. Recently, it has been shown that it is possible to identify improving moves in Hamming neighborhoods for k-bounded pseudo-Boolean optimization problems in constant time. This means that local search does not need to enumerate neighborhoods to find improving moves. It also means that evolutionary algorithms do not need to use random mutation as a operator, except perhaps as a way to escape local optima. In this paper, we show how improving moves can be identified in constant time for multiobjective problems that are expressed as k-bounded pseudo-Boolean functions. In particular, multiobjective forms of NK Landscapes and Mk Landscapes are considered.