Multi-Objective Evolutionary Optimization On Complicated Problems

Multi-objective optimization problems (MOPs) are hard problems in the field of optimization. Multi-objective evolutionary algorithms (MOEAs) are a kind of nature-inspired population-based stochastic algorithm, which can output the whole solution set for decision makers to select and analyze in a single run. Due to those advantages, booming MOEAs has become the most popular algorithm for MOPs. However, complicated MOPs are still a challenge for MOEAs. The complexity of complicated MOPs comes from two aspects, i.e., the complexity in decision and objective space. The linkage between decision variables increases the difficulty, the high dimensions of objective space lead the less-effective Pareto dominance, and noises on the objectives mislead searching. To solve those two kind of complicated MOPs, this paper carried out a series of work, which are shown as follows:1. For MOPs with complicated decision space, a direction vectors based co-evolutionary multi-objective optimization algorithm (DVCMOA) is propose. It is novel in the sense that DVCMOA applies the concept of direction vectors to co-evolutionary algorithms. DVCMOA first divides the entire population into several subpopulations on the basis of the initial direction vectors in the objective space. Then, it solves MOPs through the co-evolutionary interaction among the subpopulations in which individuals are classified according to their direction vectors. Finally, it explores the less developed regions to maintain the relatively uniform distribution of the solution space. In this way, DVCMOA has advantages in convergence, diversity and uniform distribution of the non-dominated solution set, which are explained through comparison with other state-of-the-art MOEAs.2. There can be a complicated mapping relation between decision variables and objective functions in MOPs. It is uncommon that decision variables influence objective functions equally. Decision variables act differently in different objective functions. Hence, often, the mapping relation is unbalanced, which causes some redundancy during the search in a decision space. In response to this scenario, a novel Memetic Optimization Strategy based on Dimension Reduction in decision space (DRMOS) is proposed. DRMOS firstly analyzes the mapping relation between decision variables and objective functions. Then, it reduces the dimension of the search space by dividing the decision space into several subspaces according to the obtained relation. Finally, it improves the population by the memetic local search strategies in these decision subspaces separately. Further, DRMOS has good portability to other MOEAs; that is, it is easily compatible with existing MOEAs. In order to evaluate its performance, we embed DRMOS in several state-of-the-art MOEAs to facilitate our experiments. The results show that DRMOS has the advantage in terms of convergence speed, diversity maintenance, and portability when solving MOPs with an unbalanced mapping relation between decision variables and objective functions.3. Non-dominated sorting plays an important role in Pareto-based MOEAs. When faced with many-objective optimization problems, the number of comparisons needed in non-dominated sorting becomes very large. In view of this, a new corner sort is proposed. Corner sort first adopts a fast and simple method to obtain a non-dominated solution from the corner solutions, and then uses the non-dominated solution to ignore the solutions dominated by it to save comparisons. Obtaining the non-dominated solutions requires much fewer objective comparisons in corner sort. In order to evaluate its performance, several state-of-the-art non-dominated sorts are compared with our corner sort on three kinds of artificial solution sets of MOPs and the solution sets generated from MOEAs on benchmark problems. The results show that comer sort performs well especially on many-objective optimization problems. Corner sort uses fewer comparisons than others.4. The redundancy of objectives exists in some many-objective optimization problems with correlated objectives (linearly or nonlinearly). Objective reduction can be used to decrease the difficulties of some many-objective optimization problems. A novel objective reduction approach based on nonlinear correlation information entropy (NCIE) is proposed. It uses the NCIE matrix to measure the linear and nonlinear correlation between objectives and a simple method to select the most conflicting objectives during the execution of MOEAs. Our approach is embedded into both Pareto-based and indicator-based MOEAs to analyze the impact of our reduction method on the performance of these algorithms. The results show that our approach significantly improves the performance of Pareto-based MOEAs on both reducible and irreducible many-objective optimization problems but does not help much the performance of indicator-based MOEAs.5. The large numbers of objectives of many-objective optimization problems pose challenges to MOEAs in terms of convergence, diversity, and complexity. Most existing MOEAs can only perform well in one of those three aspects. The two-archive algorithm (Two_Arch) is a low-complexity algorithm with two archives focusing on convergence and diversity separately. To design a more balanced MOEA on ManyOPs in all three aspects at the same time, a significantly improved two-archive algorithm (i.e., Two_Arch2) for many-objective optimization problems is proposed. In Two_Arch2, we assign different selection principles (indicator-based and Pareto-based) to the two archives. In addition, we design a new Lp-norm-based (p<1) diversity maintenance scheme for many-objective optimization problems in Two_Arch2. In order to evaluate the performance of Two_Arch2 on ManyOPs, we have compared it with several MOEAs on a wide range of benchmark problems with different numbers of objectives. The experimental results show that Two_Arch2 can cope with ManyOPs (up to 20 objectives) with satisfactory convergence, diversity, and complexity.6. Nadir points play an important role in many-objective optimization problems, which describe the ranges of their Pareto fronts. Using nadir points as references, decision makers may obtain their preference information for many-objective optimization problems. As the number of objectives of multi-objective optimization problems increases, nadir point estimation becomes a more difficult task. A novel nadir point estimation method based on emphasized critical regions for many-objective optimization problems is proposed. It maintains the non-dominated solutions near extreme points and critical regions after an individual number assignment to different critical regions. Furthermore, it eliminates similar individuals by a novel self-adaptive ε-clearing strategy. Our approach has been shown to perform better on many-objective optimization problems (between 10 objectives and 35 objectives) than two other state-of-the-art nadir point estimation approaches.7. Noises degrade the performance of those algorithms due to the uncertainty from the observed objective values. Model-based techniques have been adopted for de-noising. However, no characteristic of multi-objective optimization problems has been used in those model-based techniques. The regularity model is a dimension-reduced model for multi-objective optimization problems. Through studying the behavior of the regularity model on noisy multi-objective optimization problems, this paper argues that it is very efficient to solve noisy problems. Therefore, the regularity model can be embedded into existing algorithms for noise-free problems to improve their performance on noisy problems. Thus, without designing new algorithms, noisy problems can be solved. We embed the regularity model in an existing algorithm as an application for noisy problems. The proposed algorithm has a satisfactory performance in terms of both convergence and diversity. In our experiments, we have compared several state-of-the-art of algorithms with the proposed algorithm on benchmark problems with different levels of noises. The experimental results showed the effectiveness of the regularity model on noisy problems, but a degenerated performance on problems without any noises.