EMOEA/D―DE算法在卫星有效载荷配置中的应用

摘要：针对卫星有效载荷配置问题，提出了一种基于差分进化分解的改进多目标优化算法（EMOEA/DDE）的有效载荷配置模型。该模型将配置问题转化为以卫星数、卫星冗余度为目标的多目标优化问题（MOP），并采用EMOEA/DDE进行求解。此外，针对随机均匀初始化会导致种群在目标空间分布过于集中的问题，采用与优化目标相结合的随机初始化方法进行改进。实验结果表明，该模型所求解集的平均差异性在0.05以内，分布度值在0.9以上，具有较好的稳定性及分布性，且改进后的算法收敛速度提升近1倍，所求解的近似Pareto前沿相对更优。故该模型对有效载荷配置问题是一种有效的解决方法。

关键词：卫星有效载荷配置；多目标优化问题；MOEA/D；EMOEA/DDE；种群初始化

中图分类号： TP391.4

文献标志码：A

Abstract： To solve the satellite payload configuration problem， a satellite payload configuration model based on Enhanced MultiObjective Evolutionary Algorithm based on Decomposition with Differential Evolution （EMOEA/DDE） algorithm was proposed. This model turned the configuration problem into a Multiobjective Optimization Problem （MOP）， which took the number of satellites and satellite redundancy as the optimization objectives， and solved it by using EMOEA/DDE algorithm. Furthermore， to overcome the concentration of populations distribution in objective space resulted by the original randomly uniform initialization， a new random initialization combined with optimization objectives was introduced. The experimental results show that the solution set obtained by this model has good stability and distribution. The average difference is less than 0.05 and the distribution of value is above 0.9. Besides， the improved algorithm doubles the convergence speed nearly， and the approximation of Pareto front obtained is relatively better. So this model is an effective solution to solve the satellite payload configuration problem.

Key words： satellite payload configuration； Multiobjective Optimization Problem （MOP）； MultiObjective Evolutionary Algorithm based on Decomposition （MOEA/D）； Enhanced MOEA/D with Differential Evolution （EMOEA/DDE）； population initialization

0引言

卫星有效载荷配置是一类带有约束的组合优化问题。它是选择满足多功能要求和约束条件的有效载荷，并合理地组合配置在多颗卫星上，在最大限度地满足用户提出的性能指标的基础上，获得优化的产品配置方案，是卫星总体方案设计中的重要内容，因此，有效载荷配置至关重要[1]。

目前，对卫星有效载荷配置问题建模的方法主要有3种[2]：基于结构的方法、基于约束的方法和基于进化算法的方法。基于结构的方法对大规模配置设计问题，缺乏高效的求解策略；基于约束等产品配置方法仅仅构造出符合约束的配置，且当约束较少时，存在组合爆炸问题；而基于进化算法的配置设计是将配置问题抽象为带约束的组合优化问题，其能对用户提出的某一目标或多个目标进行产品配置优化设计。进化算法由于其对所求问题具有较强的全局寻优能力的优点，在求解各种优化问题中已取得了广泛的应用[3]，已成为有效载荷配置问题的主要研究方法。近些年来，基于分解的多目标优化算法（MultiObjective Evolutionary Algorithm based on Decomposition， MOEA/D）[4]因其具有较好的寻优能力和种群多样性保持能力，成为进化多目标优化算法的研究方向之一，取得一定的应用[5]。针对有效载荷配置的特点，本文通过建立配置模型，将基于分解的多目标算法引入，提出用EMOEA/DDE（Enhanced MOEA/D with Differential Evolution）[6]对有效载荷配置问题进行求解的方法。

1有效载荷配置模型

1.1配置模型

卫星任务的执行依赖于卫星有效载荷，不同任务执行所需载荷种类及数目均有所差异。由于卫星搭载能力有限，导致一些具有任务关系性的有效载荷分配在了多颗卫星上，增加了调度难度，所以有效载荷需要合理配置。通过合理配置使得卫星有效载荷在满足约束条件下，最大限度让同一颗卫星上的任务关联性最大（即卫星载荷冗余最少），不同卫星间任务差异最大化；同时总的卫星数应该达到最小，以节约成本。

有效载荷配置问题实质是带约束的组合优化问题。组合优化问题由变量集合、变量的值域、限制变量取值的约束集合以及目标函数集合组成。有效载荷配置建模的主要目的是描述其中变量集、值域集、约束集及目标函数集，将载荷配置问题转化为适用于进化算法求解的多目标优化问题。

此外，由图8可看出，当卫星分配数在7颗以上时，两者所求的冗余度几乎相等；但当卫星数在7颗以下时，相同卫星数时，两者所求的冗余度差异较大，改进的算法所求冗余度更小，结果相对更优。因而，改进的EMOEA/DDE算法比EMOEA/DDE算法更能靠近真实的Pareto前沿。

3.4实验结论

通过对比分析两种算法的实验结果，得到以下结论：

1）基于EMOEA/DDE的算法能较好地逼近Pareto前沿。对于实验的测试数据，有效载荷配置中极端的情况之一是一颗卫星分配一个任务，此时的冗余度最低为0。在所得实验结果中（见图8），出现坐标为（0，15）的解，因而算法所求近似Pareto Sets逼近程度高。

2）最终所得的解集在目标空间具有很好的分布性，几乎分布在一条曲线上。在卫星有效载荷配置中，所用的卫星数越少，卫星有效载荷的冗余度就越大；相反，有效载荷配置所需卫星数越多，卫星的冗余度就越低。对比图8两种算法最终测试结果的分布特点，可以发现，随着卫星的冗余度增加，卫星数越小；反之卫星数越多，冗余度快速减小。测试结果的分布性与理论分析相符合。

3）针对上述输入的任务和约束条件，表3的实验数据表明，在迭代次数足够大的情况下，多次试验，两种算法各自所求的结果变化不大，都具有较强的稳定性，且改进的EMOEA/DDE算法在目标空间得到的近似Pareto解集相对较优。

4）改进的EMOEA/DDE算法因初始种群在目标空间上分布上相对合理，故而相比原来的算法收敛速度更快，因而在相同数据规模的情况下，改进的EMOEA/DDE求解载荷配置问题具有优势。

4结语

本文围绕有效载荷配置问题，建立了有效载荷配置模型，并采用EMOEA/DDE算法进行求解。求解过程中，为避免初始种群分布过于集中的问题，对EMOEA/DDE算法的初始化作了改进。实验结果表明，改进后的算法种群的分布性较好，算法收敛速度加快，所求的解集相对较优。

本文对模型的构建比较精简，模型中考虑的约束因素也只有卫星搭载卫星数上限要求。在后续研究中，还需要充实模型，考虑更多实际的卫星约束条件，比如有效载荷的重量的约束，完善任务与载荷之间的依赖关系等，使得模型更加与实际相符合。

参考文献：

[1]CUI S. The status and role of satellite payloads [J]. Spacecraft Recovery and Remote Sensing 2003， 24（1）： 61-64.（崔绍春.卫星有效载荷的地位和作用[J].航天返回与遥感，2003，24（1）：61-64）.

[2]WANG Y. Satellite payloads configuration and layout design method [D]. Dalian： Dalian University of Technology， 2008.（王奕首.卫星有效载荷配置和布局设计方法[D].大连：大连理工大学，2008.）

[3]WANG Y， CAI Z X. Combining multiobjective optimization with differential evolution to solve constrained optimization problems [J]. IEEE Transactions on Evolutionary Computation， 2012， 16（1）： 117-134.

[4]ZHANG Q F， LI H. MOEA/D： a multiobjective evolutionary algorithm based on decomposition [J]. IEEE Transactions on Evolutionary Computation， 2007， 1（6）： 712-731.

[5]GONG M， JIAO L， YANG D， et al. Evolutionary multiobjective optimization algorithms [J]. Journal of Software， 2009， 20（2）： 271-289.（公茂果，焦李成，杨咚咚，等.进化多目标优化算法研究[J].软件学报，2009，20（2）：271-289）.

[6]LIU B， FERNANDEZ F V， ZHANG Q， et al. An enhanced MOEA/DDE and its application to multiobjective analog cell sizing [C]// Proceedings of the 2010 IEEE Congress on Evolutionary Computation. Piscataway： IEEE Press， 2010： 1-7.

[7]DEB K， AGRAWAL R. Simulated binary crossover for continuous search space [J]. Complex Systems， 1995， 9（1）： 115-148.

[8]ZITZLER E， THIELE L. Multiobjective evolutionary algorithms： a comparative case study and the strength Pareto approach [J]. IEEE Transactions on Evolutionary Computation， 1999， 3（4）： 257-271.

[9]DEB K， SINHA A， KUKKONEN S. Multiobjective test problems， linkages， and evolutionary methodologies [C]// GECCO06： Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. New York： ACM Press， 2006： 1141-1148.

[10]DEB K. Multiobjective genetic algorithms： problem difficulties and construction of test problems [J]. Evolutionary Computation， 1999， 7（3）： 205-230.

[11]STORN R， PRICE K. Differential evolution a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization， 1997， 11（4）： 341-359

[12]LI H， ZHANG Q F. Multiobjective optimization problems with complicated Pareto sets， MOEA/D and NSGAⅡ [J]. IEEE Transactions on Evolutionary Computation， 2008， 13（2）： 284-302.

[13]DAS S， KONAR A， CHAKRABORTY U. Two improved differential evolution schemes for faster global search [C]// GECCO05： Proceedings of the 2005 Conference on Genetic and Evolutionary Computation. New York： ACM Press， 2005： 991-998.

[14]COELLO C C， LAMONT G， WELDHUIZEN D. Evolutionary algorithms for solving multiobjective problems [M]. 2nd ed. Berlin： Springer， 2007.

[15]ZHENG J. Multiobjective evolutionary algorithm and their application [M]. Beijing： Science Press， 2007： 65-69.（郑金华.多目标进化算法及其应用[M].北京：科学出版社，2007：65-69）.