并行遗传算法的研究及应用进展[权威资料]

《并行遗传算法的研究及应用进展[权威资料]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、llelcomputerandnaturalparallelismofparallelgenetic，whichgreatlypromotestheresearchandapplicationingeneticalgorithm.TherecentresearchdevelopmentsinPGAmodels，performanceanalysis，algorithmimprovement，andimplementationplatformaresummarizedandreviewed，andthedevelo

3、pmenttrendsandapplicationperspectivesofPGAinthefutureisalsodiscussed.　　Keywords：geneticalgorithm；parallelgeneticalgorithm；parallelmodel　　并行遗传算法（PGA）作为GA的一个重要分支，得到了越来越多专家们的重视。PGA正成为GA中的一个重要研究方向。近年来，对于PGA的理论和应用研究，许多计算机科学家做了大量的工作并取得了一定的成果。并行遗传算法将并行计算机的高速并行性和遗传算法

4、的天然并行性相结合，不仅提高了求解速度，而且由于种群规模的扩大和各子种群的隔离，减少了未成熟收敛的可能性，提高了求解质量。　　1传统并行遗传算法模型　　实现PGA，需要对传统GA进行修改：一是要把串行GA的单一种群分成多个子种群，分而治之；二是要控制、管理子种群之间的信息交换，不同的分治方法产生不同的PGA结构[1]。传统并行遗传算法模型[2][3]包括：主从式模型、细粒度模型、粗粒度模型、混合模型。　　1.1主从式模型　　主从式模型是遗传算法的直接并行化方案，不改变遗传算法的基本结构特点。在主从式模型中，遗传算

5、子包括选择算子、交叉算子、变异算子以及其它高级算子都并行应用于单一种群，所有的并行处理都在单一种群内部进行。主从式模型易于实现，保留了简单遗传算法的搜索行为，可以直接应用于简单的遗传算法中。　　1.1.1选择算子　　在遗传算法中，选择算子[4]的核心思想就是优胜劣态，适应度高的个体进入下一代种群的概率大；适应度低的个体进入下一代种群的概率小。根据各个个体的适应度，按照一定的规则或方法进行实际的选择，用来确定重组或交叉个体，以及被选个体将产生多少个体代个体。计算适应度可以采用按比例或基于排序的适应度计算，进行实际的

6、选择可采用轮盘赌选择法、随机遍历抽样法、局部选择法和锦标赛选择法等。　　1.1.2交叉算子　　在遗传算法中，交叉算子[5]就像人类社会的婚姻过程，交叉又称为基因重组，是结合来自父代交配种群中的信息产生新的个体，对每一对个体.以某个概率（称为交叉概率）交换它们之间的部分染色体。依据编码表示方法的不同，有实值交叉和二进制交叉操作。　　1.1.3变异算子　　变异算子[6]是对群体中的每一个个体，以某一概率（称为变异概率）改变某一个或某一些基因座上的基因值为其他的等位基因。针对不同的编码方案，常用的编译操作有实值变异和二

7、进制变异。　　1.2细粒度模型　　当并行计算机系统的规模很大，处理器多到可以与染色体一一对应，即每一处理器上驻扎一个染色体时，可以采用细粒度模型的并行遗传算法。由于对处理器数量的要求很高，所以细粒度模型的应用范围不广，一般只运行于大规模的并行计算机。　　1.3粗粒度模型　　粗粒度并行遗传算法被称作分布式模型或孤岛模型。在粗粒度模型中，各个子群体在不同的处理器上相互独立的执行进化操作，每经过一定的进化代，各子群体间会交换若干的个体以引入其它子群体的优秀基因。粗粒度模型的通信开销较小，可获得接近线性的加速比，适合运行

8、在通信带宽较低的集群系统上。在粗粒度模型的研究中，要解决的重要问题是参数选择，包括迁移拓扑、迁移率、迁移周期等。　　1.4混合模型　　混合PGA又称为多层并行PGA模型，它把三种基本模型混合形成层次结构，主要有粗粒度-细粒度、粗粒度-粗粒度、粗粒度-主从式。实际中应用较多是粗粒度-主从式模型。首先，按上层的并行模型将全局种群划分成若干种群，然后，各种群按照下层的并行模型将