遗传算法课件

硕 士 研 究 生 课 程信 息 学 院遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制2/16信 息 学 院 遗遗传传算算法法简简称称GAGA（Genetic Genetic AlgorithmsAlgorithms）是是19621962年年由由美美国国MichiganMichigan大大学学的的HollandHolland教教授授提提出出的的模模拟拟自自然然界界遗遗传传机机制制和和生生物物进进化化论论而而成成的的一一种种并并行行随随机机搜搜索索最最优优化方法。化方法。遗传算法是以达尔文的自然选择学说为基础发展起来的。遗传算法是以达尔文的自然选择学说为基础发展起来的。遗传算法的基本原理遗传算法的基本原理遗传算法的基本原理遗传算法的基本原理简简 介介 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制3/16信 息 学 院自然选择学说包括以下三个方面：自然选择学说包括以下三个方面：（1 1）遗遗传传：这这是是生生物物的的普普遍遍特特征征，亲亲代代把把生生物物信信息息交交给给子子代代，子子代代总总是是和和亲亲代代具具有有相同或相似的性状。生物有了这个特征，物种才能稳定存在。相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2 2）变变异异：亲亲代代和和子子代代之之间间以以及及子子代代的的不不同同个个体体之之间间的的差差异异，称称为为变变异异。变变异异是是随随机发生的，变异的选择和积累是生命多样性的根源。机发生的，变异的选择和积累是生命多样性的根源。（3 3）生生存存斗斗争争和和适适者者生生存存：具具有有适适应应性性变变异异的的个个体体被被保保留留下下来来，不不具具有有适适应应性性变变异异的的个个体体被被淘淘汰汰，通通过过一一代代代代的的生生存存环环境境的的选选择择作作用用，性性状状逐逐渐渐逐逐渐渐与与祖祖先先有有所所不不同同，演变为新的物种。演变为新的物种。遗传算法的基本原理遗传算法的基本原理遗传算法的基本原理遗传算法的基本原理简简 介介 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制4/16信 息 学 院 遗遗传传算算法法将将“优优胜胜劣劣汰汰，适适者者生生存存”的的生生物物进进化化原原理理引引入入优优化化参参数数形形成成的的编编码码串串联联群群体体中中，按按所所选选择择的的适适应应度度函函数数并并通通过过遗遗传传中中的的复复制制、交交叉叉及及变变异异对对个个体体进进行行筛筛选选，使使适适适适应应度度高高的的个个体体被被保保留留下下来来，组组成成新新的的群群体体，新新的的群群体体既既继继承承了了上上一一代代的的信信息息，又又优优于于上上一一代代。这这样样周周而而复复始始，群群体体中中个个体体适适应应度度不不断断提提高高，直直到到满满足足一一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。遗传算法的基本原理遗传算法的基本原理遗传算法的基本原理遗传算法的基本原理基本思想基本思想 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制5/16信 息 学 院遗传算法的基本操作为：遗传算法的基本操作为：（1 1）复制（）复制（Reproduction OperatorReproduction Operator）复复制制是是从从一一个个旧旧种种群群中中选选择择生生命命力力强强的的个个体体位位串串产产生生新新种种群群的的过过程程。具具有有高高适适应应度的位串更有可能在下一代中产生一个或多个子孙。度的位串更有可能在下一代中产生一个或多个子孙。复复制制操操作作可可以以通通过过随随机机方方法法来来实实现现。首首先先产产生生0101之之间间均均匀匀分分布布的的随随机机数数，若若某某串串的复制概率为的复制概率为40%40%，则当产生的随机数在，则当产生的随机数在0.401.00.401.0之间时，该串被复制，否则被淘汰。之间时，该串被复制，否则被淘汰。遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作操操 作作 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制6/16信 息 学 院（2 2）交叉（）交叉（Crossover OperatorCrossover Operator）复复制制操操作作能能从从旧旧种种群群中中选选择择出出优优秀秀者者，但但不不能能创创造造新新的的染染色色体体。而而交交叉叉模模拟拟了了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。交交叉叉的的过过程程为为：在在匹匹配配池池中中任任选选两两个个染染色色体体，随随机机选选择择一一点点或或多多点点交交换换点点位位置置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。遗遗 传传 算算 法法遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作操操 作作 27 July 2024智智 能能 控控 制制7/16信 息 学 院 交交叉叉体体现现了了自自然然界界中中信信息息交交换换的的思思想想。交交叉叉有有一一点点交交叉叉、多多点点交交叉叉、还还有有一一致致交交叉叉、顺顺序序交交叉叉和和周周期期交交叉叉。一一点点交交叉叉是是最最基基本本的的方方法法，应应用用较较广广。它它是是指指染染色色体体切断点有一处，例：切断点有一处，例：遗遗 传传 算算 法法遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作操操 作作 27 July 2024智智 能能 控控 制制8/16信 息 学 院（3 3）变异）变异(Mutation Operator)(Mutation Operator)变变异异运运算算用用来来模模拟拟生生物物在在自自然然的的遗遗传传环环境境中中由由于于各各种种偶偶然然因因素素引引起起的的基基因因突突变变，它它以以很很小小的的概概率率随随机机地地改改变变遗遗传传基基因因（表表示示染染色色体体的的符符号号串串的的某某一一位位）的的值值。在在染染色色体体以以二二进进制制编编码码的的系系统统中中，它它随随机机地地将将染染色色体体的的某某一一个个基基因因由由1 1变变为为0 0，或或由由0 0变为变为1 1。遗遗 传传 算算 法法遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作操操 作作 27 July 2024智智 能能 控控 制制9/16信 息 学 院 若若只只有有选选择择和和交交叉叉，而而没没有有变变异异，则则无无法法在在初初始始基基因因组组合合以以外外的的空空间间进进行行搜搜索索，使使进进化化过过程程在在早早期期就就陷陷入入局局部部解解而而进进入入终终止止过过程程，从从而而影影响响解解的的质质量量。为为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。遗遗 传传 算算 法法遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作操操 作作 27 July 2024智智 能能 控控 制制10/16信 息 学 院（1 1）遗遗传传算算法法是是对对参参数数的的编编码码进进行行操操作作，而而非非对对参参数数本本身身，这这就就是是使使得得我我们们在在优优化化计计算算过过程程中中可可以以借借鉴鉴生生物物学学中中染染色色体体和和基基因因等等概概念念，模模仿仿自自然然界界中中生生物物的的遗遗传传和和进进化等机理；化等机理；（2 2）遗遗传传算算法法同同时时使使用用多多个个搜搜索索点点的的搜搜索索信信息息。传传统统的的优优化化方方法法往往往往是是从从解解空空间间的的单单个个初初始始点点开开始始最最优优解解的的迭迭代代搜搜索索过过程程，单单个个搜搜索索点点所所提提供供的的信信息息不不多多，搜搜索索效效率率不高，有时甚至使搜索过程局限于局部最优解而停滞不前。不高，有时甚至使搜索过程局限于局部最优解而停滞不前。遗传算法的特点遗传算法的特点遗传算法的特点遗传算法的特点特特 点点 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制11/16信 息 学 院 遗遗传传算算法法从从由由很很多多个个体体组组成成的的一一个个初初始始群群体体开开始始最最优优解解的的搜搜索索过过程程，而而不不是是从从一一个个单单一一的的个个体体开开始始搜搜索索，这这是是遗遗传传算算法法所所特特有有的的一一种种隐隐含含并并行行性性，因因此此遗遗传传算算法法的的搜索效率较高。搜索效率较高。（3 3）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用目标函）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。需目标函数的导数值等其他一些辅助信息。遗遗 传传 算算 法法遗传算法的特点遗传算法的特点遗传算法的特点遗传算法的特点特特 点点 27 July 2024智智 能能 控控 制制12/16信 息 学 院 遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题等。及组合优化问题等。（4 4）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进化过程概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。遗遗 传传 算算 法法遗传算法的特点遗传算法的特点遗传算法的特点遗传算法的特点特特 点点 27 July 2024智智 能能 控控 制制13/16信 息 学 院（5 5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；随机搜索；（6 6）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广；射矩阵甚至是神经网络的隐函数，因而应用范围较广；（7 7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。高计算速度，适合大规模复杂问题的优化。遗遗 传传 算算 法法遗传算法的特点遗传算法的特点遗传算法的特点遗传算法的特点特特 点点 27 July 2024智智 能能 控控 制制14/16信 息 学 院（1 1）函数优化。）函数优化。函函数数优优化化是是遗遗传传算算法法的的经经典典应应用用领领域域，也也是是遗遗传传算算法法进进行行性性能能评评价价的的常常用用算算例例。尤尤其其是是对对非非线线性性、多多模模型型、多多目目标标的的函函数数优优化化问问题题，采采用用其其他优化方法较难求解，而遗传算法却可以得到较好的结果。他优化方法较难求解，而遗传算法却可以得到较好的结果。遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域应应 用用 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制15/16信 息 学 院（2 2）组合优化。）组合优化。随随着着问问题题的的增增大大，组组合合优优化化问问题题的的搜搜索索空空间间也也急急剧剧扩扩大大，采采用用传传统统的的优优化化方方法法很很难难得得到到最最优优解解。遗遗传传算算法法是是寻寻求求这这种种满满意意解解的的最最佳佳工工具具。例例如如，遗遗传传算算法法已已经经在在求求解解旅旅行行商商问问题题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。背包问题、装箱问题、图形划分问题等方面得到成功的应用。遗遗 传传 算算 法法遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域应应 用用 27 July 2024智智 能能 控控 制制16/16信 息 学 院（3 3）生产调度问题）生产调度问题 在在很很多多情情况况下下，采采用用建建立立数数学学模模型型的的方方法法难难以以对对生生产产调调度度问问题题进进行行精精确确求求解解。在在现现实实生生产产中中多多采采用用一一些些经经验验进进行行调调度度。遗遗传传算算法法是是解解决决复复杂杂调调度度问问题题的的有有效效工工具具，在在单单件件生生产产车车间间调调度度、流流水水线线生生产产车车间间调调度度、生生产产规规划、任务分配等方面遗传算法都得到了有效的应用。划、任务分配等方面遗传算法都得到了有效的应用。遗遗 传传 算算 法法遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域应应 用用 27 July 2024智智 能能 控控 制制17/16信 息 学 院（4 4）自动控制。）自动控制。在在自自动动控控制制领领域域中中有有很很多多与与优优化化相相关关的的问问题题需需要要求求解解，遗遗传传算算法法已已经经在在其其中中得得到到了了初初步步的的应应用用。例例如如，利利用用遗遗传传算算法法进进行行控控制制器器参参数数的的优优化化、基基于于遗遗传传算算法法的的模模糊糊控控制制规规则则的的学学习习、基基于于遗遗传传算算法法的的参参数数辨辨识识、基基于于遗传算法的神经网络结构的优化和权值学习等。遗传算法的神经网络结构的优化和权值学习等。遗遗 传传 算算 法法遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域应应 用用 27 July 2024智智 能能 控控 制制18/16信 息 学 院（5 5）机器人）机器人 例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。机器人结构优化和行为协调等方面得到研究和应用。（6 6）图像处理）图像处理 遗遗传传算算法法可可用用于于图图像像处处理理过过程程中中的的扫扫描描、特特征征提提取取、图图像像分分割割等等的的优优化化计计算算。目目前前遗遗传传算算法法已已经经在在模模式式识识别别、图图像像恢恢复复、图图像像边边缘缘特特征征提提取取等等方方面面得得到到了应用。了应用。遗遗 传传 算算 法法遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域遗传算法的应用领域应应 用用 27 July 2024智智 能能 控控 制制19/16信 息 学 院遗传算法的构成要素遗传算法的构成要素遗传算法的构成要素遗传算法的构成要素（1 1 1 1）染色体编码方法）染色体编码方法）染色体编码方法）染色体编码方法 基基基基本本本本遗遗遗遗传传传传算算算算法法法法使使使使用用用用固固固固定定定定长长长长度度度度的的的的二二二二进进进进制制制制符符符符号号号号来来来来表表表表示示示示群群群群体体体体中中中中的的的的个个个个体体体体，其其其其等等等等位位位位基基基基因因因因是是是是由由由由二二二二值值值值符符符符号号号号集集集集0,10,10,10,1所所所所组组组组成成成成。初初初初始始始始个个个个体体体体基基基基因因因因值值值值可可可可用用用用均均均均匀匀匀匀分分分分布布布布的的的的随随随随机机机机值值值值生生生生成成成成，如如如如就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是18181818。遗传算法的优化设计遗传算法的优化设计遗传算法的优化设计遗传算法的优化设计构成要素构成要素 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制20/16信 息 学 院（2 2 2 2）个个个个体体体体适适适适应应应应度度度度评评评评价价价价：基基基基本本本本遗遗遗遗传传传传算算算算法法法法与与与与个个个个体体体体适适适适应应应应度度度度成成成成正正正正比比比比的的的的概概概概率率率率来来来来决决决决定定定定当当当当前前前前群群群群体体体体中中中中每每每每个个个个个个个个体体体体遗遗遗遗传传传传到到到到下下下下一一一一代代代代群群群群体体体体中中中中的的的的概概概概率率率率多多多多少少少少。为为为为正正正正确确确确计计计计算算算算这这这这个个个个概概概概率率率率，要要要要求求求求所所所所有有有有个个个个体体体体的的的的适适适适应应应应度度度度必必必必须须须须为为为为正正正正数数数数或或或或零零零零。因因因因此此此此，必必必必须须须须先先先先确确确确定定定定由由由由目目目目标标标标函函函函数数数数值值值值J J J J到到到到个个个个体体体体适应度适应度适应度适应度f f f f之间的转换规则。之间的转换规则。之间的转换规则。之间的转换规则。遗遗 传传 算算 法法遗传算法的优化设计遗传算法的优化设计遗传算法的优化设计遗传算法的优化设计构成要素构成要素 27 July 2024智智 能能 控控 制制21/16信 息 学 院（3 3 3 3）遗传算子：基本遗传算法使用下述三种遗传算子：）遗传算子：基本遗传算法使用下述三种遗传算子：）遗传算子：基本遗传算法使用下述三种遗传算子：）遗传算子：基本遗传算法使用下述三种遗传算子：选择运算选择运算选择运算选择运算:使用比例选择算子；使用比例选择算子；使用比例选择算子；使用比例选择算子；交叉运算交叉运算交叉运算交叉运算:使用单点交叉算子；使用单点交叉算子；使用单点交叉算子；使用单点交叉算子；变异运算变异运算变异运算变异运算:使用基本位变异算子或均匀变异算子。使用基本位变异算子或均匀变异算子。使用基本位变异算子或均匀变异算子。使用基本位变异算子或均匀变异算子。遗遗 传传 算算 法法遗传算法的优化设计遗传算法的优化设计遗传算法的优化设计遗传算法的优化设计构成要素构成要素 27 July 2024智智 能能 控控 制制22/16信 息 学 院（4 4 4 4）基本遗传算法的运行参数）基本遗传算法的运行参数）基本遗传算法的运行参数）基本遗传算法的运行参数 有下述有下述有下述有下述4 4 4 4个运行参数需要提前设定：个运行参数需要提前设定：个运行参数需要提前设定：个运行参数需要提前设定：M M M M：群体大小，即群体中所含个体的数量，一般取为：群体大小，即群体中所含个体的数量，一般取为：群体大小，即群体中所含个体的数量，一般取为：群体大小，即群体中所含个体的数量，一般取为20100201002010020100；G G G G：遗传算法的终止进化代数，一般取为：遗传算法的终止进化代数，一般取为：遗传算法的终止进化代数，一般取为：遗传算法的终止进化代数，一般取为100500100500100500100500；PcPcPcPc：交叉概率，一般取为：交叉概率，一般取为：交叉概率，一般取为：交叉概率，一般取为0.40.990.40.990.40.990.40.99；PmPmPmPm：变异概率，一般取为：变异概率，一般取为：变异概率，一般取为：变异概率，一般取为0.00010.10.00010.10.00010.10.00010.1。遗遗 传传 算算 法法遗传算法的优化设计遗传算法的优化设计遗传算法的优化设计遗传算法的优化设计构成要素构成要素 27 July 2024智智 能能 控控 制制23/16信 息 学 院 对对对对于于于于一一一一个个个个需需需需要要要要进进进进行行行行优优优优化化化化的的的的实实实实际际际际问问问问题题题题，一一一一般般般般可可可可按按按按下下下下述述述述步步步步骤骤骤骤构构构构造造造造遗遗遗遗传算法：传算法：传算法：传算法：第第第第一一一一步步步步：确确确确定定定定决决决决策策策策变变变变量量量量及及及及各各各各种种种种约约约约束束束束条条条条件件件件，即即即即确确确确定定定定出出出出个个个个体体体体的的的的表表表表现现现现型型型型X X X X和和和和问题的解空间；问题的解空间；问题的解空间；问题的解空间；第第第第二二二二步步步步：建建建建立立立立优优优优化化化化模模模模型型型型，即即即即确确确确定定定定出出出出目目目目标标标标函函函函数数数数的的的的类类类类型型型型及及及及数数数数学学学学描描描描述述述述形形形形式式式式或量化方法；或量化方法；或量化方法；或量化方法；遗传算法的应用步骤遗传算法的应用步骤遗传算法的应用步骤遗传算法的应用步骤应应 用用 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制24/16信 息 学 院第第第第三三三三步步步步：确确确确定定定定表表表表示示示示可可可可行行行行解解解解的的的的染染染染色色色色体体体体编编编编码码码码方方方方法法法法，即即即即确确确确定定定定出出出出个个个个体体体体的的的的基基基基因因因因型型型型x x x x及及及及遗遗遗遗传传传传算算算算法法法法的的的的搜索空间；搜索空间；搜索空间；搜索空间；第第第第四四四四步步步步：确确确确定定定定解解解解码码码码方方方方法法法法，即即即即确确确确定定定定出出出出由由由由个个个个体体体体基基基基因因因因型型型型x x x x到到到到个个个个体体体体表表表表现现现现型型型型X X X X的的的的对对对对应应应应关关关关系系系系或或或或转转转转换换换换方法；方法；方法；方法；第第第第五五五五步步步步：确确确确定定定定个个个个体体体体适适适适应应应应度度度度的的的的量量量量化化化化评评评评价价价价方方方方法法法法，即即即即确确确确定定定定出出出出由由由由目目目目标标标标函函函函数数数数值值值值到到到到个个个个体体体体适适适适应应应应度度度度的的的的转换规则；转换规则；转换规则；转换规则；第第第第六六六六步步步步：设设设设计计计计遗遗遗遗传传传传算算算算子子子子，即即即即确确确确定定定定选选选选择择择择运运运运算算算算、交交交交叉叉叉叉运运运运算算算算、变变变变异异异异运运运运算算算算等等等等遗遗遗遗传传传传算算算算子子子子的的的的具具具具体体体体操作方法。操作方法。操作方法。操作方法。第七步：确定遗传算法的有关运行参数，即第七步：确定遗传算法的有关运行参数，即第七步：确定遗传算法的有关运行参数，即第七步：确定遗传算法的有关运行参数，即M,G,Pc,PmM,G,Pc,PmM,G,Pc,PmM,G,Pc,Pm等参数。等参数。等参数。等参数。遗遗 传传 算算 法法应应 用用 遗传算法的应用步骤遗传算法的应用步骤遗传算法的应用步骤遗传算法的应用步骤27 July 2024智智 能能 控控 制制25/16信 息 学 院遗传算法流程图遗传算法流程图 遗传算法的操作过程遗传算法的操作过程遗传算法的操作过程遗传算法的操作过程操操 作作 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制26/16信 息 学 院利用遗传算法求利用遗传算法求利用遗传算法求利用遗传算法求RosenbrockRosenbrockRosenbrockRosenbrock函数的极大值函数的极大值函数的极大值函数的极大值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 遗遗 传传 算算 法法27 July 2024智智 能能 控控 制制27/16信 息 学 院二进制编码遗传算法求函数极大值二进制编码遗传算法求函数极大值二进制编码遗传算法求函数极大值二进制编码遗传算法求函数极大值 求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：（1 1 1 1）确定决策变量和约束条件；）确定决策变量和约束条件；）确定决策变量和约束条件；）确定决策变量和约束条件；（2 2 2 2）建立优化模型；）建立优化模型；）建立优化模型；）建立优化模型；（3 3 3 3）确定编码方法）确定编码方法）确定编码方法）确定编码方法 遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制28/16信 息 学 院 用用用用长长长长度度度度为为为为10101010位位位位的的的的二二二二进进进进制制制制编编编编码码码码串串串串来来来来分分分分别别别别表表表表示示示示两两两两个个个个决决决决策策策策变变变变量量量量x1,x2x1,x2x1,x2x1,x2。10101010位位位位二二二二进进进进制制制制编编编编码码码码串串串串可可可可以以以以表表表表示示示示从从从从0 0 0 0到到到到1023102310231023之之之之间间间间的的的的1024102410241024个个个个不不不不同同同同的的的的数数数数，故故故故将将将将x x x x1 1 1 1,x,x,x,x2 2 2 2的的的的定定定定义义义义域域域域离离离离散散散散化化化化为为为为1023102310231023个个个个均均均均等等等等的的的的区区区区域域域域，包包包包括括括括两两两两个个个个端点在内共有端点在内共有端点在内共有端点在内共有1024102410241024个不同的离散点。个不同的离散点。个不同的离散点。个不同的离散点。从从从从 离离离离 散散散散 点点点点-2.048-2.048-2.048-2.048到到到到 离离离离 散散散散 点点点点 2.048 2.048 2.048 2.048，分分分分 别别别别 对对对对 应应应应 于于于于 从从从从0000000000(0)0000000000(0)0000000000(0)0000000000(0)到到到到1111111111(1023)1111111111(1023)1111111111(1023)1111111111(1023)之间的二进制编码。之间的二进制编码。之间的二进制编码。之间的二进制编码。遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制29/16信 息 学 院 将将将将x1,x2x1,x2x1,x2x1,x2分别表示的两个分别表示的两个分别表示的两个分别表示的两个10101010位长的二进制编码串连接在一起，组位长的二进制编码串连接在一起，组位长的二进制编码串连接在一起，组位长的二进制编码串连接在一起，组成一个成一个成一个成一个20202020位长的二进制编码串，它就构成了这个函数优化问题的染色体位长的二进制编码串，它就构成了这个函数优化问题的染色体位长的二进制编码串，它就构成了这个函数优化问题的染色体位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一编码方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一编码方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一编码方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一一对应的关系。一对应的关系。一对应的关系。一对应的关系。例如：例如：例如：例如：表示表示表示表示一个个体的基因型，其中前一个个体的基因型，其中前一个个体的基因型，其中前一个个体的基因型，其中前10101010位表示位表示位表示位表示x1x1x1x1，后，后，后，后10101010位表示位表示位表示位表示x2x2x2x2。遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制30/16信 息 学 院（4 4 4 4）确确确确定定定定解解解解码码码码方方方方法法法法：解解解解码码码码时时时时需需需需要要要要将将将将20202020位位位位长长长长的的的的二二二二进进进进制制制制编编编编码码码码串串串串切切切切断断断断为为为为两两两两个个个个10101010位位位位长长长长的的的的二二二二进进进进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y y y y1 1 1 1和和和和y y y y2 2 2 2。依依依依据据据据个个个个体体体体编编编编码码码码方方方方法法法法和和和和对对对对定定定定义义义义域域域域的的的的离离离离散散散散化化化化方方方方法法法法可可可可知知知知，将将将将代代代代码码码码y y y y转转转转换换换换为为为为变变变变量量量量x x x x的的的的解解解解码码码码公式为公式为公式为公式为 例如，对个体例如，对个体例如，对个体例如，对个体遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制31/16信 息 学 院 它由两个代码所组成它由两个代码所组成它由两个代码所组成它由两个代码所组成 上述两个代码经过解码后，可得到两个实际的值上述两个代码经过解码后，可得到两个实际的值上述两个代码经过解码后，可得到两个实际的值上述两个代码经过解码后，可得到两个实际的值（5 5 5 5）确定个体评价方法：由于）确定个体评价方法：由于）确定个体评价方法：由于）确定个体评价方法：由于RosenbrockRosenbrockRosenbrockRosenbrock函数的值域总是非负的，并且优化目标函数的值域总是非负的，并且优化目标函数的值域总是非负的，并且优化目标函数的值域总是非负的，并且优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制32/16信 息 学 院选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数（6 6 6 6）设设设设计计计计遗遗遗遗传传传传算算算算子子子子：选选选选择择择择运运运运算算算算使使使使用用用用比比比比例例例例选选选选择择择择算算算算子子子子，交交交交叉叉叉叉运运运运算算算算使使使使用用用用单单单单点点点点交交交交叉算子，变异运算使用基本位变异算子。叉算子，变异运算使用基本位变异算子。叉算子，变异运算使用基本位变异算子。叉算子，变异运算使用基本位变异算子。（7 7 7 7）确确确确定定定定遗遗遗遗传传传传算算算算法法法法的的的的运运运运行行行行参参参参数数数数：群群群群体体体体大大大大小小小小M=80M=80M=80M=80，终终终终止止止止进进进进化化化化代代代代数数数数G=100G=100G=100G=100，交交交交叉概率叉概率叉概率叉概率Pc=0.60Pc=0.60Pc=0.60Pc=0.60，变异概率，变异概率，变异概率，变异概率Pm=0.10Pm=0.10Pm=0.10Pm=0.10。上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制33/16信 息 学 院 采用上述方法进行仿真，经过采用上述方法进行仿真，经过采用上述方法进行仿真，经过采用上述方法进行仿真，经过100100100100步迭代，最佳样本为步迭代，最佳样本为步迭代，最佳样本为步迭代，最佳样本为即当即当即当即当 时，时，时，时，RosenbrockRosenbrockRosenbrockRosenbrock函数具有函数具有函数具有函数具有极大值，极大值为极大值，极大值为极大值，极大值为极大值，极大值为3905.93905.93905.93905.9。遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制34/16信 息 学 院 遗传算法的优化过程是目标函数遗传算法的优化过程是目标函数遗传算法的优化过程是目标函数遗传算法的优化过程是目标函数J J J J和适应度函数和适应度函数和适应度函数和适应度函数F F F F的变化过程。的变化过程。的变化过程。的变化过程。由仿真结果可知，随着进化过程的进行，群体中适应度较低的一由仿真结果可知，随着进化过程的进行，群体中适应度较低的一由仿真结果可知，随着进化过程的进行，群体中适应度较低的一由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的最优点附近，从而搜索到问题的最优解。集中在所求问题的最优点附近，从而搜索到问题的最优解。集中在所求问题的最优点附近，从而搜索到问题的最优解。集中在所求问题的最优点附近，从而搜索到问题的最优解。遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制35/16信 息 学 院实数编码遗传算法求函数极大值实数编码遗传算法求函数极大值求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：（1 1）确定决策变量和约束条件；）确定决策变量和约束条件；（2 2）建立优化模型；）建立优化模型；（3 3）确确定定编编码码方方法法：用用2 2个个实实数数分分别别表表示示两两个个决决策策变变量量，分分别别将将的的定定义域离散化为从离散点义域离散化为从离散点-2.048-2.048到离散点到离散点2.0482.048的的SizeSize个实数。个实数。遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制36/16信 息 学 院（4 4）确定个体评价方法：）确定个体评价方法：个体的适应度直接取为对应的目标函数值，即个体的适应度直接取为对应的目标函数值，即 选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数 遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 27 July 2024智智 能能 控控 制制37/16信 息 学 院（5 5）设设计计遗遗传传算算子子：选选择择运运算算使使用用比比例例选选择择算算子子，交交叉叉运运算算使使用用单单点点交交叉算子，变异运算使用基本位变异算子。叉算子，变异运算使用基本位变异算子。（6 6）确定遗传算法的运行参数：群体大小）确定遗传算法的运行参数：群体大小M=500M=500，终止进化代数，终止进化代数G=200G=200，交叉概率交叉概率P Pc c=0.90=0.90，采用自适应变异概率，采用自适应变异概率即变异概率与适应度有关，适应度越小，变异概率越大。即变异概率与适应度有关，适应度越小，变异概率越大。遗遗 传传 算算 法法遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值遗传算法求函数极值求极大值求极大值 写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits38 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日