基于启发式遗传算法的近距空中支援超网络结构优化

张 泽，王 瑛，闫孟达，岳龙飞，胡东愿

(空军工程大学空管领航学院， 西安 710051)

1 引言

近距空中支援(close air support,CAS)是一种典型的联合作战行动，指航空兵在与己方部队距离较近、可以直接影响己方部队行动的情况下对目标实施空中突击，以支援陆上和海上作战部队。近距空中支援包括预先计划的近距空中支援和即时性近距空中支援，预先计划的近距空中支援(preplanned close air support,PCAS)指陆军和空军根据预先制定的作战计划和攻击目标申请火力打击，PCAS计划的有效制定有利于把握战场的主动权，因此本文主要对PCAS网络进行优化。优化网络结构对于预警探测、打击引导等作战行动具有重要影响，对网络效率和网络效能的高低起到决定作用。

目前，国内外关于作战信息网络结构优化的研究，主要集中在理论分析、模型构建和算法改进等方面。文献[3]把作战网络信息流运用到遗传算法中，建立信息流算法与模型，对于优化作战网络体系效能具有重要意义；文献[4]通过复杂网络提出作战体系网络连接优化控制方法，仿真分析网络结构对网络效能的影响，结果验证了网络模型的有效性。

已有研究主要集中在对作战网络结构优化方面，但仍存在以下不足：没有根据实际作战特点建立网络模型，仅停留在理想作战层面；仅考虑单个优化目标，没有针对不同层级和整体网络进行优化。本文有两点创新，一是构建CAS超网络基本模型，将基本模型中的邻接矩阵作为启发式信息，对其初始化生成遗传算法的初始种群；第二根据关键节点设置变异概率，提高种群寻优精度和速度。

本文依据超网络理论，以提高网络抗毁性、网络流转效率和全网效能为优化目标，使用遗传算法进行求解，构建CAS信息流转超网络优化模型，对优化后的网络进行仿真分析。

2 CAS超网络

美国科学家Sheffi首次提出超网络(Super-network)的概念，通常指规模巨大、连接复杂、节点具有异质性的网络，或网络中嵌套网络，且存在虚拟节点的边和流等的大型网络。超网络的特征为多层、多级、多维、多流量、多属性等，用于描述“高于而又超于现存网络”的网络。

CAS超网络是指在CAS作战中，作战信息在作战节点之间交互流通的过程，CAS超网络由五层网络组成，包括申请网、情报网、指控网、协调网和火力网，CAS超网络邻接矩阵可记为。

CAS超网络结构是集申请网()、情报网()、指控网()、协调网()和火力网()为一体的作战网络()。作战网络由作战节点()和作战信息()构成，记为=(,)，作战节点分为申请节点()、情报节点()、指控节点()、协调节点()和火力节点()，有=∪∪∪∪。以现代近距空中支援作战为背景，根据节点类型，对CAS作战力量进行分类，作战力量具体情况如表1所示；作战信息分为申请信息()、情报信息()、指控信息()、协调信息()和火力信息()，有=∪∪∪∪。五层网络通过一定的映射规则相互联系，相互作用，得到CAS超网络基本模型如图1所示。

表1 作战力量具体情况Table 1 Specific situation of operational power

续表(表1)

图1 CAS超网络基本模型示意图Fig.1 CAS super-network basic model

3 CAS超网络结构优化模型

CAS超网络结构优化是在初始网络模型的基础上，根据CAS作战目的，以提高CAS作战的灵活性和稳定性为目标，选取优化目标，建立多目标优化函数，通过遗传算法进行寻优，得出最优矩阵。由于现代战场具有极端的动态性，要求CAS作战灵活，能够迅速变更打击目标、战术和调整使用合适的武器弹药，CAS必须响应迅捷，因此以提高网络的抗毁性和网络效率为优化目标。

3.1 抗毁性

网络的抗毁性是指当遭受破坏时，网络维持或恢复其性能到一个可接受程度的能力。这种破坏可以是确定性故障，也可以是随机性故障。抗毁性可用来衡量网络的可靠性。

1) 等效最短路径数

衡量网络的抗毁性，通常选取连通性作为测量指标。全连通网络是抗毁性最强的网络，网络结构十分稳固。比较与全连通网络的结构差异，差异越小说明网络结构越紧凑，抗毁性越强。节点间的等效最短路径数可以计算与全连通网络的结构差异，等效最短路径数可以表示为

(1)

其中，表示网络中节点与之间最短路径的长度，指节点与之间长度为的最短路径条数，()为与具有相同节点数||的全连通网络′中，节点与之间长度不大于的路径条数。当与两节点之间有直接连边时，=1，否则=0，对于全部节点对(,)，如果=1，那么该网络是全连通网络。

根据等效最短路径数，可以将抗毁性表示为

(2)

当(′)=1时，表示全连通网络′中任意2个节点之间等效最短路径数为1，抗毁性最强；非全连通网络的抗毁性(′)∈(0,1)，(′)越大，抗毁性越强。

以抗毁性最强作为网络的优化目标，有

(3)

2) 约束条件

网络连边的增加可以为信息流转提供更多路径，避免节点遭损毁后信息传输中断，但连边过多会导致信息拥堵，降低信息传输效率，因此应该对网络连边总数进行限制。网络各节点在网络层级、系统功能等因素影响下，具有一定的连接容量值和节点饱和度。

节点饱和度()是节点连接容量值和连接度值()的分段函数。在时刻，节点的饱和度函数为

()=-()

(4)

其中，()∈[0,]。当()=0时，()=，说明节点处于饱和状态，不会与其他节点相连；当()>0时，()<，说明节点可以增加连边。

因此，节点的饱和度约束可以表示为

()>0

(5)

网络总连边饱和度约束为

||≤80

(6)

3.2 网络效率

网络效率表示信息在网络上传输的有效程度，通常用平均最短路径作为优化目标。

1) 平均最短路径

平均最短路径指任意2个节点之间最短路径的平均值，用来衡量网络中信息的流转效率。平均最短路径越长，节点之间交流所需成本越高，效率越低；反之，成本越低，效率越高。可表示为

(7)

其中，||表示网络中节点总数，, 指节点与之间的最短路径数。

以平均最短路径最短作为优化目标，有

(8)

CAS作战中，作战单元之间相互联系，作战信息在作战单元之间流转交互，在申请网、情报网、指控网、协调网和火力网之间建立交互关系，CAS超网络结构的改变会影响平均最短路径的长度。

2) 约束条件

平均最短路径取决于CAS超网络结构中对网络效率影响重大的网络。其中，情报网、指控网和火力网是负责情报传输、指挥控制和火力打击功能，是决定网络效率高低的关键，有

∈{,,}

其中，表示矩阵中的元素。

4 启发式遗传算法求解CAS优化问题

4.1 遗传算法简介

遗传算法是根据自然界中生物进化规律提出的，是一种通过模拟自然进化过程搜索最优解的方法。该算法利用计算机仿真运算，将问题的求解转换成染色体基因的交叉、变异等过程。传统遗传算法存在一些缺陷，本文在遗传算法的基础上，根据网络的邻接矩阵和关键节点设计改进遗传算法求解CAS优化问题。

4.2 CAS超网络的启发式遗传算法设计

1) 启发式信息初始化生成初始种群

根据CAS超网络，构建邻接矩阵。若两节点之间有连边，用1表示；若两节点之间没有连边，用0表示。这样生成网络的邻接矩阵为，将作为启发式信息，对每一位以5的概率随机进行取反操作，生成至共99个初始网络，最终得到初始种群包含个体至。

2) 适应度函数

适应度是用来度量种群中个体优劣的指标，适应度函数的设定决定算法的收敛程度和目标函数最优解。本文适应度函数由抗毁性和网络效率两部分组成，将网络效率目标函数转换为求最大值问题，可以得到适应度函数：

(9)

其中为常数，为保证适应度函数为正，取=4，越大，说明个体越好。

3) 选择机制

选择是从当前种群中选择优秀的个体，作为父代参与下一代繁衍，从而迭代出最优秀的个体。一般遗传算法采用轮盘法居多，但会导致高适应度个体过多，导致过早收敛。

为克服过早收敛问题，本文采用精英选择法和比例选择法选择进入下一代中的个体，首先使用精英选择法选择适应度排名前30的个体不经选择直接进入下一代，其余个体使用比例选择法选择30%的个体进入下一代。将2种方法结合可提高种群优化的开拓能力，避免过早收敛。

4) 关键节点变异机制

变异是指在群体中随机选择一部分个体，改变其基因型。为提高算法的寻优精度，给关键节点和其余节点设置不同的变异概率。由多属性决策的节点重要性综合评价方法得出CAS超网络中节点的重要程度，其中，重要性排名前6的节点分别为地面情报中心()、控制中心()、空中联络官()、作战参谋官()和援机中的2个长机(()、())。本文给关键节点设置2的变异概率，其余节点设置1的变异概率，以增大对关键节点连边的探索。

4.3 遗传算法求解CAS问题步骤

首先生成初始种群，在CAS超网络邻接矩阵的基础上，进行种群初始化；然后评估个体适应度，将适应度按从大到小排序，根据精英选择法和比例选择法选择个体；对选择出的个体进行交叉变异操作，变异完成后，计算新一代种群的适应度，比较个体适应度大小，依次迭代，当连续5代内最优值不变或迭代500次时算法终止，迭代结束。本文遗传算法流程如图2所示。

图2 遗传算法流程框图Fig.2 Genetic algorithm flow chart

5 仿真实验

5.1 仿真设置

由CAS超网络模型，设置参数||=28，边长度设为1，连边总数||不大于80，网络节点的连接度容量如表2所示。抽象CAS超网络的层级网络拓扑结构，如图3所示。

表2 CAS超网络节点连接度容量Table 2 CAS超网络 node connectivity capacity

图3 CAS超网络拓扑结构示意图Fig.3 CAS super-network topology structure

5.2 优化结果

根据设置的参数值，采用遗传算法，运用Matlab软件求解，得到优化后的邻接矩阵，将邻接矩阵转化为CAS超网络网络拓扑结构，如图4所示。

图4 CAS超网络优化拓扑结构示意图Fig.4 CAS super-network optimized topology structure

相较于图3，优化后的网络拓扑结构更为复杂，网络连边增多，个别节点之间信息交互关系发生改变。优化前后CAS超网络拓扑结构性能如表3所示。

表3 CAS超网络优化前后拓扑结构性能Table 3 Comparison of topology performance before and after CAS super-network optimization

由表3可知，在CAS超网络优化过程中，网络连边较优化前有了显著增加，抗毁性增强，网络效率提高，整体网络的可靠性和信息交互的灵活性有很大提高。

5.3 实验结果分析

为了评价启发式遗传算法的有效性，采用Matlab软件仿真得到适应度值作为测试结果。

图5将平均适应度与最大适应度收敛情况进行对比，结果显示当适应度值为2.8左右时，适应度趋于收敛。

图5 遗传算法适应度函数值曲线Fig.5 Genetic algorithm fitness function value

图6将启发式遗传算法和随机种群遗传算法的平均适应度函数进行对比。图6中，随机种群生成大部分无效种群，不满足约束条件，其平均适应度函数值收敛性较差，寻优精度低，启发式遗传算法收敛速度快，寻优精度更高。

图6 遗传算法平均适应度函数值曲线Fig.6 Average fitness function value of genetic algorithm

对优化前后的CAS超网络拓扑结构特性进行对比分析，进一步验证优化后CAS超网络的有效性，选取节点的超度分布、介数、聚类系数3个拓扑指标仿真分析网络的特性。

1) 超度分布

节点的超度可以表示为与该节点直接相连的其他所有节点的总数，记为，节点的度为的概率可用超度分布()来表示，描述了整个网络中所有节点度的分布情况，可以有效反映战场中信息流转动态变化的过程，表示为

(10)

其中：为超度值为的节点个数，表示超网络中节点的总数。在CAS作战中，超度值较高的节点处于各自子网的核心，作战信息在此处交互流通，信息关系复杂性高。计算超度有利于识别出CAS中重要的作战单元，对保护关键作战单元和优化战术具有重要意义。

优化前后CAS超网络拓扑结构的超度分布如图7所示。

图7 优化前后CAS超网络拓扑结构的超度分布曲线Fig.7 The super distribution curve of CAS super-network topology structure before and after optimization

由图7可知，优化前后节点分布趋势大致相似，均由大变小，当度值分别为3和5时，节点超度分布达到最大，表明CAS超网络拓扑结构整体呈现不均匀分布。优化后的网络节点度值数量明显增多，说明信息交互更加丰富，网络拓扑结构复杂度提高。

2) 介数

节点的介数是指经过该节点的最短路径的数量占整个网络中所有最短路径的数量的比例，超边的介数反映了经过该边的所有最短路径的比例。介数体现了节点和边在整个网络交互传输中的重要程度，反映了节点在信息流动中的作用，表示为

(11)

优化前后CAS超网络拓扑结构的介数分布如图8所示。由Matlab计算可知，优化前后节点的介数平均值分别为97.929和31.929，表明优化后节点对信息流动的影响力较优化前小。由图8可知，优化后的介数分布较优化前更加集中，优化前介数波动幅度较大，优化后介数分布较平稳。这说明优化后网络中经过每个节点的个数占最短路径的比例减小，节点对战场信息流转的影响基本一致。

图8 优化前后CAS超网络拓扑结构的超度分布曲线Fig.8 The betweenness curve of CAS super-network topology structure before and after optimization

3) 聚类系数

聚类系数是指节点所有邻居节点之间的实际连边条数与理论连边总条数的比例，集聚系数可以描述网络中节点的集聚情况，反映网络的紧密程度，表示为

(12)

式(12)中：表示超三角形的数目，表示长度为2的路径数目。1个超三角形指的是由3个不同的顶点和3个不同的超边构成的序列，3个顶点是相邻的，2路指的是步长为2的路，在路中顶点和超边是相异的。对CAS作战而言，聚类系数高说明作战节点之间连接紧密，内部作战信息关系复杂性高于其他节点，作战中双方对抗激烈、作战节奏快，整个CAS作战体系连接紧密度高。

优化前后CAS超网络拓扑结构的聚类系数分布如图9所示。

优化前后，网络平均聚类系数分别为0.086和0.192，优化后网络聚类系数更高，说明优化后网络的节点分布较为集中，网络更为紧密。由图9可知，优化后网络的聚类系数值都集中在0～0.4，较优化前分布均匀。这说明优化后的网络不仅信息连边大幅增加，节点之间信息交互更加频繁、联系更加紧密。

图9 优化前后CAS超网络拓扑结构的超度分布曲线Fig.9 The clustering curve of CAS super-network topology structure before and after optimization

6 结论

基于超网络理论，构建CAS超网络结构，提高了CAS作战网络的稳定性和灵活性，选择抗毁性和网络效率作为优化目标，通过启发式遗传算法求解运算，建立优化后的CAS超网络拓扑结构，仿真分析优化前后网络的超度分布、介数和聚类系数，结果表明优化后的网络具有更高的抗毁性和更快的网络效率。下一步将考虑节点和信息连边的多样性，研究节点和连边类型发生变化对CAS超网络的抗毁性和网络效率产生的影响。