Divide-and-Conquer Approach for Revealing the Non-dominated Solutions in Multi-objective Optimization Problem

摘要

Revealing the non-dominated solutions is one of the vital and essential part of multi-objective optimization algorithms. However, the process of identifying non-dominated solutions in the case of multi-objective optimization problems is computationally very expensive even though properties of dominance relation adhered very strictly. In many multi-objective optimization problems, to identify all non-dominated solutions from a set of N solutions with K objectives naïve and slow approach is commonly accepted with O(KN2) computation time. Realizing this problem as the heart of multi-objective optimization problem, we attempt here a new effective and comparatively better approach for revealing all non-dominated solutions based on divide-and-conquer technique by enjoying O(K N log2 N) computation time. Our experimental results in many benchmark multi-objective optimization problems confirm the aforementioned claim.