旅行推銷員問題實作

主要是以演化式演算法為概念進而發展一有效解決旅行推銷員問題(TSP)。將詳細介紹本研究所提出之BBICA演算法運作流程與重要的演化機制，此演算法演化機制主要分為五大部分，第一部分為各國家之定義及演化方法，第二部分則為優勢矩陣之更新機制與挖掘有效區塊的方法，並透過優勢矩陣以留存具競爭優勢之區塊，第三部分為組合人造解之方法，透過優勢矩陣以及提出之帝國競爭理念，將區塊與非區塊所包含之城市組成具有競爭優勢之人造解，將人造解注入母體加以演化，第四部分為各國人力資源之調配機制，最後則是各國利用不同機制進行自我重組之演化與優勢解之篩選機制。透過上述之五大部分進行演化並求得近似最佳解。

←流程圖如左

程式運作流程如下:

Step 1. 母體初始化：首先以隨機方式產生100條初始解，作為演化之母體。
Step 2. 計算適合度：計算母體中各個初始解之適合度函數(Fitness)。以最短距離作為適合度函數。
Step 3. 更新優勢矩陣：累計母體中解的鏈結關係更新優勢矩陣。
Step 4. 組合人造解：進行區塊挖掘，根據優勢矩陣組合出優勢區塊，將300條人造解進行母體重組。之後依各國強弱重新調配各國產生人造解之數量。
Step 5. 母體重組：將母體或人造解進行隨機演化之步驟，達到優化之目的，重組後新產生的解則稱為子代。
Step 6. 留存優勢解：篩選母體與子代中具競爭優勢的解，成為新的母體進入下一世代演化。重複執行Step3到Step6，直到停止條件滿足。

國家定義

假設有6個城市，隨機產生100條排序，如圖只顯示第一個排序與3個國家計算漢明距離以確認是否正確。

(漢明距離:與原定義不同，比較兩排序鏈結關係，鏈結相同者漢明距離=0，鏈結不同者漢明距離=1)，結果顯示3個群的漢明距離加總分別是count = 2, 5, 3，K=0的距離最短屬於第1個國家

最後會有100條解分別落在3個國家裡。

更新優勢矩陣

BBICA的機率模型主要為記錄過去具有優勢的演化訊息，故稱為優勢矩陣(Dominance Matrix)。優勢矩陣考量兩個城市之間的相連關係，能詮釋群體中每一條可行解(Feasible solution)的分佈關係，並以每世代不斷累加之方式記錄。爾後依據優勢矩陣之訊息產生優勢區塊與人造解，使得區塊與人造解更具多樣性，避免BBICA陷入局部最佳化的困境。

程式機率矩陣簡易圖(6個城市):

建構區塊

若能降低其複雜度與找出有效之資訊，則更容易找到良好之解排序，並加速收斂。優勢區塊為具有高度競爭優勢之基因鏈結，可確實找出有效資訊以致降低演化複雜度，以城市數為6的旅行推銷員問題舉例來說，如下圖所示，原先母體中的城市(City1至City6)為單獨的個體，產生的可行解有6!種排列組合，而將過去有效資訊組合出優勢區塊{B1,B2,B3}，產生之可行解的排列組合降為3!種，大幅降低可行解之複雜度。本研究藉找出具優勢之區塊，透過區塊與非區塊的組合，產生蘊含高度競爭力之人造解。以下將詳細介紹區塊之建構方法與運作細節，分為區塊挖掘(Block Mining)與區塊競爭(Blocks Competition)兩小節做解說。

複雜度比較:

區塊挖掘

藉以區塊挖掘找出有效資訊，透過其區塊組合出具競爭力之人造解。然而，區塊之組成訊息來源是之前的優勢矩陣所提供，以下將詳細介紹區塊挖掘之運作方法與細節。首先產生符合足夠數量區塊長度的空白區塊，區塊之數量設為城市數∗ 0.2，區塊之長度設為2。如圖所示，產生區塊長度為2的空白區塊。

空白區塊:

程式提供兩種挖掘區塊機制，第一種稱為MB-I(Mining Blocks-I)主要為起初即能加速收斂至一定程度。

Step 1：隨機選擇一起始點
Step 2：根據距離選出以起始點為出發點，依距離順序由短到長升冪排列
Step 3：選擇最短距離之城市，若城市被選取過則往後推延一個

挖掘區塊I示意圖:

再者稱為MB-II(Mining Blocks-II)主要為增加多樣性以避免局部優化。

Step 1：隨機選擇一起始點
Step 2：根據優勢矩陣選出以起始點為出發點
Step 3：目前可供挑選之區塊為數條，依優勢矩陣所累計之訊息轉為機率再以輪盤選擇法(RouletteWheel Selection, RWS)挑選一條作為此次產生之區塊

挖掘區塊II示意圖:

將已挖掘之區塊儲存至暫存資料庫(Buffer Archive)，暫存資料庫中保存此世代挖掘出的所有區塊。當滿足設定之挖掘區塊數量，則會進入區塊競爭之步驟。

區塊競爭

區塊競爭的方法是將此世代新產生的區塊與區塊資料庫(Block Archive)中的區塊進行挑選與比較，區塊資料庫中保存演化以來，透過區塊間的競爭所留存下來的優勢區塊。我們將暫存資料庫中的區塊與區塊資料庫中的進行比對，若區塊之間出現重複城市，將發生重複之區塊依優勢矩陣之機率值進行比較，機率較大者得以保留至區塊資料庫，較小者則刪除。假若暫存資料庫之某區塊並未與其他區塊發生城市重複，則該區塊直接進入區塊資料庫保存。

區塊競爭如圖所示，暫存資料庫與區塊資料庫中，分別包含區塊{B1,B2,B3}與區塊{B4,B5,B6}，暫存資料庫中的B1與區塊資料庫中的B4出現重複City1和City2，兩者相同則區塊保留，B2與B5出現重複的City6，以各自在優勢矩陣的值進行比較，B2的值為10，小於B5的值20，所以將不變動區塊資料庫，暫存資料庫進行下一個區塊比較；反之如果B2值大於B5值，檢查B2的City6所連接的City4與區塊資料庫B6相同，以各自在優勢矩陣的值進行比較，B2值大於B6值，B2將取代B5和B6進入區塊資料庫，而B5和B6則淘汰並刪除。下一步B3與B5出現重複的City5，B3的值為5，小於B5的值20，不變動區塊資料庫，結束當前區塊競爭。經過區塊競爭，留存B4、B5、B6，成為該世代之區塊資料庫。另因對稱型旅行推銷員問題之特性，故其區塊之相連性則不分先後，即意謂人造解組合若應用下圖之區塊B6其順序{5, 4}等同於{4, 5}。

最後的區塊資料庫將取用前80%的區塊，假如有10個區塊，將選取前8個區塊，而刪除最後2個區塊，在人造解步驟避免陷入盲點，並發掘新空間。

組合人造解

人造解組合將應用區塊挖掘機制所保留於區塊資料庫之區塊，以下將詳細介紹程式所提供的兩種組合人造解機制：

第一種為M-I(Artificial Chromosome mechanism-I)，首先將從人造解之出發點開始挖掘利用隨機方式產生，其餘N-1個位置皆使用優勢矩陣之機率以最大值做選擇，已選入人造解之城市將不再參與選擇。每當人造解選出一個城市，會將該城市與所有區塊比對，若區塊中含有該城市且另一相連城市未被選擇，則將該區塊直接複製到人造解中；若另一相連城市已被選擇即意謂該區塊已無效，從複製後的下個連結城市繼續選擇並比對，直至完成人造解。

第二種為M-II(Artificial Chromosome mechanism-II)，此方法會先隨機產生出發點，其餘N-1個位置則使用最短距離選擇下一相連城市，已選入人造解之城市將不再參與選擇。同M-I作區塊比對，若區塊中含有該城市且另一相連城市未被選擇，則將該區塊直接複製至人造解，從複製後的下個連結城市繼續選擇並比對，直至完成人造解。

M-I運作方式如下列所示，區塊資料庫中有兩條區塊分別為B1和B2，首先針對人造解隨機選擇出發點City6，將進行區塊比對，比對發現B2含有City6，因此直接將B2之內容{3,6}複製至序列，由City3開始繼續選擇下一城市，依照優勢矩陣之機率以最大值選擇City4並比對B1，比對後並未相同，則由City4繼續選擇下一城市，接續選出City1且比對區塊得知B1含有City1，將B1之內容{1,5}複製至序列，重複上述步驟直到序列完成。最後完成城市排序為{6,3,4,1,5,2}的人造解。

1. 隨機起始點City6

2. B2區塊中含有City6，將區塊B2複製到人造解中

3. 優勢矩陣之機率以最大值選擇下一個城市City4

4. 優勢矩陣之機率以最大值選擇下一個城市City1

5. B1區塊中含有City 1，將區塊B1複製到人造解中

6. 優勢矩陣之機率以最大值選擇下一個城市City2，序列完成

M-II的運作方式如下列所示，首先隨機挑選出發點City3，接續進行區塊比對，發現B3含有City3，因此直接複製B3之內容{3,6}至序列，由City6繼續選擇下一城市，依據最短距離選擇出City5並比對B1含有City5，將B1之內容{1,5}複製至序列，重複上述步驟直到序列完成。最後完成城市排序為{3,6,5,1,2,4}的人造解。

隨機起始點City3

B2區塊中含有City3，將區塊B2複製到人造解中

最短距離選擇下一個城市City5

B1區塊中含有City5，將區塊B1複製到人造解中

最短距離選擇下一個城市City2

最短距離選擇下一個城市City4，序列完成

國家演化與留存

為提高機會以找尋最佳解，我們將針對每條母體解或人造解進行突變。演化方法為單點Swap，希望藉以增加人造解演化後之多樣性，首先針對單點Swap之運作細節，以下分為兩小節做介紹；其次介紹國家留存機制。

單點swap

隨機選取2個交換點分別為point 1與point 2，如圖21將此交換點之部分以灰底表示，將其兩點之內容作交換即完成該人造解之演化。

經母體重組所產生的子代會與此世代原始之母體進行篩選，選擇出新之母體進入下一世代演化。首先，將新產生的子代與原始母體一同放入選擇池(Selection Pool)，將選擇池內之子代與母體依適合度函數作升冪排序，排序後依此結果將前N名的解則稱為新母體，新的母體進入下一世代演化。

假設母體大小為5，篩選新母體之運作示意圖如圖所示，Xi代表原始母體的解、ri代表子代的解。

競爭作用

競爭作用即是各帝國間之殖民地搶奪，本研究將其定義為各組合人造解機制於下一世代人力資源數量之調配，在此定義人力資源數量為該組合方法所需產生之人造解數量。本研究透過各國家之適合度函數之平均數作為升冪排序依據，每世代依其國家排序名次依序增減人力資源數量為：{+10, +0, −10}、{+5, +5, −10}或{+10, -5, −5}。

{+10, +0, −10}適合度皆不同時