The Research On Multiobjective Evolutionary Algorithm Based On Decomposition

The optimization problems in real life tend to cope with multiple targets, for example, time,cost, quality, quantity, etc. Evolutionary algorithms are a class of stochastic search algorithm, bysimulating the natural biological evolution and natural selection to guide an evolutionary processof individuals and to accumulate the dominant genes. Evolutionary algorithms are very robust andstrong adaptive, which can help us to avoid much limitations when solving problems directly onlywith some classic mathematic approaches, thus evolutionary algorithms can deal with the complexproblems more effectively than traditional optimization methods feel difficult to solve. What’smore, big successes of NSGA-II[1], an excellent evolutionary algorithm based on the Paretodominance method, give researchers a false impression that traditional mathematic methods inoptimization domain seem out of date. Fortunately, in recent years, methods based on scalarfunctions and decomposition approaches begin to change this situation and become one of mostnovel as well as attractive trends originating from traditional mathematic theory, then affectsfurther to the entire multi-objective optimization domain. As result, to find inspirations amongtraditional principles and approaches has become a new path. Usually, the sub-objectives amongone multi-objective optimization problem are conflictive between each other. In the meanwhile,optimization algorithm is aiming to find a set of compromised solutions to the each sub-problem,i.e., the solutions named Pareto optima. Supposed to be given an aggregative function and someorders with several preferences, a multi-objective problem can be converted to a single-objectiveoptimization problem that means many successful single-objective optimization algorithms can beeasily adopted to explore optimal solutions. However, an ideal trade-off relation for eachsub-objective cannot be predetermined, therefore an approach can provide the best candidatesolutions and choose preferences among them is necessary. Decomposition-based multi-objectiveevolutionary algorithm (MOEA/D[2]) transforms a multi-objective optimization problem into a setof single-objective and assigns suitable individuals to the each sub-problem problems via a set ofpre-generated uniform weight vectors. Obviously, the weight vectors are directly related to theperformance of the solutions. The bottleneck is the quality of a group of good weight vectors isconnected to different concrete problems, i.e., how to adjust the weight vectors and sub-problemsdynamically according to different multi-objective optimization problem becomes a key section indecomposition-based multi-objective evolutionary algorithm research region.In this research, a new method to produce uniform weights and the reasons how the weightvectors to affect shape of the non-dominant surface during the evolutionary procedure aim to beinvestigated. The main contents include the following three aspects:First, aggregation method convert the weight vectors into several selection pressures for adifferent directions and these kinds of conversions are regular in a certain degree to theaggregation functions. When using aggregation methods to decompose problems to be optimized,this research selects the weight vectors corresponding to the sub-problems according torelationship between Pareto optimal solutions and the weight vectors, subsequently, applies theweight vectors to direct the evolution of each sub-problem. The new method can adaptively adjustthe evolutionary direction of each sub-problem, making many defects produced by fixing weightvectors up.Secondly, archive set applied keeps all non-dominated solutions gotten by the algorithm,which includes much information related to optima exploring for the problem. This kind of information is useful clue for searching optimum of each sub-problem. However, the scale ofarchive set becomes larger and larger during iterative procedure, thus this research uses theK-nearest neighbor method to adjust archive set, so the size of archive set can be adaptive with thepopulation size.Thirdly, avoiding to much computational resource-consuming, this research takes advantageof clustering methods based on tentative evaluation tools to determine when adjusting the weights.It is related to the clustering degree of archive. The method is so simple that can save morecomputational resource in each iteration.Finally, experimental results show that the proposed algorithm (SMOEA/D) has been greatlyimproved in terms of distribution. The use of the Weighted Sum aggregation method can deal withthe non-convex problems better, and the same done to the convergence speed of the newalgorithm.