香港公司

分枝界限法

分枝界限法(Branch and Bound Method)

目錄

  • 1 什麼是分枝界限法
  • 2 分枝界限法的基本思想[3]
  • 3 分枝界限法的步驟[4]
  • 4 分枝界限法的演算法實例[3]
  • 5 分枝界限法的演算法分析[3]
  • 6 參考文獻

什麼是分枝界限法

 分枝界限法是由三棲學者查理德·卡普Richard M.Karp)在20世紀60年代發明,成功求解含有65個城市的旅行商問題,創當時的記錄。“分枝界限法”把問題的可行解展開如樹的分枝,再經由各個分枝中尋找最佳解[1]

  分枝界限法也能夠使用在混合整數規劃問題上,其為一種系統化的解法,以一般線性規劃之單形法解得最佳解後,將非整數值之決策變數分割成為最接近的兩個整數,分列條件,加入原問題中,形成兩個子問題(或分枝)分別求解,如此便可求得目標函數值的上限(上界)或下限(下界),從其中尋得最佳解[2]

分枝界限法的基本思想[3]

  1、基本思想

  分枝定界法是一個用途十分廣泛的演算法,運用這種演算法的技巧性很強,不同類型的問題解法也各不相同。分支定界法的基本思想是對有約束條件的最優化問題的所有可行解(數目有限)空間進行搜索。該演算法在具體執行時,把全部可行的解空間不斷分割為越來越小的子集(稱為分支),併為每個子集內的解的值計算一個下界或上界(稱為定界)。在每次分支後,對凡是界限超出已知可行解值那些子集不再做進一步分支。這樣,解的許多子集(即搜索樹上的許多結點)就可以不予考慮了,從而縮小了搜索範圍。這一過程一直進行到找出可行解為止,該可行解的值不大於任何子集的界限。因此這種演算法一般可以求得最優解。

  將問題分枝為子問題並對這些子問題定界的步驟稱為分枝定界法。

  2、分枝節點的選擇

  對搜索樹上的某些點必須作出分枝決策,即凡是界限小於迄今為止所有可行解最小下界的任何子集(節點),都有可能作為分枝的選擇對象(對求最小值問題而言)。怎樣選擇搜索樹上的節點作為下次分枝的節點呢?有兩個原則:

  1)從最小下界分枝(隊列式FIFO分枝限界法):每次算完界限後,把搜索樹上當前所有葉節點的界限進行比較。找出限界最小的節點,此結點即為下次分枝的結點。

  • 優點:檢查子問題較少,能較快地求得最佳解;
  • 缺點:要存儲很多葉節點的界限及對應的耗費矩陣,花費很多記憶體空間。

  2)從最新產生的最小下界分枝(優先隊列式分枝限界法):從最新產生的各子集中選擇具有最小的下界的結點進行分枝。

優點:節省了空間; 缺點:需要較多的分枝運算,耗費的時間較多。

  這兩個原則更進一步說明瞭,在演算法設計中的時空轉換概念。

  分枝定界法已經成功地應用於求解整數規劃問題、生產進度表問題、貨郎擔問題、選址問題、背包問題以及可行解的數目為有限的許多其它問題。對於不同的問題,分枝與界限的步驟和內容可能不同,但基本原理是一樣的。

分枝界限法的步驟[4]

  分枝界限法是組合優化問題的有效求解方法,其步驟如下所述:

  步驟一:如果問題的目標為最小化,則設定目前最優解的值Z=∞

  步驟二:根據分枝法則(Branching rule),從尚未被洞悉(Fathomed)節點(局部解)中選擇一個節點,併在此節點的下一階層中分為幾個新的節點。

  步驟三:計算每一個新分枝出來的節點的下限值(Lower bound,LB)

  步驟四:對每一節點進行洞悉條件測試,若節點滿足以下任意一個條件,則此節點可洞悉而不再被考慮:

  • 此節點的下限值大於等於Z值。
  • 已找到在此節點中,具最小下限值的可行解;若此條件成立,則需比較此可行解與Z值,若前者較小,則需更新Z值,以此為可行解的值。
  • 此節點不可能包含可行解。

  步驟五:判斷是否仍有尚未被洞悉的節點,如果有,則進行步驟二,如果已無尚未被洞悉的節點,則演算停止,並得到最優解。

  Kolen等曾利用此方法求解含時間窗約束的車輛巡迴問題,其實驗的節點數範圍為6-15。當節點數為6時,電腦演算所花費的時間大約1分鐘(電腦型為VAZ11/785),當節點數擴大至12時,電腦有記憶體不足的現象產生,所以分枝定界法比較適用於求解小型問題。Held和Karp指出分枝定界法的求解效率,與其界限設定的寬緊有極大的關係。

分枝界限法的演算法實例[3]

  1、型推銷員問題

  設有5個城v1,v2,v3,v4,v5 ,從某一城市出發,遍歷各城市一次且僅一次,最後返回原地,求最短路徑。其費用矩陣如下:

  D=\begin{bmatrix}\infty&14&1&16&2\\ 14&\infty&25&2&3\\1&25&\infty&9&9\\16&2&9&\infty&6\\2&3&9&6&\infty\end{bmatrix}

  將矩陣D對角線以上的元素從小到大排列為:

  d13,d15,d24,d45,d34,d35KKKK

  取最小的5個求和得:d13 + d15 + d24 + d45 = 14

  用分枝界限法表示,要構成一個迴路,所以每個頂點的下標在迴路的所有邊中各出現兩次。(1)中顯然5出現了3次,若用d35代替d15d13 + d35 + d24 + d25 + d45 = 21

  分枝界限法

  搜索過程可以表示如下圖:

  分枝界限法

  圖(2)的下界為21,圖(3)的下界為20,都大於19故沒有進一步搜索的價值,因此(5)為最佳路徑:v_1\to v_3\to v_4\to v_2\to v_5\to v_1

  2、型推銷員問題

  D = (dij)n * nd_{ij}\ne d_{ji}。不妨把D看成旅費,即從vivj的旅費與vjvi不一樣。

  D=\begin{bmatrix}\infty&24&34&14&15\\ 19&\infty&20&9&6\\7&9&\infty&6&8\\23&10&22&\infty&7\\20&8&11&20&\infty\end{bmatrix}

  對D的每行減去該行的最小元素,或每列減去該列的最小元素,得一新矩陣,使得每行每列至少都有一個0元素。

  分枝界限法

  第一列和第三列沒有為0的元素,所以第一列和第三列分別減去其最小元素1和3得:

  D=\begin{bmatrix}\infty&10&17&0&1\\ 12&\infty&11&3&0\\0&3&\infty&0&2\\15&3&12&\infty&0\\11&0&0&12&\infty\end{bmatrix}_{45}

  由於從任一vi出發一次,進入vi也是一次,所以問題等價於求D=\begin{bmatrix}\infty&10&17&0&1\\ 12&\infty&11&3&0\\0&3&\infty&0&2\\15&3&12&\infty&0\\11&0&0&12&\infty\end{bmatrix}_{45} 的最佳路徑,下標45是估計的界,即旅費起碼為45單位(每個點出發都去最小值)。

  由於矩陣D第一行第四列元素為0,故從v1出發的路徑應選擇v1 − − v4,為了排除v1出發進入其他點和從其他點進入v4的可能,並封鎖v4v1的路徑,在矩陣中除去第一行和第四列,並將第四列第一行元素15改為∞。得:

  \begin{bmatrix}12&\infty&11&0\\ 0&3&\infty&2\\\infty&3&12&0\\11&0&0&\infty\end{bmatrix}_{45}

  類似的從v2出的路徑應選v2 − − v5,消第v2行和第v5列,並將第v5行第v2列元素改為∞得:

  \begin{bmatrix}0&3&\infty\\\infty&3&12\\11&\infty&0\end{bmatrix}_{45}

  這時第二行沒有0元素,減去最小元素3得:   \begin{bmatrix}0&3&\infty\\\infty&0&9\\11&\infty&0\end{bmatrix}_{45}

  搜索過程如下圖:

  分枝界限法

  最後得到最佳路徑為:v_1\to v_4\to v_2\to v_5\to v_3\to v_1

分枝界限法的演算法分析[3]

  1、演算法優點:可以求得最優解、平均速度快。

  因為從最小下界分支,每次算完限界後,把搜索樹上當前所有的葉子結點的限界進行比較,找出限界最小的結點,此結點即為下次分支的結點。這種決策的優點是檢查子問題較少,能較快的求得最佳解。

  2、缺點:要存儲很多葉子結點的限界和對應的耗費矩陣。花費很多記憶體空間。

  存在的問題:分支定界法可應用於大量組合優化問題。其關鍵技術在於各結點權值如何估計,可以說一個分支定界求解方法的效率基本上由值界方法決定,若界估計不好,在極端情況下將與窮舉搜索沒多大區別。

參考文獻

  1. ↑ 鄧宇佑(碩士).求解醫院運輸部門運輸中心個數最佳化之研究
  2. ↑ 《作業研究》[M].第七章 整數規劃
  3. 3.0 3.1 3.2 分枝界限法
  4. ↑ 夏新海.物流配送車輛調度優化研究[D].武漢理工大學,2004年