个人笔记

1 启发式算法

启发式算法（Heuristic Algorithms）通常是以问题为导向的（Problem Specific），没有一个通用的框架，每个不同的问题通常设计一个不同的启发式算法，通常被用来解组合优化问题

普通启发式算法一般是一种贪婪算法，需要根据特定问题进行特定设计

贪婪算法，也叫贪心算法

其基本思想是：每一步都采取当前状态下最好的选择，而不考虑全局最优解是否已经达到。在每一步中，贪心算法都会做出一个贪心决策，即选择当前状态下最优的解决方案，并且不考虑这个决策可能会导致的未来后果

以经典的装包问题为例，其最简单的贪婪算法可表示如下：

# 贪心算法
def greedy_algorithm(costs, capacity):
    indices = np.argsort(costs)[::-1] # 排序物品，成本从大到小
    solution = np.zeros(len(costs)) # 初始化背包
    # 按照成本依次放入物品，直到无法放入或背包已满
    for i in indices:
        if capacity >= costs[i]:
            solution[i] = 1
            capacity -= costs[i]
    return solution

# 测试代码
if __name__ == '__main__':
    costs = np.array([3, 2, 4, 3]) # 各个物品的成本/重量
    capacity = 6 # 定义背包容量
    solution = greedy_algorithm(costs, capacity)
    print('Solution:', solution)

# 参考来源：https://zhuanlan.zhihu.com/p/614076976

2 元启发算法

元启发算法（Meta-Heuristic Aglorightms）启发式算法的改进，是随机算法+局部搜索算法的结合；相比于普通启发式算法，元启发式一般更具备通用性，可看作与问题独立的通用框架（也会包含针对问题的细节调整，但整体的迭代策略是不变的）

一般可考虑使用普通贪心算法构建启发式算法的初始解

元启发算法通常设计了跳出局部最优解的方法，改善了算法寻找全局最优解的能力

常见元启发算法：

• 遗传算法
• 蚁群算法
• 模拟退火法
• 粒子群算法

不同元启发算法的解决旅行商问题的效果对比（参考链接）：

常见的元启发算法实现可考虑Python包：scikit-opt

3 超启发算法

超启发式算法（Hyper-Heuristic Algorithm）在元启发式算法基础上， 根据算法的搜索历史去学习， 从而调整元启发算法的行为模式

超启发式算法的搜索空间不是问题的解空间，而是一组基本的启发式规则（low-level heuristics），也就是说它搜索的是适合求解该问题的算法，而不是该问题的解

更多超启发式算法的进阶阅读参阅：超启发式参考书目

4 启发类算法分析

启发类算法是一个在计算精度和计算所需耗费的资源之间做平衡的产物

启发类算法的缺点：

• 算法简单直观，易于修改，可适用于不同类型的NP-Hard问题
• 算法一般能在可接受的时间内给出一个合理的较优解，比盲目搜索效率高

启发类算法的缺点：

• 不适用于解空间过大的场景，比如神经网络的优化
• 不能对最终的近似解的质量进行保障，可能是很离谱的局部最优解
• 算法不稳定，缺乏有效的迭代停止条件，性能取决于具体问题和设计者经验

参考

精确算法、启发式算法、元启发式算法、近似算法

最优化问题+常用启发式算法