启发式算法
什么是算法？从枚举到贪心再到启发式（上）
目标：要优化的东西
决策：根据目标做出的决策
约束：进行决策时必须遵循的条件
算例：问题参数的具体化
枚举法：将问题所有的解一一枚举出来，挨个去评价，选出最好的那个
1.枚举法能够找到问题的最优解
2.枚举法求解时间随问题规模增长而呈爆炸式增长
贪心法：利用“构造”的方式生成解，速度相对而言会非常快，同时不会随着问题规模的增长而大幅度增加，是平缓的线性增长
什么是算法？从枚举到贪心再到启发式（下）
启发式算法：在一个合理的求解资源范围内（合理的时间，合理的内存开销等）求得一个较为满意的解。目前主要包括邻域搜索和群体仿生两大类。
解空间：所有该问题的解的集合，包括可行解和不可行解
局部搜索：不完全遍历解空间，只选择一部分进行遍历，进而大大降低搜索需要的资源。为了提高局部搜索的质量，大部分局部搜索算法都会在搜索的时候不断地抓取多个区域进行搜索，直到满足算法终止条件。
邻域：在邻域结构定义下的解的集合，它是一个相对的概念，即邻域肯定是基于某个解产生的
邻居解：邻域内某个解的称呼
邻域结构：定义了一个解的邻域
邻域结构的设计在启发式算法中非常重要，它直接决定了搜索的范围，对最终的搜索结构有着重要的影响，直接决定了最终结果质量的好坏
搜索过程
- 初始解生成
一般初始解都采用构造法进行生成，比如随机构造、贪心构造 - 邻域生成
根据所定义的邻域结构生成邻域 - 评价
在解的邻域范围内对邻居解进行评价，然后选出需要的邻居解进行“移动”。一般而言，有两种评价的模式：
first improve：首次提升原则，即在邻域内对解一一进行评价，一旦发现比当前解更优的邻居解立马进行“移动”。
best improve：最优提升原则，遍历整个邻域，找出最好的邻居解进行“移动”。
若初始解即生成在了一个局部最优上面，通常选择邻域中一个最好的邻居解进行移动（尽管它比当前解还要差），避免彻底陷入局部最优
扰动是跳出局部最优一个非常有效的做法，通常的实现方式是利用随机或者其他方式，对当前解进行重组，使其结构发生较大的改变。或者直接抛弃当前解，重新生成一个解进行后续的邻域搜索。 - 移动
当前解变换到刚刚评价选择的邻居解的过程 - 记录全局最优解
如果当前解比全局最优解还要优，那么更新全局最优解
不断重复步骤2-步骤5，直到满足终止条件，最后输出全局最优解
所有的启发式找到的都是满意解，不能说是最优解（即便真的是），因为它遍历的是解空间的局部。
一般情况下，启发式算法的时间是随着问题规模增长而呈线性增长的
干货 | 想学习优化算法，不知从何学起？
邻域搜索类
迭代局部搜索算法
模拟退火算法
变邻域搜索算法
禁忌搜索
自适应大邻域搜索
群体仿生类
遗传算法
蚁群算法
粒子群算法
人工鱼群算法
算法应用
禁忌搜索算法求解带时间窗的车辆路径问题
基于树表示法的变邻域搜索算法求解考虑后进先出的取派货旅行商问题
变邻域搜索算法求解Max-Mean dispersion problem
遗传算法求解混合流水车间调度问题
