求解航天器最优交会问题的改进和声搜索算法

引用本文

王皓，欧阳海滨，高立群. 求解航天器最优交会问题的改进和声搜索算法[J]. 东北大学学报:自然科学版 , 2015, 36(7): 913-917. 复制到剪切板

WANG Hao, OUYANG Hai-bin, GAO Li-qun. Amended Harmony Search Algorithm for Solving Spacecraft Optimal Rendezvous Problem[J]. Journal Of Northeastern University Nature Science, 2015, 36(7): 913-917. 复制到剪切板

求解航天器最优交会问题的改进和声搜索算法

王皓, 欧阳海滨, 高立群

(东北大学信息科学与工程学院，辽宁沈阳 110819)

收稿日期：2014-05-28

基金项目：国家自然科学基金资助项目(61273155); 辽宁省科技厅博士科研启动基金资助项目(L201205118)

作者简介：王皓(1981-),女,辽宁沈阳人,东北大学博士研究生; 高立群(1949-), 男,辽宁沈阳人,东北大学教授,博士生导师.

摘要：针对航天器最优交会问题，基于C-W模型建立一种燃料时间混合指标，并提出一种改进和声搜索 (AHS)算法进行求解.在AHS算法中，提出一种全局均匀学习操作，利用了当前全局最优和声的指导作用，取代了原始和声搜索算法的基音调整操作，增强全局搜索和局部搜索的平衡，并对参数PAR进行了有效的动态调整，以更好适应算法的搜索进程.利用几个最优交会实例对AHS算法的有效性进行了测试，数值结果表明AHS算法能够取得满意的结果，并且优于其他算法.

关键词：最优交会问题改进和声搜索算法全局均匀学习全局搜索局部搜索

Amended Harmony Search Algorithm for Solving Spacecraft Optimal Rendezvous Problem

WANG Hao, OUYANG Hai-bin, GAO Li-qun

School of Information Science & Engineering, Northeastern University, Shenyang 110819, China.
Corresponding author: OUYANG Hai-bin, E-mail: oyhb1987@163.com

Abstract: A hybrid index of fuel-time on the basis of C-W equations was built for the spacecraft optimal rendezvous problem, and an amended harmony search (AHS) algorithm was proposed to solve this problem. In the AHS algorithm, a global uniform learning operation was presented that the guidance of the current global best harmony was utilized and the pitch adjusting operation was replaced, resulting in the enhancement of the balance between the global search and local search. The PAR was dynamically adjusted to adapt the search process of algorithm. Several optimal rendezvous cases were used to test the effectiveness of AHS algorithm, and it was verified by the numerical results that correct satisfied results could be obtained with the proposed AHS algorithm, which is better than that of the other algorithms.

Key words: optimal rendezvous problem amended harmony search algorithm global uniform learning global search local search

空间交会对接(rendezvous and docking)是进行空间组装、空间救援、深空探测的必要技术^[1].空间交会过程主要有远距离导引段、近距离导引段、最后接近段以及逼近对接段^[2].其中在近距离导引变轨，实现空间最优交会对接对未来空间探索具有十分重要的作用.

在过去的几十年中，关于航天器最优交会问题的研究，已有很多学者做出了许多贡献.在这些研究中，许多常规的寻优方法应用于最优交会问题，例如解析法、动态规划方法等.但是传统的常规寻优方法求解速度慢，优化效果并不令人满意，要求的数学条件苛刻，而智能优化算法在最近几十年得到了迅速发展，具有寻优效率高、操作简单、数学条件要求低等优势，在许多工程领域都得到了广泛应用.在航空航天领域，许多智能优化算法也逐渐得到应用.例如：模拟生物进化理论“适者生存，优胜劣汰”准则的遗传算法以及混合遗传算法^[3],基于群体差异的差分演化算法^[4]，基于统计学理论的分布估计算法^[2].通过大量的数值仿真表明智能优化算法相对传统的常规方法搜索效率更高，并且能够较好地搜索到比较满意的结果.但是智能优化算法存在易陷入局部最优的不足，最终搜索的结果不稳定.

和声搜索 (harmony search，HS) 算法是由Geem等于2001年提出的一种新颖的智能算法^[5].HS算法已被成功应用到许多实际优化问题中.本文针对航天器最优交会问题，提出一种改进的和声搜索算法进行求解.通过几个实例表明了本文算法的有效性，并与HS算法、粒子群 (PSO)^[6]算法、差分演化 (DE)^[7]算法及人工蜂群 (ABC)^[8]算法进行了比较，结果显示了本文算法的优越性.

1 最优交会模型

航天器交会实质上是追踪航天器按照一定的规律进入到指定的目标航天器轨道.文献^[2]给出了简单的目标轨道坐标系如图 1所示.

图 1中，设目标航天器的质心为O，Ox轴为目标航天器所在轨道速度切线的反方向，背向地心的方向为Oy轴，与Ox轴，Oy轴构成右手直角坐标系为Oz轴.为了方便相对轨道位置运动的研究，认为目标轨道坐标系随着目标航天器的轨道运行.依据此坐标系建立的C-W 线性模型如下：

图 1 目标轨道坐标系 Fig. 1 Target orbit coordinate system

其中: B_x，B_y，B_z分别表示施加于追踪航天器上3个方向的连续加速度；ω为目标航天器的轨道角速度.当采用脉冲推力假设时，只需设置飞行状态的初始值，并将B_x，B_y，B_z同时置为零.设状态变量

,控制变量u=[B_x,B_y,B_z]^T,则式(1)可写成如下状态方程:

其中：

可得到状态转移矩阵为

其中：

其中，τ=ω(t－t₀).

设在t0时刻，航天器的初始状态设为(x₀,y₀,z₀,v_x0,v_y0,v_z0).运行一段时间后，加入第一次脉冲，假设此时为 t₁时刻，t₁时刻前航天器的状态为(x₁₀,y₁₀,z₁₀,v_x10,v_y10,v_z10)，由状态转移矩阵式(3)可以得到(x₁₀,y₁₀,z₁₀,v_x10,v_y10,v_z10)=φ(t-t₀)·(x₀,y₀,z₀,v_x0,v_y0,v_z0).如果t₂时刻航天器加入第二次脉冲时实现交会，并且末端状态为(0,0,0,0,0,0)，则利用状态方程和状态转移矩阵可推导出t₁时刻后的速度(v_x12,v_y12,v_z12)和t₂时刻之前航天器的速度(v_x2,v_y2,v_z2),则有第一次脉冲速度为

第二次脉冲速度为

航天器交会优化目的是实现时间和燃料消耗的最小化，文献^{[6, 7, 8, 9, 10, 11]}采用加权求和的方法建立如下指标:

其中，T₁=t₁-t₀，T₂=t₂-t₁；λ为可调的权系数；|·|表示向量取模.因为燃料消耗和时间是两个不同物理量，不能单纯叠加，式(6)有些不足，最好是分别归一化之后再相加.因此，在本文中能量-时间混合优化指标设计如下：

其中，max(x)表示取x的最大值.如果T₁和T₂给定，则Δv₁和Δv₂也可以根据式(2)~式(5)求出.所以实质上只需要优化变量T₁和T₂.

2 AHS算法设计

本文结合航天最优交会问题，提出一种改进和声搜索算法.下面具体介绍全局均匀调整方法和动态参数设计.

2.1 全局均匀调整

在和声搜索算法中，即兴创作过程是和声搜索算法最关键的部分，主要包括3个操作：和声记忆考虑、基音调整和随机选择.为了更好地增强和声搜索算法全局搜索和局部搜索的平衡，在改进和声搜索算法中，设计了一种全局均匀调整方法.其具体的表达式如下：

其中，xbest,j表示当前最好和声的第j维变量；_j表示所有和声第j维变量的平均值；第xr₁,j和xr₂,j表示随机选的两个和声的第j维变量；rand₁和rand₂表示0和1之间的随机数；c₁为全局调整因子，c₁为1或2，c₁=round(1+rand).通过当前全局最好的和声与整个和声记忆库中所有和声的平均值的比较，促使新产生的和声向当前最优方向靠近，增强算法收敛性能.另一方面利用和声记忆库中随机的较好和声拓展搜索的广泛性，防止算法陷入局部极值.

2.2 参数动态调整

在和声算法中，基音调整概率PAR决定了全局均匀调整的执行概率.为了适应算法的搜索进程，文献^{[9, 10, 11, 12]}中提出了各种PAR动态调整的方法：

其中：k和K分别代表当前迭代次数和最大迭代次数；PAR_min和PAR_max分别代表最小基音调整概率和最大基音调整概率.在式(9)~式(11)中PAR 随着迭代次数呈线性变化，PAR在整个搜索过程中，变化的速率是恒定的，这种调整简单易行，但比较粗糙.式(12)~式(14)中PAR 随着迭代次数呈指数变化.PAR在整个搜索过程中，变化的速率是变化的；如果PAR在迭代早期变化比较缓慢，更能挖掘局部信息，而随着迭代次数的增加PAR的变化逐渐加快，这样能加快搜索速度.因此，本文将参数PAR设计为

假设K=1000，参数PAR随着迭代次数k的变化曲线如图 2所示.

图 2 PAR变化曲线 Fig. 2 Changing curve of PAR

2.3 AHS算法流程

步骤1 优化问题和算法参数初始化.

航天器最优交会问题的参数包括问题的维数D=2，变量的取值范围x_j,L≤x_j≤x_j,U,j=1,2；和声搜索算法参数主要有最大迭代次数K，和声记忆库大小HMS(harmony memory size)，和声记忆考虑概率HMCR(harmony memory considering rate)，基音调整概率PAR(pitch adjusting rate)及调整步长bw.

步骤2 和声记忆库进行初始化.

和声记忆库用来存储HMS个随机的和声解向量.和声解向量的每一维和声分量由变量的上下界 x_j,U和x_j,L产生.

步骤3 进行即兴创作，产生一个新的和声解向量.其具体的即兴创作伪代码如下:

For j=1 to D do
If rand()≤HMCR 和声记忆库考虑
x_new,j= x_r,j,r∈(1,2,3,…,HMS)
If rand()≤PAR then全局均匀调整
If f(x_r₁) < f(x_r₂)
x_new,j=x_new,j+rand₁·(x_best,j－ c₁·x_new,j)+rand₂·(x_r₁,j－x_r₂,j)

Else
x_new,j=x_new,j+rand₁·(x_best,j－ c₁·x_new,j)+rand₂·(x_r₂,j－x_r₁,j)
End If
End If
Else
x_new,j=x_j,L+rand()×(x_j,U－x_j,L) 随机选择

End If

End For

步骤4 进行选择操作，更新和声记忆库.

如果新的和声解向量对应的适应值优于最差和声解向量对应的适应值，则新的和声解向量取代最差的和声解向量，否则最差的和声解向量保存不变.

步骤5 检查停止准则.

如果当前迭代次数等于最大迭代次数K,则停止运行HS算法，否则重复运行步骤3和步骤4，直到迭代次数达到最大迭代次数为止.

3 仿真实验与结果分析

假设目标航天器在400km高的圆轨道上运行，追踪航天器取两个初始相对状态计算，分别为(70000,-30000,0,-40,30,0)和(100000,-20000,0,-20,0,0)，交会终端相对状态为(0,0,0,0,0,0).

本文算法和PSO算法^[6]、DE算法^[7]、HS算法^[5]及ABC算法^[8]对此问题进行求解，各个算法的参数设置如表 1所示，每个算法的目标函数评价次数都设为50000.实验仿真环境为Windows XP系统，Intel(R) Pentium(R) 4 CPU 2.93GHz，2.94GHz,4 GB内存；仿真软件MATLAB 7.04，独立运行30次，所求得的结果如表 2所示.

表 1 算法参数 Table 1 Algorithm parameters

表 2 5种算法的优化结果(λ=0.1) Table 2 The optimization results of 5 algorithms (λ=0.1)

基于燃料最优和时间最优的考虑，将目标函数的权重λ分别设为0,0.01,0.1,0.25,0.5,0.75,0.8,0.95,1，利用本文算法进行进一步求解，所得结果见表 3，并绘制了不同权重λ时算法的优化曲线，分析燃料及时间的重要性和合理性.

由表 2可以看出，本文算法所得的结果是最好的.无论是最好值、最差值、中间值，还是平均值和方差，本文算法都比PSO算法、DE算法、HS算法、ABC算法要好，表现出良好的优化性能，说明本文算法能够有效地求解航空器最优交会问题，并获得有竞争优势的结果.

由表 3可知，随着时间权重的增加，最优指标也在逐渐增加，但增加的幅度相对较小，说明时间因素是不可忽略的.当权重λ<0.5时，最优指标的数量级保持在10^-2，当权重0.5<λ<1时，最优指标的数量级保持在10^-1.这表明在有限时间的要求下，最优的燃料消耗起到决定性的作用.

表 3 不同权重时的优化结果 Table 3 The optimization results with different weights

4 结论

本文针对航天器最优交会问题，基于C-W模型建立一种有效合理的燃料时间混合指标，并提出一种改进和声搜索(AHS)算法进行求解.在AHS算法中，应用全局均匀学习操作取代HS算法中的基音调整，有效地平衡算法的全局搜索和局部搜索.通过最优交会实例，测试了AHS算法的有效性，数值统计结果表明AHS算法优于其他智能优化算法，具有良好的寻优潜力.

参考文献

[1]	Fehse W.Automated rendezvous and docking of spacecraft[M].Oxford City:Cambridge University Press,2003.(1)
[2]	张琪新, 王士星.分布估计算法在航天器近距离最优交会中的应用[J]. 计算机工程与科学, 2012, 34(5):89-94. (Zhang Qi-xin, Wang Shi-xing.Application of the EDA algorithm in the near range optimal rendezvous for spacecrafts[J]. Computer Engineering & Science, 2012, 34(5):89-94.)(3)
[3]	王华,唐国金.用遗传算法求解双冲量最优交会问题[J]. 中国空间科学技术, 2003(1):26-30. (Wang Hua, Tang Guo-jin.Solving optimal rendezvous using two impulses based on genetic algorithms[J]. Chinese Space Science and Technology, 2003(1):26-30.)(1)
[4]	戴光明, 李晖.DE算法在空间交会中的应用[J]. 上海航天, 2007(3):46-49. (Dai Guang-ming, Li Hui.Study on application of differential evolution algorithm in space rendezvous[J]. Aerospace Shanghai, 2007(3):46-49.)(1)
[5]	Geem Z W, Kim J H, Loganathan G V.A new heuristic optimization algorithm:harmony search[J]. Simulation, 2001, 76(2):60-68.(2)
[6]	Kennedy J, Eberhart R.Particle swarm optimization[C]// Proceedings of IEEE International Conference on Neural Networks.Perth, 1995:1942-1948.(3)
[7]	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.(3)
[8]	Karaboga D, Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39(3):459-471.(3)
[9]	Wang L, Yang R X, Xu Y, et al.An improved adaptive binary harmony search algorithm[J]. Information Sciences, 2013, 232:58-87.(2)
[10]	Mahdavi M, Fesanghary M, Damangir E.An improved harmony search algorithm for solving optimization problems[J]. Applied Mathematics and Computation, 2007, 188(2):1567-1579.(2)
[11]	Chen J, Pan Q K, Li J Q.Harmony search algorithm with dynamic control parameters[J]. Applied Mathematics and Computation, 2012, 219(2):592-604.(1)
[12]	Yadav P, Kumar R, Panda S K, et al.An intelligent tuned harmony search algorithm for optimization[J]. Information Sciences, 2012, 196:47-72.(1)

本文献在全文中的定位：

... 接(rendezvous and docking)是进行空间组装、空间救援、深空探测的必要技术^[1].空间交会过程主要有远距离导引段、近距离导引段、最后接近段以及 ...

本文献在全文中的定位：

... 过程主要有远距离导引段、近距离导引段、最后接近段以及逼近对接段^[2].其中在近距离导引变轨，实现空间最优交会对接对未来空间探索具有 ...

... 基于统计学理论的分布估计算法^[2].通过大量的数值仿真表明智能优化算法相对传统的常规方法搜索效率 ...

... 实质上是追踪航天器按照一定的规律进入到指定的目标航天器轨道.文献^[2]给出了简单的目标轨道坐标系如图 1所 ...

本文献在全文中的定位：

... 物进化理论“适者生存，优胜劣汰”准则的遗传算法以及混合遗传算法^[3],基于群体差异的差分演化算法^{[4]
...}

本文献在全文中的定位：

... [3],基于群体差异的差分演化算法^[4]，基于统计学理论的分布估计算法^{[2
...}

本文献在全文中的定位：

... 搜索 (harmony search，HS) 算法是由Geem等于2001年提出的一种新颖的智能算法^[5].HS算法已被成功应用到许多实际优化问题中.本文针对航天器最优交会 ...

... DE算法^[7]、HS算法^[5]及ABC算法^[8]对此问题进行求 ...

本文献在全文中的定位：

... 求解.通过几个实例表明了本文算法的有效性，并与HS算法、粒子群 (PSO)^[6]算法、差分演化 (DE)^[7]算法及 ...

... 航天器交会优化目的是实现时间和燃料消耗的最小化，文献^{[6, 7, 8
...}

... 本文算法和PSO算法^[6]、DE算法^[7]、HS算法 ...

本文献在全文中的定位：

... (PSO)^[6]算法、差分演化 (DE)^[7]算法及人工蜂群 (ABC)^[8]算法 ...

... 现时间和燃料消耗的最小化，文献^{[6, 7, 8, 9
...}

... 本文算法和PSO算法^[6]、DE算法^[7]、HS算法^[5]及ABC算法 ...

本文献在全文中的定位：

... (DE)^[7]算法及人工蜂群 (ABC)^[8]算法进行了比较，结果显示了本文算法的优越性.

...

... ^{[6, 7, 8, 9, 10,
...}

... HS算法^[5]及ABC算法^[8]对此问题进行求解，各个算法的参数设置如 ...

本文献在全文中的定位：

... 7, 8, 9, 10, 11]< ...

... 概率PAR决定了全局均匀调整的执行概率.为了适应算法的搜索进程，文献^{[9, 10, 11,
...}

本文献在全文中的定位：

... 8, 9, 10, 11]采用加权求和的方法建立如下指 ...

... 为了适应算法的搜索进程，文献^{[9, 10, 11, 12]
...}

本文献在全文中的定位：

... 9, 10, 11]采用加权求和的方法建立如下指标:

...

... ^{[9, 10, 11, 12]}中提出了各种PAR动态调整的方法 ...

本文献在全文中的定位：

... 10, 11, 12]中提出了各种PAR动态调整的方法：

...


东北大学学报:自然科学版 2015, Vol. 36 Issue (7): 913-917	PDF (318 KB)