并行遗传算法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,并行遗传算法,并行实验室,遗传的基本概念,遗传算法（,genetic algorithms,简称,GA,）是,J.Holland,于,1975,年受生物进化论的启发而提出来的。,GA,是基于“适者生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”适者生存的过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。,优点：隐含并行性,全局解空间搜索能力,遗传与算法的对应,遗传算法通过模拟自然界优胜劣汰的进化现象，将搜索空间映射为遗传空间，把可能的解编码成一个向量（即染色体），向量的每个元素称为基因，然后通过不断计算各染色体的适应度值，选择最好的染色体，获得最优解。,遗传算法的基本步骤,确定决策变量及各种约束条件，即确定个体的表现型,X,和问题的解空间；,建立优化模型，即确定目标函数的类型；,确定表示可行解的染色体编码方案，即确定出个体的基因型,X,及遗传算法的搜索空间；,确定编码方法，即确定出由基因型,X,到个体表现型,X,的对应关系或转换方法；,确定个体适应度的量化评价方法，即确定由目标函数值,f(x,),到个体适应度,F(x,),的变换规则；,设计遗传算子，即确定出,选择、交叉、变异,的具体操作方法；,确定遗传算法的有关运行参数，即确定遗传算法的,Pc,Pm,等参数。,特点,遗传算法以决策变量的编码作为运算对象；,遗传算法直接以目标函数值作为搜索信息，它使用由目标函数值变换得到的适应度函数值作为下一步搜索方向和范围的判断标准；,遗传算法同时使用多个搜索点的搜索信息。它是从很多个体所组成的一个初始群体开始最优解的搜索，而不是从单一的个体开始搜索。这样可以避免一些不必要的搜索，其实内在包含了算法的隐含并行性；,遗传算法属于非确定性的概率算法。正是由于它的不确定和概率性，导致算法找到的解只能够是相对最优解。,遗传算法的实现,确定问题的编码方案,确定适配值函数,设计遗传算子,算法参数选择，主要包括种群数目、交叉与变异概率、进化代数等。,确定算法的终止条件。,编码,编码就是将问题的解用一种计算机可以识别的码来表示，将问题空间的状态空间与,GA,的码空间相对应。,GA,的优化过程是在一定编码机制对应的码空间上进行的，因此编码的选择是影响算法性能与效率的重要因素。,编码方式：二进制编码方法,格雷码编码方法,浮点数编码方法,通常所采用的编码方式是二进制编码。,二进制编码方法,二进制编码所构成的个体基因是一个经过编码的符号串，二进制编码符号串的长度和问题的精度有关。假设问题的参数取值范围是,Umin,Umax,使用长度为,L,的二进制编码符号串表示该参数，则能产生,2,L,种不同的编码。,若参数的编码的对应关系如下：,000000,000000,=0U,min,000000000001=1,U,min,+,111111,111111,=,2,L,-1,U,max,二进制的编码精度为：,设每个个体的编码为：,对应的解码公式：,适配值函数,适配值函数用于对个体进行评价，是优化过程发展的依据。,在简单问题的优化时，通常可以将目标函数直接变换成适配值函数，譬如将个体,X,的适配值,f(x,),定义为,M-,c(x,),或,e,ac(x,),其中,M,为一足够大正数，,c(x,),为个体的目标值，,a0,。在复杂问题的优化时，往往需要构造合适的评价函数，适应,GA,进行优化。,算法参数选择,种群的数目：影响算法优化性能和效率。种群太小导致采样点数目不足，算法性能低；而种群数目太大又会增加计算量，导致收敛时间过长。所以在设计算法时应该针对具体问题选择适宜的种群数目；,交叉概率：用于控制交叉操作的频率。概率太大，种群中串的更新很快，会使高适配值的个体很快被破坏掉；概率太小，交叉操作很少进行，会使搜索停止不前；,变异概率：增加种群多样性。基于二进制编码的,GA,中，一个非常小的变异率就会改变整个种群的基因。变异概率必须取一个适当的值，太小不会产生新个体，太大又会使,GA,完全的随机搜索；,总结：遗传算法参数的选择是非常重要的，同时也非常复杂，参数选取需要按照问题的实际大小来进行选择。,选择算子选取,选择的定义：从群体中选择优秀的个体，淘汰劣质个体的操作。,选择算子的作用：将优化的解直接遗传到下一代，或通过配对交叉的方式遗传到下一代。,常用选择算子：适应度比例法，也叫赌轮法或蒙特卡罗法。,选择执行过程：,1),计算出群体中所有个体适应度的总值；,2),计算每个个体相对适应度，即个体遗传到下一代的概率；,3),使用模拟赌轮操作,(srand(0,1),来确定各个个体被选中的次数。,假设群体的大小为,n,，其中个体,i,的适应度值为,fi,，个体,i,被选择的概率,pi,表示为,P,i,反映了个体,i,的适应度在整个群体的个体适应度总和中所占的比例。适应度越高，被选中的概率越高。,算法终止条件,在实际中算法是不允许无止境的发展下去的，而且对通常问题的最优解具有不确定性，因此需要一个条件来终止算法的进程。目前最常用的终止条件是事先给定一个最大进化步数，或者判断最佳优化值是否连续且经过若干步后都没有变化等。,隐含并行性,设,为一小正数，,L(l-1)+1,N=2,l,2,，,则遗传算法一次处理的存活概率不小于,1-,且定义长度不大于,L,的模式数位,O,（,N,3,）,.,遗传算法表面上仅对每代的,N,个个体作处理，但实际上并行处理了大约,O,（,N,3,）个模式，并且无额外的存储，这正是遗传算法具有高校搜索能力的原因，这就是遗传算法的隐含并行。,并行遗传算法,传统的遗传算法出现的问题：,局部搜索性能较差，对某些分布变化缓慢，面对大型计算问题速度难以达到要求,并行遗传算法提出：,在遗传算法并行运算的基础上，通过多种群并行进化和引入迁移算子进行进行种群之间的信息交流，实现多种群的协同进化。通过人工选择系数对每个种群最优化个体保存，通过对协调种群间的信息交换策略得到最好的进化效果。,遗传算法的并行化实现就是将进化过程划分到不同的计算节点上，进行分布式进化，并通过一定的种群间信息交换策略实现优良基因的转换。,并行遗传算法的分类,标准型并行方法：未改变串行遗传算法的基本特点，在一个总体的环境中实现进化运算，它需要使用一个统一的群体。实现时需要一个全局存储器和一个统一的控制机构来协调群体的遗传进化过程及群体之间的通信过程。,缺点：运行速率低。,分解型并行方法：将整个群体分解为几个子群体，各子群体彼此分配在不同的节点上，各自运行自身节点上的遗传算法，在适当的时候各节点之间交换信息。这种实现方法比较符合个体自然进化的过程，保存了各节点上群体进化的局部特性，有效回避了普通遗传算法早熟现象。,目前比较常用的类型是分解型并行方法，按照不同的组织结构，它又可以分为下面三种不同的类型：,主从式并行计算,粗粒度并行计算,细粒度并行计算,主从式并行计算,在这种并行方式中，一个主过程调节若干个仆过程。其中主过程控制选择、交叉和变异，仆过程仅执行适配值的计算。,缺点：,1,、各仆过程计算适应度值的时间存在明显差异时，将会照成整个系统长时间的等待；,2,、整个系统可靠性较差，对主过程状况的依赖性较大。,伪代码：,Begin,(1),产生一个初始群体,(2)while running do,(2.1)for=1 to s do,计算个体,i,的适应度值,(,并行部分,),（,2.2,）选择、交叉、变异操作，产生子代,（,2.3,）子代取代父代，形成新一代个体,End while,End,粗粒度并行算法,在自然界中，物种的群体系由一些子群体构成。在处理器比较少的情况下，可以将群体分为若干个子群体，每个子群体包含一些个体，每个群体分配一个处理器，让它们互相独立的并行执行进化，每经过一定的间隔（即若干个进化带），就把最佳个体迁移到相邻的子群体中。,算法代码：,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)do,a,、选择父代,b,、交叉操作,c,、子代变异,d,、子代取代父代形成新一代子群体,e,、评估子代的适应度,end for,(2.3.2),选择要迁移出去的个体,(2.3.3)do step a and b in parallel /*,这里发送和接收进程是并发执行的,a,、发送要迁出的个体,b,、接手迁入的个体,end while,end for,end,细粒度并行算法,如果并行系统中有足够多的处理器，那么系统可以为每个个体分配一个处理器，让它们相互独立的并行执行进程，这样就能获得并行遗传算法的最大可能的并发性。,代码：,Begin,(1),产生一个初始群体并将它分配到,P=N,个处理器上；,(2)For=1 to N do,while 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 while,End for,End,谢谢大家！,