如何用随机方法求解组合优化问题（二）
局部搜索算法
组合问题由于其可能的解的数量十分庞大，无法用穷举法求解最优解。
局部搜索算法旨在减少复杂度的情况下寻找最优解，尽管其不一定能够找到全局最优解，但是往往可以找到满意的局部最优解。
爬山法
类似于盲人爬山，无法看到全局的景象，但是有拐杖可以探测临近的区域。
每一次使用拐杖在周围扫一圈，把这一圈上每一个点的高度与自己脚底的高度比较，找到距离脚底最高的那个点所在的方向前进。
重复以上过程。直到扫描周围的一圈，发现都低于自己脚底的高度。
此时位于局部最高点。
核心思想
邻域内找一个最优的结果，接受它，再以此为新的起点，重复这个过程。
领域的概念
上文中对于领域的现实类比案例是容易理解的， 但是在组合优化问题中，领域是指什么呢？
对解 \(S\) 经过一些简单变换后，得到的另一个解称作解 \(S\) 的邻居，解 \(S\) 所有邻居的集合称作解 \(S\) 的邻域。
邻域举例
-
皇后问题：每行每列有且只有一个皇后，每对角线至多一个皇后。
\(S=\{S_i\}\) 表示一个可能解，其中 \(S_i\) 表示在第 \(i\) 行，第 \(S_i\) 列有一个皇后。
如四皇后问题的一个解： \(S=(2, 4, 1, 3)\)
任意交换两个皇后的位置获得一个解的邻居，则\((2,4,1,3)\)的所有邻居，也就是邻域为：
\(\{(4,2,1,3),(1,4,2,3),(3,4,1,2),(2,1,4,3),(2,3,1,4),(2,4,3,1)\}\)
-
旅行商问题
-
常规交换法
序列 \(S\) 是对于 \(n\) 个城市的访问顺序，将其中两个城市的访问顺序进行调换，则得到一个邻居 \(S'\).
常规交换法的路线改变示例图：
-
逆序交换法
选取两个城市 \(x_i\) 和 \(x_j\) ，将这两个城市之间的序列进行逆序操作。( \(x_i\) 和 \(x_j\) 是不变的 )
逆序交换法的路线改变示例图：
-
局部搜索算法描述
- 随机的选择一个初始的可能解 \(x_0\in D\) ，\(x_b=x_0\) ，\(P=N(x_b)\) ；
- 如果 \(P\) 不为空，则
- Begin
- 选择 \(P\) 的一个子集 \(P'\) ，\(x_n\) 为 \(P'\) 中的最优解
- 如果 \(f(x_n)<f(x_b)\)，则 \(x_b = x_n\)，\(P=N(x_b)\)，转2；
- 否则 \(P=P-P'\)，转2.
- End
- 输出计算结果
- 结束
其中：
-
\(N(x)\)函数用于获取组合 \(x\) 的邻域。
-
这里的算法比上文的爬山法更具一般性，没有直接在领域中寻找局部最优解，而是在邻域的子集中寻找最优解。
-
\(f(x)\)用于计算并比较组合 \(x\) 的优良性，从而最终可以选出局部最优解。在旅行商问题中可以是路径的长度，在0-1背包中可以是背包中物品的价格。