智能控制(第三版)chap10 智能算法及其应用2资料课件

第10章 智能算法及其应用1.随着优化理论的发展，一些智能算法成为解决传随着优化理论的发展，一些智能算法成为解决传统系统辨识问题的新方法，如统系统辨识问题的新方法，如遗传算法、遗传算法、蚁群算蚁群算法、法、粒子群算法、差分进化算法粒子群算法、差分进化算法等。等。2.都是通过都是通过模拟揭示自然现象模拟揭示自然现象来实现来实现的的。3.本章介绍本章介绍遗传算法遗传算法的基本概念和方法。的基本概念和方法。第10章 智能算法及其应用随着优化理论的发展，一些智能算法2 10.1 遗传算法的基本原理 遗遗传传算算法法简简称称GAGA（Genetic Genetic AlgorithmsAlgorithms）是是19621962年年由由美美国国HollandHolland教教授授提提出出的的模模拟拟自自然然界界生生物物进进化化机机制制的一种并行的一种并行随机搜索随机搜索最优化方法。最优化方法。遗遗传传算算法法是是以以达达尔尔文文的的自自然然选选择择学学说说为为基基础础,包包括括以下三个方面：以下三个方面：2 10.1 遗传算法的基本原理3（1 1）遗遗传传：亲亲代代把把生生物物信信息息交交给给子子代代，子子代代总总是是和和亲亲代代具具有有相相同同或或相相似似的的性性状状。生生物物有有了了这这个个特特征征，物物种种才能稳定存在。才能稳定存在。（2 2）变变异异：亲亲代代和和子子代代之之间间以以及及子子代代的的不不同同个个体体之之间间的的差差异异，称称为为变变异异。变变异异是是随随机机发发生生的的，变变异异的的选选择择和积累是生命多样性的根源。和积累是生命多样性的根源。（3 3）生生存存斗斗争争和和适适者者生生存存：具具有有适适应应性性变变异异的的个个体体被被保保留留下下来来，不不具具有有适适应应性性变变异异的的个个体体被被淘淘汰汰，通通过过一一代代代代的的生生存存环环境境的的选选择择作作用用，性性状状逐逐渐渐与与祖祖先先有有所所不不同，演变为新的物种。同，演变为新的物种。3（1）遗传：亲代把生物信息交给子代，子代总是和亲代具有相同4遗遗传传算算法法引引入入“优优胜胜劣劣汰汰，适适者者生生存存”的的生生物物进进化化机制，按所选择的适应度函数对个体进行筛选。机制，按所选择的适应度函数对个体进行筛选。适适应应度度高高的的个个体体被被保保留留下下来来，组组成成新新的的群群体体，新新的的群体既继承了上一代的信息，又优于上一代。群体既继承了上一代的信息，又优于上一代。周周而而复复始始，使使群群体体中中个个体体适适应应度度不不断断提提高高，直直到到满满足一定的条件。足一定的条件。遗传算法可并行处理，得到全局最优解。遗传算法可并行处理，得到全局最优解。4遗传算法引入“优胜劣汰，适者生存”的生物进化机制，按所选择5遗传算法的基本操作为：遗传算法的基本操作为：（1）复制（）复制（Reproduction Operator）从旧种群中选择从旧种群中选择生命力强生命力强的个体产生新种群。的个体产生新种群。通通过过随随机机方方法法实实现现。若若设设定定复复制制概概率率阈阈值值为为40%，当当产产生生的的随随机机数数在在0.41之之间间时时，该该个个体体被被复复制制到到子子代，否则该个体被淘汰。代，否则该个体被淘汰。5遗传算法的基本操作为：6（2 2）交叉（）交叉（Crossover OperatorCrossover Operator）通过两个染色体的通过两个染色体的交换组合交换组合产生新的优良个体。产生新的优良个体。任任选选两两个个染染色色体体，随随机机选选择择一一点点或或多多点点交交换换点点位位置置；交交换换双双亲亲染染色色体体在在交交换换点点右右边边的的部部分分，即即可可得得到到两两个新的染色体数字串。个新的染色体数字串。有一点交叉、多点交叉等。有一点交叉、多点交叉等。一点交叉：染色体断点仅有一处，例：一点交叉：染色体断点仅有一处，例：6（2）交叉（Crossover Operator）7一点交叉示意图一点交叉示意图7一点交叉示意图8（3 3）变异）变异(Mutation Operator)(Mutation Operator)模模拟拟基基因因突突变变现现象象，以以小小概概率率随随机机改改变变遗遗传传基基因因的值。的值。在在染染色色体体以以二二进进制制编编码码的的系系统统中中，它它随随机机地地将将染染色体的某一个基因位由色体的某一个基因位由1 1变为变为0 0，或由，或由0 0变为变为1 1。优点：可使进化过程逃离局部最优解。优点：可使进化过程逃离局部最优解。1011 0011 1011 10118（3）变异(Mutation Operator)1011 910.2 10.2 遗传算法的特点遗传算法的特点（1 1）对对参参数数编编码码进进行行操操作作，而而非非对对参参数数本本身身。因因此此，在在参参数数优优化化过过程程中中可可借借鉴鉴生生物物学学中中染染色色体体和和基基因因等等概概念，模仿生物进化等机理；念，模仿生物进化等机理；（2 2）同同时时使使用用多多个个搜搜索索点点的的搜搜索索信信息息。传传统统方方法法往往往往是是从从解解空空间间的的单单个个初初始始点点开开始始最最优优解解的的迭迭代代搜搜索索过过程程，效效率率不不高高，有有时时甚甚至至会会陷陷入入局局部部最最优优解解而而停停滞滞不不前前。以群体为基础进行搜索，效率高。以群体为基础进行搜索，效率高。910.2 遗传算法的特点（1）对参数编码进行操作，而非10（3 3）遗传算法）遗传算法直接以目标函数直接以目标函数作为搜索信息，无需目作为搜索信息，无需目标函数的标函数的导数值导数值等其他一些辅助信息。适用于目标函等其他一些辅助信息。适用于目标函数数无法求导数或导数不存在无法求导数或导数不存在的优化问题，或者组合优的优化问题，或者组合优化问题等。化问题等。（4 4）遗传算法使用概率搜索技术。各种操作：选择、）遗传算法使用概率搜索技术。各种操作：选择、交叉、变异等都是以概率的方式进行的。交叉、变异等都是以概率的方式进行的。（5 5）遗传算法在解空间进行高效）遗传算法在解空间进行高效启发式搜索启发式搜索，而非盲，而非盲目地穷举或完全随机搜索；目地穷举或完全随机搜索；10（3）遗传算法直接以目标函数作为搜索信息，无需目标函数的11（6 6）遗传算法对于待寻优的函数基本无限制，它）遗传算法对于待寻优的函数基本无限制，它既不既不要求函数连续，也不要求函数可微要求函数连续，也不要求函数可微，既可以是数学解，既可以是数学解析式所表示的析式所表示的显函数显函数，又可以是映射矩阵甚至是神经，又可以是映射矩阵甚至是神经网络的网络的隐函数隐函数，因而应用范围较广；，因而应用范围较广；（7）遗传算法具有）遗传算法具有并行计算并行计算的特点，因而可通过大规的特点，因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的模并行计算来提高计算速度，适合大规模复杂问题的优化。优化。11（6）遗传算法对于待寻优的函数基本无限制，它既不要求函数1210.3 遗传算法的算法的发展及展及应用用 自学。自学。1210.3 遗传算法的发展及应用1310.4.1 遗传算法的构成要素遗传算法的构成要素（1 1）染色体编码方法）染色体编码方法）染色体编码方法）染色体编码方法 基基基基本本本本遗遗遗遗传传传传算算算算法法法法使使使使用用用用固固固固定定定定长长长长度度度度的的的的二二二二进进进进制制制制符符符符号号号号来来来来表表表表示示示示群群群群体体体体中中中中的的的的个个个个体体体体，其其其其等等等等位位位位基基基基因因因因是是是是由由由由二二二二值值值值符符符符号号号号集集集集0,0,11所所所所组组组组成成成成。初始个体初始个体初始个体初始个体基因值基因值基因值基因值可用均匀分布的随机值生成，如可用均匀分布的随机值生成，如可用均匀分布的随机值生成，如可用均匀分布的随机值生成，如表示一个个体，该个体的表示一个个体，该个体的表示一个个体，该个体的表示一个个体，该个体的染色体染色体染色体染色体长度是长度是长度是长度是1818。10.4 10.4 遗传算法的设计遗传算法的设计1310.4.1 遗传算法的构成要素10.4 遗传算法的14（2 2）个个个个体体体体适适适适应应应应度度度度评评评评价价价价：每每每每个个个个个个个个体体体体的的的的适适适适应应应应度度度度代代代代表表表表了了了了其其其其遗遗遗遗传传传传到到到到下下下下一一一一代代代代的的的的概概概概率率率率。为为为为正正正正确确确确计计计计算算算算这这这这个个个个概概概概率率率率，要要要要求求求求所所所所有有有有个个个个体体体体的的的的适适适适应应应应度度度度必必必必须须须须为为为为正正正正数数数数或或或或零零零零。因因因因此此此此，必必必必须须须须先先先先确确确确定定定定由由由由目目目目标标标标函数值函数值函数值函数值J J到个体适应度到个体适应度到个体适应度到个体适应度f f之间的转换规则之间的转换规则之间的转换规则之间的转换规则。14（2）个体适应度评价：每个个体的适应度代表了其遗传到下一15（3 3）遗传算子：三种基本遗传算子包括）遗传算子：三种基本遗传算子包括）遗传算子：三种基本遗传算子包括）遗传算子：三种基本遗传算子包括 选择运算：使用比例选择算子；选择运算：使用比例选择算子；选择运算：使用比例选择算子；选择运算：使用比例选择算子；交叉运算：使用单点交叉算子；交叉运算：使用单点交叉算子；交叉运算：使用单点交叉算子；交叉运算：使用单点交叉算子；变异运算：使用基本位变异算子或均匀变异算子。变异运算：使用基本位变异算子或均匀变异算子。变异运算：使用基本位变异算子或均匀变异算子。变异运算：使用基本位变异算子或均匀变异算子。15（3）遗传算子：三种基本遗传算子包括16（4 4）基本遗传算法的运行参数）基本遗传算法的运行参数）基本遗传算法的运行参数）基本遗传算法的运行参数 有下述有下述有下述有下述4 4个运行参数需要提前设定：个运行参数需要提前设定：个运行参数需要提前设定：个运行参数需要提前设定：MM：群群群群体体体体大大大大小小小小，即即即即群群群群体体体体中中中中所所所所含含含含个个个个体体体体的的的的数数数数量量量量，一一一一般般般般取取取取为为为为2010020100；GG：遗传算法的终止进化代数，一般取为：遗传算法的终止进化代数，一般取为：遗传算法的终止进化代数，一般取为：遗传算法的终止进化代数，一般取为100500100500；PcPc：交叉概率，一般取为：交叉概率，一般取为：交叉概率，一般取为：交叉概率，一般取为0.40.990.40.99；PmPm：变异概率，一般取为：变异概率，一般取为：变异概率，一般取为：变异概率，一般取为0.00010.10.00010.1。16（4）基本遗传算法的运行参数17构造遗传算法解决优化问题的步骤：构造遗传算法解决优化问题的步骤：构造遗传算法解决优化问题的步骤：构造遗传算法解决优化问题的步骤：S1S1：确确确确定定定定决决决决策策策策变变变变量量量量及及及及各各各各种种种种约约约约束束束束条条条条件件件件，即即即即确确确确定定定定个个个个体体体体的的的的表表表表现现现现形式和问题的解空间；形式和问题的解空间；形式和问题的解空间；形式和问题的解空间；S2S2：建建建建立立立立优优优优化化化化模模模模型型型型，即即即即确确确确定定定定目目目目标标标标函函函函数数数数的的的的描描描描述述述述形形形形式式式式或或或或量量量量化化化化方法；方法；方法；方法；S3S3：确确确确定定定定表表表表示示示示可可可可行行行行解解解解的的的的染染染染色色色色体体体体编编编编码码码码方方方方法法法法，即即即即确确确确定定定定个个个个体体体体的的的的基因形式及遗传算法的基因形式及遗传算法的基因形式及遗传算法的基因形式及遗传算法的搜索空间搜索空间搜索空间搜索空间；10.4.2 遗传算法的应用步骤遗传算法的应用步骤17构造遗传算法解决优化问题的步骤：10.4.2 遗传算法18S4S4：确确确确定定定定个个个个体体体体适适适适应应应应度度度度的的的的量量量量化化化化评评评评价价价价方方方方法法法法，即即即即确确确确定定定定由由由由目目目目标标标标函数值函数值函数值函数值J(x)J(x)到个体适应度函数到个体适应度函数到个体适应度函数到个体适应度函数F(x)F(x)的转换规则；的转换规则；的转换规则；的转换规则；S5S5：设设设设计计计计遗遗遗遗传传传传算算算算子子子子，即即即即确确确确定定定定选选选选择择择择、交交交交叉叉叉叉、变变变变异异异异运运运运算算算算等等等等遗传算子的具体操作方法；遗传算子的具体操作方法；遗传算子的具体操作方法；遗传算子的具体操作方法；S6S6：确确确确定定定定遗遗遗遗传传传传算算算算法法法法的的的的有有有有关关关关运运运运行行行行参参参参数数数数，即即即即M,M,G,G,Pc,Pc,PmPm等参数；等参数；等参数；等参数；S7S7：确确确确定定定定解解解解码码码码方方方方法法法法，即即即即确确确确定定定定出出出出由由由由个个个个体体体体表表表表现现现现形形形形式式式式到到到到个个个个体体体体基因的对应关系或转换方法。基因的对应关系或转换方法。基因的对应关系或转换方法。基因的对应关系或转换方法。18S4：确定个体适应度的量化评价方法，即确定由目标函数值J19遗传算法流程图遗传算法流程图 参数解码计算适应度复制交叉变异满足要求?遗传操作新种群寻优结束是是否否种群编码19遗传算法流程图 参数解码计算适应度复制满足要求?遗传操作20利用遗传算法求利用遗传算法求利用遗传算法求利用遗传算法求RosenbrockRosenbrock函数的极大值函数的极大值函数的极大值函数的极大值10.5 遗传算法求函数极大值遗传算法求函数极大值20利用遗传算法求Rosenbrock函数的极大值10.5 21函数函数f(x1,x2)的三维图如图的三维图如图10-2所示，可以所示，可以发现该函数在指定的定义域上发现该函数在指定的定义域上有两个有两个靠靠近近的极的极值值点点，即一个全局极大值和一个局部，即一个全局极大值和一个局部极大值。极大值。因此，采用寻优算法求极大值时，需要避因此，采用寻优算法求极大值时，需要避免陷入局部最优解。免陷入局部最优解。21函数f(x1,x2)的三维图如图10-2所示，可以发现22函数函数f(x1,x2)的三维图的三维图22函数f(x1,x2)的三维图23采用遗传算法求解该问题的构造过程：采用遗传算法求解该问题的构造过程：采用遗传算法求解该问题的构造过程：采用遗传算法求解该问题的构造过程：（1 1）确定决策变量和约束条件；）确定决策变量和约束条件；）确定决策变量和约束条件；）确定决策变量和约束条件；（2 2）建立优化模型；）建立优化模型；）建立优化模型；）建立优化模型；（3 3）确定编码方法。）确定编码方法。）确定编码方法。）确定编码方法。10.5.1 二进制编码遗传算法求函数极大值二进制编码遗传算法求函数极大值23采用遗传算法求解该问题的构造过程：10.5.1 二进制24用用用用长长长长度度度度为为为为1010位位位位的的的的二二二二进进进进制制制制编编编编码码码码来来来来分分分分别别别别表表表表示示示示两两两两个个个个决决决决策策策策变变变变量量量量x x1 1,x,x2 2。将将将将x x1 1,x x2 2的的的的定定定定义义义义域域域域离离离离散散散散化化化化为为为为10231023个个个个均均均均等等等等的的的的区区区区域域域域，共共共共获得获得获得获得10241024个离散点。个离散点。个离散点。个离散点。离散点分别与取值区间的二进制编码相对应。离散点分别与取值区间的二进制编码相对应。离散点分别与取值区间的二进制编码相对应。离散点分别与取值区间的二进制编码相对应。0000000000(0)0000000000(0)1111111111(1023)1111111111(1023)-2.048-2.0482.0482.04824用长度为10位的二进制编码来分别表示两个决策变量x1,25将将将将x x1 1,x,x2 2的编码串接在一起，得到的编码串接在一起，得到的编码串接在一起，得到的编码串接在一起，得到2020位长的参数编码。位长的参数编码。位长的参数编码。位长的参数编码。这就是该函数优化问题的染色体编码。这就是该函数优化问题的染色体编码。这就是该函数优化问题的染色体编码。这就是该函数优化问题的染色体编码。解空间和搜索空间具有一一对应关系。解空间和搜索空间具有一一对应关系。解空间和搜索空间具有一一对应关系。解空间和搜索空间具有一一对应关系。例如：某个体的基因型如下例如：某个体的基因型如下例如：某个体的基因型如下例如：某个体的基因型如下其中前其中前其中前其中前1010位表示位表示位表示位表示x x1 1，后，后，后，后1010位表示位表示位表示位表示x x2 2。25将x1,x2的编码串接在一起，得到20位长的参数编码。26（4 4）解解解解码码码码时时时时，将将将将2020位位位位长长长长的的的的二二二二进进进进制制制制编编编编码码码码串串串串切切切切断断断断为为为为两两两两个个个个1010位位位位长长长长的的的的二二二二进进进进制制制制编编编编码码码码串串串串，然然然然后后后后分分分分别别别别将将将将它它它它们们们们转转转转换换换换为为为为对对对对应应应应的十进制整数代码，分别记为的十进制整数代码，分别记为的十进制整数代码，分别记为的十进制整数代码，分别记为y y1 1和和和和y y2 2。依依依依据据据据前前前前面面面面的的的的方方方方法法法法，将将将将代代代代码码码码y yi i转转转转换换换换为为为为变变变变量量量量x xi i的的的的解解解解码码码码公公公公式式式式为：为：为：为：例如，对染色体例如，对染色体例如，对染色体例如，对染色体x x：0000110111 11011100010000110111 1101110001，切断后，切断后，切断后，切断后得到得到得到得到y y1 1=55=55，y y2 2=881=881。解码后，得到。解码后，得到。解码后，得到。解码后，得到x x1 1=-1.828=-1.828，x x2 2=1.476=1.476。26（4）解码时，将20位长的二进制编码串切断为两个10位长27（5 5）确定）确定）确定）确定个体评价个体评价个体评价个体评价方法：由于优化目标是求函数的方法：由于优化目标是求函数的方法：由于优化目标是求函数的方法：由于优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函最大值，故可将个体的适应度直接取为对应的目标函最大值，故可将个体的适应度直接取为对应的目标函最大值，故可将个体的适应度直接取为对应的目标函数值，即数值，即数值，即数值，即选择个体适应度的倒数作为目标函数选择个体适应度的倒数作为目标函数选择个体适应度的倒数作为目标函数选择个体适应度的倒数作为目标函数27（5）确定个体评价方法：由于优化目标是求函数的最大值，故28（6 6）设计遗传算子：）设计遗传算子：）设计遗传算子：）设计遗传算子：选择运算使用选择运算使用选择运算使用选择运算使用比例选择算子比例选择算子比例选择算子比例选择算子，交，交，交，交叉运算使用叉运算使用叉运算使用叉运算使用单点交叉算子单点交叉算子单点交叉算子单点交叉算子，变异运算使用，变异运算使用，变异运算使用，变异运算使用基本位变异基本位变异基本位变异基本位变异算子算子算子算子。（7 7）确确确确定定定定遗遗遗遗传传传传算算算算法法法法的的的的运运运运行行行行参参参参数数数数：群群群群体体体体大大大大小小小小M=80M=80，终终终终止止止止 进进进进 化化化化 代代代代 数数数数 G=100G=100，交交交交 叉叉叉叉 概概概概 率率率率 Pc=0.60Pc=0.60，变变变变 异异异异 概概概概 率率率率Pm=0.10Pm=0.10。上上上上述述述述七七七七个个个个步步步步骤骤骤骤构构构构成成成成了了了了用用用用于于于于求求求求函函函函数数数数极极极极大大大大值值值值的的的的优优优优化化化化计计计计算算算算基本遗传算法。基本遗传算法。基本遗传算法。基本遗传算法。28（6）设计遗传算子：选择运算使用比例选择算子，交叉运算使29即当即当x1=-2.0480，x2=-2.0480时，时，Rosenbrock函函数具有极大值，极大值为数具有极大值，极大值为3905.9。仿真程序：仿真程序：chap10_1.m 采用上述方法进行仿真，经过采用上述方法进行仿真，经过采用上述方法进行仿真，经过采用上述方法进行仿真，经过100100步迭代，最佳样本为步迭代，最佳样本为步迭代，最佳样本为步迭代，最佳样本为书中程序出错！29即当x1=-2.0480，x2=-2.0480时，Ros%Generic Algorithm for function f(x1,x2)optimumclear all;close all;%ParametersSize=80;%种群大小G=100;%遗传代数CodeL=10;%每个变量的染色体长度（2进制编码）umax=2.048;%两个变量的取值范围是相同的umin=-2.048;%初始种群的染色体E=round(rand(Size,2*CodeL);for k=1:1:G time(k)=k;%Generic Algorithm for functio for s=1:1:Size m=E(s,:);y1=0;y2=0;m1=m(1:1:CodeL);%取第1个变量x1的染色体 for i=1:1:CodeL y1=y1+m1(i)*2(i-1);%求对应的十进制数 end x1=(umax-umin)*y1/1023+umin;%解码，求变量x1的值 m2=m(CodeL+1:1:2*CodeL);%取第2个变量x2的染色体 for i=1:1:CodeL y2=y2+m2(i)*2(i-1);end x2=(umax-umin)*y2/1023+umin;F(s)=100*(x12-x2)2+(1-x1)2;%目标函数值 end for s=1:1:Size智能控制(第三版)chap10 智能算法及其应用2资料课件智能控制(第三版)chap10 智能算法及其应用2资料课件34 遗传算法的优化过程是目标函数遗传算法的优化过程是目标函数遗传算法的优化过程是目标函数遗传算法的优化过程是目标函数J J和适应度函数和适应度函数和适应度函数和适应度函数F F的变化过程。的变化过程。的变化过程。的变化过程。由仿真结果可知，随着进化过程的进行，由仿真结果可知，随着进化过程的进行，由仿真结果可知，随着进化过程的进行，由仿真结果可知，随着进化过程的进行，群体中群体中群体中群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高适应度较低的一些个体被逐渐淘汰掉，而适应度较高适应度较低的一些个体被逐渐淘汰掉，而适应度较高适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的一些个体会越来越多，并且它们都集中在所求问题的一些个体会越来越多，并且它们都集中在所求问题的一些个体会越来越多，并且它们都集中在所求问题的最优点附近的最优点附近的最优点附近的最优点附近，从而搜索到问题的最优解。，从而搜索到问题的最优解。，从而搜索到问题的最优解。，从而搜索到问题的最优解。34 遗传算法的优化过程是目标函数J和适应度函3510.5.2 10.5.2 实数编码遗传算法求函数极大值实数编码遗传算法求函数极大值求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：（1 1）确定决策变量和约束条件；）确定决策变量和约束条件；（2 2）建立优化模型；）建立优化模型；（3 3）确确定定编编码码方方法法：用用2 2个个实实数数分分别别表表示示两两个个决决策策变变量量x1,x2，分分别别将将x1,x2的的定定义义域域离离散散化化为为从从离离散散点点-2.0482.048到到离离散散点点2.048的的SizeSize个个实实数。数。3510.5.2 实数编码遗传算法求函数极大值36（4 4）确定个体评价方法：）确定个体评价方法：个个体体的的适适应应度度直直接接取取为为对对应应的的目目标标函函数数值值，即即选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数36（4）确定个体评价方法：选个体适应度的倒数作为目标函数37（5 5）设设计计遗遗传传算算子子：选选择择运运算算使使用用比比例例选选择择算算子子，交交叉叉运运算算使使用用单单点点交交叉叉算算子子，变变异异运运算算使使用用基基本本位位变变异异算子。算子。（6）确定遗传算法的运行参数：群体大小）确定遗传算法的运行参数：群体大小M=500M=500，终，终止进化代数止进化代数G=200G=200，交叉概率，交叉概率P Pc c=0.90=0.90，采用自适应变，采用自适应变异概率异概率即变异概率与适应度有关，即变异概率与适应度有关，适应度越小，变异概率越适应度越小，变异概率越大大。37（5）设计遗传算子：选择运算使用比例选择算子，交叉运算使38上述六个步骤构成了用于求函数上述六个步骤构成了用于求函数Rosenbrock极大值极大值的实数编码遗传算法，仿真程序见的实数编码遗传算法，仿真程序见chap10_2.m。%*Step 3:交叉操作交叉操作*Pc=0.90;%交叉概率交叉概率 for i=1:2:(Size-1)temp=rand;if Pctemp alfa=rand;TempE(i,:)=alfa*E(i+1,:)+(1-alfa)*E(i,:);%交叉操作交叉操作 TempE(i+1,:)=alfa*E(i,:)+(1-alfa)*E(i+1,:);end end第i+1个个体与第i个个体进行交叉38上述六个步骤构成了用于求函数Rosenbrock极大值的%*Step 4:变异操作变异操作*Pm=0.10-1:1:Size*(0.01)/Size;%自适应变异概率自适应变异概率 Pm_rand=rand(Size,CodeL);Dif=(MaxX-MinX);for i=1:1:Size for j=1:1:CodeL if Pm(i)Pm_rand(i,j)%Mutation Condition TempE(i,j)=MinX(j)+Dif(j)*rand;%变异操作变异操作 end end end变异操作：随机变成另一个数了%*Step 4:变异操作*4010.6 基于遗传算法优化的RBF网络逼近10.6.1 遗传算法优化原理遗传算法优化原理 在在7.3节节的的RBF网网络络逼逼近近算算法法中中，网网络络权权值值W、高高斯斯函函数数的的中中心心矢矢量量C和和基基宽宽向向量量B的的初初值值难难以以确确定定，如如果果这这些些参参数数选选择择不不当当，会会造造成成逼逼近近精精度度的的下下降降甚甚至至RBF网网络络的的发发散散。采采用用遗遗传传算算法法可可实实现现RBF网网络络参参数数初初始始值值的的优化。优化。4010.6 基于遗传算法优化的RBF网络逼近10.6.141 为为获获取取满满意意的的逼逼近近精精度度，采采用用误误差差绝绝对对值值指指标标作作为为参数选择的最小目标函数。参数选择的最小目标函数。式式中中，为为逼逼近近的的总总步步骤骤，为为第第 步步RBF网网络络的的逼逼近近误误差。差。在在应应用用遗遗传传算算法法时时，为为了了避避免免参参数数选选取取范范围围过过大大，可可以以先先按按经经验验选选取取一一组组参参数数，然然后后再再在在这这组组参参数数的的周周围围利利用用遗遗传传算算法法进进行行设设计计，从从而而大大大大减减少少初初始始寻寻优优的的盲目性，节约计算量。盲目性，节约计算量。41 为获取满意的逼近精度，采用误差绝对值指标作为参数4210.6.2 仿真实例仿真实例 使用使用RBF网络逼近下列对象：网络逼近下列对象：在在RBF网络中，网络中，网络输入信号为网络输入信号为2个，即个，即u(k)和和y(k)，网网络络初初始始权权值值及及高高斯斯函函数数参参数数初初始始值值通过遗传算法优化而得。通过遗传算法优化而得。4210.6.2 仿真实例 在RBF网络中，网络输入信号43 遗传算法优化程序为遗传算法优化程序为chap10_3a.m，取逼近，取逼近总步骤为总步骤为N=500N=500，每一步的逼近误差及目标函，每一步的逼近误差及目标函数由数由chap10_3b.m求得。采用二进制编码方式，求得。采用二进制编码方式，用长度为用长度为10位的二进制编码串来分别表示向量位的二进制编码串来分别表示向量B B、C C和和W W中的每个值。中的每个值。43 遗传算法优化程序为chap10_3a.m，取逼近44 遗遗传传算算法法优优化化中中，取取样样本本个个数数为为Size=30，交交叉叉概概率率为为Pc=0.60，采采用用自自适适应应变变异异概概率率，即即适适应应度度越越小小，变异概率越大，取变异概率越大，取变异概率为变异概率为 取取用用于于优优化化的的RBF网网络络结结构构为为2-3-1，i=1,2,j=1,2,3。网网络络权权值值wj的的取取值值范范围围为为-1,+1，高高斯斯函函数数基基宽宽向向量量元元素素bj的的取取值值范范围围为为0.1,+3，高高斯斯函函数数中中心心矢矢量量元元素素cij的取值范围为的取值范围为-3,+3。取。取则共有则共有12个参数需要优化。个参数需要优化。44 遗传算法优化中，取样本个数为Size=30，交45 经过经过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网网络络高高斯斯基基函函数数参参数数的的优优化化值值及及权权值值的优化值为的优化值为:45 经过150代遗传算法进化，优化后的结果为：46 RBF网网络络遗遗传传算算法法优优化化程程序序包包括括三三部部分分，即即遗遗传传算算法法优优化化程程序序chap10_3a.m、RBF网网络络逼逼近近函函数数程程序序chap10_3b.m和和RBF网网络络逼逼近近测测试程序试程序chap10_3c.m。46 RBF网络遗传算法优化程序包括三部分，即遗传4710.7 基于遗传算法的基于遗传算法的TSP问题优化问题优化旅行商问题（旅行商问题（Traveling Salesman Problem，TSP）：）：有有N个城市，已知任意两个间的距离，现有一推销个城市，已知任意两个间的距离，现有一推销员必须遍访这员必须遍访这N个城市，并且每个城市只能访问一个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，使其旅行路线总长度最短。城市的访问次序，使其旅行路线总长度最短。4710.7 基于遗传算法的TSP问题优化旅旅行行商商问题是是一一个个典典型型的的组合合优化化问题，其其可可能能的的路路径径数数目目与与城城市市数数目目N呈呈指指数数型型增增长的的，一一般般很很难精精确确的的求求出出最最优解解，因因而而寻找找其其有有效效的的近近似似求求解解算算法法具具有有重重要的理要的理论意意义。很很多多实际应用用问题经过简化化处理理后后可可转化化为旅旅行行商商问题，因因而而对旅旅行行商商问题题求求解解方方法法的的研研究究具具有有重要的应用价值重要的应用价值旅行商问题是一个典型的组合优化问题，其可能的路径数目与城市数4910.7.1 TSP问题的编码问题的编码 在旅行商问题的各种求解方法中，描述旅行路线在旅行商问题的各种求解方法中，描述旅行路线的方法主要有如下两种：（的方法主要有如下两种：（1）巡回旅行路线经过的）巡回旅行路线经过的连接两个城市的连接两个城市的路线的顺序排列路线的顺序排列；（；（2）巡回旅行路）巡回旅行路线所经过的各个线所经过的各个城市的顺序排列城市的顺序排列。大多数求解旅行商。大多数求解旅行商问题的遗传算法是以后者为描述方法的，它们大多采问题的遗传算法是以后者为描述方法的，它们大多采用所遍历城市的顺序来表示各个个体的编码串，其等用所遍历城市的顺序来表示各个个体的编码串，其等位基因为位基因为N个整数值或个整数值或N个记号。个记号。4910.7.1 TSP问题的编码以以城市的遍历顺序城市的遍历顺序作为遗传算法的编码，目标函数作为遗传算法的编码，目标函数取路径长度。取路径长度。在群体初始化、交叉操作和变异操作中考虑在群体初始化、交叉操作和变异操作中考虑TSP问题问题的合法性约束条件（即对所有的城市做到不重不漏）。的合法性约束条件（即对所有的城市做到不重不漏）。以城市的遍历顺序作为遗传算法的编码，目标函数取路径长度。5110.7.2 TSP问题的遗传算法设计问题的遗传算法设计 采用遗传算法进行路径优化，分为以下几步：采用遗传算法进行路径优化，分为以下几步：第一步：参数编码和初始群体设定第一步：参数编码和初始群体设定对于对于TSP一类排序问题，采用一类排序问题，采用对访问城市序列进行排对访问城市序列进行排列组合的方法编码列组合的方法编码，即染色体个体表示按顺序经过的，即染色体个体表示按顺序经过的城市序列。城市序列。5110.7.2 TSP问题的遗传算法设计52N为城市总数，染色体长度为N+1，最后一位表示该路径总长度。参数编码和初始群体程序段为：pop=zeros(s,N+1);for i=1:s pop(i,1:N)=randperm(N);%随机排列随机排列end 52N为城市总数，染色体长度为N+1，最后一位表示该路径总长第二步：计算路径长度的函数设计第二步：计算路径长度的函数设计 以距离的总长度为以距离的总长度为适应度函数适应度函数来衡量求解结果是否来衡量求解结果是否最优。设最优。设D=dij是由城市是由城市i和城市和城市j之间的距离组成的之间的距离组成的距离矩阵距离矩阵。计算路径长度的程序为计算路径长度的程序为chap10_1dis.m。目标函数：目标函数：自适应度函数：自适应度函数：第二步：计算路径长度的函数设计目标函数：自适应度函数：54 第三步：计算选择算子第三步：计算选择算子群体中适应度最大的群体中适应度最大的c个个体直接替换适应度最小的个个体直接替换适应度最小的c个个体。选择算子函数为个个体。选择算子函数为chap10_4select.m。num=1;%m11为当前种群中各个体的路径总长度为当前种群中各个体的路径总长度while numc+1%取距离大的取距离大的c个个体个个体 a,mmax(num)=max(m11);%选择当前种群中距离总长度最大值，并记选择当前种群中距离总长度最大值，并记录样本编号给录样本编号给mmax(num)m11(mmax(num)=0;%清除，防止再次被选中清除，防止再次被选中%取距离小的取距离小的c个个体个个体 ,mmin(num)=min(m12);%chenyag m12(mmin(num)=a;%修改为很大的一个数，防止再次被选中修改为很大的一个数，防止再次被选中 num=num+1;end%用距离大的用距离大的c个个体替换距离小的个个体替换距离小的c个个体个个体pop(mmax,:)=pop(mmin,:);54 第三步：计算选择算子num=1;%m11 第四步：计算交叉算子第四步：计算交叉算子有序交叉法有序交叉法步骤1：随机选取两个交叉点。步骤2：复制两交叉点之间的基因串A1和B1。第四步：计算交叉算子有序交叉法56步骤步骤3：在对应位置：在对应位置交换交换X1和和X2双亲匹配段双亲匹配段A1和和B1以外的城市。以外的城市。56步骤3：在对应位置交换X1和X2双亲匹配段A1和B1以外57X1:98|45671|320A1X2:87|14032|965B183|45671|902A198|14032|756有序交叉算子（1）将8复制到子代中，并检查是否与A1中的基因重复。57X1:98|45671|320A1X2:87|140358X1:98|45671|320A1X2:87|14032|965B183|45671|902A198|14032|756有序交叉算子（2）7在子串A1中存在，处于第4个位子。只好去B1的第4个基因位找替补，即358X1:98|45671|320A1X2:87|140359X1:98|45671|320A1X2:87|14032|965B183|45671|902A198|14032|756有序交叉算子（3）59X1:98|45671|320A1X2:87|140360X1:98|45671|320A1X2:87|14032|965B183|45671|902A198|14032|756有序交叉算子（4）6在子串A1中存在，处于第3位。只好去B1的第3个基因位找替补，即060X1:98|45671|320A1X2:87|140361X1:98|45671|320A1X2:87|14032|965B183|45671|902A198|14032|756有序交叉算子（5）几经波折，找到261X1:98|45671|320A1X2:87|140362处理第二条染色体X2的方法相同。交叉算子函数为chap10_4corss.m62处理第二条染色体X2的方法相同。63 第五步：计算变异算子第五步：计算变异算子采用倒置变异法。若当前随机概率值大于变异概率采用倒置变异法。若当前随机概率值大于变异概率pm,则随机选择某一个体的两个点，然后倒置该两则随机选择某一个体的两个点，然后倒置该两个点的中间部分，产生新的个体。变异算子函数为个点的中间部分，产生新的个体。变异算子函数为chap10_4mutate.m。当前个体当前个体X：(1 3 7 4 8 0 5 9 6 2)新体新体X为：为：(1 3 7 5 0 8 4 9 6 2)选择变异点点“7”和和“9”pop(i,mpoint(1):mpoint(2)=fliplr(pop(i,mpoint(1):mpoint(2);63 第五步：计算变异算子当前个体X：(1 3 7 6410.7.3 仿真实例仿真实例 分别以分别以8个城市和个城市和30个城市的路径优化为例，其个城市的路径优化为例，其城市路径坐标保存在当前路径的文件城市路径坐标保存在当前路径的文件cities8.txt和和cities30.txt中。中。6410.7.3 仿真实例65图10-9 8城市进化次数为50时的优化效果，距离L=2.8937(M=1)65图10-9 8城市进化次数为50时的优化效果，距离L=66图10-10 30城市进化次数为300时的优化效果，距离L=424.8693（M=2）66图10-10 30城市进化次数为300时的优化效果，67END67END