《第三章求解优化问题的智能算法课件》由会员分享，可在线阅读，更多相关《第三章求解优化问题的智能算法课件（210页珍藏版）》请在金锄头文库上搜索。
1、第第 三三 章章求解优化问题的智能算法求解优化问题的智能算法5/24/202213.1 概述概述5/24/20222最最优优化化问问题题是是指指在在一一定定的的约约束束条条件件下下，决决定定某某个个或或某某些些可可控控制制的的因因素素应应有有的的合合理理取取值值，使使所所选选定定的的目目标标达达到到最最优优的的问问题题。解解决决最最优优化化问问题题的的方方法法称称为为最最优优化化方方法法。它它具具有有高高度度应应用用性性和和技技术性的特点。术性的特点。最最优优化化问问题题可可以以追追溯溯到到十十分分古古老老的的极极值值问问题题，在在17世世纪纪，伟伟大大科科学学家家Newton发发明明微微积积
2、分分的的时时候候，已已经经提提出出了了极极值值问问题题，后后来来又又出出现现了了Lagrange乘乘子子法法，Cauchy则则利利用用最最速速下下降降法法求求解解无无约约束束极极小小化化问问题题。然然而而，直直到到1947年年Dantzig提提出出求求解解一一般般线线性性规规划问题的单纯形法之后，它才成为一门独立的学科。划问题的单纯形法之后，它才成为一门独立的学科。3.1概述概述最优化方法的研究起源和意义最优化方法的研究起源和意义1/25/24/20223随随着着近近代代科科学学技技术术发发展展的的需需要要，特特别别是是由由于于计计算算机机技技术术的的飞飞速速发展，促进了最优化方法的迅速发展，
3、并很快渗透到各个领域。发展，促进了最优化方法的迅速发展，并很快渗透到各个领域。20世世纪纪70年年代代，最最优优化化方方法法这这门门应应用用技技术术科科学学又又开开始始产产生生出出最最优优设设计计、最最优优控控制制与与最最优优管管理理等等分分支支。到到20世世纪纪80年年代代，最最优优化化技技术术又又在在这这些些分分支支中中发发展展出出了了新新的的更更细细的的分分支支，比比如如，工工程程技技术术领领域域的的机机械械优优化化设设计计、建建筑筑结结构构优优化化设设计计以以及及化化工工石石油油领领域的优化设计等。域的优化设计等。3.1概述概述最优化方法的研究起源和意义最优化方法的研究起源和意义2/2
4、5/24/20224求解优化问题的步骤求解优化问题的步骤(1)分析待优化的问题，建立问题的数学模型；分析待优化的问题，建立问题的数学模型；(2)分析数学模型，选择合适的最优化算法；分析数学模型，选择合适的最优化算法；(3)编写计算机程序、上机计算、求出最优解；编写计算机程序、上机计算、求出最优解；(4)结果检验与最后决策。结果检验与最后决策。5/24/20225转化为最小化问题。3.1概述概述最优化问题的数学描述最优化问题的数学描述5/24/20226(1)枚举法。枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该
5、方法要求先对其进行离散化处理，这样就有可能产生续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。无法求解。(2)启发式算法。启发式算法。寻寻求求一一种种能能产产生生可可行行解解的的启启发发式式规规则则，以以找找到到一一个个最最优优解解或或近近似似最最优优解解。该该方方法法的的求求解解效效率率虽虽然然比比较较高高，但但对对每每一一个个需需要要求求解解的的问问题
6、题都都必必须须找找出出其其特特有有的的启启发发式式规规则则，这这个个启启发发式式规规则则无无通通用用性性，不适合于其他问题。不适合于其他问题。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法1/25/24/20227(3)搜搜索索算算法法。寻寻求求一一种种搜搜索索算算法法，该该算算法法在在可可行行解解集集合合的的一一个个子子集集内内进进行行搜搜索索操操作作，以以找找到到问问题题的的最最优优解解或或近近似似最最优优解解。该该方方法法虽虽然然保保证证不不了了一一定定能能够够得得到到问问题题的的最最优优解解，但但若若适适当当地地利利用用一一些些启启发发知知识识，就就可可在在近近似似
7、解解的的质质量量和和求求解解效效率率上上达达到到种种较较好好的的平衡。平衡。3.1概述概述求最优解或近似最优解的方法求最优解或近似最优解的方法2/25/24/20228以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具有完善的数学基础，具有计算效率高、可靠性强和比较成熟具有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下：等特点。这些算法的基本迭代步骤如下：3.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法5/24/202293.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法
8、最速下降法最速下降法5/24/2022103.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法牛顿法牛顿法5/24/2022113.1概述概述求解最优化问题的传统方法求解最优化问题的传统方法共轭方向法共轭方向法5/24/202212l对目标函数和约束函数表达的要求必须更为宽松对目标函数和约束函数表达的要求必须更为宽松l计算的效率比理论上的最优性更重要计算的效率比理论上的最优性更重要l算法随时终止能够随时得到较好的解算法随时终止能够随时得到较好的解l对优化模型中数据的质量要求更为宽松对优化模型中数据的质量要求更为宽松实实际际生生活活中中对对最最优优化化方方法法性性能能的的需需求求促促进
9、进了了最最优优化化方方法法的的发发展展，最最优优化化逐逐步步走走出出“象象牙牙塔塔”，面面向向实实际际需需要要，完完成成了了从从“方方法法定向定向”到到“问题定向问题定向”的转换。的转换。3.1概述概述对最优化提出的新的需求对最优化提出的新的需求5/24/202213l1975年年，Holland提提出出遗遗传传算算法法(GeneticAlgorithm)。这这种种优优化化方方法法模模仿仿生生物物种种群群中中优优胜胜劣劣汰汰的的选选择择机机制制，通通过过种种群群中中优优势势个体的繁衍进化来实现优化的功能。个体的繁衍进化来实现优化的功能。l1977年年，Glover提提出出禁禁忌忌搜搜索索(Ta
10、buSearch)算算法法。这这种种方方法法将将记记忆忆功功能能引引入入到到最最优优解解的的搜搜索索过过程程中中，通通过过设设置置禁禁忌忌区区阻阻止止搜索过程中的重复，从而大大提高了寻优过程的搜索效率。搜索过程中的重复，从而大大提高了寻优过程的搜索效率。l1983年年，Kirkpatrick提提出出了了模模拟拟退退火火(SimulatedAnnealing)算算法法。这这种种算算法法模模拟拟热热力力学学中中退退火火过过程程能能使使金金属属原原子子达达到到能能量量最最低低状状态态的的机机制制，通通过过模模拟拟的的降降温温过过程程，按按玻玻兹兹曼曼(Boltzmann)方方程程计计算算状状态态间间
11、的的转转移移概概率率来来引引导导搜搜索索，从从而而使使算算法法具具有有很很好好的全局搜索能力。的全局搜索能力。3.1概述概述新的优化方法不断出现新的优化方法不断出现1/25/24/202214l20世世纪纪90年年代代初初，Dorigo等等提提出出蚁蚁群群优优化化算算法法(AntColonyOptimization)算算法法。这这种种算算法法借借鉴鉴蚁蚁群群群群体体利利用用信信息息素素相相互互传传递递信信息息来来实实现现路路径径优优化化的的机机理理，通通过过记记忆忆路路径径信信息息素素的的变变化化来来解决组合优化问题。解决组合优化问题。l1995年年 ， Kenedy和和 Eberhart提提
12、 出出 粒粒 子子 群群 优优 化化 (ParticleSwarmOptimization)算算法法。这这种种方方法法模模仿仿鸟鸟类类和和鱼鱼类类群群体体觅觅食食迁迁移移中中，个个体体与与群群体体协协调调一一致致的的机机理理，通通过过群群体体最最优优方方向向、个个体最优方向和惯性方向的协调来求解实数优化问题。体最优方向和惯性方向的协调来求解实数优化问题。l1999年年，Linhares提提出出了了捕捕食食搜搜索索(PredatorySearch)算算法法。这这种种算算法法模模拟拟猛猛兽兽捕捕食食中中大大范范围围搜搜寻寻和和局局部部蹲蹲守守的的特特点点，通通过过设设置置全全局局搜搜索索和和局局部
13、部搜搜索索间间变变换换的的阈阈值值来来协协调调两两种种不不同同的的搜搜索索模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。3.1概述概述新的优化方法不断出现新的优化方法不断出现2/25/24/202215l不不以以达达到到某某个个最最优优性性条条件件或或找找到到理理论论上上的的精精确确最最优优解解为为目目标标，而是更看重计算的速度和效率；而是更看重计算的速度和效率；l对目标函数和约束函数的要求十分宽松；对目标函数和约束函数的要求十分宽松；l算算法法的的基基本本思思想想都都是是来来自自对对某某种种自自然然规规律律的的模模仿仿，具具有有人人工
14、工智能的特点；智能的特点；l多多数数算算法法含含有有一一个个多多个个体体的的群群体体，寻寻优优过过程程实实际际上上就就是是种种群群的进化过程；的进化过程；l理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。3.1概述概述新的算法的一些共同特点新的算法的一些共同特点5/24/202216l由由于于算算法法理理论论薄薄弱弱，最最早早被被称称为为“现现代代启启发发式式(ModernHeuristics)”或或“高级启发式高级启发式(AdvancedHeuristics)”；l从从其其人人工工智智能能的的特特点点，被被称称为为“智智能能计计算算
15、(IntelligentComputation)”或或“智智能能优优化化算算法法(Intelligent OptimizationAlgorithms)”；l从从不不以以精精确确解解为为目目标标的的特特点点，又又被被归归到到“软软计计算算(SoftComputing)”方法中；方法中；l从从 种种 群群 进进 化化 的的 特特 点点 看看 ， 它它 们们 又又 可可 以以 称称 为为 “进进 化化 计计 算算(EvolutionaryCompuation)”；l从从模模仿仿自自然然规规律律的的特特点点出出发发，又又有有人人将将它它们们称称为为“自自然然计计算算(NaturalComputing
16、)”。3.1概述概述新的优化方法的不同名称新的优化方法的不同名称5/24/202217l应用智能优化算法解决各类问题是重点；应用智能优化算法解决各类问题是重点；l算法改进有很大的创新空间；算法改进有很大的创新空间；l多种算法结合的混合算法是一条捷径；多种算法结合的混合算法是一条捷径；l不提倡刻意去追求理论成果；不提倡刻意去追求理论成果；l算法性能的测算是一项要下真功夫的工作；算法性能的测算是一项要下真功夫的工作；l选选择择测测试试例例题题的的一一般般规规律律：网网上上题题库库中中的的例例题题文文献献中中的的例例题题随机产生的例题随机产生的例题实际应用问题实际应用问题自己编的例题；自己编的例题；l算算法法性性能能测测试试的的主主要要指指标标：达达优优率率(解解的的目目标标平平均均值值和和最最优优解解的的目目标标值值的的比比，所所有有解解的的目目标标值值的的标标准准差差等等)，计计算算速速度度，计计算算大规模问题的能力；大规模问题的能力；l创造出新算法创造出新算法3.1概述概述怎样学习研究智能优化方法怎样学习研究智能优化方法5/24/2022183.2 遗传算法遗传算法5/24/20221
