Research On Evolutionary Multiobjective Algorithms

Many optimization problems in the real world are composed of several conflict objectives. Its optimal solution is not one but a set of solutions, and they are called the Pareto Optimal Set. As population-based global search methods, Evolutionary Algorithms (EAs) are very promising to solve the multiobjective optimization problems (MOPs). Since the mid 1980s, EAs have been applied to solve MOPs. Recently many Evolutionary Multioptimization Algorithms have been proposed, and some of them have been successfully applied in engineering. Therefore, the research of evolutionary multiobjective optimization (EMO) has become a hot research field in Evolutionary Computation community. The Multiobjective 0/1 Knapsack Problem (MOKP) is one of the most traditional combinatorial problems. It is important for theoretic research and engineering applications, and is often used to test the performance of EMOs.The aim of this dissertation is to explore the theories and mechanisms of EMOs and to design effective strategies for MOKP, and to do the corresponding theoretic and experimental analyses. The main research works in this dissertation consist of the following aspects.(1) For Multiobjective 0/1 knapsack problem, two novel weighted repair strategies are proposed. Since Zitzler proposed SPEA, EMO has been widely used to solve MOKP. The capacity constraints must be satisfied in MOKP but infeasible solutions will come into being when MOKP is solved by EAs. One of the most useful methods is repair strategy which can change infeasible solutions to feasible ones. However, the most widely used repair strategy which is based on maximum profit/weight ratio can not involve the different impacts of each item on all knapsacks. In this paper, two novel repair strategies are proposed, which are based on knapsack capacities and constraint violations respectively. These two novel strategies are applied in SPEA2 to solve MOKP. The experimental results show that SPEA2 with the novel repair strategies not only have much better convergence to the Pareto-optimal front but also better distribution on the test cases with two to four objectives. Meanwhile, the performance of SPEA2 with the novel repair strategies is significantly improved.(2) For Multiobjective optimization problem, several novel density estimation strategies are proposed which are based hybrid Minkowski distances and weighted scalar sub objective values. The aim of multiobjective optimization is to find a solution set which has good convergence and distribution. Good convergence means the distance from the solution set to the Pareto optimal front is as small as possible and good distribution means the solutions are as uniform as possible. Now the design of multiobjective optimization evolutionary algorithms is to satisfy these two conditions. Pareto domination guarantees good convergence and density estimation guarantees good distribution in EMO. However, these two strategies associate and influence each other. If the number of non-dominated solutions exceeds the size of archive set, some solutions will be deleted according to the density. The solutions with the same pareto domination will be judged by their density in the genetic selection. So the density estimation strategy is very important in EMO but the scalability of currently used strategies are not good when the number of objectives becomes more than four. In this paper, the different impacts of each sub objective are much more generally considered and several novel density estimation strategies are proposed which are based Minkowski distance and weighted scalar sub objective values. The experimental results on MOKP cases with four to nine objectives show that EMO with new density estimation strategies have better convergence to the Pareto optimal front. Then they are combined with the novel repair strategies and the performance of the algorithm is obviously enhanced. Moreover, a novel hybrid density estimation strategy is proposed which is combined by Euclid distance and random distance. The experimental results also show its validity.(3) For evolutionary multiobjective algorithm, several novel selection strategies are proposed. Genetic selection is an important step in EMO. Parent individuals are mostly selected from the archive set and the selection is usually based on competition, e.g. tournament selection. The criterion of winner depends on its fitness value which is determined by pareto relation and individual information, e.g. density function. When the objective number becomes larger, the number of non-dominated solutions will increase quickly and most of the solutions in the archive set are non-dominated. So which one will be chosen as parent just depends on density information and it is not reasonable to mainly consider its distribution. In this paper, several novel selection strategies are proposed by adopting comparison of each sub objective for two individuals. The experimental results on MOKP test cases with four to nine objectives demonstrate that the convergence of the algorithm is greatly improved by novel selection strategies. Then they are combined with the novel repair strategies to SPEA2 and the convergence of the algorithm becomes much better and the distribution is not worse.In this dissertation, with the studies in evolutionary multiobjective optimization and multiobjective 0/1 knapsack problem, two novel repair strategies are designed for MOKP, several novel density estimation strategies and several novel genetic selection strategies are proposed for Evolutionary Multiobjective Optimization. The works in this dissertation are very important not only to the research of the multiobjective optimization evolutionary algorithms but also to the optimization applications of EMOs in the real world.