优化问题求解算法：精确式、启发式、元启发式、超启发式
日期：2024-06-18 21:08:07 / 人气：
介绍四种类别算法的定义，来自于文献，具有一定的代表性而非确定性。
1.精确式算法：找到最优解并评估最优性
Exact optimization methods (Jourdan et al, 2009): ‘Exact methods find the optimal solution and assess its optimality’.
2.启发式算法：为复杂的优化问题快速生成近似最优解，构造启发式每次添加单个元素（节点、弧）等生成解决方案；贪婪启发式追求每一步的最大化改进；改进启发式从可行解开始利用邻域搜索来逐步迭代改进，一般来说，迭代过程中会保持解可行。
Heuristics (Zanakis et al, 1989)：Their [heuristics] appeal stems from their ability to produce quickly near-optimal solutions to difficult optimization problems. As opposed to the advanced mathematics that is required to develop theoretical results in the optimization arena, the development of heuristics is chiefly an art and a creative problem solving endeavor.‘Construction algorithms generate a solution by adding individual components (eg, nodes, arcs, variables) one at a time until a feasible solution is obtained. Greedy’ algorithms, seeking to maximize improvement at each step, comprise a large class of construction heuristics. In most construction heuristics, a feasible solution is not found until the end of the procedure’ and ‘Improvement heuristics begin with a feasible solution and successively improve it by a sequence of exchanges or mergers in a local search. Generally, a feasible solution is maintained throughout the procedure’.
3.元启发式算法：独立于问题的算法框架，提供一些标准用来指导启发式算法的开发，可以用来描述针对特定问题设计的启发式优化算法。
Metaheuristics (Talbi, 2009; S?rensen and Glover, 2013): ‘A metaheuristic is a high-level problem-independent algorithmic framework that provides a set of guidelines or strategies to
develop heuristic optimization algorithms. The term is also used to refer to a problem-specific implementation of a heuristic optimization algorithm according to the guidelines expressed in
such a framework’.
4.超启发式算法：提供了某种高层策略，通过操纵或管理一组低层启发式算法，生成新启发式算法。“寻找启发式算法的启发式算法。”
Hyper-heuristics (Burke et al, 2013): ‘A search method or learning mechanism for selecting or generating heuristics to solve computational search problems’.
参考文献：
Jourdan L, Basseur M and Talbi E-G (2009). Hybridizing exact methods and metaheuristics: A taxonomy. European Journal of Operational Research 199(3): 620–629.
Zanakis SH, Evans JR and Vazacopoulos AA (1989). Heuristic methods and applications: A categorized survey. European Journal of Operational Research 43(1): 88–110.
Talbi E-G (2009). Metaheuristics: From Design to Implementation. Wiley: Hoboken, NJ.
S?rensen K and Glover F (2013). Encyclopedia of Operations Research and Management Science. chap. Metaheuristics, 3rd edn. Springer:New York.
Burke EK et al (2013). Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society 64(12): 1695–1724.
