如何實(shí)現(xiàn)一個(gè)高效的啟發(fā)式算法？
一、前言
小伙伴們好，說(shuō)起來(lái)已經(jīng)好久好久好久沒(méi)見了呢！之前一直忙著做其他事情去了（泛指學(xué)習(xí)一類），公眾號(hào)已經(jīng)落下好久好久了。今天來(lái)寫點(diǎn)好玩的東西。
說(shuō)起來(lái)，小編似乎就是做啟發(fā)式算法起家的。當(dāng)時(shí)記得老師是這么跟我說(shuō)的，啟發(fā)式算法這東西很簡(jiǎn)單，你不需要基礎(chǔ)，有高中基礎(chǔ)就夠了（其實(shí)他想說(shuō)的是初中……）。
后來(lái)小編一直在學(xué)這個(gè)東西，做了三四年了，用啟發(fā)式算法做過(guò)的大大小小的project已經(jīng)不記得有多少了，所以還算得上有一點(diǎn)點(diǎn)經(jīng)驗(yàn)。因此今天就來(lái)寫寫，怎樣實(shí)現(xiàn)一個(gè)比較高效的啟發(fā)式算法吧~
二、何為高效？
說(shuō)到這個(gè)詞，相信大家一定不陌生。高效意思就是達(dá)到相同效果或者更好的效果時(shí)，使用的時(shí)間更短，所需要的資源更少。就拿小編來(lái)說(shuō)，由于小編特別笨，學(xué)一樣?xùn)|西需要花一周的時(shí)間，而群里的小伙伴只需要一天的時(shí)間就能學(xué)會(huì)。那么這位小伙伴是要比我高效的。
同樣的對(duì)于一個(gè)啟發(fā)式算法而言，不同人實(shí)現(xiàn)出來(lái)，即使是使用同一編程平臺(tái)達(dá)到同樣的效果，運(yùn)行時(shí)間也會(huì)千差萬(wàn)別，相差幾倍甚至幾十倍。這樣說(shuō)出來(lái)大家可能還沒(méi)啥感覺(jué)，那么放一下我們之前做過(guò)的一些數(shù)值實(shí)驗(yàn)大家直觀感受下吧~
這是某個(gè)Java實(shí)現(xiàn)的求解VRP類問(wèn)題的算法代碼，兩個(gè)算法都達(dá)到了同樣的效果，只不過(guò)綠色曲線對(duì)應(yīng)的算法在計(jì)算過(guò)程中去除了相關(guān)冗余，可以看到運(yùn)行時(shí)間直線下降。根據(jù)我們的統(tǒng)計(jì)，消除冗余計(jì)算后可使計(jì)算時(shí)間降低約83%，對(duì)于工業(yè)化生產(chǎn)而言，提升哪怕一個(gè)小數(shù)點(diǎn)都能帶來(lái)巨大的收益，何止是83個(gè)百分點(diǎn)呢。怎么說(shuō)呢，這簡(jiǎn)直是A small step forward，one step civiliazation。
三、放碼過(guò)來(lái)？
不要一上來(lái)就是寫代碼，不加思考就上手寫代碼，你只會(huì)搓一坨屎山出來(lái)，自己坑害自己。開始寫代碼之前一定要構(gòu)思好算法的整體架構(gòu)，解的表示方式，如何快速得到鄰居解等。建議是思考的時(shí)間一定要占總時(shí)間的一半以上。
其實(shí)思路清晰寫代碼是非常快的，比如每次在寫代碼的時(shí)候我都會(huì)先寫好注釋，比如：
//1.?先獲取所有可行點(diǎn)的信息
//2.?對(duì)點(diǎn)按照成本進(jìn)行排序
//3.?貪心將各個(gè)點(diǎn)插入到解中
然后寫的時(shí)候我只需要按照這個(gè)思路往下走就可以了，這就跟你寫小學(xué)生作文一樣，起床刷牙到公園看鯨魚，一定要思路清晰。
四、鄰居解如何計(jì)算？
到了今天的核心問(wèn)題，我們都知道，鄰域搜索過(guò)程中，鄰居解與當(dāng)前解相比往往只有細(xì)微的變化，因此迭代過(guò)程中絕大部分變量不需要重新計(jì)算，消除了冗余計(jì)算，可大大提高鄰域搜索效率，降低運(yùn)行時(shí)間。聽不懂嗎？沒(méi)關(guān)系，我舉例子，慢慢給你講解。
下面是一個(gè)VRP問(wèn)題（沒(méi)有TW哦）的一個(gè)初始解:
為了方便表示我們用表示x的cost吧，其中x可以為一個(gè)解、解中的一條路徑。表示邊
其中各條路徑的cost又可以表示為：
因此最后解的計(jì)算方式為：
為了方便比較我們將這種計(jì)算解cost的方式稱為
Algorithm1。
算一下，Algorithm1在計(jì)算時(shí)遍歷了所有的客戶點(diǎn)，對(duì)于N個(gè)客戶點(diǎn)的解而已，算法的復(fù)雜度為O(N)，嗯！還不賴。
好了現(xiàn)在解通過(guò)一個(gè)move，生成了一個(gè)鄰居解：
可以看到該move就是將客戶19從路徑中移除，并重新relocate到路徑中客戶1后面。
現(xiàn)在生成了一個(gè)鄰居解，得知道這個(gè)鄰居解是好還是壞對(duì)吧，那么我們得比較和的大小吧。前面我們通過(guò)Algorithm1算出了的大小，那么現(xiàn)在的問(wèn)題就是怎么計(jì)算了。敲黑板的重點(diǎn)來(lái)了。
利用Algorithm1對(duì)重新進(jìn)行計(jì)算，時(shí)間復(fù)雜度前面分析過(guò)了，為。
優(yōu)化一下
觀察上面的解和，可以發(fā)現(xiàn)一個(gè)鄰域搜索算法非常顯著的特點(diǎn)：鄰居解相比較當(dāng)前解而言，只發(fā)生了微小的改變，整個(gè)解中有4條路徑，只有兩條路徑發(fā)生了改變，因此的cost可以由原來(lái)計(jì)算好的一些結(jié)果進(jìn)行換算：
在上面的式子中，只有和是需要重新算的：
這樣一來(lái)，只需要計(jì)算變動(dòng)的路徑即可，就不用重新計(jì)算所有路徑了。大大降低了鄰居解的計(jì)算時(shí)間復(fù)雜度。
進(jìn)一步優(yōu)化
細(xì)細(xì)觀察一下和我們發(fā)現(xiàn)，路徑中發(fā)生變動(dòng)的邊似乎也不是很多啊。我給大家標(biāo)一下：
中發(fā)生變動(dòng)的邊我已經(jīng)用紅色實(shí)線標(biāo)出來(lái)了，中發(fā)生變動(dòng)的邊我用紅色虛線標(biāo)出來(lái)，那么和是不是可以用之前計(jì)算好的和得出來(lái)呢？當(dāng)然可以啦，我們只需減去原來(lái)的邊，再加上新的邊就可以了。
我們將這兩條式子帶入下面的式子：
即可得到：
這個(gè)時(shí)間復(fù)雜度為，OK。經(jīng)過(guò)重重優(yōu)化，將時(shí)間復(fù)雜度從原來(lái)的成功降到了。
可能大家對(duì)這個(gè)降到沒(méi)什么感覺(jué)。我來(lái)給大家分析一下，在小規(guī)模問(wèn)題，比如10個(gè)、20個(gè)節(jié)點(diǎn)這樣可能還真沒(méi)啥區(qū)別。但是別忘記了啟發(fā)式算法是針對(duì)大規(guī)模的優(yōu)化問(wèn)題的，鄰域搜索類算法的鄰域規(guī)模往往是隨著問(wèn)題規(guī)模的增長(zhǎng)而呈爆炸式增長(zhǎng)的。比如說(shuō)在一個(gè)100個(gè)節(jié)點(diǎn)的VRP算例中，對(duì)于exchange算子，交換任意兩個(gè)客戶，那么一個(gè)解所能形成的鄰居解就有，大約為5000個(gè)鄰居解。
如果每個(gè)鄰居解你都使用 Algorithm1重新算一遍，那么大概要算5000*100=500000次。如果你用優(yōu)化過(guò)的計(jì)算方法，只需要算5000*1=5000次。
這個(gè)差距有多大，大家動(dòng)動(dòng)屁股都知道了。當(dāng)然了，這只是理論上的分析。實(shí)際上的差距和編程環(huán)境以及實(shí)現(xiàn)方式等都有很大關(guān)系，但是只要差距超過(guò)10倍以上，都是能很明顯的感覺(jué)出來(lái)的。
五、小結(jié)
關(guān)于如果去除冗余，不是說(shuō)一套方法通用的，需要根據(jù)算法工程師根據(jù)問(wèn)題的特性，設(shè)計(jì)合適的解結(jié)構(gòu)，再對(duì)鄰域算子進(jìn)行降冗余的思考與實(shí)現(xiàn)。降冗余的操作比較適合鄰域搜索類的啟發(fā)式算法，因?yàn)檫@類算法顯著特點(diǎn)就是鄰居解相比較當(dāng)前解而言，變化非常細(xì)微。
當(dāng)然了，這需要豐富的編程經(jīng)驗(yàn)，所以大家有時(shí)間還是好好磨練下吧~當(dāng)然了這次也會(huì)放出相應(yīng)的學(xué)習(xí)代碼，只需要在公眾號(hào)回復(fù)【VRP去重】即可看到。
還有，寫到這里，我突然想起大一發(fā)生的一件糗事，那時(shí)候大家統(tǒng)一穿著綠色的軍裝。我去上完廁所以后突然不知道自己屬于哪個(gè)隊(duì)伍了。于是當(dāng)時(shí)被教官狠狠訓(xùn)了一頓。后來(lái)才知道，是三連。
