如何用随机方法求解组合优化问题（三）

手机

无惧汗水，尽情热爱！甄稀冰淇淋联手十足便利店助力杭州亚运征途

激战2新DLC即将上线，海外如何玩激战2国服？

家电

如何用随机方法求解组合优化问题（三）

2023-08-14 19:02:13 来源：博客园

局部搜索应用：百万皇后问题

皇后问题

皇后问题：
在一个 \(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\)。而这些最终结果与初始点有关，因此需要多次随机地设置初始点，然后在得到的多个解中，找出相对较优的解。

解决思路

按概率接受解（在领域中寻找解的时候，并不是只接受最优解，而是为每个解计算概率，然后随机走下一步）
从邻域中随机选择一个解，如果该解的指标函数好于当前已知的最好解，则以大概率接受该解，否则就以小概率接受该解。

求最大值时

概率的计算方法根据不同算法有不同实现，这里只是一个简单的例子。

\[P_{max}(x_i)=\frac{f(x_i)}{\sum\limits_{x_j\in N(x_b)}f(x_j)}\]

即指标除以邻域内所有指标之和。

同理，求最小值时：

\[P_{min}(x_i)=1-P_{max}(x_i)\]

如何按概率接受一个解？

设 \(x_i\) 的接受概率为 \(P(x_i)\)，当 \(random(0,1)

步长问题

如果步长大，而“山峰”尖，则可能最终像上图中一样，结果落在了半山腰。

解决思路

改变步长

如果步长太小，会导致计算效率降低。
如果步长太大，可能导致错过最优解。

一种解决方法是，随着迭代次数的增加，逐渐减小步长。

不同的算法有不同的改变步长的做法。

大多数情况下还是需要多次调整初始步长，然后执行程序，多次调整。

起始点问题

起始点不同，最终的结果可能不同。可能得到全局最大值，也可能得到局部最大值。

解决思路

随机产生多个起始点，从多次运行结果中选择一个最好的结果。

综合求解

面对局部搜索算法存在的问题，应综合求解。

按概率接受解；
改变步长；
多次运行方法。

有一种特殊的局部搜索算法叫模拟退火算法，就是基于“按概率接受解”和“改变步长”这两点的。

关键词：