优化是决策的一般形式，在我们的社会中很常见。它的应用包括从求解数独谜题到婚礼上的座次安排。同样的技术可以调度航班和机组成员，协调钢铁生产，组织铁矿从矿井到港口的运输。人力资源和材料管理上好的决策可以令企业提升上百万的盈利。同样的问题很多也在我们日常生活出现，成为决定每天送货路线，决定学校时间表，传输电力到家里等种种问题的一部分。除了它们的重要性，这些问题如果用传统的本科计算机科学方法难以求解。 这门课程为已经完成离散优化高阶篇的同学设计。 请看这门课程的宣传视频：http://www.cpr.cuhk.edu.hk/cutv/detail/988
3.4.2 约束和局部搜索
Loading...
來自 The Chinese University of Hong Kong 的課程
离散优化算法篇 Solving Algorithms for Discrete Optimization
個評分
從本節課中
局部搜索
这个模块带你进入局部搜索的神奇领域，它可以高效地探索一些大而复杂的搜索空间。你将会学到状态，移动和邻域的概念，还有它们在受约束的搜索空间中如何被应用在基本贪心搜索和最速梯度下降搜索中。你还将学习不同的方法来逃离或者避免局部最小值，包括重启，模拟退火，禁忌表和离散拉格朗日乘数法。最后，你将会看到大邻域搜索把在邻域中找到最优相邻点看作一个离散优化问题来解决，并因此使我们探索更远和更有效地搜索。
與講師見面
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
悟空找
到芭蕉洞后便向铁扇公主借用芭蕉扇 铁扇公主想起悟空与红孩儿的过节不愿相借
数次言语不和后，心急气躁的悟空便与铁扇公主对打
企图强抢芭蕉扇，铁扇公主法力高强 悟空一时难以招架，便拔出猴毛
化作六只猴子分身围攻铁扇公主，但仍被打的落花流水
六只猴子之间协作程度各有不同，诸葛亮给以矩尺调整阵形
或能击败铁扇公主，就召出时空飞龙 [音乐]
我们帮助了悟空找到这个芭蕉洞，也找到这个铁扇公主，然后当然呢他在问这个
铁扇公主要她的芭蕉扇呢，但是如果我们去知道他们
两个的过去的话，当然了铁扇公主是不愿意把她的
扇呢去借出来的，所以呢他们就打起来了 就当这个悟空就是发觉他有可能不够打的时候呢
他就拔出他身体上面的那个猴毛，然后把他的猴子
猴孙呢都变出来了，现在他要做呢就是把变出来的猴子呢
就是排出一个队形，这个队形非常简单，就是这样子一行
但是这个队形最厉害的地方呢就是需要每一个猴子跟他旁边的猴子呢
他们的合作性最高，然后这个队形就可以发挥它的效用了
好啦，其实对于每两个猴子呢我们都会量他们的合作性到了什么地方呢，如果是
一个正的数字的话我们就说他们的合作性是挺好的，但是如果他们合作的不好的话我们就给它- 一个负的值
就是这样子，然后我们下面就把这个刚才看到这个六只的猴子呢
他们互相的合作的地方和合作的好不好？我们可以看见呢中间呢是因为是每一
一头猴子跟自己的合作性我们都把它变为0 而且呢这个这个我们这个矩阵呢是对称的。
好啦，大家一看这个这个很简单的一个离散优化问题
我们要为一群的猴子排列，然后呢要把猴子跟猴子之间的合作的值
把它加起来然后把这个总和呢最大化 所以呢下面我们也可以看看它一个非常简单的一个
MiniZinc的模型是怎么样的，首先我们这个猴子这个枚举类型
然后呢就是一个二维的一个数组，这个数组呢就是代表的一个表，就是猴子跟猴子之间他们的- cooperation
就是他们合作的值，然后呢当然呢我们也需要一个 数组就是呢在这个排列上面每一个位置
我们应该放一头什么的猴子在这个位置呢，在这个问题里面当然我们有一个约束的
这个约束我们就需要在六个位置上面的猴子都是不同的猴子，因为悟空是变了六头的猴子出来
然后我们要优化呢就是什么呢，这猴子，每一头猴子看到旁边的猴子之间的合作
合作性的值把它加起来然后呢要把它的最大化
这个就是我们简单的一个模型，为了这个问题呢我们就有下面这个数据，原来呢
之前的猴子他们也有英语的名字的，所以我们就利用这个枚举类型的一个
来代表他们不同的猴子的名字，而且呢这个二维的表呢就是
来代表我刚才讲过的猴子跟猴子之间的它们的合作的数值
现在下面呢我们就希望可不可以利用我们讲过的局部
搜索的方法呢，来帮助他找到一个好的顺序出来，然后跟这个，帮助他去跟这个
铁扇公主继续打这一场仗。
那首先呢这个问题特别的地方
第一看起来这个不是个搜索的问题，如果我们看之前的问题呢，我们是要
找这个铁扇公主的芭蕉洞的，真的要去找一个地方
但是呢这个是一个基本的离散优化问题，但是在之前
我们曾经已经看过了，其实我们要解决一个离散优化问题呢
我们也是利用这个搜索的技术的，所以我们其实也可以利用这个想法呢，思想呢
来利用这个局部搜索呢，来搜索呢，来帮助我们解决这样子的离散优化的问题
另外一件事情这个问题跟之前的问题不一样呢就是我们上一个要
寻找这个芭蕉洞呢就是我们只有一个目标函数是没有约束的，但是我们可以
看到呢我们在这个问题里面有一个约束，就是要求呢在这个排列上面每一个未知猴子呢
他们都是互不相同的，所以在下面我们呢我们还是要讲这个局部搜索
但是呢我们要讲就是在局部搜索当中我们怎么去处理约束呢
我们将会提出两个方案，第一个方案呢我们叫隐含约束
这是什么意思呢，就是我们要保证整个搜索的过程里面我们去到每一点
每一点呢都要满足我们这个问题里面的约束的，这个包括我们的初始的状态，就是初始这个点
所以我们要首先有办法找到一个初始的点呢是满足这个 约束的，然后我们也需要定义我们的移动的方案。
这个定义呢要保证就是我们从一个满足约束的点呢，根据这个移动的
方法跳到另外一个点呢，这个新的点也是需要满足我们这个约束的。
但是呢，虽然看起来是非常好，但是这一个方案呢不是一般性的。
意思就是呢其实我们对于不同的约束我们都要为它
量身定制一个不同的邻域的定义，所以呢这个是通常不太容易的
我们介绍的另外一个方案呢是基于所谓是软的约束，就是说呢我们虽然问题里面有约束
但是我们是允许这个约束被这个违反的，但是违反之后呢，我们当然呢你违反了约束呢
我们有一个给它一个惩罚的值，然后呢惩罚的值呢也需要把它放到
我们的目标函数当中，这个是一个一般的方法，对于所有的问题呢，我们也可以
利用这个软的约束这个方案，但是 这个方案有一个不好的地方就是有可能，有可能
我们去找到的解呢永远都不可以满足我们问题里面所有的约束的，我们在下面就看看
这两个不同的方案他们怎么可以利用他们来处理我们在做这个局部搜索的时候
怎么去处理这个约束呢。
嗯，第一个方案就是呢我们把
约束当为这个隐含的约束，其实呢我们需要做呢就是 把我们在局部搜索里面的邻域
把它加上这个约束，这个约束这个限制是很简单，就是我们要保证
邻域里面的所有我们要到新的点呢都是满足问题里面的约束的
在我们现在这个故事里面有一个约束就是在整个 排列上面所有的猴子都是互不相同的
所以第一我们就要找一个初始的点，这一初始的点就是保证我们的
这个猴子都是满足这个互不相同的这个这个约束的。
我们 对于这个问题其实也挺简单，就是我们随机为我们六头的猴子
来做一个顺序的排列，就用随机的方法找出这样子的方案，所以非常明显
我们已经保证了我们的初始的点或者是叫初始的状态呢是满足了我们的这个约束
然后当然呢我们需要定义一个移动的方案，就是从一个点我们怎么可以移动到另外一个点呢
我们专门为了这个问题设计这个移动的方案呢就是我们把我们现在排列的猴子
把它每两头猴子呢互相交换他们的位置，交换了之后我们没有把猴子
换出或者是换入，所以呢我们还是保证呢在这个排列上面所有的猴子
他们还是互不相同的，我们的邻域的 定义呢就基本上利用我们这个移动的定义
得到我们现在这个点所有利用这个交换两头猴子的这个移动呢来定义我们的邻域。
好了，我们呢可以看看我们这个，如果
利用这个我们之前看过第一个的就是贪心局部搜索，也利用了这个有约束的
邻域，我们出来的搜索的结果会怎么样，我们的初始状态
刚才已经讲了，是随便地把所有的猴子顺序排列
也可以，我们就看看就是从 ABCDE 这个排列好不好。
然后当然呢我们要 算一算它的目标值，现在它的目标值为-6不太好的。
然后 我们就看看有什么可能，可以把其中两个、 两头的猴子呢把它调换呢。
在所有的可能的调换当中，因为我们现在是做
贪心的局部搜索呢，所以我们就随便、 随机地找 其中一个点出来。
譬如说，我们就找到了就是 把 C 跟
F 这两头的猴子调换的话，会发生么事情呢？我们就看看如果调换出来结果呢是这样子
然后我们也把新的目标值再算一算，是4。
4当然呢，是比这个-6好很多。
所以呢，我们就可以前往这个新的一点。
然后呢，我们就在新的一点再看看，它有什么方法可以有东西可以调换啊。
我们看看啊如果发现把 D 跟
A 调换会出现什么结果，发现如果这样子调换的话
出来的目标值为9，比6是更好的。
所以我们前往 这个新的点，然后我们再看看在这个情况之下的这个点
然后我们找一个相邻的点，就是譬如说把 F
跟 B 调换会有什么结果啊，我们发现如果把它调换的话
出来结果它的新的这个目标值呢是为0 是比这个9差劲的，所以我们就不前往了。
其实我们现在就可以继续这样子利用这个贪心局部的搜索
来继续去找更好的点，但是如果大家还记得
这个贪心局部搜索是没有保证我们可以把这个 最优的解可以找到出来的。
所以呢，我们下面就看看
如果我们是用最速下降的搜索的话，而也加上我们这个
对这个领域的约束的结果，它的效果会是怎么样。
我们起始的一点呢，我们还是用这个 ABCDEF 吧。
然后它们的目标值如果大家还记得是-6，但是我们因为是做最速下降
所以呢我就要把现在目前这个点所有可能移到的新的点呢，它们的目标值呢 也要算一遍出来。
我们可以看见呢，我们也有挺多的在它的领域里面有挺多的点。
每一个点我们都看看，如果我们就做这个调换，如果我们做这个调换，如果我们做不同的调换；
出来了，它的目标值呢是会变成怎么样，然后呢，我们就要选取最好的一点。
如果我们去到4这个点，比较所有的领域，它是最好的一点。
虽然 有其中一个出来结果跟4也是一样，但是我们随机随便选取一个吧。
所以呢我们就 决定呢要把 C 跟 B 调换，我们就可以呢
去到新的一点，它的目标值呢是4。
从这一个状态呢，我们也把它所有的相邻的点，就是所有可能的交换，两头猴子的交换，也要
算一算出来的目标值是什么。
然后我们发觉呢如果我们 把 F 跟 C 调换的话，出来的目标值呢是最好的 就是13。
所以当然呢，我们就跳去新的一点，去到13一点我们也可以看呢 发现所有相邻的点呢这个跳到把
B 跟 A 调换呢，出来的目标值是最好。
所以呢，我们也跳到这个新的一点。
跳去新的一点之后呢，我们 在把它所有相邻的点当它的目标值呢也是
再算一遍，我们发觉呢就算是最好的点，有两点是最好的点吧
出来的它的目标值呢，是比我们现在的点
它的目标值是差劲的更糟糕的。
所以呢，我们就没有这个 就算我们用最速下降的搜索的方法也是不可以再移动了。
好了，我们要重新 检视我们这个最速下降这个方法
在用于约束领域里面会有什么效果。
现在最好的移动已经会变成更差了，而且更糟糕的时候呢，我们有可能要循环到 之前的一个状态。
但是呢，我们如果因为这个问题也不是太大，其实呢我们可以
把这个里面所有不同的点它们的目标值也算出来的。
我们的猴子是这样子的一个排列的话，出来的目标值呢是15。
是比我们刚才利用我们最速下降这个方法要停的时候，发现了这个 点是更好的。
其实我们刚才发现什么事情呢？ 本来我们讲过最速下降这个方案是
可以保证可以找到这个最优这个点的。
但是还没有讲完，是在什么情况之下呢？如果我们的这个地形是凸的，
那我们就有这个保证，其实呢在这个非凸的地形呢，已经没有这个保证了。
其实更所以呢 我们刚才找到的一个点不是一个全局的最好的点。
刚才讲到的我们对于这个问题称之为局部的最大的点。
因为我们现在是做最大化的问题。
所谓这个局部最大的点，就是说刚才从这点可以出发的话，我们看看它的领域
里面所有其他的点，发现没有一个点可以帮助我们 可以再提升我们目前的目标函数的值的。
就是我们已经不可以再移动了，所有 其它的点呢，都会只会降低我们的目标函数值的。
所以呢，我们就达到这个点，我们就称之为 局部最大的点。
这就是所谓是局部最大的点，我们不知道。
但就是一个局部最大的点呢不一定是一个最优的点，所以 我们达到的只是一个局部的最优，不是全局的最优。
好啦，我们现在可以再看一看，看过刚才的
演示之后，我们可以重新再看一看这个移动跟这个局部最优之间的关系。
其实呢，我们在我们的这个这个领域呢的定义呢
是加上了限制的，所以呢在有约束的情况之下呢我们的领域呢
是比较小，而且呢更没有弹性，就是说呢我们说本来我在一个点我有很多领域
但是因为我这个问题里面有限制，所以呢 我们就是告诉这个我们搜索呢说
这个点不可以去，这个点不可以去，所以呢所以我们这个搜索的空间它的所谓的是连接性呢
是比没有约束的情况之下呢更差了。
所以我们移动的灵活性
就减少，而且呢我们有更大的机会因为我们可以移动到的地方比较少，更少；
所以呢，我们有更大的机会的只可以移动到一个我们所谓刚才讲过的局部的最优的一个点。
当然了，我们明白另外一个理由我们为什么会去到一个局部最优的点呢？
就是如果我们这个搜索的空间本身已经是非凸的，这个当然也是导致
我们可以找到这个去到一个局部最优的点。
所以对于每一个 不但是我们讲过的局部搜索的方法，如果第一个局部都搜索的方法
它是要成功的话，它们肯定是需要的一些不同的技术可以帮助我们
逃离局部最优的点，这样子的我们这个局部搜索的方法
才可以成功的。
我们在在未来的节课堂里面会
跟大家再详细地去介绍我们怎么可以逃离这个局部的最优的点。
好啦，刚才已经讲过其中一个方案去怎么
处理一个问题里面的约束，我们讲现在就讲介绍这个第二个 另外一个方案。
就是呢，我们把一个约束呢当为一个软的约束，就是说呢它们是
可以被这个违反的，但是它违反了约束之后呢，我们就需要把它给它一个
惩罚；而且呢，这个惩罚呢我们是需要把它当为我们这个
目标函数里面的一部分，这就把它加进我们的目标函数里面的。
所以呢 那我们怎么违反了一个约束之后，怎么觉得给它的惩罚，惩罚是多少呢？
其实有不同的方法，比较一个简单的方法，就很简单的
就是如果我们有一条约束不被满足的话，我们就给它一个固定的 惩罚值就可以了。
譬如你可以这个值是 1 或者是 2，但是这个这个值呢是固定的，是固定的。
但是我们觉得其实有个更好的方法，就是基于呢我们说我们违反了这个这个这个约束
但是我们违反了这个约束有多大的程度呢，又或者说我们
距离我们要满足这个约束有多少呢？我们是基于这样子的一个一个
量出来的数值呢来决定我们的惩罚值，
也可以可以呢就是我们的违反的程度乘以我们的惩罚值
就出来了，就是我们给不满足这个约束它的惩罚了。
我们看 看 alldifferent 这个约束，我们刚才讲过如果我们用利用这个简单的方法的话
就是说如果违反了 alldifferent 之后，我们就给他一个固定的惩罚值就可以了。
但是呢另外一个更好的方法 就是我们看看到底这个 alldifferent 是给违反了多少， 它的违反的程度是多少。
我们可以看看呢这个 alldifferent
里面的所有的变量 它们取的值呢有多少个它要取相同的数值的，我们就可以计算一下，然后就利用这个
有多少个相同的值呢来定为我们 如不满足这个 alldifferent 这个全局约束的它的惩罚的值。
这个是也是另外一个方案。
好了，我们就可以看看 利用这个惩罚值这个再加上我们的最速下降这个搜索
出来的效果会是怎么样。
最初始的点也是用我们原来这个 A B C D E F 吧，
我们的这个目前的目标值呢是负 6，我们的邻域呢就是什么
我们可以允许我们改变六头猴子六个位置里面其中的位置，我们可以
改变放另外一头的猴子进去，那当当然呢我们如果要放另外一头猴子进去
如果这个猴子呢是跟我们原来的猴子相同的话，新的这一头猴子不会
自己变出来的，是需要原来这头猴子他要用法术分身 变另外一头猴子出来。
那这样子说呢就需要能量了，要要要要要用能量了，所以为了这个
能用的这个多了的能量呢我们需要 把他给他一个惩罚，我们呢在这里呢就就是基于
在这个 alldifferent 这个全局约束里面违反这个 alldifferent
的次数，就是说我们现在整个 排列里面有多少个位置呢他有相同的数值呢 就作为我们的违反的次数。
然后我们说因为我们要 变一头新的猴子出来，所以要给他给他一个惩佛惩罚。
这个惩罚呢我们就现在就建议定他为 1000
吧， 如果这样子定义这个惩罚看他出来的效果是怎么样。
从这个初始的点 我们要改其中一个位置他的数值
随便找一个点吧，譬如说就是这个点我要把这头猴子呢本来是 C 的猴子呢变
为一个 A 的猴子，如果这样子变的话我们发现呢在同一个排列上面有两个
位置呢他的数值呢是一样的，所以呢我们就违 有意识地违反。
好了，然后我们也一样把这个目标
函数的值呢计算出来，把猴子跟猴子之间他们的合作的值呢
加起来而且呢因为我们违反了我们的约束一趟，所以呢我们要给他一个惩罚。
在这里呢就是 1000 乘以 1 所以就是 1000
了，出来呢就是负 994 哇！这个数值呢是非常低的。
其实你们想清楚无论我们选择去 改变任何一个位置的猴子，其实我们都
一定要违反我们这个 alldifferent 这个约束的。
为什么？因为无论你怎么改肯定会跟 在排列上面其中一头猴子呢有相同的值的。
有了要违反这个约束，我们就要 惩罚呢是
1000，这个 1000 比我们的目标函数里面所有
其他的值呢都是大很多的，所以出来的结果呢就是一个 负值非常低非常负的一个数值。
所以基本上呢我们在一个初始这个点呢我们已经
达到一个局部的最大点了，我们根本就不可以移动到 任何其他的点。
我们现在的问题就是我们要 惩罚一个违反呢是给他的惩罚值呢是太高了。
好了，刚才就把这个惩罚值呢定的太高，如果把这个惩罚值定低一点可不可以呢？譬如说 我把他定为
1 好不好啊，那这样子呢我们就可以移动了。
看看所以我们说我们改变这一个猴子这个位置的猴子吧 因为我把他改成为
A 我们出来结果呢就是所有的合作的数值，但是因为他违反了一个
一趟这个 alldifferent，所以呢我们要减 1 出来是
5，5 是比这个负 6 为好的，所以我们前往这个新的点。
然后呢我们再找另外一个位置呢，把他改改改改变他的值发现呢如果 改变为这个
A 的话，我们发现呢我们违反我们 alldifferent 呢两趟了 三趟。
因为是两个相同一趟，这两个相同一趟 这个跟这个相同也一趟，所以呢我们要减这个
3 从他的目标 函数里面减 3 出来是 11，还是比之前的目标函数的值是为好的 所以我们可以到这个新的点。
然后我们继续可以我们改变这个吧，发现改了这个第一 之后呢我们发现呢我们有三个
A，然后呢是两个 D，我们总共违反了这个 alldifferent 呢是四趟。
所以呢在下这里呢我们就要把它目标值呢减 4 我们还是出现了这个
目标值呢还是比之前的更好，所以我们前往这个点我们可以这样子继续。
然后呢 再改，然后呢我们还可以继续去到这个 17
这个 点，然后如果我们这样子继续搜索的话我们发现呢
下一个移动的点呢发现我们不可以再提高我们目前的目标函数的值了，因为呢其实呢发现我们
去到一个平原，平原所谓平原就是呢我们发现我们下一个点呢 是跟目前的目标值呢是一样的。
平原这个呢这个概念呢我们将会在未来呢更 深入的为大家探讨这个问题。
但是如果我们看看刚才的搜索呢，其实我们发没发现我们的搜索里面 根本就没有尝试过去满足我们
alldifferent 这个这个约束，因为呢我们
给他的惩罚的值呢是太低了，因为每一趟违反了一次我们才把他 减
1，相对于我们的目标的值他的出来的目标函数的值呢是可以
10，15，17 你减一点一点呢根本就没有这个这个这个这个
效用的，所以呢根本我们的搜索从来没有尝试过去 把这个约束去满足。
所以呢所以我们如果 把这个惩罚值呢定的太低这个也是不行的。
所以刚才我们看可以看见了我们如果把
一个约束当为这个惩罚的话，如果把这个惩罚值呢定的太高
我们呢就很容易就被就会去就会去到一个局部的最优的一个点，然后我们就移动不了。
因为惩罚定的太高的话我们就很我们的移动呢
就就就就就很多时候就领导我们不可以违反 更多的约束。
如果我们把这个惩罚值定的太低 的话刚才已经可以看见，基本上呢我们就是把我们的
约束放在一边，我我们的搜索呢还是为了去把我们的目标函数值呢
进一步的提高，把这个约束呢就一点都不理他，所以出来的效果也是不太好的。
好了，我们现在可以为这一节课呢来一个总结。
在这课在这节课里面呢我们介绍过 两种在这个局部搜索的算法里面怎么去处理这个约束，我们介绍了两个方案。
第一个方案 呢就是基于所谓是隐含的约束，就是那我们保障我们在整个搜索的过程里面呢
我们的约束呢每一步每一点都是呢把我们的约束呢都是满足的。
这个方案呢有一个不好的地方就是呢我们要为问题里面每一种的约束呢
都要有可能重新要设计不同的移动的方案而且呢 要重新定义什么叫这个邻域，
所以呢这个是不是一件容易的事情。
所以呢我们 这个不是一般性的一个方案可以采用的，而且呢利用这个隐含约束这个方案呢就是
因为我们就说你这个不可以去这个也不可以去，所以呢我们的
在搜索的过程里面呢就遇到很多的限制，
所以呢很容易我们就会掉到一个所谓是局部的最优的点了，这个 就是我们的隐含约束的一个问题。
但是呢这个方案有一个好处就是呢 无论我们可不可以把这个最优的解找到出来，但是如果我们可以
找到一个解，这个解呢是保证把我们问题里面所有的约束呢都满足的。
我们第二个方案呢就是基于所谓是软约束这个方案，就是呢我们可以允许我们问题里面的
约束呢是可以被违反的，但是违反约束之后当然呢我们要给他一个惩惩罚的值
就是来惩罚你违反的约束，这个是比较一般性的方案。
因为对于不同的约束呢 我们就可以用这个方案来做的，但是呢我们要用这个方案的时候呢
就要非常小心去调我们的惩罚值跟我们的目标函数他们是怎么比较的。
如 刚才已经看过最大不行最小也不行，因为最小太小的话
我们有可能呢就是去到一个找到一个出来的的解的
都是不可以满足我们问题里面约束的，最大的话我们就非常容易呢去就就掉在一个局部最优的 的一个点上面。
其实呢我们介绍这两个方案 呢是没有冲突的，所以如果我我我我们其实可以针对
我们问题里面不同的约束我们其实可以
把两种方法都都都都都应用，针对不同的约束他们的
找出一个比较合适的方案呢来来来处理这个约束
这个也是可以的。
[无声]
