A Multiobjective Evolutionary Algorithm Based On Decomposition

Population-based evolutionary algorithms are able to approximate a set of Pareto solutions in a single run,multiobjective evolutionary algorithms(MOEAs)have been recognized as a major methodology for solving multiobjective optimization problems(MOPs).Decomposition based multiobjective evolutionary algorithms(MOEA/D)decompose a multiobjective optimization problem into a set of scalar objective subproblems and solve them in a collaborative way.This thesis analyzes the advantages and disadvantages of decomposition-based MOEAs.A constrained decomposition with grids(CDG)and an adaptive strategy of adjustments for direction vectors are proposed in this thesis.This thesis addresses the following two aspects:Commonly used decomposition approaches in MOEA/D(WS,TCH and PBI)are originated from mathematical programming and the direct use of them may not suit MOEAs due to their population-based property.For instance,these decomposition approaches used in MOEAs may cause the loss of diversity and/or be very sensitive to the shapes of PFs.This thesis proposes a constrained decomposition with grids(CDG)that can better address these two issues thus more suitable for MOEAs.In addition,different subproblems in CDG defined by the constrained decomposition constitute a grid system.The grids have an inherent property of reflecting the information of neighborhood structures among the solutions,which is a desirable property for restricted mating selection in MOEAs.Based on CDG,a constrained decomposition MOEA with grid(CDG-MOEA)is further proposed.The extensive experiments are conducted to compare CDG-MOEA with other state-of-art MOEAs.The experimental results show that CDG-MOEA outperforms the compared algorithms in terms of both the convergence and diversity.More importantly,it is not sensitive to the shapes of PFs and can still be very effective on MOPs with complex PFs(e.g.,extremely convex,or with disparately scaled objectives).The performance of MOEA/D deteriorates when the number of objectives increases to four or above.To further improve its convergence on MaOPs and its diversity for MaOPs with irregular Pareto fronts(PFs,e.g.,degenerate and disconnected ones),we propose a decomposition-based many-objective evolutionary algorithm with two types of adjustments for the direction vectors(MaOEA/D-2ADV).At the very beginning,search is only conducted along the boundary direction vectors to achieve fast convergence,followed by the increase of the number of the direction vectors for approximating a more complete PF.After that,a Pareto-dominance-based mechanism is used to detect the effectiveness of each direction vector;and the positions of ineffective direction vectors are adjusted to better fit the shape of irregular PFs.The extensive experimental studies have been conducted to validate the efficiency of MaOEA/D-2ADV on many-objective optimization benchmark problems.