主从式并行遗传算法框架应用１０９９
主从式并行遗传算法框架应用＊
安竹林’刘晓平’，２张伟林’
合肥｝业大学计算机与信息学院可视化与协同计算（ＶＣＣ）研究室，合肥２３０００９
２中国科学院等离子体物理研究所ＣＡＤ室合肥２３００３１
３安徽建筑ｒ＿ Ａ｝学院合肥２３００２２
摘要主从式并行遗传算法框架，是合肥工业大学计算机与信息学院可视化与协同计算研究室
基于Ｄ． Ｌ． Ｃａｒｒｏｌｌ的“遗传算法驱动”所开发的一个开放的可重用的遗传算法框架．本文将此框
架应用于物理计算问题的求解，并在一台双至强处理器的工作站上对其进行了测试，并给出了测试
结果及分析。 －ｉ＿ ４ ｉａｌ并行债祛算法主从式物理计算
１引言
１．１遗传算法
遗传算法是一种模拟自然选择过程的有效的随机化搜索方法。它将问题的解表示成染色体，即三进
制编码串。在搜索前给出一定种群大小的染色体群，然后将这些初始染色体至于问题的环境中，并按适
者生存、优胜劣汰的遗传机制，从中选出较适应环境的染色体进行复制，再进行交叉、变异过程。产生更适应环境的新一代染色体群。这样一代一代地进化，最后就会收敛到最适应环境的一个染色体上，即
问题的最优解
１．２并行遗传算法
随着科学技术的不断发展，问题规模的不断扩大，面对复杂程度越来越高的搜索空间，串行遗传算法的搜索过程将成倍地延长。因此，其在优化效率和求解质量上都显得“力不从心’，。由于遗传算法有着
固有并行性，并行处理是很自然的解决途径。并行遗传算法将并行计算机的高速并行性和遗传算法的大然并行性相结合。极人的促进了遗传算法的研究与应用。并行处理不但加速了遗传算法的搜索过程，而
且由于种群规模的扩大和各子种群的隔离，使种群的多样性得以丰富和保持，减少了未成熟收敛的可能
性，提高了求解的质量。 目前并行遗传算法的实现大致可以分为三类［ＤＩ：全局型一主从式模型，独立型一粗粒度模型，分散
型一细粒度模型。主从式模型是遗传算法并行化的一种最直接的方式。主从式并行遗传算法系统分为一
个主处理器和若干从处理器，主处理器监控整个染色体种群，并基于全局统计执行的选择操作，各个从
处理器接受来自主处理器的个体进行重组交叉和变异，产生新一代个体，并计算适应度再把结果传给从处理器。主从式并行遗传算法比较直观，并且针对适应度评价计算量大的问题，主从模式可以的到接近
‘基金项目：女徽省教育厅自然科学研究项目（２００４ｋｊ０９７），安徽省自然基金项目（（０１０４２２０１），国家自然基金项目共同资
助（６０２７３０４４）安竹林（１９８０－），男，山东省青岛人，硕士研究生，研究方向为协同计算、授，博导，研究方向为ＣＡＤ／ＣＧ。张伟林（１９５４－），男，安徽毫州人，教授，集群计算：刘晓平（１９６４－），男，山东济南人，教研究方向为网络与并行计算。
１１００计算机技术与应用进展．＂２００４
线性的加速比。
２主从式并行遗传算法框架
２．１简介
主从式并行遗传算法框架，是在Ｄ． Ｌ． Ｃａｒｒｏｌｌ的“遗传算法驱动”［２１基础上改进而成的。Ｄ． Ｌ． Ｃａｒｒｏｌｌ
的“遗传算法驱动”是一个免费的结构化遗传算法框架。利用该框架，只需要编写和改动少量的代码，即可在相应的程序程序中加入遗传算法。主从式并行遗传算法框架对原框架所进行改进，旨在维持其原
来的易用性的同时，在其内部封装对ＭＰＩ的调用，从而使原框架可以在ＭＰＩ环境中并行的执行。
２．２程序结构
主从式并行遗传算法，对串行程序所作的主要改动是，
在适应度的计算阶段，由主处理器将适应度的计算分配到
各个处理器上去进行，计算完毕之后再由主处理器收集结
果。然后由土处理器进行选择、交叉、变异等操作，并由此产成新一代种群，从而完成一次循环。主从式遗传算法
框架结构如图］所示：
２．３与实际问题的结合
主从式并行遗传算法框架，继承了原“遗传算法驱动”
的易用性，其应用与“遗传算法驱动”完全相同。其内部的遗传算法与ＭＰＩ对用户是完全透明的，使用者不需要具
备遗传程序设计和并行程序设计基础，只要略知遗传算法
的机理，便可应用该框架求解实际问题。
具体应用时只需作如下修改： （Ｉ）在配置文件中，设定遗传算法参数以及可调参数
范围。 （２）将待求解问题作为一个子程序加入框架中，并由
此子程序确定适应度函数。图１主从式遗传算法框架结构
３应用
３．１问题描述
文［［３］提出了一个典型的物理计算问题，该问题具有计算量大，耗时长等特点。本文将主从式并行遗
传算法框架应用于该问题的求解。由于该问题的可行解在解空间中占的比例非常小，所以在实际应用中
通常给出一个经验值，在此经验值附近寻找最优值。
３．２测试方法
测试方法是，分别记录串并行程序到达指定精度的适应度的时间，并计算加速比。需要指出的是，
由于遗传算法是一种随机算法，对于不同的随机数种子，其计算过程是各异的。因此，为了使串并行程
序的计算过程具有可比性，整个计算过程采用相同的随机数种子。
主从式并行遗传算法框架应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．皿．．里鱼口鱼鱼鱼国鱼鱼鱼鱼鱼鱼鱼鱼鱼鱼鱼鱼里皿里口口国困里口．自里里旦旦旦旦巨旦３．３测试结果
遗传算法在第１７２代找到最优值，其与目标值和经验值的比较如表１所示：
表１优化结果比较１０
三角变形
目标值
经验值
优化值大半径
４．０
４．０４９
４．０００小半径
１．０
０．７９５
０．８０４０．４－０．５
０．４１１０．４５６拉ｅ．比
１．８－２．０２．３３８
２．２９４
单双ＣＰＵ同时趋向给定精度的耗时如表２所示：
表２性能测试结果
苏吞雾ＣＩＥ ０．８８０ＣＰＵ＇ｓ（０．８８５０．８９００．８９５０．９００
３．９９６
２．０９５２卫４４
４．０３８１９．７４４
１０．５６１４９．０４８
２６．５３７６６１．５７３
３８４．５４０
双ＣＰＵ相对单ＣＰＵ的加速比如表３所示： 安３双ＣＰＵ相对单ＣＰＵ的加速比
精度
加速比旦．８８０
１．９０７些旦互
１．９１７９．８９旦
１．８６９旦．８９５
１．８４８
３．４结果分析
通过表１所示可以看出，优化值较原经验值更加逼近目标值，这说明遗传算法对问题的求解是非常
成功的。 表２为单双ＣＰＵ同时趋向给定精度的耗时，由此可以清楚的着出单双ＣＰＵ耗时随适应度的增加而
增加。同时对于同一适应度值，单ＣＰＵ耗时大致为双ＣＰＵ的两倍，这种情况在表３中更加明显，加速比基本恒定不变。这说明了该遗传算法框架具有良好的并行性，极大的提高了原遗传算法的时间性能。
４结论
本文成功的将主从式并行遗传算法框架应用于一物理计算问题的求解，结果和时间效率均达到非常好的效果。由于该问题的可行解在解空间中占的比例非常小，使其不能利用遗传算法直接求解，这必须
就改进遗传算法，这是我们以后要完成的。
参考文献
［１］ Ｅｒｉｃｋ Ｃａｎｔｕ－Ｐａｚ．Ａ Ｓｕｒｖｅｙ ｏｆ Ｐａｒａｌｌｅｌ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ． ＩｌｌｉＧＡＬ Ｒｅｐｏｒｔ Ｎｏ ９７００３， Ｉｌｌｉｎｏｉｓ Ｇｅｎｅｔｉｃ
Ａｌｇｏｒｉｔｈｍｓ Ｌａｂｏｒａｔｏｒｙ， Ｕｒｂａｎａ， ＩＬ． １９９７．［２］ ＦＯＲＴＲＡＮ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ （ＧＡ） Ｄｒｉｖｅｒ Ａｖａｉｌａｂｌｅ ａｔ： ｈｕｐ：／／ｃｕａｅｒｏｓｐａｃｅ．ｃｏｍ／ｃａｒｒｏｌｌ／ｇａ．ｈｔｍｌ［３］虞清泉，朱思铮，查学军．托卡马克等离子体平衡的数值研究．计算物理，２０００，１９（５） ４１３－４１８．
１１０２计算机技术与应用进展－２００４
Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｍａｓｔｅｒ－Ｓｌａｖｅ Ｐａｒａｌｌｅｌ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ
Ｆｒａｍｅｗｏｒｋ
Ａｎ Ｚｈｕ－ｌｉｎｔ Ｌｉｕ Ｘｉａｏｐｉｎｇｔ＇２ Ｚｈａｎｇ Ｗｅｉｌｉｎ３
ＶＣＣ Ｄｉｖｉｓｉｏｎ， Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ＆Ｉｎｆｏｒｍａｔｉｏｎ， Ｈｅｆｅｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｈｅｆｅｉ， ２３０００９， Ｃｈｉｎａ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｐｌａｓｍａ Ｐｈｙｓｉｃｓ， Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅ， Ｈｅｆｅｉ， ２３００３１， Ｃｈｉｎａ３ Ａｎｈｕｉ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ａｒｃｈｉｔｅｃｔｕｒｅ＆Ｉｎｄｕｓｔｒｙ， Ｈｅｆｅｉ， ２３００２２， Ｃｈｉｎａ
Ａｂｓｔｒａｃｔ Ｍａｓｔｅｒ－Ｓｌａｖｅ ＧＡ ｆｒａｍｅｗｏｒｋ ｉｓ ａｎ ｏｐｅｎ ａｎｄ ｒｅｕｓａｂｌｅ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ｆｒａｍｅｗｏｒｋ． Ｉｔ ｉｓｄｅｖｅｌｏｐｅｄ ｂｙ ＶＣＣ Ｄｉｖｉｓｉｏｎ ｏｎ ＂Ｄ几．Ｃａｒｒｏｌｌ＇ｓ ＦＯＲＴＲＡＮ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ Ｄｒｉｖｅｒ＂． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ
ａｐｐｌｉｅｄ ｉｔ ｔｏ ａ ｐｈｙｓｉｃ ｃｏｍｐｕｔｉｎｇ ｐｒｏｂｌｅｍ． Ｔｈｅ ｐｒｏｇｒａｍ ｗａｓ ｔｅｓｔ ｏｎ ａ ｄｏｕｂｌｅ Ｘｅｏｎ ｗｏｒｋｓｔａｔｉｏｎ， ｔｈｅ ｒｅｓｕｌｔ
ａｎｄ ａｎａｌｙｓｉｓ ｗａｓ ｇｉｖｅｎ ｔｏｏ． Ｋｅｙｗｏｒｄｓ Ｐａｒａｌｌｅｌ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ； Ｍａｓｔｅｒ－Ｓｌａｖｅ； Ｐｈｙｓｉｃ ｃｏｍｐｕｔｉｎｇ