基于动态种群的分布式遗传算法

第２４卷第５期　２００２年ｌＯ月　武汉理工大学学报・信息与管理工程版　Ｖ０１．２４　Ｎｌ０．５　Ｏｃｔ．２００　ＪＯＵＲＮＡＬＯＦ哪（肌　鱼　婴　

文章编号：ｌｏｏ７—１４４ｘ（２ｃｘｒ２）ｏｓ—ｏｏｏ９—０４　

基于动态种群的分布式遗传算法　

熊盛武，王冠　

（武汉理工大学计笋机科学与技术学院，湖北武汉４３００７０）　

摘要：提出了一种基于动态种群模型的分布式遗传算法并对其进行了理论分析，该模型由传统并行模型演　变而来，但更适合于分布式并行处理。在一组由Ｐｃ机构成的网络环境下给出了该算法求解１ｓＰ问题的数值　结果，数值试验证明了该算法的有效性和可行性。　

关键词：动态种群；分布式遗传算法；可扩展集群计算；ＴＳＰ　

中图法分类号：ＴＰ　３０１　文献标识码：Ａ　

１　引　言　

遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ＧＡ）是一类借鉴　

生物界自然选择和自然遗传机制发展而来的随机　

搜索算法，在并行计算机上实现ＧＡ是增加其性　能和效率的有效途径¨Ｊ。近年来，随着计算机网　

络技术的发展和节点机性能价格比的提高，利用　

现有的计算资源，在局域网上开发分布式并行系　

统进行并行计算有着巨大的潜在价值，基于网络　

计算的分布式并行算法将为大规模工程与科学计　

算开辟一个新的领域。对于一般用户来说，廉价　

的可扩展集群计算环境是ＧＡ发挥其搜索效率和　大规模并行性的最有效的实现平台ｌ２Ｊ。笔者主要　

介绍基于动态种群（Ｄｙｎａｍｉｃ　Ｄｅｍｅｓ，ＤＤｓ）模型的　

分　式遗传算法在ＴＳＰ问题上的应用　３，通过在　ＰＣ机构成的集群计算平台上运用ＤＤｓ［　］求解ＴＳＰ　

问题的试验结果，证明了该方法具有良好的可扩　

展性和加速比。　

２可扩展集群计算　

２．１集群计算　

目前，并行平台从昂贵的、面向特定应用的大　

规模并行计算机（Ｍａｓｓｉｖｅｌｙ　Ｐａｒａｌｌｅｌ　Ｐｒｏｃｅｓｓｏｒｓ．　

ＭＰＰ）向网络计算机转变的趋势越来越明显，计算　

机网络或者集群已经变成了一个非常有吸引力的　

工具。而以ＰＣ机集群作为实现并行的平台具有　

更多的优点，它们建立在容易购买且价格低廉的　

商品化硬件（ＰＣ机）、快速局域网和标准软件组件　

（比如ＵＮＩＸ、ＰＶＭ并行编程环境）之上。这些系统　是可扩展的，它们可以根据预算和计算能力要求　

做出调整。　

２．２并行群体模型　

为了实现并行遗传算法（Ｐａｒａｌｌｅｌ　Ｇｅｎｅｔｉｃ　Ａｌｇｏ．　

ｒｉｔｈｍ，Ｐ（　），需要对传统的ＧＡ进行并行分割，把　

串行ＧＡ等价地变换成一种并行方案，将ＧＡ的结　

构修改成易于并行化实现的形式，形成并行群体　

模型。　

①全局并行模型。全局并行模型只有一个群　

体，所有个体的适应值计算都是独立的，个体之间　

可以任意匹配，因而在群体上所作的选择和匹配　

是全局的。全局模型易于实现，但是在异构环境　

中，当工作负载过大时，很容易产生“瓶颈”效应，　

因为所有的进程都不得不等待最后一个完成适应　

值计算的个体，然后才能进行选择操作。　

②粗粒度模型。粗粒度模型是对经典ＧＡ结　

构的扩展。它将群体划分为多个子群体，每个子　

群体独自运行ＧＡ，区域选择取代了全局选择，配　

偶取自同一区域，子代与同一区域中的亲本竞争，　

所以又称为孤岛模型。但是群体之间也会不时交　

换个体，这种新的遗传操作被称作迁移。我们知　

道粗粒度模型中，子群体规模比串行ＧＡ群体规　

模小，所以它的收敛显然要比串行ＧＡ快，解的质　

量可能也会下降。粗粒度模型非常适合于异构型　

计算环境，惟一的问题就在于解的质量。此外，它　

的可扩展性也是一个问题。　

③细粒度模型。细粒度模型将群体划分为许　

多非常小的子群体，理想情况是每个处理单元　

（Ｐｒｏｃｅｓｓｉｎｇ　Ｅｌｅｍｅｎｔｓ，ＰＥ）上只有一个个体。这类　

收稿日期：２０ｏ２—０４—２４．　作者简介：熊貔武（｛９６７一），男，湖北成宁人，武汉理工大学计算机科学与技术学院副教授．　基金项目：ｆ目家ｆＪ然科学基金资助项ＦＩ（６０１７３０４６）；武汉市青年科技晨光计划资助项目（２０００５ｏｏ４０４Ｏ）

　维普资讯 http://www.cqvip.com ｌＯ　汉理工大学学报・信息与管理　猩　

模型适合于ＭＰＰ，它的主要缺点是通信耗费非常　

高，所以不适合异构型计算环境，否则也会产生　

“瓶颈”。　

２．３并行虚拟机　

并行虚拟机（ＰｖＭ）是支持异构型网络并行计　

算的软件系统，它主要是基于消息传递的并行通　

讯库。通过它，用户可以将一组由不同网络连接　

的、不同类型的、采用ＵＮＩＸ的计算机看作一个虚　

拟的并行计算机资源。　

２．４旅行商问题　

旅行商（ＴＳＰ）是图论中有代表性的组合优化　

问题，ＴＳＰ问题在实际应用中具有很重要的意义，　

例如可以用来解决分配问题、路径问题、车辆调度　

问题、网络问题等。ＴＳＰ算法其定义域是一个符　

号空间，由于组合爆炸，其解空间通常非常大，属　

于非多项式确定（ＮＰ）问题，利用传统优化方法求　

解这一问题是非常困难的。用ＤＤｓ求解ＴＳＰ问题　

是对其性能的一个极好考验。　

３动态种群模型在ＰＶＭ环境下求解ＴＳＰ　

问题的算法描述　

３．１　Ｍ　ＡＧＥＲ进程　它是系统中惟一的进程，负责启动整个程序。　

它利用ｐｖｍ—ｓｐａｗｎ语句初始化ＳＯＲＴＥＲ进程、　

ＣＯＵＮＴＥＲ进程以及所有的ＳＬＡＶＥ进程。并把　

ＳＯＲＴＥＲ和ＣＯＵＮＴＥＲ进程的进程标识符（Ｐｒｏｃｅｓｓ　

ＩＤ，ＰＩＩ））打包发给所有的ＳＬＡＶＥ进程，接着等待　

接收ＳｏＲ１　Ｒ进程发来的终止消息，之后向　

ＣＯＵＮＴＥＲ进程和所有的ＳＬＡＶＥ进程发出终止消　

息。　

３．２　ＣＯＵＮｒＩＥＲ进程　

它和ＭＡＮＡＧＥＲ一样，也是整个系统中惟一　

的进程。它利用ｐｖｍ—ｓｐａｗｎ语句初始化所有　

ＭＡＳＴＥＲ进程，然后进行负载平衡的动态管理。　

它的流程如下。　

①初始化ＭＡＳＴＥＲ进程，形成一个首尾相接　

的ＭＡＳＴＥＲ进程链表。　

②等待ＳＬＡＶＥ进程发来的消息，计数器归　

零。　

③确认消息的来源是ＳＬＡＶＥ后（通过消息标　

志符），向ＳＬＡＶＥ发送当前ＭＡＳＴＥＲ进程的ＰＩＤ，　

计数器加１。　

④通过计数器确认当前ＭＡＳＴＥＲ进程得到足　

够的ＳＬＡＶＥ个体后，下一个ＭＡＳＴＥＲ设为当前　

ＭＡＳ１ＥＲ。　

⑤ｇｏ　ｔＯ②。　２００２年１Ｏ月　

⑥当收到ＭＡＮＡＧＥＲ进程发来的终止消息　

后，进程结束，并向ＭＡＳＴＥＲ进程发送终止消息。　

３．３　ＳＬＡＶＥ进程　ＳＬＡＶＥ进程的数目可以根据需要确定，它的　

个数就是个体数。它的流程如下。　

①随机产生一个ＴＳＰ个体并计算出自己的适　

应值。　②通知ＳＯＲＴＥＲ进程和ＣＯＵＮＴＥＲ进程。　

③等待ＣＯＵＮＴＥＲ进程发来的ＭＡＳＴＥＲ进程　

的ＰＩＤ，然后把自己的适应值和ＰＩＤ打包发给该　

ＭＡＳＴＥＲ进程。等待ＭＡＳＴＥＲ进程进行选择和配　

对。　

④等待接收消息。当确认消息是ＭＡＳＴＥＲ进　

程发来的复制消息和交叉消息时，ＳＬＡＶＥ进程进　

行复制、交叉、变异操作。计算出新个体的适应值　

并取代当前个体，进行个体更新。ｇｏ　ｔｏ＠。　

⑤收到ＭＡＮＡＧＥＲ进程的终止消息，进程结　

束。　

３．４　ＭＡＳＴＥＲ进程　

ＭＡＳＴＥＲ进程的个数根据需要而定，它的个　

数就是子群数。在接收到满足种群数目的个体之　

后，ＭＡＳＴＥＲ进行选择操作，确定需要进行复制操　

作和被复制操作的个体ＰＩＤ，以及需要进行交叉　

操作的两个配对个体ＰＩＤ，然后分别向这些个体　

发出复制和交叉消息。它的结束由ＣＯＵＮＴＥＲ进　

程控制。　

３．５　ＳｏＲｒＩＥＲ进程　

收到一个ＳＬＡＶＥ进程的消息，计数器加１，当　

满足演化代数后，向ＭＡＮＡＧＥＲ进程发出终止消　

息。　

４动态种群的理论分析　

ＤＤｓ具有类似于全局模型，在子群上又具有　

粗粒度模型的特点。前面已经介绍全局并行模型　

的选择操作是基于整个种群，个体有机会和整个　

种群中任何一个个体配对，搜索空间是全局性的；　

而粗粒度模型和细粒度模型的选择操作是在各自　

的子群体内完成，个体只能和子群体中的其他个　

体进行配对，搜索空间是局域性的。要使计算时　

间不至过长，使搜索空间达到尽可能的大，最好的　

办法就是个体的动态分配。从并行观点来看，基　

于ＤＤｓ的并行遗传算法是一种异步消息传递的　

算法，它的主要思想是在算法中避免等待最慢主　

机或最差个体，使得算法不至因等待而被拖延。　

它具有完全的可扩展性，从全局并行开始，随着改　

变每个种群所拥有的个体数，可以轻易地扩展到　维普资讯 http://www.cqvip.com 第２４卷第５期　于动态种群的分布述遗传篡　

细粒度模型。综上所述，可以得出ＤＤｓ具有以下　

几个优点：　

①具有较好的可扩展性和灵活性。　

②容错能力强。即使一些主机崩溃，算法依　

旧能够继续。　

③动态负载平衡。每个主机分配的进程数虽　

然一样多，但是通过动态分配个体，速度快的主机　

上的个体完成的遗传代数会比速度慢的主机上的　

个体完成得多。　

④简易的控制。　

ＤＤｓ模型所能获得的加速比主要受ＰＣ机硬　

件及网络环境的影响，并行一般不具有无限制的　

可扩展性，加速比会在达到某一极限后停止增加　

并开始下降，这是因为通信的消耗已经开始大于　

并行处理器增加所带来的好处。在这里：　

一　为ＣＯＵＮＴＥＲ进程循环一次运行时间；　

为ＭＡＳＴＥＲ进程循环一次运行时间；　ｌ　为　

ＳＬＡＶＥ进程循环一次运行时间；ｔｓｅｎｄ为发送一个　

消息所花的时间；Ｎ为总的个体数（ＳＬＡＶＥ的个　

数）；Ｍ为子群数（ＭＡＳＴＥＲ的个数）；ｎ为每个子　

群拥有的个体数（ｎ＝Ｎ／Ｍ）。　

为了便于分析，考虑理想情况，省略循环和条　

件判断语句的运行时间。　

所以　

Ｔｃ（＇ｌｌｎｔｅｒ＝Ｎ×ｔｓｅｎｄ　

Ｔｍ∞ｔｅｒ：ｎ×ｔｓｅｎｄ＋ｔｓｅｌｅｃｔｉｏｎ　

这里／ｓｅｌｅｃｔｉｏｎ是在整个种群里进行选择操作所　

需要的时间。　

ＳＬ，￣ＶＥ进程循环一次需要先后与ＭＡＳＴＥＲ进　

程、ＣＯＵＮＴＥＲ进程、配对的ＳＬＡＶＥ进程进行信息　

交换，此外还要完成适应值计算、交叉、变异等遗　

传操作，因此：　难的。当通信消耗很大时，Ⅳ要很小，即要减小　

群体规模，但是这样往往会使算法陷入局部最优。　

一般而言，处理器能力越强，群体可以越大而且结　

果越好。很难从理论上预测ＤＤｓ的性能，但是可　

以确定的是，在遗传操作特别是适应值计算比较　

复杂（ｔｆｉｔｎ　较大）的问题上，运用ＤＤｓ的性能会比　

较好。这需要通过实验来证明。　

５实验结果及分析　

１ａｖｅ＝ｔｆｉｔｎｅｓｓ＋ｔｍｕｔａｔｌｏｎ＋￡ｃｒｏｓ８０ｖｅｒ＋３　ｔｓｅｎｄ　程序要正常运行必须满足条件　

。Ｔｏ０Ｉｌ　ｔ　ｒ≤Ｔｓｌａｖｅ＋　ｌａ８ｔ　

综合以上各式可得到：　

Ｎ　≥ｌＸ　ｔ　ｓｅｎｄ　因为　

（ｎ＋３）×ｔｓｅｎｄ　．　—　：　

所以　

±　≥Ⅳ　

￡　１代表通信消耗，它一般由机器硬件、机器　

负载、网络速度以及网络负载决定，判断它是很困　Ｐ实验程序由６个文件组成，分别是在　

ＬＩＮＵＸ　７．１下Ｃ编写的Ｍａｎａｇｅｒ．ｅ、Ｃｏｕｎｔｅｒ．ｅ、　

Ｓｏｒｔｅｒ．ｅ、Ｍａｓｔｅｒ．ｅ、Ｓｌａｖｅ．ｅ以及Ｍａｋｅｆｉｌｅ．ａｉｍｋ文　

件。试验是由处于同一局域网中的４台ＰＣ机（Ｐ２　

—４ＯＯ，２台Ｐ２—２６６，Ｐ２—２３３）组成的ＰＣ机集群　

上完成的，并行编程环境是ＰＶＭ。程序中重要参　

・数值由表１中给出。　

表１实验参数