专栏首页程序猿声如何实现一个高效的启发式算法?

如何实现一个高效的启发式算法?

一、前言

小伙伴们好,说起来已经好久好久好久没见了呢!之前一直忙着做其他事情去了(泛指学习一类),公众号已经落下好久好久了。今天来写点好玩的东西。

说起来,小编似乎就是做启发式算法起家的。当时记得老师是这么跟我说的,启发式算法这东西很简单,你不需要基础,有高中基础就够了(其实他想说的是初中……)。

后来小编一直在学这个东西,做了三四年了,用启发式算法做过的大大小小的project已经不记得有多少了,所以还算得上有一点点经验。因此今天就来写写,怎样实现一个比较高效的启发式算法吧~

二、何为高效?

说到这个词,相信大家一定不陌生。高效意思就是达到相同效果或者更好的效果时,使用的时间更短,所需要的资源更少。就拿小编来说,由于小编特别笨,学一样东西需要花一周的时间,而群里的小伙伴只需要一天的时间就能学会。那么这位小伙伴是要比我高效的。

同样的对于一个启发式算法而言,不同人实现出来,即使是使用同一编程平台达到同样的效果,运行时间也会千差万别,相差几倍甚至几十倍。这样说出来大家可能还没啥感觉,那么放一下我们之前做过的一些数值实验大家直观感受下吧~

这是某个Java实现的求解VRP类问题的算法代码,两个算法都达到了同样的效果,只不过绿色曲线对应的算法在计算过程中去除了相关冗余,可以看到运行时间直线下降。根据我们的统计,消除冗余计算后可使计算时间降低约83%,对于工业化生产而言,提升哪怕一个小数点都能带来巨大的收益,何止是83个百分点呢。怎么说呢,这简直是A small step forward,one step civiliazation

三、放码过来?

不要一上来就是写代码,不加思考就上手写代码,你只会搓一坨屎山出来,自己坑害自己。开始写代码之前一定要构思好算法的整体架构,解的表示方式,如何快速得到邻居解等。建议是思考的时间一定要占总时间的一半以上。

其实思路清晰写代码是非常快的,比如每次在写代码的时候我都会先写好注释,比如:

//1. 先获取所有可行点的信息

//2. 对点按照成本进行排序

//3. 贪心将各个点插入到解中

然后写的时候我只需要按照这个思路往下走就可以了,这就跟你写小学生作文一样,起床刷牙到公园看鲸鱼,一定要思路清晰。

四、邻居解如何计算?

到了今天的核心问题,我们都知道,邻域搜索过程中,邻居解与当前解相比往往只有细微的变化,因此迭代过程中绝大部分变量不需要重新计算,消除了冗余计算,可大大提高邻域搜索效率,降低运行时间。听不懂吗?没关系,我举例子,慢慢给你讲解。

下面是一个VRP问题(没有TW哦)的一个初始解

S_1

:

为了方便表示我们用

C(x)

表示x的cost吧,其中x可以为一个解、解中的一条路径。

c_{ij}

表示边<i,j>的距离。对于初始解,计算它的cost,只能是从头到尾挨个遍历一下了。因此:

C(S_1) = C(r_1) + C(r_2) + C(r_3) + C(r_4)

其中各条路径的cost又可以表示为:

C(r_1) = c_{0,6} +c_{6,4}+ ... + c_{8,0}
......
C(r_4) = c_{0,14} +c_{14,18}+ ... + c_{25,0}

因此最后解的计算方式为:

C(S_1) = c_{0,6} +c_{6,4}+ ... +c_{25,0}

为了方便比较我们将这种计算解cost的方式称为Algorithm1

算一下,Algorithm1在计算时遍历了所有的客户点,对于N个客户点的解而已,算法的复杂度为O(N),嗯!还不赖。

好了现在解

S_1

通过一个move,生成了一个邻居解

S_2

可以看到该move就是将客户19从路径

r_2

中移除,并重新relocate到路径

r_3

中客户1后面。

现在生成了一个邻居解,得知道这个邻居解是好还是坏对吧,那么我们得比较

C(S_1)

C(S_2)

的大小吧。前面我们通过Algorithm1算出了

C(S_1)

的大小,那么现在的问题就是

C(S_2)

怎么计算了。敲黑板的重点来了。

利用Algorithm1

S_2

重新进行计算,时间复杂度前面分析过了,为

O(n)

优化一下

观察上面的解

S_1

S_2

,可以发现一个邻域搜索算法非常显著的特点:邻居解

S_2

相比较当前解

S_1

而言,只发生了微小的改变,整个解中有4条路径,只有两条路径发生了改变,因此

S_2

的cost可以由原来计算好的一些结果进行换算:

C(S_2) = C(S_1) - C(r_2) - C(r_3) + C(r'_2) + C(r'_3)

在上面的式子中,只有

C(r'_2)

C(r'_3)

是需要重新算的:

C(r'_2) = c_{0,15} +c_{15,12}+ ... + c_{7,0}
C(r'_3) = c_{0,32} +c_{32,13}+ ... + c_{5,0}

这样一来,只需要计算变动的路径即可,就不用重新计算所有路径了。大大降低了邻居解的计算时间复杂度。

进一步优化

细细观察一下

r'_2

r'_3

我们发现,路径中发生变动的边似乎也不是很多啊。我给大家标一下:

S_1

中发生变动的边我已经用红色实线标出来了,

S_2

中发生变动的边我用红色虚线标出来,那么

C(r'_2)

C(r'_3)

是不是可以用之前计算好的

C(r_2)

C(r_3)

得出来呢?当然可以啦,我们只需减去原来的边,再加上新的边就可以了。

C(r'_2) = C(r_2) - c_{11,19}-c_{19,17}+c_{11,17}
C(r'_3) = C(r_3) - c_{1,2}+c_{1,19}+c_{19, 2}

我们将这两条式子带入下面的式子:

C(S_2) = C(S_1) - C(r_2) - C(r_3) + C(r'_2) + C(r'_3)

即可得到:

C(S_2) = C(S_1) - c_{11,19}-c_{19,17}+c_{11,17} - c_{1,2}+c_{1,19}+c_{19, 2}

这个时间复杂度为

O(1)

,OK。经过重重优化,将时间复杂度从原来的

O(n)

成功降到了

O(1)

可能大家对这个

O(n)

降到

O(1)

没什么感觉。我来给大家分析一下,在小规模问题,比如10个、20个节点这样可能还真没啥区别。但是别忘记了启发式算法是针对大规模的优化问题的,邻域搜索类算法的邻域规模往往是随着问题规模的增长而呈爆炸式增长的。比如说在一个100个节点的VRP算例中,对于exchange算子,交换任意两个客户,那么一个解所能形成的邻居解就有

C_{100}^{2}=4950

,大约为5000个邻居解。

  • 如果每个邻居解你都使用Algorithm1重新算一遍,那么大概要算5000*100=500000次。
  • 如果你用优化过的计算方法,只需要算5000*1=5000次。

这个差距有多大,大家动动屁股都知道了。当然了,这只是理论上的分析。实际上的差距和编程环境以及实现方式等都有很大关系,但是只要差距超过10倍以上,都是能很明显的感觉出来的。

五、小结

关于如果去除冗余,不是说一套方法通用的,需要根据算法工程师根据问题的特性,设计合适的解结构,再对邻域算子进行降冗余的思考与实现。降冗余的操作比较适合邻域搜索类的启发式算法,因为这类算法显著特点就是邻居解相比较当前解而言,变化非常细微。

当然了,这需要丰富的编程经验,所以大家有时间还是好好磨练下吧~当然了这次也会放出相应的学习代码,只需要在公众号回复【VRP去重】即可看到。

还有,写到这里,我突然想起大一发生的一件糗事,那时候大家统一穿着绿色的军装。我去上完厕所以后突然不知道自己属于哪个队伍了。于是当时被教官狠狠训了一顿。后来才知道,是三连。

本文分享自微信公众号 - 程序猿声(ProgramDream),作者:番茄鸡蛋炒饭

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-02

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何实现一个高效的启发式算法?(VRPTW篇)

    上一期大家的反馈还不错,希望小编多多写写这种类似心得的文章。刚好小编最近也要学新东西了,打算把之前学的东西都整理一下写写,希望给大家带来一点小小的帮助吧~所以今...

    短短的路走走停停
  • 如何实现一个KNN算法

    KNN算法,也称为K邻近算法,可以解决回归和分类问题,但解决分类问题才是它的优势。

    佛系编程人
  • 如何打造一个高效的研发团队

    互联网公司的成功很大一部分归结为人才储备,如何打造有活力、持续创新的研发团队,相信很多管理者都比较关心。

    用户7676729
  • 如何实现一个 3D 效果的魔方

    当我们遇到一个较难问题的时候,把它逐步分解,转化为我们熟悉的内容,问题就很容易得到解决。

    山月
  • 我发现了一个高效学习的新方法!

    在体验了公司新出的几个 约炮 交友产品后,我又开始学习了!学了一种非常新颖的读书方式,分享给大家。

    机智的程序员小熊
  • 如何做一个高效的前端开发工程师

    不知大家有没类似这样的经历:一天忙到晚,一会被PM叫去确认需求,一会被设计拉去确认UI是否能实现,一会又被测试叫去确认bug,然后貌似做了很多事,但好像工作进度...

    用户4962466
  • 如何做一个高效的前端开发工程师

    不知大家有没类似这样的经历:一天忙到晚,一会被PM叫去确认需求,一会被设计拉去确认UI是否能实现,一会又被测试叫去确认bug,然后貌似做了很多事,但好像工作进度...

    用户4962466
  • 算法图解:如何用两个栈实现一个队列?

    队列和栈是计算机中两个非常重要的数据结构,经过前面的学习(《队列》、《栈》)我们知道了它们各自的特点,队列是先进先出(FIFO)的,而栈是先进后出(FILO)的...

    Java中文社群-磊哥
  • 分布式集群如何实现高效的数据分布

    随着互联网的发展,用户产生的数据越来越多,企业面临着庞大数据的存储问题,目前市面上主流的分布式大数据文件系统,都是对数据切片打散,通过离散方法将数据散列在集群的...

    2020labs小助手

扫码关注云+社区

领取腾讯云代金券