局部搜索应用：百万皇后问题
皇后问题
皇后问题：
在一个 \(n\times n\) 的棋盘上，每行每列有且只有一个皇后棋子，每对角线至多一个皇后棋子。
如果使用回溯法，计算10皇后、20皇后问题还是可行的。
但是当皇后数增加到一百万个时，又该如何求解呢？
局部搜索算法用于求解组合优化问题，而皇后问题是组合问题，和优化没有关系，我们可以先将皇后问题转化为最优化问题。
-
指标函数：棋盘上皇后的冲突数。
-
表示：
\(S=\{S_i\}\)表示一个可能解，其中 \(S_i\) 表示在第 \(i\) 行，第 \(S_i\) 列有一个皇后。
如四皇后问题的一个解：\(S=(2,4,1,3)\)
皇后搜索算法
- 随机地将 \(n\) 个皇后分布在棋盘上，使得棋盘的每行、每列只有一个皇后；
- 计算皇后间的冲突数 \(c\) ；
- 如果冲突数 \(c\) 等于0，则转 (7)
- 任选两个皇后交换他们在序列中的位置；
- 如果交换后的冲突数 \(c\) 减少，则接受这次交换，更新冲突数 \(c\) ，转(3)；
- 如果陷入了局部极小，即交换了所有的皇后后，冲突数仍然不能下降，则转1；
- 输出结果；
- 结束。
可以使用局部搜索算法解决大规模皇后问题（并找到全局最优解）的关键在于：我们知道冲突数这个指标有最小值，并且最小值为0，从而我们可以判断某一时刻是否陷入了局部极小，或者是否已到达最优解。
而对于另一个著名的组合问题，旅行商问题来说，我们也可以用局部搜索算法来求解，但是我们不知道指标（路径长度）的最小值是多少，因此我们只能求得局部最优解，无法判断求得的局部最优解是否全局最优。
大多数组合问题都和旅行商问题一样，使用局部搜索算法往往是无法判断全局最优的。
局部搜索算法存在的问题
局部最优问题
最明显的问题是可能会得到局部最优解，如上图的 \(B\) 和 \(C\)，而得不到 \(A\)。而这些最终结果与初始点有关，因此需要多次随机地设置初始点，然后在得到的多个解中，找出相对较优的解。
解决思路
-
按概率接受解（在领域中寻找解的时候，并不是只接受最优解，而是为每个解计算概率，然后随机走下一步）
-
从邻域中随机选择一个解，如果该解的指标函数好于当前已知的最好解，则以大概率接受该解，否则就以小概率接受该解。
求最大值时
概率的计算方法根据不同算法有不同实现，这里只是一个简单的例子。
即 指标 除以 邻域内所有指标之和。
同理，求最小值时：
如何按概率接受一个解？
- 设 \(x_i\) 的接受概率为 \(P(x_i)\)，当 \(random(0,1)<P(x_i)\) 时接受 \(x_i\)
步长问题
如果步长大，而“山峰”尖，则可能最终像上图中一样，结果落在了半山腰。
解决思路
改变步长
- 如果步长太小，会导致计算效率降低。
- 如果步长太大，可能导致错过最优解。
一种解决方法是，随着迭代次数的增加，逐渐减小步长。
不同的算法有不同的改变步长的做法。
大多数情况下还是需要多次调整初始步长，然后执行程序，多次调整。
起始点问题
起始点不同，最终的结果可能不同。可能得到全局最大值，也可能得到局部最大值。
解决思路
随机产生多个起始点，从多次运行结果中选择一个最好的结果。
综合求解
面对局部搜索算法存在的问题，应综合求解。
- 按概率接受解；
- 改变步长；
- 多次运行方法。
有一种特殊的局部搜索算法叫模拟退火算法，就是基于“按概率接受解”和“改变步长”这两点的。