求解优化问题的智能算法.pptx
《求解优化问题的智能算法.pptx》由会员分享,可在线阅读,更多相关《求解优化问题的智能算法.pptx(210页珍藏版)》请在咨信网上搜索。
1、2024/4/2 周二1第第 三三 章章求解优化问题的智能算法求解优化问题的智能算法2024/4/2 周二23.1 概述概述2024/4/2 周二3最最优优化化问问题题是是指指在在一一定定的的约约束束条条件件下下,决决定定某某个个或或某某些些可可控控制制的的因因素素应应有有的的合合理理取取值值,使使所所选选定定的的目目标标达达到到最最优优的的问问题题。解解决决最最优优化化问问题题的的方方法法称称为为最最优优化化方方法法。它它具具有有高高度度应应用用性性和和技技术性的特点。术性的特点。最最优优化化问问题题可可以以追追溯溯到到十十分分古古老老的的极极值值问问题题,在在17世世纪纪,伟伟大大科科学学
2、家家Newton发发明明微微积积分分的的时时候候,已已经经提提出出了了极极值值问问题题,后后来来又又出出现现了了Lagrange乘乘子子法法,Cauchy则则利利用用最最速速下下降降法法求求解解无无约约束束极极小小化化问问题题。然然而而,直直到到1947年年Dantzig提提出出求求解解一一般般线线性性规规划问题的单纯形法之后,它才成为一门独立的学科。划问题的单纯形法之后,它才成为一门独立的学科。3.1概述概述最优化方法的研究起源和意义最优化方法的研究起源和意义1/22024/4/2 周二4随随着着近近代代科科学学技技术术发发展展的的需需要要,特特别别是是由由于于计计算算机机技技术术的的飞飞速
3、速发展,促进了最优化方法的迅速发展,并很快渗透到各个领域。发展,促进了最优化方法的迅速发展,并很快渗透到各个领域。20世世纪纪70年年代代,最最优优化化方方法法这这门门应应用用技技术术科科学学又又开开始始产产生生出出最最优优设设计计、最最优优控控制制与与最最优优管管理理等等分分支支。到到20世世纪纪80年年代代,最最优优化化技技术术又又在在这这些些分分支支中中发发展展出出了了新新的的更更细细的的分分支支,比比如如,工工程程技技术术领领域域的的机机械械优优化化设设计计、建建筑筑结结构构优优化化设设计计以以及及化化工工石石油油领领域的优化设计等。域的优化设计等。3.1概述概述最优化方法的研究起源和
4、意义最优化方法的研究起源和意义2/22024/4/2 周二5求解优化问题的步骤求解优化问题的步骤(1)分析待优化的问题,建立问题的数学模型;分析待优化的问题,建立问题的数学模型;(2)分析数学模型,选择合适的最优化算法;分析数学模型,选择合适的最优化算法;(3)编写计算机程序、上机计算、求出最优解;编写计算机程序、上机计算、求出最优解;(4)结果检验与最后决策。结果检验与最后决策。2024/4/2 周二6转化为最小化问题。3.1概述概述最优化问题的数学描述最优化问题的数学描述2024/4/2 周二7(1)枚举法。枚举法。枚举出可行解集合内的所有可行解,以求出精确最优解。对于连枚举出可行解集合内
5、的所有可行解,以求出精确最优解。对于连续函数,该方法要求先对其进行离散化处理,这样就有可能产生续函数,该方法要求先对其进行离散化处理,这样就有可能产生离散误差而永远达不到最优解。另外,当枚举空间比较大时,该离散误差而永远达不到最优解。另外,当枚举空间比较大时,该方法的求解效率比较低,有时甚至在目前最先进的计算工具上都方法的求解效率比较低,有时甚至在目前最先进的计算工具上都无法求解。无法求解。(2)启发式算法。启发式算法。寻寻求求一一种种能能产产生生可可行行解解的的启启发发式式规规则则,以以找找到到一一个个最最优优解解或或近近似似最最优优解解。该该方方法法的的求求解解效效率率虽虽然然比比较较高高
6、,但但对对每每一一个个需需要要求求解解的的问问题题都都必必须须找找出出其其特特有有的的启启发发式式规规则则,这这个个启启发发式式规规则则无无通通用用性性,不适合于其他问题。不适合于其他问题。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法1/22024/4/2 周二8(3)搜搜索索算算法法。寻寻求求一一种种搜搜索索算算法法,该该算算法法在在可可行行解解集集合合的的一一个个子子集集内内进进行行搜搜索索操操作作,以以找找到到问问题题的的最最优优解解或或近近似似最最优优解解。该该方方法法虽虽然然保保证证不不了了一一定定能能够够得得到到问问题题的的最最优优解解,但但若若适适当当地地利
7、利用用一一些些启启发发知知识识,就就可可在在近近似似解解的的质质量量和和求求解解效效率率上上达达到到种种较较好好的的平衡。平衡。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法2/22024/4/2 周二9以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具有完善的数学基础,具有计算效率高、可靠性强和比较成熟具有完善的数学基础,具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下:等特点。这些算法的基本迭代步骤如下:3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法2024/4/2 周二10
8、3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法最速下降法最速下降法2024/4/2 周二113.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法牛顿法牛顿法2024/4/2 周二123.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法共轭方向法共轭方向法2024/4/2 周二13l对目标函数和约束函数表达的要求必须更为宽松对目标函数和约束函数表达的要求必须更为宽松l计算的效率比理论上的最优性更重要计算的效率比理论上的最优性更重要l算法随时终止能够随时得到较好的解算法随时终止能够随时得到较好的解l对优化模型中数据的质量要求更为宽松对优化模型中数据的质量要求更为
9、宽松实实际际生生活活中中对对最最优优化化方方法法性性能能的的需需求求促促进进了了最最优优化化方方法法的的发发展展,最最优优化化逐逐步步走走出出“象象牙牙塔塔”,面面向向实实际际需需要要,完完成成了了从从“方方法法定向定向”到到“问题定向问题定向”的转换。的转换。3.1概述概述对最优化提出的新的需求对最优化提出的新的需求2024/4/2 周二14l1975年年,Holland提提出出遗遗传传算算法法(GeneticAlgorithm)。这这种种优优化化方方法法模模仿仿生生物物种种群群中中优优胜胜劣劣汰汰的的选选择择机机制制,通通过过种种群群中中优优势势个体的繁衍进化来实现优化的功能。个体的繁衍进
10、化来实现优化的功能。l1977年年,Glover提提出出禁禁忌忌搜搜索索(TabuSearch)算算法法。这这种种方方法法将将记记忆忆功功能能引引入入到到最最优优解解的的搜搜索索过过程程中中,通通过过设设置置禁禁忌忌区区阻阻止止搜索过程中的重复,从而大大提高了寻优过程的搜索效率。搜索过程中的重复,从而大大提高了寻优过程的搜索效率。l1983年年,Kirkpatrick提提出出了了模模拟拟退退火火(SimulatedAnnealing)算算法法。这这种种算算法法模模拟拟热热力力学学中中退退火火过过程程能能使使金金属属原原子子达达到到能能量量最最低低状状态态的的机机制制,通通过过模模拟拟的的降降温
11、温过过程程,按按玻玻兹兹曼曼(Boltzmann)方方程程计计算算状状态态间间的的转转移移概概率率来来引引导导搜搜索索,从从而而使使算算法法具具有有很很好好的的全局搜索能力。全局搜索能力。3.1概述概述新的优化方法不断出现新的优化方法不断出现1/22024/4/2 周二15l20世世纪纪90年年代代初初,Dorigo等等提提出出蚁蚁群群优优化化算算法法(Ant ColonyOptimization)算算法法。这这种种算算法法借借鉴鉴蚁蚁群群群群体体利利用用信信息息素素相相互互传传递递信信息息来来实实现现路路径径优优化化的的机机理理,通通过过记记忆忆路路径径信信息息素素的的变变化化来来解决组合优
12、化问题。解决组合优化问题。l1995年年,Kenedy和和Eberhart提提出出粒粒子子群群优优化化(ParticleSwarmOptimization)算算法法。这这种种方方法法模模仿仿鸟鸟类类和和鱼鱼类类群群体体觅觅食食迁迁移移中中,个个体体与与群群体体协协调调一一致致的的机机理理,通通过过群群体体最最优优方方向向、个个体体最最优优方方向和惯性方向的协调来求解实数优化问题。向和惯性方向的协调来求解实数优化问题。l1999年年,Linhares提提出出了了捕捕食食搜搜索索(PredatorySearch)算算法法。这这种种算算法法模模拟拟猛猛兽兽捕捕食食中中大大范范围围搜搜寻寻和和局局部部
13、蹲蹲守守的的特特点点,通通过过设设置置全全局局搜搜索索和和局局部部搜搜索索间间变变换换的的阈阈值值来来协协调调两两种种不不同同的的搜搜索索模式,从而实现了对全局搜索能力和局部搜索能力的兼顾。模式,从而实现了对全局搜索能力和局部搜索能力的兼顾。3.1概述概述新的优化方法不断出现新的优化方法不断出现2/22024/4/2 周二16l不不以以达达到到某某个个最最优优性性条条件件或或找找到到理理论论上上的的精精确确最最优优解解为为目目标标,而是更看重计算的速度和效率;而是更看重计算的速度和效率;l对目标函数和约束函数的要求十分宽松;对目标函数和约束函数的要求十分宽松;l算算法法的的基基本本思思想想都都
14、是是来来自自对对某某种种自自然然规规律律的的模模仿仿,具具有有人人工工智能的特点;智能的特点;l多多数数算算法法含含有有一一个个多多个个体体的的群群体体,寻寻优优过过程程实实际际上上就就是是种种群群的进化过程;的进化过程;l理论工作相对比较薄弱,一般说来都不能保证收敛到最优解。理论工作相对比较薄弱,一般说来都不能保证收敛到最优解。3.1概述概述新的算法的一些共同特点新的算法的一些共同特点2024/4/2 周二17l由由于于算算法法理理论论薄薄弱弱,最最早早被被称称为为“现现代代启启发发式式(ModernHeuristics)”或或“高级启发式高级启发式(AdvancedHeuristics)”
15、;l从从 其其 人人 工工 智智 能能 的的 特特 点点,被被 称称 为为“智智 能能 计计 算算(IntelligentComputation)”或或“智智 能能 优优 化化 算算 法法(Intelligent OptimizationAlgorithms)”;l从从不不以以精精确确解解为为目目标标的的特特点点,又又被被归归到到“软软计计算算(SoftComputing)”方法中;方法中;l从从 种种 群群 进进 化化 的的 特特 点点 看看,它它 们们 又又 可可 以以 称称 为为“进进 化化 计计 算算(EvolutionaryCompuation)”;l从从模模仿仿自自然然规规律律的的
16、特特点点出出发发,又又有有人人将将它它们们称称为为“自自然然计计算算(NaturalComputing)”。3.1概述概述新的优化方法的不同名称新的优化方法的不同名称2024/4/2 周二18l应用智能优化算法解决各类问题是重点;应用智能优化算法解决各类问题是重点;l算法改进有很大的创新空间;算法改进有很大的创新空间;l多种算法结合的混合算法是一条捷径;多种算法结合的混合算法是一条捷径;l不提倡刻意去追求理论成果;不提倡刻意去追求理论成果;l算法性能的测算是一项要下真功夫的工作;算法性能的测算是一项要下真功夫的工作;l选选择择测测试试例例题题的的一一般般规规律律:网网上上题题库库中中的的例例题
17、题文文献献中中的的例例题题随机产生的例题随机产生的例题实际应用问题实际应用问题自己编的例题;自己编的例题;l算算法法性性能能测测试试的的主主要要指指标标:达达优优率率(解解的的目目标标平平均均值值和和最最优优解解的的目目标标值值的的比比,所所有有解解的的目目标标值值的的标标准准差差等等),计计算算速速度度,计计算算大规模问题的能力;大规模问题的能力;l创造出新算法创造出新算法3.1概述概述怎样学习研究智能优化方法怎样学习研究智能优化方法2024/4/2 周二193.2 遗传算法遗传算法2024/4/2 周二20生生物物在在自自然然界界中中的的生生存存繁繁衍衍,显显示示出出了了其其对对自自然然环
18、环境境的的优优异异自自适适应应能能力力。受受其其启启发发,人人们们致致力力于于对对生生物物各各种种生生存存特特性性的的机机理理研研究究和和行行为为模模拟拟,为为人人工工自自适适应应系系统统的的设设计计和和开开发发提提供供了了广广阔阔的前景。的前景。遗遗传传算算法法(GeneticAlgorithm,简简称称GA)就就是是这这种种生生物物行行为为的的计计算机模拟中令人瞩目的重要成果。算机模拟中令人瞩目的重要成果。基基于于对对生生物物遗遗传传和和进进化化过过程程的的计计算算机机模模拟拟,遗遗传传算算法法使使得得各各种种人工系统具有优良的自适应能力和优化能力。人工系统具有优良的自适应能力和优化能力。
19、遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传算法所借鉴的生物学基础就是生物的遗传和进化。3.2遗传算法遗传算法概要概要2024/4/2 周二21虽虽然然人人们们还还未未完完全全揭揭开开遗遗传传与与进进化化的的奥奥秘秘,既既没没有有完完全全掌掌握握其其机机制制,也也不不完完全全清清楚楚染染色色体体编编码码和和译译码码过过程程的的细细节节,更更不不完完全全了了解解其控制方式,但遗传与进化的以下几个特点却为人们所共识:其控制方式,但遗传与进化的以下几个特点却为人们所共识:(1)生生物物的的所所有有遗遗传传信信息息都都包包含含在在其其染染色色休休中中,染染色色体体决决定定了了生生物的性状。物的
20、性状。(2)染染色色体体是是由由基基因因及及其其有有规规律律的的排排列列所所构构成成的的,遗遗传传和和进进化化过过程发生在染色体上。程发生在染色体上。(3)生物的繁殖过程是由其基因的复制过程来完成的:生物的繁殖过程是由其基因的复制过程来完成的:(4)通通过过同同源源染染色色体体之之间间的的交交叉叉或或染染色色体体的的变变异异会会产产生生新新的的物物种种,使生物呈现新的性状。使生物呈现新的性状。(5)对对环环境境适适应应性性好好的的基基因因或或染染色色体体经经常常比比适适应应性性差差的的基基因因或或染染色体有更多的机会遗传到下一代。色体有更多的机会遗传到下一代。3.2遗传算法遗传算法概要概要20
21、24/4/2 周二22遗遗传传算算法法是是模模拟拟生生物物在在自自然然环环境境下下的的遗遗传传和和进进化化过过程程而而形形成成的的一种自适应全局优化概率搜索算法。一种自适应全局优化概率搜索算法。它它最最早早由由美美国国密密执执安安大大学学的的Holland教教授授提提出出,起起源源于于60年年代代对对自然和人工自适应系统的研究。自然和人工自适应系统的研究。70年年代代DeJong基基于于遗遗传传算算法法的的思思想想在在计计算算机机上上进进行行了了大大量量的的纯纯数值函数优化计算实验。数值函数优化计算实验。在在一一系系列列研研究究工工作作的的基基础础上上,80年年代代由由Goldberg进进行行
22、归归纳纳总总结结,形成了遗传算法的基本框架。形成了遗传算法的基本框架。3.2遗传算法遗传算法概要概要2024/4/2 周二23式中,式中,为决策变量,为决策变量,f(X)为目标函数,后两个为目标函数,后两个式子为约束条件,式子为约束条件,U是基本空间,是基本空间,R是是U的一个子集。的一个子集。对于一个求函数最大值的优化问题对于一个求函数最大值的优化问题(求函数最小值也类同求函数最小值也类同),一,一般可描述为下述数学规划模型:般可描述为下述数学规划模型:满满足足约约束束条条件件的的解解X称称为为可可行行解解,集集合合R表表示示由由所所有有满满足足约约束束条条件件的的解解所所组组成成的的一一个
23、个集集合合,叫叫做做可可行行解解集集合合。它它们们之之间间的的关关系系如图所示。如图所示。3.2遗传算法遗传算法概要概要2024/4/2 周二24U基本空间基本空间R可行解集合可行解集合X可行解可行解3.2遗传算法遗传算法概要概要2024/4/2 周二25对对于于上上述述最最优优化化问问题题,目目标标函函数数和和约约束束条条件件种种类类繁繁多多,有有的的是是线线性性的的,有有的的是是非非线线性性的的;有有的的是是连连续续的的,有有的的是是离离散散的的;有有的的是是单峰值的,有的是多峰值的。单峰值的,有的是多峰值的。随随着着研研究究的的深深入入,人人们们逐逐渐渐认认识识到到在在很很多多复复杂杂情
24、情况况下下要要想想完完全全精精确确地地求求出出其其最最优优解解既既不不可可能能,也也不不现现实实,因因而而求求出出其其近近似似最最优解或满意解是人们的主要着眼点之一。优解或满意解是人们的主要着眼点之一。3.2遗传算法遗传算法概要概要2024/4/2 周二26遗遗传传算算法法中中,将将n维维决决策策向向量量用用n个个记记号号xi(n=l,2,n)所组成的符号串所组成的符号串X来表示:来表示:把把每每一一个个xi看看作作一一个个遗遗传传基基因因,它它的的所所有有可可能能取取值值称称为为等等位位基基因因,这样,这样,X就可看做是由就可看做是由n个遗传基因所组成的一个染色体。个遗传基因所组成的一个染色
25、体。般般情情况况下下,染染色色体体的的长长度度n是是固固定定的的,但但对对一一些些问问题题n也也可可以以是是变化的。变化的。根根据据不不同同的的情情况况,这这里里的的等等位位基基因因可可以以是是一一组组整整数数,也也可可以以是是某某一范围内的实数值,或者是纯粹的一个记号。一范围内的实数值,或者是纯粹的一个记号。最最简简单单的的等等位位基基因因是是由由0和和1这这两两个个整整数数组组成成的的。相相应应的的染染色色体体就就可表示为一个二进制符号串。可表示为一个二进制符号串。3.2遗传算法遗传算法概要概要2024/4/2 周二27这这种种编编码码所所形形成成的的排排列列形形式式X是是个个体体的的基基
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 求解 优化 问题 智能 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。