一种改进的微分进化算法及其在多目标访问任务中的应用

姚 玮，罗建军，马卫华，袁建平

(1.西北工业大学航天学院，西安710072；2. 航天飞行动力学技术重点实验室，西安710072)

一种改进的微分进化算法及其在多目标访问任务中的应用

姚 玮1,2，罗建军1,2，马卫华1,2，袁建平1,2

(1.西北工业大学航天学院，西安710072；2. 航天飞行动力学技术重点实验室，西安710072)

研究在给定时空约束下利用单平台机动实现地面多目标重访任务问题的建模与求解。首先在问题描述和建模过程中考虑多约束与性能指标要求，大大缩减优化算法的参数搜索空间，提高求解效率；然后针对传统微分进化算法的不足，提出一种改进的微分进化算法，并将其应用于求解多约束多目标重访优化问题。改进的微分进化算法通过引入双重自适应因子和独立变异体，提高了算法的优化效率并使其在陷入局部最优后仍具有一定的跳出局部最优的能力。仿真中改进的算法在打靶仿真均值，最优结果和均方差方面都远优于传统算法，验证了本文设计的建模方法和改进优化算法的正确性和有效性。

机动轨道设计; 自适应微分进化; 多约束; 多目标访问

0 引 言

以对地观测、遥感和目标侦查等任务目标作为实际需求的对地访问任务一直以来都是航天领域的核心问题之一。其中，多目标覆盖与重访又是一个相对复杂的任务，最为普遍的星座组网任务模式存在系统复杂、代价高昂、维护困难的弊端，因此通过单平台机动的方式实现对地多目标重访任务具有十分重要的应用前景。对地多目标重访任务和问题的解决离不开优化，近些年，随着智能优化算法的快速发展，遗传算法[1-3]，粒子群算法[4-7]和微分进化算法[8-16]等脱颖而出，但遗传算法存在计算量大，效率低等缺点，而粒子群算法极易陷入局部最优，并存在对离散问题处理能力欠缺的局限性。微分进化算法于1995年由Storn和Price[9-10]提出，由于原理简单、易于实现、计算效率高等优点被广泛地用于解决轨道优化[8,13-14]，星座设计[12]，机动优化[15]，多目标分配[11]和参数辨识[16]等问题，当然它也存在智能优化算法所共有的易陷入局部最优的问题。

为了有效地进行电离层扰动机理与效应研究，观察和记录气辉效应，通常在不同纬度带选取适当地点进行空间环境观测与诊断。国内相关单位与欧洲EISCAT国际组织有着长期的合作，利用特洛姆瑟等地基非相干散射雷达等手段开展空间环境观测研究，同时国内在昆明建有电波环境综合观测试验基地，海南有探空火箭发射场等便利条件，因此选择挪威、昆明和海口三地作为在轨试验观察诊断区域，充分发挥了国际合作和国内优势，并以此构建天地联合试验观测诊断体系，支撑空间环境科学研究。

本文针对单平台机动实现地面多目标重访任务，在建模方面采用将约束指标直接作用于建模过程的处理方式，大大缩减优化算法的参数搜索空间，提高优化效率和性能；在优化算法方面，通过引入双重自适应进化因子和添加自由变异因子实现了对传统微分进化算法的改进，显著提升算法的智能性和高效性，且在一定程度上改善了算法陷入局部最优的问题。最后的算例仿真表明改进的算法在优化结果和稳定性方面都具有明显的优势。

1 问题描述

电离层扰动效应的夜晚观测效果好于白天，因此需要通过相应轨道设计创造夜晚飞经三地的机会，同时为提高试验效率，还需要通过轨道机动策略优化设计实现较短时间内完成以上三地的观测试验。选取两天为总任务时间，对三个目标点尽可能多地执行多次重访任务。

三个目标点具体的经纬度信息如下：

A.高纬目标点(挪威)参数(69.59°N, 19.23°E);

B.中纬目标点(昆明)参数(25.6°N, 103.8°E);

C.低纬目标点(海口)参数(20.0°N, 110.34°E)。

整个覆盖和重访任务必须满足以下指标：

1)初始轨道为300 km的太阳同步轨道;

2)累计速度脉冲约束不超过1000 m/s;

3)仰角80°的仰视锥角内为空间经过依据;

4)访问当地地方时在21:00至次日05:00之间;

5)在访问次数最多的基础上，尽量降低燃耗。

本文针对上述任务和要求，建立了多约束多目标重访任务的模型，并采用微分进化算法进行优化求解。问题描述和建模求解过程如图1所示。

图1 问题描述和建模求解流程图Fig.1 The flow chart of problem formulation and solution

2 模型建立

解决多目标快速机动连续访问问题，在优化之前，数学建模必不可少，本文通过先不考虑任务约束，将问题简化，再逐步引入约束进行拓展的思路完成对整个搜索空间的建模，主要包含反解任务星轨道要素(仅考虑访问约束)，拓展为任务星群(引入传感器覆盖仰角约束)，拓展为任务星群带(引入轨道面调整约束)，拓展为任务星群网(引入任务时间不确定性约束)四个阶段。

2.1反解任务星轨道要素

通过目标点的经、纬度信息和轨道倾角，根据星下点轨迹、经度线与赤道构成的球面三角形几何关系如图2所示，利用下式

(1)

可以求得访问目标点的任务星在访问时刻升交点经度Ω和真近点角f的信息，其中φ，φ，i分别代表目标点经度、纬度和轨道倾角。

图2 星下点轨迹几何关系示意图Fig.2 Geometry of ground track

2.2任务星群拓展

考虑到地面目标点传感器的覆盖仰角，通过分析，可将单颗任务星考虑探测范围后拓展为一个圆构型的任务星群，则只要卫星的当前t时刻升交点经度和真近点角在允许可变范围内均可视为能够实现访问任务，分析过程如图3所示。星群地心角θ2，升交点赤经沿拓量Δl和真近点角沿拓量Δf如式(2)～(4)所示，其中a代表轨道半长轴，d代表传感器敏感半径，ΔΩ代表升交点赤经变化范围。

(2)

(3)

(4)

图3 任务星群拓展分析过程示意图Fig.3 The process of expanding to a feasible region

2.3任务星群带拓展

由于平台具有一定的机动能力，根据燃料约束可求得根据初始轨道倾角在考虑最大机动能力后对应的可行轨道倾角范围，如图4所示。分析可得最大和最小轨道倾角imax，imin如式(5)、(6)所示。

imax=arccos(-cosicosΔi+sinisinΔicosft)

(5)

imin=arccos(cosπ cosΔi+sinisinΔicosft)

(6)

图4 任务星群带拓展分析示意图Fig.4 The process of expanding to feasible strip area

2.4任务星群网拓展

在该任务中，目标点的访问时间在规定时间段内是一个可变参数，因此考虑任务时间t变化时，可将任务星群带拓展为任务星群网，事实上是给升交点赤经和真近点角分别添加一个与时间和地球自转角速度ωe或轨道角速度ωo相关的漂移量，如下所示：

(7)

到此，整个建模过程完成，如式(8)所示，根据三个目标点的经纬度确定的由任务时间、任务轨道倾角、任务星升交点赤经、真近点角构成的三个四维矩阵就可作为优化算法的参数搜索空间，该搜索空间已经将约束合理引入，大大缩减了搜索空间的维度，可大幅提升求解效率。后续的优化过程只需通过合适的优化算法在该参数搜索空间内寻找到目标函数值(燃料消耗)最小的参数组即可，本文的优化目标函数为累计速度脉冲IV。

(8)

2.5建模过程仿真校验

为了校验上述建模过程的正确性和可靠性，同时对建模过程进行更加形象的演示，本文将Matlab数值仿真结果与STK场景仿真结果进行对比分析，可以看出最终STK场景仿真结果与Matlab数值仿真结果完全一致，证明了整个建模过程的可靠性和有效性。图5(a)～(d)依次为单颗任务星示意图、任务星群带示意图、任务时间间隔为1 h的任务星群网示意图和STK场景仿真示意图。

图5 建模过程仿真校验效果图Fig.5 Verification of modeling process in STK

3 改进的微分进化算法

3.1传统微分进化算法

当定义优化问题变量数为N，种群个体数为n，进化总代数为K，i表示变量编号，j表示个体编号，g表示当前进化代数编号时，微分进化过程可表示如下[8,10]：

1)随机初始种群生成：

(9)

2)通过变异操作生成突变体：

一般有两种突变体生成方式：

(1)以上一代最优个体作为突变体基准值

(10)

(2)以上一代随机个体作为突变体基准值

(11)

其中随机数进化因子：

Fi,j=rand(0,1)

(12)

3)交叉操作确定突变体是否作为备选体：

Ui,j(g)=

(13)

其中随机数进化因子：

FCRi(g)=rand(0,1)

(14)

4)选择操作，通过指标函数比较选取合适的新一代个体：

(15)

5)重复2)～4)过程反复迭代，直到指标函数满足要求或达到迭代次数上限。

3.2双重自适应进化因子设计

(16)

其中，与上一代指标函数相关的进化因子表述为

(17)

与迭代步数相关的进化因子表达式为

Fi,j(g)=(0.1～1)

虽然很多初中地理教师在进行具体教学的过程中，能够意识到不同学生在智力以及知识接受能力上会有所不同，但却依旧使用最为传统的应试教育方法进行初中地理科目的教学，不能充分认识到针对学生特点应用差异教学方法所发挥的重要作用。同时，在具体教学过程中灵活应用差异教学，需要教师全面了解班级每一位学生的特点，以及学生在地理科目学习中存在的问题，同时还要结合班级的实际情况，将差异教学的理论落实成为教学的有效策略，这些工作对于习惯了应用传统方法进行教学的教师来说难度较大，并不能在短时间内高质量高效率地完成。

(18)

同时，考虑到交叉过程中的交叉几率因子FCRi(g)决定了突变体和本体对新一代个体贡献与否，因此本文也将FCRi(g)设计成与进化代数和指标函数相关的自适应函数，具体形式为：

(19)

(20)

(21)

3.3变异因子设计

在以上自适应性改进之后，通过对算法进行仿真分析，发现算法进行过程中仍会陷入局部最优而无法跳出，导致最终优化结果并不理想。因此，本文通过在每一步进化过程中都将最后一个个体设置为独立变异因子，其不随整个群体进行有向的进化，而是自身进行随机变异，当算法陷入局部最优之后，一旦该变异因子的指标函数优于局部最优值，整个优化过程会立刻跳出局部最优，重新在该变异因子附近进行新的进化过程，变异因子的设置如下所示：

(22)

4 仿真分析

本节将采用传统微分进化算法和改进后的算法分别对本文所关注的多目标机动访问问题进行优化，利用打靶仿真对改进后的算法性能进行测试，并与传统微分进化算法进行对比分析。

4.1算法改进效果对比分析

当进化代数设置为100，种群个体数为10，六种微分进化算法50次打靶仿真的结果如表1、图6和图7所示。总体来看,以随机个体作为基准值的三种算法效果要优于对应的以最优值作为基准值得三种算法。然而，纵向来看，当对传统微分进化算法先后添加双重自适应因子和自由变异因子后，算法性能得到了明显的改善。结合图7和表1可以看出，算法(6)不但具有很好的优化结果，也具有很好的稳定性，该算法均方差仅为0.4254，远小于传统算法，是均值和最优值最好的一组。在优化过程中计算量消耗主要存在于目标函数值计算过程中，而这个过程只与进化代数和每一代个体数有关，因此新算法的时间消耗与传统算法基本一致，并未明显提高。

表1 6种微分进化算法打靶仿真结果Table 1 Monte Carlo simulation results of the six algorithms

如图8～9所示，随着整个微分进化过程的进行，迭代步数逐渐增加，最优指标函数逐渐降低，自适应因子也在随着指标函数和进化代数的改变进行自适应过程，其最大值从优化初期大于3逐渐减小到优化末期的0.1左右，从而可以实现在微分进化的整个阶段进行的每步迭代具有不同的搜索范围和不同的全局搜索或局部搜索能力，从而使得优化过程更加高效和智能。

4.2案例仿真综合设计结果

综合仿真最终优化结果如下，在该机动过程中，任务开始后7581.6 s将施加异面变轨脉冲和第一个相位调整脉冲，该任务轨道面调整角度为2.8072°，对应的速度脉冲消耗为378.4928 m/s，需调整相位角为0.0101°，对应速度脉冲为2×0.0722 m/s，调相轨道高度为6677.8 km，轨道周期为5430.9 s，接着在调相轨道上运行一个周期后施加第二个调相脉冲，最后在目标轨道上继续运行4031.2 s后实现对目标A的访问，该结果对应的搜索空间四维矩阵参数中任务时间，轨道倾角，升交点赤经和真近点角分别为17064 s，97.5067° 162.8392°，19.8610°。

表2给出整个任务执行过程中多阶段综合优化设计结果机动参数，由表2可知，整个任务多阶段综合仿真中，先后5次对目标点进行了有效访问，任务航天器一共机动四次，分别为CA,AB,BA,AC，其中燃料主要消耗发生在第一次和第二次机动的轨道面调整部分以及第四次机动的相位角调整部分，最终累计速度脉冲消耗为867.5989 m/s，满足任务要求。

图6 6种微分进化算法50次打靶仿真效果图Fig.6 The convergence of six algorithms and 50 Monte Carlo samples for one mission

图7 6种微分进化算法50次打靶仿真均值对比图Fig.7 The average value of Q in 50 simulations for six algorithms

图8 进化过程目标函数Q趋势图Fig.8 The convergence of Q during the optimization process

图9 自适应进化因子F随进化过程改变趋势图Fig.9 The convergence of F during the optimization process

最后本文通过STK场景演示对本案例进行了验证，如表3所示，可以看出设计结果中，卫星均在相应的时间段按计划通过指定目标点，通过时间和次序与表2一致，因此可知本文的设计结果精确有效。

表2 CABAC过程多阶段综合优化设计结果-任务执行时间序列表(累计速度脉冲867.5989 m/s)Table 2 Optimal maneuver parameters sequence table for the result of CABAC multi-stage comprehensive optimization mission (total velocity impulse is 867.5989 m/s)

表3 STK多阶段综合仿真中5次访问具体参数表Table 3 Parameter results for five visit times

5 结 论

本文针对多目标点快速机动连续访问问题，直接将约束条件作用于模型建立阶段，缩小搜索空间，提高求解效率；并通过双重自适应因子和变异因子的引入，对传统的微分进化算法进行改进和仿真校验，打靶仿真结果表明改进后的算法在最优结果、优化均值、均方差等多个方面都按预期体现出了明显的优势，改进效果显著。进一步的研究将关注于将该算法应用到其他多个相关领域，尤其是复杂的多目标多约束优化问题。

[1] Abdelkhalik O, Mortari D. Orbit design for ground surveillance using genetic algorithms [J]. Journal of Guidance, Control, and Dynamics, 2006, 29(5): 1231-1235.

[2] Abdelkhalik O, Gad A. Optimization of space orbits design for Earth orbiting missions[J]. Acta Astronautica, 2011(68): 1307-1317.

[3] Kim Y H, Spencer D B. Optimal spacecraft rendezvous using genetic algorithms[J]. Journal of Guidance, Control, and Dynamics, 2012, 39(6): 859-865.

[4] Pontani M,Conway B A. Particle swarm optimization applied to space trajectories[J]. Journal of Guidance, Control, and Dynamics, 2011, 33(5): 1429-1441.

[5] Pontani M, Conway B A. Particle swarm optimization applied to impulsive orbital transfers[J]. Acta Astronautica, 2012,74: 141-155.

[6] Pontani M.Particle swarm optimization of ascent trajectories of multistage launch vehicles [J]. Acta Astronautica, 2014, 94(2): 852-864.

[7] Wang M M, Luo J J,Walter U. Trajectory planning of free-floating space robot using particle swarm optimization (PSO)[J].Acta Astronautica, 2015, 112: 77-88.

[8] Chen Y G, Mahalec V, Chen Y W.Optimal satellite orbit design for prioritized multiple targets with threshold observation time using self-adaptive differential evolution[J]. Journal of Aerospace Engineering, 2015, 28(2).

[9] Storn R, Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997 (11): 341-359.

[10] Storn R, Price K. Differential evolution-a practical approach to global optimization [M]. Springer Science & Business Media, 2006.

[11] 黄勇,李小将,张东来,等. 分布式卫星系统在轨操作的多目标分配[J]. 宇航学报, 2013, 34(11): 1475-1482. [Huang Yong, Li Xiao-jiang, Zhang Dong-lai, et al. A multi target assignment method for on orbit operation of distributed satellites system[J]. Journal of Astronautics, 2013, 34(11): 1475-1482.]

[12] 刘文, 张育林, 刘昆. 基于多目标进化算法的卫星通信星座优化设计[J]. 宇航学报, 2008, 29(1):95-99. [Liu Wen, Zhang Yu-lin, Liu Kun. Optimization of multi-objective evolutionary algorithm-based communication satellite constellation[J]. Journal of Astronautics, 2008, 29(1): 95-99.]

[13] 张仁勇, 罗建军, 程潏, 等. 基于微分进化算法的深空轨道全局优化设计[J].力学学报, 2012, 44(6):1079-1083. [Zhang Ren-yong, Luo Jian-jun, Cheng Yu, et al. The global optimization of space exploration trajectory design based on differential evolution algorithm[J]. Chinese Journal of Theoretical and Applied Mechanics, 2012, 44(6):1079-1083.]

[14] 尚海滨, 崔平远, 乔栋. 基于形状的行星际小推力转移轨道初始设计方法[J].宇航学报, 2010, 31(6):1569-1574. [Shang Hai-bin, Cui Ping-yuan,Qiao Dong. A shape-based design approach to interplanetary low-thrust transfer trajectory[J]. Journal of Astronautics, 2010, 31(6):1569-1574.]

[15] 王石, 祝开建, 戴金海, 等. 用进化算法求解轨道转移的时间能量优化问题[J]. 宇航学报, 2002, 23(1):73-75. [Wang Shi, Zhu Kai-jian, Dai Jin-hai, et al.Solving orbital transformation problems based on EA[J]. Journal of Astronautics, 2002, 23(1):73-75.]

[16] 刘正雄, 鹿振宇, 黄攀峰. 基于递推差分进化算法的空间机器人参数辨识[J]. 宇航学报, 2014, 35(10):1127-1134. [Liu Zheng-xiong, Lu Zhen-yu, Huang Pan-feng. Parameter identification of space robot based on recursive different evolution algorithm[J]. Journal of Astronautics, 2014, 35(10): 1127-1134.]

AnImprovedDifferentialEvolutionAlgorithmandItsApplicationonMultipleVisitingTargetProblem

YAO Wei1,2，LUO Jian-jun1,2，MA Wei-hua1,2，YUAN Jian-ping1,2

(1. School of Astronautics, Northwestern Polytechnical University，Xi’an710072，China；2. Science and Technology on Aerospace Flight Dynamics Laboratory，Xi’an 710072，China)

An optimal problem of orbit maneuver when multiple targets need to be visited in a described period of time is modeled and solved in this paper. Firstly, the problem description and modeling process considering multiple constraints and performance indexes can reduce the searching space and improve the efficiency. Then focusing on the drawbacks of the classical differential evolution algorithm, an improved algorithm is proposed and applied on the multiple visiting target problem. The traditional algorithm is improved by designing the double self-adaption control parameters and introducing a random mutant to improve the efficiency of optimizing and make the algorithm can jump out when trapped into the local optimum. Specific simulation verifies that the SA-DE-RM (rand) algorithm has a better performance on average value, best result and mean square error and it is feasible and effective.

Orbit maneuver design; Self-adaptive differential evolution; Multi-constraints; Multiple visiting target

V448

A

1000-1328(2017)09- 0919- 08

10.3873/j.issn.1000-1328.2017.09.004

2017- 04-14;

2017- 07- 07

国家自然科学基金(61690210,61690211)

姚玮(1990-)，男，博士生，主要从事航天轨道设计研究。

通信地址：陕西省西安市友谊西路127号(710072)

电话：18700878078

E-mail:451685010@qq.com