遗传算法ppt专题知识专家讲座

当代设计方法之遗传优化算法遗传算法ppt专题知识专家讲座第1页目录1、智能优化算法

2、基本遗传算法

3、遗传算法特点4、遗传算法数学基础5、遗传算法收敛性分析6、遗传算法应用举例

7、遗传算法小结

遗传算法ppt专题知识专家讲座第2页1、智能优化算法

智能优化算法又称为当代启发式算法，是一个含有全局优化性能、通用性强、且适合于并行处理算法。这种算法普通含有严密理论依据，而不是单纯凭借教授经验，理论上能够在一定时间内找到最优解或近似最优解。遗传算法ppt专题知识专家讲座第3页惯用智能优化算法

（1）遗传算法（GeneticAlgorithm，简称GA）（2）模拟退火算法（SimulatedAnnealing，简称SA）（3）禁忌搜索算法（TabuSearch，简称TS）

……遗传算法ppt专题知识专家讲座第4页智能优化算法特点它们共同特点：都是从任一组解出发，按照某种机制，以一定概率在整个求解空间中探索最优解。因为它们能够把搜索空间扩展到整个问题空间，因而含有全局优化性能。遗传算法ppt专题知识专家讲座第5页遗传算法起源遗传算法是由美国Michigan大学J.Holland教授于1975年在他专著《自然界和人工系统适应性》中首先提出，它是一类借鉴生物界自然选择和自然遗传机制随机化搜索算法。遗传算法ppt专题知识专家讲座第6页遗传算法搜索机制遗传算法模拟自然选择和自然遗传过程中发生繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从候选解群中选取较优个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法ppt专题知识专家讲座第7页2、基本遗传算法基本遗传算法（SimpleGeneticAlgorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出一个最基本遗传算法，其遗传进化操作过程简单，轻易了解，是其它一些遗传算法雏形和基础。遗传算法ppt专题知识专家讲座第8页基本遗传算法组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数遗传算法ppt专题知识专家讲座第9页SGA框图

产生初始群体是否满足停顿准则是输出结果并结束计算个体适应度值百分比选择运算单点交叉运算基本位变异运算否产生新一代群体执行M/2次遗传算法ppt专题知识专家讲座第10页染色体及其编码遗传算法以生物细胞中染色体(chromosome)代表问题中个体对象。而一个染色体能够看作是由若干基因组成位串,所以需要将问题中个体对象编码为某种位串形式。这么,原个体对象也就相当于生命科学中所称生物体表现型(phenotype),而其编码即“染色体”也就相当于生物体基因型(genotype)。遗传算法中染色体普通用字符串表示,而基因也就是字符串中一个个字符。比如,假设数字9是某问题中个体对象,则我们就能够用它二进制数串1001作为它染色体编码。

遗传算法ppt专题知识专家讲座第11页基因型：1000101110110101000111

表现型：0.637197编码解码个体（染色体）基因遗传算法ppt专题知识专家讲座第12页适应度与适应度函数

遗传算法对一个个体（解）好坏用适应度函数值来评价，适应度函数值越大，解质量越好。适应度(fitness)就是借鉴生物个体对环境适应程度,而对所求解问题中对象设计一个表征优劣测度。适应度函数(fitnessfunction)就是问题中全体对象与其适应度之间一个对应关系,即对象集合到适应度集合一个映射。它普通是定义在论域空间上一个实数值函数。适应度函数是遗传算法进化过程驱动力，也是进行自然选择唯一标准，它设计应结合求解问题本身要求而定。说明：“论域”是数理逻辑中概念。“在一个逻辑系统中，全部个体组成集合，称为个体域，亦称论域。”

遗传算法ppt专题知识专家讲座第13页种群(population)

SGA采取随机方法生成若干个个体集合，该集合称为初始种群。初始种群中个体数量称为种群规模。

或种群就是模拟生物种群而由若干个染色体组成群体,它普通是整个论域空间一个很小子集。遗传算法ppt专题知识专家讲座第14页遗传操作

遗传算法中有三种关于染色体运算（遗传算子）:选择-复制、交叉和变异,这三种运算被称为遗传操作或遗传算子(geneticoperator)。

遗传算法ppt专题知识专家讲座第15页选择-复制算子和选择概率

选择-复制(selectionreproduction)操作是模拟生物界优胜劣汰自然选择法则一个染色体运算,就是从种群中选择适应度较高染色体进行复制,以生成下一代种群。选择-复制通常做法是,对于一个规模为N种群S,按每个染色体xi∈S选择概率P(xi)所决定选中机会,分N次从S中随机选定N个染色体,并进行复制。这里选择概率P(xi)计算公式为Note:复制即为个体被选中并遗传到下一代；遗传算法ppt专题知识专家讲座第16页其中,f为适应度函数,f(xi)为xi适应度。能够看出,染色体xi被选中概率就是其适应度f(xi)所占种群中全体染色体适应度之和百分比。显然,按照这种选择概率定义,适应度越高染色体被随机选定概率就越大,被选中次数也就越多,从而被复制次数也就越多。相反,适应度越低染色体被选中次数也就越少,从而被复制次数也就越少。假如把复制看做染色体一次换代话,则这就意味着适应度越高染色体其后代也就越多,适应度越低染色体其后代也就越少,甚至被淘汰。这正吻合了优胜劣汰自然选择法则。遗传算法ppt专题知识专家讲座第17页SGA选择算子遗传算法使用选择运算来实现对群体中个体进行优胜劣汰操作：适应度高个体被遗传到下一代群体中概率大；适应度低个体，被遗传到下一代群体中概率小。选择操作任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采取轮盘赌选择方法。

遗传算法ppt专题知识专家讲座第18页轮盘赌选择又称百分比选择算子，它基本思想是：各个个体被选中概率与其适应度函数值大小成正比。遗传算法ppt专题知识专家讲座第19页上述按概率选择方法可用一个称为赌轮原理来实现。即做一个单位圆,然后按各个染色体选择概率将圆面划分为对应扇形区域(如图1所表示)。这么,每次选择时先转动轮盘,当轮盘静止时,上方指针所正对着扇区即为选中扇区,从而对应染色体即为所选定染色体。比如,假设种群S中有4个染色体:s1,s2,s3,s4,其选择概率依次为:0.11,0.45,0.29,0.15,则它们在轮盘上所占份额如图1中各扇形区域所表示。图1赌轮选择示例

遗传算法ppt专题知识专家讲座第20页

在算法中赌轮选择法可用下面过程来模拟:①在［0,1］区间内产生一个均匀分布伪随机数r。②若r≤q1,则染色体x1被选中。③若qk-1<r≤qk(2≤k≤N),

则染色体xk被选中。其中qi称为染色体xi(i=1,2,…,n)积累概率,其计算公式为：遗传算法ppt专题知识专家讲座第21页一个染色体xi被选中次数,能够用下面期望值e(xi)来确定：

其中f为种群S中全体染色体平均适应度值。

遗传算法ppt专题知识专家讲座第22页交叉(crossover)算子

所谓交叉运算，是指对两个相互配正确染色体依据交叉概率Pc按某种方式相互交换两个染色体一些位上基因，从而形成两个新个体。交叉运算是遗传算法区分于其它进化算法主要特征，它在遗传算法中起关键作用，是产生新个体主要方法。SGA中交叉算子采取单点交叉算子。遗传算法ppt专题知识专家讲座第23页

比如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即：

则得新串s1′=01000101,s2′=10011011。s1′和s2′能够看做是原染色体s1和s2子代染色体。

交叉(crossover)算子单点交叉运算：交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉点遗传算法ppt专题知识专家讲座第24页变异(mutation)算子变异(mutation)亦称突变,就是改变染色体某个(些)位上(基因座)基因。是依据变异概率Pm将个体编码串中一些基因值用其它基因值来替换，从而形成一个新个体。遗传算法中变异运算是产生新个体辅助方法，它决定了遗传算法局部搜索能力，同时保持种群多样性。交叉运算和变异运算相互配合，共同完成对搜索空间全局搜索和局部搜索。SGA中变异算子采取基本位变异算子。遗传算法ppt专题知识专家讲座第25页基本位变异算子基本位变异算子是指对个体编码串随机指定某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示个体，若需要进行变异操作某一基因座上原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。遗传算法ppt专题知识专家讲座第26页基本位变异算子执行过程变异前：

000001110000000010000变异后：

000001110001000010000变异点遗传算法ppt专题知识专家讲座第27页运行参数（1）M：种群规模(20-100)（2）T：遗传运算终止进化代数(100-500)（3）Pc：交叉概率(0.4-0.9)（4）Pm：变异概率(0.001-0.01)参加交叉运算染色体个数占全体染色体总数百分比，记为Pc。因为生物繁殖时染色体交叉是按一定概率发生,所以参加交叉操作染色体也有一定百分比,而交叉率也就是交叉概率。变异率(mutationrate)是指发生变异基因位数所占全体染色体基因总位数百分比，记为Pm。因为在生物繁衍进化过程中,变异也是按一定概率发生,而且发生概率普通很小,所以变异率也就是变异概率。遗传算法ppt专题知识专家讲座第28页SGA框图产生初始群体是否满足停顿准则是输出结果并结束计算个体适应度值百分比选择运算单点交叉运算基本位变异运算否产生新一代群体执行M/2次遗传算法ppt专题知识专家讲座第29页基本遗传算法流程说明：

步1

在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；步2随机产生U中N个染色体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1；步3计算S中每个染色体适应度f(si)；步4若终止条件满足，则取S中适应度最大染色体作为所求结果，算法结束。步5

按选择概率P(xi)所决定选中机会，每次从S中随机选定1个染色体并将其复制，共做N次，然后将复制所得N个染色体组成群体S1；

遗传算法ppt专题知识专家讲座第30页步6按交叉率Pc所决定参加交叉染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生新染色体代替原染色体，得群体S2；步7按变异率Pm所决定变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生新染色体代替原染色体，得群体S3；步8将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；

遗传算法ppt专题知识专家讲座第31页

需要说明是,在应用遗传算法处理实际问题时,还需给出结构模式表示方案、适应度计算方法、终止条件等。表示方案通常是把问题搜索空间每一个可能点,编码为一个看做染色体字符串,字符通常采取二进制数0、1。适应度计算方法普通依据实际问题而定。

遗传算法ppt专题知识专家讲座第32页3、遗传算法特点（1）GA搜索群体中点是并行,而不是单点；（2）GA使用概率变换规则,而不是确定变换规则;（3）适应度函数不受连续、可微等条件约束，适用范围很广。只需要影响搜索方向目标函数和相对应适应度函数;(4)GA使用编码参数集,而不是本身参数集;遗传算法ppt专题知识专家讲座第33页4、遗传算法数学基础（1）模式定理(PatternTheorem)（2）积木块假设(BuildingBlockHypothesis)遗传算法ppt专题知识专家讲座第34页模式

模式是指种群个体基因串中相同样板，它是一个用来描述基因串中一些位置上含有结构相同性0、1字符串集合方法。在二进制编码中，基于三值字符集(0,1,*)字符串所产生能描述含有一些结构相同性0,1字符串集字符串称为模式.符号*代表任意字符，即0或者1。

模式示例：*0001描述了含有”0001”特征全部字符串,即(00001,10001);遗传算法ppt专题知识专家讲座第35页两个定义

定义1：模式H中确定位置个数称为模式H阶，记作O(H)。比如O(10**1)=3。O(011*1*)=4;O(0*****)=1

note:一个模式阶数越高，其样本数就越少,因而确定性就越高定义2：模式H中第一个确定位置和最终一个确定位置之间距离称为模式H定义距，记作δ(H)。比如δ(10**1)=4;δ(0*****)=0遗传算法ppt专题知识专家讲座第36页模式阶和定义距含义

模式阶用来反应不一样模式间确定性差异，一个模式阶数越高，其样本数就越少,因而确定性就越高。在遗传操作中，即使阶数相同模式，也会有不一样性质，而模式定义距就反应了这种性质差异。遗传算法ppt专题知识专家讲座第37页模式定理

模式定理：在遗传算子选择、交叉和变异作用下，含有低阶、短定义距以及平均适应度高于种群平均适应度模式在子代中将以指数级增加。(GA必要条件)模式定理确保了较优模式（遗传算法较优解）样本数目呈指数级增加，为解释遗传算法机理提供了数学基础。遗传算法ppt专题知识专家讲座第38页模式定理

从模式定理可看出，有高平均适应度、短定义距、低阶基因模式，其样本在子代里取得最少以指数增加数目，这主要是因为选择使最好模式有更多复制，交叉算子不轻易破坏高频率出现、短定义距模式，而普通突变概率又相当小，因而它对这些主要模式几乎没有影响。遗传算法ppt专题知识专家讲座第39页积木块假设

积木块假设：阶数低、短定义距、适应度高模式（这类模式称为积木块），在遗传算子作用下相互结合，能生成阶数高、长度长、适应度高模式,可最终靠近全局最优解。

与积木块一样,一些好模式在遗传算子作用下相互拼搭、结合,产生适应度更高串,从而找到了更优可行解,这正是积木块假设所揭示内容.

遗传算法ppt专题知识专家讲座第40页S1AAS2S3CCS4BBS5S6S7AAS8BB初始种群S1AAS2BBS3AACCS4BBS5S6CCS7AABBS8第二代种群积木块：AABBCC遗传算法ppt专题知识专家讲座第41页S1AAS2BBS3AABBCCS4S5S6BBS7AACCS8第三代种群遗传算法ppt专题知识专家讲座第42页模式定理确保了较优模式(遗传算法较优解)样本数呈指数增加，从而满足了寻找最优解必要条件,即遗传算法存在着寻找到全局最优解可能性；积木块假设则指出,GA具备找到全局最优解能力,即积木块在遗传算子作用下，能生成阶数高、长度长、适应度高模式,最终生成全局最优解。小结遗传算法ppt专题知识专家讲座第43页5.遗传算法收敛性分析

遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能抵达全局最优解；其次算法必须由保优操作来预防最优解遗失。与算法收敛性相关原因主要包含种群规模、选择操作、交叉概率和变异概率。遗传算法ppt专题知识专家讲座第44页种群规模对收敛性影响

通常，种群太小则不能提供足够采样点，以致算法性能很差；种群太大，尽管能够增加优化信息，阻止早熟收敛发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度迟缓。遗传算法ppt专题知识专家讲座第45页选择操作对收敛性影响

选择操作使高适应度个体能够以更大概率生存，从而提升了遗传算法全局收敛性。假如在算法中采取最优保留策略，即将父代群体中最正确个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。1.轮盘赌2.随机竞争选择(按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高选中，如此重复，直到选满为止)3.最优保留策略(当前种群中适应度最高个体不参加交叉和变异操作，而是用它来替换掉本代种群中经交叉、变异等操作后所产生适应度最低个体，确保算法终止时得到最终结果是历代出现过得最高适应度个体)

….遗传算法ppt专题知识专家讲座第46页交叉概率对收敛性影响

交叉操作用于个体对，产生新个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值个体很快被破坏掉；概率太小时，交叉操作极少进行，从而会使搜索停滞不前，造成算法不收敛。遗传算法ppt专题知识专家讲座第47页变异概率对收敛性影响

变异操作是对种群模式扰动，有利于增加种群多样性。不过，变异概率太小则极难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。遗传算法ppt专题知识专家讲座第48页遗传算法ppt专题知识专家讲座第49页遗传算法本质

遗传算法本质上是对染色体模式所进行一系列运算，即经过选择算子将当前种群中优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。经过这些遗传操作，模式逐步向很好方向进化，最终得到问题最优解。遗传算法ppt专题知识专家讲座第50页6.遗传算法应用举例

例1.利用遗传算法求解区间［0,31］上二次函数y=x2最大值；【分析】能够看出,只要能在区间［0,31］中找到函数值最大点a,则函数y=x2最大值也就能够求得。于是,原问题转化为在区间［0,31］中寻找能使y取最大值点a问题。显然,对于这个问题,任一点x∈［0,31］都是可能解,而函数值f(x)=x2也就是衡量x能否为最正确解一个测度。那么,用遗传算法眼光来看,区间［0,31］就是一个(解)空间,x就是其中个体对象,函数值f(x)恰好就能够作为x适应度。这么,只要能给出个体x适当染色体编码,该问题就能够用遗传算法来处理。遗传算法ppt专题知识专家讲座第51页解：

(1)定义适应度函数,编码染色体。由上面分析,函数f(x)=x2就可作为空间U上适应度函数。显然y=x2是一个单调增函数,其取最大值点x=31是个整数。另首先,5位二进制数也刚好能表示区间［0,31］中全部整数。所以,我们就仅取［0,31］中整数来作为参加进化个体,而且用5位二进制数作为个体x基因型编码,即染色体。

(2)设定种群规模,产生初始种群。设定种群规模为4,取染色体s1=01101(13),s2=11000(24),s3=01000(8),s4=10011(19)组成初始种群S1。

遗传算法ppt专题知识专家讲座第52页

(3)计算各代种群中各染色体适应度,并进行遗传操作,直到适应度最高染色体(该问题中显然为“11111”=31)出现为止。计算S1中各染色体适应度、选择概率、积累概率等并列于表1中。

遗传算法ppt专题知识专家讲座第53页表

1第一代种群S1中各染色体情况

r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503设从区间［0,1］中产生4个随机数以下:遗传算法ppt专题知识专家讲座第54页选择-复制

设从区间［0,1］中产生4个随机数以下:r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503按赌轮选择法，染色体s1,s2,s3,s4被选中次数依次为：1,2,0,1。于是，经复制得到新群体以下：

s1’=11000（24）,s2’=01101（13）,s3’=11000（24）,s4’=10011（19）

能够看出，在第一轮选择中适应度最高染色体s2被选中两次，因而被复制两次；而适应度最低染色体s3一次也没有选中而遭淘汰。

遗传算法ppt专题知识专家讲座第55页交叉设交叉率pc=100%，即S1中全体染色体都参加交叉运算。设s1’与s2’配对，s3’与s4’配对。分别交换染色体后两位基因，得新染色体：s1’’=11001（25）,s2’’=01100（12）,

s3’’=11011（27）,s4’’=10000（16）变异设变异率pm=0.001。这么，群体S1中共有5×4×0.001=0.02位基因能够变异。0.02位显然不足1位，所以本轮遗传操作不做变异。

现在，我们得到了第二代种群S2：s1=11001（25）,s2=01100（12）,

s3=11011（27）,s4=10000（16）Note:s1’=11000（24）,s2’=01101（13）,s3’=11000（24）,s4’=10011（19）

遗传算法ppt专题知识专家讲座第56页

假设这一轮选择-复制操作中，种群S2中4个染色体都被选中（因为选择概率毕竟只是一个几率，所以4个染色体恰好都被选中情况是存在），我们得到群体：

s1’=11001（25）,s2’=01100（12）,s3’=11011（27）,s4’=10000（16）

然后，做交叉运算，让s1’与s2’，s3’与s4’

分别交换后三位基因，得

s1’’=11100（28）,s2’’=01001（9）,s3’’=11000（24）,s4’’=10011（19）

这一轮依然不会发生变异。于是，得第三代种群S3：

s1=11100（28）,s2=01001（9）,s3=11000（24）,s4=10011（19）

表

2第二代种群S2中各染色体情况

遗传算法ppt专题知识专家讲座第57页表3第三代种群S4中各染色体情况

遗传算法ppt专题知识专家讲座