启发式算法概述
Oct 28, 2018·
·
2 min read
Shenghui (Samuel) Gu
启发式算法（Heuristic Algorithm）是相对于最优化算法提出的。 它有不同的定义：
- 其中一种是，一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。
- 另一种是，启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。
启发式算法是一种近似算法，它更像是一种算法框架，定义了算法的流程步骤，并没有成型的理论体系。
有一类的通用启发式策略称为元启发式算法（Metaheuristic），通常使用乱数搜寻技巧。 他们可以应用在非常广泛的问题上，但不能保证效率。 近年来随着智能计算领域的发展，出现了一类被称为超启发式算法（Hyper-Heuristic Algorithm）的新算法类型。
以下表格是对启发式算法的分类：
| 传统启发式算法 | 元启发式算法 | 超启发式算法 | |
|---|---|---|---|
| 搜索空间 | 由实例解构成 | 由实例解构成 | 由启发式算法构成 |
| 问题的领域知识 | 需要 | 需要 | 不需要（或很少需要） |
| 典型类别 | 局部搜索 | 蚁群算法 | 基于随机选择的超启发式算法 |
| 爬山法 | 粒子群算法 | 基于贪心策略的超启发式算法 | |
| 贪心法 | 模拟退火算法 | 基于元启发式算法的超启发式算法 | |
| 遗传算法 | 基于学习的超启发式算法 | ||
| 禁忌搜索 | |||
| 进化规划 | |||
| 进化策略 | |||
| 变邻域搜索 | |||
| 人工神经网络 |
Authors
Shenghui (Samuel) Gu
(he/him)
Postdoctoral Researcher
Postdoctoral Researcher at the University of Ottawa specializing in Trustworthy AI and Software Engineering, holding a Ph.D. from Nanjing University.
Research lies at the intersection of AI Safety and System Reliability, with deep expertise spanning LLM-driven testing, search-based software engineering for autonomous systems, and AIOps for distributed architectures.
Dedicated to developing rigorous, interpretable, and scalable methodologies that leverage generative AI to solve complex validation challenges in safety-critical and large-scale industrial systems.