启发式算法总揽
启发式算法：一种基于经验或者式样算法的统称。
元启发式算法：自然界的一些现象取得灵感，通过这些现象的求解过程。
启发式算法的一些基础方法。
启发式算法 = 元启发式算法+ 问题特征
一、禁忌搜索算法
Tabu Search
- 从一个初始可行解出发，选择一系列的特定搜索方向作为试探，选择实现让特定的目标函数值变化最多的移动
- 为了避免陷入局部最优解，TS搜索中采用了一种灵活的记忆技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立
- 标记已经解得的局部最优解或求解过程，并在进一步迭代中避开这些局部最优解或者求解过程，局部搜索的缺点在于，太过于对某一局部以及器领域的搜索，导致一叶账目。为了找到全局最优解，禁忌搜索就是对与找到的一部分最优解，有意识的避开他，从而获得更多的搜索区域。
1.1、基本概念
领域：所谓领域，简单说就是给定点附近其他点的集合。领域就是指对当前解进行一个操作（这个操作可以称为领域动作）可以得到呃所有解的集合（类似于GA中的种群）
领域动作：
- 领域动作是一个函数，通过这个函数，对当前解s，产生其相应的领域解集合
- 例如：对于一个bool型问题，其当前解为：s=1001,当将领域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)=
禁忌表：
- 禁忌对象：犹豫需要避免一些操作的重复进行，就要将一些元素放到禁忌表中以禁止对这些元素进行操作。这些元素就是我们指的禁忌对象（通常指找到的局部最优解）
- 禁忌长度：禁忌长度是被禁对象不允许选择的迭代次数
候选集合：领域太大，不必要对所有领域中的对象进行考察，只需要选取一部分，这部分就是候选集合
评价函数：目标函数，是候选集合元素选取的一个评价公式，候选集合的元素通过评价函数值来选取。
1.2、算法步骤
Step1：禁忌表H=空集，并选定一个初始解x1
Step2：在xi的领域N(xi)中选择候选集Can_N(xi) 在候选集中选一个评价值最佳的解 xi+1
- xi+1不在禁忌表中，选为当前解
- xi+1在禁忌表中，满足破禁条件，xi+1为当前解，否则从不再禁忌表解中选择一个最优解
Step3：重复第二步，直到满足停止条件。
1.3、解决问题
TS解决5个节点的TSP问题。
二、模拟退火
三、遗传算法
基因是染色体上具有特定遗传功能的DNA片段，染色体是基因的载体。
染色体由DNA分子和蛋白质所构成，每个DNA分子上有许多的基因。
现在遗传算法的基本信息：
基因结构：每个物料对应可以生产的机组列表 List<List<Long>> genes，例如[[4,5]]说明物料1可以在机组4，机组5上面生产
种群，个体，编码，解码，交叉，变异，选择
选择：线性排序选择，指数排序选择
交叉：顺序交叉，在交叉过程中会产生非法解， 需要调整非法解
GC的编码问题：遗传算法的核心是编码！想学会优化算法，编码是核心，是必须会的！谁敢反对！
- TSP问题，城市集合{1,2,3,4,5}，染色体表示
- JSSP（作业车间调度问题）：
- 工件A：A1->A2， 工件B：B1->B2，工件C：C1
- 染色体：[A1, B1, A2, C1, B2]
- 编码能体现加工约束条件，遗传算法能高效优化排程，减少工厂等待时间和设备闲置率。
- 背包问题，在有限容量的资源下，如何选择物品组合，使总收益最大化
- 编码方式：二进制编码
- 编码原理：每个基因表示一个物品是否被选中，1表示选中，0表示不选
- 染色体实例：
- 物品集合：P1, P2, P3, P4, P5
- 染色体：[1, 0, 1, 0, 1]
- 含义：选择P1, P3, P5, 舍弃P2, P4
- 适合各种取舍类优化问题。
- 4、连续参数优化（如PID控制器调节）
- 在自动控制、信号处理、工程设计中需要优化连续参数，如PID控制器的Kp， Ki， Kd
- 编码方式：实数编码
- 编码原理：染色体直接用实数表示参数值，避免二进制转化误差
- 染色体示例：
- 参数：Kp, Ki, Kd
- 染色体：[2,35, 1.80, 4,12]
5、路径规划（无人机，机器人）
问题背景：无人机需要在复杂环境下，从起点飞到目标点，绕开障碍物并尽量节省能量
编码方式：路径节点序列编码
编码原理：染色体由路径节点序列构成，表示飞行路径
染色体示例：
- 节点：S=起点，G=终点，中间点=
- 染色体：[S, 2, 5, 7, G]
编码能自然表示路径，遗传算法可以优化最短路径或最低能耗
NSGA-2
Pareto
非支配排序
A(x1|y1) dominates B(x2|y2)
when
(x1<=x2 and y1<=y2) and (x1<x2 or y1 < y2)
- A所有目标不比B差
- 至少一个目标严格要更好
拥挤度
四、蚁群算法
就是蚂蚁会在经过的路径上面留下信息素。
对基本蚁群算法的改进：
- 在路径选择中采用利用和探索相结合的方法。
- 信息素的更新采用了全局更新和局部更新相结合的方案
- 局部更新就是所有蚂蚁完成一次移动，后执行一个公式
- 全局更新是，在所有的蚂蚁完成了旅行商回路后执行，全局更新仅仅对目前的最优回路上的路径进行信息素的添加。