第6章+遗传算法的数学理论1.ppt

浙大生物系统工程与食品科学学院,1,第6章遗传算法的数学理论,模式定理积木块假设与遗传算法欺骗问题隐含并行性遗传算法的收敛性分析适应度函数的自相关分析,浙大生物系统工程与食品科学学院,2,遗传算法是通过对群体中多个个体的迭代搜索来逐步找出问题的最优解。这个搜索过程是通过个体之间的优胜劣汰、交叉重组和突然变异等遗传操作来实现的，在这个搜索过程中，为什么会将好性状(适应度大的)的个体留下，而将差的淘汰?这一章主要介绍遗传算法的机理，即理论基础。,浙大生物系统工程与食品科学学院,3,6.1模式定理6.1.1模式,例子(以二进制编码为例)：经过遗传一代性状得到改善，注意到以1打头的个体增加了。,浙大生物系统工程与食品科学学院,4,其实，遗传算法处理了一些具有相似编码结构模板的个体。如果把个体作为某些相似模板的具体表示的话，对个体的搜索过程实际上就是对这些相似模板的搜索过程。定义6.1模式（schema）表示一些相似的模块。它描述了在某些位置上具有相似结构特征的个体编码串的一个子集。对于二进制编码方式，个体是由2值字符集v=0,1中的元素所组成的一个编码串，而模式却是由3值字符集v0,1,*中的元素所组成的一个编码串其中“*”表示通配符，它既可被当作“1”，也可被当作“0”。,浙大生物系统工程与食品科学学院,5,在引入模式概念之后，遗传算法的本质是对模式所进行的一系列运算即通过选择算子将当前群体中的优良模式遗传到下一代群体中，通过交叉算子进行模式的重组，通过变异算子进行模式的突变。通过这些遗传运算，一些较差的模式逐步被淘汰，而一些较好的模式逐步被遗传和进化最终就可得到问题的最优解。为什么会将好的模式遗传下来？,浙大生物系统工程与食品科学学院,6,定义6.2在模式H中具有确定基因值的位置数目称为该模式的模式阶(schemaorder)，记为o(H)。对于二进制编码字符串而言，模式阶就是模式中所含有的1相0的数目。当字符串的长度固定时模式阶数越高，能与该模式匹配的字符串(称为样本)数就越少因而该模式的确定性也就越高。例如，o(11*0)的阶为3，能与该模式匹配的个体有8个。定义6.3模式H中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离称为该模式的模式定义长度，记为(H)。例如(11*0)=4。,浙大生物系统工程与食品科学学院,7,6.1.2模式定理,假设在进化过程中的第t代时，当前群体P(t)中能与模式H匹配的个体数(样本数)记为m(H,t)，下一代群体P(t+1)中能与模式H匹配的个体数记为m(H,t+1)。选择算子的作用基本遗传算法中的选择运算使用的是比例选择算子。设是f(H,t)第t代群体中模式H所隐含个体的平均适应度；F(t)是第t代群体的平均适应度。则下式成立。,浙大生物系统工程与食品科学学院,8,上式可改写成令：则m(H,t+1)=m(H,t)(1+C)由此可见，m(H,t)为一等比级数，其通项公式为：m(H,t)m(H,0)(1+C)t当C0，则m(H,t)呈指数级增长；若C0，则m(H,t)呈指数级减少。由此可得到下述结论：在选择算子作用下，对于平均适应度高于群体平均适应度的模式，其样本数将呈指数级增长：而对于平均适应度低于群体平均适应度的模式，其样本数将呈指数级减少。,浙大生物系统工程与食品科学学院,9,交叉算子的作用（以单点交又其子为例）隐含在该模式中的样本与其他个体进行交叉操作。根据交叉点的位置不同，有可能破坏该模式，也有可能不破坏该模式而使其继续生存到下一代群体中。显然，当随机设置的交叉点在模式的定义长度之内时，将有可能破坏该模式；而当随机设置的交叉点在模式约定义长度之外时，肯定不会破坏该模式。再考虑到交叉操作本身是以交叉概率Pc发生的，所以模式H的生存概率为：,浙大生物系统工程与食品科学学院,10,变异算子的作用(以基本位变异算子为例）此时，若某一模式被破坏，则必然是模式描述形式中通配符“*”之外的某一基因位发生了变化，其发生概率是：由此可知，在变异算子作用下，模式H的生存概率大约是：可见o(H)越小，模式H越易于生存；o(H)越大，模式H越易于被破坏。,浙大生物系统工程与食品科学学院,11,综合上述，并忽略一些极小项，则在比例选择算子、单点交叉算子、基本位变异算子的连续作用下，群体中模式H的子代样本数为：模式定理遗传算法中，在选择、交叉和变异算子的作用下，具有低阶、短的定义长度，并且平均适应度高于群体平均适应度的模式将按指数级增长。,浙大生物系统工程与食品科学学院,12,6.2积木块假设与遗传算法欺骗问题,6.2.1积木块假设模式定理说明了具有某种结构特征的模式在遗传进化过程中其样本数将按指数级增长，这种模式就是具有低阶、短的定义长度，且平均适应度高于群体平均适应度的模式。这种类型的模式被称为基因块或积木块。积木块假设个体的基因块通过选择、交叉、变异等遗传算子的作用，能够相互拼接在一起，形成适应度更高的个体编码串。,浙大生物系统工程与食品科学学院,13,6.2.2遗传算法欺骗问题应用实践表明存在着一类用遗传其法难以求解的问题，称为“GA难”问题，这类问题往往不满足积木块假设；即由基因块之间的拼接，往往会欺骗遗传算法，使其进化过程偏离最优解。各种研究结果表明，属于“GA难”的问题一般包含有孤立的最优点，即在这个最优点周围是一些较差的点，从而使得遗传算法较难通过基因之间的相互拼接而达到这个最优点的模式。,浙大生物系统工程与食品科学学院,14,6.3隐含并行性,在遗传算法的运行过程中，每代都处理了M个个体，但由于一个个体编码串中隐含有多种不同的模式，所以算法实质上却是处理了更多的模式。以二进制编码符号串为例，长度为l的编码串中隐含有2l种模式，这样，规模为M的群体中就可能隐含有2lM2l种不同的模式。随着进化过程的进行，这些模式中一些定义长度较长的模式被破坏掉，而另一些定义长度较短的模式却能够生存下来。也就是说遗传算法不能有效处理2lM2l种模式个数，到底能够有效处理多少模式数目？结论：遗传算法所处理的有效模式总数约与群体规模M的立方成正比。,浙大生物系统工程与食品科学学院,15,模式定理虽然定量地估算出了具有较优结构特点的模式在进化过程中的增长规律，但并未导出遗传算法能够收敛于问题最优解的概率。定理6.1基本遗传算法收敛于最优解的概率小于l。定理6.2使用保留最佳个体策略的遗传算法能收敛于最优解的概率为1。,6.4遗传算法的收敛性分析,浙大生物系统工程与食品科学学院,16,6.5适应度函数的自相关分析,经过改进的遗传算法虽然能够以概率1收敛于问题的最优解，但若这个收敛过程进行得比较缓慢的话、也会使其毫无应用价值。所以从应用的角度来说，需要定量分析求解效率和解的质量，往往还需要在求解效率和解的质量之间达到一种平衡。6.5.1适应度函数的景象前面对遗传算法的理论分析是基于模式的概念来进行的，未涉及到适应度函数。但是，遗传算法的运行过程中毕竟主要是依据个体的适应度来进行优胜劣汰操作的，所以有必要对适应度函数的特性进行研究。,浙大生物系统工程与食品科学学院,17,解空间不仅只是表示可行解的一系列点的集合，与解空间中的邻接结构相对应，各点都有不同的适应度，这样，在解空间中也可定义一种适应度分布函数，从而构成了一种适应度函数的景象。研究适应度函数的景象，是因为适应度函数的景象与最优化的难易程度密切相关。有些最优化问题，在所考虑的邻接结构下其适应度函数的景像凸凹不平、有很多局部最优解，如图6-4所示，这类函数优化起来就比较困难。而另一些最优化问题，其适应度函数的景象起伏一致，如图6-5所示，这类函数优化起来就比较方便。,浙大生物系统工程与食品科学学院,18,6.5.2适应度函数的自相关函数,从解空间中的某一点x出发，作向其邻接点的随机漫游xi，并确定各漫游点的适应度F(xi)。若以适应度F为随机变量，则该随机漫游过程个所得到的适应度函数的自相关函数可定义为：,浙大生物系统工程与食品科学学院,19,随机漫游的观测结果表明，对于很多组合优化的问题，其适应度函数的自关函数是以某一相关长度lc为参数而指数衰减的，即：(s)exp(-s/lc)其中的相关长度lc是该适应度函数的一个重要特征参数。对于图6-4所示的具有凸凹型景象的适应度函数、其相关长度lc就意味着当前搜索点的适应度函数值与相关长度以前的点的适应度函数值无关，此时它相对于相关长度以前的点来说，是呈现出一种随机摆动的趋势。对这类函数进行优化计算时，最好应把可行解区域按相关长度lc分割为一些小的区域，各个区域分别直进行求解，并且相关长度越短，需分割的份数越多。而对于图6-5所示的具有山峰型景象的适应度函数，可认为其相关长度很大，这样邻近点之间的适应度有一定的关系，若当前搜索点的适应度较