如何实现一个高效的启发式算法？
共 2699字，需浏览 6分钟
·
2020-10-03 03:29
一、前言
小伙伴们好，说起来已经好久好久好久没见了呢！之前一直忙着做其他事情去了（泛指学习一类），公众号已经落下好久好久了。今天来写点好玩的东西。
说起来，小编似乎就是做启发式算法起家的。当时记得老师是这么跟我说的，启发式算法这东西很简单，你不需要基础，有高中基础就够了（其实他想说的是初中……）。
后来小编一直在学这个东西，做了三四年了，用启发式算法做过的大大小小的project已经不记得有多少了，所以还算得上有一点点经验。因此今天就来写写，怎样实现一个比较高效的启发式算法吧~
二、何为高效？
说到这个词，相信大家一定不陌生。高效意思就是达到相同效果或者更好的效果时，使用的时间更短，所需要的资源更少。就拿小编来说，由于小编特别笨，学一样东西需要花一周的时间，而群里的小伙伴只需要一天的时间就能学会。那么这位小伙伴是要比我高效的。
同样的对于一个启发式算法而言，不同人实现出来，即使是使用同一编程平台达到同样的效果，运行时间也会千差万别，相差几倍甚至几十倍。这样说出来大家可能还没啥感觉，那么放一下我们之前做过的一些数值实验大家直观感受下吧~
这是某个Java实现的求解VRP类问题的算法代码，两个算法都达到了同样的效果，只不过绿色曲线对应的算法在计算过程中去除了相关冗余，可以看到运行时间直线下降。根据我们的统计，消除冗余计算后可使计算时间降低约83%，对于工业化生产而言，提升哪怕一个小数点都能带来巨大的收益，何止是83个百分点呢。怎么说呢，这简直是A small step forward，one step civiliazation。
三、放码过来？
不要一上来就是写代码，不加思考就上手写代码，你只会搓一坨屎山出来，自己坑害自己。开始写代码之前一定要构思好算法的整体架构，解的表示方式，如何快速得到邻居解等。建议是思考的时间一定要占总时间的一半以上。
其实思路清晰写代码是非常快的，比如每次在写代码的时候我都会先写好注释，比如：
//1. 先获取所有可行点的信息
//2. 对点按照成本进行排序
//3. 贪心将各个点插入到解中
然后写的时候我只需要按照这个思路往下走就可以了，这就跟你写小学生作文一样，起床刷牙到公园看鲸鱼，一定要思路清晰。
四、邻居解如何计算？
到了今天的核心问题，我们都知道，邻域搜索过程中，邻居解与当前解相比往往只有细微的变化，因此迭代过程中绝大部分变量不需要重新计算，消除了冗余计算，可大大提高邻域搜索效率，降低运行时间。听不懂吗？没关系，我举例子，慢慢给你讲解。
下面是一个VRP问题（没有TW哦）的一个初始解:
为了方便表示我们用表示x的cost吧，其中x可以为一个解、解中的一条路径。表示边
其中各条路径的cost又可以表示为：
因此最后解的计算方式为：
为了方便比较我们将这种计算解cost的方式称为
Algorithm1。
算一下，Algorithm1在计算时遍历了所有的客户点，对于N个客户点的解而已，算法的复杂度为O(N)，嗯！还不赖。
好了现在解通过一个move，生成了一个邻居解：
可以看到该move就是将客户19从路径中移除，并重新relocate到路径中客户1后面。
现在生成了一个邻居解，得知道这个邻居解是好还是坏对吧，那么我们得比较和的大小吧。前面我们通过Algorithm1算出了的大小，那么现在的问题就是怎么计算了。敲黑板的重点来了。
利用Algorithm1对重新进行计算，时间复杂度前面分析过了，为。
优化一下
观察上面的解和，可以发现一个邻域搜索算法非常显著的特点：邻居解相比较当前解而言，只发生了微小的改变，整个解中有4条路径，只有两条路径发生了改变，因此的cost可以由原来计算好的一些结果进行换算：
在上面的式子中，只有和是需要重新算的：
这样一来，只需要计算变动的路径即可，就不用重新计算所有路径了。大大降低了邻居解的计算时间复杂度。
进一步优化
细细观察一下和我们发现，路径中发生变动的边似乎也不是很多啊。我给大家标一下：
中发生变动的边我已经用红色实线标出来了，中发生变动的边我用红色虚线标出来，那么和是不是可以用之前计算好的和得出来呢？当然可以啦，我们只需减去原来的边，再加上新的边就可以了。
我们将这两条式子带入下面的式子：
即可得到：
这个时间复杂度为，OK。经过重重优化，将时间复杂度从原来的成功降到了。
可能大家对这个降到没什么感觉。我来给大家分析一下，在小规模问题，比如10个、20个节点这样可能还真没啥区别。但是别忘记了启发式算法是针对大规模的优化问题的，邻域搜索类算法的邻域规模往往是随着问题规模的增长而呈爆炸式增长的。比如说在一个100个节点的VRP算例中，对于exchange算子，交换任意两个客户，那么一个解所能形成的邻居解就有，大约为5000个邻居解。
如果每个邻居解你都使用 Algorithm1重新算一遍，那么大概要算5000*100=500000次。如果你用优化过的计算方法，只需要算5000*1=5000次。
这个差距有多大，大家动动屁股都知道了。当然了，这只是理论上的分析。实际上的差距和编程环境以及实现方式等都有很大关系，但是只要差距超过10倍以上，都是能很明显的感觉出来的。
五、小结
关于如果去除冗余，不是说一套方法通用的，需要根据算法工程师根据问题的特性，设计合适的解结构，再对邻域算子进行降冗余的思考与实现。降冗余的操作比较适合邻域搜索类的启发式算法，因为这类算法显著特点就是邻居解相比较当前解而言，变化非常细微。
当然了，这需要丰富的编程经验，所以大家有时间还是好好磨练下吧~当然了这次也会放出相应的学习代码，只需要在公众号回复【VRP去重】即可看到。
还有，写到这里，我突然想起大一发生的一件糗事，那时候大家统一穿着绿色的军装。我去上完厕所以后突然不知道自己属于哪个队伍了。于是当时被教官狠狠训了一顿。后来才知道，是三连。
