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

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

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

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

3、机程序、上机计算、求出最优解；(4)结果检验与最后决策。9/20/20215转化为最小化问题。3.1概述——最优化问题的数学描述9/20/20216(1)枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。(2)启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则

4、无通用性，不适合于其他问题。3.1概述——求最优解或近似最优解的方法1/29/20/20217(3)搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到—种较好的平衡。3.1概述——求最优解或近似最优解的方法2/29/20/20218以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下：3.1概述——求解最优化问题的传统方法

5、9/20/202193.1概述——求解最优化问题的传统方法——最速下降法9/20/2021103.1概述——求解最优化问题的传统方法——牛顿法9/20/2021113.1概述——求解最优化问题的传统方法——共轭方向法9/20/202112对目标函数和约束函数表达的要求必须更为宽松计算的效率比理论上的最优性更重要算法随时终止能够随时得到较好的解对优化模型中数据的质量要求更为宽松实际生活中对最优化方法性能的需求促进了最优化方法的发展，最优化逐步走出“象牙塔”，面向实际需要，完成了从“方法定向”到“问题定向”的转换。3.1概述——对最优化提出的新的需求9/20/202113

6、1975年，Holland提出遗传算法(GeneticAlgorithm)。这种优化方法模仿生物种群中优胜劣汰的选择机制，通过种群中优势个体的繁衍进化来实现优化的功能。1977年，Glover提出禁忌搜索(TabuSearch)算法。这种方法将记忆功能引入到最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，从而大大提高了寻优过程的搜索效率。1983年，Kirkpatrick提出了模拟退火(SimulatedAnnealing)算法。这种算法模拟热力学中退火过程能使金属原子达到能量最低状态的机制，通过模拟的降温过程，按玻兹曼(Boltzmann)方程计算状态间的转

7、移概率来引导搜索，从而使算法具有很好的全局搜索能力。3.1概述——新的优化方法不断出现1/29/20/20211420世纪90年代初，Dorigo等提出蚁群优化算法(AntColonyOptimization)算法。这种算法借鉴蚁群群体利用信息素相互传递信息来实现路径优化的机理，通过记忆路径信息素的变化来解决组合优化问题。1995年，Kenedy和Eberhart提出粒子群优化(ParticleSwarmOptimization)算法。这种方法模仿鸟类和鱼类群体觅食迁移中，个体与群体协调一致的机理，通过群体最优方向、个体最优方向和惯性方向的协调来求解