《进化算法-遗传算法精选PPT.ppt》由会员分享，可在线阅读，更多相关《进化算法-遗传算法精选PPT.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、进化算法化算法-遗传算法算法1第1页，此课件共49页哦第第8章进化算法章进化算法遗传算法遗传算法智能控制基础智能控制基础第2页，此课件共49页哦8.2.1 遗传学习的基本思想8.2.2遗传学习算法的理论基础8.2.3遗传学习算法的改良8.2.4遗传学习算法的应用8.2 遗传学习原理与算法遗传学习原理与算法3第3页，此课件共49页哦1.问题的提出问题的提出v美国的美国的J.Holland教授于教授于1975年提出年提出v在遗传学的基础上利用计算机来模拟生物的进在遗传学的基础上利用计算机来模拟生物的进化过程，从而实现复杂问题的优化求解。化过程，从而实现复杂问题的优化求解。v模拟生物染色体的运作（复
2、制、交叉、变异），模拟生物染色体的运作（复制、交叉、变异），是一种随机化搜索算法是一种随机化搜索算法4第4页，此课件共49页哦步骤步骤5第5页，此课件共49页哦需要解决的问题需要解决的问题 v编码机制；编码机制；v选择机制；选择机制；v控制参数选择；控制参数选择；v二进制字符串的群体构成；二进制字符串的群体构成；v适应度函数的计算适应度函数的计算v遗传算子（交叉、变异）的定义。遗传算子（交叉、变异）的定义。6第6页，此课件共49页哦2.遗传学习算法的操作算子遗传学习算法的操作算子 v编码机制编码机制(Encoding mechanism)v适应度函数适应度函数(Fitness function
3、)v选择机制选择机制(Selection mechanism)v 交叉算子交叉算子(Crossover)v变异算子变异算子(Mutation)7第7页，此课件共49页哦(1)编码机制编码机制 v二进制编码二进制编码 n每一个位（0或1）基因n字符串染色体v多值编码方法多值编码方法 v实数编码实数编码8第8页，此课件共49页哦(2)适应度函数适应度函数 v优化问题的目标函数优化问题的目标函数v“适应度值适应度值”的计算直接通过将目标函数经一定的计算直接通过将目标函数经一定的线性变换映射到的的线性变换映射到的0，1区间内的一个值。区间内的一个值。9第9页，此课件共49页哦(3)选择机制选择机制 v
4、基本思想取自于自然界进化论的基本思想取自于自然界进化论的“适者生存适者生存”。v适应度值越高的个体，生存的数量也越高。满适应度值越高的个体，生存的数量也越高。满足足“优胜劣汰优胜劣汰”自然法则。自然法则。v也可称为复制机制也可称为复制机制v比例选择法比例选择法(Proportionate selection scheme)v转轮选择法转轮选择法(Roulette Wheel Selection Scheme)：随机方法随机方法10第10页，此课件共49页哦(4)交叉算子交叉算子 v模拟有性繁殖现象模拟有性繁殖现象v随机地从父辈集合中选取两个个体作为双亲。随机地从父辈集合中选取两个个体作为双亲。
5、设设L表示一个体的字符串（染色体）长度，随机地表示一个体的字符串（染色体）长度，随机地产生产生(0L)之间的一个数之间的一个数d，并把此点位置称为，并把此点位置称为交叉点。交叉运算就是将双亲的基因链在交叉交叉点。交叉运算就是将双亲的基因链在交叉点断裂，且将在交叉点之后的基因根据交叉率点断裂，且将在交叉点之后的基因根据交叉率的条件决定是否进行相互交换形成下一代。的条件决定是否进行相互交换形成下一代。v所谓交叉率所谓交叉率pc是根据优化问题预先确定的一个是根据优化问题预先确定的一个01之间的值。通常取之间的值。通常取0.60.9。11第11页，此课件共49页哦(5)变异算子变异算子v模拟基因突变现
6、象模拟基因突变现象v所谓变异指的是随机地选取染色体中的某个基因所谓变异指的是随机地选取染色体中的某个基因（也即字符串中的某一位）进行取反运算，即将（也即字符串中的某一位）进行取反运算，即将原有的原有的“1”变为变为“0”和反之。和反之。v变异率变异率pm取比较小的数值，一般取比较小的数值，一般pm为为0.0010.2。12第12页，此课件共49页哦3.遗传学习算法的设计举例遗传学习算法的设计举例 13第13页，此课件共49页哦(1)群体初始化群体初始化v群体规模群体规模N 一般情况下取一般情况下取N=10200之间为宜。之间为宜。v初始群体的构成初始群体的构成 随机选择随机选择 14第14页，
7、此课件共49页哦举例举例群体群体 P1（随机初始化）（随机初始化）染色体适应度值00000111000.210000111110.601101010110.611111110110.915第15页，此课件共49页哦v以以的比例分配转轮的比例分配转轮(2)选择选择 16第16页，此课件共49页哦选择举例选择举例 群体群体 P2（经选择经选择后）后）染色体适应度值10000111110.601101010110.611111110110.911111110110.917第17页，此课件共49页哦群体群体 P3（交叉运算后）（交叉运算后）染色体适应度值10000110110.501101010110
8、.611111110110.911111111111.0(3)交叉交叉 v本例中随机选取本例中随机选取1和和4号个体、号个体、2和和3号个体分别形号个体分别形成两对进行交叉运算。当取交叉率成两对进行交叉运算。当取交叉率pc=0.5时，只有时，只有个体个体1和和4这一对双亲进行真正的交叉运算，而另这一对双亲进行真正的交叉运算，而另一对个体一对个体2和和3不进行交叉运算。不进行交叉运算。18第18页，此课件共49页哦(4)变异变异 v取取pm=0.05 vP4给出了第给出了第2个个体和第个个体和第4个个体中分别有一个基个个体中分别有一个基因发生变异后的情况。因发生变异后的情况。群体群体P4(变变异
9、运算后异运算后)染色体适应度值10000110110.501101110110.711111110110.901111111110.919第19页，此课件共49页哦(5)终止准则判断终止准则判断 v方法有两类：方法有两类：20第20页，此课件共49页哦8.2.1 遗传学习的基本思想8.2.2遗传学习算法的理论基础8.2.3遗传学习算法的改良8.2.4遗传学习算法的应用8.2 遗传学习原理与算法遗传学习原理与算法21第21页，此课件共49页哦8.2.2 理论基础理论基础v有多种理论分析遗传算法的收敛性，例如有多种理论分析遗传算法的收敛性，例如nHolland提出的模板理论(Schema theo
10、ry)nGoldberg提出的建筑块假设(Building block hypothesis)。v它们通过计算有用相似性，检查包含在群体中的它们通过计算有用相似性，检查包含在群体中的各种模板的增长速率来表明遗传学习的能力。各种模板的增长速率来表明遗传学习的能力。v这里主要介绍模板定理这里主要介绍模板定理 22第22页，此课件共49页哦1.模板的基本概念模板的基本概念v模板表示那些在某些基因位置上具有相同性质、而模板表示那些在某些基因位置上具有相同性质、而在另一些位置上是不影响子集特征的染色体集合。在另一些位置上是不影响子集特征的染色体集合。v例如：模板例如：模板*000表示最后三个位置的值必须
11、为表示最后三个位置的值必须为“0”的一组染色体构成的子集。的一组染色体构成的子集。v在二进制编码前提下，在二进制编码前提下，“*”可以是可以是“0”、也可、也可以是以是“1”。23第23页，此课件共49页哦模板的阶o(S)模板的阶o(S)模板的定义长度(S)模板中含有0或1的个数。如S=*111，则模板S的阶o(S)=3。模板中有确定值数码之间的最大距离。如：S=*111，则模板S的长度(S)=2。S=1*00*，则模板S的长度(S)=3。两个定义两个定义24第24页，此课件共49页哦2.模板定理模板定理v假设一个假设一个L长的染色体。如果用二进制编码，则有长的染色体。如果用二进制编码，则有2
12、L个模板。个模板。v对于有对于有N个个体构成的群体总的模板数个个体构成的群体总的模板数NS满足：满足：。vNS的实际大小取决于群体中染色体的分散性。的实际大小取决于群体中染色体的分散性。v模板理论可以说明在进化计算中特定字符串在下一模板理论可以说明在进化计算中特定字符串在下一代中繁殖的情况。代中繁殖的情况。25第25页，此课件共49页哦（1）选择算子）选择算子 v假设模板假设模板S在在t时刻在群体中有时刻在群体中有n(S,t)个特定字符串个特定字符串（即同一字符串在群体中的占有数目）。（即同一字符串在群体中的占有数目）。v由比例选择法可知由比例选择法可知 其中：其中：f(S):模板S内所有子集
13、的目标函数平均值；f(P):群体内的平均目标函数值.当当f(S)f(P)时，该模板的数目会增加时，该模板的数目会增加 26第26页，此课件共49页哦（2）交叉算子）交叉算子 v交叉算子运算后，模板交叉算子运算后，模板S中保留特定字符串的概率中保留特定字符串的概率 v选择、交叉算子运算后，在下一代中模板选择、交叉算子运算后，在下一代中模板S的特定的特定字符串数目满足字符串数目满足：v具有较好的目标函数和较短定义长度的模板，其具有较好的目标函数和较短定义长度的模板，其字符串的增长率最快。字符串的增长率最快。27第27页，此课件共49页哦（3）变异算子）变异算子 v在变异运算后字符串仍然属于在变异运
14、算后字符串仍然属于S模板的概率为模板的概率为 因为，变异率因为，变异率pm通常是非常小通常是非常小 28第28页，此课件共49页哦定理定理8-1:模板定理模板定理 v这一定理表明了随着遗传学习的进行，优秀品这一定理表明了随着遗传学习的进行，优秀品质的字符串个体在群体中占有的数目会越来越质的字符串个体在群体中占有的数目会越来越多，最终得到平均适应度高、定义长度短和阶多，最终得到平均适应度高、定义长度短和阶次小的模板。这种模板又可称为建筑块。次小的模板。这种模板又可称为建筑块。29第29页，此课件共49页哦8.2.1 遗传学习的基本思想8.2.2遗传学习算法的理论基础8.2.3遗传学习算法的改良8
15、.2.4遗传学习算法的应用8.2 遗传学习原理与算法遗传学习原理与算法30第30页，此课件共49页哦8.2.3 遗传学习算法的改良遗传学习算法的改良 v目前已经提出的改进方案有：目前已经提出的改进方案有：n编码机制灰度编码和动态编码；n选择机制优选策略、基于次序的选择、稳定状态选择及随机余数法的比例选择；n交叉机制两点或多点交叉、均匀交叉；n控制参数动态自适应参数控制技术；n算法策略分布式遗传学习算法和并行遗传学习算法。31第31页，此课件共49页哦1.编码机制的改进编码机制的改进 v灰度编码技术保证连续变量编码后的相邻灰度编码技术保证连续变量编码后的相邻Hamming距离为距离为1。0 00
16、00 8 0011 1 1000 9 1011 2 1100 10 1111 3 0100 11 0111 4 0110 12 0101 5 1110 13 1101 6 1010 14 1001 7 0010 15 000132第32页，此课件共49页哦2.选择机制的改进选择机制的改进 v解决早熟问题。有两个途径：解决早熟问题。有两个途径：n一是采用全量程适应度函数定标；n二是采用改进的选择方案。33第33页，此课件共49页哦全量程适应度函数定标全量程适应度函数定标v线性变换线性变换 计算的准则是希望换算后的适应度最大值应该是群体平均适计算的准则是希望换算后的适应度最大值应该是群体平均适应度
17、值的某一小的倍数，通常取应度值的某一小的倍数，通常取1.5或或2。v-截断法截断法 其中其中 ：群体的平均适应度值；群体的平均适应度值；：群体适应度的标准方差；群体适应度的标准方差；c：一个小的常数，通常取一个小的常数，通常取13。34第34页，此课件共49页哦选择方法的改进选择方法的改进v基于次序的选择法基于次序的选择法 v竞争选择竞争选择 v随机余数技术随机余数技术 v优选策略优选策略 v局部替代法局部替代法 v稳定状态法稳定状态法 v选择育种法选择育种法 35第35页，此课件共49页哦 3.交叉机制的改进交叉机制的改进 v两点交叉或多点交叉两点交叉或多点交叉v均匀交叉（是否交叉由概率决定
18、）均匀交叉（是否交叉由概率决定）n父辈字符串分别为A、B：A=10110011011101 B=11011000010101 n交叉后的子代为：A=11110011010101 B=1001100001110136第36页，此课件共49页哦倒置变换倒置变换 v对于字长为对于字长为10的字符串个体的字符串个体 A=1001101010随机选取两点随机选取两点4和和8。将。将4与与8之间的字符串进行之间的字符串进行倒置，即第倒置，即第7位变换到第位变换到第4位、第位、第6位变换到第位变换到第5位位.，生成新的个体，生成新的个体A A=100101101037第37页，此课件共49页哦4.控制参数控
19、制参数 经验性结论经验性结论v增大群体规模会增加群体中个体的发散性，减少增大群体规模会增加群体中个体的发散性，减少GA算法过早收敛于局部最优的可能性。但也算法过早收敛于局部最优的可能性。但也增加了算法的计算时间。增加了算法的计算时间。v小规模群体的小规模群体的GA搜索问题可以选择相对较大的搜索问题可以选择相对较大的交叉率和变异率，而群体规模比较大时，可以选交叉率和变异率，而群体规模比较大时，可以选择较小的交叉率和变异率。择较小的交叉率和变异率。38第38页，此课件共49页哦5.算法策略算法策略 v动态自适应策略动态自适应策略 根据性能指标和搜索的阶段，自适应调整控制参根据性能指标和搜索的阶段，
20、自适应调整控制参数，对于遗传算法的收敛，尤其对高精度最优解数，对于遗传算法的收敛，尤其对高精度最优解的搜索有着重要的作用的搜索有着重要的作用。v分布式分布式GA算法和并行算法和并行GA算法策略算法策略n分布式GA算法是一个群整体分解为几个弱相关的子体分别进行进化计算，n并行GA算法是对传统的串行计算方法用并行计算手段来实现。39第39页，此课件共49页哦GA的优点的优点vGA算法的突出优点在于能够根据交互的环境中的相算法的突出优点在于能够根据交互的环境中的相应情况和进化算子在没有任何最优解先验知识条件应情况和进化算子在没有任何最优解先验知识条件下寻找到最优解。它不同于梯度下降法那样只对一下寻找
21、到最优解。它不同于梯度下降法那样只对一点进行优化计算而是通过对群体中的所有个体进行点进行优化计算而是通过对群体中的所有个体进行遗传操作达到优化的目的，因此避免了单点优化算遗传操作达到优化的目的，因此避免了单点优化算法可能出现的局部最优问题。从而使得法可能出现的局部最优问题。从而使得GA算法可算法可以处理复杂的、高维的、多目标的优化问题。这以处理复杂的、高维的、多目标的优化问题。这些都是传统优化方法无法比拟的。些都是传统优化方法无法比拟的。40第40页，此课件共49页哦8.2.1 遗传学习的基本思想8.2.2遗传学习算法的理论基础8.2.3遗传学习算法的改良8.2.4遗传学习算法的应用8.2 遗
22、传学习原理与算法遗传学习原理与算法41第41页，此课件共49页哦8.2.4 遗传学习算法的应用遗传学习算法的应用 v遗传学习算法能够解决许多传统的优化方法难以解遗传学习算法能够解决许多传统的优化方法难以解决的众多问题，已经在工程优化设计、机器学习、决的众多问题，已经在工程优化设计、机器学习、自适应控制、鲁棒控制器设计、自适应控制、鲁棒控制器设计、PID控制、模糊逻控制、模糊逻辑控制器优化、最优控制、系统辨识、故障诊断、辑控制器优化、最优控制、系统辨识、故障诊断、神经网络控制等领域得到应用和发展。神经网络控制等领域得到应用和发展。42第42页，此课件共49页哦1.非线性系统的神经网络辨识非线性系
23、统的神经网络辨识 43第43页，此课件共49页哦举例举例v考虑非线性系统考虑非线性系统v选择神经网络结构为选择神经网络结构为n输入矢量为y(k),y(k-1),u(k)n输出矢量为y(k+1)。44第44页，此课件共49页哦GA设计设计v用一个用一个16位字长的编码来表示一个权系数，神经网位字长的编码来表示一个权系数，神经网络结构共需要络结构共需要16(1+3)6+(6+1)1=496位长的字符串。位长的字符串。v群体规模群体规模N=60，pc=0.7,pm=0.01。45第45页，此课件共49页哦收敛曲线收敛曲线46第46页，此课件共49页哦2.倒立摆神经网络控制倒立摆神经网络控制 47第47页，此课件共49页哦动力学方程动力学方程 v 摆杆重量 mp=0.1kgv 车、杆总重量 m=1.1kgv 杆长的一半 l=0.5mv 小车对地摩擦系数 c=0.0005v 杆对小车摩擦系数 p=0.000002v 重力加速度 g=9.8v 作用于小车的力 F=-10,10牛顿之间。48第48页，此课件共49页哦控制效果控制效果v经过经过22次迭代后，其控制维持时间大于次迭代后，其控制维持时间大于15000步。步。v倒立摆摆角倒立摆摆角和小车位移和小车位移X的运动轨迹如图：的运动轨迹如图：49第49页，此课件共49页哦