第三章求解优化问题的智能算法课件.ppt

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

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

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

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

4、1/24/20234求解优化问题的步骤求解优化问题的步骤(1)分析待优化的问题，建立问题的数学模型；分析待优化的问题，建立问题的数学模型；(2)分析数学模型，选择合适的最优化算法；分析数学模型，选择合适的最优化算法；(3)编写计算机程序、上机计算、求出最优解；编写计算机程序、上机计算、求出最优解；(4)结果检验与最后决策。结果检验与最后决策。1/24/20235转化为最小化问题。3.1概述概述最优化问题的数学描述最优化问题的数学描述1/24/20236(1)枚举法。枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该

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

6、题都都必必须须找找出出其其特特有有的的启启发发式式规规则则，这这个个启启发发式式规规则则无无通通用用性性，不适合于其他问题。不适合于其他问题。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法1/21/24/20237(3)搜搜索索算算法法。寻寻求求一一种种搜搜索索算算法法，该该算算法法在在可可行行解解集集合合的的一一个个子子集集内内进进行行搜搜索索操操作作，以以找找到到问问题题的的最最优优解解或或近近似似最最优优解解。该该方方法法虽虽然然保保证证不不了了一一定定能能够够得得到到问问题题的的最最优优解解，但但若若适适当当地地利利用用一一些些启启发发知知识识，就就可可在在近近似似

7、解解的的质质量量和和求求解解效效率率上上达达到到种种较较好好的的平衡。平衡。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法2/21/24/20238以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具有完善的数学基础，具有计算效率高、可靠性强和比较成熟具有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下：等特点。这些算法的基本迭代步骤如下：3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法1/24/202393.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法

8、最速下降法最速下降法1/24/2023103.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法牛顿法牛顿法1/24/2023113.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法共轭方向法共轭方向法1/24/202312l对目标函数和约束函数表达的要求必须更为宽松对目标函数和约束函数表达的要求必须更为宽松l计算的效率比理论上的最优性更重要计算的效率比理论上的最优性更重要l算法随时终止能够随时得到较好的解算法随时终止能够随时得到较好的解l对优化模型中数据的质量要求更为宽松对优化模型中数据的质量要求更为宽松实实际际生生活活中中对对最最优优化化方方法法性性能能的的需需求求促促进

9、进了了最最优优化化方方法法的的发发展展，最最优优化化逐逐步步走走出出“象象牙牙塔塔”，面面向向实实际际需需要要，完完成成了了从从“方方法法定向定向”到到“问题定向问题定向”的转换。的转换。3.1概述概述对最优化提出的新的需求对最优化提出的新的需求1/24/202313l1975年年，Holland提提出出遗遗传传算算法法(GeneticAlgorithm)。这这种种优优化化方方法法模模仿仿生生物物种种群群中中优优胜胜劣劣汰汰的的选选择择机机制制，通通过过种种群群中中优优势势个体的繁衍进化来实现优化的功能。个体的繁衍进化来实现优化的功能。l1977年年，Glover提提出出禁禁忌忌搜搜索索(Ta

10、buSearch)算算法法。这这种种方方法法将将记记忆忆功功能能引引入入到到最最优优解解的的搜搜索索过过程程中中，通通过过设设置置禁禁忌忌区区阻阻止止搜索过程中的重复，从而大大提高了寻优过程的搜索效率。搜索过程中的重复，从而大大提高了寻优过程的搜索效率。l1983年年，Kirkpatrick提提出出了了模模拟拟退退火火(SimulatedAnnealing)算算法法。这这种种算算法法模模拟拟热热力力学学中中退退火火过过程程能能使使金金属属原原子子达达到到能能量量最最低低状状态态的的机机制制，通通过过模模拟拟的的降降温温过过程程，按按玻玻兹兹曼曼(Boltzmann)方方程程计计算算状状态态间间

11、的的转转移移概概率率来来引引导导搜搜索索，从从而而使使算算法法具具有有很很好好的全局搜索能力。的全局搜索能力。3.1概述概述新的优化方法不断出现新的优化方法不断出现1/21/24/202314l20世世纪纪90年年代代初初，Dorigo等等提提出出蚁蚁群群优优化化算算法法(AntColonyOptimization)算算法法。这这种种算算法法借借鉴鉴蚁蚁群群群群体体利利用用信信息息素素相相互互传传递递信信息息来来实实现现路路径径优优化化的的机机理理，通通过过记记忆忆路路径径信信息息素素的的变变化化来来解决组合优化问题。解决组合优化问题。l1995年年，Kenedy和和 Eberhart提提 出

12、出 粒粒 子子 群群 优优 化化(ParticleSwarmOptimization)算算法法。这这种种方方法法模模仿仿鸟鸟类类和和鱼鱼类类群群体体觅觅食食迁迁移移中中，个个体体与与群群体体协协调调一一致致的的机机理理，通通过过群群体体最最优优方方向向、个个体最优方向和惯性方向的协调来求解实数优化问题。体最优方向和惯性方向的协调来求解实数优化问题。l1999年年，Linhares提提出出了了捕捕食食搜搜索索(PredatorySearch)算算法法。这这种种算算法法模模拟拟猛猛兽兽捕捕食食中中大大范范围围搜搜寻寻和和局局部部蹲蹲守守的的特特点点，通通过过设设置置全全局局搜搜索索和和局局部部搜搜

13、索索间间变变换换的的阈阈值值来来协协调调两两种种不不同同的的搜搜索索模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。3.1概述概述新的优化方法不断出现新的优化方法不断出现2/21/24/202315l不不以以达达到到某某个个最最优优性性条条件件或或找找到到理理论论上上的的精精确确最最优优解解为为目目标标，而是更看重计算的速度和效率；而是更看重计算的速度和效率；l对目标函数和约束函数的要求十分宽松；对目标函数和约束函数的要求十分宽松；l算算法法的的基基本本思思想想都都是是来来自自对对某某种种自自然然规规律律的的模模仿仿，具具有有人人工工智能

14、的特点；智能的特点；l多多数数算算法法含含有有一一个个多多个个体体的的群群体体，寻寻优优过过程程实实际际上上就就是是种种群群的进化过程；的进化过程；l理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。3.1概述概述新的算法的一些共同特点新的算法的一些共同特点1/24/202316l由由于于算算法法理理论论薄薄弱弱，最最早早被被称称为为“现现代代启启发发式式(ModernHeuristics)”或或“高级启发式高级启发式(AdvancedHeuristics)”；l从从其其人人工工智智能能的的特特点点，被被称称为为“智智能能计计算算(In

15、telligentComputation)”或或“智智能能优优化化算算法法(Intelligent OptimizationAlgorithms)”；l从从不不以以精精确确解解为为目目标标的的特特点点，又又被被归归到到“软软计计算算(SoftComputing)”方法中；方法中；l从从 种种 群群 进进 化化 的的 特特 点点 看看，它它 们们 又又 可可 以以 称称 为为“进进 化化 计计 算算(EvolutionaryCompuation)”；l从从模模仿仿自自然然规规律律的的特特点点出出发发，又又有有人人将将它它们们称称为为“自自然然计计算算(NaturalComputing)”。3.1

16、概述概述新的优化方法的不同名称新的优化方法的不同名称1/24/202317l应用智能优化算法解决各类问题是重点；应用智能优化算法解决各类问题是重点；l算法改进有很大的创新空间；算法改进有很大的创新空间；l多种算法结合的混合算法是一条捷径；多种算法结合的混合算法是一条捷径；l不提倡刻意去追求理论成果；不提倡刻意去追求理论成果；l算法性能的测算是一项要下真功夫的工作；算法性能的测算是一项要下真功夫的工作；l选选择择测测试试例例题题的的一一般般规规律律：网网上上题题库库中中的的例例题题文文献献中中的的例例题题随机产生的例题随机产生的例题实际应用问题实际应用问题自己编的例题；自己编的例题；l算算法法性

17、性能能测测试试的的主主要要指指标标：达达优优率率(解解的的目目标标平平均均值值和和最最优优解解的的目目标标值值的的比比，所所有有解解的的目目标标值值的的标标准准差差等等)，计计算算速速度度，计计算算大规模问题的能力；大规模问题的能力；l创造出新算法创造出新算法3.1概述概述怎样学习研究智能优化方法怎样学习研究智能优化方法1/24/2023183.2 遗传算法遗传算法1/24/202319生生物物在在自自然然界界中中的的生生存存繁繁衍衍，显显示示出出了了其其对对自自然然环环境境的的优优异异自自适适应应能能力力。受受其其启启发发，人人们们致致力力于于对对生生物物各各种种生生存存特特性性的的机机理理

18、研研究究和和行行为为模模拟拟，为为人人工工自自适适应应系系统统的的设设计计和和开开发发提提供供了了广广阔阔的前景。的前景。遗遗传传算算法法(GeneticAlgorithm，简简称称GA)就就是是这这种种生生物物行行为为的的计计算机模拟中令人瞩目的重要成果。算机模拟中令人瞩目的重要成果。基基于于对对生生物物遗遗传传和和进进化化过过程程的的计计算算机机模模拟拟，遗遗传传算算法法使使得得各各种种人工系统具有优良的自适应能力和优化能力。人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传算法所借鉴的生物学基础就是生物的遗传和进化。3.2遗传算法遗传算法概要概要

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

20、。程发生在染色体上。(3)生物的繁殖过程是由其基因的复制过程来完成的：生物的繁殖过程是由其基因的复制过程来完成的：(4)通通过过同同源源染染色色体体之之间间的的交交叉叉或或染染色色体体的的变变异异会会产产生生新新的的物物种种，使生物呈现新的性状。使生物呈现新的性状。(5)对对环环境境适适应应性性好好的的基基因因或或染染色色体体经经常常比比适适应应性性差差的的基基因因或或染染色体有更多的机会遗传到下一代。色体有更多的机会遗传到下一代。3.2遗传算法遗传算法概要概要1/24/202321遗遗传传算算法法是是模模拟拟生生物物在在自自然然环环境境下下的的遗遗传传和和进进化化过过程程而而形形成成的的一种

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

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

23、23U基本空间基本空间R可行解集合可行解集合X可行解可行解3.2遗传算法遗传算法概要概要1/24/202324对对于于上上述述最最优优化化问问题题，目目标标函函数数和和约约束束条条件件种种类类繁繁多多，有有的的是是线线性性的的，有有的的是是非非线线性性的的；有有的的是是连连续续的的，有有的的是是离离散散的的；有有的的是是单峰值的，有的是多峰值的。单峰值的，有的是多峰值的。随随着着研研究究的的深深入入，人人们们逐逐渐渐认认识识到到在在很很多多复复杂杂情情况况下下要要想想完完全全精精确确地地求求出出其其最最优优解解既既不不可可能能，也也不不现现实实，因因而而求求出出其其近近似似最最优解或满意解是人

24、们的主要着眼点之一。优解或满意解是人们的主要着眼点之一。3.2遗传算法遗传算法概要概要1/24/202325遗遗传传算算法法中中，将将n维维决决策策向向量量用用n个个记记号号xi(n=l，2，n)所组成的符号串所组成的符号串X来表示：来表示：把把每每一一个个xi看看作作一一个个遗遗传传基基因因，它它的的所所有有可可能能取取值值称称为为等等位位基基因因，这样，这样，X就可看做是由就可看做是由n个遗传基因所组成的一个染色体。个遗传基因所组成的一个染色体。般般情情况况下下，染染色色体体的的长长度度n是是固固定定的的，但但对对一一些些问问题题n也也可可以以是是变化的。变化的。根根据据不不同同的的情情况

25、况，这这里里的的等等位位基基因因可可以以是是一一组组整整数数，也也可可以以是是某某一范围内的实数值，或者是纯粹的一个记号。一范围内的实数值，或者是纯粹的一个记号。最最简简单单的的等等位位基基因因是是由由0和和1这这两两个个整整数数组组成成的的。相相应应的的染染色色体体就就可表示为一个二进制符号串。可表示为一个二进制符号串。3.2遗传算法遗传算法概要概要1/24/202326这这种种编编码码所所形形成成的的排排列列形形式式X是是个个体体的的基基因因型型，与与它它对对应应的的X值值是个体的是个体的表现型表现型。通通常常个个体体的的表表现现型型和和其其基基因因型型是是一一一一对对应应的的，但但有有时

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

27、进进行行的的，从从而而由由所所有有的的染染色色体体X就就组组成成了了问问题题的的搜搜索索空空间间。通通过过编编码码和和解解码码，使使得得问问题题的的解解空间和搜索空间一一对应。空间和搜索空间一一对应。3.2遗传算法遗传算法概要概要1/24/202327生物的进化是以集团为主体的。与此相对应，遗传算法的运算对生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是出象是出M个个体所组成的集合，称为个个体所组成的集合，称为群体群体。与与生生物物一一代代一一代代的的自自然然进进化化过过程程相相类类似似，遗遗传传算算法法的的运运算算过过程程也也是是一一个个反反复复迭迭代代的的过过程程，第第t代代群

28、群体体记记做做P(t)，经经过过一一代代遗遗传传和和进进化化后后，得得到到第第t+l代代群群体体，它它们们也也是是由由多多个个个个体体组组成成的的集集合合，记记做做P(t+1)。这这个个群群体体不不断断地地经经过过遗遗传传和和进进化化操操作作，并并且且每每次次都都按按照照优优胜胜劣劣汰汰的的规规则则将将适适应应度度较较高高的的个个体体更更多多地地遗遗传传到到下下一一代代，这这样样最最终终在在群群体体中中将将会会得得到到一一个个优优良良的的个个体体X，它它所所对对应应的的表表现现型型X将将达达到或接近于问题的最优解到或接近于问题的最优解X*。生生物物的的进进化化过过程程主主要要是是通通过过染染色

29、色体体之之间间的的交交叉叉和和染染色色体体的的变变异异来来完完成成的的，与与此此相相对对应应，遗遗传传算算法法中中最最优优解解的的搜搜索索过过程程也也模模仿仿生生物物的的这这个个进进化化过过程程，使使用用所所谓谓的的遗遗传传算算子子(geneticoperators)作作用用于群体于群体P(t)中，进行下述遗传操作，从而得到新一代群体中，进行下述遗传操作，从而得到新一代群体P(t+1)。3.2遗传算法遗传算法概要概要1/24/202328选选择择(selection)：根根据据各各个个个个体体的的适适应应度度，按按照照一一定定的的规规则则或或方方法法，从从第第t代代群群体体P(t)中中选选择择

30、出出一一些些优优良良的的个个体体遗遗传传到到下下一一代代群群体体P(t+1)中。中。交交叉叉(crossover)：将将群群体体P(t)内内的的各各个个个个体体随随机机搭搭配配成成对对，对对每每对对个个体体，以以某某个个概概率率(称称为为交交叉叉概概率率，crossoverrate)交交换换它它们们之之间的部分染色体。间的部分染色体。变变异异(mutation)：对对群群体体P(t)中中的的每每一一个个个个体体，以以某某一一概概率率(称称为为变变异异概概率率，mutationrate)改改变变某某一一个个或或某某一一些些基基因因座座上上的的基基因因值为其他的等位基因。值为其他的等位基因。3.2

31、遗传算法遗传算法概要概要1/24/202329使使用用上上述述三三种种遗遗传传算算子子(选选择择算算子子、交交叉叉算算子子、变变异异算算子子)的的遗遗传算法的主要运算过程如下所述：传算法的主要运算过程如下所述：步骤一：初始化。步骤一：初始化。设置进化代数计数器设置进化代数计数器t0；设置最大进化代数；设置最大进化代数T；随机生成；随机生成M个个个体作为初始群体个体作为初始群体P(0)。步骤二：个体评价。步骤二：个体评价。计算群体计算群体P(t)中各个个体的适应度。中各个个体的适应度。步骤三：选择运算。步骤三：选择运算。将选择算子作用于群体。将选择算子作用于群体。3.2遗传算法遗传算法运算过程运

32、算过程1/24/202330步骤四：交叉运算。步骤四：交叉运算。将交叉算子作用于群体。将交叉算子作用于群体。步骤五：变异运算。步骤五：变异运算。将变异算于作用于群体。将变异算于作用于群体。群体群体P(t)经过选择、交叉、变异运算之后得到下一代群体经过选择、交叉、变异运算之后得到下一代群体P(t+1)。步骤六：终止条件判断。步骤六：终止条件判断。若若t T，则：，则：tt+1，转到步骤二。，转到步骤二。若若tT，则则以以进进化化过过程程中中所所得得到到的的具具有有最最大大适适应应度度的的个个体体作作为为最最优解输出，终止计算。优解输出，终止计算。3.2遗传算法遗传算法运算过程运算过程1/24/2

33、02331基基于于对对自自然然界界中中生生物物遗遗传传与与进进化化机机理理的的模模仿仿，针针对对不不向向的的问问题题，很很多多学学者者设设计计了了许许多多不不同同的的编编码码方方法法来来表表示示问问题题的的可可行行解解，开开发发出出了了许许多多种种不不同同的的遗遗传传算算子子来来模模仿仿不不同同环环境境下下的的生生物物遗遗传传特特。这这样样，由由不不同同的的编编码码方方法法和和不不同同的的遗遗传传算算子子就就构构成成了了各各种种不不同同的遗传算法。的遗传算法。但但这这些些遗遗传传算算法法都都有有共共同同的的特特点点，即即通通过过对对生生物物遗遗传传和和进进化化过过程程中中选选择择、交交叉叉、变

34、变异异机机理理的的模模仿仿，来来完完成成对对问问题题最最优优解解的的自自适应搜索过程。适应搜索过程。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现1/24/202332基基于于这这个个共共同同特特点点，Goldberg总总结结出出了了一一种种统统一一的的最最基基本本的的遗遗传传算法算法基本遗传算法基本遗传算法(SimpleGeneticAlgorithms，简称简称SGA)。基基本本遗遗传传算算法法使使用用固固定定长长度度的的二二进进制制符符号号串串来来表表示示群群体体中中的的个个体体，其其等等位位基基因因是是由由二二值值符符号号集集0，1所所组组成成的的。初初始始群群体体中中各各

35、个个个个体的基因值可用均匀分布的随机数来生成。体的基因值可用均匀分布的随机数来生成。基基本本遗遗传传算算法法使使用用比比例例选选择择算算子子、单单点点交交叉叉算算子子和和基基本本位位变变异异算算子子这这三三种种基基本本遗遗传传算算子子，其其遗遗传传进进化化操操作作过过程程简简单单，容容易易理理解解，是是其其他他一一些些遗遗传传算算法法的的雏雏形形和和基基础础，它它不不仅仅给给各各种种遗遗传传算算法法提提供供了一个基本框架，同时也具有一定的应用价值。了一个基本框架，同时也具有一定的应用价值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现1/24/202333用二进制编码来离散自变量，

36、码长根据离散精度来确定。用二进制编码来离散自变量，码长根据离散精度来确定。例如当自变量例如当自变量a的变化区间为的变化区间为amin，amax，当离散精度为，当离散精度为 时，时，码长码长m的计算公式为：的计算公式为：相应的解码公式为：相应的解码公式为：3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现编码和解码编码和解码1/24/202334在在遗遗传传算算法法中中，以以个个体体适适应应度度的的大大小小来来确确定定该该个个体体被被遗遗传传到到下下一一代代群群体体中中的的概概率率。个个体体的的适适应应度度越越大大，该该个个体体被被遗遗传传到到下下一一代代的的概概率率也也越越大大；反反之

37、之，个个体体的的适适应应度度越越小小，该该个个体体被被遗遗传传到到下下一一代代的概率也越小。的概率也越小。基基本本遗遗传传算算法法使使用用比比例例选选择择算算子子来来确确定定群群体体中中各各个个个个体体遗遗传传到到下一代群体中的数量。下一代群体中的数量。为为正正确确计计算算不不同同情情况况下下各各个个个个体体的的遗遗传传概概率率，要要求求所所有有个个体体的的适应度必须为正数或零，不能是负数。适应度必须为正数或零，不能是负数。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价1/41/24/202335对于求目标函数最小值的优化问题，理论上只需简单地对其增对于求目标函

38、数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：加一个负号就可将其转化为求目标函数最大值的优化问题，即：minf(X)max(f(X)当优化目标是求函数最大值，并且目标函数总取正值时，可以当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度直接设定个体的适应度F(x)就等于相应的目标函数值就等于相应的目标函数值f(X)，即：，即：F(X)f(X)但实际优化问题中的目标函数值有正也有负，优化目标有求函但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值。数最大值，也有求函数最小值。上上面面两两式式

39、保保证证不不了了所所有有情情况况下下个个体体的的适适应应度度都都是是非非负负数数这这个个要要求求。所所以以必必须须寻寻求求出出一一种种通通用用且且有有效效的的由由目目标标函函数数值值到到个个体体适适应度之间的转换关系，由它来保证个体适应度总取非负值。应度之间的转换关系，由它来保证个体适应度总取非负值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价2/41/24/202336为满足适应度取非负值的要求，基本遗传算法一般采用下面两种为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值方法之一将目标函数值f(X)变换为个体的适应度变换为个体的适

40、应度F(x)。式中，式中，Cmin为一个适当地相对比较小的数，它可以用下面几种方为一个适当地相对比较小的数，它可以用下面几种方法之一来选择：法之一来选择：方法一：对于求目标函数最大值的优化问题，变换方法为：方法一：对于求目标函数最大值的优化问题，变换方法为：预先指定的一个较小的数。预先指定的一个较小的数。进化到当前代为止的最小目标函数值。进化到当前代为止的最小目标函数值。当前代或最近几代群体中的最小目标函数值。当前代或最近几代群体中的最小目标函数值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价3/41/24/202337方法二：对于求目标函数最小值的优化问题，

41、变换方法为：方法二：对于求目标函数最小值的优化问题，变换方法为：式式中中，Cmax为为一一个个适适当当地地相相对对比比较较大大的的数数，它它可可以以用用下下面面几几种种方法之一来选择：方法之一来选择：预先指定的一个较大的数。预先指定的一个较大的数。进化到当前代为止的最大目标函数值。进化到当前代为止的最大目标函数值。前代或最近几代群体中的最大目标函数值。前代或最近几代群体中的最大目标函数值。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现适应度评价适应度评价4/41/24/202338选选择择算算子子或或复复制制算算子子的的作作用用是是从从当当前前代代群群体体中中选选择择出出一一些些比

42、比较较优优良良的的个个体体，并并将将其其复复制制到到下下一一代代群群体体中中。最最常常用用和和最最基基本本的的选选择择算子是比例选择算子。算子是比例选择算子。比比例例选选择择实实际际上上是是一一种种有有退退还还随随机机选选择择，也也叫叫做做赌赌盘盘(Roulettewheel)选选择择，因因为为这这种种选选择择方方式式与与赌赌博博中中的的赌赌盘盘操操作作原原理理颇颇为为相相似。似。所所谓谓比比例例选选择择算算子子，是是指指个个体体被被选选中中并并遗遗传传到到下下一一代代群群体体中中的的概率与该个体的适应度大小成正比。概率与该个体的适应度大小成正比。3.2遗传算法遗传算法基本遗传算法的实现基本遗

43、传算法的实现比例选择算子比例选择算子1/41/24/202339整整个个赌赌盘盘被被分分为为大大小小不不同同的的一一些些扇扇面面，分分别别对对应应着着价价值值各各不不相相同同的的一一些些赌赌博博物物品品。当当旋旋转转着着的的赌赌盘盘自自然然停停下下来来时时，其其指指针针所所指指扇扇面上的物品就归赌博者所有。面上的物品就归赌博者所有。虽虽然然赌赌盘盘的的指指针针具具体体停停止止在在哪哪一一个个扇扇面面是是无无法法预预测测的的，但但指指针针指指向向各各个个扇扇面面的的概概率率却却是是可可以以估估计计的的，它它与与各各个个扇扇面面的的圆圆心心角角大大小小成成正正比比：圆圆心心角角越越大大，停停在在该

44、该扇扇面面的的可可能能性性也也越越大大；圆圆心心角角越越小小，停在该扇面的可能性也越小。停在该扇面的可能性也越小。与与此此类类似似，在在遗遗传传算算法法中中，整整个个群群体体被被各各个个个个体体所所分分割割，各各个个个个体体的的适适应应度度在在全全部部个个体体的的适适应应度度之之和和中中所所占占比比例例也也大大小小不不一一，这这个个比比例例值值瓜瓜分分了了整整个个赌赌盘盘盘盘面面，它它们们也也决决定定了了各各个个个个体体被被遗遗传到下一代群体中的概率。传到下一代群体中的概率。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现比例选择算子比例选择算子2/41/24/202340金银铜铁1

45、02030403.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现比例选择算子比例选择算子3/41/24/202341令：3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现比例选择算子比例选择算子4/41/24/202342算子的具体执行过程如下算子的具体执行过程如下：(1)对群体中的个体进行两两随机配对。对群体中的个体进行两两随机配对。若群体的大小为若群体的大小为M，则共有，则共有M/2对相互配对的个体组。其中对相互配对的个体组。其中x表示不大于表示不大于x的最大整数。的最大整数。(2)对每一对相互配对的个体，随机设置某一基因座之后的位置对每一对相互配对的个体，随机设置某一基因

46、座之后的位置为交叉点。若染色体的长度为为交叉点。若染色体的长度为n，则共有，则共有(n-1)个可能的交叉点位个可能的交叉点位置。置。(3)对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率pc在其交叉点在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。处相互交换两个个体的部分染色体，从而产生出两个新的个体。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现单点交叉算子单点交叉算子1/21/24/202343单点交叉示意如下所示：单点交叉示意如下所示：A：1011011100A：1011011111B：0001110011B；00011100

47、00单点单点交叉交叉交叉点交叉点3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现单点交叉算子单点交叉算子2/21/24/202344对于基本遗传算法中用二进制编码符号串所表示的个体，若需要对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为进行变异操作的某一基因座上的原有基因值为0，则变异操作将，则变异操作将该基因值变为该基因值变为1；反之，若原有基因值为；反之，若原有基因值为l，则变异操作将其变为，则变异操作将其变为0。A：10l0101010A：10l0001010基本位变异基本位变异变异点变异点(1)对个体的每一个基因座，依变异概率对

48、个体的每一个基因座，依变异概率pm指定其为变异点。指定其为变异点。(2)对每一个指定的变异点，对其基因值做取反运算或用其它等对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。位基因值来代替，从而产生出一个新的个体。3.2遗传算法遗传算法基本遗传算法的实现基本遗传算法的实现基本位变异算子基本位变异算子1/24/202345基本遗传算法有下述基本遗传算法有下述4个运行参数需要提前设定：个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为：群体大小，即群体中所含个体的数量，一般取为20 1000T：遗传运算的终止进化代数，一般取为：遗传运算

49、的终止进化代数，一般取为100 500Pc：交叉概率，：交叉概率，般取为般取为0.4 0.99。Pm：变异概率，一般取为：变异概率，一般取为0.0001 0.1这这4个运行参数对遗传算法的求解结果和求解效率都有一定的影个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。响，但目前尚无合理选择它们的理论依据。3.2遗传算法遗传算法遗传算法的运行参数遗传算法的运行参数1/21/24/202346在在遗遗传传算算法法的的实实际际应应用用中中，往往往往需需要要经经过过多多次次试试算算后后才才能能确确定定出这些参数合理的取值大小或取值范围。出这些参数合理的取值大小或

50、取值范围。一一般般来来说说，选选择择较较大大数数目目的的初初始始种种群群可可以以同同时时处处理理更更多多的的解解，因因而而容容易易找找到到全全局局的的最最优优解解，其其缺缺点点使使增增加加了了每每次次迭迭代代所所需需要要的时间。的时间。交交叉叉概概率率的的选选择择决决定定了了交交叉叉操操作作的的频频率率。频频率率越越高高，可可以以越越快快收收敛敛到到最最有有希希望望的的最最优优解解区区域域；但但是是太太高高的的频频率率也也可可能能导导致致收收敛于一个解。敛于一个解。变变异异概概率率通通常常只只取取较较小小的的数数值值。若若选选取取高高的的变变异异率率，一一方方面面可可以以增增加加样样本本的的多