遗传算法——遗传算法.pptx

《遗传算法——遗传算法.pptx》由会员分享，可在线阅读，更多相关《遗传算法——遗传算法.pptx（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 遗遗传传算算法法简简称称GAGA（Genetic Genetic AlgorithmsAlgorithms）是是19621962年年由由美美国国MichiganMichigan大大学学的的HollandHolland教教授授提提出出的的模模拟拟自自然然界界遗遗传传机机制制和和生生物物进进化化论论而而成成的的一一种种并并行行随随机机搜搜索索最最优化方法。优化方法。遗遗传传算算法法是是以以达达尔尔文文的的自自然然选选择择学学说说为为基基础础发发展展起起来的。自然选择学说包括以下三个方面：来的。自然选择学说包括以下三个方面：第1页/共81页（1 1）遗遗传传：这这是是生生物物的的普普遍遍特特征征，

2、亲亲代代把把生生物物信信息息交交给给子子代代，子子代代总总是是和和亲亲代代具具有有相相同同或或相相似似的的性性状状。生生物有了这个特征，物种才能稳定存在。物有了这个特征，物种才能稳定存在。（2 2）变变异异：亲亲代代和和子子代代之之间间以以及及子子代代的的不不同同个个体体之之间间的的差差异异，称称为为变变异异。变变异异是是随随机机发发生生的的，变变异异的的选选择择和积累是生命多样性的根源。和积累是生命多样性的根源。（3 3）生生存存斗斗争争和和适适者者生生存存：具具有有适适应应性性变变异异的的个个体体被被保保留留下下来来，不不具具有有适适应应性性变变异异的的个个体体被被淘淘汰汰，通通过过一一代

3、代代代的的生生存存环环境境的的选选择择作作用用，性性状状逐逐渐渐逐逐渐渐与与祖祖先先有有所不同，演变为新的物种。所不同，演变为新的物种。第2页/共81页 遗遗传传算算法法将将“优优胜胜劣劣汰汰，适适者者生生存存”的的生生物物进进化化原原理理引引入入优优化化参参数数形形成成的的编编码码串串联联群群体体中中，按按所所选选择择的的适适应应度度函函数数并并通通过过遗遗传传中中的的复复制制、交交叉叉及及变变异异对对个个体体进进行行筛筛选选，使使适适适适应应度度高高的的个个体体被被保保留留下下来来，组组成成新新的的群群体体，新新的的群群体体既既继继承承了了上上一一代代的的信信息息，又又优优于于上上一一代代

4、。这这样样周周而而复复始始，群群体体中中个个体体适适应应度度不不断断提提高高，直直到到满满足足一一定定的的条条件件。遗遗传传算算法法的的算算法法简简单单，可可并并行行处理，并能到全局最优解。处理，并能到全局最优解。第3页/共81页遗传算法的基本操作为：遗传算法的基本操作为：（1 1）复制（）复制（Reproduction OperatorReproduction Operator）复复制制是是从从一一个个旧旧种种群群中中选选择择生生命命力力强强的的个个体体位位串串产产生生新新种种群群的的过过程程。具具有有高高适适应应度度的的位位串串更更有有可可能能在在下下一一代代中产生一个或多个子孙。中产生一

5、个或多个子孙。复复制制操操作作可可以以通通过过随随机机方方法法来来实实现现。首首先先产产生生0101之之间间均均匀匀分分布布的的随随机机数数，若若某某串串的的复复制制概概率率为为40%40%，则则当当产产生生的的随随机机数数在在0.401.00.401.0之之间间时时，该该串串被被复复制制，否否则则被被淘汰。淘汰。第4页/共81页（2 2）交叉（）交叉（Crossover OperatorCrossover Operator）复复制制操操作作能能从从旧旧种种群群中中选选择择出出优优秀秀者者，但但不不能能创创造造新新的的染染色色体体。而而交交叉叉模模拟拟了了生生物物进进化化过过程程中中的的繁繁殖

6、殖现现象象，通通过过两两个个染染色色体体的的交交换换组组合合，来来产产生生新新的的优优良良品品种。种。交交叉叉的的过过程程为为：在在匹匹配配池池中中任任选选两两个个染染色色体体，随随机机选选择择一一点点或或多多点点交交换换点点位位置置；交交换换双双亲亲染染色色体体交交换换点点右边的部分，即可得到两个新的染色体数字串。右边的部分，即可得到两个新的染色体数字串。第5页/共81页 交杈体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法，应用较广。它是指染色体切断点有一处，例：第6页/共81页（3 3）变异）变异(Mutation Oper

7、ator)(Mutation Operator)变变异异运运算算用用来来模模拟拟生生物物在在自自然然的的遗遗传传环环境境中中由由于于各各种种偶偶然然因因素素引引起起的的基基因因突突变变，它它以以很很小小的的概概率率随随机机地地改改变变遗遗传传基基因因（表表示示染染色色体体的的符符号号串串的的某某一一位位）的的值值。在在染染色色体体以以二二进进制制编编码码的的系系统统中中，它它随随机机地地将将染染色体的某一个基因由色体的某一个基因由1 1变为变为0 0，或由，或由0 0变为变为1 1。第7页/共81页 若若只只有有选选择择和和交交叉叉，而而没没有有变变异异，则则无无法法在在初初始始基基因因组组合

8、合以以外外的的空空间间进进行行搜搜索索，使使进进化化过过程程在在早早期期就就陷陷入入局局部部解解而而进进入入终终止止过过程程，从从而而影影响响解解的的质质量量。为为了了在在尽尽可可能能大大的的空空间间中中获获得得质质量量较较高高的的优优化化解解，必必须须采采用用变变异异操操作。作。第8页/共81页10.2 10.2 遗传算法的特点遗传算法的特点（1 1）遗遗传传算算法法是是对对参参数数的的编编码码进进行行操操作作，而而非非对对参参数数本本身身，这这就就是是使使得得我我们们在在优优化化计计算算过过程程中中可可以以借借鉴鉴生生物物学学中中染染色色体体和和基基因因等等概概念念，模模仿仿自自然然界界中

9、中生生物物的的遗遗传和进化等机理；传和进化等机理；（2 2）遗遗传传算算法法同同时时使使用用多多个个搜搜索索点点的的搜搜索索信信息息。传传统统的的优优化化方方法法往往往往是是从从解解空空间间的的单单个个初初始始点点开开始始最最优优解解的的迭迭代代搜搜索索过过程程，单单个个搜搜索索点点所所提提供供的的信信息息不不多多，搜搜索索效效率率不不高高，有有时时甚甚至至使使搜搜索索过过程程局局限限于于局局部部最最优优解解而停滞不前。而停滞不前。第9页/共81页 遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索

10、效率较高。（3 3）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。第10页/共81页 遗传算法可应用于目标函数无法求导数或导数不遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题等。存在的函数的优化问题，以及组合优化问题等。（4 4）遗传算法使用概率搜索技术。遗传算法的选择、）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行

11、的，交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行，遗传算法新的群体会更多地产生出许化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。多新的优良的个体。第11页/共81页（5 5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；（6 6）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广；（7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来

12、提高计算速度，适合大规模复杂问题的优化。第12页/共81页10.3 10.3 遗传算法的发展及应用遗传算法的发展及应用10.3.1 遗传算法的发展遗传算法的发展 遗传算法起源于对生物系统所进行的计算机模拟研究。早在20世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入20世纪60年代，美国密执安大学的Holland教授及其学生们受到这种生物模拟技术的启发，创造出一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术遗传算法。第13页/共81页 以下是在遗传算法发展进程中一些关键人物所做出的主要

13、贡献：（1）J.H.Holland 20世纪70年代初，Holland教授提出了遗传算法的基本定理模式定理，从而奠定了遗传算法的理论基础。模式定理揭示了群体中优良个体（较好的模式）的样本数将以指数级规律增长，从理论上保证了遗传算法用于寻求最优可行解的优化过程。1975年，Holland出版了第一本系统论述遗传算法和人工自适应系统的专著自然系统和人工系统的自适应性。20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统分类器系统，开创了基于遗传算法的机器学习的新概念。第14页/共81页（2）J.D.Bagley 1967年，Holland的学生Bagley在其博士论文中首次提

14、出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。在遗传算法的不同阶段采用了不同的概率，从而创立了自适应遗传算法的概念。第15页/共81页（3）K.A.De Jong 1975年，De Jong博士在其博士论文中结合模式定理进行了大量纯数值函数优化计算实验，树立了遗传算法的工作框架。他推荐了在大多数优化问题中都较适用的遗传算法的参数，建立了著名的De Jong五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。（4）D.J.Goldberg 1989年，Goldberg出版了专著搜索、优化和机

15、器学习中的遗传算法，该书全面地论述了遗传算法的基本原理及其应用，奠定了现代遗传算法的科学基础。第16页/共81页（5）L.Davis 1991年，Davis编辑出版了遗传算法手册一书，为推广和普及遗传算法的应用起到了重要的指导作用。（6）J.R.Koza 1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程的概念，并成功地将遗传编程的方法应用于人工智能、机器学习和符号处理等方面。第17页/共81页10.3.1 遗传算法的应用遗传算法的应用（1）函数优化。）函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性函数优化是遗传算法的经典应用领域，也是遗传算法进

16、行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。好的结果。（2 2）组合优化。）组合优化。随随着着问问题题的的增增大大，组组合合优优化化问问题题的的搜搜索索空空间间也也急急剧剧扩扩大大，采采用用传传统统的的优优化化方方法法很很难难得得到到最最优优解解。遗遗传传算算法法是是寻寻求求这这种种满满意意解解的的最最佳佳工工具具。例例如如，遗遗传传算算法法已已经经在在求求解解旅旅行行商商问问题题、背背包包问问题题、装

17、箱问题、图形划分问题等方面得到成功的应用。装箱问题、图形划分问题等方面得到成功的应用。第18页/共81页（3 3）生产调度问题）生产调度问题 在在很很多多情情况况下下，采采用用建建立立数数学学模模型型的的方方法法难难以以对对生生产产调调度度问问题题进进行行精精确确求求解解。在在现现实实生生产产中中多多采采用用一一些些经经验验进进行行调调度度。遗遗传传算算法法是是解解决决复复杂杂调调度度问问题题的的有有效效工工具具，在在单单件件生生产产车车间间调调度度、流流水水线线生生产产车车间间调调度度、生生产产规规划划、任任务务分分配配等等方方面面遗遗传传算算法法都都得得到到了了有有效效的的应用。应用。第1

18、9页/共81页（4 4）自动控制。）自动控制。在在自自动动控控制制领领域域中中有有很很多多与与优优化化相相关关的的问问题题需需要要求求解解，遗遗传传算算法法已已经经在在其其中中得得到到了了初初步步的的应应用用。例例如如，利利用用遗遗传传算算法法进进行行控控制制器器参参数数的的优优化化、基基于于遗遗传传算算法法的的模模糊糊控控制制规规则则的的学学习习、基基于于遗遗传传算算法法的的参参数数辨辨识识、基于遗传算法的神经网络结构的优化和权值学习等。基于遗传算法的神经网络结构的优化和权值学习等。第20页/共81页（5 5）机器人 例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构

19、优化和行为协调等方面得到研究和应用。（6 6）图像处理 遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。第21页/共81页（7）人工生命 人工生命是用计算机、机械等人工媒体模拟或构造出的具有生物系统特有行为的人造系统。人工生命与遗传算法有着密切的联系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。遗传算法为人工生命的研究提供了一个有效的工具。（8）遗传编程 遗传算法已成功地应用于人工智能、机器学习等领域的编程。第22页/共81页（9）机器学习 基于遗传算法的机器学习在很多领域都得到了应用。例如

20、，采用遗传算法实现模糊控制规则的优化，可以改进模糊系统的性能；遗传算法可用于神经网络连接权的调整和结构的优化；采用遗传算法设计的分类器系统可用于学习式多机器人路径规划。第23页/共81页10.4.1 遗传算法的构成要素遗传算法的构成要素（1 1）染色体编码方法）染色体编码方法 基基本本遗遗传传算算法法使使用用固固定定长长度度的的二二进进制制符符号号来来表表示示群群体体中中的的个个体体，其其等等位位基基因因是是由由二二值值符符号号集集0,10,1所所组组成。初始个体基因值可用均匀分布的随机值生成，如成。初始个体基因值可用均匀分布的随机值生成，如就可表示一个个体，该个体的染色体长度是就可表示一个个

21、体，该个体的染色体长度是1818。10.4 遗传算法的优化设计遗传算法的优化设计第24页/共81页（2 2）个个体体适适应应度度评评价价：基基本本遗遗传传算算法法与与个个体体适适应应度度成成正正比比的的概概率率来来决决定定当当前前群群体体中中每每个个个个体体遗遗传传到到下下一一代代群群体体中中的的概概率率多多少少。为为正正确确计计算算这这个个概概率率，要要求求所所有有个个体体的的适适应应度度必必须须为为正正数数或或零零。因因此此，必必须须先先确确定定由由目目标标函函数值数值J J到个体适应度到个体适应度f f之间的转换规则。之间的转换规则。第25页/共81页（3 3）遗传算子：基本遗传算法使用

22、下述三种遗传算）遗传算子：基本遗传算法使用下述三种遗传算子：子：选择运算选择运算:使用比例选择算子；使用比例选择算子；交叉运算交叉运算:使用单点交叉算子；使用单点交叉算子；变异运算变异运算:使用基本位变异算子或均匀变异算子。使用基本位变异算子或均匀变异算子。第26页/共81页（4 4）基本遗传算法的运行参数）基本遗传算法的运行参数 有下述有下述4 4个运行参数需要提前设定：个运行参数需要提前设定：MM：群群体体大大小小，即即群群体体中中所所含含个个体体的的数数量量，一一般般取取为为2010020100；GG：遗传算法的终止进化代数，一般取为：遗传算法的终止进化代数，一般取为1005001005

23、00；PcPc：交叉概率，一般取为：交叉概率，一般取为0.40.990.40.99；PmPm：变异概率，一般取为：变异概率，一般取为0.00010.10.00010.1。第27页/共81页 对对于于一一个个需需要要进进行行优优化化的的实实际际问问题题，一一般般可可按按下下述述步骤构造遗传算法：步骤构造遗传算法：第第一一步步：确确定定决决策策变变量量及及各各种种约约束束条条件件，即即确确定定出出个个体体的表现型的表现型X X和问题的解空间；和问题的解空间；第第二二步步：建建立立优优化化模模型型，即即确确定定出出目目标标函函数数的的类类型型及及数数学描述形式或量化方法；学描述形式或量化方法；10.

24、4.2 遗传算法的应用步骤遗传算法的应用步骤第28页/共81页第第三三步步：确确定定表表示示可可行行解解的的染染色色体体编编码码方方法法，即即确确定定出个体的基因型出个体的基因型x x及遗传算法的搜索空间；及遗传算法的搜索空间；第第四四步步：确确定定解解码码方方法法，即即确确定定出出由由个个体体基基因因型型x x到到个个体表现型体表现型X X的对应关系或转换方法；的对应关系或转换方法；第第五五步步：确确定定个个体体适适应应度度的的量量化化评评价价方方法法，即即确确定定出出由目标函数值到个体适应度的转换规则；由目标函数值到个体适应度的转换规则；第第六六步步：设设计计遗遗传传算算子子，即即确确定定

25、选选择择运运算算、交交叉叉运运算算、变异运算等遗传算子的具体操作方法。变异运算等遗传算子的具体操作方法。第第 七七 步步：确确 定定 遗遗 传传 算算 法法 的的 有有 关关 运运 行行 参参 数数，即即M,G,Pc,PmM,G,Pc,Pm等参数。等参数。第29页/共81页以上操作过程可以用图10-1来表示。图图10-1 遗传算法流程图遗传算法流程图 第30页/共81页利用遗传算法求利用遗传算法求RosenbrockRosenbrock函数的极大值函数的极大值10.5 遗传算法求函数极值遗传算法求函数极值第31页/共81页10.5.1 10.5.1 二进制编码遗传算法求函数极大值 求解该问题遗

26、传算法的构造过程：求解该问题遗传算法的构造过程：（1 1）确定决策变量和约束条件；）确定决策变量和约束条件；（2 2）建立优化模型；）建立优化模型；（3 3）确定编码方法）确定编码方法 第32页/共81页 用用长长度度为为1010位位的的二二进进制制编编码码串串来来分分别别表表示示两两个个决决策策变变量量x1,x2x1,x2。1010位位二二进进制制编编码码串串可可以以表表示示从从0 0到到10231023之之间间的的10241024个个不不同同的的数数，故故将将x x1 1,x,x2 2的的定定义义域域离离散散化化为为10231023个个均均等等的的区区域域，包包括括两两个个端端点点在在内内

27、共共有有10241024个不同的离散点。个不同的离散点。从从离离散散点点-2.0482.048到到离离散散点点2.048 2.048，分分别别对对应应于于从从0000000000(0)0000000000(0)到到1111111111(1023)1111111111(1023)之之间间的的二二进进制制编码。编码。第33页/共81页 将将x1,x2x1,x2分别表示的两个分别表示的两个1010位长的二进制编码串位长的二进制编码串连接在一起，组成一个连接在一起，组成一个2020位长的二进制编码串，它就构位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编成了这个函数优化问题的

28、染色体编码方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一一对应码方法，解空间和遗传算法的搜索空间就具有一一对应的关系。的关系。例如：例如：表示一个个体表示一个个体的基因型，其中前的基因型，其中前1010位表示位表示x1x1，后，后1010位表示位表示x2x2。第34页/共81页（4 4）确确定定解解码码方方法法：解解码码时时需需要要将将2020位位长长的的二二进进制制编编码码串串切切断断为为两两个个1010位位长长的的二二进进制制编编码码串串，然然后后分分别别将将它它们们转转换换为为对对应应的的十十进进制制整整数数代代码码，分分别别记记为为y y1 1和和y y2 2。依依据据个个

29、体体编编码码方方法法和和对对定定义义域域的的离离散散化化方方法法可可知知，将代码将代码y y转换为变量转换为变量x x的解码公式为的解码公式为 例如，对个体例如，对个体第35页/共81页 它由两个代码所组成它由两个代码所组成 上述两个代码经过解码后，可得到两个实际的值上述两个代码经过解码后，可得到两个实际的值（5 5）确定个体评价方法：由于）确定个体评价方法：由于RosenbrockRosenbrock函数的函数的值域总是非负的，并且优化目标是求函数的最大值，值域总是非负的，并且优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即故可将个体的适应度直接取为对应的目标函数值，

30、即第36页/共81页选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数（6 6）设设计计遗遗传传算算子子：选选择择运运算算使使用用比比例例选选择择算算子子，交交叉叉运运算算使使用用单单点点交交叉叉算算子子，变变异异运运算算使使用用基基本本位位变变异异算子。算子。（7 7）确确定定遗遗传传算算法法的的运运行行参参数数：群群体体大大小小M=80M=80，终终止止进进化化代代数数G=100G=100，交交叉叉概概率率Pc=0.60Pc=0.60，变变异异概概率率Pm=0.10Pm=0.10。上上述述七七个个步步骤骤构构成成了了用用于于求求函函数数极极大大值值的的优优化化计计算算基本遗传算法

31、。基本遗传算法。第37页/共81页 采用上述方法进行仿真，经过100步迭代，最佳样本为即当 时，Rosenbrock函数具有极大值，极大值为3905.9。仿真程序：chap5_1.m 第38页/共81页 遗传算法的优化过程是目标函数遗传算法的优化过程是目标函数J J和适应度函数和适应度函数F F的变化过程。的变化过程。由仿真结果可知，随着进化过程的进行，群体中由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的一些个体会越来越多，并且它们都集中在所求问题的最优点附近

32、，从而搜索到问题的最优解。的最优点附近，从而搜索到问题的最优解。第39页/共81页10.5.2 10.5.2 实数编码遗传算法求函数极大值实数编码遗传算法求函数极大值求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：（1 1）确定决策变量和约束条件；）确定决策变量和约束条件；（2 2）建立优化模型；）建立优化模型；（3 3）确确定定编编码码方方法法：用用2 2个个实实数数分分别别表表示示两两个个决决策策变变量量，分分别别将将的的定定义义域域离离散散化化为为从从离离散散点点-2.0482.048到离散点到离散点2.048的的SizeSize个实数。个实数。第40页/共81页（4 4）确

33、定个体评价方法：个体的适应度直接取为对应的目标函数值，即 选个体适应度的倒数作为目标函数 第41页/共81页（5 5）设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。（6）确定遗传算法的运行参数：群体大小M=500M=500，终止进化代数G=200G=200，交叉概率P Pc c=0.90=0.90，采用自适应变异概率即变异概率与适应度有关，适应度越小，变异概率越大。第42页/共81页 上 述 六 个 步 骤 构 成 了 用 于 求 函 数RosenbrockRosenbrock极大值的优化计算的实数编码遗传算法。十进制编码求函数Rosenbroc

34、kRosenbrock极大值。仿真程序见chap10_2.mchap10_2.m。仿真程序经过200200步迭代，最佳样本为即当 ，时，函数具有极大值，极大值为3880.33880.3。第43页/共81页10.6 基于遗传算法优化的RBF网络逼近10.6.1 遗传算法优化原理遗传算法优化原理 在在7.3节节的的RBF网网络络逼逼近近算算法法中中，网网络络权权值值、高高斯斯函函数数的的中中心心矢矢量量和和基基宽宽向向量量的的初初值值难难以以确确定定，如如果果这这些些参参数数选选择择不不当当，会会造造成成逼逼近近精精度度的的下下降降甚甚至至RBF网网络络的的发发散散。采采用用遗传算法可实现遗传算法

35、可实现RBF网络参数的优化。网络参数的优化。第44页/共81页 为获取满意的逼近精度，采用误差绝对值指标作为参数选择的最小目标函数。式中，为逼近的总步骤，为第 步RBF网络的逼近误差。在应用遗传算法时，为了避免参数选取范围过大，可以先按经验选取一组参数，然后再在这组参数的周围利用遗传算法进行设计，从而大大减少初始寻优的盲目性，节约计算量。第45页/共81页10.6.2 仿真实例 使用RBF网络逼近下列对象：在RBF网络中，网络输入信号为2个，即和 ，网络初始权值及高斯函数参数初始值通过遗传算法优化而得。第46页/共81页 遗传算法优化程序为遗传算法优化程序为chap10_3a.m，取逼近，取逼

36、近总步骤为，每一步的逼近误差由总步骤为，每一步的逼近误差由chap10_3b.m求求得。采用二进制编码方式，用长度为得。采用二进制编码方式，用长度为10位的二位的二进制编码串来分别表示向量进制编码串来分别表示向量b b、c c和和w w中的每个中的每个值。值。第47页/共81页 遗遗传传算算法法优优化化中中，取取样样本本个个数数为为Size=30，交交叉叉概概率率为为Pc=0.60，采采用用自自适适应应变变异异概概率率，即即适适应应度度越越小小，变异概率越大，取变异概率越大，取变异概率为变异概率为 取取用用于于优优化化的的RBF网网络络结结构构为为2-3-1，网网络络权权值值wj的的取取值值范

37、范围围为为-1,+1，高高斯斯函函数数基基宽宽向向量量的的取取值值范范围围为为0.1,3.0，高斯函数中心矢量的取值范围为，高斯函数中心矢量的取值范围为-3,+3。取。取则共有则共有12个参数需要优化。个参数需要优化。第48页/共81页 经过150代遗传算法进化，优化后的结果为：p=2.7732，2.6343，2.2630，1.8680，-0.0616，-0.7126，-0.3959，2.2669，-1.4047，-0.3099，0.7478，-0.3353。则RBF网络高斯基函数参数的初始值及权值的初始值为:第49页/共81页 RBF网网络络遗遗传传算算法法优优化化程程序序包包括括三三部部分

38、分，即即遗遗传传算算法法优优化化程程序序chap10_3a.m、RBF网网络络逼逼近近函函数数程程序序chap10_3b.m和和RBF网网络络逼逼近近测测试程序试程序chap10_3c.m。第50页/共81页 10.7 基于遗传算法的伺服系统静态摩擦参数辨识 摩擦分为静摩擦和动摩擦，它们之间的区别就是看两个物体之间的接触面有没有相对位移，分为三种情况：如果没有相对位移，也没有位移的趋势，则是没有摩擦力；如果没有相对位移，但是有位移的趋势，则为静摩擦力；如果有相对位移，则为动摩擦。摩擦现象是一种复杂的、非线性的、具有不确定性的自然现象。在高精度、超低速伺服系统中，由于非线性摩擦环节的存在，使系统

39、的动态及静态性能受到很大程度的影响，主要表现为低速时出现爬行现象，稳态时有较大的静差或出现极限环振荡。克服这一问题的有效方法是进行摩擦辨识，从而进行有效的补偿。第51页/共81页 10.7.1 伺服系统的静态摩擦模型 基于SISO的伺服系统可描述为 （10.7）其中 为转动惯量，为转角，为控制输入力矩，F为摩擦力矩。许多伺服系统在低速情况下存在静摩擦现象。静摩擦力矩与转速之间的稳态对应关系为：（10.8）其中 、为静态摩擦参数，为库仑摩擦，为静摩擦，为粘性摩擦系数，为切换速度。第52页/共81页 伺服系统在正反转动速度方向运行时，其静态摩擦力矩的静态参数通常为不同的值。当 时，静态参数的值为

40、、；当 ，静态参数的值为 、，表示如下：(10.9)由上式所确定的转速-摩擦力矩曲线称为Stribeck曲线。对于摩擦模型中的静态参数，通过恒速跟踪实验可以得到Stribeck曲线，再由Stribeck曲线，采用遗传算法可辨识出静态参数22。第53页/共81页 恒速跟踪实验为在线条件下运行，工程上很容易实现，而遗传算法是在离线情况下运行，因而本方法具有较强的实际工程价值。10.7.2 静摩擦模型Stribeck曲线的获取 在静态摩擦条件下，由式（10.7）可知，。由于u可测得，采用一组恒速跟踪，可获得一组相应的控制输入信号和静态摩擦力矩，从而获得Stribeck曲线。具体方法为：取闭环系统的一

41、组恒定转速序列 作为速度指令信号，通过采用PD控制律，实现被控对象精确的速度跟踪，得到相应的控制力矩序列 ，从而获得一组相应的静态摩擦力矩序列。PD控制律为：（10.10）第54页/共81页 10.7.3 基于遗传算法的静态摩擦参数辨识 取待辨识静态摩擦参数向量为个体，遗传算法的每步迭代得到静态摩擦参数的辨识值为：，（10.11）其中M为种群规模。由下式可得到相应的摩擦力矩辨识值：（10.12）第55页/共81页 辨识误差为：，其中值根据所建立的Stribeck曲线得到。取目标函数为：（10.13）选择个体适应度函数如下：或 ，（10.14）第56页/共81页 采用十进制浮点编码格式，选择操作

42、采取保存最优个体的随机采样选择方法，交叉操作采用均匀交叉算子，交叉概率 ，变异操作采用高斯变异算子，变异概率随进化代数自适应调整，即，其中 g当前遗传代数。遗传算法的步骤如下：Step 1.置进化代数计数器为 ，随机产生初始化种群 ；Step 2.计算个体适应度 ，；Step 3.判断是否达到最大进化代数，若是，则算法终止，否则，转step 4；Step 4.经过选择操作，产生新一代种群 ；Step 5.以概率 进行交叉操作；Step 6.以概率 进行个体变异操作；Step 7.，转step 2；第57页/共81页 一旦辨识得到的参数估计值，便可以设计摩擦力矩的补偿环节，实现对系统的摩擦进行补

43、偿，基于摩擦力矩补偿的控制系统描述为：（10.15）10.7.4 仿真实例 被控对象为（10.7）式，取 ，控制律取PD控制。参数辨识的仿真分以下两步实现。仿真之一：Stribeck曲线的测试 恒速跟踪时，为静态摩擦，实际系统的摩擦模型取（10.9）式，被控对象为带有静态摩擦模型式（10.7）的实际对象，取 ，。取速度信号 作为指令信号，共41个速度指令信号。针对每个指令信号，采用PD控制律，取 ，。仿真结果如图10-8至10-10所示。仿真结束后，将所得到的静摩擦力矩估计值保存在文件Fi_file.mat中。第58页/共81页图10-8 恒速斜波跟踪（速度指令为1.0时）第59页/共81页图

44、10-9 Stribeck曲线的实际值与测试值的比较 第60页/共81页图10-10 Stribeck曲线的辨识误差第61页/共81页 仿真之二：遗传算法的静态摩擦参数辨识 首先将仿真之一“Stribeck曲线设计”所得到的摩擦力矩估计值 从文件Fi_file.mat中调入，作为实际系统的静摩擦力矩的估计值。恒速跟踪时为静态摩擦。取速度信号 作为指令信号，共41个速度指令信号。针对每个指令信号，采用PD控制律，取 ，。在遗传算法仿真中，取种群规模，最大遗传代数 。参数搜索范围为 ，静态摩擦模型取（10.9）式，将遗传算法设计所得到了静摩擦力矩与实际摩擦力矩比较得到目标函数值。当运行到最大遗传代

45、数 时，目标函数值为 。第62页/共81页遗传算法的辨识过程及辨识曲线如图10-11和10-12所示，实际值与辨识值比较的仿真结果如表10-1所示。表10-1 静态摩擦参数实际值与辨识值的比较真实值0.150.600.020.050.200.700.030.05辨识值0.15030.63430.01910.0499 0.20010.730.02950.0506第63页/共81页图10-11 目标函数值变化曲线局部放大图第64页/共81页图10-12 辨识Stribeck曲线与实际 Stribeck曲线第65页/共81页 10.7.5 基于摩擦模型补偿的伺服系统控制 为了验证基于遗传算法的伺服系

46、统静态摩擦参数辨识的效果，将PD控制与基于静态摩擦模型补偿的PD控制进行比较，采用低速正弦信号 作为位置指令。在PD控制中，取 ，。采用手动转换开关实现两种控制方法的切换，一种为只采用PD控制，另一种为基于摩擦补偿的PD控制，仿真结果如图10-13和10-14所示。在图10-13中，由于存在静摩擦，造成了位置跟踪出现了“平顶”现象。第66页/共81页图10-13 未加补偿的PD控制位置跟踪第67页/共81页图10-14 基于摩擦补偿的PD控制位置跟踪第68页/共81页 10.8 基于遗传算法的TSP问题优化 在第8.5节已经对旅行商问题进行了描述。遗传算法由于其全局搜索的特点，在解决TSP问题

47、中有明显的优势。10.8.1 TSP问题的编码 设 是由城市i和城市j之间的距离组成的距离矩阵，旅行商问题就是求出一条通过所有城市且每个城市只通过一次的具有最短距离的回路。第69页/共81页 在旅行商问题的各种求解方法中，描述旅行路线的方法主要有如下两种：（1）巡回旅行路线经过的连接两个城市的路线的顺序排列；（2）巡回旅行路线所经过的各个城市的顺序排列。大多数求解旅行商问题的遗传算法是以后者为描述方法的，它们大多采用所遍历城市的顺序来表示各个个体的编码串，其等位基因为N个整数值或N个记号。以城市的遍历次序作为遗传算法的编码，目标函数取路径长度。在群体初始化、交叉操作和变异操作中考虑TSP问题的

48、合法性约束条件（即对所有的城市做到不重不漏）。第70页/共81页 10.8.2 TSP问题的遗传算法设计 采用遗传算法进行路径优化，分为以下几步：第一步：参数编码和初始群体设定 一般来说遗传算法对解空间的编码大多采用二进制编码形式，但对于TSP一类排序问题，采用对访问城市序列进行排列组合的方法编码，即某个巡回路径的染色体个体是该巡回路径的城市序列。针对TSP问题，编码规则通常是N取进制编码，即每个基因仅从1到N的整数里面取一个值，每个个体的长度为N，N为城市总数。定义一个s行t列的pop矩阵来表示群体，t为城市个数N+1，即N+1，s为样本中个体数目。针对30个城市的TSP问题，t取值31，第

49、71页/共81页 即矩阵每一行的前30个元素表示经过的城市编号，最后一个元素表示经过这些城市要走的距离。参数编码和初始群体设定程序为：pop=zeros(s,t);for i=1:s pop(i,1:t-1)=randperm(t-1);end 第二步：计算路径长度的函数设计 在TSP的求解中，用距离的总和作为适应度函数，来衡量求解结果是否最优。将POP矩阵中每一行表示经过的距离的最后一个元素作为路径长度。第72页/共81页 两个城市m和n间的距离为：（10.16）用于计算路径长度的程序为chap10_1dis.m。通过样本的路径长度可以得到目标函数和自适应度函数。根据t的定义，两两城市组合数

50、共有t-2组，则目标函数为：（10.17）自适应度函数取目标函数的倒数，即：（10.18）第73页/共81页 第三步：计算选择算子 选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估基础上。仿真中采用最优保存方法，即将群体中适应度最大的c个个体直接替换适应度最小的c个个体。选择算子函数为chap10_7select.m。仿真中，取 。第四步：计算交叉算子 交叉算子在遗传算法中起着核心的作用，它是指将个体进行两两配对，并以交叉概率将配对的父代个体加以替换重组而生成新个体的操作。仿真中，取 。有序交叉法实现的步骤是:第74页/共81页 有序交叉法实现的步骤是:步骤 1