遗传算法及应用

遗传算法及应用第一页，共四十六页，编辑于2023年，星期三5.1遗传算法的原理与特点

Darwin的进化论：

优胜劣汰，适者生存。

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

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

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

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

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

4第四页，共四十六页，编辑于2023年，星期三5.1.2遗传算法的特点1)遗传算法是对参数的编码进行操作，而不是对参数本身；

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

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

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

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

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

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

5第五页，共四十六页，编辑于2023年，星期三5.2遗传算法的基本操作与模式理论设需要求解的优化问题为寻找当自变量x在0～31之间取整数值时函数f(x)=x2的最大值。

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

初始种群的产生

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

01101、11000、01000、10011

6第六页，共四十六页，编辑于2023年，星期三5.2.1.1复制操作

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

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

5.2.1遗传算法的基本操作7第七页，共四十六页，编辑于2023年，星期三种群的初始串及对应的适配度

序号串X值适配度占整体的百分数%期望的复制数实际得到的复制数1011011316914.40.582110002457649.21.973010008645.50.224100111936130.91.23总计1170100.04.00平均29325.01.00最大值57649.01.975.2.1.1复制操作

5.2.1遗传算法的基本操作8第八页，共四十六页，编辑于2023年，星期三经复制后的新的种群为01101110001100010011串1被复制了一次串2被复制了两次串3被淘汰串4也被复制了一次5.2.1.1复制操作

5.2.1遗传算法的基本操作9第九页，共四十六页，编辑于2023年，星期三种群的初始串及对应的适配度

序号串X值适配度占整体的百分数%期望的复制数实际得到的复制数1011011316914.40.5812110002457649.21.9723010008645.50.2204100111936130.91.231总计1170100.04.004平均29325.01.001最大值57649.01.97210第十页，共四十六页，编辑于2023年，星期三交叉(Crossover)操作可分为两步：第一步—将新复制产生的匹配池中的成员随机两两匹配。第二步—进行交叉繁殖。设串的长度为l，则串的l个数字位之间的空隙标记为1，2，…，l-１。随机地从[1，l-1]中选取一整数位置k，则将两个父母串中从位置k到串末尾的子串互相交换，而形成两个新串。5.2.1.2交叉操作

5.2.1遗传算法的基本操作11第十一页，共四十六页，编辑于2023年，星期三本例中初始种群的两个个体

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

5.2.1遗传算法的基本操作12第十二页，共四十六页，编辑于2023年，星期三新串号匹配池匹配对象交叉点新种群x值适配度f(x)101101240110012144211000141100125625311000421101127729410011321000016256总计1754平均439最大值729交叉操作

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

5.2.1.3变异操作

5.2.1遗传算法的基本操作14第十四页，共四十六页，编辑于2023年，星期三在经过一次复制、交叉和变异操作后，最优的和平均的目标函数值均有所提高。种群的平均适配度从293增至439，最大的适配度从575增至729。可见每经过这祥的一次遗传算法步骤，问题的解便朝着最优解方向前进了一步。5.2.1遗传算法的基本操作15第十五页，共四十六页，编辑于2023年，星期三5.2.2遗传算法的模式理论

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

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

16第十六页，共四十六页，编辑于2023年，星期三称一个模式与一个特定的串相匹配是指：该模式中的1与串中的1相匹配模式中的0与串中的0相匹配模式中的*可以匹配串中的0或1例如模式00*00匹配两个串：00100，00000模式*11*0匹配四个串：01100，01110，11100，111105.2.2遗传算法的模式理论

17第十七页，共四十六页，编辑于2023年，星期三对于前面例子中的5位字串，由于模式的每一位可取0、1或*，因此总共有种模式。对一般的问题，若串的基为k，长度为l，则总共有种模式。可见模式的数量要大于串的数量。

5.2.2遗传算法的模式理论

18第十八页，共四十六页，编辑于2023年，星期三一般地，一个串中包含种模式。例如串11111是个模式的成员，因为它可以与每个串位是1或*的任一模式相匹配。因此，对于大小为n的种群则包含有到n×种模式。设一个7位二进制串可以用如下的符号来表示这里每个代表一个二值特性(也称为基因)。

5.2.2遗传算法的模式理论

19第十九页，共四十六页，编辑于2023年，星期三引入两个模式的属性定义：模式次数和定义长度。一个模式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。

5.2.2遗传算法的模式理论

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

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

的串的平均适配度。是整个种群的平均适配度。21第二十一页，共四十六页，编辑于2023年，星期三为了进一步分析高于平均适配度的模式数量增长，设

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

(2)

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

5.2.2.1复制对模式的影响22第二十二页，共四十六页，编辑于2023年，星期三交叉过程是串之间的有组织的然而又是随机的信息交换，它在创建新结构的同时，最低限度地破坏复制过程所选择的高适配度模式。考察一个l＝7的串以及此串所包含的两个代表模式。A＝0111000

5.2.2.2交叉对模式的影响23第二十三页，共四十六页，编辑于2023年，星期三推广到一般情况，可以计算出任何模式的交叉存活概率的下限为中大于号表示当交叉点落入定义长度内时也存在模式不被破坏的可能性。

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

(3)5.2.2.2交叉对模式的影响24第二十四页，共四十六页，编辑于2023年，星期三若综合考虑复制和交叉的影响，特定模式在下一代中的数量可用下式来估计

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

5.2.2.2交叉对模式的影响25第二十五页，共四十六页，编辑于2023年，星期三5.2.2.3变异对模式的影响26第二十六页，共四十六页，编辑于2023年，星期三综合考虑上述复制、交叉及变异操作，可得特定模式H的数量改变为

(6)5.2.2遗传算法的模式理论

27第二十七页，共四十六页，编辑于2023年，星期三5.3遗传算法的实现与改进根据具体问题特点可采用不同的编码方式，其中二进制编码是最常用的编码方式。一般包括以下几个步骤：

1)根据具体问题确定待寻优的参数；

2)对每一个参数确定它的变化范围，并用一个二进制数来表示。例如若参数a的变化范围为，用一位二进制数b来表示，则二者之间满足

3)将所有表示参数的二进制数串接起来组成一个长的二进制字串。该字串的每一位只有0或1两种取值。该字串即为遗传算法可以操作的对象。5.3.1编码问题28第二十八页，共四十六页，编辑于2023年，星期三5.3遗传算法的实现与改进5.3.2初始种群的产生

产生初始种群的方法通常有两种：一种是用完全随机的方法产生。例如用随机数发生器来产生。设要操作的二进制字串总共p位，设初始种群取n个样本（n<），可在0～之间随机地产生n个整数，则该n个整数所对应的二进制表示即为要求的n个初始样本。随机产生样本的方法适于对问题的解无任何先验知识的情况。另一种产生初始种群的方法是，对于具有某些先验知识的情况，可首先将这些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本。这样选择初始种群可使遗传算法更快地到达最优解。29第二十九页，共四十六页，编辑于2023年，星期三5.3.3适配度的设计1)直接以待求解的目标函数的作为适配度函数，若目标函数f(x)为最大化问题，令适配度函数若目标函数f(x)为最小化问题，令适配度函数2)若目标函数为最小问题，则式中cmax为f(x)的最大估计值。若目标函数为最大问题，则30第三十页，共四十六页，编辑于2023年，星期三5.3.3适配度的设计3)若目标函数为最小问题，则若目标函数为最大问题，则5.3遗传算法的实现与改进31第三十一页，共四十六页，编辑于2023年，星期三5.3.4遗传算法的操作步骤

利用遗传算法解决一个具体的优化问题，一般分为三个步骤：1)准备工作

(1)确定有效且通用的编码方法，将问题的可能解编码成有限位的字符串；

(2)定义一个适应度函数，用以测量和评价各解的性能；

(3)确定遗传算法所使用的各参数的取值，如种群规模n，交叉概率，变异概率等等。5.3遗传算法的实现与改进32第三十二页，共四十六页，编辑于2023年，星期三5.3.4遗传算法的操作步骤2)遗传算法搜索最佳串

(1)t=0，随机产生初始种群A(0)；

(2)计算各串的适配度，；

(3)根据对种群进行复制操作，以概率对种群进行交叉操作，以概率对种群进行变异操作，经过三种操作产生新的种群；

(4)t=t+1，计算各串的适配度；

(5)当连续几代种群的适配度变化小于某个事先设定的值时，认为终止条件满足，若不满足返回(3)；

(6)找出最佳串，结束搜索。

5.3遗传算法的实现与改进33第三十三页，共四十六页，编辑于2023年，星期三5.3.4遗传算法的操作步骤3)根据最佳串给出实际问题的最优解。

5.3遗传算法的实现与改进34第三十四页，共四十六页，编辑于2023年，星期三5.3.5遗传算法中的参数选择

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

5.3遗传算法的实现与改进35第三十五页，共四十六页，编辑于2023年，星期三5.3.6遗传算法的改进

(1)自适应变异

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

(2)优秀个体保护法

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

(3)移民法

：用交叉产生出的个体替换上一代中适应度低的个体，继而按移民的比例，引入新的外来个体来替换新一代中适应度低的个体。

(4)分布式遗传算法将总的群体分成若干子群，各子群将有略微不同的基因模式，各自的遗传过程具有相对的独立性和封闭性，另一方面，在各子群之间又以一定的比率定期地进行优良个体的迁移，使各子群能共享优良的基因模式以防止某些子群向局部最优方向收敛。

5.3遗传算法的实现与改进36第三十六页，共四十六页，编辑于2023年，星期三5.4.2遗传算法用于控制系统建模与设计

5.4.2.1控制系统建模设定开环伺服电机系统模型微分方程式为5.4遗传算法在智能控制中的应用传递函数形式为其中，，其余3个参数为待求的优化解。

37第三十七页，共四十六页，编辑于2023年，星期三5.4.2遗传算法用于控制系统建模与设计

5.4遗传算法在智能控制中的应用5.4.2.1控制系统建模

将遗传算法应用于该模型的辨识，方案如下：解的编码方法采用二进制编码，3个参数变量每个对应一个7位二进制串，则每个参数变量范围内有128个可能值；

3个二进制串级联成一个用21位二进制数表示的染色体串；种群的大小为n=50；复制操作采用排序复制；交叉概率为=0.6，变异概率为=0.01；模型的输入激励采用单位阶跃函数。

38第三十八页，共四十六页，编辑于2023年，星期三5.4.2遗传算法用于控制系统建模与设计

5.4.2.1控制系统建模模型输出与样本输出之间的误差作为个体评价测度。

按照个体的排序序位k计算个体的适配度，计算公式经遗传算法优化辨识，获得最优模型辨识参数为

39第三十九页，共四十六页，编辑于2023年，星期三5.4.2遗传算法用于控制系统建模与设计

5.4.2.2控制系统设计一种综合反映系统稳态和暂态响应的简单误差函数为

将遗传算法应用于基于上述直流伺服电机辨识模型的控制器设计，获得最优控制器的传递函数为40第四十页，共四十六页，编辑于2023年，星期三5.4.2遗传算法用于控制系统建模与设计

5.4.2.2控制系统设计经遗传算法优化的直流伺服电机控制系统的阶跃响应

41第四十一页，共四十六页，编辑于2023年，星期三5.4.3遗传算法用于神经网络的权值优化

将神经网络中所有神经元的连接权值编码成二进制码串或实数码串表示的个体，随机生成这些码串的初始群体，即可进行常规的遗传算法优化计算。每进行一代计算后，将码串解码为权值构成新的神经网络