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

群体智能优化算法并行化浅析 　　摘要:针对目前并行化的群体智能优化算法在实际应用中的现状进行分析研究，从并行模型，并行结构，以及算法设计等方面介绍了群体智能算法并行化研究的相关内容。对更进一步的研究提出了关于通信等方面需要考虑的问题。 　　关键词：群体智能优化算法，并行算法，通讯 　　中图分类号：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结构基于总线连接，集中式共享存储。该结构采用单地址空间，易编程性，动态负载平衡，无需显示数据分配。具有高速缓存及其一致性，数据局部性，硬件维持一致性，低