群体智能优化算法的并行化浅析

王元元

摘要:针对目前并行化的群体智能优化算法在实际应用中的现状进行分析研究，从并行模型，并行结构，以及算法设计等方面介绍了群体智能算法并行化研究的相关内容。对更进一步的研究提出了关于通信等方面需要考虑的问题。

关键词：群体智能优化算法，并行算法，通讯

中图分类号：TP301文献标识码：A文章编号：1009-3044(2012)05-1142-02

通过观察，我们发现自然界中群体生活的动物大部分都具有完成复杂行为的能力，个体之间的交互作用在构建群行为中起到重要作用。国内外学者[1]参考群体动物生活的社会行为,提出了群体智能优化算法。所谓群体智能(Swarm Intelligence)指的是简单个体组成群体,个体之间存在可以进行直接通信或者间接通信,通过相互作用形成强大的群体智慧来解决复杂的问题。自20世纪90年代模拟蚂蚁行为的蚁群算法(ACO)提出以来,又产生了模拟鸟类行为的微粒群[2]算法(PSO)、模拟鱼类生存习性的人工鱼群[3]算法、模拟青蛙觅食的混合蛙跳算法(SFLA)等。

在解决实际问题时，我们会充分利用群体智能优化算法的特点。首先，群体中相互作用的个体是独立的,没有直接的控制中心,即使个体失败,整个群体仍然具有完成任务的能力，不会因为个别个体出现故障而影响整个问题的求解,具有较强的稳定性;其次，每个个体只能感知局部信息,个体所遵循的规则非常简单,所以群体智能的实现简单。第三，系统具有很好的可扩充性，因为系统个体的增加而引起的通信开销的增加很小。这样，使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决,大大增强了人们解决和处理优化问题的能力,使得人们投入更大的精力对其理论和实际应用进行研究。

正因为这些特点，无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。

群体智能算法具有良好的寻优能力,并具有鲁棒性强，对于初值和参数选择不敏感、简单易实现等诸多优点，但在实际应用中也存在些问题。例如在解决水库群优化调度的应用中，随着水库群规模的增大，对优化算法的求解质量和运行速度提出了更高的要求。另外，在问题求解空间逐渐增加时，群体智能串行算法的执行存在计算量大，速度慢，甚至有时无法得到满意的结果。因此，我们将群体智能优化算法与并行算法相结合进行改进,产生并行化的群体智能优化算法。

1并行算法的研究内容

1.1基本原理

并行算法就是用多台处理机联合求解问题的方法和步骤,其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题,然后使用多台计算机同时求解它,从而最终求得原问题的解.如图1所示。

图1并行算法示意图

1.2并行计算模型

并行计算模型通常指从并行算法的设计和分析出发，将各种并行计算机（至少某一类并行计算机）的基本特征抽象出来，形成一个抽象的计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。并行计算模型有PRAM模型，BSP模型，LogP模型，BDM模型等。

早期的并行计算模型是共享存储模型，如PRAM（Parallel Random Access Machine，随机存取并行机器）模型，就是共享存储的SIMD模型，它是一种抽象的并行计算模型。在这种模型中，假定存在一个容量无限大的共享存储器，有有限个或无限个功能相同的处理器，且他们都具有简单的算术运算和逻辑判断功能，在任何时刻个处理器都可以通过共享存储单元相互交互数据。

第二代是分布存储模型。如BSP模型是个分布存储的MIMD计算模型。在这个阶段如何把不同的通信性能抽象成模型参数，是研究重点。BSP模型强调了计算任务和通信任务的分开，它将处理器和路由器分开，这样做既掩盖具体的互连网络拓扑，又简化了通信协议。

随着网络技术的发展，通信延迟固然还有影响，但对并行带来的影响不再像当年那样重要。LogP模型是一种分布存储的、点到点通信的多处理机模型，它充分说明了互联网络的性能特性，而不涉及到具体的网络结构，也不假定算法一定要用现实的消息传递操作进行描述。

1.3并行算法的设计技术

虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。

2并行结构

2.1多处理机MP(Multiprocessors)结构

MP结构基于总线连接，集中式共享存储。该结构采用单地址空间，易编程性，动态负载平衡，无需显示数据分配。具有高速缓存及其一致性，数据局部性，硬件维持一致性，低通信延迟等优点，但存在欠可靠，不可扩放性等缺陷。

2.2大规模并行处理系统MPP（massively parallel processing）

MPP是成百上千个处理器组成的大规模计算机系统，其规模是可以变化的。它的结钩稳定，高带宽低延迟，有较好的通用性和可用性。

这两种并行结构除了处理器数量有所不同外,还存在很大差异。比如内部互连方式、存贮器组织结构,以及操作系统支持方式和应用领域等方面。

2.3工作站机群NOW(network of workstation)

工作站机群中每一个节点都是一个完整的工作站，有自己的磁盘和操作系统。通过互连网将工作站连接在一起，并配以相应的支撑软件,构成一个分布式并行计算机系统。特别地，大规模并行处理机(MPP)可以近似的看成为一个没有本地磁盘的COW。COW的网络接口是松耦合的，即它是接到I/O总线上而不是像MPP那样直接接到处理器存储总线上的。

这种结构的优点是投资风险小，系统结构灵活，性价比高，能充分利用分散的计算资源，可扩放性好。但通信性能和并行编程环境是需要考虑的问题。

3对群体智能优化算法并行化研究的现状

求解TSP问题的智能优化算法主要包括蚁群算法和模拟退火算法等，这些算法求解TSP问题的速度比传统的精确求解算法有很大改进，但在问题的求解空间逐渐增加时，串行执行速度往往还是无法满足人们的需求.针对此问题，文献[4]研究了蚁群算法、模拟退火算法以及两者的混合算法的并行实现方法，建立了PC机群实验平台，基于MPI环境对蚁群算法、模拟退火算法以及混合算法的并行算法进行了测试.根据理论研究和实际测试的结果，比较了并行算法和传统串行算法的性能差异，说明了基于MPI的并行算法求解TSP问题是一种低成本、高效率的解决方案。

文献[5]建立并行粒子群算法求解多阶段最优化问题数学模型,重点研究了粗粒度并行粒子群算法。应用开发的分布式水库群优化调度并行计算系统,将文中两种策略的并行粒子群算法（PPSO）和串行粒子群算法( PSO )应用于金沙江与雅砻江混联水库群优化调度中。通过对其优化结果的分析表明, PPSO有利于提高运算速度和求解精度以及改善算法的收敛性能。文献[6]设计和实现了一种并行粒子群优化算法.实验结果表明,基于岛屿群体模型的并行粒子群优化算法不仅提高了求解效率,而且改善了早收敛现象,算法的性能比经典粒子群优化算法有了很大提高。

文献[7]提出了自适应免疫量子粒子群优化并行算法。针对该算法计算量大、耗时长的缺点，结合已有的并行计算技术，构造出了该算法的并行计算方法。仿真实验表明无论是优化算法的搜索能力还是运行时间以及并行效率，该并行算法都具有较明显的优势，从而为解决复杂优化问题提供了一种有力手段。

4将群体智能优化算法并行化需要考虑的几点

1）分治策略。将一个比较复杂的问题分解为若干个与原有问题相似但规模适度可以独立运算的子问题，最后通过合并这些子问题的结果就得到原问题的解。在分解过程中要使得这些子任务能在多个处理机上并行执行和相互通信,彼此合作，协调一致地完成整个计算任务。

2）并行策略。要根据实际问题选择适合的并行策略。粗粒度（coarse-grained）方法是指将较多的子任务分配给单个处理器因此能减少处理器之间的信息传递。细粒度（fine-grained）并行指分配给单个处理器较少的计算实体，但随之而来的是处理器间频繁的信息交互，会带来通讯的开销。

3）通讯。如何减少通信开销和同步开销也是设计智能并行算法的关键。在并行算法中存在着随着处理机台数的增加，算法的并行效率有所下降的问题。要想尽可能地减少通信开销,有效途径是改善网络接口,减小或重叠通信延迟和降低发收开销。

5总结

从目前已有的许多并行化的群体智能优化算法应用在实际中看出对它的研究前景是很广阔的。这种并行化的优化算法，对传统智能优化算法的缺陷以及处理复杂问题的时间进行了改进。高性能计算的普及在一定的程度上改变了科学研究的方式，并必将成为人们认识自然改造自然的一种新方法。

参考文献：

[1]黄席樾,胡小兵.现代智能算法理论及应用[M].北京:科学出版社,2005.

[2]曾建潮,介婧,崔志华.微粒群算法[M].北京:科学出版社2004.

[3]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002 11:32238.

[4]许智宏，宋勃，郭艳艳。模拟退火与蚁群混合并行算法解旅行商问题[J].河北工业大学学报,2010，39（2）:48-51.

[5]陈立华,朱海涛,梅亚东.并行粒子群算法及其在水库群优化调度中应用[J].广西大学学报,2011,36(4): 677-682.

[6]黄芳,樊晓平.基于岛屿群体模型的并行粒子群优化算法[J].控制与决策,2006,21(2):177-179.

[7]成新文,自适应免疫量子粒子群优化并行算法[J].计算机工程与应用, 2010,46（21）:34-36.