优化是决策的一般形式，在我们的社会中很常见。它的应用包括从求解数独谜题到婚礼上的座次安排。同样的技术可以调度航班和机组成员，协调钢铁生产，组织铁矿从矿井到港口的运输。人力资源和材料管理上好的决策可以令企业提升上百万的盈利。同样的问题很多也在我们日常生活出现，成为决定每天送货路线，决定学校时间表，传输电力到家里等种种问题的一部分。除了它们的重要性，这些问题如果用传统的本科计算机科学方法难以求解。 这门课程为已经完成离散优化高阶篇的同学设计。 请看这门课程的宣传视频：http://www.cpr.cuhk.edu.hk/cutv/detail/988
3.4.7 大邻域搜索
Loading...
Do curso por The Chinese University of Hong Kong
离散优化算法篇 Solving Algorithms for Discrete Optimization
classificação
The Chinese University of Hong Kong
classificação
Na lição
局部搜索
这个模块带你进入局部搜索的神奇领域，它可以高效地探索一些大而复杂的搜索空间。你将会学到状态，移动和邻域的概念，还有它们在受约束的搜索空间中如何被应用在基本贪心搜索和最速梯度下降搜索中。你还将学习不同的方法来逃离或者避免局部最小值，包括重启，模拟退火，禁忌表和离散拉格朗日乘数法。最后，你将会看到大邻域搜索把在邻域中找到最优相邻点看作一个离散优化问题来解决，并因此使我们探索更远和更有效地搜索。
Conheça os instrutores
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
[音乐] [音乐]
[音乐]
[音乐] [音乐]
[音乐]
[音乐]
[音乐] [音乐]
[音乐]
[音乐] [音乐]
[音乐]
悟空终于拿到他的芭蕉扇，所以呢他就去到这个火焰山。
我们也 可以看看这个就是火焰山的地形，利用这个等高线来表示出来，除了
这个中间这个地方，很大火的地方之外呢，我们其实也看见呢上面这个火焰山
的整个山里面都有不同的着火点，这些着火点呢是在不同的高度，
也是呢沿着不同的山坡往上走的，一共有一百个着火点，
所以呢悟空就知道了他一个人呢没有可能可以处理那么多的着火点的，所以呢他就利用他的
分身术变了很多的悟空出来，这就可以帮他的忙了，但是呢
他经过绵长的大战，跟这个铁扇公主，跟这个牛魔王来大战之后呢
他也有一点累，所以当天他加上他自己之外 之内呢总共只有变了43个悟空出来。
好啦，我们有100个着火点，但是呢不同的着火点呢它们的
火烧的程度是不一样的，所以呢它们对灭火的要求也不一样。
第一，每一个着火点呢当然要求这个不同的数量的悟空。
当然呢也有一个不同的 持续的时间才可以把这个火这个泼灭，所以呢我们看到19号这个着火点呢
需要9个悟空，然后是12分钟呢才可以泼灭，46呢这个
需要这个悟空呢比较少一点，而且呢也比较短的时间呢已经可以把它泼灭了。
除了没有着火点它的要求之外呢 其实我们要把火泼灭了我们也可以利用一点点的
物理的知识呢可以帮助我们呢把火泼灭得更好的。
我们知道呢 我们的着火点呢都是，很多都是沿着同一个山坡的，其实我们知道呢火都是往上跑的
所以呢，如果我们在同一个山坡的话呢，我们应该呢先把下面的火呢
泼灭，然后呢才去处理这个在中间的火呢。
不然的话呢，我们先去处理这个火呢，
把它泼灭之后，其实下面的火呢有可能把这个重新点起来的，所以呢我们先
要泼灭这个这个比较低的，然后到中间，然后呢 处理中间之后我们才处理呢这个最高的，
好啦，我们都知道呢，这个诸葛亮呢他是非常
厉害的，他是懂得这个夜观天象，所以呢他知道这个在不同的地方这个着火点呢
其实不是要一整天都是烧得那么厉害的，其实他发觉呢，每一个着火点呢
每天都有一段的时间呢就是比较弱一点，而且呢
有一个最弱的一个时间，这个就是我们开始去泼灭这个火的
最好的一个时机，但是呢，当然我们要明白就是因为着火点在不同的地方，所以
呢我们每一个着火点呢都有不同的这个最好的时机开始泼灭它的。
好啦，我们现在呢要看看这个我们的灭火这个问题，我们在这个问题里面呢，我们总共有43个
悟空，包括他本来他自己，然后呢有100个着火点，
每一个着火点呢，它们对悟空的数量的要求跟这个持续
时间来灭火的时间呢都有不同的要求，在这个问题里面呢，我们有两个约束，第
一个约束很简单，我们只有43个悟空，就是在任何的时间呢，我们要调用的悟空的数量不- 可以超过
我们所有的悟空，而且呢在两个相邻的着火点呢我们应该呢
先处理高度比较低的这个着火点，然后呢才处理
高的这个着火点，刚才已经解释过是因为一个很简单的物理的作用。
至于我们的目标呢就是跟刚才提过呢就是每一个着火点呢，其实在一天的时间当中呢有某一个
时间呢，它们是变得最弱的，这个就是我们的最好的时间 呢去开始去处理这个着火点。
所以呢我们就可以把我们调度的时间跟每一个火最好的一个时间呢
它的误差计算出来，而且呢把所有的误差 呢加起来然后呢我们需要把这个误差呢
之和最小化，这个就是我们的目标函数，因为这样子呢
悟空才可以利用最小的力量呢就可以把所有的火呢 都泼灭的。
这里呢我们也可以看看我们MiniZinc这个模型，就是我们灭火这个问题
首先我们可以看看我们的数据，w呢就是悟空的 数量，然后n呢就是我们着火点的数量，
然后呢我们也有三个数组，这三个数组就是代表每一个着火点呢它的起始时间，需要的时间
去泼灭它，而且呢每一个着火点呢我们需要多少个悟空来处理它。
然后每一个着火点呢我们也有一个刚才提过的最好的一个时机，开始去泼灭它呢 就是最好了。
然后呢我们也利用一个我们之前用过很多它的一个标准的方法来表达，
很多优先去处理不同的任务的一个方法，就是我们有m个
优先次序的一个对的数量，然后呢我们就利用两个数组，pre呢就是我们现在处理的
这个任务，post就是我们要后处理这个任务。
下面呢我们也可以去计算一个所谓是最大的时间， 最大的时间是什么呢？就是我们假设悟空不可以并行去处理所有的着火点的
就是一个一个它来处理的，我们
最多要调用多少时间呢？因为这个maxt这个最大的时间点呢就可以帮助我们去
定义我们的决策的变量，就是我们有两个数组，就是代表我们的决策的变量。
就是呢，每一个着火点，我们什么时候开始去处理这个着火点呢，
它的范围呢就是0到刚才计算出这个maxt来的。
然后其实每一个着火点我们有了它的
开始的时间呢，因为我们也知道它持续的需要的时间，所以呢我们其实也可以计算出它结束的
时间的，有了我们决策的变量之后呢我们当然要定义
问题里面约束，刚才也提到过我们有两种不同的约束。
第一种的约束呢就是我们要求呢就是在这个有优先次序的处理，就是我们先要
比较低的着火点才可以处理比较高的着火点，这个呢就是说我们要先
完成e，就是完成pre这个着火点的处理，才可以要先
于开始去处理这个post这个着火点的，然后另外一个约束呢就是说我们同一个时间
不可以调用多余我们有的悟空的数量，原来呢我们利用一个全局约束
cumulative就很简单的把这个表达出来了，s就是我们的变量就是我们开始处理
每一个着火点的时间，第一个跟这个reqk，r，e，q，w呢，就是我们每一个着火点需- 要的持续
去处理的时间，需要悟空的数量，然后这个w呢我们就是不可以超过的就是悟空 总共的数量了。
看看我们的目标函数，我们的目标函数呢就是看看，每一个
着火点我们计算，它我们调度，计算出来的这个 开始的时间跟每一个火它的所谓是最好的时机
把它们的误差计算出来，所以我们是用这个绝对值，然后呢把这个误差呢
我们就加起来，然后加起来呢这个就是我们的目标函数值啦，然后我们需要把这个目标函数值呢
最小化，这个就是我们灭火问题这个模型。
我们在下面这样会利用一个比较
小型的数据呢来演示我们怎么利用我们将会介绍
新的算法来解决这个问题，我们本来这个问题是100个着火点的，在这个小的
数据里面呢我们只有10个着火点，而且呢我们只有8个 悟空，所以我们看见这个是8，这个是10，然后每一个着火点呢我们有
三个数组来代表它们持续的时间，需要悟空的数量，而且呢每一个着火点呢，它是最好
最佳的时间是什么时候去开始处理它们？然后我们也有一个6
对的数组呢，就是来代表呢就是我们 先要处理比较低的着火点才可以处理高一点的着火点。
好啦，我们要介绍一个新的算法 来处理这个问题，但是呢介绍这个新的方法之前，我们要
回顾一下我们之前讲这个局部搜索里面一个非常重要的概念，就是邻域这个概念。
在一个最速下降的局部搜索这个算法里面呢我们最关键的一个步骤呢就是
我们在到了当前一点，我们呢就要看看这一点呢它的邻域是什么？然后呢我们就要检查
它所有相邻的点，然后从这所有相邻的点呢，我们找到当前我们这个点
最好的一个相邻点，而且呢因为我们现在问题里面有约束了，
我们也需要呢我们到的访问的每一个点呢都需要把我们问题里面所有的 约束呢都要满足的。
我们在看清楚其实我们要解决的就是找
最好的相邻的点而且要满足所有的约束呢，本身就是一个受约束的 离散优化的问题。
其实我们有没有其他的我们学过的方法可以帮助
我们去解决刚才提到这个关键的一个步骤呢？其实呢，答案是对的 是是的。
我们呢，如果大家还记得呢，我们刚开始介绍
局部搜索的时候呢我们已经在演示当中呢，比较过 就是小的邻域跟大的邻域呢它们的分别是什么？
最大的分别就是我们如果是利用大的邻域的话，可以帮助我们提高
我们搜索这个效率的，但是呢如果我们要处理大的邻域的话，我们因为有太多
的相邻的点要检查，而且要找出最好的一个相邻的点，所以呢我们用的资源呢要更多。
所以通常呢我们都是处理一个比较小的一个邻域的，我们通常也是利用一个
穷举的一个搜索的方法，就是把这个邻域里面每一个相邻 的点都检查它，看看它们的目标函数值是什么是多少？
然后呢我们就找出一个最好的相邻的点出来的。
但是如果我们要处理的是一个大邻域的话， 我们刚才已经讲过了，太多的相邻的点，那我们就要
利用太多的资源去找出这个最好的这个相邻的点。
所以其实呢，我们现在就是提出我们其实不需要 利用这个穷举这个搜索的，我们其实可以利用我们之前学过的
约束编程的方法或者是混合整数规划这个方法呢这些的技术呢，也是其实可以帮助我们
在一个大邻域里面找出一个最好的相邻的点的，那这个就是
我们将会要给大家介绍的一个大邻域搜索 这个方法，我们也叫它叫LNS。
现在问题就是我们怎么可以定义一个大邻域呢，我们当前
来到我们搜索的其中一个点呢，怎么去定义一个大的邻域呢，其实有一个
通常的方法呢就是什么呢？我们看看现在目前的状态，目前的一个点，我们呢可以把这个点，
其实这个点是个赋值，我们呢可以决定把这个赋值里面k%那么多的变量
它们固定它们现有的值di里面，其他的变量呢我们其实就可以
把它们现在的赋值呢，把它松弛，就是说呢，把它的赋值呢
解除，就没有这个赋值了，然后呢我们就可以基于搜索其他的变量呢，我们就可以
把我们相邻最好的一点呢可以找出来了，那当然呢这个我们刚才介绍呢其实只是其中一个
方法可以定义一个大邻域，其实也有其他的方法的，譬如说我们可以把
当前这个点我们可以改变k个变化的状态，
就是把目前的状态我们允许我们改变k个变量的，我们也可以，如果k
是够大的话，这个也是个大邻域来的，那当然呢，其实呢不同的问题其实我们也可以
设计不同生成不同的相关的大邻域的定义，有可能我们可以把问题里面
相关的变量之外其他的变量呢，我们就允许我们可以把它松弛， 这个也是一个大邻域的一个可行的一个定义。
好了，为什么我们要利用这个大邻域这个搜索呢，其实之前也看见过
就是如果我们的领域是够大的话，我就允许我们的搜索 可以看到远一点，而且呢探索得更远，
而且呢因为我们相邻的点够多了，所以呢我们就不再容易被困在一个局部的最小点。
因为呢我们可以检视更多的其他的点，有机会呢
多一点机会就是它们的目标值呢比我们现在这个点这个值呢 更好，所以我们就可以去到更好的地方。
而且另外一个最好的好处就是利用这个方法呢我们基本上
可以处理呢任何的约束，那当然呢就是因为我们基本上是用我们用过的技术，
就是需要你的求解器呢是可以处理这样子的约束呢，我们都可以利用这个大邻域这个搜索来处- 理它们。
那当然呢，利用一个新的方法我们也是有东西要 考虑的，譬如说如果我们定义的
领域是太大会怎么样呢，虽然我们希望这个邻域越大越好，但是如果太大也是有问题的，如果
把这个邻域定义得太小，当然呢太小就不是大邻域
了是吗？然后虽然我们用了这个大邻域，虽然我们刚才说
不太容易不再更容易呢被困在局部的最小点，但是其实我们还是有机会呢
是可以困在一个局部的最小点，那我们怎么处理呢？ 而且最大的其中一个问题呢就是我们要利用这个大邻域的搜索呢，
我们就是要计算出一个初始的一个可行的解，这些
问题呢，这些考虑呢我们在下面呢都会跟大家再比较深入的去讨论的。
好啦，这个就是我们的大邻域的搜索的一个算法，这个是一个基本的算法。
我们下面呢会 提出不同的变种，我们叫这个large_
neighbourhood_search这个函数，其实看起来呢跟我们一般用起来的
这个局部搜索的这个伪代码呢都是很像的，一开始 我们利用这个initial_valuation这个函数的调用，我们就找出一个
初始的一个点，但是我刚才已经讲过了这个呢要小心一点，因为我们要保证呢这个初始的点呢- 要满足我们
问题里面的所有的约束的，然后我们进入一个循环啦，这个循环跟之前见过也是一样，
我们把这个循环不停的做，直到我们把我们所有搜索的资源用完呢我们才停止的。
然后呢第一步呢，里面就是define_neighbourhood这个函数，这个 define_neighbourhood这个函数呢就是基于我们现在目前这个点我们要
找出一个大邻域出来，然后呢我们叫这个大的邻域呢叫大N，然后呢
我们就利用explore_neighbourhood这个函数呢来帮助我们去探索这- 个大邻域
里面的所有的相邻的点，希望可以找出一个好的一个新的点，
这个新的点我们叫e，就是呢这个大邻域里面最好的一个点， 通常是最好的一点吧，然后我们就比较新的一点跟旧的一点是不是
更好，如果是更好的话我们就把目前这一点呢这个变量呢更新。
我们就一直一直这样子做这个循环，到了最后用完所有的搜索的
这个资源之后呢我们就停止，就返回我们目前在的一点呢就是我们目前找到最好的一点了。
那要提一提呢就是我们在去explore_neighbourhood，做这个expl- ore_neighbourhood
这个函数的时候呢我们通常，因为我们的邻域是比较大的，我们通常呢都是
给这个explore_neighbourhood这个函数呢一点的限制，
就是不是说一定要找到最好的一点才停止的。
下面呢我们就把刚才我们的算法里面两个比较重要的
这个调用的函数呢去解释一下，我们刚才已经讲过define_neighbourhoo- d就是帮助我们在当前的一点
去计算出一个新的邻域出来，这个邻域呢就是定义了我们所有相邻的点，希望在里面呢我们可- 以找到最好的一个
点的，但是呢有一点要提出呢就是，就算是对一个相同的点 d
哈，如果我们在我们刚才这个迭代这个循环里面在不同的迭代里面呢 有可能我们地方
neighbourhood 计算出来的这个大的邻域 呢也有可能是每一个迭代里面的计算出来也有不同的。
啊这个是非常重要的，因为有时候很可能呢就是，我们计算出一个邻域出来，里面找到的最好的
一点呢，没有把我们目前的点的这个目标值
去改善的话我们就需要重新再算一个新的 邻域出来。
然后希望在新的邻域里面我们可以找到一个更好的一点。
我们怎么定义这个 邻域呢？通常在做这个
lns 这个大邻域的搜索的话呢，通常呢就是把一个我们问题里面
某一部分的变量，它们现在的赋值呢把它松弛，就是把它们的赋值呢移除。
然后呢就在这个移除的这个松弛的变量呢在上面进行搜索，找出呢一个最 好的新的一点出来。
这个 explore neighbourhood 这个函数呢就是我们真的希望这个邻域
里面找出一个新的一点出来，默认的情况之下呢
我们就是要找这个邻域里面最好的一点的。
但是有时候如果我们资源是不够的话呢，我们是满足 不找最好的一点的，这个我们在下面再讨论。
我们做这个 explore neighbourhood
呢其实 我们就可以调用我们之前学过的不同的技术，通常就是完备的搜索的技术去，譬如说
约束编程或者是混合整数规划这些技术来搜索。
但是呢其实 我们可以调用不同的搜索的方式来去计算也可以的。
有了这个之后呢，我们就可以看看这个一个对 我们刚才提过这个小型的数据来一个演示。
但是刚才已经提过了 要进行这个大邻域的一个搜索呢，最重要的第一步就是我们可以
计算到一个初始的可行的一个解。
那我们怎么做呢，其实呢非常简单。
就是把我们原来的一个优化的问题，原来的问题是优化的。
但是 呢我们可以把里面的目标的函数呢 暂时地移除，不理它。
我们只是需要解决我们原来问题的约束的一个满足的版本。
我们现在要解决这个灭火的一个问题呢其实是一个调度的问题。
对这一类问题 其实是比较简单的。
我们要解决它原来的约束的满足的版本的问题呢，其实呢我们就可以利用这个
注解就可以调用我们的求解区呢去解决这个约束满足的版本。
出来的结果 呢通常其实呢出来结果跟我们用一个比较简单的贪心算法算出来是一模一样的。
因为呢在 现在情况之下，我们没有对我们要什么时候要完成我们所有的任务有任何的限制。
所以 呢，我们就可以为每一个着火点呢就找出一个最早
可以开始的时间，没有违反刚才提到的所有的约束呢就可以了。
但是出来的时间表呢当然 有可能是比较差劲的，但是这个没有所谓。
这个只是我们 初始的一个可行的解。
因为我们将会利用我们这个算法呢 去把这个现在的点呢一步一步改进的。
好了，假设我们已经利用一个求解器解决 了我们约束满足的一个问题了。
这个就是我们找出一个初始的 一个时间表了。
在这个图上面呢我们把每一个任务
就是要处理每一个着火点呢跟以前一样，它的长度就是 它需要的起始时间。
它的高度呢就是代表它需要物控的时间。
而且它在这个图上面呢我们也把 所有的着火点呢，它的最好的一个处理它的时间呢也标明了出来。
你们可以看见呢，我们目前这个初始的可行的 解呢其实不太好的。
其实除了这个 白色这个着火点呢，它是可以在它最好的时间开始去处理它，其它所有的
着火点呢我们处理它的时间呢都是不是不可以在最好的时间。
只是呢，譬如说 黑色这个着火点呢比较近它的最好的时间，但是这个的着火点呢距离它的
最好的时间呢比较远一点。
而且呢我们可以看见呢初始的时间 它的目标值是 42，不太好的。
所以呢，我们下一步就是什么呢 定义我们的大邻域了。
我们的方法呢就是什么呢，我们随机把我们十个变量里面的 百分之六十的变量把它固定。
你们可以看到呢就是我们随机 决定要固定的着火点的开始的时间。
没有固定，松弛的变量呢，我们把它们的颜色 淡化一点，你们就知道了。
然后呢我们可以在这个松弛的变量
上面呢去搜索，把它们重新再调度，看看出来的结果呢我们发现我们 可以找到一个新的一个解。
这个新的解呢它的目标值呢是 40，是 一个刚好的一个时间表。
那当然呢我们就要去到这个新的点了。
到了新的点之后，我们要重新再定义一个新的大邻域。
跟刚才一样，我们要随机固定 其中的百分之六十的变量，就是六个变量。
这一趟呢我们就是固定 不同的变量了。
其他的变量呢松弛的变量我们就把它的颜色淡化一点。
然后我们再去把最好的一个相邻的点找出来。
而我们发现这一趟呢我们找到一个目标值 为 30 的一个点。
啊比我们刚才这个目标值的好了很多，当然呢我们就要去到这个新的点。
然后呢我们也再次把上面的随机地把百分之六十的
变量呢固定，其他呢我们就松弛，再这个这个 找最好的一个相邻的点。
这一趟呢我们发现呢新的点呢 出来的目标值呢也是跟之前一样也是 30，就是没有改进。
所以呢我们 不应该去这个新的点了，我们要重新回到我们刚才的点，然后呢再选择
另外的不同的随机的百分之六十的变量呢把它固定，其他的松弛。
再找最 好的一个点，然后发现呢最新一个点呢就是 28 比我们刚才的更好。
所以呢我们当然就可以去新的点了。
然后呢我们发觉呢，其实呢我们到了这个新的点呢，我们就来到我们问题里面一个局部的最 小点。
那什么叫局部的最小点呢？在我们这个大邻域搜索当中，其实所谓局部的最小点呢就是
基于不同的大邻域的定义，我们呢这个点呢也是局部最小点呢这个才
称之为局部的最小点的。
其实这个是局部的最小点 也是因为它是我们问题里面的全局的最小点。
那当然呢我们当时来到这个点的时候是不知道的。
因为呢，我们这个大邻域的搜索呢，还是一个局部搜索的方法。
其实呢我们是没有办法去保证 也没有办法呢去证明呢，我们已经找到最优 的一个解的。
在现实当中呢我们运行这个 大邻域的搜索的时候呢，我们是需要搜索到我们的所有搜索的资源都已经
耗尽的时候呢，我们才停止，然后呢返回我们当前的这个点为我们的答案。
好了，刚才呢我们就利用一个比较小的
数据来演示一下大邻域这个搜索的它的 它的进行是怎么样的。
但是有一个问题我们还没有 好好的讨论过，就是我们应该是根据什么去定义我们一个问题的
这个大邻域呢？其实呢我们可以有，根据我们具体的问题，我们可以 定不同的方案。
譬如说呢，我们可以把一个问题里面某一部分，我觉得它们这一部分的变量
是比较有关系的相关的，我们就说了我们就可以松弛这一批的
变量作为我们的大邻域。
也可以呢我们可以看看我们目前这一点
我们什么的变量呢，是给我们的目标值的贡献是特别地差劲的，我们也可以选
择呢去把这一组的变量呢去松弛。
如果我们返回我们 之前看过的悟空，猴子这个组队 的一个问题呢。
譬如说我们觉得呢，相邻的猴子，譬如说 1 到 3，或者是
2 到 5，或者是 4 到 6，因为它们是相邻，我们就觉得他们是比较有关系的。
我们就可以选择把这一批的不同的变量呢 可以松弛。
又或者我们可以看看目前的一点，看看目前 的一点，我们是这样子排列我们所有的猴子的，A
的 A 到 H ，然后呢，我们可以看看，如果 A 跟 B 相邻呢，它们合作的
值呢是4，这个是0，这个是9，然后我们发现呢，这个0跟这个2呢，是对我们的目标，目标
值的贡献是比较不好的，所以呢，我们可以 选择呢，把 B、 C、 E
跟 F， 这4头的猴子呢，它们的位置松弛，然后呢，作为我们这个问题的大邻域。
也可以的，但是要，要，要强调就是很多时候我们要定义一个好的邻域呢，我们可以要
基于是我们具体的问题里面特定的结构呢，才可以定义一个比较好的领域的。
好了，我们也可以给另外一个例子，譬如说我们有一个车辆
寻路的一个问题，在这个问题里面呢，我们就有很多不同的任务，
每一个任务呢，它有特定的位置要去处理这个任务，
而且呢，要处理这个任务呢，也需要在某一个时间段里面，这样处理的，然后
我们也需要呢，把不同的任务呢，分配给我们所有的不同的卡车。
好了 这样，这样子的一个问题，我们怎么可以为它定义不同的邻域呢，有一个可能就是说
啊，我们可以把属于一个卡车的所有的任务，
把我们，决定把它松弛，因为他们都属于同一个卡车的话，我们其实呢，就是允许我们
去这个，它做这个大邻域的时候呢，就是把这个卡车里面所有的任务，
再进行优化一趟，我们其实也可以基于什么呢，一个时间段，就是把所有，所有
属于同一个时间段里面的任务，把我们把它都 松弛，又或者呢，我们可以基于这个区域，
就是同一个地区的所有的任务呢，把它们松弛，然后呢，我们就其实可以允许呢，在
同一个时间段里面的所有卡车，或者是在同一个地区里面的卡车呢，它们互相交换它们的任务。
嗯，就是不同的方法呢，可以改善我们目前这一点的这个目标，目标值的。
除了我们要决定，用其中一个的邻域的定义呢，之外呢，其实呢，我们也可以
利用一个所谓是自适应的一个方案的，就是说呢， 我们在我们的算法里面呢，把我们刚才提过的3个
邻域的定义都调用，有可能是利用随机来决定，这一个迭代我们用这个，这个
定义，第二个迭代我们用这个定义，然后呢，利用随机的方法来 选择哪一个迭代，用哪一个定义。
然后呢， 但是在我们进行一个搜索当中呢，我们也记录下来，哪一个邻域的定义呢，它的表象是比-
较好的。
所谓，所谓是表象比较好的，就是基于这个定义的邻域里面，我们比较有
把握的，可以找出一个更好的一个点出来，然后我们把这个记录下来了，我们就可以改变
我们调用不同的邻域的定义的概率吧，然后我们就集中了。
用一些比较成功的邻域的定义上面，这个也可以的。
我们刚才呢，就是提到，就是怎么去利用我们问题里面一些
特性或者结构，怎么可以去定义一个好的大邻域。
其实呢， 领域也可以是随机的，所以呢，我们也可以定义一个随机的大邻域，
就是怎么样呢，我们其实呢，刚才我们在做，做这个演示的时候呢，我们定义的邻域呢
也是一个随机的邻域，我们刚才讲的就是要把这个问题里面一个随机的百分比，里面的
变量呢，把它固定，其实呢，另外一个讲法呢，就是对于每一个变量我们给它一个 概率叫
k，k%，这样子的概率，这样来决定这个变量是不是要固定的，或者是松弛的。
然后呢，我们就对其它松弛的变量呢，来求解，这个也是我们的随机的邻域了。
如果我们可以把这个k 定义的好的话呢，它出来的效果，出来的这个效率呢，
是可以非常的好的，但是如果我们把 这个 k 定义的太大的话，k
一太大就是我们要把 太多的变量，把它的值要固定，就是说呢，我们的邻域是比较小，所以我们的自由度就是有限，
所以呢，很多时候呢，在我们相邻，比较少的相邻的点呢，我们根本就找
不到可以，比我们现在目前一点比较好的一个点出来的。
而且呢，我们有更大的机会呢，会在一个局部的最小点， 如果我们把这个
k 定义的太小的话，就是说我们把比较
小量的变量呢，它的值是固定，就是说，我们的邻域呢，就是非常的大。
非常的大的话，我们就要搜索的时间呢，就有可能是过长，有可能呢
几乎是，是，等同是为我们原来的问题来求解，那这个也是不划算的。
所以呢，我们要把这个 k 呢，定义的非常的好，但是呢，不用害怕，因为呢，其实
我们有一个所谓是，自适应的一个方法来帮助我们去定义一个
随机的邻域的，我们呢，一开始的时候可以定义一个固定的 k
， k%，然后呢，然后我们也需要定义另外一个参数，这个参数
呢，我们称之为 S ，这个大 S 这个参数呢，就是决定我们去搜索我们的邻域的时候，
我们最多可以动用的资源是多少，刚才已经讲过了，那当然呢，默认我们就希望把这个邻-
域里面最 好的一点找出来，但是呢，如果我们的邻域是太大的话，我们根本就没有
办法，办法呢把这最好的一点找出来的，所以呢，我们需要把 我们可以调用的资源呢，来一个限制。
好，好了，初始，我们就有一个 k%
然后呢，我们就重复下面这个步骤，就是呢，先利用我们刚才定的这个 k
生成一个 随机的邻域 N ，然后，如果我们
发觉了，在 S 步之内， 我们就利用这个
S 来限制我们可以，可以利用多少的资源去搜索。
我们这个领域 N ，如果我们可以在小 n 之内那么多步呢，
就可以完成这个搜索的话，而且呢，这个小 n
是远远 的小于这个大 S 的话，就是代表什么呢，我们现在的邻域呢是太小了。
我们就很容易，就可以把最好的一个点呢，找到出来，所以呢，我们呢， 可以把我们的
k 呢，定的小一点，k 定的小一点的话呢，
我们就可以，我们的邻域呢，就可以变的大一点了，但是如果我们发觉呢，在 S
步之内我们 不可，不可能完成这个搜索的话，就是我们的
k 定的太小了，所以我们要把这个 k 呢，变的更大，就是说把 我们的邻域呢，定的小一点。
所以呢，我们就可以慢慢的去找 出一个，一个好的 k 的定义出来。
我们利用自适应这个 邻域的定义呢，是，其实是非常的鲁棒的，而且呢，
其实很，很多时候呢，很难被其它的方法呢，可以击败的。
好了，我们除了这个
要把这个大邻域里面最好的一点找出来之外呢，其实我们也可以 有其它的这个变种的。
因为刚才已经提过，如果我们的邻域是太大，
太多的相邻的点，需要我们求解的话，我们就可能，可能调用的时间是太多了，这个不值得的。
所以呢，其实我们有一个大邻域搜索的一个变种，就是我们称之 为贪心的大邻域搜索，就是在我们
为这个大邻域搜索的时候，我们不一定要把最好的一点找出来，我们呢，可以把
第一个，比较好的点找出来了，我们就停止了。
就返回这个点了，又或者把我们呢，
到了我们把我们一个限定的一个资源，把它已经用，用完之后，把目前为止找的最好
一个点，也可以返回了，也可以的，这个呢，我们就叫一个贪心的 大，大领域这个搜索。
嗯...这个 这样子呢，我们就有时候就不需要花太多的时间，去探索我们这个太大的一个邻域了。
当然呢，你们觉得会问，那到底这个 你这个刚才介绍的那么好的一个算法，在这个
MinZinc 当中我们可不可以调用呢？ 这要看看你在 MinZinc
里面将会要什么要的求解器了，我们有一些求解器呢，是 支持这个大邻域搜索的，譬如说
Gecode 就是其中一个的， 如果我们要
Gecode 调用这个大邻域搜索呢，我们只需要在我们的这个模型里面
solve这一项呢我们加上一个注解，就是加relax_and_
reconstruct，里面有两个参数，第一个参数呢就是我们希望去处理的 定义大邻域的变量。
另外呢一个就是刚才就是说我们要固定的变量的一个
百分比，首先呢，要解释呢就是这个varlist这个第一个参数呢我们不一定
要把我们问题里面所有的变量都放在这个数组里面的。
其实如果我们不放在这个变量的数组里面的话呢， 机构呢就会选择把不放在里面的变量都送出的，
这个譬如说如果我们问题里面，
除了我们主要的变量我们应该放在这个变量的数组里面呢，其他的辅助的变量
其实我们不需要放在这个里面的，有一点我们要提出呢就是
我们是需要，如果要用这个大邻域搜索呢，我们需要跟这个机构
里面的重启，restart这个技术一起来用的，但是如果我们用restart的话呢，- 我们通常
我们就要选择一个搜索的一个策略，这个
搜索的策略呢可以是固定的，如果我们选择了一个固定的搜索的
策略的话，我们每一趟的重启呢我们都会调用同一个搜索的策略，但是我们知道在resta- rt重启
这个技术方面呢，我们通常选择的搜索的一个策略呢，通常就是一个自适应的，譬如说
down_w_deg，或者是一些基于这个随机的一些搜索的策略呢是比较好一点。
好啦，现在我们就可以看看，我们把这个大邻域搜索再加上这个restart，它们
的威力有多大呢？我们就用，我们这个灭火问题来 演示一下，使我们原来的问题，不是我们刚才看的这个
小型数据哈，我们里面有100个着火点，里面有43个悟空，我们呢就把我们的
这个时限呢定为这个15分钟，就是我们跑
这个求解器15分钟，跑不出，然后我们就把它停下来，然后呢把
当前最好的一个结果呢，我们就返回，好了，我们可以看看，我们不用这个大邻域搜索，
我们就用普通，我们不定义什么的搜索的策略，就用minizinc
看看它的默认的一个搜索的策略，我们发现呢求出来的解呢是一个 差不多是八万那么大的一个数字。
这个值是，差不多是八万的，但是如果我们用重启这个搜索，
而且我们就是用这个luby这个policy的话，我们发现我们
找出来的这个解它的目标值呢比我们默认这个搜索的 策略呢是好了很多的，好了差不多是一万，
如果我们结合这个大邻域搜索跟我们刚才的luby这个重启的搜索的话，我们
也是利用这个70%这个固定率的话呢，
我们发现我们也可以把这个改善呢，差不多八千，
它的目标值，而且呢我们看一点这个非常重要，我们其实
经过一分钟，两分钟，三分钟之后呢，我们的大邻域搜索呢，因为它
搜索得更远，看得更远，搜索得 也更远呢，所以呢其实很快呢已经把我们的
目标值呢带到很低很低的一个数值呢，所以呢一个大邻域
搜索有一点跟刚才这两个搜索的策略有不同的地方就是其实在
15分钟的时候，我要把它停的时候呢，其实我发觉这个 它还是不断的找到更好的
最好的解，它的目标值它还是在降低的。
好啦，我们来为这一节课来一个小结，我们介绍这个大邻域
的一个局部的搜索方法呢是一个非常强大的 基于完备搜索方法的一个局部的搜索的一个技术。
而且它一个其中一个非常好的地方呢，就是它可以 处理任意的约束，当然有时候呢
我们很难是把所有的约束都满足的，特别我刚
才已经讲过了，我们是需要找出一个初始的可行的解的，
如果这个是很难的话，我们当然有可能是需要呢把某一些约束呢转
化为一个惩罚这个方法呢来处理的，我们这个
大邻域的一个搜索的方案呢其实就是帮助我们把一个我们完备的搜索的方法呢，把它扩展到
应用到更大的问题，其实最近呢，杰克我们介绍的都是
局部的搜索，而且呢在大邻域搜索里面，我们发现随机的领域呢是非常
的鲁棒的，但是要小心一点，我们不 这个不代表呢大邻域的这个搜索呢一定
是最好的，在特定的应用底下，有时候如果我们采用针对
我们这个问题一些专门的局部的搜索的技术的话，有可能呢出来的效果还是比这个大邻域的
搜索呢更好的。
[空白_录音] [空白_录音]
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2019 Coursera Inc. Todos os direitos reservados.
