The Unreasonable Effectiveness of Optimal Transport Distance in the Design of Multi-Objective Evolutionary Optimization Algorithms
摘要
Most Multi-Objective Evolutionary Algorithms (MOEAs) face significant challenges in many-objective optimization. MOEAs have random elements in the selection and crossover operators which endow them with global convergence properties. The key contribution of this paper is to integrate discrete probability distributions instead of just randomization in the design of the algorithm. This allows us to use the Wasserstein distance to drive the selection operator, instead of the Euclidean distance. Achieving balance between convergence and diversity is a key issue in evolutionary multi-objective optimization. The use of the Wasserstein distance constitutes a novel approach to the diversity management mechanism. This approach can be applied to the two main strategies: Pareto sampling, as in NSGA-II, and decomposition, as in MOEA/D, resulting in new algorithms NSGA-II/W and MOEA/D/W. The performance of the proposed algorithms is validated on a number of unconstrained and constrained benchmark problems with up to 10 objectives.