Multiobjective Optimization Evolutionary Algorithms Based On Delaunay Triangulation Neighborhood

Optimization problems are usually ultimate and key procedure to be done before some problem is eventually solved. So they are of great frequency and importance. Recently, with the increasing development of science technology and engineering application, many problems can be modelled as optimization problems which can be divided into single optimization problems and multiobjective optimization problems according to the number of optimization problems. More and more problems in the real world are modelled as the multiobjective optimization problems as they are complicated to be solved. This is also one major reason why multiobjective optimization problems are getting more and more attention by researchers all over the world. Solving the multiobjective optimization problems are of great importance. But many multiobjective optimization problems are complicated and nonlinear, without some mathematical properties. So in terms of all of the properties, traditional methods cannot solve these problems well. Currently, multiobjective optimization evolutionary algorithm(MOEA) is one kind of effective method to solve the multiobjective optimization problems. Performance metric of MOEA commonly includes two meanings: 1.the extent of approximation from the solution set obtained by the optimization algorithm to the real optima solution set of one problem. 2. the uniformity and spread of the solution set obtained by the optimization algorithm. Representatively, nondominated sorting genetic algorithm II(NSGA-II) and multi-objective evolutionary algorithm based on decomposition(MOEA/D) are currently mostly used and studied EA frameworks. The former is on behalf of one kind of EA based on nondominated sorting and the latter is on behalf of one based on decomposition. Both two kinds of MOEA use the density metric to keep the diversity of the solution set. NSGA-II defines the crowding distance and traditional Euclidian distance is used in the MOEA/D. Both two kinds of distance metric considers the value of distance between two points only. But in 3D space or more general dimension, both neighborhood and distance need to be taken into consideration. So triangulation is introduced in this thesis to combine the neighborhood-based ideology and distance-based ideology, which is aimed at enhancing the uniformity. According to the experimental result data, the newly introduced method in this thesis works well in keeping the diversity of the solution set. Main works in the thesis are listed as two: 1. Newly proposed improvement methods embedded in NSGA-II. The core of NSGA-II based on nondominated sorting lies in the construction of the partial order to individuals of the evolutionary population. First of all, the population is sorted according to nondomination and divided into several nondominated fronts. The algorithm chooses the individuals in the order of their ranking of different nondominated levels until no more fronts can be accommodated into the population. Then, the crowding distances of individuals of the current front are calculated. And the algorithm chooses the best individuals based on the crowding distance in descending order to fill all left population slots. According to the partial order, nondominated sorting aims at improving convergence while crowding distance targets to enhancing uniformity. In this thesis, more accurate distance with triangulation is used when calculating the crowding distance in NSGA-II. 2. Newly proposed improvement methods embedded in MOEA/D. According to the analysis of the relationship between the weight vectors and the optimal solutions, the corresponding weight vector of a solution in the objective space can be calculated. So we can adjust the position of individuals in the objective space to make individuals spread the Pareto front more uniformly. When measuring the distance among individuals, also triangulation is used to obtain more accurate metric. Then diversity of the algorithm is improved when adding an individual into the sparse region and removing one from the crowding region in objective space.