Evolutionary approaches to many-objective combinatorial optimization problems

Abstract

Many-objective evolutionary approaches try to characterize and overcome the challenges posed by the large number of objectives and have been shown to be very e ective for achieving good Pareto approximations. Despite the growing interest, most of the existing studies work on well-de ned continuous objective functions with designed features, and studies on combinatorial problems are still rare. The proposed many-objective evolutionary algorithm is characterized by elitist nondominated sorting and reference set based sorting where the reference points are mapped onto a xed hyperplane obtained at the beginning of the algorithm by solving single-objective problems. All evolutionary mechanisms such as reference point guided path relinking, repair and local improvement procedures are designed to complement the reference set based sorting. Moreover, the reference set co-evolves simultaneously with the solution set, using both cooperative and competitive interactions to balance diversity and convergence, and adapts to the topology of the Pareto front in a self-adaptive parametric way. The proposed algorithm works successfully both under binary and permutation encoding, as well as for correlated objectives or objectives with di erent scales. Near optimal solutions can be used to construct the hyperplane without any signi cant deterioration in the quality of the Pareto approximation. Moreover, when an optimization problem under scenario-based uncertainty is modeled as a many-objective problem, the proposed algorithm can provide good solutions simultaneously for several robust measures. Numerical experiments demonstrate the success of the proposed algorithm compared to state-of-art approaches and con rm that it can be applied sustainably to a variety of many-objective combinatorial problems.