第五章 分布式遗传算法研究

§5.1 分布式遗传算法简介

遗传算法的基本结构及特征决定了它特别适合大规模并行。一些研究表明，在并行或分布式系统上进行演化计算，不仅可以提高解题的速度和解的质量，甚至可以获得超线性的加速比。因而，近年来，关于遗传算法并行实现的研究受到了人们的广泛重视。

分布式遗传算法一般实行粗粒度及群体级并行，各子群体间的相互作用较弱，主要依靠一些几乎串行的遗传算法来加速搜索过程。群体级的并行即是将一个大群体按照硬件的结构划分为一些子群体，这些子群体一般独立地演化，即它们在自身内部进行选择及遗传操作，只是经过一定的代数才在子群体间交流一些信息，即所谓的迁移模型。

在迁移模型中，群体的组织方式通常是一个大群体划分为一些子群体，每个子群体自成为一个单位，只是在子群体之间实行个体的迁移，即个体从一个子群体迁移到另外一个子群体，迁移量的多少通常由两个参数来确定：迁移代频和迁移率。这两个参数的大小以及实行迁移的方式决定了迁移模型之间的差别。若个体的迁移是完全随机的，即从子群体中均匀随机地进行抽样，然后再随机地迁移到另一个群体中，这时可以认为这些子群体是完全独立的，个体的选择和迁移对这些子群体都是对等的，即相当于将这些子群体看成是一些独立的岛屿，个体从一个岛屿到另外一个岛屿的机会是均等的，这种迁移模式称为“岛屿”模式，是研究的比较多的一种模型。在实现并行时，子群体的互连方式既可以是总线形，也可以是环形，或二维阵列，超立方体等。可以根据互连方式的区别来确定子群体间的相邻关系，从而使个体迁移到相邻子群体具有较大的概率，这样进行迁移的方式称为“脚踏石“模型。

§5.2 分布式遗传算法的实现和算法研究

目前随着以高主频Pentium II﹑Pentium III ﹑AMD K-7为代表的高性能微机的逐渐应用，微机的性能已经得到了很大的提高，运算速度已经和以前小型机﹑中型机相当，而网络速度的提高和价格的降低也使得10M﹑100M甚至千兆以太网逐渐普及。进行分布式计算的硬件条件比较容易得到满足。另一方面，高性能并行计算机价格居高不下，大多数人对其软硬件也很不熟悉。所以作者的研究重点自然地放在分布式遗传算法在微机环境下实现的研究上。

从微机操作系统来看，目前最普及的是微软的Windows操作系统（包括Windows 9X系列和NT系列，以及最新的2000系列），以及Linux操作系统，由于作者可以得到的研究环境为高性能的Windows工作站，所以将研究在Windows环境下分布式遗传算法的实现。

如何在Windows环境下进行分布式运算，有较多的方法，以下为其中最常用的几种：

（1）采用微软的DCOM标准；

（2）采用分布式对象CORBA标准；

（3）采用Windows Socket编程；

DCOM技术是微软推荐使用的，比较成熟，开发工具较多。CORBA技术可以跨平台，即可以在Windows和Unix系统下进行通讯，但是开发工具较少，一般都采用Borland公司的Builder系列产品进行开发。目前DCOM和CORBA的技术资料较少，另外DCOM和CORBA的底层实际上也是采用TCP/IP协议实现的，Windows Socket就是在Windows环境下对TCP/IP协议的编程接口，可以认为Windows Socket技术比DCOM和CORBA技术更加底层，同时DCOM和CORBA还有许多面向对象的实现，即可以在网络环境下实现对象的透明访问。这三种技术中，作者最为熟悉的是采用Windows Socket编程。由于本研究的重点不在于建立一个十分完善的分布式环境，所以本章均采用Windows Socket编程。

TCP/IP协议中的传输协议有面向连接的TCP协议和面向无连接的UDP协议，由于作者的实验环境为100M高速局域网，而且传输的数据量也不是太大，所以就选择了效率稍低﹑但编程相对较简单的TCP协议作为传输协议。

分布式实现采用客户服务器方式，即数据的传输只是发生在客户和服务器之间，客户之间无直接的通讯，客户的数据由服务器集中处理。服务器的功能相对比较简单，主要作用是为各个客户传来的数据进行缓冲，等待客户之间的同步，按照一定的策略交换对应于各客户的数据并且将交换后的数据发回给客户。基于客户服务器方式的通讯需要遵循一定的协议，作者采用如下思路建立相应的通讯协议，并将其命名为分布式遗传算法协议DGAP（Distributed Genetic Algorithmic Protocol）。

在分布式遗传规划的计算过程中，各个子群体不允许中途退出，由于遗传规划本身的计算量很大，一般来说一个客户就对应着一台计算机，所以在此与一般的客户服务器程序不同的是，在开始阶段就必须明确知道参与计算的客户（计算工作站）的数量，服务器在所有的客户均与之连接上并经过验证后，给客户下达开始计算的命令，各个客户机开始进行计算，当客户机演化到指定的代数后，计算暂停，各客户分别与服务器进行通讯，上传用于进行交换的个体基因数据，然后等待服务器再次与自己联系，得到服务器经过处理后的基因数据，将这些基因数据转化为相应的个体加入到当前的群体中，继续迭代过程。重复以上过程，直到各个客户端求解结束，输出结果。

在以上过程中，如果发生任何的网络错误，整个的分布式计算即宣告失败。以上模型是基于传统的分布式计算的，在网络环境良好时是可行的，由于实验的背景为高速局域网，该条件可以实现。如果在网络条件不好，比如在广域网上实现时，该模型是不适合的，必须进行适当的修改。

下面是客户和服务器的运行流程：

对于客户：

（1）连接服务器；

（2）输入基本参数并得到验证；

（3）开始计算；

（4）到设定的代数，向服务器发送进行交换个体的基因数据，并等待服务器发回数据；

（5）得到服务器发回的数据，将数据转换为对应的个体，随机替换掉当前群体的个体，继续运算；

对于服务器：

（1）等待客户的连接请求；

（2）接受客户；

（3）验证客户参数，验证失败则给客户发送错误码，成功则继续；

（4）等待客户上传基因数据，如果只得到部分客户的数据，令已发送数据的客户等待；

（5）得到所有客户的数据，交换基因数据，并将数据传回；

通讯协议的实现最有力的工具是采用有限状态机来表示，图5.1是服务器端与客户进行交互的有限状态机，值得强调的是有限状态机对于不同的客户是不同的。