程序猿聲

代碼黑科技的分享區(qū)

一、前言

今年開(kāi)年那會(huì)還在做一個(gè)課題的實(shí)驗(yàn),那時(shí)候想用large neighborhood search來(lái)做一個(gè)問(wèn)題,但是后來(lái)發(fā)現(xiàn)常規(guī)的一些repair、destroy算子效果并不是很好。后來(lái)才知道,large neighborhood search以及它的衍生算法,這類框架給人一種非常通用的感覺(jué),就是無(wú)論啥問(wèn)題都能往里面套。

往往的結(jié)果是套進(jìn)去效果也是一般。這也是很多剛?cè)胄械男』锇榻?jīng)常喜歡干的事吧,各種算法框架套一個(gè)問(wèn)題,發(fā)現(xiàn)結(jié)果不好了就感覺(jué)換下一個(gè)。最后復(fù)現(xiàn)了N多個(gè)算法發(fā)現(xiàn)依然no process,這時(shí)候就會(huì)懷疑人生了。其實(shí)要想取得好的performance,肯定還是要推導(dǎo)一些問(wèn)題特性,設(shè)計(jì)相應(yīng)的算子也好,鄰域結(jié)構(gòu)也好。

好了,回到正題。當(dāng)時(shí)我試了好幾個(gè)large neighborhood search算子,發(fā)現(xiàn)沒(méi)啥效果的時(shí)候,心里難受得很。那幾天晚上基本上是轉(zhuǎn)輾反側(cè),難以入眠,當(dāng)然了是在思考問(wèn)題。然后一個(gè)idea突然浮現(xiàn)在我的腦瓜子里,常規(guī)的repair算子難以在問(wèn)題中取得好的performance,是因?yàn)榧s束太多了,插入的時(shí)候很容易違背約束。

在不違背約束的條件下又難以提升解的質(zhì)量,我就想能不能插入的啥時(shí)候采取branch and bound。遍歷所有的可能插入方式,然后記錄過(guò)程中的一個(gè)upper bound用來(lái)刪掉一些分支。

感覺(jué)是有搞頭的,后來(lái)想想,這個(gè)branch的方法以及bound的方法似乎是有點(diǎn)難設(shè)計(jì)。然后又?jǐn)R置了幾天,最后沒(méi)進(jìn)展的時(shí)候突然找了一篇論文,是好多年前的一篇文章了。里面詳細(xì)講解了large neighborhood search中如何利用branch and bound進(jìn)行插入,后來(lái)實(shí)現(xiàn)了以下感覺(jué)還可以。感覺(jué)這個(gè)方法還是有一定的參考價(jià)值的,因此今天就來(lái)寫(xiě)寫(xiě)(其實(shí)當(dāng)時(shí)就想寫(xiě)了,只不過(guò)一直拖到了現(xiàn)在。。。)

二、large neighborhood search

關(guān)于這個(gè)算法,我在此前的推文中已經(jīng)有過(guò)相應(yīng)的介紹,詳情小伙伴們可以戳這篇的鏈接進(jìn)行查看:

自適應(yīng)大鄰域搜索(Adaptive Large Neighborhood Search)入門到精通超詳細(xì)解析-概念篇

我把其中的一段話摘出來(lái):

大多數(shù)鄰域搜索算法都明確定義它們的鄰域。在LNS中,鄰域是由和方法隱式定義的。方法會(huì)破壞當(dāng)前解的一部分,而后方法會(huì)對(duì)被破壞的解進(jìn)行重建。方法通常包含隨機(jī)性的元素,以便在每次調(diào)用方法時(shí)破壞解的不同部分。

那么,解的鄰域就可以定義為:首先通過(guò)利用方法破壞解,然后利用方法重建解,從而得到的一系列解的集合。LNS算法框架如下:

有關(guān)該算法更詳細(xì)的介紹可以參考Handbook Of Metaheuristics這本書(shū)2019版本中的Chapter 4Large Neighborhood Search(David Pisinger and Stefan Ropke),文末我會(huì)放出下載的鏈接。

關(guān)于destroy算子呢,有很多種,比如隨機(jī)移除幾個(gè)點(diǎn),貪心移除一些比較差的點(diǎn),或者基于后悔值排序移除一些點(diǎn)等,這里我給出文獻(xiàn)中的一種移除方式,Shaw (1998)提出的基于進(jìn)行移除:

假設(shè)需要從解中所有的移除個(gè),它首先隨機(jī)選擇一個(gè)放進(jìn)(已經(jīng)移除的列表)(第1行),然后迭代地(3–6行)移除剩下的個(gè)。每次這樣的迭代都會(huì)先從中隨機(jī)選擇一個(gè),并根據(jù)相關(guān)標(biāo)準(zhǔn)對(duì)其余未移除的進(jìn)行排序(第3-4行)。在第5行中計(jì)算要插入的新的下標(biāo),然后插入到中(第6行),直到迭代結(jié)束。關(guān)聯(lián)度的定義如Shaw(1998)所述:

其中,customer 和 在不同的路徑中時(shí),否則為0。

三、branch and bound

上面講了Large Neighborhood Search以及介紹了一個(gè)方法,下面就是重頭戲,如何利用branch and bound進(jìn)行插入了。

3．1 branch

其實(shí)插入的分支方式還是挺好設(shè)計(jì)的,這玩意兒呢我將也比較難講清楚,我就畫(huà)圖好了,還是基于VRP問(wèn)題示例,其他問(wèn)題類似,假如我們現(xiàn)在有這樣一個(gè)解:

為了演示我就不畫(huà)太多點(diǎn)太多路徑了,免得大家看得心累。

紅色箭頭就是能夠插入的位置�，F(xiàn)在,假如我們插入(由于branch and bound是需要遍歷所有可能的插入組合,因此先插入哪個(gè)后插入哪個(gè)都是可以的,但是分支定界的速度可能會(huì)受到很大的影響,這個(gè)咱們暫時(shí)不討論):

為了讓大家看得更加清楚,我把的位置用粉紅色給標(biāo)記出來(lái)了,一共有3條分支,有個(gè)候選的位置就有多少條分支。

現(xiàn)在,還剩下,插入的時(shí)候,我們需要繼續(xù)進(jìn)行分支:

55～畫(huà)分支樹(shù)真是畫(huà)死我啦(大家一定要給個(gè)贊,點(diǎn)個(gè)在看呀～),可以看到,最后每條路徑就是一個(gè)完成的解。在兩個(gè)點(diǎn)的插入兩個(gè)點(diǎn)最后分支完成的居然有12個(gè)!!!大家可以自行腦補(bǔ)下,在90個(gè)點(diǎn)的中插入10個(gè)點(diǎn)最終形成的分支會(huì)有多少。毫無(wú)疑問(wèn)會(huì)很多很多,多到你無(wú)法想象。下面是DFS搜索分支樹(shù)的過(guò)程:

如果要插入的客戶組為空,則可以認(rèn)為所有客戶已經(jīng)插入到solution中,形成了一個(gè),因此判斷找到的一個(gè)upper bound是否比最優(yōu)的upper bound還要好,是的話就對(duì)upper bound進(jìn)行更新。否則,它會(huì)選擇插入效果最好的客戶,這會(huì)使目標(biāo)函數(shù)下降得最大(Shaw 1998中也使用了這種啟發(fā)式方法)。然后,對(duì)所有插入客戶后形成的分支按照l(shuí)ower bound進(jìn)行排序,從lower bound低的分支開(kāi)始繼續(xù)往下分支(可以算是一種加速的策略)。同樣,請(qǐng)注意,該算法僅探索其lower bound比upper bound更好的分支。

3．2 bound

開(kāi)始之前大家想想bound的難點(diǎn)在哪里呢?首先想想bound中最重要的兩個(gè)界:upper bound和lower bound:

lower bound是指搜索過(guò)程中一個(gè)partial solution(比如上圖插入后形成的3個(gè))的目標(biāo)值,因?yàn)椴⒉荒芩阃暾�的一個(gè)解,繼續(xù)往下的時(shí)候只可能增加(最小化問(wèn)題)或者減少(最大化問(wèn)題),因此它的意思是說(shuō)當(dāng)前支路的最終形成解的目標(biāo)值下界(最終目標(biāo)值不可能比這個(gè)lower bound更好)。upper bound是指搜索過(guò)程中找到的一個(gè)feasible solution(比如上圖插入后形成的12個(gè)中滿足所有約束的就是)的目標(biāo)值,如果存在某支路的lower bound比upper bound還要差,那么該支路顯然是沒(méi)有繼續(xù)往下的必要了,可以剪去。

顯然可以使用LNS在destroy之前的解的目標(biāo)值作為upper bound,因?yàn)槲覀兛偸瞧谕�找到比�?dāng)前解更好的解,才會(huì)去進(jìn)行destroy和repair。現(xiàn)在的問(wèn)題是如何對(duì)一個(gè)的lower bound應(yīng)該怎樣計(jì)算。下面講講幾種思路:

(1) 文獻(xiàn)中給出的思路,利用最小生成樹(shù):

這個(gè)方案我試了,但是找到的lower bound實(shí)在是太低了,這個(gè)lower bound只考慮了距離因素,但問(wèn)題中往往還存在時(shí)間窗等約束。因此這個(gè)方法在我當(dāng)時(shí)做的問(wèn)題中只能說(shuō)聊勝于無(wú)。

(2) 按照greedy的方法將所有未插入的Customer插入到他們最好的位置上,形成一個(gè),然后該的目標(biāo)值作為lower bound。

但是這個(gè)lower bound是有缺陷的,因?yàn)楹茈y保證不會(huì)錯(cuò)過(guò)某些比較有潛力的分支。

(3) 直接利用當(dāng)前的的目標(biāo)值作為lower bound,也比較合理。但是該值往往太低了,這可能會(huì)導(dǎo)致要遍歷更多的分支,消耗更多時(shí)間。

以上就是一些思路,至于有沒(méi)有更好的bound方法,我后面也沒(méi)有往下深究了。當(dāng)時(shí)實(shí)現(xiàn)出來(lái)以后效果是有的,就是時(shí)間太長(zhǎng)了,然后也放棄了。

當(dāng)然這篇paper后面也給了一個(gè)利用LDS進(jìn)行搜索以加快算法的速度,這里就不展開(kāi)了,有空再說(shuō)。感興趣的小伙伴可以去看看原paper,我會(huì)放到留言區(qū)的。

四、代碼環(huán)節(jié)

代碼實(shí)現(xiàn)放兩個(gè),一個(gè)是我當(dāng)時(shí)寫(xiě)的一個(gè)DFSEXPLORER,采用的是思路2作為bound的,(代碼僅僅提供思路)如下:

private void DFSEXPLORER5(LNSSolution node, LNSSolution upperBound, int dep) {
 Queue

第二個(gè)是GitHub上找到的一個(gè)人復(fù)現(xiàn)的,我已經(jīng)fork到我的倉(cāng)庫(kù)中了:

https://github．com/dengfaheng/vrp

這個(gè)思路bound的思路呢沒(méi)有按照paper中的,應(yīng)該還是用的貪心進(jìn)行bound�？雌饋�(lái)在R和RC系列的算例中效果其實(shí)也一般般,因?yàn)橛昧薒DS吧可能。下面是運(yùn)行的c1_2_1的截圖:

導(dǎo)入idea或者eclipse后等他安裝完依賴,運(yùn)行下面的文件即可,更改算例的位置如圖所示:

這個(gè)思路是直到借鑒的,大家在用LNS的時(shí)候也可以想想有什么更好的bound方法。

好了,這就是今天的分享了�？赡苡泻芏嗟胤�?jīng)]寫(xiě)的很明白,因?yàn)樯婕暗狞c(diǎn)太多了我也只能講個(gè)大概提供一個(gè)思路而已。大家來(lái)了就幫我點(diǎn)個(gè)在看再走吧～