欢迎来到天天文库
浏览记录
ID:15325083
大小:26.00 KB
页数:13页
时间:2018-08-02
《并行遗传算法的研究及应用进展[权威资料]》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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模型,它把三种基本模型混合形成层次结构,主要有粗粒度-细粒度、粗粒度-粗粒度、粗粒度-主从式。实际中应用较多是粗粒度-主从式模型。首先,按上层的并行模型将全局种群划分成若干种群,然后,各种群按照下层的并行模型将
此文档下载收益归作者所有