针对路径规划问题，目前的研究方法大致可以分为传统算法和启发式智能算法2类。传统算法包括视图法、人工势场法、单元分解法、精确数学规划法等[2]，存在模型复杂、效率低和容易陷入局部最优等缺点。启发式智能算法包括遗传算法、蚁群算法、粒子群(Particle Swarm Optimization, PSO)算法和鸽群(Pigeon-Inspired Optimization，PIO)算法等[3]，具有模型参数少、求解速度快和收敛性好等优点。
鸽群算法是2014年Duan和Qiao[4]受到鸽群自主归巢行为启发提出的仿生智能优化算法。自提出后，鸽群算法在编队路径规划方面取得了许多成果。林娜、黄思铭、拱长青[5]利用鸽群算法解决无人机航迹规划问题，引入自适应权重系数，解决了局部最优和收敛速度慢的问题，但是航迹质量和效率有待提高，另外需要经过样条平滑算法改进。北京航空航天大学的胡耀龙、冯强等[6]为了避免标准鸽群算法陷入局部最优，提出了一种基于自适应学习策略的改进鸽群优化算法，该算法提升了多峰函数优化问题中的收敛精度和收敛速度，并且能有效避免陷入局部最优解，但是没有针对实际问题建模分析。哈尔滨工程大学的崔文豪[7]研究了J2摄动下的卫星编队队形重构与队形保持方法，利用极小值理论，运用多重打靶法结合改进鸽群算法，改善重构控制精度和燃料消耗，但是并没有考虑各成员星变轨时的碰撞问题。Zhang和Duan[8]提出了一种满足高斯分布的鸽群算法用来解决航天器编队重构路径规划问题，考虑了各成员不发生碰撞情况下的燃料消耗最小化问题，但稳定性需要提高。虽然已有很多研究体现了鸽群算法的有效性，但是鸽群算法仍然存在参数优化、收敛速度慢、易陷入局部最优等问题，路径规划的效果并不理想。
针对上述鸽群算法本身及应用的不足之处，本文对基本鸽群算法进行了3点改进：采用Tent Map混沌模型进行鸽群初始化操作，增加种群多样性；设计了自适应的地图和指南针算子防止搜索停滞；在地标算子阶段引入高斯扰动，帮助算法跳出局部最优。基于上述改进，本文提出了一种基于混沌初始化和高斯扰动的自适应鸽群(CGAPIO)算法，来解决航天器编队重构路径规划问题，实现燃料消耗最优化。
1 模型构建 1.1 轨道动力学模型 假设地球是均匀球体，忽略任何摄动力，参考航天器为A，伴随航天器为B，两航天器轨道均为圆轨道。
航天器编队飞行时，两航天器之间的相对位置矢量δr与伴随航天器的惯性位置矢量r0相比，相对位置矢量的模很小，如下：
 | (1) |
编队飞行相对参考坐标系与地心惯性坐标系的关系如图 1所示。O-XYZ为地心惯性坐标系。A-xyz为参考航天器的相对运动坐标系，其原点与参考航天器的质心固连，y轴与参考航天器的地心矢量r重合，由地心指向参考航天器。x轴在参考航天器的轨道面内垂直于y轴并指向运动方向为正，z轴由右手规则确定。
 |
| 图 1 编队飞行相对参考坐标系 Fig. 1 Relative frame of reference for formation flight |
| 图选项 |
基于上述假设和条件，根据相对运动动力学，可以用Clohessy-Wiltshire方程[9](C-W方程)来描述航天器间相对运动。C-W方程表示为
 | (2) |
式中：ω为参考航天器轨道角速度的大小；x、y、z分别为相对位置矢量在参考航天器轨道坐标系三轴的投影。
假设给定初始条件，相对位置初始值δr0=[x0, y0, z0]，相对速度初始值
 | (3) |
1.2 目标函数及约束 本文提出的航天器编队重构路径规划问题，将总燃料消耗作为目标函数，将碰撞概率视为约束条件。通过罚函数，将带约束条件的最优化问题转化为无约束条件的最优化问题。
罚函数是目前解决带约束优化问题的方法之一，其思想是：对违反约束条件的非可行点或者试图穿越约束边界逃离可行域的点给予惩罚，使其靠近可行域[10-11]。具体实施方法是：将约束函数组成一个惩罚项，与原目标函数相加，迫使迭代点逼近可行域[12]。
构造CGAPIO算法的适应度函数S(X)为
 | (4) |
式中：F(X)为航天器变轨过程中燃料的总消耗量；γ为惩罚因子；C(X)为碰撞概率[13]。
本文提出的CGAPIO算法将航天器轨迹离散化，计算所有相邻离散点之间的相对速度变化量之和，以此来衡量燃料总消耗量。当两航天器之间的相对距离小于临界安全距离时，表示碰撞风险较大，此时C(X)起到惩罚作用使航天器远离风险区域。
2 基于混沌初始化和高斯扰动的自适应鸽群算法 本文对基本鸽群算法提出了3点改进，基于此，提出了CGAPIO算法。
2.1 基本鸽群算法 鸽群算法将每一个鸽子个体视为可能解，每个个体包含位置和速度2个参数，并且根据鸽子飞行的不同阶段提出了2种算子模型。
1) 地图和指南针算子
在距离目的地较远时，鸽群主要依靠地磁场的指引靠近目的地。随着鸽群越来越接近目的地，会减少对地磁场的依赖。此阶段，个体的速度由上一代原有速度、种群的最佳位置与上一代原有位置的差值共同决定；个体的位置由其上一代原有位置和当前速度共同决定。地图和指南针算子的数学表达式为
 | (5) |
 | (6) |
式中：t为迭代次数；R为地图和指南针因子，是一个[0, 1]的常数；rand为[0, 1]的随机数；Vi(t)和Xi(t)分别为个体i在第t代的速度和位置；Xg为当前种群最佳位置。
2) 地标算子
距离目的地较近时，鸽群会依靠地标导航，跟随熟悉地标的个体飞行，不熟悉地标的个体将被逐渐舍弃，鸽群的中心位置成为速度的参考方向。地标算子的数学表达式为
 | (7) |
 | (8) |
 | (9) |
式中：Np(t)为第t次迭代的个体数目；Xc(t)为第t次迭代的剩余鸽群的中心位置；S(Xi(t))为个体i在第t次迭代时的适应度函数。
2.2 混沌初始化改进算法 基本鸽群算法的位置和速度矢量初值由随机数产生，该方法尽可能地保证了随机性，整体上可以保证初始鸽群在整个解空间均匀分布，但是通过随机数产生的方法，会使某些初值远离最优解，影响种群迭代效果。
混沌现象是普遍存在于非线性动态系统中的伪随机过程。混沌运动是指在一个确定性系统中，存在着貌似随机的不规则运动，具有遍历性、随机性和对初始条件敏感等特点[14]。Tent Map混沌模型[15]是研究动力系统、混沌、分形等复杂系统行为的一个经典模型，数学表达式为
 | (10) |
式中：a?[0, 4]为Tent Map映射参数。
初始值Y0取值影响混沌效果，Y0?(0，1)。图 2举例说明并对比了Y0分别取0.288和0.588产生50个混沌随机数的效果。
 |
| 图 2 不同初始值下的Tent Map混沌模型结果 Fig. 2 Results of Tent Map chaotic model with different initial values |
| 图选项 |
针对本文解决的问题，经过反复测试的取值，最终选择为0.280，可以产生较好的多样性效果。本文以式(11)生成初代鸽群位置。
 | (11) |
式中：Nmax为初代鸽群的鸽子总数。
图 3以Nmax=50，X1的模值为0.280 km为例，对比了Tent Map混沌模型和随机数各自产生初代鸽群位置的效果。可以看出，随机数在矩形框围住的区域内基本没有取值，初始值多样性效果较差；而在椭圆框围住的区域内，取值又比较集中，容易在迭代过程中形成局部最优。使用Tent Map混沌模型产生的初值无明显集中或者远离某区域的现象，比较均匀地分布在整个平面内，比使用随机数产生的初值有更好的多样性和覆盖性。
 |
| 图 3 随机数与Tent Map混沌模型初始化结果对比 Fig. 3 Comparison of initialization results between random numbers and Tent Map chaotic model |
| 图选项 |
为了在保持群体初值随机性的前提下，提高多样性和覆盖性，本文使用Tent Map混沌模型代替随机数赋予鸽群位置矢量和速度矢量初值。
2.3 自适应因子改进算法 基本鸽群算法对多维函数进行求解时，普遍存在易陷入局部极值的缺点[16]。为了提高种群个体的全局搜索能力，本文在基本鸽群算法原有的地图和指南针算子迭代公式基础上引入了自适应权重因子和学习因子。
通过分析基本鸽群算法地图和指南针算子模型的速度迭代公式可以发现，个体速度的更新一方面取决于上一代的速度影响，该部分影响大小主要体现在地图和指南针因子；另一方面取决于上一代全局最优的位置对个体位置的修正。
基本鸽群算法中地图和指南针因子在迭代前期的作用是保持鸽群个体的多样性，使种群在整个解空间内广泛搜索[17]。但是，在基本鸽群算法中的值是固定不变的，而且式(5)中Vi(t-1)e-Rt代表的是个体保持原来速度的大小和方向的效果，该乘积项包含指数函数，衰减速度太快。令R=0.4，当t=18次时，e-Rt≈0即迭代到第18次，种群就完全放弃了个体原有的速度，只参考种群最佳位置。此时算法不再进行全局搜索，使得种群围绕在当前全局最优进行搜索和迭代，陷入局部最优的陷阱[18]。
为了解决基本鸽群算法中地图和指南针因子的固有弊端，本文引入自适应的权重因子w代替指数函数e-Rt，如式(12)所示；引入自适应的学习因子c来控制种群最优位置的影响，如式(13)所示。
 | (12) |
 | (13) |
式中：tmax为迭代总次数；wmax为权重因子最大值，取0.9；wmin为权重因子最小值，取0.6。
引入自适应权重因子和学习因子后，地图和指南针算子速度迭代公式为
 | (14) |
图 4显示了权重因子和学习因子随着迭代次数的变化情况。w的初值较大，c的初值较小，体现了在迭代初期，多样化的个体在全局的搜索能力比全局最优个体的贡献更重要。随着迭代过程的进行，权重因子线性递减，学习因子呈三角函数非线性递增，体现了在迭代后期，筛选出来的全局最优位置更加具有指导性，局部搜索能力更加重要，能够加快收敛。
 |
| 图 4 自适应权重因子和学习因子随迭代次数的变化 Fig. 4 Changes of adaptive weighting factor and learning factor with number of iterations |
| 图选项 |
2.4 高斯扰动改进算法 在地标算子阶段，鸽群整体的中心位置成为速度的参考方向，个体向中心位置靠拢。但是如果当前鸽群中心位置是一个局部极值点，会更加容易导致鸽群陷入局部最优。为了解决这一问题，本文将高斯扰动项引入到鸽群算法的地标算子中。
以f(x)=x为例，图 5对比了加入均值为0、方差为100的高斯扰动前后的情况。可以看到，加入高斯扰动后f(x)的值围绕着原值进行波动，波动的大小可以由方差控制。在鸽群算法的地标算子阶段，鸽群的中心位置已经接近最优解，加入适宜的高斯扰动既不会过度偏离已知解，保证了算法的收敛性，又可以避免陷入局部最优无法摆脱。
 |
| 图 5 高斯扰动示意图 Fig. 5 Schematic diagram of Gaussian disturbance |
| 图选项 |
CGAPIO算法在地标算子中增加高斯扰动项后，鸽群个体位置按照式(15)更新。
 | (15) |
式中：G(μ, σ2)为高斯扰动项，μ为均值，σ2为方差。
在相关的加入高斯扰动的仿生群体智能算法研究中，通常均值取0，保证高斯分布均匀性[19-22]；而方差σ2的数值大小需要根据具体问题来确定。针对本文研究的问题，在其他条件相同的情况下，经过对比发现方差取值为20时得到的效果最好。
图 6为CGAPIO算法的流程。首先根据C-W方程建立航天器编队相对运动的数学模型，然后利用Tent Map混沌模型给位置和速度赋初值。根据初值进行首次适应度排序，然后引入自适应因子到鸽群算法的地图和指南针算子迭代过程。在经过规定次数的迭代后，进入地标算子迭代过程，在此阶段利用高斯扰动跳出局部最优。在完成设定的总迭代次数后，输出规划后的路径。
 |
| 图 6 CGAPIO算法流程 Fig. 6 Flowchart of CGAPIO |
| 图选项 |
3 仿真实验 本文算法以4个航天器从圆形编队变换到直线形编队为例，轨迹离散点设为3个；鸽群总数为30个，路径规划维度为20维。迭代次数为100次，其中地图与指南针算子阶段迭代66次，地标算子阶段迭代34次。在C-W坐标系下，航天器初始位置和目标位置如表 1所示。
表 1 航天器初始位置与目标位置 Table 1 Initial and target positions of spacecraft
| 航天器编号 | 初始位置/km | 目标位置/km |
| 1 | (1.732，2，0.034 64) | (0，1，0) |
| 2 | (0，4，0) | (0，-2，0) |
| 3 | (-1.732，-2，0.034 64) | (0，-1，0) |
| 4 | (0，-4，0) | (0，2，0) |
表选项
CGAPIO、PIO、PSO三种算法规划的路径结果分别如图 7~图 9所示。
 |
| 图 7 CGAPIO算法路径规划结果 Fig. 7 Path planning results of CGAPIO |
| 图选项 |
 |
| 图 8 PIO算法路径规划结果 Fig. 8 Path planning results of PIO |
| 图选项 |
 |
| 图 9 PSO算法路径规划结果 Fig. 9 Path planning results of PSO |
| 图选项 |
观察PIO算法和PSO算法的规划结果，规划路径的起始方向与目标位置所在的方向相差甚多，这是由于使用随机数方法赋予初始值，种群可能选取到距离最优解较远的初值；规划所得到的路径比较曲折，方向改变幅度很大。这是由于种群过早丧失了全局搜索能力，所跟随的“最优解”是局部最优，才导致规划所得的路径质量不高。
相比之下，CGAPIO算法的路径规划结果明显更加平滑，没有大幅度转折。特别是对于航天器3，CGAPIO算法规划得到的路径近似于连接起点与终点的直线。各航天器速度方向改变不大，保证了各航天器之间有一定安全距离余量，降低了碰撞概率；又避免了过大幅度的无效机动。
图 7~图 9路径规划结果对应的总燃料消耗如表 2所示。CGAPIO算法总燃料消耗与PIO算法相比，平均降低了12.86%；与PSO算法相比，平均降低了22.71%。
表 2 不同算法总燃料消耗对比 Table 2 Comparison of total fuel consumption among different algorithms
| 算法 | 燃料消耗/(km·s-1) | 总燃料消耗/(km·s-1) | |||
| 航天器1 | 航天器2 | 航天器3 | 航天器4 | ||
| CGAPIO | 0.006 65 | 0.012 40 | 0.012 29 | 0.006 72 | 0.038 06 |
| PIO | 0.007 52 | 0.015 53 | 0.015 36 | 0.007 08 | 0.045 49 |
| PSO | 0.007 04 | 0.018 16 | 0.017 19 | 0.007 14 | 0.049 53 |
表选项
由于采用了Tent Map混沌模型进行初始化，鸽群初始值分布比较均匀，靠近最优解的可能性较大，在开始迭代时，CGAPIO算法的适应度值小于50，甚至优于用PSO算法得到的最优解。
PIO和PSO算法分别在第10次和第16次就停止了适应度的更新，最终的适应度值分别是49.73和45.78，都在迭代初期陷入了局部最优的陷阱，并且始终无法摆脱。然而CGAPIO算法在迭代初期保留了全局搜索的能力，对应的是图 10中迭代初期适应度变化缓慢。同时CGAPIO算法保证了种群有较快的演化速度，快速淘汰距离最优解较远的个体，对应的是图 10中适应度呈折线形变化，在迭代不到30次的时候就已经十分接近用PIO算法得到的最优解。CGAPIO算法一直保持更新适应度到第72次迭代，最终的适应度值为38.06，得到了更深的种群演化深度。
 |
| 图 10 不同算法适应度对比 Fig. 10 Comparison of fitness curves among different algorithms |
| 图选项 |
4 结论 1) 引入混沌初始化模型、自适应因子和高斯扰动对基本鸽群算法进行改进，提出CGAPIO算法用于航天器编队重构路径规划。规划结果路径平滑，消耗燃料少，既避免了碰撞，又避免了无效机动。
2) 仿真结果表明，与PIO算法和PSO算法相比，不论是编队的总燃料消耗还是各个航天器的燃料消耗，CGAPIO算法都是最少的。
3) CGAPIO算法有着较低的初始适应度值，表明Tent Map混沌模型确实起到了增强种群的多样性的作用；而PSO算法和PIO算法使用随机数模型，导致在开始迭代时，适应度初始值均超过了CGAPIO算法。
4) CGAPIO算法兼顾了全局搜索能力和演化深度，最终的适应度值比PSO算法和PIO算法大大降低。
参考文献
| [1] | 李亮, 王洪, 刘良玉, 等. 微小卫星星座与编队技术发展[J]. 空间电子技术, 2017, 14(1): 1-3. LI L, WANG H, LIU L Y, et al. Microsatellite constellation and formation technology development[J]. Space Electronic Technology, 2017, 14(1): 1-3. (in Chinese) |
| [2] | MAC T T, COPOT C, TRAN D T, et al. Heuristic approaches in robot path planning: A survey[J]. Robotics and Autonomous Systems, 2016, 86: 13-28. DOI:10.1016/j.robot.2016.08.001 |
| [3] | GARCIA M A P, MONTIEL O, CASTILLO O, et al. Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation[J]. Applied Soft Computing, 2009, 9(3): 1102-1110. DOI:10.1016/j.asoc.2009.02.014 |
| [4] | DUAN H B, QIAO P X. Pigeon-inspired optimization: A new swarm intelligence optimizer for air robot path planning[J]. International Journal of Intelligent Computing and Cybernetics, 2014, 7(1): 24-37. DOI:10.1108/IJICC-02-2014-0005 |
| [5] | 林娜, 黄思铭, 拱长青. 基于自适应权重鸽群算法的无人机航路规划[J]. 计算机仿真, 2018, 35(1): 38-42. LIN N, HUANG S M, GONG C Q. UAV route planning based on adaptive weighted pigeon colony algorithm[J]. Computer Integrated Manufacturing Systems, 2018, 35(1): 38-42. (in Chinese) |
| [6] | 胡耀龙, 冯强, 海星朔, 等. 基于自适应学习策略的改进鸽群优化算法[J/OL]. 北京航空航天大学学报, 2020(2020-02-26)[2020-06-17]. https://doi.org/10.13700/j.bh.1001-5965.2019.0603. HU Y L, FENG Q, HAI X S, et al.Improved pigeon group optimization algorithm based on adaptive learning strategy[J/OL]. Journal of Beijing University of Aeronautics and Astronautics, 2020(2020-02-26)[2020-06-17]. https://doi.org/10.13700/j.bh.1001-5965.2019.0603 (in Chinese). |
| [7] | 崔文豪. J2摄动下的卫星编队队形重构与队形保持方法研究[D]. 哈尔滨: 哈尔滨工程大学, 2019: 94-95. CUI W H.Research on satellite formation reconstruction and formation maintenance method under J2 disturbance[D]. Harbin: Harbin Engineering University, 2019: 94-95(in Chinese). |
| [8] | ZHANG S J, DUAN H B. Gaussian pigeon-inspired optimization approach to orbital spacecraft formation reconfiguration[J]. Chinese Journal of Aeronautics, 2015, 28(1): 200-205. DOI:10.1016/j.cja.2014.12.008 |
| [9] | CLOHESSY W H, WILTSHIRE R S. Terminal guidance system for satellite rendezvous[J]. Journal of the Aerospace Science, 1960, 27(5): 653-658. |
| [10] | 连淑君, 唐加会, 杜爱华. 带等式约束的光滑优化问题的一类新的精确罚函数[J]. 运筹学学报, 2018, 22(4): 108-116. LIAN S J, TANG J H, DU A H. A new class of exact penalty functions for smooth optimization problems with equality constraints[J]. Operations Research Transactions, 2018, 22(4): 108-116. (in Chinese) |
| [11] | 崔承刚, 杨晓飞. 基于内部罚函数的进化算法求解约束优化问题[J]. 软件学报, 2015, 26(7): 1688-1699. CUI C G, YANG X F. Evolutionary algorithm based on internal penalty function for constrained optimization problems[J]. Journal of Software, 2015, 26(7): 1688-1699. (in Chinese) |
| [12] | ANTCZAK T. A lower bound for the penalty parameter in the exact minimax penalty function method for solving nondifferentiable extremum problems[J]. Journal of Optimization Theory and Applications, 2013, 159(2): 437-453. DOI:10.1007/s10957-013-0335-3 |
| [13] | HUA B, HUANG Y, WU Y H, et al. Spacecraft formation reconfiguration trajectory planning with avoidance constraints using adaptive pigeon-inspired optimization[J]. Science China Information Sciences, 2019, 62(70209): 1-3. |
| [14] | 聂瑞, 章卫国, 李广文, 等. 基于Tent映射的自适应混沌混合多目标遗传算法[J]. 北京航空航天大学学报, 2012, 38(8): 1010-1016. NIE R, ZHANG W G, LI G W, et al. Adaptive chaotic hybrid multi-objective genetic algorithm based on Tent mapping[J]. Journal of Beijing University of Aeronautics and Astronautics, 2012, 38(8): 1010-1016. (in Chinese) |
| [15] | TAVAZOEI M S, HAERI M. Comparison of different one-dimensional maps as chaotic search pattern in chaos optimization algorithms[J]. Applied Mathematics and Computation, 2007, 187(2): 1076-1085. DOI:10.1016/j.amc.2006.09.087 |
| [16] | 段海滨, 叶飞. 鸽群优化算法研究进展[J]. 北京工业大学学报, 2017, 43(1): 1-7. DUAN H B, YE F. Research progress of pigeon colony optimization algorithm[J]. Journal of Beijing University of Technology, 2017, 43(1): 1-7. (in Chinese) |
| [17] | 周雨鹏. 基于鸽群算法的函数优化问题求解[D]. 长春: 东北师范大学, 2016: 6-8. ZHOU Y P.Function optimization problem based on pigeon colony algorithm[D]. Changchun: Northeast Normal University, 2016: 6-8(in Chinese). |
| [18] | 陶国娇, 李智. 带认知因子的交叉鸽群算法[J]. 四川大学学报(自然科学版), 2018, 55(2): 295-300. TAO G J, LI Z. Cross-pigeon algorithm with cognitive factors[J]. Journal of Sichuan University(Natural Science Edition), 2018, 55(2): 295-300. (in Chinese) |
| [19] | 王日宏, 李祥, 李娜. 基于高斯扰动和混沌初始化的狼群算法[J]. 计算机工程与设计, 2019, 40(10): 2879-2884. WANG R H, LI X, LI N. Wolf pack algorithm based on Gaussian perturbation and chaos initialization[J]. Computer Engineering and Design, 2019, 40(10): 2879-2884. (in Chinese) |
| [20] | 王瑞, 肖冰松. 基于改进鸽群优化和马尔可夫链的多无人机协同搜索方法[J]. 工程科学学报, 2019, 41(10): 1342-1350. WANG R, XIAO B S. A cooperative search method for multiple UAVs based on improved pigeon optimization and Markov chains[J]. Journal of Engineering Sciences, 2019, 41(10): 1342-1350. (in Chinese) |
| [21] | 艾兵, 董明刚. 基于高斯扰动和自然选择的改进粒子群优化算法[J]. 计算机应用, 2016, 36(3): 687-691. AI B, DONG M G. Improved particle swarm optimization algorithm based on Gaussian disturbance and natural selection[J]. Journal of Computer Applications, 2016, 36(3): 687-691. (in Chinese) |
| [22] | 朱德刚, 孙辉, 赵嘉, 等. 基于高斯扰动的粒子群优化算法[J]. 计算机应用, 2014, 34(3): 754-759. ZHU D G, SUN H, ZHAO J, et al. Particle swarm optimization algorithm based on Gaussian perturbation[J]. Journal of Computer Applications, 2014, 34(3): 754-759. (in Chinese) |
