基于蚁群的天基预警多目标优化算法

程禹， 魏承， 游斌弟， 赵阳， 吴限德

(1.哈尔滨工业大学 航天学院，黑龙江 哈尔滨 150001； 2.哈尔滨工程大学 航天与建筑工程学院，黑龙江 哈尔滨 150001)

天基红外系统具有覆盖范围广、预警速度快、作战用途多等特点，在反导信息保障中占据重要地位[1],受到了美国、俄罗斯等军事强国的高度关注和大力投入[2-3]。天基预警系统传感器调度优化是天基预警系统的关键问题。多传感器调度优化是一个存在监控冲突的多目标、动态、复杂多约束的非线性优化问题[4]。在传感器调度问题中，优化目标之间存在冲突，如何在改善目标评价的同时不使另一个目标的评价恶化，实现多个目标共同优化，这就是多目标优化问题(multiobjective optimization problem，MOP)[5]。与单目标优化问题不同，在解决MOP问题时，需要寻找所有目标中最权衡的解[6]。

国内外实验室、科研机构和工程单位已经开发了许多基于规则的元启发式算法[7]解决多传感器调度优化问题。然而，尽管它们具有高效率的特点，但元启发式算法也存在若干限制，例如，大多数算法在每次运行中生成单个解决方案，并且按照固定逻辑进行决策。这些局限性推动了替代解决方案技术的发展。

多目标进化算法(multiobjective optimization evolutionary algorithm,MOEAs)是基于进化的元启发式算法，是解决高度复杂的MOP问题的常用方法之一[8]。文献中提供了多种MOEAs方法，例如非支配排序遗传算法Ⅱ(NSGA-Ⅱ)[9]或基于分解的多目标进化算法(MOEA/D)[10]。MOEAs采用了基于帕累托排序的选择机制，即基于帕累托最优性对解决方案进行排名，使非支配解决方案被选择的概率更高。然而，基于帕累托的MOEAs在处理具有多目标的MOP问题时表现不佳[11-12]。

蚁群优化算法(ant colony optimization,ACO)最初的目的是解决组合优化问题，多年来ACO不仅应用在天基预警系统中[4]，同时在空间碎片清除、中继数据传输和地面目标观测等航天领域也有比较成熟的应用[13-15]，解决了动态任务分配和多目标优化等关键问题[5，16]。虽然，多目标蚁群优化算法(multiobjective optimization ant colony optimization,MOACO)已经广泛应用在多目标优化问题的研究[17]，但是，MOACO是一个离散优化算法，对于天基预警任务规划这种多目标连续优化问题，需要进行改进。本文引入了基于指标的连续搜索空间的多目标蚁群优化算法(iMOACO)。该算法在最先进的MOEAs方面具有足够竞争力[18]。

1 天基预警连续搜索域蚁群多目标优化算法

1.1 搜索算法ACO_R

基于指标的连续搜索空间蚁群优化算法是一种基于ACO元启发式的多目标优化算法。对于天基预警这种连续问题，ACO的一个典型拓展是ACO_R，与遗传算法、概率学习方法和其他与蚂蚁相关的算法相比，ACO_R已呈现出良好的计算结果。ACO_R还被用作2个连续领域MOACO算法的搜索方法。因此提出一种以ACO_R为搜索算法的天基预警规划算法。

1.2 基于R2的天基预警方案排序算法

给定Pareto前沿近似值A，指标的一元版本定义为：

(1)

天基预警方案排序算法的主要目的是创建一个非显性排序方案。首先，优化一组目标的解决方案，并将解决方案放在排序的最前面。然后，删除这些已排名的点，并以相同的方式分配第2个方案，依此类推，直到没有更多的点需要进行排名。该方案的优点是在选择压力较大的问题上都具有良好的性能。

关于式(1)中效用函数的选择，本文使用了价值标度函数(achivement scalarizing function，ASF)。ASF的定义为：

(2)

式中：r为参考向量；λ为权重向量，维数均为Λ={λi|i=1,2，…,N}。为了定义效用函数集，需要创建一组权重向量Λ={λi|i=1,2，…,N}。使用创建网格{m,h}的单纯形网格设计(simplex lattice design,SLD)计算Λ，其中m是目标数，h是比例参数。这个结构由每个目标函数的所有可能的比例组合组成。因此，权重向量的系数是在0和1之间取h+1个均匀分布的值，即：

(3)

图1 基于R2的天基预警方案排序算法Fig.1 Sorting algorithm of space-based early warning scheme based on R2

在基于R2的天基预警方案排序算法中，假设规划结果集合p.F:中的每个规划结果p.F:都具有以下结构：

p.F: 目标向量；p.α: 权重向量λ的当前价值；p.u*: 获得最优价值；p.rank: 由算法分配的解的排列结果。

1.3 更新参考点

引入了2个重要的参考向量：理想向量z*和最低点向量znad。前者保留每个目标的最小值，后者由帕累托最优前沿的解得到的最大目标值组成。这些向量在目标的规范化过程中特别相关。

基于R2的天基预警结果排序算法要求对目标向量进行归一化，以生成排序。进行归一化：

(4)

本文提出了一种机制，分别生成理想向量和最低点向量的统计近似值zmin和zmax。在每次迭代中监控当前总体的最低点，确定距离真正帕累托前沿的解有多接近。方差越高代表解离帕累托前沿越远。

图2 更新参考点Fig.2 Update reference point

1.4 基于指标的天基预警连续搜索空间蚁群优化算法

在本节中，描述了用于构建基于指标的天基预警连续搜索空间蚁群优化算法的基本机制(参见算法3)。该方案是ACO元启发式算法的一个推广，用于求解以ACO_R为搜索引擎，无变量相关机制的连续多目标优化问题。该优化算法的2个主要特点如下：1)使用了一个不同的信息素存档方式，它根据方案排序算法存储最好的解决方案；2)信息素更新过程促进了新创建的解决方案与存储在存档中的当前解决方案之间的竞争。

每个蚂蚁a∈A和信息素p∈Γ，其中A表示一组蚂蚁，Γ表示信息素档案，具有以下结构：

x: 决策变量；F: 目标向量；Fnorm: 归一化目标向量；α: 当前利益值；u*: 最优利益值。

天基预警连续空间蚁群优化算法需要6个参数：Gmax、q、ε、ξ、α和h。Gmax是最大的蚁群代数。参数q和ξ由基于ACO_R的搜索引擎使用。参考向量的更新需要参数α和ε，分别是方差阈值和公差阈值。最后，h是用于在SLD上构造单纯形格的比例参数，以创建N个权重向量集。N同样被用作蚂蚁数量和信息素存档Γ的基数。这一决定是基于R2指标的μ-最优分布，即如果有μ≥N的解决方案μ和权重向量N，解决方案μ-N将不会对R2指标值产生影响。

如图4所示是天基预警连续搜索空间蚁群优化算法描述。首先计算N个权重向量集，然后根据信息素存档Γ使用统一分布进行初始化并计算z*和znad。然后创建并初始化记录实例。使用天基预警方案排序算法对Γ中的观测方案进行排序，确定解的质量。之后执行算法的主循环，直到超过最大迭代次数。每个蚂蚁使用ACO_R的标准机制生成一个新的预警观测方案。然后计算理想观测方案和最低点观测方案的统计近似值。在这之后描述了信息素更新过程。设Ψ=A∪Γ。然后，对所有解的目标向量进行归一化，目的是通过天基预警方案排序算法进行排序。随后，根据如下指标：切换次数、疲劳度和观测时长，按递增顺序对Γ进行排序。排序将确保把些接近帕累托最优集的解排在最前端。将前N个观测方案复制到存档中然后删除了Γ的所有观测方案。如上所述，信息素的更新过程促进了新创造的信息素和旧信息素之间的竞争，目的是保留那些使R2指标值最大化的观测方案。在搜索过程结束时，返回Γ的内容作为帕累托前沿近似值。

图3 天基预警连续搜索空间蚁群优化算法流程Fig.3 Ant colony optimization algorithm flow of space-based early warning continuous search space

图4 基于规则的元启发式算法计算结果Fig.4 Results of rule based meta heuristic algorithm

下面分析天基预警连续空间蚁群优化算法的计算复杂性。新解决方案的产生需要O(N2n)。更新参考向量需要O(Nm)。对A和Γ以及目标向量做标准化需要O(Nm)。天基预警方案排序算法的计算复杂度是O(N2(logN+m))(其中N=|P|，P为规划结果集合)。从Γ中移除之前的解决方案需要O(1)。从ψ中复制最好的前N个值到Γ中需要O(N(n+m))。最后，再次执行天基预警排序算法，这里需要O(N2(logN+m))，其间，排序工作占用了O(NlogN)。因此，天基预警连续空间蚁群优化算法每步迭代的计算复杂度为O(N2(logN+m+n))，存储数据的计算复杂度为O(N(n+m))。

2 仿真测试与分析

2.1 仿真场景设计

本文参考了美国低轨天基预警系统STSS(space tracking and surveillance system)，即空间跟踪与监视系统，其主要任务是弹道导弹初段，中段及末段跟踪与识别。

2.1.1 天基预警系统组成

本文仿真场景星座采用的是Walker-Delta构型，用卫星数目T、轨道面数P、相位参数F描述，用来表示，整个系统由24颗卫星组成。

天基预警系统的星座构架T/P/F为24/3/1，地1个轨道面初始时刻的升交点赤经为0°，第1个轨道面第1颗卫星初始时刻的幅角为0°，为了满足全球覆盖，所以采用极地轨道，其轨道倾角为90°；每颗卫星的轨道高度为1 600 km。

2.1.2 天基预警系统的工作方式

天基预警系统中每颗低轨卫星采用临边观测跟踪传感器，采用短波长探测方式。临边以上的工作方式指的是自卫星与地球切线开始向切线上方扫描的过程，临边即沿切线的含义。临边观测本质上是一种基于空域的观测方式。

2.2 算法对比

本节基于该场景将天基预警连续搜索空间蚁群多目标优化算法与基于规则的元启发式算法[7]以及动态蚁群算法[19]进行对比。

天基预警任务中，由于星座均匀分布，因此目标分布越集中，预警系统的可用资源越少，对算法的要求越高。因此，为了全面比较3种算法，将导弹设置为相同发射点不同落点，并设计了资源充足，资源紧缺和资源严重不足3种场景。算法评价值为优化目标的加权和：

(5)

2.2.1 资源充足场景仿真

资源充足场景选择2枚单弹头的二级导弹作为观测目标。2枚导弹选择了相同的发射点，不同的飞行高度和不同的目标点。这种情况对任务规划算法的压力较低，以此来比较3种算法在资源充足场景中的能力。

1)弹道参数

2枚导弹选择相同发射点经度：100°、纬度：41°、高度：1 km，同时，弹道高度和目标点相距较远，使得预警资源比较充足，通过下面的计算结果比较3种算法的不同能力。

表1 导弹参数Table 1 Missile parameters

2)计算结果

资源充足场景中，3种算法总观测时长比较接近，均可以获得长时间覆盖目标的观测结果。同时，多目标蚁群算法的传感器切换次数和单星观测时长均小于前2种算法，显示出优异的优化性能，在资源充足场景中更合理的利用观测资源。

表2 评价指标Table 2 Evaluating indicator

2.2.2 资源紧缺场景仿真

资源紧缺场景选择5枚中远射程导弹作为观测目标。5枚导弹选择了相同的发射点，不同的飞行高度和不同的目标点。相比于上一个场景，本场景对资源的需求量更大，以此来比较3种算法在资源紧缺场景中的能力。

1)弹道参数

5枚导弹选择相同的发射点经度100°、纬度41°、高度1 km，并且选择中远射程导弹，相比于上一场景中的近程导弹，对预警系统的资源需求量更大。

2)计算结果

资源紧缺场景中元启发式算法虽然也获得了满足覆盖时间的优化结果，但单星观测时长平均值为827.2 s，高于另2个算法，传感器疲劳度较高，因此评价值最低。动态蚁群算法的优化结果拥有最长的目标覆盖时间，同时单星观侧时长低于元启发式算法，因此评价值较高。多目标蚁群算法的优化结果不仅平均切换次数最少，同时单星观侧时间也远低于前两种算法，对3种优化目标的均衡性和寻优性最好，因此高评价值最高。

图5 动态蚁群算法计算结果Fig.5 Results of dynamic ant colony algorithm

图6 连续域蚁群算法结果Fig.6 Continuous domain ant colony algorithm results

表3 导弹参数Table 3 Missile parameters

2.2.3 资源严重不足场景仿真

资源严重不足场景选择8枚远程导弹作为观测目标。8枚导弹选择相同发射点经度100°、纬度41°、高度1 km，并同时发射，因此预警系统资源无法同时观测所有目标，导弹飞行高度分布在1 200～3 100 km不等，射程在3 406～6 089 km不等，在满足资源严重不足的条件的同时，丰富弹道种类，以检验算法普遍性。此场景仿真目的是对天基预警系统传感器资源严重不足的情况进行仿真，测试3种算法在资源严重不足场景中的能力。

1)弹道参数

图7 基于规则的元启发式算法计算结果Fig.7 Results of rule based meta heuristic algorithm

图8 动态蚁群算法计算结果Fig.8 Results of dynamic ant colony algorithm

图9 连续域蚁群算法结果Fig.9 Continuous domain ant colony algorithm results

表4 评价指标Table 4 Evaluating indicator

表5 导弹参数Table 5 Missile parameters

2)计算结果

资源严重不足场景中，元启发式算法的总观测时长，但同时存在切换次数多和单星疲劳度高等问题，元启发式算法为固定逻辑搜索算法，在资源压力较大时，存在多目标优化性能弱的问题。动态蚁群算法通过随机寻优的方式，优化结果中切换次数和疲劳度2个优化目标均优于元启发式算法，但仍没有多目标蚁群算法的寻优结果理想。多目标蚁群算法在满足总观测时长的前提下，切换次数和疲劳度均低于另外2种算法，可见，在资源严重不足的场景中，多目标蚁群优化算法具有更好的优化性能。

图10 基于规则的元启发式算法计算结果Fig.10 Results of rule based meta heuristic algorithm

图11 动态蚁群算法计算结果Fig.11 Results of dynamic ant colony algorithm

图12 连续域蚁群算法结果Fig.12 Continuous domain ant colony algorithm results

表6 评价指标Table 6 Evaluating indicator

3 结论

1)本文针对天基预警系统传感器调度问题中，本文根据任务中的约束情况，提出了一种天基预警连续搜索空间多目标蚁群优化算法，解决了传统蚁群算法在天基预警任务规划中存在多目标权衡能力差，连续搜索空间计算效率低等问题。

2)本文以扩展蚁群算法为搜索引擎，采用基于R2指标的天基预警方案排序算法来寻找最优解。该算法适用于天基预警星座系统对弹道导弹等具有红外特性运动目标的跟踪方案优化问题。

3)本文参考美国天基预警系统设计仿真场景，并将算法与元启发式和动态蚁群算法在资源充足、资源紧缺和资源严重不足3种仿真场景中进行对比仿真，仿真结果基于蚁群的天基预警多目标优化算法在3种场景中均表现出良好的优化性能。