基于蚁群算法的负载优化方法研究

于尧，赵忠文，郭皇皇

（装备学院复杂电子系统仿真实验室，北京101416）

为了充分挖掘并行仿真潜力，实现负载优化是提升并行仿真效率的关键问题。一般解决方式分为动态负载平衡和静态负载平衡两种算法，动态负载平衡[1-8]是一种通用的平衡方法，但这种方法本身存在通信开销较大的问题，因此在特定的应用领域，静态负载平衡设计一般比动态均衡算法更有效。在静态负载平衡技术中，文献[9]提出规则分块算法和不规则分块算法相结合的方法，从图论的角度讨论了静态负载平衡问题，文献[10-16]提出了基于蚁群算法的调度策略，提高了并行计算性能；文献[17]提出基于最大-最小蚁群算法的模糊分类设计方法，实现了精确性与解释性的折衷。但相关文献对于仿真中存在的通信负载平衡问题研究相对较少，因此本文针对并行仿真通信负载的优化问题进行研究。

由于模型间的复杂交互，使通信负载和计算负载的测试及优化变得繁琐及困难，本文将状态通信问题转化为模型间的交互作用，将模型的计算负载转化为模型复杂度问题，通过蚁群算法将交互频繁的仿真模型聚合到相同的处理器上，以减少处理器间模型消息传递的通信开销，采用遗传算法快速搜索优势，以此弥补蚁群算法初期信息素匮乏导致算法收敛速度慢的缺陷。充分发挥多核处理器优势，还需满足不同处理器总模型复杂度均衡，从交互作用及模型复杂度两个方面实现负载优化。

1　负载优化问题的简化

仿真模型如何映射到多核处理器将会对仿真效率有很大的影响，由于同一个处理器上模型的通信开销将远小于不同处理器的通信开销，因此应当将交互频繁的仿真模型指派到同一个处理器上，以减少通信负载，为充分发挥多核处理器计算能力，每个处理器应根据自身处理能力以及模型的计算量进行适度映射。

由于模型间的状态通信以及模型计算量在整个动态仿真中是变化的而且难以准确测量或描述，因此可将该问题简化，将模型的通信问题转化为模型交互作用问题，将模型的计算负载转化为模型复杂度问题。模型的交互作用体现在传递消息上，传递消息的越频繁，交互作用就越大，两个模型间的通信越就紧密，因此将交互作用频繁的模型聚合在同一个处理器上，将会减少通信开销，模型的交互作用可根据模型的交互结构进行静态分析计算。模型复杂度反映的是模型的计算量，模型设计的越复杂，可以认为模型的计算量越大，模型复杂度可采用群决策法进行分析计算，然后根据层次分析法可计算出各模型复杂程度的权重，该权重值即作为模型复杂度。但实际中模型的计算量不仅和模型的复杂度有关，还与模型在仿真中执行的频率有关，因此可通过交互作用进行补偿，即交互作用越大计算量越大。最后将交互作用频繁的模型聚合在一起，映射到同一个处理器上以减少通信开销，为充分发挥多核处理器性能，应保证每个处理器聚合后的模型复杂度相差较小。

1.1　交互作用的计算

静态分析方法是围绕仿真任务进行静态分析的一种方法，所谓静态指的是仿真运行前进行的处理器映射，在运行的过程中不作调整，直到运行结束为止。通过仿真任务在处理器上的合理映射，以达到仿真系统的综合性能最优。

为了让交互频繁的模型映射到相同的处理器，我们可将模块间的交互作用转化为关系距离的概念，交互作用越大，两者的关系距离则越小，按照关系距离对模型进行聚合，交互作用转化为距离公式如式（2）所示，其中dijnew表示关系距离。

1.2　模型复杂度的计算

群决策也称为多人决策，它是将不同知识结构及不同经验的决策者集中在一起，弥补个人知识及经验的不足的科学决策方法。在一个群决策过程中，大多要求各个决策者给出因素的评价分值或是比较的结果等。对于模型的复杂度的确定可根据模型的相互触发关系、模型的内部设计结构、以及模型程序设计结构进行比较分析，形成决策者对各模型复杂程度的判断矩阵。其模型复杂度比较的评语集应如表1所示。

表1　模型i对模型j复杂度的评语集

2　基于改进蚁群算法的处理器映射

为了让交互频繁的模型映射到相同的处理器上，我们首先需要对模型进行排序，排序的原则就是保证两两模型间的交互作用尽可能大，即模型间总的交互作用最大。我们将模块间的交互作用转化为关联距离的概念，交互作用越大，两者的关联距离则越小，从而将每个处理器交互作用最大问题转化为关联距离最短问题。对于这类问题概率搜索算法有其独特的优势，但也有其明显的缺陷，因此本节首先利用遗传算法全局搜索的优势对蚁群算法的初始信息素值进行修正，解决了蚁群算法前期由于初始信息素过低而引起的全局搜索收敛慢的问题，再利用蚁群算法的反馈机制寻找模型排序的最优解。为了充分发挥多核处理器的并行能力，需要将闭合排序按照关联距离的大小进行切割聚类，从而保证每个组的交互作用尽可能的大，同时需要根据每个模型复杂度及每个处理器的能力进行计算负载平衡，从而让每个处理器能够充分发挥其计算能力。

2.1　改进的蚁群算法设计

1）遗传算法编码对模型的关联距离进行二进制编码，生成距离矩阵D，起始点到目标结束点的路径序列作为一条染色体的编码，每个染色体都代表了一个完整模型交互作用距离的路径。

2）适应度函数设定染色体g的适应度函数如式（4）所示，其中的Dkikj表示第i个模型到第j个模型的距离。

3）选择操作采用轮盘赌选择方法，从旧群体按概率选择到新群体当中。

4）交叉操作两条染色体随机选择一个公共点作为交叉点，从起始点到交叉点的节点顺序保持不变，将交叉点与目标节点间的顺序相互交换。

5）变异操作一条染色体中任选两个点进行位置互换。

6）遗传算法结束在遗传算法的迭代过程中同时统计进化率，公式为

设遗传算法迭代次数为N，若连续三次进化率都小于最小进化率时，则停止遗传算法迭代过程，进入蚁群算法。

7）遗传算法对蚁群算法信息素的修正选择遗传算法结果的适应值最高的前10%条路径V，作为蚁群算法的初始路径，由于遗传算法没有信息素值，所以定义τF=k∙F（g）为遗传算法产生的信息素值，k为常数，当有多条路径经过仿真模型位置时，τa需要进行叠加。因此，蚁群算法的信息素初值为τs=τa+τF，τa为常数。

8）目标点转移概率采用轮盘赌原理的路径选择策略，见式（6），式（6）中的为t时刻蚂蚁k从模型i转移到模型j的概率。其中ηij（t）为启发函数，表示蚂蚁从模型i转移到模型j的期望程度；allowk（k=1，2，…，m）为蚂蚁k待访问模型的集合；α为信息素重要程度因子，简称信息素因子，其值越大，表明信息素强度影响越大；β为启发函数重要程度因子，简称启发函数因子，其值越大，表明启发函数影响越大。

9）信息度更新规则蚂蚁在行走的同时，信息素的强度也在挥发而逐渐消失。式（7）中的ρ（0<ρ<1）表示信息素的挥发程度，信息素浓度为

其中式（8）中的Q为信息素常数，表示蚂蚁循环一次所释放的信息素总量；Lk为第k只蚂蚁经过路径的总长度，并记录最短路径时模型的连接顺序。

2.2　模型聚类与处理器的映射

改进的蚁群算法按照总交互作用最大，其意义是两两模型间的交互作用也将越大，从而得到各模型连接的一个封闭的关联环，关联环上每个点代表了一个仿真模型，每个边代表仿真模型间的关联距离，整个关联环点的顺序体现了在总关联距离最小时，仿真模型的连接顺序，如图1（a）所示。

如果仅考虑通信的切换开销最小，将所有的模型映射到同一个处理器上，显然通信的切换开销将是最小的，但是多核处理器的性能显然没有发挥出来，因此还需要先将关联环进行适当的划分，将交互频繁的模型聚类，然后将每段的模型映射到相应的处理器上，从而充分发挥多核处理器的并行计算优势。

图1　蚁群算法的关联环示意图

1）关联环切割

关联环的分割的过程实际是将交互频繁的模型聚类的过程，根据关联距离的大小进行切割的，其中关联距离为无穷大的必须进行切割，这部分表示模型之间没有任何交互作用，通常是模型是区域隔离的，例如某个地面雷达站只会定位其探测范围内的飞机的位置，而距离其较远未知的飞机与该雷达如果没有任何交互，因此他们的关联距离才会为无穷大，因此先进行切割。然后依次按照关联距离的由大到小将关联环进行切割，如图1（b）所示，直到发生断开边的模型存在紧密的交互作用后停止切分（设置关联距离小于某一阈值即停止），我们可认为剩余连接的模型都是交互频繁的。

2）处理器的映射

切割后的n组模型需要再一次重组到m个处理器上，为了充分发挥处理器的计算能力，处理器的映射应该考虑计算负载平衡，其目的在于让所有处理器尽量在相同的时间根据各自的处理能力完成各自相应的任务量。在此我们忽略并行仿真中每个处理器等待其他处理器的消息的时间，仅考虑处理器的效率因素，分配给处理器相应的任务量，即处理效率即比为任务量分配比，可按照式（9）计算每个处理器应分配的任务量，其中P代表处理器的计算能力，C代表聚合后的各段模型总复杂度，右下标数字代表处理器标号。

然后根据式（10）检验每个处理器的计算负载是否平衡，其中α为允许的误差范围，其中i为处理器标号，其取值范围为1，2…m。

3　实验验证及分析

实验算例采用的是某个导弹突防仿真，对敌方分布的5个目标群分别使用128/256/314/512/640枚导弹进行目标群轰炸，每个目标群含有一套雷达干扰设备，导弹分配到5个目标群数量比为26:26:26:25:25，采用上述方法将仿真模型映射到多核处理器进行并行仿真。

1）模型间交互作用及模型复杂度

将该仿真分成5个子任务，D1R1、D2R2、…、D5R5，其中D代表导弹，R代表雷达设备，导弹具有移动模型，雷达具有决策模型、干扰模型和移动模型，模型的t、p、s以及模型间的交互作用计算如表2所示，未说明模型间交互作用记为0；通过群决策法可得4个模型复杂度分别为0.53、0.11、0.08、0.29。

表2　模型间的交互作用

2）蚁群算法的聚类

按照式（2）将交互作用转化为关系距离，按照式（4）-（8）的蚁群算法将模型进行排序，然后根据关联距离的大小将模型聚类，停止切分的的关联距离阈值设置为R1-R5的模型间交互作用的最小值。利用MATLAB实现改进的蚁群算法的模型聚类的过程，其实验参数设定如表3所示。

表3　实验参数设定

MATLAB的仿真结果如图2所示，其中1-5分别代表D1-D5的移动模型，6-8、9-11、12-14、15-17、18-20分别代表R1-R5的3个模型。比较传统蚁群算法和改进的蚁群算法，5次实验的平均运行时间分别由20.40 s提高到11.88 s，验证了算法改进的有效性。

图2　模型交互作用的聚合图

3）处理器的映射

以128个导弹的处理器分配为例，根据每个处理器的模型复杂度平衡原则将模型映射到处理器上。映射到四核和八核处理器上，结果如表4和表5所示。

表4　四核处理器的模型映射关系

表5　八核处理器的模型映射关系

4）仿真实验验

基于ROSS仿真引擎对上述模型进行实现，将模型分别映射到处理器为四、八核的处理器上进行运行，并与串行仿真进行比较，比较结果如图3所示，经比较发现并行仿真中，四核处理器仿真效率比串行提高63.0%，八核处理器仿真效率比串行提高73.6%，均能够较好的发挥并行仿真的能力，说明了该方法能够通过模型合理映射到处理器上实现负载的优化，能够比较充分发挥多核处理器的性能，验证了该方法的有效性。

图3　并行仿真与串行仿真的效率对比

4　结束语

本文将仿真模型通信负载及计算负载问题简化为模型交互作用及模型复杂度问题，利用改进的蚁群算法将模型按照交互作用进行排序和聚类，并根据模型复杂度以及处理器的能力将模型映射到处理器上，该方法能够减少仿真中的通信开销，并能充分发挥仿真的并行程度，在导弹突防的仿真中得到了很好的效果，证明了该方法在并行仿真的负载优化的有效性。