并行遗传算法的研究及应用进展

冯小丹　娄自婷　王文元

摘要：并行遗传算法（PGA）将并行计算机的高速并行性和遗传算法天然的并行性相结合，极大地促进了遗传算法的研究与应用。该文对近年来并行遗传算法的模型、性能分析、算法改进、实现平台进行了归纳和评述，并且对并行遗传算法今后的主要研究方向和发展前景进行了展望。

关键词： 遗传算法；并行遗传算法；并行模型

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）10-2347-04

Abstract： Parallel Genetic Algorithm（PGA） combines High-speed parallel computer and natural parallelism of parallel genetic， which greatly promotes the research and application in genetic algorithm. The recent research developments in PGA models， performance analysis， algorithm improvement， and implementation platform are summarized and reviewed， and the development trends and application perspectives of PGA in the future is also discussed.

Key words： genetic algorithm； parallel genetic algorithm； parallel model

并行遗传算法（PGA）作为GA的一个重要分支，得到了越来越多专家们的重视。PGA正成为GA中的一个重要研究方向。近年来，对于PGA的理论和应用研究，许多计算机科学家做了大量的工作并取得了一定的成果。并行遗传算法将并行计算机的高速并行性和遗传算法的天然并行性相结合，不仅提高了求解速度，而且由于种群规模的扩大和各子种群的隔离，减少了未成熟收敛的可能性，提高了求解质量。

1 传统并行遗传算法模型

实现PGA，需要对传统GA进行修改：一是要把串行GA的单一种群分成多个子种群，分而治之；二是要控制、管理子种群之间的信息交换，不同的分治方法产生不同的PGA结构[1]。传统并行遗传算法模型[2][3]包括：主从式模型、细粒度模型、粗粒度模型、混合模型。

1.1 主从式模型

主从式模型是遗传算法的直接并行化方案，不改变遗传算法的基本结构特点。在主从式模型中，遗传算子包括选择算子、交叉算子、变异算子以及其它高级算子都并行应用于单一种群，所有的并行处理都在单一种群内部进行。主从式模型易于实现，保留了简单遗传算法的搜索行为，可以直接应用于简单的遗传算法中。

1.1.1 选择算子

在遗传算法中，选择算子[4]的核心思想就是优胜劣态，适应度高的个体进入下一代种群的概率大；适应度低的个体进入下一代种群的概率小。根据各个个体的适应度，按照一定的规则或方法进行实际的选择，用来确定重组或交叉个体，以及被选个体将产生多少个体代个体。计算适应度可以采用按比例或基于排序的适应度计算，进行实际的选择可采用轮盘赌选择法、随机遍历抽样法、局部选择法和锦标赛选择法等。

1.1.2 交叉算子

在遗传算法中，交叉算子[5]就像人类社会的婚姻过程，交叉又称为基因重组，是结合来自父代交配种群中的信息产生新的个体，对每一对个体.以某个概率（称为交叉概率）交换它们之间的部分染色体。依据编码表示方法的不同，有实值交叉和二进制交叉操作。

1.1.3 变异算子

变异算子[6]是对群体中的每一个个体，以某一概率（称为变异概率）改变某一个或某一些基因座上的基因值为其他的等位基因。针对不同的编码方案，常用的编译操作有实值变异和二进制变异。

1.2 细粒度模型

当并行计算机系统的规模很大，处理器多到可以与染色体一一对应，即每一处理器上驻扎一个染色体时，可以采用细粒度模型的并行遗传算法。由于对处理器数量的要求很高，所以细粒度模型的应用范围不广，一般只运行于大规模的并行计算机。

1.3 粗粒度模型

粗粒度并行遗传算法被称作分布式模型或孤岛模型。在粗粒度模型中，各个子群体在不同的处理器上相互独立的执行进化操作，每经过一定的进化代，各子群体间会交换若干的个体以引入其它子群体的优秀基因。粗粒度模型的通信开销较小，可获得接近线性的加速比，适合运行在通信带宽较低的集群系统上。在粗粒度模型的研究中，要解决的重要问题是参数选择，包括迁移拓扑、迁移率、迁移周期等。

1.4 混合模型

混合PGA又称为多层并行PGA模型，它把三种基本模型混合形成层次结构，主要有粗粒度-细粒度、粗粒度-粗粒度、粗粒度-主从式。实际中应用较多是粗粒度-主从式模型。首先，按上层的并行模型将全局种群划分成若干种群，然后，各种群按照下层的并行模型将其分成若干子种群。在下模型中每个子种群按下层模型进行进化，而在上层模型中，种群之间按上层模型协调运行[7]。

对于不同的应用问题，基本GA的参数难于设定，但混合PGA允许GA参数随染色体进化而进化，因此，结点的结构是动态变化的，这样减少了遗传算法因具体求解任务而受影响的程度，所以混合PGA是自适应算法，然而该算法最为复杂，实现代价高[8]。

2 并行遗传算法的性能分析

在上世纪90年代中期以前，虽然并行遗传算法被广泛应用于各种领域，但主要限于实践，为得到好的优化效果，研究者要进行大量的实验，试用各种策略和参数。

文献[9]给出了两条定性评价并行遗传算法的指标：（1）确定一个适应度指标，利用串行遗传算法最短的搜索时间（找到一个个体适应度高于适应度指标）除以并行遗传算法的搜索时间，作为并行遗传算法的加速比指标。（2）给定一段时间，利用并行遗传算法进行优化，能够得到的最高适应度比利用串行遗传算法搜索到的最高适应度高出多少。

3 并行遗传算法的改进

经典遗传算法存在着局部搜索性能较差的缺陷，对于某些分布变化缓慢的问题，需要进行大量的计算，并且由于进化初期的超常个体使得种群过早收敛到局部最小值。而改进的并行遗传算法通过编码表示及参数设定的思想，在系统中建立一个存放精华个体的主机，来控制系统的通信以及精华种群的传播，使系统中通信量减少，有利于提高算法的时间性能。

3.1 改进的主从式并行遗传算法

遗传算法的内在并行性不仅仅体现在适应度计算阶段，选择、交叉和变异三个阶段均可并行执行。之所以传统的主从模式没有将这三个阶段并行执行， 是因为传统的主从模型针对并行集群设计，必须考虑结点间的通信延迟和负载平衡，因此不适宜对计算量相对较小的选择、交叉和变异三个阶段采用并行执行。而改进的主从式并行遗传算法[10]将选择、交叉和编译三个阶段也采用并行执行，在多核计算环境下通过多线程的方式实现程序的并行执行，进程间通信通过共享内存完成， 通信延迟不再影响并行程序的性能。

3.2 改进的粗粒度并行遗传算法

为了解决在分布式系统中，需要使每个处理器了解整个系统信息，需要花费大量时间，实现起来也比较复杂。传统粗粒度并行遗传算法存在容易早熟并且收敛速度较慢的不足。基于此，采用改进的并行遗传算法可以保证算法的时间开销，有效的增加种群的多样性，抑制早熟现象，提高最优解的质量[11]。文献[12]首先初始化种群，遗传代数归零；网络中的各个从机接受主机的启动信号后，开始进行串行遗传计算，对种群的大小、染色体的长度、交叉率、变异率、最大进化代等遗传参数进行设置；然后进行选择、交叉和变异操作后，分别计算个体的适应度；如果满足迁移条件，将当前从机中最优个体传送给主机的优秀基因库，之后接收主机发送的优秀基因，淘汰从机中适应度最差的个体。

3.3 基于自适应迁移策略的并行遗传算法（AMPGA）

基于传统并行遗传算法存在迁移固定不变，盲目性等缺点[13]，提出了一种基于自适应迁移策略的并行遗传算法（AMPGA） [14]，其算法包括精英策略，编码方式，选择算子，交叉淘汰算子，迁移算子，接受算子等组成部分。在AMPGA中，各个子种群中执行个体的迁移时，改变了传统并行遗传算法迁移固定不变的缺点，根据当前的演化状态动态、有条件地迁移，并解决了盲目性与局限性等缺点。

综上所述，基于传统并行遗传算法在收敛速度，时间性能，求解精度及并行效率等方面存在局限性，提出的多种改进的并行遗传算法高效率的解决了一系列问题。

4 并行遗传算法程序的实现平台

4.1 工作站机群（COW）

工作站机群COW [15]是实现并行计算的一种新的主流技术，是属于分布式存储的MIMD并行计算机结构，由工作站和互连网络两部分组成。充分利用各工作站资源，统一调度、协调处理，大大提高了求解的质量。

在工作站机群上构造并行遗传算法，需要考虑的问题有：

1）子群体划分方式。可采用将整个群体M均匀分配到p个处理机的方式。

2） 信息交换方式。在并行遗传算法运行过程中，各处理机间要互相交换一些信息，信息交换方式通过参加信息交换的对象、交换信息的内容、交换时间、交换信息量这四个部分组成。

4.2 集群系统

从PC或工作站集群到SMP集群的可扩展计算机集群[16]正很快成为高性能计算的标准平台。这种系统建立在容易购买且价格低廉的商品化硬件、快速局域网和标准软件组件之上，他们根据预算和计算能力的要求做出调整，能够有效地运行高要求的并行和串行程序。借助高性能计算机（集群系统）[17]，在高性能并行软件环境的支持下，设计并实现一种并行遗传算法，使该算法具有可行性和有效性。

4.3 多核微机

随着技术的成熟与价格的下降，多核CPU逐渐普及，而用高性能多核PC组建的集群系统具有投资风险小、结构灵活、可扩展性强、易于实现的特点，有很高的性价比，可以容易地利用较低的成本获得传统并行机的高计算性能。构建以多核PC为单计算节点的集群系统已成为并行计算机体系结构的一个发展趋势，也是一种有效适用的并行计算机系统的实现方法[18]。

4.4 Internet

目前，遗传算法以粗粒度并行遗传算法最为流行，它只需在串行遗传算法中增加迁移子例程，在并行计算机的节点上各自运行一个副本，并定期交换几个个体即可，此算法非常适合在Internet平台下实现。其稳定性好，优化速度明显得到改善，优化质量得到显著提高，能较快地找到问题的最优解或次优解。但在实际应用中，还需考虑计算机之间的协同工作能力、网络通讯量、网络是否安全和用户是否愿意参与等问题。

5 并行遗传算法的应用

并行遗传算法[19]是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智能技术，已经广泛应用于计算机科学、人工智能、信息技术及工程实践等多个领域中。

1）列车控制

列车控制[20]问题是研究如何控制列车运行以使得能耗最小，采用主从式控制网络PGA能够有效解列车控制问题，PGA的加速比比较满意。GA与其它优化算法相结合能显示出强大的搜索优势，并且算法易实现。

2） 组合优化

随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类问题，遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用[21]。

3） 带约束并行多机调度

在实际工程应用中，经常遇到的并行多机调度问题带有约束条件，最小化完工时间的带约束并行多机调度问题的并行遗传算法可解决这一问题。计算时间短，适应性强，鲁棒性高，适用于大规模问题。例如在单件生产车间调度、流水线生产车间调度、生产规则、任务分配等方面并行遗传算法都得到了有效的应用[22]。

4）函数优化

函数优化[23]是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例，很多人构造出了各种各样的复杂形式的测试函数。用几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而并行遗传算法却可以方便地得到较好的结果。

5） 机器人智能控制

机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源来自于对人工自适应系统的研究，所以机器人智能控制理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用[24]。

6） 自动控制

在自动控制领域中许多与优化相关的问题需要求解，因而并行遗传算法的应用日益增加，并显示了良好的效果[25]。

7）图像处理和模式识别

图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会产生一些误差，这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。并行遗传算法在图像处理中的优化计算方面是完全胜任的。目前，已在图像分割、图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用[26]。

8） 机器学习

学习能力是高级自适应系统所应具备的能力之一。基于并行遗传算法的机器学习，特别是分类器系统，在许多领域得到了应用。

9） 人工生命

人工生命是用计算机等人工媒体模拟或构造出具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于并行遗传算法的进化模型是研究人工生命现象的重要理论基础。

6 小结

并行遗传算法的研究归纳起来分为理论与技术研究、应用研究两个方面。理论与技术研究主要从遗传操作、群体大小、参数控制、适应度评价以及并行实现技术等方面来提高算法的性能。开发并行遗传算法的商业软件、开拓更广泛的并行遗传算法应用领域是今后应用研究的主要任务。

参考文献：

[1] 王小良，李强.并行遗传算法研究及其应用[J].微计算机信息，2007，23（3）：205-206.

[2] 余艳芳，钱峰.并行遗传算法研究[J].化学世界，2002，3（7）：189.

[3] 贾丽媛.并行遗传算法研究[J].湖南城市学院学报（自然科学版），2006，15（3）：72-74.

[4] 郭肇禄.一种基于自适应迁移策略的并行遗传算法[D].江西理工大学，2009.

[5] 刘嵩.改进的并行遗传算法应用研究[D].大连交通大学，2006.

[6] 赵航涛.并行遗传算法概述[J].福建电脑，2006，4：31-32.

[7] 于滨，姚宝珍，于艳弘.一种基于粗粒度—主从式的混合并行遗传算法[J].微型电脑应用，2004，20（9）：16-18.

[8] 曾国荪，丁春玲.并行遗传算法分析[J].计算机工程，2001，27（9）： 53-55.

[9] Han Yang Foo. Esbensen H， Song J. et al. Performance improvement of a genetic algorithm for floorplanning with parallel computing technology[A].Proc.ISCA97[C].Yew York，USA：IEEE，1997.3：1544-1547.

[10] 谢克家，刘昕，王成良.多核计算环境下改进的主从式并行遗传算法[J].微计算机信息，2011，27（3）：164-166.

[11] 赵戈.改进的并行遗传算法在知识库中的应用研究[D].大连交通大学，2008.

[12] 刘嵩.改进的并行遗传算法应用研究[D].大连交通大学，2006.

[13] 李伟，黄颖，李康顺.一种基于自适应迁移策略的并行遗传算法[J].武汉理工大学学报，2011，33（7）：138-142.

[14] 郭肇禄.一种基于自适应迁移策略的并行遗传算法[D].江西理工大学，2009.

[15] 张晓波，并行遗传算法求解应急系统最短路径的研究[D]，太原理工大学，2005.

[16] 王冠.并行遗传算法及其在组合优化问题上的分布式应用[D].武汉理工大学，2003.

[17] 马晓晨.迁移式并行遗传算法求解支持向量机反问题[D]，河北大学，2008.

[18] THOMASZEWSKIB，PABST S，BLOCH INGER W.Parallel techniques for physically based simulation on multi-core processor architectures[J].Computers and Graphics， 2008 （32） ： 25-40.

[19] 来金花.基于并行遗传算法的图像分割的设计与实现[D].天津工业大学，2009.

[20] 吴昊.并行遗传算法的研究与应用[D].安徽大学，2001.

[21] 李余琪.遗传算法在数据挖掘中的研究与应用[D].中南大学，2007.

[22] 华灵群.基于遗传算法的旅行商问题仿真研究[D].西北工业大学，2006.

[23] 李余琪.遗传算法在数据挖掘中的研究与应用[D].中南大学，2007.

[24] 韩丽霞.解两类组合优化问题的遗传算法[D].西安电子科技大学，2005.

[25] 赵戈.改进的并行遗传算法在知识库中的应用研究[D].大连交通大学，2008.

[26] 王海龙.并行遗传算法在装箱问题中的应用研究[D].山东大学，2008.