第三章求解优化问题的智能算法精选文档.ppt

《第三章求解优化问题的智能算法精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章求解优化问题的智能算法精选文档.ppt（209页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章求解优化问题的智能算法2023/1/91本讲稿第一页，共二百零九页3.1 概述概述2023/1/92本讲稿第二页，共二百零九页最最优优化化问问题题是是指指在在一一定定的的约约束束条条件件下下，决决定定某某个个或或某某些些可可控控制制的的因因素素应应有有的的合合理理取取值值，使使所所选选定定的的目目标标达达到到最最优优的的问问题题。解解决决最最优优化化问问题题的的方方法法称称为为最最优优化化方方法法。它它具具有有高高度度应应用用性性和和技技术术性性的的特点。特点。最最优优化化问问题题可可以以追追溯溯到到十十分分古古老老的的极极值值问问题题，在在17世世纪纪，伟伟大大科科学学家家Newton

2、发发明明微微积积分分的的时时候候，已已经经提提出出了了极极值值问问题题，后后来来又又出出现现了了Lagrange乘乘子子法法，Cauchy则则利利用用最最速速下下降降法法求求解解无无约约束束极极小小化化问问题题。然然而而，直直到到1947年年Dantzig提提出出求求解解一一般般线线性性规规划划问问题题的的单单纯纯形形法法之之后后，它它才成为一门独立的学科。才成为一门独立的学科。3.1概述概述最优化方法的研究起源和意义最优化方法的研究起源和意义1/22023/1/93本讲稿第三页，共二百零九页随随着着近近代代科科学学技技术术发发展展的的需需要要，特特别别是是由由于于计计算算机机技技术术的的飞飞

3、速速发发展展，促促进了最优化方法的迅速发展，并很快渗透到各个领域。进了最优化方法的迅速发展，并很快渗透到各个领域。20世世纪纪70年年代代，最最优优化化方方法法这这门门应应用用技技术术科科学学又又开开始始产产生生出出最最优优设设计计、最最优优控控制制与与最最优优管管理理等等分分支支。到到20世世纪纪80年年代代，最最优优化化技技术术又又在在这这些些分分支支中中发发展展出出了了新新的的更更细细的的分分支支，比比如如，工工程程技技术术领领域域的的机机械械优优化化设设计计、建筑结构优化设计以及化工石油领域的优化设计等。建筑结构优化设计以及化工石油领域的优化设计等。3.1概述概述最优化方法的研究起源和

4、意义最优化方法的研究起源和意义2/22023/1/94本讲稿第四页，共二百零九页求解优化问题的步骤求解优化问题的步骤(1)分析待优化的问题，建立问题的数学模型；分析待优化的问题，建立问题的数学模型；(2)分析数学模型，选择合适的最优化算法；分析数学模型，选择合适的最优化算法；(3)编写计算机程序、上机计算、求出最优解；编写计算机程序、上机计算、求出最优解；(4)结果检验与最后决策。结果检验与最后决策。2023/1/95本讲稿第五页，共二百零九页转化为最小化问题。3.1概述概述最优化问题的数学描述最优化问题的数学描述2023/1/96本讲稿第六页，共二百零九页(1)枚举法。枚举法。枚举出可行解集

5、合内的所有可行解，以求出精确最优解。对于连续函数，枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。有时甚至在目前最先进的计算工具上都无法求解。(2)启发式算法。启发式算法。寻寻求求一一种种能能产产生生可可行行解解的的启启发发式式规规则则，以以找找到到一一个个最最优优解解或或近近似似最最优

6、优解解。该该方方法法的的求求解解效效率率虽虽然然比比较较高高，但但对对每每一一个个需需要要求求解解的的问问题题都都必必须须找找出出其其特特有有的的启启发发式式规规则则，这这个个启启发发式式规规则则无无通通用用性性，不不适适合于其他问题。合于其他问题。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法1/22023/1/97本讲稿第七页，共二百零九页(3)搜搜索索算算法法。寻寻求求一一种种搜搜索索算算法法，该该算算法法在在可可行行解解集集合合的的一一个个子子集集内内进进行行搜搜索索操操作作，以以找找到到问问题题的的最最优优解解或或近近似似最最优优解解。该该方方法法虽虽然然保保证证

7、不不了了一一定定能能够够得得到到问问题题的的最最优优解解，但但若若适适当当地地利利用用一一些些启启发发知知识识，就可在近似解的质量和求解效率上达到就可在近似解的质量和求解效率上达到种较好的平衡。种较好的平衡。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法2/22023/1/98本讲稿第八页，共二百零九页以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下：点。这些算法的基本迭

8、代步骤如下：3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法2023/1/99本讲稿第九页，共二百零九页3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法最速下降法最速下降法2023/1/910本讲稿第十页，共二百零九页3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法牛顿法牛顿法2023/1/911本讲稿第十一页，共二百零九页3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法共轭方向法共轭方向法2023/1/912本讲稿第十二页，共二百零九页l对目标函数和约束函数表达的要求必须更为宽松对目标函数和约束函数表达的要求必须更为宽松l计算的效率比理

9、论上的最优性更重要计算的效率比理论上的最优性更重要l算法随时终止能够随时得到较好的解算法随时终止能够随时得到较好的解l对优化模型中数据的质量要求更为宽松对优化模型中数据的质量要求更为宽松实实际际生生活活中中对对最最优优化化方方法法性性能能的的需需求求促促进进了了最最优优化化方方法法的的发发展展，最最优优化化逐逐步步走走出出“象象牙牙塔塔”，面面向向实实际际需需要要，完完成成了了从从“方方法法定定向向”到到“问题定向问题定向”的转换。的转换。3.1概述概述对最优化提出的新的需求对最优化提出的新的需求2023/1/913本讲稿第十三页，共二百零九页l1975年年，Holland提提出出遗遗传传算算

10、法法(GeneticAlgorithm)。这这种种优优化化方方法法模模仿仿生生物物种种群群中中优优胜胜劣劣汰汰的的选选择择机机制制，通通过过种种群群中中优优势势个个体体的的繁衍进化来实现优化的功能。繁衍进化来实现优化的功能。l1977年年，Glover提提出出禁禁忌忌搜搜索索(TabuSearch)算算法法。这这种种方方法法将将记记忆忆功功能能引引入入到到最最优优解解的的搜搜索索过过程程中中，通通过过设设置置禁禁忌忌区区阻阻止止搜搜索索过过程程中中的的重重复复，从而大大提高了寻优过程的搜索效率。从而大大提高了寻优过程的搜索效率。l1983年年，Kirkpatrick提提出出了了模模拟拟退退火火

11、(SimulatedAnnealing)算算法法。这这种种算算法法模模拟拟热热力力学学中中退退火火过过程程能能使使金金属属原原子子达达到到能能量量最最低低状状态态的的机机制制，通通过过模模拟拟的的降降温温过过程程，按按玻玻兹兹曼曼(Boltzmann)方方程程计计算算状状态态间间的的转转移移概概率率来来引引导导搜搜索索，从从而而使使算算法法具具有有很很好好的的全全局局搜搜索索能能力。力。3.1概述概述新的优化方法不断出现新的优化方法不断出现1/22023/1/914本讲稿第十四页，共二百零九页l20世世 纪纪 90年年 代代 初初，Dorigo等等 提提 出出 蚁蚁 群群 优优 化化 算算 法

12、法(Ant ColonyOptimization)算算法法。这这种种算算法法借借鉴鉴蚁蚁群群群群体体利利用用信信息息素素相相互互传传递递信信息息来来实实现现路路径径优优化化的的机机理理，通通过过记记忆忆路路径径信信息息素素的的变变化化来来解解决决组合优化问题。组合优化问题。l1995年年，Kenedy和和 Eberhart提提 出出粒粒 子子 群群 优优 化化(Particle SwarmOptimization)算算法法。这这种种方方法法模模仿仿鸟鸟类类和和鱼鱼类类群群体体觅觅食食迁迁移移中中，个个体体与与群群体体协协调调一一致致的的机机理理，通通过过群群体体最最优优方方向向、个个体体最最优

13、优方方向向和和惯惯性性方方向向的的协调来求解实数优化问题。协调来求解实数优化问题。l1999年年，Linhares提提出出了了捕捕食食搜搜索索(PredatorySearch)算算法法。这这种种算算法法模模拟拟猛猛兽兽捕捕食食中中大大范范围围搜搜寻寻和和局局部部蹲蹲守守的的特特点点，通通过过设设置置全全局局搜搜索索和和局局部部搜搜索索间间变变换换的的阈阈值值来来协协调调两两种种不不同同的的搜搜索索模模式式，从从而而实实现现了了对对全全局局搜索能力和局部搜索能力的兼顾。搜索能力和局部搜索能力的兼顾。3.1概述概述新的优化方法不断出现新的优化方法不断出现2/22023/1/915本讲稿第十五页，共

14、二百零九页l不不以以达达到到某某个个最最优优性性条条件件或或找找到到理理论论上上的的精精确确最最优优解解为为目目标标，而而是是更看重计算的速度和效率；更看重计算的速度和效率；l对目标函数和约束函数的要求十分宽松；对目标函数和约束函数的要求十分宽松；l算法的基本思想都是来自对某种自然规律的模仿，具有人工智能的特点；算法的基本思想都是来自对某种自然规律的模仿，具有人工智能的特点；l多多数数算算法法含含有有一一个个多多个个体体的的群群体体，寻寻优优过过程程实实际际上上就就是是种种群群的的进进化化过过程；程；l理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。理论工作相对比较薄弱，一般说来都不能保

15、证收敛到最优解。3.1概述概述新的算法的一些共同特点新的算法的一些共同特点2023/1/916本讲稿第十六页，共二百零九页l由由 于于 算算 法法 理理 论论 薄薄 弱弱，最最 早早 被被 称称 为为“现现 代代 启启 发发 式式(ModernHeuristics)”或或“高级启发式高级启发式(AdvancedHeuristics)”；l从从 其其 人人 工工 智智 能能 的的 特特 点点，被被 称称 为为“智智 能能 计计 算算(IntelligentComputation)”或或“智智 能能 优优 化化 算算 法法(Intelligent OptimizationAlgorithms)”；

16、l从从不不以以精精确确解解为为目目标标的的特特点点，又又被被归归到到“软软计计算算(SoftComputing)”方法中；方法中；l从从 种种 群群 进进 化化 的的 特特 点点 看看，它它 们们 又又 可可 以以 称称 为为“进进 化化 计计 算算(EvolutionaryCompuation)”；l从从模模仿仿自自然然规规律律的的特特点点出出发发，又又有有人人将将它它们们称称为为“自自然然计计算算(NaturalComputing)”。3.1概述概述新的优化方法的不同名称新的优化方法的不同名称2023/1/917本讲稿第十七页，共二百零九页l应用智能优化算法解决各类问题是重点；应用智能优化

17、算法解决各类问题是重点；l算法改进有很大的创新空间；算法改进有很大的创新空间；l多种算法结合的混合算法是一条捷径；多种算法结合的混合算法是一条捷径；l不提倡刻意去追求理论成果；不提倡刻意去追求理论成果；l算法性能的测算是一项要下真功夫的工作；算法性能的测算是一项要下真功夫的工作；l选选择择测测试试例例题题的的一一般般规规律律：网网上上题题库库中中的的例例题题文文献献中中的的例例题题随随机产生的例题机产生的例题实际应用问题实际应用问题自己编的例题；自己编的例题；l算算法法性性能能测测试试的的主主要要指指标标：达达优优率率(解解的的目目标标平平均均值值和和最最优优解解的的目目标标值值的的比，所有解

18、的目标值的标准差等比，所有解的目标值的标准差等)，计算速度，计算大规模问题的能力；，计算速度，计算大规模问题的能力；l创造出新算法创造出新算法3.1概述概述怎样学习研究智能优化方法怎样学习研究智能优化方法2023/1/918本讲稿第十八页，共二百零九页3.2 遗传算法遗传算法2023/1/919本讲稿第十九页，共二百零九页生生物物在在自自然然界界中中的的生生存存繁繁衍衍，显显示示出出了了其其对对自自然然环环境境的的优优异异自自适适应应能能力力。受受其其启启发发，人人们们致致力力于于对对生生物物各各种种生生存存特特性性的的机机理理研研究究和和行行为为模模拟拟，为为人工自适应系统的设计和开发提供了

19、广阔的前景。人工自适应系统的设计和开发提供了广阔的前景。遗遗传传算算法法(GeneticAlgorithm，简简称称GA)就就是是这这种种生生物物行行为为的的计计算算机机模模拟拟中中令人瞩目的重要成果。令人瞩目的重要成果。基基于于对对生生物物遗遗传传和和进进化化过过程程的的计计算算机机模模拟拟，遗遗传传算算法法使使得得各各种种人人工工系统具有优良的自适应能力和优化能力。系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传算法所借鉴的生物学基础就是生物的遗传和进化。3.2遗传算法遗传算法概要概要2023/1/920本讲稿第二十页，共二百零九页虽虽然然人人们们还

20、还未未完完全全揭揭开开遗遗传传与与进进化化的的奥奥秘秘，既既没没有有完完全全掌掌握握其其机机制制，也也不不完完全全清清楚楚染染色色体体编编码码和和译译码码过过程程的的细细节节，更更不不完完全全了了解解其其控控制制方式，但遗传与进化的以下几个特点却为人们所共识：方式，但遗传与进化的以下几个特点却为人们所共识：(1)生生物物的的所所有有遗遗传传信信息息都都包包含含在在其其染染色色休休中中，染染色色体体决决定定了了生生物物的的性状。性状。(2)染染色色体体是是由由基基因因及及其其有有规规律律的的排排列列所所构构成成的的，遗遗传传和和进进化化过过程程发发生生在在染染色体上。色体上。(3)生物的繁殖过程

21、是由其基因的复制过程来完成的：生物的繁殖过程是由其基因的复制过程来完成的：(4)通通过过同同源源染染色色体体之之间间的的交交叉叉或或染染色色体体的的变变异异会会产产生生新新的的物物种种，使使生生物物呈呈现新的性状。现新的性状。(5)对对环环境境适适应应性性好好的的基基因因或或染染色色体体经经常常比比适适应应性性差差的的基基因因或或染染色色体体有有更多的机会遗传到下一代。更多的机会遗传到下一代。3.2遗传算法遗传算法概要概要2023/1/921本讲稿第二十一页，共二百零九页遗遗传传算算法法是是模模拟拟生生物物在在自自然然环环境境下下的的遗遗传传和和进进化化过过程程而而形形成成的的一一种自适应全局

22、优化概率搜索算法。种自适应全局优化概率搜索算法。它它最最早早由由美美国国密密执执安安大大学学的的Holland教教授授提提出出，起起源源于于60年年代代对对自自然然和和人人工工自适应系统的研究。自适应系统的研究。70年年代代DeJong基基于于遗遗传传算算法法的的思思想想在在计计算算机机上上进进行行了了大大量量的的纯纯数数值函数优化计算实验。值函数优化计算实验。在在一一系系列列研研究究工工作作的的基基础础上上，80年年代代由由Goldberg进进行行归归纳纳总总结结，形形成成了遗传算法的基本框架。了遗传算法的基本框架。3.2遗传算法遗传算法概要概要2023/1/922本讲稿第二十二页，共二百零

23、九页式中，式中，为决策变量，为决策变量，f(X)为目标函数，后两个式为目标函数，后两个式子为约束条件，子为约束条件，U是基本空间，是基本空间，R是是U的一个子集。的一个子集。对于一个求函数最大值的优化问题对于一个求函数最大值的优化问题(求函数最小值也类同求函数最小值也类同)，一般可，一般可描述为下述数学规划模型：描述为下述数学规划模型：满满足足约约束束条条件件的的解解X称称为为可可行行解解，集集合合R表表示示由由所所有有满满足足约约束束条条件件的的解解所所组组成成的的一一个个集集合合，叫叫做做可可行行解解集集合合。它它们们之之间间的的关关系系如如图图所示。所示。3.2遗传算法遗传算法概要概要2

24、023/1/923本讲稿第二十三页，共二百零九页U基本空间基本空间R可行解集合可行解集合X可行解可行解3.2遗传算法遗传算法概要概要2023/1/924本讲稿第二十四页，共二百零九页对对于于上上述述最最优优化化问问题题，目目标标函函数数和和约约束束条条件件种种类类繁繁多多，有有的的是是线线性性的的，有有的的是是非非线线性性的的；有有的的是是连连续续的的，有有的的是是离离散散的的；有有的的是是单单峰峰值值的的，有有的的是是多峰值的。多峰值的。随随着着研研究究的的深深入入，人人们们逐逐渐渐认认识识到到在在很很多多复复杂杂情情况况下下要要想想完完全全精精确确地地求求出出其其最最优优解解既既不不可可能

25、能，也也不不现现实实，因因而而求求出出其其近近似似最最优优解解或或满满意意解解是人们的主要着眼点之一。是人们的主要着眼点之一。3.2遗传算法遗传算法概要概要2023/1/925本讲稿第二十五页，共二百零九页遗遗传传算算法法中中，将将n维维决决策策向向量量用用n个个记记号号xi(n=l，2，n)所组成的符号串所组成的符号串X来表示：来表示：把把每每一一个个xi看看作作一一个个遗遗传传基基因因，它它的的所所有有可可能能取取值值称称为为等等位位基基因因，这这样，样，X就可看做是由就可看做是由n个遗传基因所组成的一个染色体。个遗传基因所组成的一个染色体。般般情情况况下下，染染色色体体的的长长度度n是是

26、固固定定的的，但但对对一一些些问问题题n也也可可以以是是变变化的。化的。根根据据不不同同的的情情况况，这这里里的的等等位位基基因因可可以以是是一一组组整整数数，也也可可以以是是某某一一范围内的实数值，或者是纯粹的一个记号。范围内的实数值，或者是纯粹的一个记号。最最简简单单的的等等位位基基因因是是由由0和和1这这两两个个整整数数组组成成的的。相相应应的的染染色色体体就就可可表示为一个二进制符号串。表示为一个二进制符号串。3.2遗传算法遗传算法概要概要2023/1/926本讲稿第二十六页，共二百零九页这这种种编编码码所所形形成成的的排排列列形形式式X是是个个体体的的基基因因型型，与与它它对对应应的

27、的X值值是是个个体体的的表现型表现型。通通常常个个体体的的表表现现型型和和其其基基因因型型是是一一一一对对应应的的，但但有有时时也也允允许许基基因因型型和表现型是多对一的关系。和表现型是多对一的关系。染色休染色休X也称为个体也称为个体X。对对于于每每一一个个个个体体X，要要按按照照一一定定的的规规则则确确定定出出其其适适应应度度；个个体体的的适适应应度度与与其其对对应应的的个个体体表表现现型型X的的目目标标函函数数值值相相关关联联，X越越接接近近于于目目标标函函数数的的最最优优点点，其适应度越大；反之，其适应度越小。其适应度越大；反之，其适应度越小。遗遗传传算算法法中中，决决策策变变量量X组组

28、成成了了问问题题的的解解空空间间。对对问问题题最最优优解解的的搜搜索索是是通通过过对对染染色色体体X的的搜搜索索过过程程来来进进行行的的，从从而而由由所所有有的的染染色色体体X就就组组成成了了问问题题的的搜搜索索空空间间。通通过过编编码码和和解解码码，使使得得问问题题的的解解空空间间和和搜搜索索空空间一一对应。间一一对应。3.2遗传算法遗传算法概要概要2023/1/927本讲稿第二十七页，共二百零九页生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是出生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是出M个个体所组成的集合，称为个个体所组成的集合，称为群体群体。与与生生物物

29、一一代代一一代代的的自自然然进进化化过过程程相相类类似似，遗遗传传算算法法的的运运算算过过程程也也是是一一个个反反复复迭迭代代的的过过程程，第第t代代群群体体记记做做P(t)，经经过过一一代代遗遗传传和和进进化化后后，得到第得到第t+l代群体，它们也是由多个个体组成的集合，记做代群体，它们也是由多个个体组成的集合，记做P(t+1)。这这个个群群体体不不断断地地经经过过遗遗传传和和进进化化操操作作，并并且且每每次次都都按按照照优优胜胜劣劣汰汰的的规规则则将将适适应应度度较较高高的的个个体体更更多多地地遗遗传传到到下下一一代代，这这样样最最终终在在群群体体中中将将会会得得到到一一个个优良的个体优良

30、的个体X，它所对应的表现型，它所对应的表现型X将达到或接近于问题的最优解将达到或接近于问题的最优解X*。生生物物的的进进化化过过程程主主要要是是通通过过染染色色体体之之间间的的交交叉叉和和染染色色体体的的变变异异来来完完成成的的，与与此此相相对对应应，遗遗传传算算法法中中最最优优解解的的搜搜索索过过程程也也模模仿仿生生物物的的这这个个进进化化过过程程，使使用用所所谓谓的的遗遗传传算算子子(geneticoperators)作作用用于于群群体体P(t)中中，进进行行下下述述遗遗传传操操作，从而得到新一代群体作，从而得到新一代群体P(t+1)。3.2遗传算法遗传算法概要概要2023/1/928本讲

31、稿第二十八页，共二百零九页选选择择(selection)：根根据据各各个个个个体体的的适适应应度度，按按照照一一定定的的规规则则或或方方法法，从从第第t代群体代群体P(t)中选择出一些优良的个体遗传到下一代群体中选择出一些优良的个体遗传到下一代群体P(t+1)中。中。交交叉叉(crossover)：将将群群体体P(t)内内的的各各个个个个体体随随机机搭搭配配成成对对，对对每每对对个个体体，以某个概率以某个概率(称为交叉概率，称为交叉概率，crossoverrate)交换它们之间的部分染色体。交换它们之间的部分染色体。变变异异(mutation)：对对群群体体P(t)中中的的每每一一个个个个体体

32、，以以某某一一概概率率(称称为为变变异异概概率率，mutationrate)改改变变某某一一个个或或某某一一些些基基因因座座上上的的基基因因值值为为其其他他的的等等位位基因。基因。3.2遗传算法遗传算法概要概要2023/1/929本讲稿第二十九页，共二百零九页使使用用上上述述三三种种遗遗传传算算子子(选选择择算算子子、交交叉叉算算子子、变变异异算算子子)的的遗遗传传算算法法的的主主要运算过程如下所述：要运算过程如下所述：步骤一：初始化。步骤一：初始化。设置进化代数计数器设置进化代数计数器t0；设置最大进化代数；设置最大进化代数T；随机生成；随机生成M个个体个个体作为初始群体作为初始群体P(0)

33、。步骤二：个体评价。步骤二：个体评价。计算群体计算群体P(t)中各个个体的适应度。中各个个体的适应度。步骤三：选择运算。步骤三：选择运算。将选择算子作用于群体。将选择算子作用于群体。3.2遗传算法遗传算法运算过程运算过程2023/1/930本讲稿第三十页，共二百零九页步骤四：交叉运算。步骤四：交叉运算。将交叉算子作用于群体。将交叉算子作用于群体。步骤五：变异运算。步骤五：变异运算。将变异算于作用于群体。将变异算于作用于群体。群体群体P(t)经过选择、交叉、变异运算之后得到下一代群体经过选择、交叉、变异运算之后得到下一代群体P(t+1)。步骤六：终止条件判断。步骤六：终止条件判断。若若t T，则

34、：，则：tt+1，转到步骤二。，转到步骤二。若若tT，则则以以进进化化过过程程中中所所得得到到的的具具有有最最大大适适应应度度的的个个体体作作为为最最优优解解输出，终止计算。输出，终止计算。3.2遗传算法遗传算法运算过程运算过程2023/1/931本讲稿第三十一页，共二百零九页基基于于对对自自然然界界中中生生物物遗遗传传与与进进化化机机理理的的模模仿仿，针针对对不不向向的的问问题题，很很多多学学者者设设计计了了许许多多不不同同的的编编码码方方法法来来表表示示问问题题的的可可行行解解，开开发发出出了了许许多多种种不不同同的的遗遗传传算算子子来来模模仿仿不不同同环环境境下下的的生生物物遗遗传传特特

35、。这这样样，由由不不同同的的编编码码方方法和不同的遗传算子就构成了各种不同的遗传算法。法和不同的遗传算子就构成了各种不同的遗传算法。但但这这些些遗遗传传算算法法都都有有共共同同的的特特点点，即即通通过过对对生生物物遗遗传传和和进进化化过过程程中中选选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现2023/1/932本讲稿第三十二页，共二百零九页基基于于这这个个共共同同特特点点，Goldberg总总结结出出了了一一种种统统一一的的最最基基本本的的遗遗传传算算法法

36、基本遗传算法基本遗传算法(SimpleGeneticAlgorithms，简称，简称SGA)。基基本本遗遗传传算算法法使使用用固固定定长长度度的的二二进进制制符符号号串串来来表表示示群群体体中中的的个个体体，其其等等位位基基因因是是由由二二值值符符号号集集0，1所所组组成成的的。初初始始群群体体中中各各个个个个体体的的基因值可用均匀分布的随机数来生成。基因值可用均匀分布的随机数来生成。基基本本遗遗传传算算法法使使用用比比例例选选择择算算子子、单单点点交交叉叉算算子子和和基基本本位位变变异异算算子子这这三三种种基基本本遗遗传传算算子子，其其遗遗传传进进化化操操作作过过程程简简单单，容容易易理理解

37、解，是是其其他他一一些些遗遗传传算算法法的的雏雏形形和和基基础础，它它不不仅仅给给各各种种遗遗传传算算法法提提供供了了一一个个基基本本框框架，同时也具有一定的应用价值。架，同时也具有一定的应用价值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现2023/1/933本讲稿第三十三页，共二百零九页用二进制编码来离散自变量，码长根据离散精度来确定。用二进制编码来离散自变量，码长根据离散精度来确定。例如当自变量例如当自变量a的变化区间为的变化区间为amin，amax，当离散精度为，当离散精度为 时，码长时，码长m的计算公式为：的计算公式为：相应的解码公式为：相应的解码公式为：3.2遗传算法

38、遗传算法基本遗传算法的实现基本遗传算法的实现编码和解码编码和解码2023/1/934本讲稿第三十四页，共二百零九页在在遗遗传传算算法法中中，以以个个体体适适应应度度的的大大小小来来确确定定该该个个体体被被遗遗传传到到下下一一代代群群体体中中的的概概率率。个个体体的的适适应应度度越越大大，该该个个体体被被遗遗传传到到下下一一代代的的概概率率也也越越大大；反反之之，个个体体的的适适应应度度越越小小，该该个个体体被被遗遗传传到到下下一一代代的的概概率率也越小。也越小。基基本本遗遗传传算算法法使使用用比比例例选选择择算算子子来来确确定定群群体体中中各各个个个个体体遗遗传传到到下下一一代代群群体体中的数

39、量。中的数量。为为正正确确计计算算不不同同情情况况下下各各个个个个体体的的遗遗传传概概率率，要要求求所所有有个个体体的的适适应应度度必必须为正数或零，不能是负数。须为正数或零，不能是负数。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价1/42023/1/935本讲稿第三十五页，共二百零九页对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：号就可将其转化为求目标函数最大值的优化问题，即：minf(X)max(f(X)当优化目标是求函数最大值，并

40、且目标函数总取正值时，可以直接设定当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度个体的适应度F(x)就等于相应的目标函数值就等于相应的目标函数值f(X)，即：，即：F(X)f(X)但实际优化问题中的目标函数值有正也有负，优化目标有求函数最但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值。大值，也有求函数最小值。上上面面两两式式保保证证不不了了所所有有情情况况下下个个体体的的适适应应度度都都是是非非负负数数这这个个要要求求。所所以以必必须须寻寻求求出出一一种种通通用用且且有有效效的的由由目目标标函函数数值值到到个个体体适适应应度度之之间

41、间的转换关系，由它来保证个体适应度总取非负值。的转换关系，由它来保证个体适应度总取非负值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价2/42023/1/936本讲稿第三十六页，共二百零九页为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值之一将目标函数值f(X)变换为个体的适应度变换为个体的适应度F(x)。式中，式中，Cmin为一个适当地相对比较小的数，它可以用下面几种方法之一来为一个适当地相对比较小的数，它可以用下面几种方法之一来选择：选择：方法一：对于求目标函数最大值的

42、优化问题，变换方法为：方法一：对于求目标函数最大值的优化问题，变换方法为：预先指定的一个较小的数。预先指定的一个较小的数。进化到当前代为止的最小目标函数值。进化到当前代为止的最小目标函数值。当前代或最近几代群体中的最小目标函数值。当前代或最近几代群体中的最小目标函数值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价3/42023/1/937本讲稿第三十七页，共二百零九页方法二：对于求目标函数最小值的优化问题，变换方法为：方法二：对于求目标函数最小值的优化问题，变换方法为：式式中中，Cmax为为一一个个适适当当地地相相对对比比较较大大的的数数，它它可可以以用用下下

43、面面几几种种方方法法之一来选择：之一来选择：预先指定的一个较大的数。预先指定的一个较大的数。进化到当前代为止的最大目标函数值。进化到当前代为止的最大目标函数值。前代或最近几代群体中的最大目标函数值。前代或最近几代群体中的最大目标函数值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价4/42023/1/938本讲稿第三十八页，共二百零九页选选择择算算子子或或复复制制算算子子的的作作用用是是从从当当前前代代群群体体中中选选择择出出一一些些比比较较优优良良的的个个体体，并并将将其其复复制制到到下下一一代代群群体体中中。最最常常用用和和最最基基本本的的选选择择算算子子是

44、是比比例选择算子。例选择算子。比比例例选选择择实实际际上上是是一一种种有有退退还还随随机机选选择择，也也叫叫做做赌赌盘盘(Roulettewheel)选择，因为这种选择方式与赌博中的赌盘操作原理颇为相似。选择，因为这种选择方式与赌博中的赌盘操作原理颇为相似。所所谓谓比比例例选选择择算算子子，是是指指个个体体被被选选中中并并遗遗传传到到下下一一代代群群体体中中的的概概率率与与该个体的适应度大小成正比。该个体的适应度大小成正比。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现比例选择算子比例选择算子1/42023/1/939本讲稿第三十九页，共二百零九页整整个个赌赌盘盘被被分分为为大大小

45、小不不同同的的一一些些扇扇面面，分分别别对对应应着着价价值值各各不不相相同同的的一一些些赌赌博博物物品品。当当旋旋转转着着的的赌赌盘盘自自然然停停下下来来时时，其其指指针针所所指指扇扇面面上上的物品就归赌博者所有。的物品就归赌博者所有。虽虽然然赌赌盘盘的的指指针针具具体体停停止止在在哪哪一一个个扇扇面面是是无无法法预预测测的的，但但指指针针指指向向各各个个扇扇面面的的概概率率却却是是可可以以估估计计的的，它它与与各各个个扇扇面面的的圆圆心心角角大大小小成成正正比比：圆圆心心角角越越大大，停停在在该该扇扇面面的的可可能能性性也也越越大大；圆圆心心角角越越小小，停停在在该该扇扇面面的的可可能能性也

46、越小。性也越小。与与此此类类似似，在在遗遗传传算算法法中中，整整个个群群体体被被各各个个个个体体所所分分割割，各各个个个个体体的的适适应应度度在在全全部部个个体体的的适适应应度度之之和和中中所所占占比比例例也也大大小小不不一一，这这个个比比例例值值瓜瓜分分了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现比例选择算子比例选择算子2/42023/1/940本讲稿第四十页，共二百零九页金银铜铁102030403.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实

47、现比例选择算子比例选择算子3/42023/1/941本讲稿第四十一页，共二百零九页令：3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现比例选择算子比例选择算子4/42023/1/942本讲稿第四十二页，共二百零九页算子的具体执行过程如下算子的具体执行过程如下：(1)对群体中的个体进行两两随机配对。对群体中的个体进行两两随机配对。若群体的大小为若群体的大小为M，则共有，则共有M/2对相互配对的个体组。其中对相互配对的个体组。其中x表示不表示不大于大于x的最大整数。的最大整数。(2)对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。对每一对相互配对的个体，随机设置某一基因座之

48、后的位置为交叉点。若染色体的长度为若染色体的长度为n，则共有，则共有(n-1)个可能的交叉点位置。个可能的交叉点位置。(3)对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。交换两个个体的部分染色体，从而产生出两个新的个体。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现单点交叉算子单点交叉算子1/22023/1/943本讲稿第四十三页，共二百零九页单点交叉示意如下所示：单点交叉示意如下所示：A：1011011100A：1011011111B：0001110011B；0

49、001110000单点交叉单点交叉交叉点交叉点3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现单点交叉算子单点交叉算子2/22023/1/944本讲稿第四十四页，共二百零九页对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为，则变异操作将该基因值变为1；反之，若原有基因值为；反之，若原有基因值为l，则变异操作将其变为，则变异操作将其变为0。A：10l0101010A：10l0001010基本位变异基本位变异变异点变异

50、点(1)对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率pm指定其为变异点。指定其为变异点。(2)对每一个指定的变异点，对其基因值做取反运算或用其它等位基对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。因值来代替，从而产生出一个新的个体。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现基本位变异算子基本位变异算子2023/1/945本讲稿第四十五页，共二百零九页基本遗传算法有下述基本遗传算法有下述4个运行参数需要提前设定：个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为：群体大小，即群体中所含个体的数量