摘 要：在单机多核下分别构造基于 OpenMP 和 MPI 的并行蚁群算法模型，在多核集群机下构造基于 MPI 和 MPI+OpenMP 的并行蚁群算法模型，并提出动态蚁群择优策略及分段周期交流策略。基于实际路网的路径寻优问题对上述模型进行比较，实验结果表明，在单机多核下，基于 MPI 的模型与基于 OpenMP 的模型相比，运行时间短，加速比高，在多核集群机下，基于 MPI+OpenMP 的混合模型相比基于MPI 的模型，在进程数较多时仍具有较高的加速比。
关键词：蚁群算法；多核；集群机；并行模型；信息交流策略
1 概述
蚁群算法在求解大规模问题时存在收敛速度慢、易早熟等问题。鉴于蚁群算法潜在的并行性，可用并行计算技术缓解以上问题。文献[1]提出了 5 种信息交流策略，在一定程度上加速了算法的收敛，缓解了早熟现象的发生。文献[2]提出了同步并行策略和部分异步并行策略。文献[3]提出了完全连接、替换最差、超立方体、环、并行独立运行 5 种并行策略。这些策略都加快了算法的收敛速度。本文在此基础上构造了基于 MPI(Message Passing Interface)、OpenMP(Open Multi-processing)、MPI+OpenMP 的并行蚁群算法模型，并将三者用于西安市路网路径寻优问题的求解。
2 基本蚁群算法及路径寻优问题
2.1 基本蚁群算法
设有 m 个蚂蚁、n 个城市节点，把这 m 个蚂蚁随机放在n 个城市节点上，让这些蚂蚁按式(1)向前移动，并在路径上撒上定量的信息素，直到回到原点，所有的蚂蚁周游一次后，本次迭代结束。
其中， ( )kijp t 是 t 时刻蚂蚁 k 由城市 i 到城市 j 的转移概率；kTabu 为蚂蚁 k 的禁忌表； ( )ijτ t为 t 时刻城市 i、j 之间边上的信息素量； ( )ijη t为 t 时刻由城市 i 转移到 j 的期望值；启发因子α 、β 分别是边上积累的信息素的重要程度及选择此边的重要程度。每只蚂蚁周游一次后，根据式(2)进行局部更新。
其中，0τ =C，C 为常数；1 ρ是信息素挥发系数。本次迭代后，进行一次全局更新，把本次迭代后最优路径上的信息按式(3)更新，经过数次迭代，最终形成一条最优路径。1( ) ( ) ( , ), ( , ) ( , )mkij ij ij ij ijkτ t n ρ τ t τ t t n τ t t n τt t n=+ = +Δ + Δ + = ∑+(3)其中，1 ρ是信息素挥发系数； ( , )kijΔτ t t + n是第 k 只蚂蚁在时刻(t, t+n)留在路径 ij 上的信息素量。2.2 路径寻优问题与旅行商问题本文研究的路径寻优问题类似于经典旅行商问题，即在m 个城市中取 n(n≤m)个节点，要求遍历完 n 个节点，回到起点，且代价最小，此 n 个节点不一定两两相通。该问题所研究代写论文的图是任意两点都相通的，但实际道路并非任意两点都相通，利用蚁群算法求解可能遇到回溯问题，如图 1 所示。
当蚂蚁 k 的路径为 A->C->B 时，B 点所有的邻接点都已访问过，只能回溯到 C 点。它走过的路径为 A->C->B->C，C点访问 2 次，在经典旅行商问题中不存在回溯，且每个节点仅访问一次。
2.3 基于蚁群算法的路径寻优问题求解流程
利用蚁群算法求解路径寻优问题的具体步骤如下：(1)在西安市地图 4 525 个节点中随机选取 n 个节点，设定边上的信息素值maxτ ，并设 Q0=0.1，生成随机数 Q ∈ (0,1)，把 m 个蚂蚁放在 n 个节点上(m≤n)。若 Q≥Q0，算法保证优先访问必经节点，即如果从当前必经节点 i 到下一个必经节点 j 道路连通且转移概率相比其他节点高，蚂蚁按式(1)选择下一节点 j；如果从当前必经节点 i 没有一条道路连通下一个必经节点 j，则选择转移概率较高的其他节点。如果出现图 1的情况，则选择回溯；若 Q<Q0，每只蚂蚁按式(4)选择下一个节点。
k(2)本次迭代后保存最优路径，重置各边上的信息素范围为min max[τ ,τ ]，并按式(2)进行局部更新。(3)迭代若干次后，判断最优路径在某个时间段是否改变，若改变，继续迭代，按式(3)进行全局更新；若不改变，迭代结束，保存最优解。
3 并行蚁群算法
并行蚁群算法策略有如下 4 种[1,3]：并行独立蚁群，完全连接，超立方体，环。上述策略在一定程度上加快了算法收敛速度，提高了运行效率，但存在通信过于频繁及忽略种群多样性等问题，如果把每次迭代中最优的蚂蚁信息广播给其他所有的蚁群，容易陷入局部最优及产生过大的通信开销。最差蚂蚁可能是局部最差，但若忽略这些最差蚂蚁走过的路径，最优蚂蚁极易使局部最优路径信息素过强，不利于最终最优路径生成。最差蚂蚁也应该以一定的概率把信息广播给其他蚁群，从而提高种群多样性，得到全局最优解。3.1 动态蚁群择优策略若有 n 个蚁群，受“田忌赛马”的启示，每个蚁群分别选择最优蚂蚁、较优蚂蚁及最差蚂蚁，按式(5)求出每个蚁群的适应度值 ω ，所有蚁群进行一次比较，分别标号。
其中， α、 β是(0,1)内的随机数；gl 、ml 、bl 分别为最优蚂蚁、较优蚂蚁及最差蚂蚁走过的距离。筛选出适应度值最高的蚁群 AC1 及适应度值最低的蚁群 AC2，用群 AC1 的最优蚂蚁替换 AC2 的较优蚂蚁，再用 AC1 的较优蚂蚁替换 AC2的最差蚂蚁，最后用 AC1 的最差蚂蚁替换 AC2 的最优蚂蚁。这样，优等蚂蚁和劣等蚂蚁都以一定概率传递给另一蚁群，根据“田忌赛马”原则，最终还是优等蚂蚁传递较多的信息，既达到了通信的目的，又可以增强种群多样性。
3.2 分段周期交流策略
若每迭代完后都迁移蚂蚁，则信息交换频繁，不利于种群多样性；若周期太长，种群间信息交换太少，不利于算法收敛。为提高蚁群收敛速度，本文提出基于分段周期的交流策略。蚁群算法在刚开始时收敛速度较慢，路径选择范围较大，此时为加快收敛速度，每次迭代后都要进行信息交换；随着迭代次数的增多，路径开始收敛，为了不陷入局部最优，需增大交流周期，以降低信息交换频率。
4 基于 OpenMP 及 MPI 的并行蚁群算法
4.1 基于 OpenMP 的并行蚁群算法原理
蚂蚁群体在每次迭代中选择下一个城市节点时存在潜在的并行性。传统的算法是一只蚂蚁完成一次周游后，另一只蚂蚁进行下一次周游。使用 OpenMP 指令后，可把每次迭代中的 m 只蚂蚁分配给 k 个线程，这 k 个线程同时执行。并行策略采用动态蚁群择优策略。OpenMP 使内层循环并行化，外层迭代不变，假如有 20 只蚂蚁、4 个线程，每个线程分配5 只蚂蚁，OpenMP 采取默认的 static 调度方式。每个线程分配的蚂蚁号如表 1 所示。
4.2 基于 MPI 的并行蚁群算法原理
把迭代次数分配给不同的进程。不同的进程参数不同，并行策略采用动态蚁群择优策略及分段周期交流策略。假如迭代 100 次，有 4 个进程进行迭代，则每个进程迭代25 次，每个进程所分配的迭代号如表 2 所示。
4.3 单机多核下基于 OpenMP 和 MPI 的并行蚁群算法实验OpenMP 和 MPI 都可以在共享存储结构下进行消息传递。本文在单机四核下对两者进行了性能比较。蚁群算法参数为：α = rnd(1,5)， β = rnd(1,5)， ρ =0.9，maxτ =1，蚂蚁数为 50，其中，rnd(1,5)表示返回 1~5 的一个值，不同的进程生成不同的参数。统计结果如图 2~图 4 所示，其中，s(1)表示串行执行；t(2)、t(4)代表 OpenMP 分别启动 2 个、4 个线程；p(2)、p(4)代表 MPI 分别启动 2 个、4 个进程；每个进程(线程)占用一个处理核。
由图 2~图 4 可以得出以下结论：
(1)无论问题规模如何，MPI 或 OpenMP 并行模型在Intel 编译器下的程序运行时间都少于在 Visual Studio 2008编译器下的运行时间。
(2)OpenMP 在启动 2 个线程时，刚开始的运行时间比串行时间多，因为此时问题规模较小(200 个~1 000 个城市)，随着规模的扩大，时间呈减少趋势；OpenMP 本身存在开销，OpenMP 的并行能力借助于运行库的支持，在程序并行过程中，这些库也会带来一定的开销，所以有时引入 OpenMP 后，并行的效率不一定好于串行。当必经城市数达到 1 000 时，运行时间随着问题规模的增大开始变长，根据 Gustafson 定律，并行效果逐渐明显。在启动 4 个线程时，刚开始运行时间远大于串行时间，此时问题规模比较小，引入 4 个线程定会带来巨大的开销，因此，运行时间很长，随着问题规模的扩大，运行时间开始减少，最终少于串行所用时间。
(3)单机多核下用 MPI 启动 2 个进程，运行时间基本只有串行的一半，启动 4 个进程，运行时间基本只有串行的1/4。分别用 MPI 和 OpenMP 启动 2 个和 4 个线程进行比较，MPI 并行模型的运行时间更少，加速比更高。因为MPI 是进程级并行模型，资源独立，编程难度较大，并行效率高，而 OpenMP 是线程级并行模型，资源共享，编程难度较小，且借助于运行库的支持，并行效率低。另外，在 Intel 编译器和 VS2008 编译器下，MPI 并行模型的加速比基本相同，且呈线性。
5 混合并行蚁群算法
5.1 混合并行模型
混合模型中采用节点间和节点内的两级并行机制，综合了进程间各个区域的粗粒度并行和进程内部循环级的细粒度并行。混合编程模型有 MPI+OpenMP 及 MPI+Threads 等。
集群机下用 MPI+OpenMP 混合编程有 2 种：细粒度并行及粗粒度并行。本文采用细粒度并行，在多核节点内用 OpenMP 开发并行性，节点间用 MPI 开发并行性，实验结果证明，MPI+OpenMP 混合编程解决了 MPI 和 OpenMP不能解决的问题[4]。MPI+OpenMP 混合编程的优势和注意事项可参考文献[4-5]。
5.2 MPI+OpenMP 混合并行蚁群算法原理
在集群机下，外部迭代次数按进程数分配，每个处理机运行一个进程，进程内部按线程数分配每次迭代的蚂蚁数。并行策略采用动态蚁群择优策略及分段周期交流策略。假如有 100 次迭代、20 只蚂蚁、4 个进程，每个进程包括2 个线程，则每个进程迭代 25 次，为每个 0 号线程分配12 只蚂蚁，为每个 1 号线程分配 13 只蚂蚁，如表 3 所示。
5.3 集群机下 MPI 和 MPI+OpenMP 编程实验
集群机配置如下：CPU 为 Intel Core 6320 1.86 GHz；Socket 为 singal-socket；协议为 TCP/IP；内存为 1 GB；节点数为 8 个；操作系统为 Windows XP；编程语言为 C++；IDE为 Visual Studio 2008；MPI 为 mpich2-1.2-win-ia32。实验结果如图 5、图 6 所示，其中，p(1)~p(8)分别代表处理机数(进程数)为 1 个、2 个、4 个、6 个和 8 个。
在图 5、图 6 中，当必经城市数为 100 个时，基于 MPI的并行蚁群算法运行时间少于基于 MPI+OpenMP 的混合并行蚁群算法，由于此时问题规模较小，而 OpenMP 本身存在开销，因此优势没有体现出来。当城市数为 1 000 个时，MPI 运行时间多于 MPI+OpenMP，此时问题规模较大，OpenMP 的优势得以体现。在 MPI 性能到达瓶颈之前，运行时间随着进程数的增多而减少；MPI 的理想进程个数由程序本身(问题规模、时间复杂度等)决定。
加速比实验结果表明，当处理机(进程)数目为 8 时，MPI 的加速比略有下降，MPI+OpenMP 仍然接近线性加速比，因为程序进程变多，进程间通信量变大，所以 MPI 性能接近瓶颈，而混合编程中每个进程任务由多个线程同时完成，运行时间变少，加速比变大，弥补了进程通信量变大所占用的时间，因此，加速比基本保持线性加速比。
6 结束语
并行蚁群算法可以使传统蚁群算法收敛速度慢、易早熟等问题得到缓解，因此，本文分别采用 OpenMP、MPI和 MPI+OpenMP 混合编程模型实现了蚁群并行化，并应用于西安市路网的路径寻优问题。在真实应用背景下分析了上述各并行模型对问题规模的适应性。下一步工作是对OpenMP、MPI、TBB 及 Cilk++几种并行编程模型进行对比分析，以及将 TBB 和 MPI 结合，为多核处理器节点集群提供并行层次化结构，从而优化集群性能。
参考文献
[1] Randall M, Lewis A. A Parallel Implementation of Ant ColonyOptimization[J]. Journal of Parallel and Distributed Computing,2002, 62(9): 1421-1432.
[2] Bernd B, Gabriel E K, Christine S. Parallelization Strategies forthe Ant System[Z]. Vienna, Austria: University of Vienna, 1997.
[3] Manfrin M, Birattari M, Stutzle T, et al. Parallel Ant ColonyOptimization for the Traveling Salesman Problem[R]. Universite’Libre de Bruxelles, Belgium, Technical Report: TR/IRIDIA/2006-007, 2006.
[4] 单 莹, 吴建平, 王正华. 基于 SMP 集群的多层次并行编程模型与并行优化技术[J]. 计算机应用与研究, 2006, 23(10): 254-256.
[5] 王惠春, 朱定局, 曹学年, 等. 基于 SMP 集群的混合并行编程模型研究[J]. 计算机工程, 2009, 35(3): 271-274.
