跳到主要内容

局部搜索

阐述​

局部搜索是指在问题的空间中从一个完整的解出发，通过逐次改变解的一小部分来完成搜索。允许改变的解的部分称为「邻域」，有很多种定义邻域的办法。

局部搜索可以用来解决 3 种不同的问题：

可满足性问题​

这实际上是把可满足性问题转化为优化问题来解决的，定义一个目标函数来衡量违反约束的程度，然后尽可能减少这种违反的程度。

「违反的程度」可以是个数，也可以是某种加权平均。

最大最小冲突原则：选择在最多个违反中出现的变量，然后把它改变为一个让违反数最小的变量。

优化问题​

最简单，直接优化即可

带有约束的优化问题​

3 种策略：

  1. 转化为一系列可满足性问题，逐渐减小目标值
  2. 保证约束被满足的情况下进行局部搜索
  3. 允许约束被违反，同时优化约束和目标函数

第二种方法有的时候可能会非常难从一个可行解移动到另一个可行解，需要精心设计邻域。

第三种方法的难点在于局部最小值不一定满足约束，但是也可以通过设计目标函数来解决这个问题。

基本理论​

用 ss 表示问题的解，定义

  • 邻域：N(s)N(s) 是在一步搜索中能达到的解的集合
  • 有效邻域：L(N,s)L(N,s)
  • 选择函数：S(L,s)S(L,s) 从有效邻域中选择一个新的解，也被称为
  • 启发：一种选择下一个解的方法，通常找到局部最优解
  • 元启发：一种跳出局部最优解的方法，目标是找到全局最优解

常见的方法：

  • LL: 有改进、无退步、或者允许退步

启发​

  • 选择最好的邻居
  • 第一个邻居
  • 多步选择
    • Max-min conflict 选择冲突最多的变量，然后改为冲突最少的值
    • Min-conflict 随机选择变量，然后改为冲突最少的值
  • 随机行走
  • 二阶邻域：考虑所有的变化
  • Metropolis 启发

元启发​

实例​

可满足性问题​

八皇后问题，每次考虑一个列的皇后，用最大最小冲突原则选择一个更好的位置

车辆排序问题，每次交换两个车，保证需求一直满足

幻方问题，每次交换两个数字，用 ∣s−t∣|s-t| 来作为违反的度量

纯优化问题​

仓库位置问题，每次改变一个仓库的开关，或者交换两个仓库

带有约束的优化问题​

旅行商问题，每次交换几条边

  • 2-OPT：每次 2 条
  • 3-OPT：每次 3 条（效果好）
  • K-OPT：连续进行 2-OPT 的序列，然后找出一个最小的子序列

图染色问题：

第二种策略，可以用 Kemp Chain 来作为邻域（交换两种颜色之间互相连接的节点）

第三种策略，合适的目标函数是

∑i2∣Bi∣∣Ci∣−∑i∣Ci∣2\sum_i2|B_i||C_i|-\sum_i|C_i|^2

旅行锦标赛问题，合适的邻域是

  • 交换主客场
  • 交换轮数
  • 交换团队
  • 部分交换轮数
  • 部分交换团队

性质​

局部最小值​

局部搜索得到的解总是一个局部最小值，它可能好也可能坏：

∀n∈N(c):f(n)≥f(c)\forall n\in N(c):f(n)\ge f(c)

需要采用一定的技巧来避免陷入局部最小值

连通性​

称邻域函数 NN 是连通的，如果对任何一个组态 SS 都存在一个最优解 OO 和一条路径

S=S0→S1→S2→⋯→Sn=OS=S_0\to S_1\to S_2\to\cdots\to S_n=O

其中 Si∈N(Si−1)S_i\in N(S_{i-1}). 例如，旅行商问题的 2-OPT 邻域是连通的。

相关内容​

相比之下，约束规划总是从一个不完整的解出发，逐步扩展得到完整的解。

参考文献​