干货 | 变邻域搜索算法(Variable Neighborhood Search,VNS)超详细一看就懂

目录

01 局部搜索再次科普

02 变邻域搜索

03 造轮子写代码

字数

1936 字

时间

预计10分钟

01 局部搜索科普三连

虽然之前做的很多篇启发式算法都有跟大家提过局部搜索(local search)这个概念,为了加深大家的印象,在变邻域主角登场之前还是给大家科普一下相关概念。热热身嘛~

1.1 局部搜索是什么玩意儿?

官方一点:局部搜索是解决优化问题的一种启发式算法。对于某些计算起来非常复杂的优化问题,比如各种NP-难问题,要找到最优解需要的时间随问题规模呈指数增长,因此诞生了各种启发式算法来退而求其次寻找次优解,是一种近似算法,以时间换精度的思想。局部搜索就是其中的一种方法。

通俗一点:局部搜索算法是对一类算法的统称,符合其框架的算法很多,比如之前公众号推文中介绍的爬山法、模拟退火算法和禁忌搜索算法都属于局部搜索算法尽管各个算法在优化过程中的细节存在差异,但在优化流程上呈现出很大的共性。

它的基本原理是在邻近解中迭代,使目标函数逐步优化,直至不能再优化为止。

1.2 局部搜索的过程

我们可以将局部搜索算法的统一框架描述为:

1) 算法从一个或若干个初始解出发。

2) 在算法参数控制下由当前状态的邻域中产生若干个候选解。

3) 以某种策略在候选解中确定新的当前解。

4) 伴随控制参数的调节,重复执行上述搜索过程,直至满足算法终止条件。

5) 结束搜索过程并输出优化结果。

1.3 局部搜索的几大要素

局部搜索算法主要包含五大要素:

1) 目标函数:用来判断解的优劣。

2) 邻域的定义:根据不同问题,有着不同的邻域定义。

3) 初始解的产生方法。

4) 新解的产生和接受规则。

5) 算法终止条件。

其中前两个要素的定义和算法要解决的特定问题有关,而且不同的人对同一问题可能有完全不同的定义。后三个要素定义的不同则会产生各种不同的局部搜索算法,它们的效率和最终解的质量也会有很大的差异。

02 变邻域搜索算法

2.1 什么是VNS?

对上面的局部搜索有一定的印象后,理解变邻域搜索也不难了。其实说白了,变邻域搜索算法(VNS)就是一种改进型的局部搜索算法。它利用不同的动作构成的邻域结构进行交替搜索,在集中性和疏散性之间达到很好的平衡。其思想可以概括为“变则通”。

变邻域搜索算法依赖于以下事实:

1) 一个邻域结构的局部最优解不一定是另一个邻域结构的局部最优解。

2) 全局最优解是所有可能邻域的局部最优解。

变邻域搜索算法主要由以下两个部分组成:

1) VARIABLE NEIGHBORHOOD DESCENT (VND)

2) SHAKING PROCEDURE

大家别急,下面我们将会对这两个部分进行分析。然后,before that……

2.2 你们一定想知道邻域是什么?

官方一点:所谓邻域,简单的说即是给定点附近其它点的集合。在距离空间中,邻域一般被定义为以给定点为圆心的一个圆;而在组合优化问题中,邻域一般定义为由给定转化规则对给定的问题域上每结点进行转化所得到的问题域上结点的集合 (太难懂了 呜呜呜.....)。

通俗一点:邻域就是指对当前解进行一个操作(这个操作可以称之为邻域动作)可以得到的所有解的集合。那么不同邻域的本质区别就在于邻域动作的不同了。

2.3 还是要说说邻域动作

邻域动作是一个函数,通过这个函数,对当前解s,产生其相应的邻居解集合。例如:对于一个bool型问题,其当前解为:s = 1001,当将邻域动作定义为翻转其中一个bit时,得到的邻居解的集合N(s)={0001,1101,1011,1000},其中N(s) ∈ S。同理,当将邻域动作定义为互换相邻bit时,得到的邻居解的集合N(s)={0101,1001,1010}。

2.4 Variable Neighborhood Descent (VND)

VND其实就是一个算法框架,它的过程描述如下:

1) 给定初始解S; 定义m个邻域,记为N_k(k = 1, 2, 3......m);i = 1。

2) 使用邻域结构N_i(即 N_i(S))进行搜索,如果在N_i(S)里找到一个比S更优的解S′,则令S=S′, i=1

3) 如果搜遍邻域结构N_i仍找不到比S更优的解,则令i++。

4) 如果i≤m ,转步骤2。

5) 输出最优解S。

我知道没图你们是不会点进来的……

VND的图解如下:

只说两点,再问自杀:

1) 当在本邻域搜索找不出一个比当前解更优的解的时候,我们就跳到下一个邻域继续进行搜索。如图中虚黑线所示。

2) 当在本邻域搜索找到了一个比当前解更优的解的时候,我们就跳回第一个邻域重新开始搜索。如图中红线所示。

之前我们把局部搜索比作爬山的过程,那么每变换一次邻域,也可以理解为切换了搜索的地形(landscape)。效果如下 :

每一次跳跃,得到都是一个新的世界……

伪代码描述如下:

2.5 shaking procedure

其实呀,这玩意儿。说白了就是一个扰动算子,类似于邻域动作的这么一个东

西。通过这个算子,可以产生不同的邻居解。虽然名词很多看起来很高大上,扰动、抖动、邻域动作这几个本质上还是没有什么区别的都是通过一定的规则,将一个解变换到另一个解而已。这里读者还是抓其本质,不要被表象所迷惑了就好。

2.6 VNS过程

在综合了前面这么多的知识以后,VNS的过程其实非常简单, 直接看伪代码,一目了然:

做点说明吧。伪代码中N_kN_l代表的邻域集合,分别是给ShakingVND使用的,这两点希望大家要格外注意,区分开来哈。这两个邻域集合可以是一样的,也可以不一样。

本打算将伪代码用文字来翻译一下,但是这个过程太痛苦了,小编抓狂了一阵后就放弃了。拜托大家还是看伪代码吧。有什么疑问请在留言区提出来,小编会老老实实的回复的。

03 变邻域搜索代码应用举例

小编打算用这个算法多做几个代码实例,如果都放在这里文章篇幅可能有点大。所以敬请关注我们,代码实例会在后面陆续推出的。

原文发布于微信公众号 - 数据魔术师(data-magician)

原文发表时间:2018-05-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨熹的专栏

David Silver深度强化学习第1课

强化学习-1.jpg 强化学习本质上是要找到一种最优的方式来做决策。 强化学习涉及到很多学科领域,例如它是计算机科学中机器学习的一部分,工业中的优化控制,还有模...

3155
来自专栏AI研习社

从理论到实践,一文详解 AI 推荐系统的三大算法

介绍 背景 随着互联网行业的井喷式发展,获取信息的方式越来越多,人们从主动获取信息逐渐变成了被动接受信息,信息量也在以几何倍数式爆发增长。举一个例子,PC时...

4087
来自专栏AI科技评论

百度ICML论文:如何用一种算法同时解决中英两种语言的语音识别需求

论文作者:Dario Amodei , Rishita Anubhai , Eric Battenberg , Carl Case , Jared Casper...

40912
来自专栏量子位

当你的深度学习模型走进死胡同,问问自己这5个问题

安妮 编译自 Semantics3官方博客 量子位 出品 | 公众号 QbitAI ? 深度学习是一项庞大又复杂的工程,在建立深度学习模型时,走进死胡同被迫从头...

3894
来自专栏华章科技

一文看懂数据可视化:从编程工具到可视化表现方式

说到可视化,就不得不说一下大数据,毕竟可视化是解决大数据的一种高效的手段,而如今人人都在谈论大数据,大数据 ≠ 有数据 ≠ 数据量大, 离谱的是,如今就连卖早点...

992
来自专栏数据科学与人工智能

【案例】10个数据可视化案例,让您更懂可视化

小编邀请您,先思考: 1 如何选择正确的图标视觉化数据?有哪些经验教训? 数据可视化,是一种用来将复杂信息数据清晰表述出来的强大有力的工具。通过可视化信息,我们...

2995
来自专栏AI科技大本营的专栏

硬货 | 分析完2017ACL论文和演讲,我发现了深度学习在NLP中的四个发展趋势

向AI转型的程序员都关注了这个号☝☝☝ ? 作者通过分析2017年ACL的论文,以及演讲内容,得出了四个NLP深度学习趋势: Linguistic Struct...

3104
来自专栏机器之心

资源 | 《深度学习》中译版读书笔记:GitHub项目等你来Fork&Commit

3745
来自专栏大数据文摘

深度学习中的怪圈

2569
来自专栏量子位

周星驰的睡梦罗汉拳心法,现在AI也学会了:梦中“修炼”,醒来“实战”

刚刚,两位人工智能界的大牛:Google Brain团队的David Ha(从高盛董事总经理任上转投AI研究),瑞士AI实验室的Jürgen Schmidhub...

1063

扫码关注云+社区