7遗传算法与并行处理.doc

第七章 遗传算法与并行处理71 遗传算法固有的并行性及其并行化的困难自然界的进化过程本身就是一个并行过程。遗传算法来源于自然进化，是对自然进化过程的机器模拟，很自然地也就继承了自然进化过程所固有的并行性。Holland在最早提出遗传算法的理论和模型时就阐述了它所包含的固有的并行性。遗传算法在并行实现上的因难：标准遗传算法在并行化的过程中会遇到通信量过大的困难。必须对标准遗传算法进行改造，尽量减少巨量通信从而获得高效率。但是，任何对标准遗传算法的改造都必须以尽可能少地影响其进化效果为前提。72 遗传算法的并行化途径721 主从式（master-slave）并行化方法当施行适应度评估时我们可以相互独立地评估群体内的每个个体的适应度，从通信量的角度来讲，这意味着在评估进程之间无需通信。如单纯从减少通信量入手，也很自然地首先想到可将适应度评估等局部操作交给从处理器网络(slave)并行执行，而将选择、交叉等全局操作留给主处理器(master)串行执行、这就是所谓主从式并行化方法。因为无论当哪个处理器运行主算法时都要有同步机制，所以像这样来开发存在于遗传算法中的并发性效率还是不高的。这是由于主进程忙而子进程空闲以及子进程忙而主进程空闲等情况(即负载不均衡)所造成的。在上述算法的并行实现中，选择操作应该对整个群体的适应度有个全局的了解，这部分地决定了通信要求。主处理器必须知道每个个体的适应度值，所以必须支持多到一的通信。放牧式(farming)：放牧式的思想或结构适用于有一组相互独立的工作可以并发完成的问题。控制进程，即运行在根节点上的牧场主(farmer)进程将任务划分为工作包，然后将它们“放牧”到一组相同的工人进程上。用放牧式的思想来实现并行遗传算法是，让牧场主进程保存有整个群体的适应度值，它负责执行遗传操作，而适应度评估工作则交由工人网(workers)完成。接收到任务的第一个空闲的工人把它承担下来，完成它并将结果送回给牧场主。通常，每个处理器上有一个工人进程，必须以一个合适的拓朴(如流水线)结构来连接处理器，并增加选路进程负责给空闲的工人进程送去工作包，给控制进程回送结果。因为集中存储群体易造成瓶颈，所以任何基于放牧式的并行遗传算法的可扩放性都不好。可能采用放牧式的理由如下：(1) 放牧式很通用且容易实现。(2) 如果个体评估需时相同，则放牧式效率很高且负载均衡(3) 可以用放牧式来模拟迁杉式和扩散式，(4) 放牧式将评估交给工人网络来完成，降低了对主处理器的内存要求。实现时，体系结构可以采用树而不是流水线，控制进程放在根节点上。但是，这种方式也只有在交叉和评估比选择和传送费时很多的情况下才有效。因为它不是将进化过程并行化的“自然”方式，所以无法得到令人满意的结果。即使只用少量个处理器，放牧式的加速比也很小。总的来说，主从式比较直观且容易实现，它并没有对标准遗传算法的框架结构作任何改动，所以不会影响其解决具体问题的效果。但是它不可避免地存在有负载不均衡的问题，而且通信量仍然很大，这使得它的效率不高，从而限制了它的实用性。722 粗粒度模型在自然界中，物种的群体是由一些个体组成。在处理器个数较少的情况下，我们可以将群体分为若干个子群体，每个子群体包含一些个体，每个子群体分配一个处理器，让它们互相独立地并行执行进化，每经过一定的间隔(即若干进化代)就把它们的最佳个体迁移到相邻的子群体中去。这种租粒度的并行遗传算法被称作迁移式(migration)或孤岛(islands)模型，可以描述如下：begin (1)产生一个初始群体并将它划分成p个子群体 (2)for il to p par-do (2.1)初始化 (2.2)评估第一代子群体的适应度(2.3)while running do (2.3.1)for j = 1 to n(generations) do(a) select parents(b) crossover(c) mutation(d) evaluate sub-population endfor(2.3.2) select emigrants/* 选择要迁移出去的个体 */(2.3.3) do step (a) and (b) in parallel(a) send emigrants/* 发送要迁移出去的个体 */(b) receive immigrants/* 接收迁入的个体 */endwhile endforend723 细粒度模型如果并行系统中有足够多的处理器，则我们可以将每个个体分配一个处理器，让它们互相独立地并行执行进化，这样就能获得并行遗传算法的最大可能的并发性，相应地称这种模型为细粒度模型，它可以描述如下：begin（1）产生一个初始群体并将它分配到P=N个处理器上（2）for i = 1 to N par-do while running do （2.1）do step（a）and（b）in parallel （a）receive immigrants/* 接收迁入个体 */ （b）send self/* 发送本个体 */ （2.2）evaluate immigrants /* 对迁入N个体进行适应度评估 */ （2.3）select mate from immigrants /* 从迁入的个体中选择对象 */ （2.4）reproduce /* 交叉 */ （2.5）mutate child/* 变异 */ （2.6）evaluate self and child/* 评估本个体及其后代 */ （2.7）replace self/* 用后代取代本个体 */ endwhile endforend在细粒度模型中，通常处理器被连接成平面网格（grid），每个处理器上仅分配一个个体，选择和交叉只在网格中相邻个体之间进行（根据一个预先定义的邻域结构来判定个体之间是否相邻）。这种细粒度的并行遗传算法被称作扩散式（diffusion）或邻域模型。73 粗粒度的孤岛模型在遗传算法的并行化过程中，为了减少通信量，可以降低全局评估和交叉的颇率，不是每代一次，而是迭代若干次以后再全局通信一次。自然界并不服从随机交配原则，群体常常是广泛分布的，只有孤立地看各个子群体内部时才是随机支配的。731 粗粒度模型的生物学依据断续平衡理论的两个基本原则：孤立发生的物种形成（即当个体被从地理上与他们共同的祖先分开后新物种的迅速进化）和静态平衡即停滞（即在一个稳定的环境中达到平衡后，物种的基因组成维持不变）。实际的观察导致如下假设：即若干个相互竞争的子群体，比起将所有个体都聚在一起的大群体，在搜索方面效率更高。生物进化史表明，这种孤岛方式不仅没有妨碍正常的进化，反而促成了目前干变万他的适应性很强的物种群体。粗粒度模型有几种变化形式：可以对不同的子群体赋以不同的控制参数以获得能适应不同环境的进化过程。在个体迁移方面也有一些不同的策略：（1）要迁移的个体可以选择适应度最佳的，（2）也可以只选择适应度不低于子群体内平均值的，（3）也可以是随机选择的。两个有趣的结论：一、随机选择迁出者所产生的效果至少不比任何其它方法差；二、孤岛模型仅需最小的迁移率就足以获得比随机交配（即串行遗传算法）更好的性能。733 孤岛模型在MIMD机器上的实现Tanese等首先在个超立方结构上实现了孤岛模型。n维的超立方是由N=2n个处理器构成的n维二进制立方体。每个处理器作为立方体的节点拥有自己的CPU和局部内存，处理器间的通信方式是消息传递。每个处理器都和其它n个作为其邻域的处理器直接相连，这使得立方体中任何两个处理器间的距离最大为n。结果：（1） 当保持群体大小不变，增加超立方的维数(即增加处理器个数)时我们发现，每个子群体迭代次数之和大致等同于一个串行实现要获得最佳结果所需的迭代次数。在恒定的迭代次数之内获得最大值，同时每代的计算时间又相等，但又是分布在若干个处理器上，这意味着达到了线性加速比。（2） 采用不同的参数设置，所得结果与最佳设置下获得的结果差不多，这说明在参数设置方面分布式算法比串行算法有更好的鲁棒性。（3） 通过实验验证了这样一个经验主义的假设：即在每个处理器分配一个子群体的孤岛模型的实现中仍然保持着串行遗传算法中由模式定理保证的效果。734 扩展的分布式遗传算法粗粒度模型的不足：最佳个体的多次迁移仍然造成了一定的通信开销，这使得其加速比达不到线性。而且因为选择的局部性，获得的解有可能不是全局最优的。Prahladah等提出的扩展分布式遗传算法(EDGA)是粗粒度模型的推广。它采用分布式子群体的概念去获取好的加速比，同时又采用全局搜索策略的概念去获取较好的最优解。根处理器执行对整个群体的全局选择，而处理单元(PE)执行对相应子群体的局部搜索。经过一个预定的间隔，根处理器和PE上的经过进化的群体相互交换，此周期重复循环一定次数，或直到满足终止条件为止。子群体的局部适应和整个群体的全局适应结合起来提供了一种在最佳搜索空间的快速搜索和找到更好的最佳解的能力。EDGA简单、高效，在现有的并行硬件系统上可以很容易地实现。这种算法可以获得很高的加速比，而且它还能使所有处理器达到负载平衡，从而保证并行系统能有好的性能。1EDGA的基本术语 总群体：放在根处理器上，其大小为PopSz。 子群体：总群体被分成大小为SubPopSzPopSzPE.num的子群体，它们被分配到各处理单元(PE)上，其中PE.num表示PE的数目。 归并子群体：进化后的子群体被从PE传送到根处理器上，归并形成新的总群体。 全局选择：从总群体中选择个体。 局部选择：从子群体中选择个体。终止条件：已达到已知的最佳适应度值等。2. EDGA的算法描述Randomly generate an initial population P0 of size PopSzDivide the Population into PE.num subpopulatlons of size SubPopSzCopy one subpopulatlon to each PESend the parameter values to all the PEsfor i1 to K do On root run SGA on P0 until all PEs Interrupt for all PEs par-do for generation=1 to G do Run sequential GA on subpopulatlon endfor Send interrupt to the root processor Send evolved subpopulatlon to root endfor Make population P1 With evolved subpopulations Make subpopulations with evolved P0 Send one subpopulatlon to each PE P0 = P1Endfor3EDGA的性能分析优点：(1)在根处理器和处理单元(PE)之间达到负载平衡，提高了处理器的利用率。(2)同时具备粗粒度模型的长处和主从式的全局选择的持点。7.4 细粒度的邻域模型这样产生的分布式计算模型包含有空间性的概念，遗传算法中群体里的个体被分配到给定空间环境(通常是排列成环形阵列的二维网格状以防止边界效应)中的特定位置。所以网格上的邻域关系就限定了个体间空间上的关系。遗传操作被看作随机的局部更新规则，这样该模型就是完全分布的而无需任何全局控制结构。对每个细胞而言，选择仅在赋给该细胞及其邻域的个体上进行；交叉也仅交配邻近的个体；而变异是标淮的。另外还增加了其它操作。因为遗传操作都成了局部操作，所以通信量大大降低。细粒度模型上的算法的基本框架如下：(1) 随机产生一个初始群体，并将个体一对一地分布到网格中的结点上，计算每个个体的适应度值。(2) 并发地对每个结点c执行(a)，(b)，(c)和(d)。a) 从c及其邻域中选择一个个体占据c。b) 从c的邻域中选择一个个体，根据概率Pc使其与c上的个体交叉，再将子个体之一赋给c。c) 对c上的个体根据概率Pm进行变异。d) 计算c上的新个体的适应度。(3) 若没结束，转去(2)。7.4.1 细粒度模型的理论基础细粒度模型上的遗传算法也叫作扩散式(diffusion)并行遗传算法，因为在此模型上同生类(结点的邻域就是该结点上的个体的同生类)的重叠可以使适应度高于平均值的模式(scheme)慢慢地扩散到整个群体。实验表明其中子代对父代个体的取代(replacement)对并行遗传算法的效率和性能都有深刻的影响。可选择的取代方式有：(1)直接取代。(2)仅当子代个体较优时才用它取代父代个体。(3)根据父代和子代个体的适应度差别而或然地取代(模拟退火)。7.4.2 细粒度模型的研究现状Manderick和Spiessens首先比较了并行遗传算法和标准算法的性能，结论是细粒度模型能提供对搜索空间的更彻底的探索，因为它的局部选择机制减轻了选择压力(这好比几个人搜索一大片地域，如果他们分工包干，一人负责一小块地方，则会比大家合伙干的效率要高)。这样，简单问题的求解效率可能不高，但难度较大的问题将从这种彻底搜索中获益。另外。他们还首次给出了关于算法对参