并行遗传算法.ppt

《并行遗传算法.ppt》由会员分享，可在线阅读，更多相关《并行遗传算法.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、并行遗传算法现在学习的是第1页，共19页遗传的基本概念遗传算法（genetic algorithms,简称GA）是J.Holland于1975年受生物进化论的启发而提出来的。GA是基于“适者生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”适者生存的过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。优点：隐含并行性 全局解空间搜索能力现在学习的是第2页，共19页遗传与算法的对应遗传算法通过模拟自然界优胜劣汰的进化现象，将搜索空间映射为遗传空间，把可能的解编码成一个向量（即染色体），向量的每

2、个元素称为基因，然后通过不断计算各染色体的适应度值，选择最好的染色体，获得最优解。现在学习的是第3页，共19页遗传算法的基本步骤确定决策变量及各种约束条件，即确定个体的表现型X和问题的解空间；建立优化模型，即确定目标函数的类型；确定表示可行解的染色体编码方案，即确定出个体的基因型X及遗传算法的搜索空间；确定编码方法，即确定出由基因型X到个体表现型X的对应关系或转换方法；确定个体适应度的量化评价方法，即确定由目标函数值f(x)到个体适应度F(x)的变换规则；设计遗传算子，即确定出选择、交叉、变异的具体操作方法；确定遗传算法的有关运行参数，即确定遗传算法的Pc,Pm等参数。现在学习的是第4页，共1

3、9页特点遗传算法以决策变量的编码作为运算对象；遗传算法直接以目标函数值作为搜索信息，它使用由目标函数值变换得到的适应度函数值作为下一步搜索方向和范围的判断标准；遗传算法同时使用多个搜索点的搜索信息。它是从很多个体所组成的一个初始群体开始最优解的搜索，而不是从单一的个体开始搜索。这样可以避免一些不必要的搜索，其实内在包含了算法的隐含并行性；遗传算法属于非确定性的概率算法。正是由于它的不确定和概率性，导致算法找到的解只能够是相对最优解。现在学习的是第5页，共19页遗传算法的实现确定问题的编码方案确定适配值函数设计遗传算子算法参数选择，主要包括种群数目、交叉与变异概率、进化代数等。确定算法的终止条件

4、。现在学习的是第6页，共19页编码编码就是将问题的解用一种计算机可以识别的码来表示，将问题空间的状态空间与GA的码空间相对应。GA的优化过程是在一定编码机制对应的码空间上进行的，因此编码的选择是影响算法性能与效率的重要因素。编码方式：二进制编码方法 格雷码编码方法 浮点数编码方法通常所采用的编码方式是二进制编码。现在学习的是第7页，共19页二进制编码方法二进制编码所构成的个体基因是一个经过编码的符号串，二进制编码符号串的长度和问题的精度有关。假设问题的参数取值范围是Umin,Umax,使用长度为L的二进制编码符号串表示该参数，则能产生2L种不同的编码。若参数的编码的对应关系如下：0000000

5、00000=0Umin 000000000001=1 Umin+111111111111=2L-1 Umax二进制的编码精度为：设每个个体的编码为：对应的解码公式：现在学习的是第8页，共19页适配值函数适配值函数用于对个体进行评价，是优化过程发展的依据。在简单问题的优化时，通常可以将目标函数直接变换成适配值函数，譬如将个体X的适配值f(x)定义为M-c(x)或eac(x),其中M为一足够大正数，c(x)为个体的目标值，a0。在复杂问题的优化时，往往需要构造合适的评价函数，适应GA进行优化。现在学习的是第9页，共19页算法参数选择种群的数目：影响算法优化性能和效率。种群太小导致采样点数目不足，算

6、法性能低；而种群数目太大又会增加计算量，导致收敛时间过长。所以在设计算法时应该针对具体问题选择适宜的种群数目；交叉概率：用于控制交叉操作的频率。概率太大，种群中串的更新很快，会使高适配值的个体很快被破坏掉；概率太小，交叉操作很少进行，会使搜索停止不前；变异概率：增加种群多样性。基于二进制编码的GA中，一个非常小的变异率就会改变整个种群的基因。变异概率必须取一个适当的值，太小不会产生新个体，太大又会使GA完全的随机搜索；总结：遗传算法参数的选择是非常重要的，同时也非常复杂，参数选取需要按照问题的实际大小来进行选择。现在学习的是第10页，共19页选择算子选取选择的定义：从群体中选择优秀的个体，淘汰

7、劣质个体的操作。选择算子的作用：将优化的解直接遗传到下一代，或通过配对交叉的方式遗传到下一代。常用选择算子：适应度比例法，也叫赌轮法或蒙特卡罗法。选择执行过程：1)计算出群体中所有个体适应度的总值；2)计算每个个体相对适应度，即个体遗传到下一代的概率；3)使用模拟赌轮操作(srand(0,1)来确定各个个体被选中的次数。假设群体的大小为n，其中个体i的适应度值为fi，个体i被选择的概率pi表示为Pi反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。适应度越高，被选中的概率越高。现在学习的是第11页，共19页算法终止条件在实际中算法是不允许无止境的发展下去的，而且对通常问题的最优解具有

8、不确定性，因此需要一个条件来终止算法的进程。目前最常用的终止条件是事先给定一个最大进化步数，或者判断最佳优化值是否连续且经过若干步后都没有变化等。现在学习的是第12页，共19页隐含并行性设为一小正数，L(l-1)+1,N=2l,2，则遗传算法一次处理的存活概率不小于1-且定义长度不大于L的模式数位O（N3）.遗传算法表面上仅对每代的N个个体作处理，但实际上并行处理了大约O（N3）个模式，并且无额外的存储，这正是遗传算法具有高校搜索能力的原因，这就是遗传算法的隐含并行。现在学习的是第13页，共19页并行遗传算法传统的遗传算法出现的问题：局部搜索性能较差，对某些分布变化缓慢，面对大型计算问题速度难

9、以达到要求并行遗传算法提出：在遗传算法并行运算的基础上，通过多种群并行进化和引入迁移算子进行进行种群之间的信息交流，实现多种群的协同进化。通过人工选择系数对每个种群最优化个体保存，通过对协调种群间的信息交换策略得到最好的进化效果。遗传算法的并行化实现就是将进化过程划分到不同的计算节点上，进行分布式进化，并通过一定的种群间信息交换策略实现优良基因的转换。现在学习的是第14页，共19页并行遗传算法的分类标准型并行方法：未改变串行遗传算法的基本特点，在一个总体的环境中实现进化运算，它需要使用一个统一的群体。实现时需要一个全局存储器和一个统一的控制机构来协调群体的遗传进化过程及群体之间的通信过程。缺点

10、：运行速率低。分解型并行方法：将整个群体分解为几个子群体，各子群体彼此分配在不同的节点上，各自运行自身节点上的遗传算法，在适当的时候各节点之间交换信息。这种实现方法比较符合个体自然进化的过程，保存了各节点上群体进化的局部特性，有效回避了普通遗传算法早熟现象。目前比较常用的类型是分解型并行方法，按照不同的组织结构，它又可以分为下面三种不同的类型：主从式并行计算粗粒度并行计算细粒度并行计算现在学习的是第15页，共19页主从式并行计算在这种并行方式中，一个主过程调节若干个仆过程。其中主过程控制选择、交叉和变异，仆过程仅执行适配值的计算。缺点：1、各仆过程计算适应度值的时间存在明显差异时，将会照成整个

11、系统长时间的等待；2、整个系统可靠性较差，对主过程状况的依赖性较大。伪代码：Begin(1)产生一个初始群体(2)while running do (2.1)for=1 to s do计算个体i的适应度值(并行部分)（2.2）选择、交叉、变异操作，产生子代（2.3）子代取代父代，形成新一代个体End whileEnd现在学习的是第16页，共19页粗粒度并行算法在自然界中，物种的群体系由一些子群体构成。在处理器比较少的情况下，可以将群体分为若干个子群体，每个子群体包含一些个体，每个群体分配一个处理器，让它们互相独立的并行执行进化，每经过一定的间隔（即若干个进化带），就把最佳个体迁移到相邻的子群体

12、中。算法代码：Begin(1)产生一个初始群体并将它划分为p个子群体(2)for 1 to p do /*P表示处理器个数，也是子群体的个数(2.1)初始化(2.2)评估第一代子群体的适应度(2.3)while condition to(2.3.1)for J=1 to H(generations)doa、选择父代b、交叉操作c、子代变异d、子代取代父代形成新一代子群体e、评估子代的适应度end for(2.3.2)选择要迁移出去的个体(2.3.3)do step a and b in parallel /*这里发送和接收进程是并发执行的 a、发送要迁出的个体b、接手迁入的个体end whil

13、eend forend现在学习的是第17页，共19页细粒度并行算法如果并行系统中有足够多的处理器，那么系统可以为每个个体分配一个处理器，让它们相互独立的并行执行进程，这样就能获得并行遗传算法的最大可能的并发性。代码：Begin(1)产生一个初始群体并将它分配到P=N个处理器上；(2)For=1 to N dowhile running do(2.1)do step(a)and(b)in parallel(a)接收迁入个体(b)发送本个体(2.2)对迁入个体进行适应度评估(2.3)从迁入的个体中选择对象(2.4)交叉操作(2.5)子代变异(2.6)评估本个体及其后代(2.7)用后代取代本个体 end whileEnd forEnd现在学习的是第18页，共19页谢谢大家！现在学习的是第19页，共19页