Decomposition-based Multi-objective Evolutionary Algorithms And Their Applications

Decomposition-based multi-objective evolutionary algorithms(MOEAs) exploit the divide-and-conquer idea to e?ectively reduce the di?culty in solving the multi or many-objective optimization problems. According to the form of decomposition,decomposition-based MOEAs can be further classified into two types: aggregation-based MOEAs and reference-point based MOEAs. Although decomposition-based MOEAs have become one of the most promising techniques for many-objective optimization problems, they still have the defects and shortages in both the development of the methods and practices. This dissertation focuses on this class of algorithms, and conducts a systematic study on “how to balance the convergence and diversity in the objective space”and “how to balance the exploration and exploitation in the decision space”, aiming to further perfect the general algorithmic framework and promote their applications on real-world problems. The major work and contribution in this dissertation include:(1) To address the problem of diversity loss in aggregation-based many-objective optimizers, an idea is proposed to maintain the desired distribution of solutions in the evolutionary process explicitly by exploiting the perpendicular distance from the solution to the weight vector in the objective space, which is expected to achieve better balance between convergence and diversity in many-objective optimization. This idea is implemented to enhance two typical aggregation-based algorithms, multi-objective evolutionary algorithms based on decomposition(MOEA/D) and ensemble fitness ranking.(2) The recently suggested NSGA-III is one of the most representative referencepoint based MOEAs, but it has the di?culty in converging to the Pareto front in highdimensional objective space. To address this problem, an evolutionary algorithm based on a new dominance relation is proposed for many-objective optimization. The proposed evolutionary algorithm aims to enhance the convergence of NSGA-III by exploiting the fitness evaluation scheme in MOEA/D, but still inherit the strength of the former in diversity maintenance.(3) An experimental investigation of variation operators in NSGA-III is conducted to understand how to balance the exploration and exploitation in decomposition-based MOEAs for solving many-objective optimization problems, and three new NSGA-III variants are proposed. The experimental results show that the performance of NSGAIII is significantly bottlenecked by its variation operators.(4) A new memetic algorithm is proposed for solving the multi-objective flexible job shop scheduling problem(MO-FJSP), which is an important problem in the field of production scheduling. The proposed algorithm incorporates a critical operation based local search procedure into the adapted NSGA-II, where the selection of initial solution and direction for local search is based on a selection mechanism similar to that in multiobjective genetic local search. Furthermore, a novel hierarchical strategy is adopted in local search to handle the considered three objectives with di?erent priority.