第三章 高级搜索

• 局部搜索方法
• 模拟退火方法
• 遗传算法
  高级搜索其实就是求组合优化问题的解，之前的运筹学（还是叫别的什么名字来的）这门课上都学过，也是美赛的必备技能之一。
  优化问题的一般描述：
  在x的定义域D上，求f满足条件g的极值max f 或min f
  （简书什么时候能支持公式啊\怨念）

---

局部搜索

基本思想：始终向着离目标最近的方向搜索。
（这里不做特殊说明，则默认是求最小值）
步骤：

1. 随机选择一个解x_0，生成邻域P。
   邻域的生成方法有很多种，比如旅行商问题中，选择两个点交换，将所有可能的交换结果列出来，得到的就是原始解的邻域。
2. 如果P为空，则结束计算。否则，从P中任选一个元素x_n。
3. 如果f(x_n)<f(x_0)，则把这个解作为新解，更新邻域P。
4. 否则，P=P-{x_n}。
5. 转到2
   以上步骤的一个明显问题：容易陷入局部最优。只要找到一个极值点，就会停止计算。有三种改进的思路：

• 改进1：按照f的值随机选点。
  • 课件上模拟退火在用这个随机的时候，方法是按照Metropolis准则来转换状态。在P中随机选一个解，f减小则选中，f增大则按照玻尔兹曼分布选中。
• 改进2：每次选点之后都改变一下步长。
• 改进3：散布不同的初值点进行搜索，在最终结果中找出最优的。
  Remark：本章之后的算法都是上述改进的组合。上述改进1和改进2结合，就形成了模拟退火算法。

---

模拟退火

在上述改进1的基础上，按照Metropolis准则进行状态转化：
当从状态i转为状态j时，如果E(j)<=E(i)，则接受转化状态；否则，以Boltzman分布接受，即以概率:
$e^{\frac{E(i)-E(j)}{KT}}$
接受。
其中E是待优化的函数，T是温度，K是玻尔兹曼常数。
之后的重点基本上就是算法的实现。有以下几个点：

• 初始温度的选取；
• 温度的衰减函数；
• 算法的终止准则；
• 每个温度下的马尔科夫链长度（也就是要算多少次）；

起始温度的选择

初始温度要尽量大，使得$e^{\frac{E(i)-E(j)}{KT}}\approx 1$
可以直接给定，也可以用升温的办法求取。先给定一个小的温度，然后产生一个邻域，算一下被接受的概率。如果符合设想的值（比如0.98），那么就接受；否则就升温。

温度下降

可以采用等比例下降、等值下降或者平衡分布的方法。

每一温度下的马尔科夫链长度

• 固定长度
• 被接受的状态数到达一定值
• 接受率到达一定值
• 两代之间的指标函数差值小于一定值

算法的终止

• 当温度小于一定值（零度法）
• 当温度下降的次数达到一定值（循环总控制法）
• 当温度下降后，指标函数没有变化（无变化控制法）
• 除了当前最优之外，其他状态的接受概率都很小
• 相对误差估计法

---

遗传算法

遗传算法就是根据进化论推出来的一个算法——其实这样说有种戴个很大的帽子的感觉……遗传算法就是前面提到的随机搜索算法的改进1和改进3的组合。每一代通过选择、交叉、变异这三个步骤，生成子代。最后选择整个进化过程中最优的后代。
选择过程对应着改进1，用很多随机初始点进行模拟对应着改进3。对前面的部分理解了之后这一部分就没什么难的了。
比较困难的部分是编码。不过这一部分属于工程处理问题，大概不会考，期末复习笔记就不写了。