大邻域搜索
回顾邻域
一个在最速下降局部搜索里的关键步骤是：
- 找到当前状态的最好相邻点
- 我们要求每个访问点都需要满足所有约束
大邻域
- 通常我们有小邻域，且我们探索邻域里的每一个点，利用：
- 穷举搜索
- 我们也可以有大邻域和通过以下方法探索：
- 约束编程，或
- 混合整数规划
大邻域搜索（LNS）
我们如何指定一个大邻域？通常：
- 给定一个现有的状态 \(d\)
- 其中 k% 的变量 \(x_i\) 固定在它们的现有值 \(d_i\)
- 对剩余的未固定的变量求解
- 就好像对原始问题的一个简化版求解
也可以用其他方法：
- 将邻域定义为变量值最多有 \(k\) 个变化的状态
- 除了特定的相关变量外，固定其他变量
- 与问题相关的邻域定义
优势：
- 可以“看见”和探索得更远
- 更不容易困在局部最小值
- 可以处理任意约束（只要你的求解器可以处理它们）
考虑：
- 如果邻域太大呢？
- 如果领域太小呢？
- 那些使用大邻域后依然陷入的局部最小值？
- 我们怎么得到一个初始的可行解？
基本的最小化问题的大邻域搜索算法框架：
large_neighbourhood_search(f, D)
d := initial_validation(D)
while(not stoppingcondition())
N := define_neighbourthood(d, D)
e := explore_neighbourhood(N)
if (f(e) < f(d))
d := e
return d
注：通常限制邻域的搜索
-
initial_validation(D)
- 为了得到初始解，我们可以忽略目标值，即解决原问题的约束满足版本
- 对调度问题而言是简单的
- 贪心算法
- 得到的时间表可能很差，但我们后续会进行改进
-
define_neighbourthood(d, D)
- 定义当前解（点）\(d\) 附近的一个邻域 \(N\) 进而搜索
- 对相同的 \(d\) ，在不同的迭代使用中可以有不同的结果
- 通常通过松弛一组变量来指定这样的领域
-
explore_neighbourhood(N)
- 搜索邻域以找到另一个解 \(e\) （默认情况下即邻域里最好的）
- 搜索的方式可能会改变
- 在大邻域搜索，我们通常使用约束编程或者混合整数规划来完成
就像其它的局部搜索算法，大邻域搜索不能证明最优。在实践中，我们运行大邻域搜索直到资源耗尽并返回当前答案。
定义邻域
根据具体问题而定：如果我们理解了问题之后我们可能会选择松弛
- 与问题的某一部分相关的所有变量
- 可能是使目标值特别差的一组变量
以车辆寻路问题为例，它有以下要点：
- 每个任务有特定位置和时间段
- 我们把任务分配给卡车
可能的邻域定义：
- 取消 / 松弛某一卡车的所有现有任务分配
- 允许一个卡车优化自己的时间表
- 取消 / 松弛在某一时间段内的所有现有任务分配
- 允许卡车之间交换任务
- 取消 / 松弛在某一区域的所有现有任务分配
- 允许卡车之间交换任务
我们也可以使用自适应选择的邻域：
- 集中在一些已经成功的方法上
一般化的随机邻域定义
随机邻域定义
- 对每一个变量
- 有 \(k\%\) 的概率将它固定在当前的值
- 对所有松弛的变量求解
关于 \(k\) ：
- 如果 \(k\) 的选择比较合适的话，效果会好得令人惊奇
- 太大：邻域的*度有限，搜索中不能发现改善之处
- 太小：太大的邻域以至于搜索使用时间过长，基于等同于求解原来的问题
自适应的随机邻域定义
从 \(k\%\) 的固定率开始，对于任意邻域最多允许搜索 \(S\) 步
重复以下步骤
- 利用 \(k\) 生成随机的邻域 \(N\)
- 在 \(S\) 步之内求解大邻域搜索问题
- 如果求解在 \(n\) 步之内完成，而且 \(n<<S\)
- 令 \(k\) 更小（固定更少的变量）
- 如果求解在 \(S\) 步之内未能完成
- 令 \(k\) 更大（固定更多的变量）
自适应邻域定义具有鲁棒性，而且很难很难被击败！
大邻域搜索的变种——贪心的大邻域搜索
-
在大邻域中搜索
-
第一个得到改善的解，或者
-
直到资源耗尽
-
-
前往第一个解
-
继续大邻域搜索的循环
小结
- 一种强大的局部搜索方法
- 基于完备的搜索方法
- 可以处理任意约束
- 即使有时我们想把某些约束转化为惩罚
- 使用完备搜索方法可以拓展应用到更大的问题
- 随机邻域是鲁棒的
- 并不是说大邻域搜索就是最好的，对于一些特殊应用，专门为其设计的局部搜索策略有可能会好于大邻域搜索
灭火问题
- 给定
- 43 个悟空
- 100 个着火点，每个着火点要求不同数量的悟空和持续时间来扑灭
- 约束
- 在任何时间，需要的悟空不能超过可用的数量
- 在任何两个相邻的火点中，较低高度的火应该在较高的火点之前扑灭
- 目标
- 每个火点都在一天中的某个时间变得最弱，这也是对付它的最好时间
- 最小火灭火时间和最好时机的误差之和
灭火问题模型
-
数据
int: w; % 悟空数量 int: n; % 火点数量 set of int: FIRE = 1..n; array[FIRE] of int: d; % 持续时间 array[FIRE] of int: reqW; % 需要的悟空数量 array[FIRE] of int: best; % 最好时机 int: m; % 优先次序对的数量 set of int: PREC = 1..m; array[PREC] of FIRE: pre; % 先扑灭这个 array[PREC] of FIRE: post; % 再扑灭这个 int: maxt = sum(f in FIRE))(d[f]); % 最大时间点 -
决策变量
array[FIRE] of var 0..maxt: s; % 灭火开始时间 array[FIRE] of var 0..maxt: e = [s[f] + d[f] | f in FIRE]; % 结束时间 -
约束
constraint forall(i in PREC) (e[pre[i]] <= s[post[i]]); include "cumulative.mzn"; constraint cumulative(s, d, reqW, w); -
目标
var int: obj = sum(f in FIRE)(abs(s[f] - best[f])); solve minimize obj; output["Start = \(s)\n" ++ "End = \(e)\n" ++ "Obj = \(obj)\n"];