遗传算法及应用补

遗传算法及应用补第1页，课件共31页，创作于2023年2月1一、遗传算法的基本原理

Darwin的进化论：

优胜劣汰，适者生存。

Mendel的基因遗传学：遗传是作为一种指令码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有特殊的位置并控制某个特殊的性质，每个基因产生的个体对环境有一定的适应性，基因杂交和基因突变可能产生对环境适应性更强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。

第2页，课件共31页，创作于2023年2月2一、遗传算法的基本原理遗传算法将问题的求解表示成“染色体”（用编码表示字符串）。该算法从一群“染色体”串出发，将它们置于问题的“环境”中，根据适者生存的原则，从中选择出适应环境的“染色体”进行复制，通过交叉、变异两种基因操作产生出新的一代更适应环境的“染色体”种群。随着算法的运行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。

第3页，课件共31页，创作于2023年2月3一、遗传算法的基本原理常规的寻优方法主要有三种类型：解析法：间接法是通过让目标函数的梯度为零，进而求解一组非线性方程来寻求局部极值。直接法是使梯度信息按最陡的方向逐次运动来寻求局部极值，它即为通常所称的爬山法。

枚举法：可寻找到全局极值，不需要目标函数连续光滑。

随机法：搜索空间中随机地漫游并随时记录下所取得的最好结果。

第4页，课件共31页，创作于2023年2月4二、遗传算法的基本操作设需要求解的优化问题为寻找当自变量x在0～31之间取整数值时函数f(x)=x2的最大值。

第一步：准备工作“染色体”串的编码采用二进制数来对其进行编码，可用5位数来表示。例如01010对应x=10，11111对应x=31。

初始种群的产生

设种群大小为4，即含有4个个体，则需按位随机生成4个5位二进制串：

01101、11000、01000、10011

第5页，课件共31页，创作于2023年2月5(一)复制操作

复制(Copy)亦称再生(Reproduction)或选择(Selection)，复制过程是个体串按照它们的适配度进行复制。本例中目标函数值即可用作适配度。

按照适配度进行串复制的含义是适配度越大的串，在下一代中将有更多的机会提供一个或多个子孙。

第6页，课件共31页，创作于2023年2月6种群的初始串及对应的适配度

序号串X值适配度占整体的百分数%期望的复制数实际得到的复制数1011011316914.40.582110002457649.21.973010008645.50.224100111936130.91.23总计1170100.04.00平均29325.01.00最大值57649.01.97第7页，课件共31页，创作于2023年2月7经复制后的新的种群为01101110001100010011串1被复制了一次串2被复制了两次串3被淘汰串4也被复制了一次(一)复制操作

第8页，课件共31页，创作于2023年2月8种群的初始串及对应的适配度

序号串X值适配度占整体的百分数%期望的复制数实际得到的复制数1011011316914.40.5812110002457649.21.9723010008645.50.2204100111936130.91.231总计1170100.04.004平均29325.01.001最大值57649.01.972第9页，课件共31页，创作于2023年2月9(二)交叉操作

交叉(Crossover)操作可分为两步：第一步—将新复制产生的匹配池中的成员随机两两匹配。第二步—进行交叉繁殖。设串的长度为l，则串的l个数字位之间的空隙标记为1，2，…，l-１。随机地从[1，l-1]中选取一整数位置k，则将两个父母串中从位置k到串末尾的子串互相交换，而形成两个新串。第10页，课件共31页，创作于2023年2月10本例中初始种群的两个个体

假定从１到４间选取随机数，得到k＝４，那么经过交叉操作之后将得到如下两个新串(二)交叉操作

第11页，课件共31页，创作于2023年2月11新串号匹配池匹配对象交叉点新种群x值适配度f(x)101101240110012144211000141100125625311000421101127729410011321000016256总计1754平均439最大值729交叉操作

第12页，课件共31页，创作于2023年2月12(三)变异

变异(Mutation)是以很小的概率随机地改变一个串位的值。变异的概率通常是很小的，一般只有千分之几。变异操作相对于复制和交叉操作而言，是处于相对次要的地位，其目的是为了防止丢失一些有用的遗传因子，变异操作可以起到恢复串位多样性的作用。

第13页，课件共31页，创作于2023年2月13二、遗传算法的基本操作在经过一次复制、交叉和变异操作后，最优的和平均的目标函数值均有所提高。种群的平均适配度从293增至439，最大的适配度从575增至729。可见每经过这祥的一次遗传算法步骤，问题的解便朝着最优解方向前进了一步。第14页，课件共31页，创作于2023年2月14三、遗传算法的特点1)遗传算法是对参数的编码进行操作，而不是对参数本身；

2)遗传算法是从许多初始点开始并行操作，因而可以有效地防止搜索过程收敛于局部最优解，而且有较大的可能求得全部最优解；

3)遗传算法通过目标函数来计算适配度，而不需要其它的推导和附属信息，从而对问题的依赖性较小；

4)遗传算法使用概率的转变规则，而不是确定性的规则；

5)遗传算法在解空间内不是盲目地穷举或完全随机测试，而是一种启发式搜索，其搜索效率往往优于其它方法；

6)遗传算法对于待寻优的函数基本无限制，因而应用范围很广；

7)遗传算法更适合大规模复杂问题的优化。

第15页，课件共31页，创作于2023年2月15四、遗传算法的模式理论

某些子串模式(schemata)在遗传算法的运行中起着关键的作用。在上面的例子中，样本串第1位的“1”使得适配度比较大，首位为“1”的子串可以表示成这样的模式：1****其中*是通配符，它既可代表“1”，也可代表“0”。用｛0,

1,*}可以构造出任意一种模式。

第16页，课件共31页，创作于2023年2月16四、遗传算法的模式理论称一个模式与一个特定的串相匹配是指：该模式中的1与串中的1相匹配模式中的0与串中的0相匹配模式中的*可以匹配串中的0或1例如模式00*00匹配两个串：00100，00000模式*11*0匹配四个串：01100，01110，11100，11110第17页，课件共31页，创作于2023年2月17四、遗传算法的模式理论对于前面例子中的5位字串，由于模式的每一位可取0、1或*，因此总共有种模式。对一般的问题，若串的基为k，长度为l，则总共有种模式。可见模式的数量要大于串的数量。

第18页，课件共31页，创作于2023年2月18四、遗传算法的模式理论一般地，一个串中包含种模式。例如串11111是个模式的成员，因为它可以与每个串位是1或*的任一模式相匹配。因此，对于大小为n的种群则包含有到n×种模式。设一个7位二进制串可以用如下的符号来表示这里每个代表一个二值特性(也称为基因)。

第19页，课件共31页，创作于2023年2月19四、遗传算法的模式理论引入两个模式的属性定义：模式次数和定义长度。一个模式H的次数由O(H)表示，它等于模式中固定串位的个数。例如模式H＝011*1**，其次数为4，记为O(H)=4。模式H的长度定义为模式中第一个确定位置和最后一个确定位置之间的距离，用符号(H)表示。例如模式H＝011*1**，其中第一个确定位置是1，最后一个位置是5，所以(H)=5-1=4。若模式H＝******0，则(H)=0。

第20页，课件共31页，创作于2023年2月20(一)复制对模式的影响在某一世代t，种群A(t)包含有m个特定模式，记为m=m(H,t)在复制过程中，A(t)中的任何一个串以概率被选中进行复制。因此可以期望在复制完成后，在t+1世代，特定模式H的数量将变为

或写成（１）其中f(H)表示在世代t时对应于模式H

的串的平均适配度。是整个种群的平均适配度。第21页，课件共31页，创作于2023年2月21(一)复制对模式的影响为了进一步分析高于平均适配度的模式数量增长，设

c>0则上面的方程可改写为如下的差分方程假定c为常数，可得

(2)

可见，对于高于平均适配度的模式数量将呈指数形式增长。

第22页，课件共31页，创作于2023年2月22(二)交叉对模式的影响

交叉过程是串之间的有组织的然而又是随机的信息交换，它在创建新结构的同时，最低限度地破坏复制过程所选择的高适配度模式。考察一个l＝7的串以及此串所包含的两个代表模式。A＝0111000

第23页，课件共31页，创作于2023年2月23(二)交叉对模式的影响推广到一般情况，可以计算出任何模式的交叉存活概率的下限为中大于号表示当交叉点落入定义长度内时也存在模式不被破坏的可能性。

一般情况若设交叉的概率力，则上式变为

(3)第24页，课件共31页，创作于2023年2月24若综合考虑复制和交叉的影响，特定模式在下一代中的数量可用下式来估计

(4)可见，对于那些高于平均适配度且具有短的定义长度的模式将更多地出现在下一代中。

(二)交叉对模式的影响第25页，课件共31页，创作于2023年2月25(三)变异对模式的影响

第26页，课件共31页，创作于2023年2月26四、遗传算法的模式理论综合考虑上述复制、交叉及变异操作，可得特定模式H的数量改变为

(6)第27页，课件共31页，创作于2023年2月27五、遗传算法中的参数选择

初始种群的大小n:选择较大数目的初始种群可以同时处理更多的解，因此容易找到全局的最优解，其缺点是增加了每次迭代所需要的时间。交叉概率pc：交叉概率的选择决定了交叉操作的频率。频率越高，可以越快地收敛到最有希望的最优解区域；但是太高的频率也可能导致收敛于一个解。变异概率pm：变异概率通常只取较小的数值，一般为0.001～0.1。若选取高的变异率，一方面可以增加样本模式的多样性，另一方面可能引起不稳定，但是若选取太小的变异概率，则可能难于找到全局的最优解。

第28页，课件共31页，创作于2023年2月28六、遗传算法的改进

(1)自适应变异

:在交叉之前，以海明(Hamming)距离测定双亲基因码的差异，根据测定值决定后代的变异概率。若双亲的差异较小，则选取较大的变异概率。

(2)优秀个体保护法

：对于每代中一定数量的最优个体，使之直接进入下一代。这样可以防止优秀个体由于选择、交叉或变异中的偶然因素而被破坏掉。

(3)移民法

：用交叉产生出的个体替换上一代中适应度低的个体，