Distributed Bit Climbing Algorithm for Binary Multi-objective Optimization
Yudai Tagawa, Hernan E. Aguirre, Kiyoshi Tanaka · 2024
We study a distributed bit climbing algorithm for multi-objective optimization of binary problems. This algorithm decomposes the many-objective problem into a minimum number of single-objective problems, specified by the original evaluation functions and one additional scalarizing function that computes the solution hypervolume. Random bit climbers optimize sepa-rately their assigned single-objective function until they reach a local optimum and restart their search from a bounded population of non-dominated solutions collected from the solutions generated by all climbers. In this paper, we observe the climbing characteristics according to the restarting solution of the climbers to shed light on how they contribute to finding an approximation of the Pareto set. Also, we verify the effectiveness of the solution hypervolume as a scalarization function. We evaluate the method on subclasses of epistatic problems using MNK-landscapes, varying the number of objectives from 2 to 5 and the number of epistatic interactions from 1 to 20. We compare results with two popular decomposition-based multi-objective optimizers, showing that the simpler distributed bit climber performs better than the other optimizers in 2, 3, and 4 objective problems for most values of epistatic interactions.