Runtime analysis of different Approaches to select conflicting auxiliary objectives in the generalized OneMax problem

It has been shown that single-objective optimization may be improved by introducing auxiliary objectives. Ideally, auxiliary objectives should be designed to be independent. However, in practice, this is not always easy or possible and the objectives may be conflicting. Particularly, this happens in the Job-Shop Scheduling problem and in certain search-based software engineering problems. We theoretically analyse different approaches of using auxiliary objectives on the general ONEMAX problem with conflicting auxiliary objectives ONEMAX and ZEROMAX. In most of the considered methods, the optimized objectives are selected dynamically. We also consider a method, where the same objectives are optimized during the whole run. We show that dynamic selection of conflicting auxiliary objectives combined with explicit optimization of the target objective has the best runtime of O(nlogn) among all the considered methods.