Research On Manifold Learning Algorithm For High-Dimensional Multi-Objective Optimization Problems

The Multi-Objective Problems(MOPs) is a kind of problem frequently encountered in scientific reseach and engineering. MOPs contains multiple conflicting sub-goals, for finding out design optimal to meet all objectives, it is necessary to solve conflict between multi-objective and multi-constraint, namely multi-objective optimization problem. MOPs has wide range of applications, such as:engineering optimization and design, operational research, biomedical,data mining. In theoretical research and engineering applications, there is such a kind of MOPs:high data dimension of the decision space and non-linear distribution of data points, that is called high dimensional multiobjective optimization problems which will be focused in the paper (High-Dimensional Multi-Objective Optimization Problems).Traditional Evolutionary Multi-objective Optimization Algorithms(EMOAs) and Model-based Multi-objective Optimization Algorithms(MOEAs) are two method for solving MOPs, but each has its advantages and disadvantages:(1) For a class of continuous MOPs, it distribution of Pareto Set (PS) is a sectionally continuous (m-l)-dimentional manifold(among m is the number of object), which does not be taken advantage by the traditional EMOAs;On the other hand, in the traditional EMOAs,when the population is close to convergence, blind crossover and mutation operations would make converged populations deviate from the actual Pareto set (Pareto Set, PS);(2) Based on the disadvantages of the traditional EMOAs, Model-based Multi-objective Optimization Algorithms(MOEAs) have been put forward by scholars, MOEAs apply statistical learning methods to establish distribution model of decision space, and then breed offspring from the model,such repeated, thus achieve population convergence, but inadequate of MOEAs is as following:modeling method of MOEAs is linear method, such as Local PC A, PC A, but for for high-dimensional nonlinear data, linear modeling procedure is complex and model is inaccurate.Manifold learning algorithm can mining the overall geometry and topology contain in the high-dimensional nonlinear data set, that is to say:Manifold learning algorithm can find out the low-dimensional smooth manifold structure embedded in high-dimensional data space.So,in this paper, the manifold learning algorithm is introduced into Multi-Objective Optimization Algorithms for high-dimensional MOPs, propose a new type of optimization algorithm called Multi-Objective Evolutionary Algorithm via Manifold Learning to overcome algorithm deficiency of the traditional EMOAs and MOEAs, use manifold learning algorithm reduce dimension of data and mining manifold in the decision space of MOPs, build accurate model, guide algorithm evolution and accelerate convergence. Main works of the paper is devided into five levels:(1)In consideration of shortcomings of the traditional EMOAs and MOEAs, Multi-Objective Evolutionary Algorithm via Manifold Learning is purposed, which can mining manifold in decision space of high-dimensional MOPs.And a universal optimization algorithm framework via manifold learning for MOPs is purposed, which will facilitate subsequent study of the paper.(2) For reasonable evaluation algorithm performance, in this paper, based on comprehensive analysis the geometrical shape of dicision space and objective space of frequently-used MOPs test function and measure metric is selected for algorithm evaluation.(3) Purposed two categories Multi-Objective Optimization Algorithm via Manifold Learning:Multi-Objective Evolutionary Algorithm via Self-Organizing Maps (SOM-MOEA) and Multi-Objective Evolutionary Algorithm via Locally Linear Embedding (LLE-MOEA).①Analysis algorithm characteristics of SOM, based on the disadvantage of RM-MEDA(A Regularity Model-based Multiobjective Estimation of Distribution Algorithm):building linear model via Local PCA(principal component analysis) in RM-MEDA, this paper purposed SOM-MOEA, through neurons of SOM, learn manifold structure of population, then reproduce individuals via expanding SOM neurons by random noise vector, in order to establish manifold structure of problem’s decision space and guide algorithm evolution.②SOM-MOEA and RM-MEDA, respectively, reproduce individuals via SOM neurons and Clustering of principal components by random noise vector, their common deficiencies is:procedure of the expansion is blind and it may destroy established model of population.So LLE-MOEA is purposed, contrast SOM-MOEA and RM-MEDA, the biggest improvement of LLE-MOEA is that:LLE-MOEA can not use the "expansion" strategy, but directly mining intrinsic manifold of problems’ decision space, and directly reproduce individuals of next population from data points on that of "manifold", no "expansion" and build non-linear model.Based on improved algorithm of LLE,SLLE-MOEA(Multi-Objective Evolutionary Algorithm Based on Supervised Locally Linear Embedding) and HLLE-MOEA(Multi-Objective Evol-utionary Algorithm Based on Hessian Locally Linear Embedding) is put forward.In all, there are four Multi-Objective Evolutionary Algorithms via Manifold Learning:SOM-MOEA,LLE-MOEA,SLLE-MOEA and HLLE-MOEA.(4)In the paper three types of MOPs is selected for algorithm test:variable-independent, variable linear-correlation and variable nonlinear-correlation, the experimental results are as follows:①When LLE, SLLE or HLLE is used for dimensionality reduction alone, which algorithm performance largely influenced by neighborhood parameter k, but when LLE, SLLE or HLLE is used for Multi-Objective Evolutionary Algorithm via Manifold Learning, which algorithm performance is less influenced by neighborhood parameter k,in this paper the optimal k=2through experiment, the bigger k will increase calculated amount and destroy manifold structure,further experiments shows:LLE-MOEA is fit for solving variable-independent MOPs.②Algorithm performance of SLLE-MOEA show sensitivity influence by category parameter a of SLLE,if change a blindly, manifold of population will be destroyed.So SLLE-MOEA is fit for solving variable linear-correlation MOPs.③For variable nonlinear-correlation MOPs, SOM-MOEA is superior to LLE-MOEA, because diversity of population is increased by the strategy of expanding SOM neurons.④In all,algorithm performance of SOM-MOEA and LLE-MOEA is superior to that of RM-MEDA and NSGA-II.(5)Solve satellite constellation design problem by Multi-Objective Evolutionary Algorithm via Manifold Learning. Satellite constellation optimization is one class of very complex problem, its optimization results are relate to a variety of optimization indicators which functions are computational complexity and even have no analytical expression.So satellite constellation optimization design is a kind of typical high-dimensional MOPs,therefore Multi-Objective Evolutionary Algorithm via Manifold Learning is suited to solve.Compare with geometry analysis method and simulation method, the method of manifold learning has obvious advantages:Multi-Objective Evolutionary Algorithm via Manifold Learning can expand searching space of satellite constellation design problem, then uniform or asymmetric constellation configuration can be worked out rapidly by the algorithm.By SOM-MOEA and LLE-MOEA,solve regional coverage satellite constellation design problem, experiment shows: manifold learning algorithm indeed can reduce dimensionality of data set in engineering optimization problems’ decision space and mining manifold structure, accelerate convergence of optimization algoritm.In conclusion, for overcoming algorithm deficiency of the traditional EMOAs and MOEAs, this paper purposed a new type of optimization algorithm called Multi-Objective Evolutionary Algorithm via Manifold Learning, through mining manifold structure embedding in decision space of high-dimensional MOPs by the manifold learning algorithm and reproducing individulas of next population, build accurate model of decision space, guide algorithm evolution and accelerate convergence.Experiment on standard test functions and satellite constellation design problems shows it is effective and efficient that solving high-dimentional engneering MOPs using Multi-Objective Evolutionary Algorithm via Manifold Learning. The research results of this paper will not only enrich theory of the Multi-Objective Optimization Algorithms, but also purpose new research approach for application of Multi-Objective Optimization Algorithms.