优化领域算法的分类

优化领域解决问题通常使用三种方法&＃xff0c;第一种是精确方法&＃xff08;Exact Approaches&＃xff09;&＃xff0c;另外还有启发式算法&＃xff08;Heuristics Algorithm&＃xff09;和以及元启发式算法&＃xff08;Meta-heuristics Algorithm&＃xff09;

1. 精确方法&＃xff08;Exact Approaches&＃xff09;&＃xff0c;通常使用数学建模的方法建立数学模型&＃xff08;包括决策变量&＃xff0c;目标函数以及约束条件&＃xff09;&＃xff0c;通过优化算法&＃xff08;单纯形法&＃xff0c;分支定界&＃xff0c;分支切割&＃xff0c;割平面方法等&＃xff09;解这个数学模型得出问题的最优解。解的好坏由模型建立的是否合理&＃xff0c;优化算法的设计等决定。

对于常见的数学模型&＃xff0c;比如线性规划&＃xff08;Linear Programming&＃xff09;&＃xff0c;整数规划 (Integer Programming)&＃xff0c;混合整数规划 (Mixed Integer Programming)&＃xff0c;二次规划 &＃xff08;Quadratic Programming&＃xff09;等&＃xff0c;都可以使用优化求解器IBM Cplex&＃xff0c;Gurobi&＃xff0c;FICO Xpress&＃xff0c;SCIP &＃xff08;前两个学术用户可以免费申请&＃xff0c;最后一个是开源的&＃xff09;等进行求解&＃xff0c;大大节省了求解时间。关于各个优化求解器性能&＃xff0c;可参见这个网址&＃xff0c;可以看出Cplex 和 Gurobi 的性能总体较好。值得注意的是&＃xff0c;这个网站的性能对比仅仅是对比算例的结果&＃xff0c;对于其他模型或者算例的结果可能有所不同。比如我最近解决一个问题&＃xff0c;同样的求解器&＃xff0c;同样的问题&＃xff0c;变量和约束少的模型求解时间时间是变量和约束多的模型求解时间近十倍。

为什么使用启发式算法呢&＃xff1f;使用精确方法虽然可以求得最优解&＃xff08;Optimal Solution&＃xff09;&＃xff0c;可以从理论上证明求得的解是最优的&＃xff0c;但随着问题规模的扩大&＃xff08;可能呈指数级或者阶乘级的增长&＃xff09;&＃xff0c;对于中等规模或者大规模的问题&＃xff0c;在有限的时间内不可能求得最优解&＃xff08;对于我研究的问题&＃xff0c;目前可以求得42个机器最优解&＃xff09;。这就需要在求解精读和运算时间之间有一个折衷和权衡&＃xff08;trade off&＃xff09;。对于大规模的问题&＃xff0c;我们不需要求得最优解&＃xff0c;只需在短时间内求得次优解&＃xff08;Sub-Optimal Solution&＃xff09;或者满意解&＃xff08;Satisfactory Solution&＃xff09;&＃xff08;西南交通大学靳番教授和金炜东教授对满意优化理论做了开创性研究&＃xff09;&＃xff0c;加之计算机性能的提升&＃xff0c;出现了启发式算法。

作者&＃xff1a;知乎用户
链接&＃xff1a;https://www.zhihu.com/question/29762576/answer/212138630
来源&＃xff1a;知乎
著作权归作者所有。商业转载请联系作者获得授权&＃xff0c;非商业转载请注明出处。
 

2. 启发式算法&＃xff08;Heuristics Algorithm&＃xff09;&＃xff0c;启发式算法是以问题为导向&＃xff08;Problem-oriented&＃xff09;程序&＃xff0c;根据问题的特殊结构或者性质来改进解。一般情况下&＃xff0c;启发式算法比精确方法更容易实现。启发式算法包括构造算法&＃xff08;Construction Algorithm&＃xff09;和 改进算法 &＃xff08;Improvement Algorithm&＃xff09;等。对于构造算法&＃xff08;Construction Algorithm&＃xff09;&＃xff0c;针对布局问题&＃xff0c;对于和其它机器流量比较小的机器尽量摆在机器序列的两端&＃xff0c;这样就可以形成一个启发式规则&＃xff0c;基于流量的排列&＃xff08;Flow-based permutation, FBP&＃xff09;&＃xff0c; 这样就可以根据这个规则得到机器序列&＃xff1b;另外还有基于机器长度的排列&＃xff08;Length-based permutation, LBP&＃xff09;规则&＃xff0c;尽量把长度小的机器排列到中间&＃xff0c;基于这规则也可以得到一个机器序列。这样产生的解都是可行解&＃xff08;Feasible Solution&＃xff09;&＃xff0c;但一般情况下都不是最优解。对于 改进算法 &＃xff08;Improvement Algorithm&＃xff09;&＃xff0c;常见的就是使用基于贪婪方法的爬山法&＃xff08;Hill Climbing&＃xff09;&＃xff0c;见下图&＃xff0c;它是由一个初始解开始改进解&＃xff0c;爬山法太贪婪&＃xff0c;容易陷入局部最优&＃xff08;Local Optimum&＃xff09;。如图所示&＃xff0c;从C点搜索到A点&＃xff0c;就陷入了局部最优&＃xff0c;而问题的全局最优在B点。

3. 元启发式算法&＃xff08;Meta-heuristics Algorithm&＃xff09;&＃xff0c;相对于启发式算法&＃xff0c;元启发式算法是问题独立&＃xff08;Problem-independent&＃xff09;的是针对大范围的优化问题提供通用的流程。一般地&＃xff0c;需要提供至少一个初始可行解&＃xff08;Initial Feasible Solution&＃xff09;&＃xff0c;在预定义的搜索空间高效搜索用以迭代地改进解。可以分为基于单个解&＃xff08;Single solution based&＃xff09;的元启发式算法&＃xff0c;例如&＃xff1a; 模拟退火算法 &＃xff08;Simulated Annealing&＃xff09;和禁忌搜索算法&＃xff08;Tabu Search&＃xff09;&＃xff1b; 另外是基于群体&＃xff08;Population based&＃xff09;的元启发式算法&＃xff0c;比如遗传算法&＃xff08;Genetic Algorithm&＃xff09;,分散搜索算法&＃xff08;Scatter Search Algorithm&＃xff09;,粒子群算法&＃xff08;Particle Swarm Optimization&＃xff09;和蚁群算法&＃xff08;Ant Colony Optimization&＃xff09;等。元启发式算法可以使用某些操作跳出局部最优。

现在越来越多的学者使用混合算法&＃xff08;Hybrid Algorithm&＃xff09;,包括元启发式算法与精确方法的混合&＃xff0c;比如这篇09年的综述文章&＃xff1a;Hybridizing exact methods and metaheuristics: A taxonomy。对于双行布局问题&＃xff0c;既要确定机器排列顺序&＃xff0c;又要确定机器的精确位置&＃xff0c;这是一个组合优化和连续优化结合的问题&＃xff0c;对于大规模的算例&＃xff0c;需要元启发式算法和精确方法协同解决。元启发式算法与启发式算法的混合&＃xff0c;元启发式算法的性能非常依赖初始解的质量&＃xff0c;可以使用启发式算法为元启发式算法产生初始解&＃xff0c;以提高其性能。元启发式算法与元启发式算法的混合&＃xff0c;可以参考11年的综述文章&＃xff1a;Hybrid metaheuristics in combinatorial optimization: A survey。算法的混合可以发挥各个算法的优点&＃xff0c;抵消其缺点&＃xff0c;以实现更好的性能。

元启发算法范围内大部分应用了随机优化机构&＃xff0c;多目标优化用的蛮多。但是多目标优化中&＃xff0c;目标太多时一般会先降维&＃xff08;比如PCA&＃xff09;&＃xff0c;多于3-5个目标的优化效率低&＃xff0c;也没有太多实际的可读性。接近实际的案例里面一般都会涉及多种算法&＃xff0c;先用元启发算法求得一个小范围的满意解&＃xff0c;再用启发或者精确算法找最优解&＃xff0c;这样即提高了计算效率又能有高质量结果。

参考连接&＃xff1a;https://www.zhihu.com/question/29762576