《第三章求解优化问题的智能算法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第三章求解优化问题的智能算法PPT讲稿.ppt（209页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章求解优化问题的智能算法2022/10/131第1页，共209页，编辑于2022年，星期二3.1 概述概述2022/10/132第2页，共209页，编辑于2022年，星期二最最优优化化问问题题是是指指在在一一定定的的约约束束条条件件下下，决决定定某某个个或或某某些些可可控控制制的的因因素素应应有有的的合合理理取取值值，使使所所选选定定的的目目标标达达到到最最优优的的问问题题。解解决决最最优优化化问问题题的的方方法法称称为为最最优化方法。它具有高度应用性和技术性的特点。优化方法。它具有高度应用性和技术性的特点。最最优优化化问问题题可可以以追追溯溯到到十十分分古古老老的的极极值值问问题题，在在
2、17世世纪纪，伟伟大大科科学学家家Newton发发明明微微积积分分的的时时候候，已已经经提提出出了了极极值值问问题题，后后来来又又出出现现了了Lagrange乘乘子子法法，Cauchy则则利利用用最最速速下下降降法法求求解解无无约约束束极极小小化化问问题题。然然而而，直直到到1947年年Dantzig提提出出求求解解一一般般线线性性规规划划问问题题的的单单纯纯形形法法之之后，它才成为一门独立的学科。后，它才成为一门独立的学科。3.1概述概述最优化方法的研究起源和意义最优化方法的研究起源和意义1/22022/10/133第3页，共209页，编辑于2022年，星期二随随着着近近代代科科学学技技术术
3、发发展展的的需需要要，特特别别是是由由于于计计算算机机技技术术的的飞飞速速发发展展，促促进了最优化方法的迅速发展，并很快渗透到各个领域。进了最优化方法的迅速发展，并很快渗透到各个领域。20世世纪纪70年年代代，最最优优化化方方法法这这门门应应用用技技术术科科学学又又开开始始产产生生出出最最优优设设计计、最最优优控控制制与与最最优优管管理理等等分分支支。到到20世世纪纪80年年代代，最最优优化化技技术术又又在在这这些些分分支支中中发发展展出出了了新新的的更更细细的的分分支支，比比如如，工工程程技技术术领领域域的的机机械械优优化化设设计计、建建筑筑结结构构优优化化设设计计以以及及化化工工石石油油领
4、领域域的的优优化化设计等。设计等。3.1概述概述最优化方法的研究起源和意义最优化方法的研究起源和意义2/22022/10/134第4页，共209页，编辑于2022年，星期二求解优化问题的步骤求解优化问题的步骤(1)分析待优化的问题，建立问题的数学模型；分析待优化的问题，建立问题的数学模型；(2)分析数学模型，选择合适的最优化算法；分析数学模型，选择合适的最优化算法；(3)编写计算机程序、上机计算、求出最优解；编写计算机程序、上机计算、求出最优解；(4)结果检验与最后决策。结果检验与最后决策。2022/10/135第5页，共209页，编辑于2022年，星期二转化为最小化问题。3.1概述概述最优化
5、问题的数学描述最优化问题的数学描述2022/10/136第6页，共209页，编辑于2022年，星期二(1)枚举法。枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。在目前最先进的计算工具上都无法求解。(2)启发
6、式算法。启发式算法。寻寻求求一一种种能能产产生生可可行行解解的的启启发发式式规规则则，以以找找到到一一个个最最优优解解或或近近似似最最优优解解。该该方方法法的的求求解解效效率率虽虽然然比比较较高高，但但对对每每一一个个需需要要求求解解的的问问题题都都必必须须找找出出其其特特有有的的启启发发式式规规则则，这这个个启启发发式式规规则则无无通通用用性性，不不适适合合于于其其他问题。他问题。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法1/22022/10/137第7页，共209页，编辑于2022年，星期二(3)搜搜索索算算法法。寻寻求求一一种种搜搜索索算算法法，该该算算法法在在可
7、可行行解解集集合合的的一一个个子子集集内内进进行行搜搜索索操操作作，以以找找到到问问题题的的最最优优解解或或近近似似最最优优解解。该该方方法法虽虽然然保保证证不不了了一一定定能能够够得得到到问问题题的的最最优优解解，但但若若适适当当地地利利用用一一些些启启发发知知识识，就可在近似解的质量和求解效率上达到就可在近似解的质量和求解效率上达到种较好的平衡。种较好的平衡。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法2/22022/10/138第8页，共209页，编辑于2022年，星期二以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具以最速下降法、牛顿法和共扼方向法等为代表
8、的传统优化算法具有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下：点。这些算法的基本迭代步骤如下：3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法2022/10/139第9页，共209页，编辑于2022年，星期二3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法最速下降法最速下降法2022/10/1310第10页，共209页，编辑于2022年，星期二3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法牛顿法牛顿法2022/10/1311第11页，共209页，编辑于2
9、022年，星期二3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法共轭方向法共轭方向法2022/10/1312第12页，共209页，编辑于2022年，星期二l对目标函数和约束函数表达的要求必须更为宽松对目标函数和约束函数表达的要求必须更为宽松l计算的效率比理论上的最优性更重要计算的效率比理论上的最优性更重要l算法随时终止能够随时得到较好的解算法随时终止能够随时得到较好的解l对优化模型中数据的质量要求更为宽松对优化模型中数据的质量要求更为宽松实实际际生生活活中中对对最最优优化化方方法法性性能能的的需需求求促促进进了了最最优优化化方方法法的的发发展展，最最优优化化逐逐步步走走出出“象象
10、牙牙塔塔”，面面向向实实际际需需要要，完完成成了了从从“方方法法定定向向”到到“问题定向问题定向”的转换。的转换。3.1概述概述对最优化提出的新的需求对最优化提出的新的需求2022/10/1313第13页，共209页，编辑于2022年，星期二l1975年年，Holland提提出出遗遗传传算算法法(GeneticAlgorithm)。这这种种优优化化方方法法模模仿仿生生物物种种群群中中优优胜胜劣劣汰汰的的选选择择机机制制，通通过过种种群群中中优优势势个个体体的的繁衍进化来实现优化的功能。繁衍进化来实现优化的功能。l1977年年，Glover提提出出禁禁忌忌搜搜索索(TabuSearch)算算法法
11、。这这种种方方法法将将记记忆忆功功能能引引入入到到最最优优解解的的搜搜索索过过程程中中，通通过过设设置置禁禁忌忌区区阻阻止止搜搜索索过过程程中的重复，从而大大提高了寻优过程的搜索效率。中的重复，从而大大提高了寻优过程的搜索效率。l1983年年，Kirkpatrick提提出出了了模模拟拟退退火火(SimulatedAnnealing)算算法法。这这种种算算法法模模拟拟热热力力学学中中退退火火过过程程能能使使金金属属原原子子达达到到能能量量最最低低状状态态的的机机制制，通通过过模模拟拟的的降降温温过过程程，按按玻玻兹兹曼曼(Boltzmann)方方程程计计算算状状态态间间的的转转移移概概率率来引导
12、搜索，从而使算法具有很好的全局搜索能力。来引导搜索，从而使算法具有很好的全局搜索能力。3.1概述概述新的优化方法不断出现新的优化方法不断出现1/22022/10/1314第14页，共209页，编辑于2022年，星期二l20世世 纪纪 90年年 代代 初初，Dorigo等等 提提 出出蚁蚁 群群 优优 化化 算算 法法(Ant ColonyOptimization)算算法法。这这种种算算法法借借鉴鉴蚁蚁群群群群体体利利用用信信息息素素相相互互传传递递信信息息来来实实现路径优化的机理，通过记忆路径信息素的变化来解决组合优化问题。现路径优化的机理，通过记忆路径信息素的变化来解决组合优化问题。l199
13、5年年，Kenedy和和 Eberhart提提 出出粒粒 子子 群群 优优 化化(Particle SwarmOptimization)算算法法。这这种种方方法法模模仿仿鸟鸟类类和和鱼鱼类类群群体体觅觅食食迁迁移移中中，个个体体与与群群体体协协调调一一致致的的机机理理，通通过过群群体体最最优优方方向向、个个体体最最优优方方向向和惯性方向的协调来求解实数优化问题。和惯性方向的协调来求解实数优化问题。l1999年年，Linhares提提出出了了捕捕食食搜搜索索(PredatorySearch)算算法法。这这种种算算法法模模拟拟猛猛兽兽捕捕食食中中大大范范围围搜搜寻寻和和局局部部蹲蹲守守的的特特点点
14、，通通过过设设置置全全局局搜搜索索和和局局部部搜搜索索间间变变换换的的阈阈值值来来协协调调两两种种不不同同的的搜搜索索模模式式，从而实现了对全局搜索能力和局部搜索能力的兼顾。从而实现了对全局搜索能力和局部搜索能力的兼顾。3.1概述概述新的优化方法不断出现新的优化方法不断出现2/22022/10/1315第15页，共209页，编辑于2022年，星期二l不不以以达达到到某某个个最最优优性性条条件件或或找找到到理理论论上上的的精精确确最最优优解解为为目目标标，而而是是更更看重计算的速度和效率；看重计算的速度和效率；l对目标函数和约束函数的要求十分宽松；对目标函数和约束函数的要求十分宽松；l算算法法的
15、的基基本本思思想想都都是是来来自自对对某某种种自自然然规规律律的的模模仿仿，具具有有人人工工智智能能的特点；的特点；l多多数数算算法法含含有有一一个个多多个个体体的的群群体体，寻寻优优过过程程实实际际上上就就是是种种群群的的进进化化过程；过程；l理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。3.1概述概述新的算法的一些共同特点新的算法的一些共同特点2022/10/1316第16页，共209页，编辑于2022年，星期二l由由于于算算法法理理论论薄薄弱弱，最最早早被被称称为为“现现代代启启发发式式(ModernHeuristics)”或
16、或“高级启发式高级启发式(AdvancedHeuristics)”；l从从其其人人工工智智能能的的特特点点，被被称称为为“智智能能计计算算(IntelligentComputation)”或或“智能优化算法智能优化算法(IntelligentOptimizationAlgorithms)”；l从从 不不 以以 精精 确确 解解 为为 目目 标标 的的 特特 点点，又又 被被 归归 到到“软软 计计 算算(SoftComputing)”方法中；方法中；l从从种种群群进进化化的的特特点点看看，它它们们又又可可以以称称为为“进进化化计计算算(EvolutionaryCompuation)”；l从从模
17、模仿仿自自然然规规律律的的特特点点出出发发，又又有有人人将将它它们们称称为为“自自然然计计算算(NaturalComputing)”。3.1概述概述新的优化方法的不同名称新的优化方法的不同名称2022/10/1317第17页，共209页，编辑于2022年，星期二l应用智能优化算法解决各类问题是重点；应用智能优化算法解决各类问题是重点；l算法改进有很大的创新空间；算法改进有很大的创新空间；l多种算法结合的混合算法是一条捷径；多种算法结合的混合算法是一条捷径；l不提倡刻意去追求理论成果；不提倡刻意去追求理论成果；l算法性能的测算是一项要下真功夫的工作；算法性能的测算是一项要下真功夫的工作；l选选择
18、择测测试试例例题题的的一一般般规规律律：网网上上题题库库中中的的例例题题文文献献中中的的例例题题随机产生的例题随机产生的例题实际应用问题实际应用问题自己编的例题；自己编的例题；l算算法法性性能能测测试试的的主主要要指指标标：达达优优率率(解解的的目目标标平平均均值值和和最最优优解解的的目目标标值值的的比比，所所有有解解的的目目标标值值的的标标准准差差等等)，计计算算速速度度，计计算算大大规规模问题的能力；模问题的能力；l创造出新算法创造出新算法3.1概述概述怎样学习研究智能优化方法怎样学习研究智能优化方法2022/10/1318第18页，共209页，编辑于2022年，星期二3.2 遗传算法遗传
19、算法2022/10/1319第19页，共209页，编辑于2022年，星期二生生物物在在自自然然界界中中的的生生存存繁繁衍衍，显显示示出出了了其其对对自自然然环环境境的的优优异异自自适适应应能能力力。受受其其启启发发，人人们们致致力力于于对对生生物物各各种种生生存存特特性性的的机机理理研研究究和和行行为为模模拟，为人工自适应系统的设计和开发提供了广阔的前景。拟，为人工自适应系统的设计和开发提供了广阔的前景。遗遗传传算算法法(GeneticAlgorithm，简简称称GA)就就是是这这种种生生物物行行为为的的计计算算机机模模拟中令人瞩目的重要成果。拟中令人瞩目的重要成果。基基于于对对生生物物遗遗传
20、传和和进进化化过过程程的的计计算算机机模模拟拟，遗遗传传算算法法使使得得各各种种人人工工系系统统具具有优良的自适应能力和优化能力。有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传算法所借鉴的生物学基础就是生物的遗传和进化。3.2遗传算法遗传算法概要概要2022/10/1320第20页，共209页，编辑于2022年，星期二虽虽然然人人们们还还未未完完全全揭揭开开遗遗传传与与进进化化的的奥奥秘秘，既既没没有有完完全全掌掌握握其其机机制制，也也不不完完全全清清楚楚染染色色体体编编码码和和译译码码过过程程的的细细节节，更更不不完完全全了了解解其其控控制制方方式，但遗传
21、与进化的以下几个特点却为人们所共识：式，但遗传与进化的以下几个特点却为人们所共识：(1)生生物物的的所所有有遗遗传传信信息息都都包包含含在在其其染染色色休休中中，染染色色体体决决定定了了生生物物的性状。的性状。(2)染染色色体体是是由由基基因因及及其其有有规规律律的的排排列列所所构构成成的的，遗遗传传和和进进化化过过程程发发生生在在染色体上。染色体上。(3)生物的繁殖过程是由其基因的复制过程来完成的：生物的繁殖过程是由其基因的复制过程来完成的：(4)通通过过同同源源染染色色体体之之间间的的交交叉叉或或染染色色体体的的变变异异会会产产生生新新的的物物种种，使使生生物物呈呈现新的性状。现新的性状。
22、(5)对对环环境境适适应应性性好好的的基基因因或或染染色色体体经经常常比比适适应应性性差差的的基基因因或或染染色色体体有有更更多多的机会遗传到下一代。的机会遗传到下一代。3.2遗传算法遗传算法概要概要2022/10/1321第21页，共209页，编辑于2022年，星期二遗遗传传算算法法是是模模拟拟生生物物在在自自然然环环境境下下的的遗遗传传和和进进化化过过程程而而形形成成的的一一种种自自适应全局优化概率搜索算法。适应全局优化概率搜索算法。它它最最早早由由美美国国密密执执安安大大学学的的Holland教教授授提提出出，起起源源于于60年年代代对对自自然然和人工自适应系统的研究。和人工自适应系统的
23、研究。70年年代代DeJong基基于于遗遗传传算算法法的的思思想想在在计计算算机机上上进进行行了了大大量量的的纯纯数数值值函函数优化计算实验。数优化计算实验。在在一一系系列列研研究究工工作作的的基基础础上上，80年年代代由由Goldberg进进行行归归纳纳总总结结，形成了遗传算法的基本框架。形成了遗传算法的基本框架。3.2遗传算法遗传算法概要概要2022/10/1322第22页，共209页，编辑于2022年，星期二式中，式中，为决策变量，为决策变量，f(X)为目标函数，后两个式子为为目标函数，后两个式子为约束条件，约束条件，U是基本空间，是基本空间，R是是U的一个子集。的一个子集。对于一个求函
24、数最大值的优化问题对于一个求函数最大值的优化问题(求函数最小值也类同求函数最小值也类同)，一般可描述，一般可描述为下述数学规划模型：为下述数学规划模型：满满足足约约束束条条件件的的解解X称称为为可可行行解解，集集合合R表表示示由由所所有有满满足足约约束束条条件件的的解解所组成的一个集合，叫做可行解集合。它们之间的关系如图所示。所组成的一个集合，叫做可行解集合。它们之间的关系如图所示。3.2遗传算法遗传算法概要概要2022/10/1323第23页，共209页，编辑于2022年，星期二U基本空间基本空间R可行解集合可行解集合X可行解可行解3.2遗传算法遗传算法概要概要2022/10/1324第24
25、页，共209页，编辑于2022年，星期二对对于于上上述述最最优优化化问问题题，目目标标函函数数和和约约束束条条件件种种类类繁繁多多，有有的的是是线线性性的的，有有的的是是非非线线性性的的；有有的的是是连连续续的的，有有的的是是离离散散的的；有有的的是是单单峰峰值的，有的是多峰值的。值的，有的是多峰值的。随随着着研研究究的的深深入入，人人们们逐逐渐渐认认识识到到在在很很多多复复杂杂情情况况下下要要想想完完全全精精确确地地求求出出其其最最优优解解既既不不可可能能，也也不不现现实实，因因而而求求出出其其近近似似最最优优解解或或满满意意解解是是人人们们的的主主要要着眼点之一。着眼点之一。3.2遗传算法
26、遗传算法概要概要2022/10/1325第25页，共209页，编辑于2022年，星期二遗遗传传算算法法中中，将将n维维决决策策向向量量用用n个个记记号号xi(n=l，2，n)所组成的符号串所组成的符号串X来表示：来表示：把把每每一一个个xi看看作作一一个个遗遗传传基基因因，它它的的所所有有可可能能取取值值称称为为等等位位基基因因，这这样，样，X就可看做是由就可看做是由n个遗传基因所组成的一个染色体。个遗传基因所组成的一个染色体。般般情情况况下下，染染色色体体的的长长度度n是是固固定定的的，但但对对一一些些问问题题n也也可可以以是是变变化化的。的。根根据据不不同同的的情情况况，这这里里的的等等位
27、位基基因因可可以以是是一一组组整整数数，也也可可以以是是某某一一范范围围内内的实数值，或者是纯粹的一个记号。的实数值，或者是纯粹的一个记号。最最简简单单的的等等位位基基因因是是由由0和和1这这两两个个整整数数组组成成的的。相相应应的的染染色色体体就就可可表表示示为为一个二进制符号串。一个二进制符号串。3.2遗传算法遗传算法概要概要2022/10/1326第26页，共209页，编辑于2022年，星期二这这种种编编码码所所形形成成的的排排列列形形式式X是是个个体体的的基基因因型型，与与它它对对应应的的X值值是是个个体体的的表现型表现型。通通常常个个体体的的表表现现型型和和其其基基因因型型是是一一一
28、一对对应应的的，但但有有时时也也允允许许基基因因型型和表现型是多对一的关系。和表现型是多对一的关系。染色休染色休X也称为个体也称为个体X。对对于于每每一一个个个个体体X，要要按按照照一一定定的的规规则则确确定定出出其其适适应应度度；个个体体的的适适应应度度与与其其对对应应的的个个体体表表现现型型X的的目目标标函函数数值值相相关关联联，X越越接接近近于于目目标函数的最优点，其适应度越大；反之，其适应度越小。标函数的最优点，其适应度越大；反之，其适应度越小。遗遗传传算算法法中中，决决策策变变量量X组组成成了了问问题题的的解解空空间间。对对问问题题最最优优解解的的搜搜索索是是通通过过对对染染色色体体
29、X的的搜搜索索过过程程来来进进行行的的，从从而而由由所所有有的的染染色色体体X就就组组成成了了问问题题的的搜搜索索空空间间。通通过过编编码码和和解解码码，使使得得问问题题的的解解空空间间和搜索空间一一对应。和搜索空间一一对应。3.2遗传算法遗传算法概要概要2022/10/1327第27页，共209页，编辑于2022年，星期二生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是出是出M个个体所组成的集合，称为个个体所组成的集合，称为群体群体。与与生生物物一一代代一一代代的的自自然然进进化化过过程程相相类类似似，遗遗传传算算法法的的
30、运运算算过过程程也也是是一一个个反反复复迭迭代代的的过过程程，第第t代代群群体体记记做做P(t)，经经过过一一代代遗遗传传和和进进化化后后，得得到到第第t+l代群体，它们也是由多个个体组成的集合，记做代群体，它们也是由多个个体组成的集合，记做P(t+1)。这这个个群群体体不不断断地地经经过过遗遗传传和和进进化化操操作作，并并且且每每次次都都按按照照优优胜胜劣劣汰汰的的规规则则将将适适应应度度较较高高的的个个体体更更多多地地遗遗传传到到下下一一代代，这这样样最最终终在在群群体体中中将将会会得得到到一一个个优优良良的个体的个体X，它所对应的表现型，它所对应的表现型X将达到或接近于问题的最优解将达到
31、或接近于问题的最优解X*。生生物物的的进进化化过过程程主主要要是是通通过过染染色色体体之之间间的的交交叉叉和和染染色色体体的的变变异异来来完完成成的的，与与此此相相对对应应，遗遗传传算算法法中中最最优优解解的的搜搜索索过过程程也也模模仿仿生生物物的的这这个个进进化化过过程程，使使用用所所谓谓的的遗遗传传算算子子(geneticoperators)作作用用于于群群体体P(t)中中，进进行行下下述述遗遗传操作，从而得到新一代群体传操作，从而得到新一代群体P(t+1)。3.2遗传算法遗传算法概要概要2022/10/1328第28页，共209页，编辑于2022年，星期二选选择择(selection)：
32、根根据据各各个个个个体体的的适适应应度度，按按照照一一定定的的规规则则或或方方法法，从第从第t代群体代群体P(t)中选择出一些优良的个体遗传到下一代群体中选择出一些优良的个体遗传到下一代群体P(t+1)中。中。交交叉叉(crossover)：将将群群体体P(t)内内的的各各个个个个体体随随机机搭搭配配成成对对，对对每每对对个个体体，以某个概率以某个概率(称为交叉概率，称为交叉概率，crossoverrate)交换它们之间的部分染色体。交换它们之间的部分染色体。变变异异(mutation)：对对群群体体P(t)中中的的每每一一个个个个体体，以以某某一一概概率率(称称为为变变异异概概率率，muta
33、tionrate)改改变变某某一一个个或或某某一一些些基基因因座座上上的的基基因因值值为为其其他他的的等等位位基因。基因。3.2遗传算法遗传算法概要概要2022/10/1329第29页，共209页，编辑于2022年，星期二使使用用上上述述三三种种遗遗传传算算子子(选选择择算算子子、交交叉叉算算子子、变变异异算算子子)的的遗遗传传算法的主要运算过程如下所述：算法的主要运算过程如下所述：步骤一：初始化。步骤一：初始化。设置进化代数计数器设置进化代数计数器t0；设置最大进化代数；设置最大进化代数T；随机生成；随机生成M个个体作为初个个体作为初始群体始群体P(0)。步骤二：个体评价。步骤二：个体评价。
34、计算群体计算群体P(t)中各个个体的适应度。中各个个体的适应度。步骤三：选择运算。步骤三：选择运算。将选择算子作用于群体。将选择算子作用于群体。3.2遗传算法遗传算法运算过程运算过程2022/10/1330第30页，共209页，编辑于2022年，星期二步骤四：交叉运算。步骤四：交叉运算。将交叉算子作用于群体。将交叉算子作用于群体。步骤五：变异运算。步骤五：变异运算。将变异算于作用于群体。将变异算于作用于群体。群体群体P(t)经过选择、交叉、变异运算之后得到下一代群体经过选择、交叉、变异运算之后得到下一代群体P(t+1)。步骤六：终止条件判断。步骤六：终止条件判断。若若t T，则：，则：tt+1
35、，转到步骤二。，转到步骤二。若若tT，则则以以进进化化过过程程中中所所得得到到的的具具有有最最大大适适应应度度的的个个体体作作为为最最优优解输出，终止计算。解输出，终止计算。3.2遗传算法遗传算法运算过程运算过程2022/10/1331第31页，共209页，编辑于2022年，星期二基基于于对对自自然然界界中中生生物物遗遗传传与与进进化化机机理理的的模模仿仿，针针对对不不向向的的问问题题，很很多多学学者者设设计计了了许许多多不不同同的的编编码码方方法法来来表表示示问问题题的的可可行行解解，开开发发出出了了许许多多种种不不同同的的遗遗传传算算子子来来模模仿仿不不同同环环境境下下的的生生物物遗遗传传
36、特特。这这样样，由由不不同同的的编编码码方方法和不同的遗传算子就构成了各种不同的遗传算法。法和不同的遗传算子就构成了各种不同的遗传算法。但但这这些些遗遗传传算算法法都都有有共共同同的的特特点点，即即通通过过对对生生物物遗遗传传和和进进化化过过程程中中选选择择、交交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现2022/10/1332第32页，共209页，编辑于2022年，星期二基基于于这这个个共共同同特特点点，Goldberg总总结结出出了了一一种种统统一一的的最最基基本
37、本的的遗遗传传算算法法基本遗传算法基本遗传算法(SimpleGeneticAlgorithms，简称，简称SGA)。基基本本遗遗传传算算法法使使用用固固定定长长度度的的二二进进制制符符号号串串来来表表示示群群体体中中的的个个体体，其其等等位位基基因因是是由由二二值值符符号号集集0，1所所组组成成的的。初初始始群群体体中中各各个个个个体体的的基基因值可用均匀分布的随机数来生成。因值可用均匀分布的随机数来生成。基基本本遗遗传传算算法法使使用用比比例例选选择择算算子子、单单点点交交叉叉算算子子和和基基本本位位变变异异算算子子这这三三种种基基本本遗遗传传算算子子，其其遗遗传传进进化化操操作作过过程程简
38、简单单，容容易易理理解解，是是其其他他一一些些遗遗传传算算法法的的雏雏形形和和基基础础，它它不不仅仅给给各各种种遗遗传传算算法法提提供供了了一一个个基基本本框框架架，同同时时也也具有一定的应用价值。具有一定的应用价值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现2022/10/1333第33页，共209页，编辑于2022年，星期二用二进制编码来离散自变量，码长根据离散精度来确定。用二进制编码来离散自变量，码长根据离散精度来确定。例如当自变量例如当自变量a的变化区间为的变化区间为amin，amax，当离散精度为，当离散精度为 时，码长时，码长m的计算公式为：的计算公式为：相应的解码
39、公式为：相应的解码公式为：3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现编码和解码编码和解码2022/10/1334第34页，共209页，编辑于2022年，星期二在在遗遗传传算算法法中中，以以个个体体适适应应度度的的大大小小来来确确定定该该个个体体被被遗遗传传到到下下一一代代群群体体中中的的概概率率。个个体体的的适适应应度度越越大大，该该个个体体被被遗遗传传到到下下一一代代的的概概率率也也越越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基基本本遗遗传传算算法法使使用用比比例例选选择择算算子子来来确确定定
40、群群体体中中各各个个个个体体遗遗传传到到下下一代群体中的数量。一代群体中的数量。为为正正确确计计算算不不同同情情况况下下各各个个个个体体的的遗遗传传概概率率，要要求求所所有有个个体体的的适适应应度度必必须须为正数或零，不能是负数。为正数或零，不能是负数。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价1/42022/10/1335第35页，共209页，编辑于2022年，星期二对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：负号就可将其转化为求目
41、标函数最大值的优化问题，即：minf(X)max(f(X)当优化目标是求函数最大值，并且目标函数总取正值时，可以直当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度接设定个体的适应度F(x)就等于相应的目标函数值就等于相应的目标函数值f(X)，即：，即：F(X)f(X)但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值。也有求函数最小值。上上面面两两式式保保证证不不了了所所有有情情况况下下个个体体的的适适应应度度都都是是非非负负数数这这个个要要求求。所所以以必必须须寻寻求求出出
42、一一种种通通用用且且有有效效的的由由目目标标函函数数值值到到个个体体适适应应度度之之间间的的转转换关系，由它来保证个体适应度总取非负值。换关系，由它来保证个体适应度总取非负值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价2/42022/10/1336第36页，共209页，编辑于2022年，星期二为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值之一将目标函数值f(X)变换为个体的适应度变换为个体的适应度F(x)。式中，式中，Cmin为一个适当地相对比较小的数，它可以用下面几种
43、方法之一为一个适当地相对比较小的数，它可以用下面几种方法之一来选择：来选择：方法一：对于求目标函数最大值的优化问题，变换方法为：方法一：对于求目标函数最大值的优化问题，变换方法为：预先指定的一个较小的数。预先指定的一个较小的数。进化到当前代为止的最小目标函数值。进化到当前代为止的最小目标函数值。当前代或最近几代群体中的最小目标函数值。当前代或最近几代群体中的最小目标函数值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价3/42022/10/1337第37页，共209页，编辑于2022年，星期二方法二：对于求目标函数最小值的优化问题，变换方法为：方法二：对于求目标
44、函数最小值的优化问题，变换方法为：式式中中，Cmax为为一一个个适适当当地地相相对对比比较较大大的的数数，它它可可以以用用下下面面几几种种方方法法之之一一来来选择：选择：预先指定的一个较大的数。预先指定的一个较大的数。进化到当前代为止的最大目标函数值。进化到当前代为止的最大目标函数值。前代或最近几代群体中的最大目标函数值。前代或最近几代群体中的最大目标函数值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价4/42022/10/1338第38页，共209页，编辑于2022年，星期二选选择择算算子子或或复复制制算算子子的的作作用用是是从从当当前前代代群群体体中中选选
45、择择出出一一些些比比较较优优良良的的个个体体，并并将将其其复复制制到到下下一一代代群群体体中中。最最常常用用和和最最基基本本的的选选择择算算子子是是比比例选择算子。例选择算子。比比例例选选择择实实际际上上是是一一种种有有退退还还随随机机选选择择，也也叫叫做做赌赌盘盘(Roulettewheel)选择，因为这种选择方式与赌博中的赌盘操作原理颇为相似。选择，因为这种选择方式与赌博中的赌盘操作原理颇为相似。所所谓谓比比例例选选择择算算子子，是是指指个个体体被被选选中中并并遗遗传传到到下下一一代代群群体体中中的的概概率率与与该该个个体体的适应度大小成正比。的适应度大小成正比。3.2遗传算法遗传算法基本
46、遗传算法的实现基本遗传算法的实现比例选择算子比例选择算子1/42022/10/1339第39页，共209页，编辑于2022年，星期二整整个个赌赌盘盘被被分分为为大大小小不不同同的的一一些些扇扇面面，分分别别对对应应着着价价值值各各不不相相同同的的一一些些赌赌博博物物品品。当当旋旋转转着着的的赌赌盘盘自自然然停停下下来来时时，其其指指针针所所指指扇扇面面上上的物品就归赌博者所有。的物品就归赌博者所有。虽虽然然赌赌盘盘的的指指针针具具体体停停止止在在哪哪一一个个扇扇面面是是无无法法预预测测的的，但但指指针针指指向向各各个个扇扇面面的的概概率率却却是是可可以以估估计计的的，它它与与各各个个扇扇面面的
47、的圆圆心心角角大大小小成成正正比比：圆圆心心角角越越大大，停在该扇面的可能性也越大；圆心角越小，停在该扇面的可能性也越小。停在该扇面的可能性也越大；圆心角越小，停在该扇面的可能性也越小。与与此此类类似似，在在遗遗传传算算法法中中，整整个个群群体体被被各各个个个个体体所所分分割割，各各个个个个体体的的适适应应度度在在全全部部个个体体的的适适应应度度之之和和中中所所占占比比例例也也大大小小不不一一，这这个个比比例例值值瓜瓜分分了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。3.2遗传算法遗传算法基本遗传算法的实现基本遗
48、传算法的实现比例选择算子比例选择算子2/42022/10/1340第40页，共209页，编辑于2022年，星期二金银铜铁102030403.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现比例选择算子比例选择算子3/42022/10/1341第41页，共209页，编辑于2022年，星期二令：3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现比例选择算子比例选择算子4/42022/10/1342第42页，共209页，编辑于2022年，星期二算子的具体执行过程如下算子的具体执行过程如下：(1)对群体中的个体进行两两随机配对。对群体中的个体进行两两随机配对。若群体的大小为若群体的大小为
49、M，则共有，则共有M/2对相互配对的个体组。其中对相互配对的个体组。其中x表示表示不大于不大于x的最大整数。的最大整数。(2)对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为点。若染色体的长度为n，则共有，则共有(n-1)个可能的交叉点位置。个可能的交叉点位置。(3)对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。换两个个体的部分染色体，从而产生出两个新的个体。3.2遗传算法遗传算法基本遗
50、传算法的实现基本遗传算法的实现单点交叉算子单点交叉算子1/22022/10/1343第43页，共209页，编辑于2022年，星期二单点交叉示意如下所示：单点交叉示意如下所示：A：1011011100A：1011011111B：0001110011B；0001110000单点交叉单点交叉交叉点交叉点3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现单点交叉算子单点交叉算子2/22022/10/1344第44页，共209页，编辑于2022年，星期二对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的