Research On Evolutionary Algorithms Based On Decomposition For Multi-objective And Many-objective Optimization Problems

There are many problems with several optimization objectives or criterias in the real world(multi-objective optimization problems, MOPs). MOPs are widely used in engineering optimization and design, data mining, and operation research, biomedical and so on. Because objectives of an MOP are conflicting and exclusive to each other, there is not a best solution but a set of best solutions(Pareto optimal solutions). Multi-objective optimization algorithms(MOEAs) are an effective method for solving MOPs, and research on MOEAs has been one of the hottest points. The diversity and convergence of obtained solutions are two main goals of MOEAs. In order to simultaneously achieve the two goals, several multi-objective evolutionary algorithms based on decomposition are designed for complicated multi-objective optimization problems and many-objective problems. The main contributions of this thesis are as follows:First, in order to improve the search efficiency of an evolutionary algorithm and maintain the diversity of solutions, the learning automata is firstly used for quantization orthogonal crossover(QOX) and a new fitness function based on decomposition is proposed to achieve the above two goals respectively. Based on these, an orthogonal evolutionary algorithm(OELA) is proposed. The multi-objective optimization problems with complicated Pareto optimal solutions(PS) and many local Pareto optimal fronts(PF) are tested in our experiments. The experimental results show that, for multi-objective optimization problems with complicated PS, the performance of OELA is better than MOEA/D, NNIA and NSGAII, and OELA is able to find more accurate and evenly distributed Pareto-optimal fronts than others three algorithms; for multi-objective optimization problems with many PFs, OELA can more quickly converge to global PF than MOEA/D, NNIA and NSGAII.Second, in order to well maintain the diversity of solutions, an evolutionary algorithm based on decomposition of the objective space(EASS) is designed to well maintain the diversity. Firstly, objective space of a MOP is divided into a number of sub-objective spaces by a set of direction vectors; then, EASS makes each sub-objective space have a solution, even if it is not a non-dominated solution. In such a way, the diversity ofobtained solutions can be maintained. In addition, if a solution is dominated by other solutions, the solution can generate more new solutions than its dominators, which makes the solution of each sub-objective space converge to the optimal solutions as more as possible. Six such MOPs are tested to estimate the performance of EASS, simulation results show that EASS is better at maintaining the diversity than MOEA/D, NNIA and NSGAII, and the solutions obtained by EASS can converge closer to the true PF.Third, when the number of objectives increases(A MOP with more than four objectives is a many-objective optimization problem), the proportion of non-dominated solution in population will increase quickly, many MOEAs heavily depend on the proportion and a large proportion can cause that the convergence ability of these MOEAs sharply reduce. In order to enhance the convergence pressure and maintain the diversity, a new contraction method(CN) is proposed to contract the non-dominance area. The method makes the objective space as well as the non-dominance area be contracted into smaller regions by modifying the function value of each objective. Then the modified objective vectors are ranked via the Pareto dominance. This proposed contraction method can well balance the convergence and diversity. Compared with two state-of-the-art relaxed forms of Pareto dominance, the experimental results show that this method can well maintain the diversity and enhance the convergence pressure.Fourth, for many-objective optimization problems, diversity and convergence of obtained solutions are very difficult to achieve. In order to achieve the two goals, a uniform evolutionary algorithm based on decomposition and the proposed contraction method(UREA/D) is proposed. UREA/D uses the uniform design to generate the uniformly distributed weight vectors over the design space, and the number of the vectors will not increase nonlinearly with the number of objectives and can be freely set, which makes the size of the population be freely set. In order to improve the convergence of UREA/D, a sub-population strategy is used to enhance the local search, and the CN is used to rank the solutions of each sub-population. MOPs with from 5 to 25 objectives are tested respectively, Comparing with some efficient state-of-the-art algorithms, e.g., NSGAII-CE(NSGAII based on control of dominance area of solutions), MOEA/D and Hyp E, simulation results show that UREA/D is able to obtain better diversity and converge closer to the Pareto optimal solutions.