第三章求解优化问题的智能算法

《第三章求解优化问题的智能算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章求解优化问题的智能算法6/25/202113.1概述6/25/20212最优化问题是指在一定的约束条件下，决定某个或某些可控制的因素应有的合理取值，使所选定的目标达到最优的问题。解决最优化问题的方法称为最优化方法。它具有高度应用性和技术性的特点。最优化问题可以追溯到十分古老的极值问题，在17世纪，伟大科学家Newton发明微积分的时候，已经提出了极值问题，后来又出现了Lagrange乘子法，Cauchy则利用最速下降法求解无约束极小化问题。然而，直到1947年Dantzig提出求解一般线性规划问题的单纯形法之后，它才成为一门独立的学科。最优化方法的研究起源和意义1/2

2、6/25/20213随着近代科学技术发展的需要，特别是由于计算机技术的飞速发展，促进了最优化方法的迅速发展，并很快渗透到各个领域。20世纪70年代，最优化方法这门应用技术科学又开始产生出最优设计、最优控制与最优管理等分支。到20世纪80年代，最优化技术又在这些分支中发展出了新的更细的分支，比如，工程技术领域的机械优化设计、建筑结构优化设计以及化工石油领域的优化设计等。最优化方法的研究起源和意义2/26/25/20214求解优化问题的步骤(1)分析待优化的问题，建立问题的数学模型；(2)分析数学模型，选择合适的最优化算法；(3)编写计算机程序、上机计算、求出最优解；(4)结果

3、检验与最后决策。6/25/20215最优化问题的数学描述转化为最小化问题。6/25/20216求解最优化问题的传统方法以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下：6/25/20217最速下降法6/25/20218牛顿法6/25/20219共轭方向法6/25/202110对最优化提出的新的需求对目标函数和约束函数表达的要求必须更为宽松计算的效率比理论上的最优性更重要算法随时终止能够随时得到较好的解对优化模型中数据的质量要求更为宽松实际生活中对最优化方法性能的需求促进了最优化方法

4、的发展，最优化逐步走出“象牙塔”，面向实际需要，完成了从“方法定向”到“问题定向”的转换。6/25/202111新的优化方法不断出现1/21975年，Holland提出遗传算法(GeneticAlgorithm)。这种优化方法模仿生物种群中优胜劣汰的选择机制，通过种群中优势个体的繁衍进化来实现优化的功能。1977年，Glover提出禁忌搜索(TabuSearch)算法。这种方法将记忆功能引入到最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，从而大大提高了寻优过程的搜索效率。1983年，Kirkpatrick提出了模拟退火(SimulatedAnnealing)算法。

5、这种算法模拟热力学中退火过程能使金属原子达到能量最低状态的机制，通过模拟的降温过程，按玻兹曼(Boltzmann)方程计算状态间的转移概率来引导搜索，从而使算法具有很好的全局搜索能力。6/25/202112新的优化方法不断出现1/220世纪90年代初，Dorigo等提出蚁群优化算法(AntColonyOptimization)算法。这种算法借鉴蚁群群体利用信息素相互传递信息来实现路径优化的机理，通过记忆路径信息素的变化来解决组合优化问题。1995年，Kenedy和Eberhart提出粒子群优化(ParticleSwarmOptimization)算法。这种方法模仿鸟类和鱼类

6、群体觅食迁移中，个体与群体协调一致的机理，通过群体最优方向、个体最优方向和惯性方向的协调来求解实数优化问题。1999年，Linhares提出了捕食搜索(PredatorySearch)算法。这种算法模拟猛兽捕食中大范围搜寻和局部蹲守的特点，通过设置全局搜索和局部搜索间变换的阈值来协调两种不同的搜索模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。6/25/202113新的算法的一些共同特点不以达到某个最优性条件或找到理论上的精确最优解为目标，而是更看重计算的速度和效率；对目标函数和约束函数的要求十分宽松；算法的基本思想都是来自对某种自然规律的模仿，具有人工智能的特点；多数

7、算法含有一个多个体的群体，寻优过程实际上就是种群的进化过程；理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。6/25/202114不同的名称由于算法理论薄弱，最早被称为“现代启发式(ModernHeuristics)”或“高级启发式(AdvancedHeuristics)”；从其人工智能的特点，被称为“智能计算(IntelligentComputation)”或“智能优化算法(IntelligentOptimizationAlgorithms)”；从不以精确解为目标的特点，又被归到“软计算(SoftCompu