Research On Hypervolume Based Evolutionary Multi-objective Optimization Algorithms

There are many optimization problems in reality,especially multi-objective optimization problems.In the field of scientific research and engineering,there are more than one optimization problem that people often need to consider,but two or more.The optimization objectives of these problems are often conflicting,that is,the optimization of one of the targets will inevitably lead to the deterioration of other targets,and there is no single solution that optimizes the search target at the same time.Therefore,the traditional methods in operational research are difficult to solve these problems independently.The evolutionary algorithm is different from the traditional method.The characteristics of its population search have obvious advantages to solving the multi-objective optimization problem,and the importance of its status is increasing.In this paper,through the in-depth study and exploration of the multi-objective evolutionary algorithm,some improved ideas and schemes for the existing multi-objective evolutionary algorithms are proposed.The target is a class of multi-objective evolutionary algorithms based on the hyper-volume index and some other algorithms based on the index.Specifically,the main contents and innovative research include the following aspects.1)a fast approximation algorithm for super volume(hypervolume).The difficulty of computing the hyper volume in high dimension is an urgent problem to be solved in the field of multi-objective evolution algorithm based on hypervolume index.This problem has always hindered the further development and application of this field.On the other hand,the accurate measurement of the super volume has been proved to be a NP hard problem.It can only be completed in exponential time,unless NP=P.Therefore,at present,people tend to search for a super volume approximate substitution value instead of the exact value.Based on this,a fast and approximate super volume method is proposed in this paper.A characteristic of the method is partial accurate calculation and partial approximate calculation,the precision is improved by accurate calculation,and the calculation speed is improved by the approximate calculation,which achieve the purpose of improving them simultaneously.First,we propose a new method for segmenting hypercube,which decomposes a hypervolume problem into several sub problems,namely sub hypervolume.In these sub problems,a part of the volume is easy to calculate,and the other is difficult to calculate.Then we calculate the part of the calculation accurately,approximate the difficult part,and finally merge the result,that is,we can estimate an approximate solution of the original problem.In this paper,we have compared with other methods of calculating the volume,such as QHV and FPRAS algorithm.Experiments show that our algorithm performs at least 10 times faster than the above algorithm under the same accuracy.2)based on the above algorithm,we propose a multi-objective evolutionary algorithm based on hypervolume index,which uses the hypervolume index of approximate calculation to guide the evolution direction of the population.Because the multi-objective evolutionary algorithm based on hypervolume index is widely considered to be very effective on solving the problem of super multi objective optimization,it is very important to design a multi-objective evolutionary algorithm based on hypervolume index in high dimension.However,this kind of algorithm often needs to calculate a large number of hypervolume measurements in one iteration,which makes the complexity of the algorithm very high,and the current computer is not able to load.In order to solve this problem,the above calculation method is integrated into the SMS-EMOA framework,and the SMS-PPPA algorithm is proposed,which uses the approximate calculated values to find the smallest contribution in the population,not only the ordinary computer can load,but also the running time is not long.Through experiments,the algorithm still can keep running time within 5 seconds in the 15 dimension objective space,far less than other similar algorithms,such as SMS-IWFG.Most of the calculation examples can outperform other algorithms including NSGA-III,and a few examples have similar performance.Finally,we propose a method of solving the n-order approximation of the hypervolume measurement value by integration method.This method can prove that the calculated value is a n-order approximation value of the hypervolume measurement value,and the calculation time is completed in the n-time polynomial time.