Model-Based Multi-Objective Constellation Optimization Algorithm Design

Many optimization problems, in scientific research economy areas and engineering areas, belong to multi-objective optimization problems. The optimal solution of multi-objective problem is a set of solutions. As multi-objective evolutionary algorithms can get many feasible solutions, multi-objective evolutionary algorithms become hot spots and achieved many good results in multi-objective area gradually in recent decades.The constellation composed of multi-satellites that worked synergically to satisfy the regional coverage demand required by specifically spatial mission. Satellites play a more and more important role in many fields such as communication, navigation and surveillance, weather forecast, geological prospecting by right of their unique spatial position advantage. It is a key issue for constellation optimization to design efficient and feasible constellation layout. Constellation optimization relating to multi-aim points and multi-optimized index is a complex multi-dimensional, dynamic, multi-objective problem. Since it is not high efficiency to get solutions and is not strong convergence and doesn't utilize distributing regulation of Pareto set for conventional evolvement algorithms, with the development of research and application, the complexity of resolution bring forward new challenge for performance of algorithm.Estimation of distribution algorithms (EDAs) were introduced to the field of multi-objective optimization by Thierens, Bosman and etc in 2001. EDAs use the important speciality that the Pareto sets'distributing of certain continuous multi-objective optimization problems present definite regulation, and reach good solutions on the high dimensional multi-objective optimization problem.EDAs don't use crossover or mutation opteration like conventional evolvement algorithms but extract globally statistical information from the selected solutions and build probability distribution models of promising solutions based on this extracted information. New solutions are sampled from the models thus built. Qingfu Zhang etc. have developed a regularity model-based multi-objective estimation of distribution (RM-MEDA) in 2007 which captures and utilizes the regularity of the Pareto set in the decision space. Systematic experiments show that, overall RM-MEDA outperforms GDE2, PCX-NSGA-Ⅱand MIDEA, on a set of test instances with variable linkages. However, RM-MEDA has its drawbacks and shortcomings. Clustering and building probability distribution models of algorithm based on model are more complex and cost much time. Adopt probability distribution models to produce new individuals at early of algorithm on some test problems usually make the search direction far away from objective direction. For example, the regularity model-based multi-objective estimation of distribution (RM-MEDA) is not convergence on ZDT4, ZDT6, DTLZ1and DTLZ3, which make algorithm not stability on some degree.This paper first presents the research background, significance and actuality in and out of problem, discussing multi-objective optimization problem and analyzing advantage and shortcoming of conventional evolvement algorithms and estimation of distribution algorithms. Study of model based algorithm is emphasized and two kinds of multi-objective optimization problem are brought in and expatiated. The manifold of PF and PS for the firs kind of multi-objective problem are all (m-1)-D, while the The manifold of PF for the second kind of multi-objective problem is (m-1)-D and the dimension of its PS is higher than (m-1)-D.Then we improve and design model based algorithm for the two kinds of algorithm including:1) strategy of manifold initialization population, construct a upotian Pareto front(UPF) and choose N(size of population) individuals that are closestt to UPF from current samples as initialized samples. This strategy make the individuals of population trying their best to approach Pareto front uniformly; 2) revise parameter of convergence criterion in the first kind of optimization problem based on anterior work that producing individuals in the way of GA+EDA, which enhance the proportion of using EDA to produce individuals in the precondition of keeping even improving quality of solutions; 3) make sure of latent dimension and design convergence criterion for the second kind optimization problem, when the latent dimension of K clusters in population are not far away from each other we decide the distribution of population present certain regulation, and this time we can use EDA to creat the next generation.In addition, we construct three new test functions ZDT2.3, DTLZ2.3 and DTLZ2.4 with more complex PS(multimodal curve or multimodal curved surface) and supply IGD measurement based on convergence measurement and diversity measurement. The IGD measurement evaluates convergence and distributing uniformity at the same time which renew performance evaluate of three-objective problem.We compare improvement algorithm m-RM-MEDA with NSGA-Ⅱ,NSGA-Ⅱwith manifold initialization(m-NSGA-Ⅱ),RM-MEDA and IORM-MEDA. After analyzing the result we found that the advantage of model-based algorithm will be weaken when the complexity of problems' regulation is low while the advantage of m-NSGA-Ⅱis prominence. However when the distribution regulation of PS of problems become more complex, the model-based algorithm appear advantage gradually, at the same time the convergence of NSGA-Ⅱand m-NSGA-Ⅱare down and the their diversity are off form. As the PS of problems become more complex, use EDA to creat the next generation at early make against search in all solutions space for algorithm. But it is aslo bad if we just use GA to creat child generation. So it is a good choice to merge GA and EDA to produce child. The experimental results aslo show that m-RM-MEDA is efficient on convergence and distributing uniformity.The fifth chapter use m-RM-MEDA to resolve low earth orbit (LEO) constellation optimization problem and compared with m-NSGA-Ⅱ,RM-MEDA and IORM-MEDA. The experiment results show that the convergence percentage of our improved algorithm is better than other algorithms, and can better meet the regional durative coverage demand, providing a useful reference for decision maker dealing with constellation optimization.