最优化算法——常见优化算法分类及总结

之前做特征选择，实现过基于群智能算法进行最优化的搜索，看过一些群智能优化算法的论文，在此做一下总结。最优化问题　　在生活或者工作中存在各种各样的最优化问题，比如每个企业和个人都要考虑的一个问题“在一定成本下，如何使利润最大化”等。最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。　　工程设计中最优化问题（optim...

超级代码搬运工

139878人浏览 · 2018-10-27 12:54:53

超级代码搬运工 · 2018-10-27 12:54:53 发布

之前做特征选择，实现过基于群智能算法进行最优化的搜索，看过一些群智能优化算法的论文，在此做一下总结。

最优化问题

　　在生活或者工作中存在各种各样的最优化问题，比如每个企业和个人都要考虑的一个问题“在一定成本下，如何使利润最大化”等。最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。

　　工程设计中最优化问题（optimalization problem）的一般提法是要选择一组参数（变量），在满足一系列有关的限制条件（约束）下，使设计指标（目标）达到最优值。因此，最优化问题通常可以表示为数学规划形式的问题。进行工程优化设计时，应将工程设计问题用上述形式表示成数学问题，再用最优化的方法求解。这项工作就是建立优化设计的数学模型。

　　
　　最优化问题分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间的连续变量，而组合优化的对象则是解空间中的离散状态。其中典型的组合优化问题有旅行商(Traveling salesman problem,TSP)问题、加工调度问题(Scheduling problem,如Flow-shop,Job-shop)、0-1背包问题(Knapsack problem)、装箱问题(Bin packing problem)、图着色问题(Graph coloring problem)、聚类问题(Clustering problem)等。

最优化算法

根据自己对最优化的理解，采用最优化算法解决实际问题主要分为下列两步：

建立数学模型。对可行方案进行编码（变量），约束条件以及目标函数的构造。
最优值的搜索策略。在可行解（约束条件下）搜索最优解的方法，有穷举、随机和启发式搜索方法。

最优化算法有三要素：变量（Decision Variable）、约束条件（Constraints）和目标函数（Objective function）。最优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或规则来得到满足用户要求的问题的解。

优化问题相关算法有如下分类：

精确算法(绝对最优解)

精确算法包括线性规划、动态规划、整数规划和分支定界法等运筹学中的传统算法，其算法计算复杂性一般很大，只适合于求解小规模问题，在工程中往往不实用。

启发式算法（近似算法）

　　启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。

领域搜索算法。从任一解出发，对其领域的不断搜索和当前解的替换来实现优化。根据搜索行为，它又可分为局部搜索法和指导性搜索法。

局部领域搜索法（也称爬山法）。以局部优化策略在当前解的领域中贪婪搜索，如只接受优于当前解的状态作为下一当前解的爬山法；接受当前邻域中的最好解作为下一当前解的最陡下降法等。
指导性搜索法。利用一些指导规则来指导整个解空间中优良解的探索，如SA、GA、EP、ES和TS等.

个体启发（寻找相对最优）

特点：每次输出的是相同的。从一个解开始，寻找最优，易陷入局部最优。

爬山算法

算法思想：从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(即山峰最高点)；反之就用最高的邻居节点替换当前节点，从而实现向山峰的高处攀爬的目的。

其实就是，在初始值的附近，找到最大的一个。

优点
- 容易理解，容易实现，具有较强的通用性；
- 局部开发能力强，收敛速度很快
缺点
- 全局开发能力弱，只能搜索到局部最优解；
- 搜索结果完全依赖于初始解和邻域的映射关系。

禁忌算法(Tabu Search，TS)

基本思想：基于爬山算法的改进，标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某一局部区域以及其邻域的搜索，导致一叶障目。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而或得更多的搜索区域

特点：
- 避免在搜索过程中的循环
- 只进不退的原则,通过禁忌表实现
- 不以局部最优作为停止准则
- 邻域选优的规则模拟了人类的记忆功能
禁忌表：用于防止搜索出现循环
- 记录前若干步走过的点、方向或目标值，禁止返回
- 表是动态更新的
- 表的长度称为Tabu-Size
禁忌表的主要指标（两项指标）
- 禁忌对象：禁忌表中被禁的那些变化元素
- 禁忌长度：禁忌的步数
禁忌对象（三种变化）
- 以状态本身或者状态的变化作为禁忌对象
- 以状态分量以及分量的变化作为禁忌对象
- 采用类似的等高线做法，以目标值变化作为禁忌对象
禁忌长度:可以是一个固定的常数(T=c),也可以是动态变化的，可按照某种规则或公式在区间内变化。
- 禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；
- 禁忌长度过长，候选解全部被禁忌，造成计算时间较大，也可能造成计算无法继续下去。

参考：

贪婪算法

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

基本都要先排序，从排序的开始那个依次判断，符合就留下不符合就去掉。

模拟退火(simulated annealing，SA)

模拟退火算法作为局部搜索算法的扩展，在每一次修改模型的过程中，随机产生一个新的状态模型，然后以一定的概率选择邻域中能量值大的状态．这种接受新模型的方式使其成为一种全局最优算法，并得到理论证明和实际应用的验证．SA虽然在寻优能力上不容置疑，但它是以严密的退火计划为保证的，具体地讲，就是足够高的初始温度、缓慢的退火速度、大量的迭代次数及同一温度下足够的扰动次数。