The Research On Hypervolume Indicator And Its Application In Multi-objective Evolutionary Algorithm

Multi-objective optimization is the principle research area in optimization method. Most real-world problems have many conflicting objectives. Different from the single objective optimization problems which have the only optimum solution, the optimum solutions of multi-objective optimization problems are a group of trade-off solutions, namely Pareto optimum solutions set. Multi-objective evolutionary algorithm is a kind of random search algorithm which simulates the nature selection and evolution. It specializes in solving highly sophisticated and nonlinear multi-objective optimization problems. It attracts so many attentions from researchers that develop rapidly. From a single run, multi-objective evolutionary algorithm could obtain a set of non-dominated solutions which are used to be measured and selected by decision maker. Therefore, how to evaluate and measure the solutions obtained by multi-objective evolutionary algorithm, and how to obtain high quality solutions are main research area in multi-objective evolutionary algorithm.This research work focuses on the computation of hypervolume indicator and its application in multi-objective evolutionary algorithm. The contribution of this work contains the following two folds:First, hypervolume indicator is a comprehensive metric which is used to evaluate the quality of the solutions set. That is to say, hypervolume indicator could evaluate the convergence, diversity and spread of the solutions set simultaneously, and give the evaluation result. Therefore, it obtains more and more attentions from researchers in recent years. However, the time cost for computing the hypervolume indicator is relatively high, which greatly hampers the development of its further application. For this purpose, we develop a mapping based algorithm for calculating hypervolume indicator by slicing objective (denoted as MHSO). The points in high dimensional space are recursively mapped into fewer dimensions and the iteration would not stop until there are only three objectives left. In three-dimensional case, a heuristic method is incorporated to extract efficient points from the whole set, which are used to calculate the hypervolume value on the plane of projection. Experimental results demonstrate that our method is more efficient.Second, tree neighbor containing relation is defined in order to descript the close degree of individuals. We propose a metric which is used to evaluate the density of the individual. Based on the Pareto dominance relationship, the density metric is combined to assign the fitness value. Utilizing a slicing based method, a novel algorithm to calculate the exclusive hypervolume indicator in two and three dimensional cases is proposed. Besides, the exclusive hypervolume indicator is used to guide the maintenance of the external population. Based on all of these, an Adaptive Neighbor Multi-objective Evolutionary Algorithm based on Hypervolume Indicator (ANMOEA/HI) is proposed. Experimental results demonstrate that the proposed algorithm obtains good performance in both convergence and distribution, especially on the complicated MOPs.