【离散优化】大邻域搜索

大邻域搜索

回顾邻域

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

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

大邻域

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

大邻域搜索(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"];
    
上一篇:论文阅读笔记(一)——squeezenet


下一篇:unity|火焰和烟效果(粒子系统)