智能优化算法总结.pdf

智能优化算法总结 优化算法有很多，经典算法包括：有线性规划，动态规划等；改进型局部搜索算法包括爬⼭法，最速下降法等，模拟退⽕、遗传算法以及禁 忌搜索称作指导性搜索法。⽽神经⽹络，混沌搜索则属于系统动态演化⽅法。 梯度为基础的传统优化算法具有较⾼的计算效率、较强的可靠性、⽐较成熟等优点，是⼀类最重要的、应⽤最⼴泛的优化算法。但是，传统 的最优化⽅法在应⽤于复杂、困难的优化问题时有较⼤的局限性。⼀个优化问题称为是复杂的，通常是指具有下列特征之⼀：（1）⽬标函 数没有明确解析表达；（2）⽬标函数虽有明确表达，但不可能恰好估值；（3）⽬标函数为多峰函数；（4）⽬标函数有多个，即多⽬标优 化。⼀个优化问题称为是困难的，通常是指：⽬标函数或约束条件不连续、不可微、⾼度⾮线性，或者问题本⾝是困难的组合问题。传统优 化⽅法往往要求⽬标函数是凸的、连续可微的，可⾏域是凸集等条件，⽽且处理⾮确定性信息的能⼒较差。这些弱点使传统优化⽅法在解决 许多实际问题时受到了限制。 智能优化算法⼀般都是建⽴在⽣物智能或物理现象基础上的随机搜索算法，⽬前在理论上还远不如传统优化算法完善，往往也不能确保解的 最优性，因⽽常常被视为只是⼀些"元启发式⽅法"（meta-heuristic）。但从实际应⽤的观点看，这类新算法⼀般不要求⽬标函数和约束 的连续性与凸性，甚⾄有时连有没有解析表达式都不要求，对计算中数据的不确定性也有很强的适应能⼒。 下⾯给出⼀个局部搜索，模拟退⽕，遗传算法，禁忌搜索的形象⽐喻： 　　 　　为了找出地球上最⾼的⼭，⼀群有志⽓的兔⼦们开始想办法。 　　　 　　1．兔⼦朝着⽐现在⾼的地⽅跳去。他们找到了不远处的最⾼⼭峰。但是这座⼭不⼀定是珠穆朗玛峰。这就是局部搜索，它不能保证局 部最优值就是全局最优值。 　　　 　　2．兔⼦喝醉了。他随机地跳了很长时间。这期间，它可能⾛向⾼处，也可能踏⼊平地。但是，他渐渐清醒了并朝最⾼⽅向跳去。这就 是模拟退⽕。 　　3．兔⼦们吃了失忆药⽚，并被发射到太空，然后随机落到了地球上的某些地⽅。他们不知道⾃⼰的使命是什么。但是，如果你过⼏年 就杀死⼀部分海拔低的兔⼦，多产的兔⼦们⾃⼰就会找到珠穆朗玛峰。这就是遗传算法。 　　　 　　4.兔⼦们知道⼀个兔的⼒量是渺⼩的。他们互相转告着，哪⾥的⼭已经找过，并且找过的每⼀座⼭他们都留下⼀只兔⼦做记号。他们制 定了下⼀步去哪⾥寻找的策略。这就是禁忌搜索。 ⼀般⽽⾔，局部搜索就是基于贪婪思想利⽤邻域函数进⾏搜索，若找到⼀个⽐现有值更优的解就弃前者⽽取后者。但是，它⼀般只可以得 到"局部极⼩解"，就是说，可能这只兔⼦登"登泰⼭⽽⼩天下"，但是却没有找到珠穆朗玛峰。⽽模拟退⽕，遗传算法，禁忌搜索，神经 ⽹络等从不同的⾓度和策略实现了改进，取得较好的"全局最⼩解"。 　　 　　模拟退⽕算法（Simulated Annealing，SA） 　　 　　模拟退⽕算法的依据是固体物质退⽕过程和组合优化问题之间的相似性。物质在加热的时候，粒⼦间的布朗运动增强，到达⼀定强度 后，固体物质转化为液态，这个时候再进⾏退⽕，粒⼦热运动减弱，并逐渐趋于有序，最后达到稳定。 　　 　　模拟退⽕的解不再像局部搜索那样最后的结果依赖初始点。它引⼊了⼀个接受概率p。如果新的点（设为pn）的⽬标函数f（pn）更 好，则p=1，表⽰选取新点；否则，接受概率p是当前点（设为pc）的⽬标函数f（pc），新点的⽬标函数f（pn）以及另⼀个控制参数"温 度"T的函数。也就是说，模拟退⽕没有像局部搜索那样每次都贪婪地寻找⽐现在好的点，⽬标函数差⼀点的点也有可能接受进来。随着算 法的执⾏，系统温度T逐渐降低，最后终⽌于某个低温，在该温度下，系统不再接受变化。 　　 　　模拟退⽕的典型特征是除了接受⽬标函数的改进外，还接受⼀个衰减极限，当T较⼤时，接受较⼤的衰减，当T逐渐变⼩时，接受较⼩的 衰减，当T为0时，就不再接受衰减。这⼀特征意味着模拟退⽕与局部搜索相反，它能避开局部极⼩，并且还保持了局部搜索的通⽤性和简 单性。 　　在物理上，先加热，让分⼦间互相碰撞，变成⽆序状态，内能加⼤，然后降温，最后的分⼦次序反⽽会更有序，内能⽐没有加热前更 ⼩。就像那只兔⼦，它喝醉后，对⽐较近的⼭峰视⽽不见，迷迷糊糊地跳⼀⼤圈⼦，反⽽更有可能找到珠峰。 值得注意的是，当T为0时，模拟退⽕就成为局部搜索的⼀个特例。 　　　 　　模拟退⽕的伪码表达： 　　procedure simulated annealing 　　begin 　　t:=0; 　　initialize temperature T 　　select a current string vc at random; 　　evaluate vc; 　　repeat 　　 repeat 　　 se 智能优化算法是现代计算技术中解决复杂优化问题的重要手段，它们源自生物智能和自然界的现象，如生物进化、物理过程等。这些算法弥补了传统优化方法在处理非线性、非凸、多目标以及存在不确定性的优化问题时的局限性。 传统优化算法，如线性规划和动态规划，依赖于目标函数的解析表达和特定的数学性质，如连续可微和凸性。然而，实际问题往往不具备这些理想条件，导致传统方法在面对复杂问题时效果不佳。相比之下，智能优化算法，如模拟退火、遗传算法和禁忌搜索，具有更强的适应性和鲁棒性。 模拟退火算法是受到固体材料退火过程启发的一种全局优化方法。它通过引入“温度”T的概念，允许在一定概率下接受劣质解，以跳出局部最优，探索全局最优。算法开始时，系统处于高温状态，新解的接受概率较高，随着温度逐渐降低，算法倾向于接受更优秀的解，最终在低温下稳定，达到全局最优或接近最优的状态。模拟退火算法的伪代码通常包括初始化温度、选择初始解、重复迭代以及根据接受准则更新解的过程。 遗传算法则是受到生物进化论启发的搜索策略，通过模拟自然选择、基因重组和突变等机制来探索解空间。算法将解表示为“个体”（如字符串），并通过操作这些个体来生成新的解，逐步优化种群，以期望找到最优解。在这个过程中，适应度高的个体更有可能被保留下来，而低适应度的个体则被淘汰。 禁忌搜索则强调记忆和学习，避免重复搜索已探索区域。它通过禁忌列表记录已尝试的解，并制定策略来决定下一步的搜索方向，防止陷入局部最优。 这些智能优化算法在解决实际问题时表现出色，例如在工程设计、调度问题、机器学习模型参数优化等领域都有广泛应用。尽管它们可能无法保证找到绝对最优解，但往往能获得满意的结果，特别是在处理大规模、高维度和复杂约束的优化问题时。 智能优化算法通过引入随机性和探索性，能够在不确定性和复杂性中寻找到问题的良好解，弥补了传统方法的不足。随着计算能力和理论研究的不断深入，这些算法在未来的应用前景将持续拓宽，为解决更多现实世界中的难题提供有力工具。