1 分布式遗传算法简介

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

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

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

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）得到所有客户的数据，交换基因数据，并将数据传回；

        通讯协议的实现最有力的工具是采用有限状态机来表示。

        有限状态机各个状态转移的条件如下：

（1）如果当前状态为UNCHECKED_STATE，当客户送来命令字串“PARA”时转到状态PARA_STATE；

（2）如果当前状态为PARA_STATE，当客户送来正确的数据串“ID GeneNumber ExchangeMember ExchangeFrequency ”（该数据串的意为，求解问题的代码，此数据相同表示各个客户求解的是同一问题，第二个参数意为交换的个体数，第三个参数意为每个个体的基因数，第四个参数意为交换代频）时转到状态CHECKED_STATE，如果此时是第1个客户在进行通讯，即将其参数作为进行分布式计算的参数，如果不是第1个客户，则要求其参数和已有的参数一致否则服务器发送错误码给客户，并且不做状态转移；

（3）如果当前状态为CHECKED_STATE，当客户送来命令字串“DATA”时转到状态DATA_STATE；

（4）如果当前状态为DATA_STATE，接受客户送来的基因数据，如果数据全了，即各个客户都已将数据送到，则按照一定的策略交换数据，并将数据传回到客户，状态转移到CHECKED_STATE，如果数据未全，进入READY_STAT

E，此时远端客户处于等待数据阶段；

        注意这里的状态机之间的转换都是发生在服务器上的，即与客户端实际交互的插口（Socket）相关。

        分布式遗传算法程序客户的退出有两种情况：

（1）异常退出（客户端计算出现问题，这时客户给服务器发送命令“ABORT

”，出现这种情况的原因在于客户端发生了错误或是在调试阶段，需要提前中断计算）；

（2）正常退出（客户计算结束，这时客户给服务器发送“SUCCESS”；

        采用典型的客户服务器，服务器的各个插口是在同一线程中的。所以有效的通讯形式是尽量快地对客户传入的信息进行处理，一般来讲互传的数据不宜过大。单线程的优点是不需考虑同步的问题。当然，采用多线程就会更加灵活，不过编程较复杂，需要考虑线程之间的同步。由于本章的研究重点在于分布式遗传算法本身，所以就没有在多线程方面进行深入的研究。本分布式计算的服务器采用单线程方式。

        在本章分布式遗传算法的实现中，选择用于交换个体的方式是常用的轮盘赌，所以在子群体中适应度越高的的个体越容易被选中用于交换。

        在服务器端对各个客户个体基因信息的处理采用顺序交换的方式。首先随机地将多个客户排序，然后顺序交换个体的基因信息。以三个客户为例，假设

当前随机的顺序为客户1﹑客户2﹑客户3，那么首先将客户3的个体数据暂存，然后将用客户2的数据替代客户3，客户1的数据替代客户2，最后将暂存的数据替代客户1的数据。

显然本算法采用的是“岛屿”模型。

3 结论及进一步的工作

        本章提出了分布式遗传算法在局域网微机环境下的一种实现，建立一种适用于分布式遗传算法的通讯协议—“DGAP”，个体之间进行迁徙采用的是“岛屿”模型，客户群体中选择进行迁徙的个体采用的是根据适应度进行“轮盘赌”的方式。多个算例表明算法计算性能令人满意。各个群体之间共同维持着一种“稳态”，同时各个子群体的规模可以相应降低。

       由于时间的关系，同时也由于分布式遗传算法的内容较多，所以作者认为在分布式遗传算法上还需要做较多的工作。

       工作重点之一是研究新的交换方式，比如可以考虑对子群体进行评估，即进行排名，在进行交换时将依据排名的不同而有所区别。比如采用第一名群体与第二名群体交换个体，第二名群体与第三名群体交换个体。这样做的好处是可以防止出现相差过大的群体之间交换个体(即可能出现最差群体与最优群体之间交换数据 )，从而导致分布式遗传算法最优性能的降低。另外可以考虑对不同的客户采用不同的遗传参数（复制概率﹑变异概率等），从而可以在一定程度上增加客户的多样性。

        对于问题规模较大﹑模型分析本身就很费时间的优化问题，可以将群体分布到网络环境下进行计算，当然这和一般的分布式遗传算法本质上不同。在此考虑的实际上只是一个群体。可以认为是单个群体的分布式计算。

        最后，作者认为，建立一个功能比较完整和自主版权的分布式计算编程环境是很有必要的。最好的方式是基于UDP的Socket编程，这样效率﹑跨平台等方面都有足够的保证，缺点就是编程的难度较大。 当然也可以采用成熟的分布式计算标准DCOM和CORBA。

        另外由于教研室计算机数量所限，没有讨论大规模分布式遗传算法需要注意的问题。随着硬件条件的成熟，该方面的研究必然将成为一个重点，实际上美国现在的一些大学和研究机构已经将数千台采用高速局域网（一般为光纤网）互连的高性能计算工作站作为计算集群来求解工程问题。