第七章遗传算法简介课件.ppt

1、第七章 遗传算法与控制简介模拟进化计算模拟进化计算（Simulated Evolutionary Computation)是近十几年来信息科学、人工智能与计算机科学的一是近十几年来信息科学、人工智能与计算机科学的一大研究领域，由此所派生的求解优化问题的仿生类算大研究领域，由此所派生的求解优化问题的仿生类算法（遗传算法、演化策略、进化程序），由于其鲜明法（遗传算法、演化策略、进化程序），由于其鲜明的生物背景、新颖的设计原理、独特的分析方法和成的生物背景、新颖的设计原理、独特的分析方法和成功的应用实践，正日益形成全局搜索与多目标优化理功的应用实践，正日益形成全局搜索与多目标优化理论的一个崭新分支。

2、论的一个崭新分支。遗传算法遗传算法（Genetic Algorithm,简称简称GA）是通过模拟生）是通过模拟生物进化过程来完成优化搜索的。物进化过程来完成优化搜索的。科学研究、工程实际与国民经济发展的众多问题可归结为科学研究、工程实际与国民经济发展的众多问题可归结为“最大效益、最小代价最大效益、最小代价”这类典型的优化模型。求解这类这类典型的优化模型。求解这类模型导致寻求某个目标函数（有解析表达式或无解析表达模型导致寻求某个目标函数（有解析表达式或无解析表达式）在特定区域上的最优解，传统的建立在梯度计算基础式）在特定区域上的最优解，传统的建立在梯度计算基础上的非线性规划类方法，当目标函数仅具

3、有单极点时，通上的非线性规划类方法，当目标函数仅具有单极点时，通常表现出较高的计算效率，但当目标函数具有多极值点时，常表现出较高的计算效率，但当目标函数具有多极值点时，由于其本身固有的局部优化性及不稳健等缺陷，而被广泛由于其本身固有的局部优化性及不稳健等缺陷，而被广泛认为不适于全局优化问题的求解。近二十年来，人们相继认为不适于全局优化问题的求解。近二十年来，人们相继发展了许多求解全局优化问题的方法，一般可分为确定型发展了许多求解全局优化问题的方法，一般可分为确定型与非确定型（如随机搜索）算法。与非确定型（如随机搜索）算法。Monto-Carlo方法及模拟方法及模拟退火算法都归属后者。当目标函数

4、具有为数不多的极值点退火算法都归属后者。当目标函数具有为数不多的极值点时，确定型算法常表现出较高的计算效率，但同时也暴露时，确定型算法常表现出较高的计算效率，但同时也暴露出算法复杂、对目标函数的性质要求高、可靠性差等缺点。出算法复杂、对目标函数的性质要求高、可靠性差等缺点。相比而言，随机搜索方法具有较强的鲁棒性，算法容易实相比而言，随机搜索方法具有较强的鲁棒性，算法容易实现，但常有计算效率低的缺点。现，但常有计算效率低的缺点。仿生类算法是近十几年来才发展起来的一类新型全局优化仿生类算法是近十几年来才发展起来的一类新型全局优化搜索技术，它们通过向自然界学习，借鉴生物进化机制求搜索技术，它们通过向

5、自然界学习，借鉴生物进化机制求解问题。这类算法的主要优点在于其本质上的并行性、广解问题。这类算法的主要优点在于其本质上的并行性、广泛的可适用性（如对目标函数的性态无特殊要求，特别可泛的可适用性（如对目标函数的性态无特殊要求，特别可以没有明确的表达式）和较强的鲁棒性、简明性与全局优以没有明确的表达式）和较强的鲁棒性、简明性与全局优化性能。虽然从基本思想的产生至今已有二、三十年的历化性能。虽然从基本思想的产生至今已有二、三十年的历史，但广泛用于求解优化问题还是近十几年的事。初步研史，但广泛用于求解优化问题还是近十几年的事。初步研究及广泛的应用实践已显示出它们作为可靠、有效的全局究及广泛的应用实践已

6、显示出它们作为可靠、有效的全局优化算法的巨大潜力和诱人前景。优化算法的巨大潜力和诱人前景。仿生类算法，就其目前发展而言，可分为仿生过程算法与仿生类算法，就其目前发展而言，可分为仿生过程算法与仿生结构算法两大类，前者以模拟进化算法为代表，后者仿生结构算法两大类，前者以模拟进化算法为代表，后者以神经网络为典型。以神经网络为典型。染色体染色体(chromosome)：生物生物的遗传物质的主要载体。的遗传物质的主要载体。基因基因(gene)：扩展生物性状扩展生物性状的遗传物质的功能单元和结的遗传物质的功能单元和结构单位。构单位。基因座（基因座（locus）：染色体）：染色体中基因的位置。中基因的位置。

7、等位基因（等位基因（alleles）：基因）：基因所取的值。所取的值。遗传算法的基本思想：遗传算法的基本思想：在求解问题时从多个解开始，然后通过一定的法在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。则进行逐步迭代以产生新的解。最优化问题 遗传算法 目标函数 可 行 解 一组 解 适应度函数染 色 体 种 群适用性适用性：算法所能适用的问题种类。：算法所能适用的问题种类。可靠性可靠性：算法对于所设计的问题，以适当的精度求解算法对于所设计的问题，以适当的精度求解其中大多数问题的能力其中大多数问题的能力。收敛性收敛性：算法能否收敛到全局最优。：算法能否收敛到全局最优。稳定性稳

8、定性：算法对其控制参数及问题数据的敏感度算法对其控制参数及问题数据的敏感度。生物类比生物类比：通过类比的方法引入在生物界被认为是有：通过类比的方法引入在生物界被认为是有效的方法及操作。效的方法及操作。编码方案编码方案：编码表示方式。：编码表示方式。适应度函数适应度函数：目标函数。：目标函数。选择策略选择策略：优胜劣汰。：优胜劣汰。控制参数控制参数：种群的规模、算法执行的最大代数、执行：种群的规模、算法执行的最大代数、执行不同遗传操作的概率等。不同遗传操作的概率等。遗传算子遗传算子：选择：选择(selection)；交叉；交叉(crossover)；变异；变异(mutation)。算法的终止准则

9、算法的终止准则：规定一个最大的演化代数，或算法：规定一个最大的演化代数，或算法在连续多少代以后解的适应值没有改进。在连续多少代以后解的适应值没有改进。一维染色体编码方法一维染色体编码方法：将问题空间的参数编码为一维排：将问题空间的参数编码为一维排列的染色体的方法。列的染色体的方法。二进制编码二进制编码：用若干二进制数表示一个个体，将原问题：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间的解空间映射到位串空间 B=0，1上，然后在位串空上，然后在位串空间上进行遗传操作。间上进行遗传操作。（1）二进制编码二进制编码(1)二进制编码二进制编码（续）（续）优点优点：类似于生物染色体的组成，

10、算法易于用生物遗传理论解释，遗类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。传操作如交叉、变异等易实现；算法处理的模式数最多。缺点：缺点：相邻整数的二进制编码可能具有较大的相邻整数的二进制编码可能具有较大的Hamming距离，降距离，降低了遗传算子的搜索效率。低了遗传算子的搜索效率。15：01111 16：10000 要先给出求解的精度。要先给出求解的精度。求解高维优化问题的二进制编码串长，算法的搜索效率低。求解高维优化问题的二进制编码串长，算法的搜索效率低。Gray编码编码:将二进制编码通过一个变换进行转换得到的编码。将二进制编码通过

11、一个变换进行转换得到的编码。二进制串二进制串 n.21 Gray n.21二进制编码二进制编码 Gray编码编码1111kkkkkGray编码编码 二进制编码二进制编码 )2(mod1kiik 采用实数表达法采用实数表达法不必进行数制转换不必进行数制转换，可直接在解的表，可直接在解的表现型上进行遗传操作。现型上进行遗传操作。多参数映射编码的基本思想多参数映射编码的基本思想：把每个参数先进行二进把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。制编码得到子串，再把这些子串连成一个完整的染色体。多参数映射编码中的每个子串对应各自的编码参数，多参数映射编码中的每个子串对应各自的编

12、码参数，所以，可以有所以，可以有不同的串长度和参数的取值范围不同的串长度和参数的取值范围。有序问题有序问题：目标函数的值不仅与表示解的字符串的值目标函数的值不仅与表示解的字符串的值有关，而且与其所在字符串的位置有关。有关，而且与其所在字符串的位置有关。4结构式编码结构式编码 Goldberg等提出等提出MessyGA(mGA)的遗传算法编码方法。的遗传算法编码方法。1.初始种群的产生初始种群的产生（1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中

13、个体数目达到了预先确定的规模。2.种群规模的确定种群规模的确定 模式定理模式定理表明：若群体规模为M，则遗传操作可从这M 个个体中生成和检测 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。3M 群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。群体规模太大，计算复杂。1.1.将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法 若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则)()(xfxfFit)(1)(xfxfFit将目标函数转换为求最大值的形式将目标函数转换为求最大值的形式,且保证函数值非负！且保证函数值非负！若目标函数为最大化最大化

14、问题，则 若目标函数为最小化最小化问题，则minmin()()()0f xCf xCFit f x其他情况maxmax()()()0Cf xf xCFit f x其他情况1.1.将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法(续）续）存在界限值预选估计困难或者不能精确估计的问题！存在界限值预选估计困难或者不能精确估计的问题！若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则 ：目标函数界限的保守估计值。1()0()01()Fit f xccf xcf x，1()0()01()Fit f xccf xcf x，c2.适应度函数的尺度变换适应度函数的尺度变换 在遗

15、传算法中，将所有妨碍适应度值高的个体产生，从而 影 响 遗 传 算 法 正 常 工 作 的 问 题 统 称 为 欺 骗 问 题欺 骗 问 题（deceptive problem）。过早收敛过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。停滞现象停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。适应度函数的尺度变换（尺度变换（fitness scaling）或者定标定标：对适应度函数值域的某种映射变换。2.适应度函数适应度函数的尺度变换的尺度变换(续）续）（1）线性变换：baffminfffaavgavgminminffffbavgavgavgavgmultfffCamax

16、)1(avgavgavgmultffffCfbmaxmax)(,avgavgff avgmultfCfmax满足满足最小适应度值非负满足最小适应度值非负 2.适应度函数适应度函数的尺度变换的尺度变换(续）续）（2）幂函数变换法：Kff affe（3）指数变换法：Miiisiffp1 各个个体被选择的概率和其适应度值成比例。个体 被选择的概率为：i 线性排序：J.E.Baker 群体成员按适应值大小从好到坏依次排列：个体 按转盘式选择的方式选择父体Nxxx,21 iipx 分配选择概率)1(MMbiapi 非线性排序：Z.Michalewicz 将群体成员按适应值从好到坏依次排列，并按下式分配选

17、择概率：MiMiqqqpMii1,2,1)1()1(11 可用其他非线性函数来分配选择概率，只要满足以下条件：Miip11 )2(满足则且若iMMpxfxfxfxxxP ),(.)()(,)1(212,1Mppp 21 按个体的选择概率产生一个轮盘，轮盘每个区的角度与个按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。体的选择概率成比例。产生一个随机数，它落入转盘的哪个区域就选择相应的个产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。体交叉。第1轮产生一个随机数：0.81 第2轮产生一个随机数：0.32 锦标赛选择方法锦标赛选择方法：从群体中随机选择个个体，将其中

18、适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。随机竞争方法随机竞争方法（stochastic tournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。),(选择),(从规模为 的群体中随机选取个体通过重组和变异生成 个后代，再选取 个最优的后代作为新一代种群。)(选择 从 个后代与其父体共 中选取 个最优的后代。)(最佳个体（最佳个体（elitist model）保存方法）保存方法：把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代

19、出现过的最高适应度的个体。（5）最佳个体保存方法 随机选取两个个体 ，若 则选择适应值好的作为胜者，否则计算概率 ，若 ，选择差解，否则选择好解。21,xx|21xfxf Txfxfp|exp21)1,0randomp 一点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。（2）二点交叉二点交叉（two-point crossover）均匀交叉：按照均匀概率抽取一些位，每一位是否被选取都是随机的，并且独立于其他位。然后将两个个体被抽取位互换组成两个新个体。（3）均匀交叉均匀交

20、叉（uniform crossover）或一致交叉231765489A645932178B231932489A645765178BHHHA176548HHHB493218481765HHHA 184932HHHB 481932765 A184765932 B（3）循环交叉循环交叉CX：Smith D.(1985)部分离散交叉部分离散交叉：在父解向量中选择一部分分量，然后交换这些分量。二进制的点式交叉二进制的点式交叉 整体离散交叉整体离散交叉：以0.5的概率交换父体 的所有分量。二进制编码的均匀性交叉二进制编码的均匀性交叉 21ss 与 部分算术部分算术：先在父解向量中选择一部分分量，如第 个分

21、量以后的所有分量，然后生成 个0，1区间的随机数，并将两个后代定义为：kkn)1(,.,1,.,()2()1()2(11)1(11)1()1(1vvvvvvnnnnkkkkkzaaaas)1(,.,1,.,()1()2()1(11)2(11)2()2(1vvvvvvnnnnkkkkkwaaaasnkaa.1 整体算术交叉整体算术交叉：先生成 n 个区间的随机数，则后代分别定义为：)()1()2()1()2()2()1(iiiiiiiiivvavvavaz)()1()1()2()1()1()2(iiiiiiiiivvavvavawnaaa.21（2）逆转变异逆转变异：在个体码串中随机选择两点（逆

22、转点），然后将两点之间的基因值以逆向排序插入到原位置中。（3）插入变异插入变异：在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间。：父解),.,.,(21nkvvvvs：变异产生的后代),.,.,(21nkvvvvskivkivski,均匀性变异均匀性变异：在父解向量中随机地选择一个分量（第 个），然后在 中以均匀概率随机选择 代替 以得到 ，即 k,kkbakvkv snvvvs,21 解向量n,21 摄动向量,s被选个体,s新个体,0expiiiNiiiNvv,0ni,2,1 Z.Michalewicz首先提出将变异算子的结果与演化代数联系起来。在演化初期，变异范围相对较大，

23、而随着演化的推进，变异范围越来越小，起着一种对演化系统的微调作用。：解空间的一个向量,21nvvvs max1fsfT变异温度：自适应变异方式与非一致性变异算子相同，只是将其中的演化代数 改为 ，函数表达式变为：tTTryyT1,0001100000 0101111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）88521071251910140.08695758521071251910140.

24、0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086

25、960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！淘汰！淘汰！0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 00010100110001100000

26、 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001

27、01001100011110100000010110111100001011010110111100001001010100000110011101001100000001101010100010100100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010

28、10001010010011x-1,2 x-1,2 ，求解结果精确到，求解结果精确到6 6位小数。位小数。0.2)10sin()(xxxf编码解码个体（染色体）基因niiiiFFP1/交叉点交叉点变异点变异点产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次（1 1）对群体中的所有个体对群体中的所有个体按其适应度大小进行降序排按其适应度大小进行降序排序；序；（2 2）根据具体求解问题，根据具体求

29、解问题，设计一个概率分配表，将各设计一个概率分配表，将各个概率值按上述排列次序分个概率值按上述排列次序分配给各个个体；配给各个个体；（3 3）以各个个体所分配到以各个个体所分配到的概率值作为其遗传到下一的概率值作为其遗传到下一代的概率，基于这些概率用代的概率，基于这些概率用赌盘选择法来产生下一代群赌盘选择法来产生下一代群体。体。（1 1）随机产生一个与个体随机产生一个与个体编码长度相同的二进制屏蔽编码长度相同的二进制屏蔽字字P=WP=W1 1W W2 2WWn n ；（2 2）按下列规则从按下列规则从A A、B B两两个父代个体中产生两个新个个父代个体中产生两个新个体体X X、Y Y：若：若W

30、 Wi i=0=0，则，则X X的第的第i i个基因继承个基因继承A A的对应基因，的对应基因，Y Y的第的第i i个基因继承个基因继承B B的对应基的对应基因；若因；若W Wi i=1=1，则，则A A、B B的第的第i i个基因相互交换，从而生成个基因相互交换，从而生成X X、Y Y的第的第i i个基因。个基因。变异前：变异前：3 4 8|7 9 6 5|2 13 4 8|7 9 6 5|2 1变异前：变异前：3 4 8|5 6 9 7|2 13 4 8|5 6 9 7|2 12xf(x)2xf(x)2xf(x)iisffPiiff 串2 串1 串4 串3 1、基于遗传算法的、基于遗传算法

31、的PID参数优化设计参数优化设计基于遗传算法的自适应基于遗传算法的自适应PID控制的原理框图如图所示，图中省控制的原理框图如图所示，图中省略了遗传算法的具体操作过程。其思想就是将控制器参数构成略了遗传算法的具体操作过程。其思想就是将控制器参数构成基因型，将性能指标构成相应的适应度，便可利用遗传算法来基因型，将性能指标构成相应的适应度，便可利用遗传算法来整定控制器的最佳参数，并且不要求系统是否为连续可微的，整定控制器的最佳参数，并且不要求系统是否为连续可微的，能否以显式表示。能否以显式表示。(1)当遗传算法用于当遗传算法用于PID控制参数寻优时的操作流程控制参数寻优时的操作流程 参数编码、种群初

32、始化参数编码、种群初始化;适应度函数的确定适应度函数的确定;通过复制、交叉、变异等算子更新种群通过复制、交叉、变异等算子更新种群;结束进化过程。结束进化过程。(2)采用遗传算法进行采用遗传算法进行PID三个参数的整定时具有的优点三个参数的整定时具有的优点 与单纯形相比，遗传算法同样具有良好的寻优特性，且它克服了单纯形参数与单纯形相比，遗传算法同样具有良好的寻优特性，且它克服了单纯形参数初值的敏感性。在初始条件选择不当的情况下，遗传算法在不需要给出调节器初初值的敏感性。在初始条件选择不当的情况下，遗传算法在不需要给出调节器初始参数的情况下，仍能寻找到合适的参数，使控制目标满足要求。同时单纯形法始

33、参数的情况下，仍能寻找到合适的参数，使控制目标满足要求。同时单纯形法难以解决多值函数问题以及在多参数寻优中，容易造成寻优失败或时间过长，而难以解决多值函数问题以及在多参数寻优中，容易造成寻优失败或时间过长，而遗传算法的特性决定了它能很好地克服以上问题。遗传算法的特性决定了它能很好地克服以上问题。与专家整定法相比，它具有操作方便、速度会地优点，不需要复杂地规则，与专家整定法相比，它具有操作方便、速度会地优点，不需要复杂地规则，只通过字串进行简单地复制、交叉、变异，便可达到寻优。避免了专家整定法中只通过字串进行简单地复制、交叉、变异，便可达到寻优。避免了专家整定法中前期大量地知识库整理工作及大量地

34、仿真实验。前期大量地知识库整理工作及大量地仿真实验。遗传算法是从许多点开始并行操作，在解空间进行高效启发式搜索，克服了遗传算法是从许多点开始并行操作，在解空间进行高效启发式搜索，克服了从单点出发的弊端以及搜索的盲目性，从而使寻优速度更快，避免了过早陷入局从单点出发的弊端以及搜索的盲目性，从而使寻优速度更快，避免了过早陷入局部最优解。部最优解。遗传算法不仅适用于单目标寻优，而且也适用于多目标寻优。根据不同的控遗传算法不仅适用于单目标寻优，而且也适用于多目标寻优。根据不同的控制系统，针对一个或多个目标，遗传算法均能在规定的范围内寻找到合适的参数。制系统，针对一个或多个目标，遗传算法均能在规定的范围

35、内寻找到合适的参数。遗传算法作为一种全局优化算法，得到了越来越广泛的应用。近年来，在控制上遗传算法作为一种全局优化算法，得到了越来越广泛的应用。近年来，在控制上的应用也越来越多。的应用也越来越多。2、基于遗传算法的预测自整定、基于遗传算法的预测自整定PID控制器控制器基于遗传算法的预测自整定基于遗传算法的预测自整定PID控制系统结构如图所示。控制系统结构如图所示。这种算法利用预测技术克服时滞，利用遗传算法优化这种算法利用预测技术克服时滞，利用遗传算法优化PID控控制器参数。对工业过程中典型的大时滞被控过程鲁棒性强，制器参数。对工业过程中典型的大时滞被控过程鲁棒性强，响应速度快，抗干扰能力强，可构成较实用的工程控制器。响应速度快，抗干扰能力强，可构成较实用的工程控制器。按按PID控制的增量式算式，控制的增量式算式，Kp，Ki，Kd便是控制器要寻优的便是控制器要寻优的参数，在遗传算法中其初始值随机产生。参数，在遗传算法中其初始值随机产生。PID控制器的输入控制器的输入是最优预测形成的反馈偏差，在控制过程中，被控过程未来是最优预测形成的反馈偏差，在控制过程中，被控过程未来的最优状态来控制其当前行为，提高控制决策的智能性及控的最优状态来控制其当前行为，提高控制决策的智能性及控制系统的动态品质，减小时滞对系统稳定性的影响。制系统的动态品质，减小时滞对系统稳定性的影响。