虽然之前做的很多篇启发式的算法都有跟大家提过局部搜索这个概念,为了加深大家的印象,在变邻域主角登场之前还是给大家科普一下相关概念。热热身嘛~
官方一点:局部搜索是解决最优化问题的一种启发式算法。对于某些计算起来非常复杂的最优化问题,比如各种NP完全问题,要找到最优解需要的时间随问题规模呈指数增长,因此诞生了各种启发式算法来退而求其次寻找次优解,是一种近似算法(Approximate algorithms),以时间换精度的思想。局部搜索就是其中的一种方法。
通俗一点:局部搜索算法是对一类算法的统称,符合其框架的算法很多,比如之前公众号推文中介绍的爬山法、模拟退火法和禁忌搜索算法都属于局部搜索算法。尽管各个算法在优化过程中的细节存在差异,但在优化流程上呈现出很大的共性。
它的基本原理是在临近解中迭代,使目标函数逐步优化,直至不能再优化为止。
我们可以将局部搜索算法的统一框架描述为:
局部搜索算法主要包含五大要素:
其中前两个要素的定义和算法要解决的特定问题有关,而且不同的人对同一问题可能有完全不同的定义。后三个要素定义的不同则会产生各种不同的局部搜索算法,而它们的效率和最终解的质量也会有很大的差异。
对上面的局部搜索有一定的印象以后,理解变邻域搜索也不难了。其实说白了,变邻域搜索算法(VNS)就是一种改进型的局部搜索算法。它利用不同的动作构成的邻域结构进行交替搜索,在集中性和疏散性之间达到很好的平衡。其思想可以概括为“变则通”。
变邻域搜索依赖于以下事实:
它由主要由以下两个部分组成:
大家别急,下面我们将会对这两个部分进行分析。然后,before that……
官方一点:所谓邻域,简单的说即是给定点附近其他点的集合。在距离空间中,邻域一般被定义为以给定点为圆心的一个圆;而在组合优化问题中,邻域一般定义为由给定转化规则对给定的问题域上每结点进行转化所得到的问题域上结点的集合。
通俗一点:邻域就是指对当前解进行一个操作(这个操作可以称之为邻域动作)可以得到的所有解的集合。那么邻域的本质区别就在于邻域动作的不同了。
邻域动作是一个函数,通过这个函数,对当前解s,产生其相应的邻居解集合。例如:对于一个bool型问题,其当前解为:s = 1001,当将邻域动作定义为翻转其中一个bit时,得到的邻居解的集合N(s)={0001,1101,1011,1000},其中N(s) ∈ S。同理,当将邻域动作定义为互换相邻bit时,得到的邻居解的集合N(s)={0101,1001,1010}。
VND其实就是一个算法框架,它的过程描述如下:
我知道没图你们是不会点进来的……
VND的图解如下:
只说两点,再问自杀:
之前我们把局部搜索比喻作爬山的过程,那么每变换一次邻域,也可以理解为切换了搜索的地形(landscape)。效果如下 :
每一次跳跃,得到都是一个新的世界……
伪代码描述如下:
其实呀,这玩意儿。说白了就是一个扰动算子,类似于邻域动作的这么一个东西。通过这个算子,可以产生不同的邻居解。虽然名词很多看起来很高大上,扰动、抖动、邻域动作这几个本质上还是没有什么区别的。都是通过一定的规则,将一个解变换到另一个解而已。这里读者还是抓其本质,不要被表象所迷惑了就好。
在综合了前面这么多的知识以后,VNS的过程其实非常简单。可以描述为以下几步:
结合伪代码,一目了然:
分别举两个应用实例。
C++代码。
欲获取代码,请关注我们的微信公众号【程序猿声】,在后台回复:VNS代码。即可获取。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。