什么是算法?從枚舉到貪心再到啟發(fā)式(下)-終于有人把鄰域搜索講...
前言在上一篇文章中我們聊了枚舉算法和貪心算法并進行了詳細對比讓大家了解了這兩個算法的相關特點相關的傳送門如下：
什么是算法？從枚舉到貪心再到啟發(fā)式（上）
今天咱來聊聊啟發(fā)式算法吧至于什么是啟發(fā)式算法為什么有了枚舉和貪心還要啟發(fā)式算法
看完這篇文章，相信你就能找到答案哦
什么是啟發(fā)式算法？
在上一篇文章中我們對比分析了枚舉法和貪心法的特點枚舉法呢，雖然能求得問題的最優(yōu)解，但是所花的時間是在是太太太大了。
貪心法呢，雖然能在極短的時間內找到一個尚且過得去的解，但是呢，有時候求得的解是在是太low啦。雖然在上次的文章中大家沒有很明顯看到這一點，因為0-1背包問題還算比較簡單，但是在一些復雜的組合優(yōu)化問題比如vrp問題中，貪心法的弊端就凸顯出來了。
所以啊枚舉法時間太長沒法用??貪心質量太差人們就需要另辟蹊徑找到一條既能夠得到一個比較優(yōu)質的解又能將求解資源控制在一定范圍內的社會主義道路這時候啟發(fā)式算法就應運而生啦
說白了，啟發(fā)式算法就是在一個合理的求解資源范圍內（合理的時間，合理的內存開銷等）求得一個較為滿意的解。
該解毫無疑問，是要優(yōu)于或等于貪心解，有可能達到枚舉法求得的最優(yōu)解。這是怎么做到的呢？下面讓我慢慢道來
注：啟發(fā)式算法目前主要包括鄰域搜索和群體仿生兩大類，本篇主要介紹鄰域搜索類。同時鄰域搜索類會涉及很多概念，我盡量用大白話的語言向大家闡述。因為啟發(fā)式算法強調的是一個應用，即你拿到問題能設計相應的算法并求解出來。概念只是輔助我們理解這個過程而已。
先從局部搜索說起
大家平常找東西都是怎么找的呢？按照正常人的思路，丟了東西以后我們往往都會先確定一個范圍，然后沿著確定的范圍進行搜索。這其實就有種局部搜索的味道了。
不過在開始局部搜索前我們先來了解一個概念解空間問題的解空間是指所有該問題的解的集合，包括可行解和不可行解。對于算法而言，其本質就是一個搜索尋優(yōu)的過程。
在哪里搜？
當然是在解空間里面搜啦。
一開始人們的做法是遍歷整個解空間進行全局搜索，然后找出問題的最優(yōu)解。
但是漸漸地人們發(fā)現，當問題規(guī)模增大時，其解空間就會變得很大很大。全局搜索需要的時間和資源是無法接受的。
這就像你去華中科技大學游玩的時候丟了身份證，別說是對整個洪山區(qū)展開地毯式搜索，光是對我科展開地毯式搜索都夠嗆。
所以，為了解決這個問題，人們就想出了另一種方式：局部搜索。說白了就是咱不完全遍歷解空間了，只挑一部分出來進行遍歷，這樣就可以大大降低搜索需要的資源，說不定碰巧挑出來的局部中還含有最優(yōu)解呢。
如上圖，局部搜索時如果只搜索藍色虛線左下的區(qū)域，那么就有可能找到最優(yōu)解。為了提高局部搜索的質量，大部分局部搜索算法都會在搜索的時候不斷地抓取多個區(qū)域進行搜索，直到滿足算法終止條件。領域搜索
相信大家肯定存在一個疑問局部搜索是怎么挑選“局部”的？別急，看完本節(jié)鄰域搜索的內容你就understand了
鄰域搜索是基于“鄰域”的一類啟發(fā)式算法，本質還是屬于局部搜索的范疇。在此之前我們還是介紹必要的一些概念。“同學”、“家人”、“鄰居”這些概念想必大家已經非常熟悉了。下面我們來看一張有趣的圖片：
圖1 生活上的“鄰域”舉例你，通過血緣關系，可以找到你的家人集合（包括你爸爸、媽媽、爺爺奶奶等）；你家，通過地里位置上的距離遠近，可以找到你家的鄰居集合（隔壁的、對面的、同樓層的）；你，通過判斷與你是否同一班級，可以找到你同學的集合（同班的就是你同學）。
大家發(fā)現沒有，上面的示例都是通過某種關聯（血緣關系、距離遠近等），將一個基準點（比如你、你家）映射到了一個集合（比如你的家人、你家的鄰居）上面。
好了我們現在再來看一張圖：
圖2 啟發(fā)式算法中的鄰域生成上面就是生成一個解的鄰域的過程，怎樣，是不是跟剛剛的幾個例子（圖1）有著異曲同工之妙呢？
鄰域生成的過程（圖2）其實也是一樣的，只不過是使用了更專業(yè)的概念而已。下面我們就來解釋下這些概念的含義吧。
概念介紹
鄰域其實就是在鄰域結構定義下的解的集合，比如在圖2中s1-s6等構成的集合就是s的鄰域。它是一個相對的概念，即鄰域肯定是基于某個解產生的，比如當前解s的鄰域，最優(yōu)解s_b的鄰域等。鄰居解是鄰域內某個解的稱呼。比如在圖2中，解s1-s6及其該鄰域中任意一個解都可以稱為解s的鄰居解。很好理解對吧~
鄰域結構定義了一個解的鄰域，就像圖1中血緣關系定義了你的家人集合一樣?？赡艽蠹覍ι钪械睦佣加幸粋€比較感性的認識，但對于啟發(fā)式中的就覺得比較抽象。
下面我再舉一個簡單的例子
對于一個背包問題的解s_bp = 11010，它的各個位上對應的值如下：
現在定義一個鄰域結構：交換任意兩位。那么解s_bp能夠形成的鄰居解就有
個。比如交換第1、第二位上的兩個1，得到11010；交換第1、第3位上的1和0，得到01110……等等。最終鄰域生成如下圖所示：
鄰域結構的設計在啟發(fā)式算法中非常重要，它直接決定了搜索的范圍，對最終的搜索結構有著重要的影響。其實，按照小編的經驗來講，鄰域結構的設計直接決定了最終結果質量的好壞。
當然這只是我的一些個人經驗，畢竟啟發(fā)式算法這東西不像精確式算法那樣具有很強的理論性，它更多注重的是應用，而應用就和經驗掛鉤了。所以一千個讀者有一千個哈姆雷特也不足為奇。
搜索過程
此前我們說過，鄰域搜索本質還是一個局部搜索的過程，事實上，它就是通過鄰域搜索進行局部探優(yōu)的，并且往往是多個“局部區(qū)域”進行搜索的，那么它是怎么確定搜索區(qū)域，又是怎么搜索的呢？下面我們一步一步給大家演示，看完相信大家就豁然開朗啦。
假如初始時我們有以下的解空間，其中綠色的是最優(yōu)解，如下（密恐福利）：
STEP1：初始解生成因為鄰域是基于一個解生成的，要想進行鄰域搜索，得先有一個解。所以首先要做的，當然是生成初始解啦。
一般初始解都采用構造法進行生成，比如隨機構造啦，之前講的貪心構造啦等，怎樣，是不是明白什么了呢。假如我們現在構造了一個初始解如下（它位于圖上方偏右）：
STEP2：鄰域生成
有了初始解，接下來就可以根據所定義的鄰域結構生成鄰域了：
STEP3：評價
現在鄰域有了，即要搜索的局部已經確定下來，我們是不是得進去找想要的東西了呀！評價就是在解的鄰域范圍內對鄰居解進行評價，然后選出需要的鄰居解進行“移動”。一般而言，有兩種評價的模式：
first improve：首次提升原則，即在鄰域內對解一一進行評價，一旦發(fā)現比當前解更優(yōu)的鄰居解立馬進行“移動”。
best improve：最優(yōu)提升原則，遍歷整個鄰域，找出最好的鄰居解進行“移動”。
STEP4：移動
何為移動呢？其實就是當前解變換到剛剛評價選擇的鄰居解的過程。初始解在其鄰域內找到了一個更好的鄰居解，然后移動過去了，如下圖所示：
STEP5：記錄全局最優(yōu)解
如果當前解比全局最優(yōu)解還要優(yōu)，那么更新全局最優(yōu)解。
然后接下來的過程大家應該都知道了，就是不斷重復STEP2-STEP5，直到滿足終止條件，最后輸出全局最優(yōu)解。如果算法足夠優(yōu)秀加上運氣buff的話，最后找到全局最優(yōu)是沒有問題的：
糟糕！陷入局部最優(yōu)了
這里有必要再講講上述搜索過程中:STEP3：評價這一步驟。當我們以first improve或者best improve對當前解的鄰居進行評價時，通常的做法是找到比當前解要好的鄰居解進行移動。但往往出現的情況是當前解的鄰域中并不存在更優(yōu)的鄰居解，如下圖：
初始解即生成在了一個局部最優(yōu)上面，這時候我們通常選擇鄰域中一個最好的鄰居解進行移動（盡管它比當前解還要差），如果不這樣做那就徹底陷入局部最優(yōu)了。
但是這樣做還有可能發(fā)生一個問題，它在兜兜轉轉移來移去結果又給移回去了：
這種情況也可以認為是陷入了局部最優(yōu)，通常的判斷條件就是經過多次鄰域搜索依舊沒有得到很好的improve。這種情況怎么辦呢？當然是“跳一跳”啦，如下：
這種“跳一跳”在啟發(fā)式中被稱為shake或者perturbation，中文稱之為擾動。是跳出局部最優(yōu)一個非常有效的做法。
通常的實現方式是利用隨機或者其他方式，對當前解進行重組，使其結構發(fā)生較大的改變。或者直接拋棄當前解，重新生成一個解進行后續(xù)的鄰域搜索。
隨機因素
隨機因素也是啟發(fā)式算法的一大特色了因為無法判斷搜索“區(qū)域”的好壞我們一般會隨機進行選擇搜索比如初始解的生成就有很多種可能性
如果你長得足夠好看的話，直接生成最優(yōu)解也不是不可能。每一個初始解對應的鄰域不同，搜索的路徑就不同。但通常經過優(yōu)化，各個初始解基本都能收斂到一個比較接近的水平。同時，shake也是一個隨機過程：
這也是為什么很多新手朋友喜歡找到我，張口就來：小編你的代碼有錯！每次結果都不一樣的。
小結
看了上述的過程，大家明白鄰域搜索和局部搜索這種千絲萬縷的關系了吧。最后放上一個基于鄰域的局部搜索算法偽代碼幫助大家更好理解
符號：
:第
次迭代的解。
:解的鄰域。
:最大迭代次數。
:執(zhí)行擾動的周期。
:對解
進行擾動。
基于鄰域的局部搜索算法偽代碼
實驗部分
上一篇文章中大家看到了貪心算法對于背包問題效果似乎很不錯
也能在較短的時間內找出接近最優(yōu)解的滿意解是不是就意味著我們可以拋棄其他算法擁抱貪心了呢？
當然不是0-1背包問題其實還是比較容易的，捏軟柿子其實說明不了什么。所以我們這次測試的問題改成了TSP問題，算例來源TSPLIB網站。關于算例文件和最優(yōu)解可以關注公眾號【程序猿聲】在資源下載一欄可以進行下載。
枚舉法是什么體驗？
對于TSP問題，如果用枚舉的話，大家想想全枚舉會有多少中組合呢？假如有N個城市，那么全枚舉就是N個城市的全排列，總數就是N的階乘N!。好了大家可能還是沒有什么概念，假如N=20（很小的規(guī)模了），那么其階乘的結果是2432902008176640000。用枚舉？簡直連想都不敢想。
貪心和啟發(fā)式
對于Greedy，其思想是隨機生成第一個城市，加入cityList，然后從剩下的依次找離cityList最后一個城市最近的放進去。參見最近鄰域法--nearest neighborhood search，傳送門：旅行商問題的近似算法之最近鄰法(Nearest Neighbor) C語言實現
protected?int[]?createGreedyRandomizedTour(int?dimension)?{
????int[]?newTour?=?new?int[dimension];
????Set?unvisitedCities?=?new?HashSet<>();
????for(int?i?=?1;?i?<=?dimension;?i++)
????????unvisitedCities.add(i);
????newTour[0]?=?rnd.nextInt(dimension)+1;
????unvisitedCities.remove(newTour[0]);
????for(int?i?=?1;?i?????????int?nearestCity?=?getNearestCity(newTour[i-1],?unvisitedCities);
????????newTour[i]?=?nearestCity;
????????unvisitedCities.remove(nearestCity);
????}
????return?newTour;
}
protected?int?getNearestCity(int?city,?Set?endpoints) ?{
????Iterator?it?=?endpoints.iterator();
????int?nearestCity?=?0;
????double?minDistance?=?Double.MAX_VALUE;
????while?(it.hasNext())?{
????????int?i?=?it.next();
//??????????boolean?containedInParents?=?(neighbours1[city?-?1][0]?==?i
//??????????????????||?neighbours1[city?-?1][1]?==?i
//??????????????????||?neighbours2[city?-?1][0]?==?i?||?neighbours2[city?-?1][1]?==?i);
????????if?(distanceTable.getDistanceBetween(city,?i)?????????????????)?{
????????????minDistance?=?distanceTable.getDistanceBetween(city,?i);
????????????nearestCity?=?i;
????????}
????}
????if?(nearestCity?!=?0)
????????return?nearestCity;
????else?//treats?the?case?that?all?possible?edges?are?already?contained?in?the?parents
????{
????????it?=?endpoints.iterator();
????????while?(it.hasNext())?{
????????????int?i?=?it.next();
????????????if?(distanceTable.getDistanceBetween(city,?i)?????????????????minDistance?=?distanceTable.getDistanceBetween(city,?i);
????????????????nearestCity?=?i;
????????????}
????????}
????????return?nearestCity;
????}
????????
}
對于Local Search，初始解是貪心生成的，只用了一種鄰域結構，2-opt(i, j)，其中
。如果有改進那么會一直進行2-opt全鄰域搜索，沒有的話就在greedy一個解進行下一輪鄰域搜索。1000次迭代。public?double[]?executeAlgorithm(int?iterationNr)?{
????System.out.println(getOptimalDistance());
????long?startTime?=?System.currentTimeMillis();
????Tour?t?=?Tour.createTour(createGreedyRandomizedTour(instance.getDimension()));
????Tour?bestFoundSolution?=?t;
????double?greedyCost?=?t.distance(instance);
????long?greedyTime?=?System.currentTimeMillis()-?startTime;
????int?numberOfRestarts?=?0;
????startTime?=?System.currentTimeMillis();
????while?(numberOfRestarts?<=?iterationNr){
????????TSP2OptHeuristic?heuristic?=?new?TSP2OptHeuristic(instance);
????????heuristic.apply(t);
????????results.add(relativeDistance(t));
????????bestFoundSolution?=?bestFoundSolution.distance(instance)?>?t.distance(instance)???t?:?bestFoundSolution;
????????numberOfRestarts++;
????????t?=?Tour.createTour(createGreedyRandomizedTour(instance.getDimension()));
????}
????long?localSearchTime?=?System.currentTimeMillis()-?startTime;
//??????System.out.println(System.currentTimeMillis()-startTime);
????//System.out.println("Number?of?restarts:?"?+?numberOfRestarts);
????double?bestFoundCost?=?bestFoundSolution.distance(instance);
????return?new?double[]{greedyCost,?bestFoundCost,?getOptimalDistance(),relativeDistance(greedyCost),relativeDistance(bestFoundCost),
????????????greedyTime,?localSearchTime};
}
/**
?*?Applies?the?2-opt?heuristic?to?the?specified?tour.
?*?
?*?@param?tour?the?tour?that?is?modified?by?the?2-opt?heuristic
?*/
public?void?apply(Tour?tour)?{
????DistanceTable?distanceTable?=?instance.getDistanceTable();
????boolean?modified?=?true;
????//?tours?with?3?or?fewer?nodes?are?already?optimal
????if?(tour.size()?4)?{
????????return;
????}
????while?(modified)?{
????????modified?=?false;
????????for?(int?i?=?0;?i?????????????for?(int?j?=?i+2;?j?????????????????double?d1?=?distanceTable.getDistanceBetween(tour.get(i),?tour.get(i+1))?+
????????????????????????distanceTable.getDistanceBetween(tour.get(j),?tour.get(j+1));
????????????????double?d2?=?distanceTable.getDistanceBetween(tour.get(i),?tour.get(j))?+
????????????????????????distanceTable.getDistanceBetween(tour.get(i+1),?tour.get(j+1));
????????????????//?if?distance?can?be?shortened,?adjust?the?tour
????????????????if?(d2?????????????????????tour.reverse(i+1,?j);
????????????????????modified?=?true;
????????????????}
????????????}
????????}
????}
}我們上述的Greedy和LocalSearch對9個TSP算例進行了測試，結果如下表所示：
其中：Inst表示算例的名稱。
GD(1 runs)表示運行一次，Greedy得到的解的距離。
LS(1 runs)表示運行一次，LocalSearch得到的解的距離。
OPT表示該算例下的最優(yōu)解。
GD Gap(%)表示GD(1 runs)與OPT的差值（GD(1 runs) - OPT）/ OPT * 100，越小證明Greedy越好。
LS Gap(%)表示LS(1 runs)與OPT的差值（LS(1 runs)- OPT）/ OPT * 100，越小證明LocalSearch越好。
GD Time(1 runs)表示Greedy運行時間。
LS Time(1 runs)表示LocalSearch運行時間。
下面我們從幾個方面看看吧
解的質量
可能直接看表不太直觀，我們做成圖看看：
可以明顯看到，Greedy比LocalSearch還是差了不少的啊。每個算例均比LocalSearch高出不少，個別算例還高出一大截。究竟差了多少，我們可以從上表中的Gap列看出。Greedy比最優(yōu)解普遍要高出10%-30%不等，有的甚至超過了1000%，而LocalSearch與最優(yōu)解相差維持在5%以內。這時候就充分體現了LocalSearch的優(yōu)勢，Greedy的劣勢了。時間上的差異
emm……時間就不用對比了Greedy秒天秒地秒空氣單憑速度上而言構造法應該是最快的了不過這里提一下LocalSearch的時間看下面的圖：
通常而言，啟發(fā)式算法的運行時間和終止條件密切相關。比如迭代次數，運行時間限制，無改進終止等。與精確算法之類的不同，啟發(fā)式算法拋開終止條件談運行時間是沒有意義的。因為對于精確算法、枚舉算法、構造法，他們都有一個明確的目標：
精確算法、枚舉算法：找到最優(yōu)解后終止。
構造法：構造一個解之后終止。
而對于啟發(fā)式而言，首先我不知道最優(yōu)解，所以我也不能確定找到的解是不是最優(yōu)解。所以，它的終止條件是認為設定的，這就意味著時間也是認為控制的。通常而言，時間越長找到的解質量越優(yōu)，但所有的啟發(fā)式找到的都是滿意解，不能說是最優(yōu)解（即便真的是），因為它遍歷的是解空間的局部。
一般情況下啟發(fā)式算法的時間是隨著問題規(guī)模增長而呈線性增長的
這也是它的最大優(yōu)勢之一，比如說你問題規(guī)模擴大一倍，那么我的算法在同樣的終止條件下運行時間也基本上是翻倍、或者變成幾倍而已，是一個平緩的線性增長。不會說變成
倍這種指數級別爆炸式的增長。從上面的時間曲線也可以看出，至于為什么在算例gr202上面頂了個小帳篷呢，是因為我們設置了一個比較坑爹的搜索條件，有改進就持續(xù)進行搜索。大家可以想一下：
紅色路徑的搜索過程時間肯定要比綠色路徑的長。
總結哈哈看到這里，想必大家也很不容易了。最后我想再問大家一個問題：啟發(fā)式算法相比Greedy算法來說好像并沒有提高多少（從上圖可以看出），為什么呢？花數千倍甚至萬倍的時間提高這么一點，有意義嗎？
首先回答為什么。其實這個問題也很好回答，你打游戲的時候從1級升到20級是很容易的，但是從20級升到30級難度就不可同日而語了。對于優(yōu)化也是一樣，解的質量越高，就越難以提升。
至于有沒有意義，對于現在的工業(yè)化社會而言，哪怕提升的只是一個小數點，放大到成千上萬的生產量上面，降低的成本都是極大的。這也是為什么精確算法很難應用到企業(yè)中去，但依然有一大堆學者孜孜不倦最求研究的原因。
文案&編輯：鄧發(fā)珩（華中科技大學管理學院本科三年級）審稿人：秦時明岳（華中科技大學管理學院）指導老師：秦時明岳（華中科技大學管理學院）排版：程欣悅（荊楚理工學院本科二年級）
如對文中內容有疑問，歡迎交流。PS：部分資料來自網絡。如有需求，可以聯系：秦虎老師（[email protected]）鄧發(fā)珩(華中科技大學管理學院本科三年級：[email protected])程欣悅（荊楚理工學院本科二年級：[email protected]）
推薦閱讀：
干貨 | 學習算法，你需要掌握這些編程基礎（包含JAVA和C++）
記得點個在看支持下哦～
評論
圖片
表情