【离散优化】大邻域搜索

大邻域搜索

回顾邻域

一个在最速下降局部搜索里的关键步骤是：

• 找到当前状态的最好相邻点
• 我们要求每个访问点都需要满足所有约束

大邻域

• 通常我们有小邻域，且我们探索邻域里的每一个点，利用：
  • 穷举搜索
• 我们也可以有大邻域和通过以下方法探索：
  • 约束编程，或
  • 混合整数规划

大邻域搜索（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"];
  

原文：https://www.cnblogs.com/xxxxxxxxx/p/13139094.html