启发式算法

什么是算法？从枚举到贪心再到启发式（上）

目标 ：要优化的东西

决策 ：根据目标做出的决策

约束 ：进行决策时必须遵循的条件

算例 ：问题参数的具体化

枚举法 ：将问题所有的解一一枚举出来，挨个去评价，选出最好的那个

1.枚举法能够找到问题的最优解

2.枚举法求解时间随问题规模增长而呈爆炸式增长

贪心法 ：利用“构造”的方式生成解，速度相对而言会非常快，同时不会随着问题规模的增长而大幅度增加，是平缓的线性增长

什么是算法？从枚举到贪心再到启发式（下）

启发式算法 ：在一个合理的求解资源范围内（合理的时间，合理的内存开销等）求得一个较为满意的解。目前主要包括邻域搜索和群体仿生两大类。

解空间 ：所有该问题的解的集合，包括可行解和不可行解

局部搜索 ：不完全遍历解空间，只选择一部分进行遍历，进而大大降低搜索需要的资源。为了提高局部搜索的质量，大部分局部搜索算法都会在搜索的时候不断地抓取多个区域进行搜索，直到满足算法终止条件。

邻域 ：在邻域结构定义下的解的集合，它是一个相对的概念，即邻域肯定是基于某个解产生的

邻居解 ：邻域内某个解的称呼

邻域结构 ：定义了一个解的邻域

邻域结构的设计在启发式算法中非常重要，它直接决定了搜索的范围，对最终的搜索结构有着重要的影响，直接决定了最终结果质量的好坏

搜索过程

不断重复步骤2-步骤5，直到满足终止条件，最后输出全局最优解

所有的启发式找到的都是满意解，不能说是最优解（即便真的是），因为它遍历的是解空间的局部。

一般情况下，启发式算法的时间是随着问题规模增长而呈线性增长的

干货 | 想学习优化算法，不知从何学起？

邻域搜索类

迭代局部搜索算法

模拟退火算法

变邻域搜索算法

禁忌搜索

自适应大邻域搜索

群体仿生类

遗传算法

蚁群算法

粒子群算法

人工鱼群算法

算法应用

禁忌搜索算法求解带时间窗的车辆路径问题

基于树表示法的变邻域搜索算法求解考虑后进先出的取派货旅行商问题

变邻域搜索算法求解Max-Mean dispersion problem

遗传算法求解混合流水车间调度问题