基于LabVIEW仿真的全局最短路徑的遺傳算法設計

楊多星，劉蘊紅

（大連理工大學 電氣工程學院，遼寧 大連 116023）

最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中結點之間的最短路徑。問題的主要種類有：確定起點的最短路徑問題；確定終點的最短路徑問題；確定起點終點的最短路徑問題；全局最短路徑問題。其中全局最短路徑是求連接圖中所有點的最短路徑，它的限制最少，答案的可能性卻最多。同時當加入一定的限制條件后也可以相應的轉化成前3種問題，所以更值得研究推廣。

現有的解決最短路徑問題的遺傳算法大多是將圖轉化成一棵樹，通過各種遍歷手段，得到與這棵樹唯一對應的一個數組排列（或向量），并以此作為遺傳算法的種群個體[1-3]。生成樹以及遍歷方法的優劣就決定了該種遺傳算法的好壞[4]。本文并不是提出一種改進的生成樹或遍歷的方法，相反，完全隨機生成樹，不做任何限制，也未對樹進行遍歷，只是在遺傳算法對每代種群進行優勝劣汰時，同時對不合格的個體進行淘汰。省略了生成樹以及遍歷的過程，也就相當于化簡了編碼解碼過程。

1 問題描述

在一定區域內分布著一些點，要使用線段將所有點連接到同一個網絡下。如何連接這些點才能令使用到的所有線段的總長度最短。建立相應的數學模型。設有M個點，坐標記為Pi（xi，yi），1≤i≤M 則每兩個點之間的距離為

要連接M個點并使總距離最短，則至少要有M-1條線段，那么目標函數即總距離

2 編 碼

遺傳算法的編碼很重要，因為在整個過程中會不斷地對基因做交叉變異以及適應度的運算，所以編碼方式直接影響算法的速度。很明顯，編碼后的基因鏈越短，每個基因位上的基因種類越少，算法的運行速度越快。使用二進制編碼的話，雖然每個基因位上的基因種類只有2種，但如果點的個數較多，將會使基因鏈過長，在遺傳變異的過程中中間節點情況太多，使整個過程變得過于復雜，所以這里選擇用十進制編碼的方法[5]。

一般的編碼方法都是將節點和線段編號，再通過某種運算對用這些編號構成的向量進行一系列處理，得到較原向量更為簡單或與連接方法能一一對應的新向量，并以此作為種群個體。本文的方法中，線段不但有編號，而且具有方向性。利用其方向性線段編號可以直接作為個體使用，省略了一般情況下的編碼解碼過程，所以運算更加簡單快捷。

2.1 個體確定

M個點兩兩相連，共有M（M-1）/2條線段，將所有線段編號。編號的順序規則為：

1）從1號點出發，按順序依次連接2號點、3號點......M號點的線段，編號為1～M-1；

2）從2號點出發，按順序依次連接3號點、4號點......M號點的線段，編號為M～2M-3；

3）直到M-1號點連接M號點的線段為最后一條線段。

每個基因就是1條線段，那么每個基因就有種可能，要使用數量最少的線段就連接所有點，需要M-1條線段。如圖1所示網絡，共有5個點，兩兩相連共有10條線段，形成個體需要其中的4條線段，圖1所示的2個個體對應的基因鏈即種群個體分別為{1、3、4、5}和{1、2、5、10}。

圖1 5節點網絡和2個個體Fig.1 Five-node network and two individuals

2.2 合法性判斷

很明顯不是任意4條線（以圖1的5個點為例）都適合作為初始種群的個體，所以在使用每個種群個體前判斷其合法性就相當于減少了基因的種類，大大化簡了運算過程，免去一些不必要的計算，加快收斂速度。合法性可以通過以下3個條件進行判斷：

條件1：不能出現重復編號。

如{1、1、2、3}，其實只有 3 條線，這個個體必然是錯誤的，在最開始就可以淘汰，不需要進入循環中運算。

條件2：4條線的編號必須從小到大。

如{1、2、3、5}和{5、3、1、2}是 2 種不同的種群個體，但實質上是同樣的4條線，進行了從小到大的定義后就可以避免產生大量的最優解，導致運算混亂。

條件3：必須保證所有點連在一起（或者沒有回路）。

如{1、2、5、10}（圖 1 第 2 個個體），連接了所有點，但 1、2、5構成回路導致5個點被分成了兩部分，相當于有一部分沒有被連接進網絡，此個體也要直接淘汰。

為了判斷上述3個條件是否滿足，需要建立2個數組，點信息數組Point[]和線信息數組Line[]。Point[]是二維數值數組，按點的編號順序存儲，每一行存有一個點的橫縱坐標2個數。Line[]是二維數值數組，按線段的編號順序存儲，每一行存有一條線段信息，包括線段的端點和長度3個數。圖2為5節點時LabVIEW前面板的模擬圖及2個數組的存儲情況。

圖2 點信息數組、線信息數組和模擬圖Fig.2 Point information array、line information array and simulated diagram

條件 2易滿足，為滿足條件 1和條件 3，定義（M-1）×M階判斷矩陣A，表示被選中的線段與各節點的關系。每一行對應一條線段，每一列依次對應M個節點。在定義Line[]的2個端點時，都是序號小的節點在前，大的在后，所以不妨把每條線段看成有方向的矢量，從小號節點指向大號節點。在矩陣對應的位置，起點為-1，終點為1，其他點為0。以圖1為例，2 個個體 對應的判 斷矩陣分 別為 A1、3、4、5和 A1、2、5、10。

判斷矩陣 A1、3、4、5的行向量線性不相關，秩是列數 4，也就是被選中的線段個數即每個個體的基因數。個體{1、2、5、10}因為 1、2、5 構成了回路，可以得到 1+5=2，其判斷矩陣 A1、2、5、10中對應的3個行向量必定是同樣的關系，則這3個行向量線性相關。 所以判斷矩陣 A1、2、5、10的秩必然小于列數 4。 由矢量圖能看出，每多一條回路，判斷矩陣的秩就會減少1。當出現重復編號時，如{1、1、2、5}，則有 2個行向量相同，其判斷矩陣A的秩必然也小于列數4.

綜上，Point[]是已知的。由Point[]可以得到Line[]（如圖3（a））。任意給定4條線的個體，由Line[]和Point[]得到判斷矩陣 A，如果 rank（A）=M-1，則滿足 3 個條件（如圖 3（b））；否則，該個體非法。

3 初始種群獲取

圖3 求Line[]并判斷合法性Fig.3 Getting Line[]and judging legitimacy program

根據上面的說明，本文在獲取初始種群時，每一個個體首先是從M（M-1）/2條線段中隨機取出M-1條。取得的方法是：

1）建立M（M-1）/2階布爾數組，數組里每個元素是假常量；

2）產生一個0～1的隨機數與M（M-1）/2相乘并向下取整，隨機得到一個整數 n，則 n∈[0，M（M-1）/2-1]；

3）將布爾數組中第n個元素替換為真常量；

4）重復2、3步直到布爾數組中有了M-1個真常量；

5）依次提取布爾數組中的每個真常量的索引值并加1。其取得方法的框圖如圖4所示。

圖4 利用隨機數產生一個隨機個體Fig.4 A random individual with randam number

得到的M-1階常數數組就是一個隨機產生的初始個體，而且此個體直接滿足條件1和條件2。對這樣的個體進行合法性判斷，如果不合法舍去重新產生新個體。如果合法保留再生成下一個個體。用for循環來控制種群大小。

4 適應度函數

因為目標函數是求最小值，而且D肯定大于0，所以不妨直接以目標函數的倒數作為適應度函數。

5 遺傳策略

本文基于Srinivas提出的自適應遺傳算法（Adaptive GA，簡稱AGA）[7]提出新的編碼方式下的遺傳策略。

式中，pc表示交叉率，pm表示變異率，fmax表示種群最大適應度值，favg表示種群平均適應度值，f′表示在要交叉的兩個個體中較大的適應度值，f表示要變異的個體適應度值。k1，k2，k3，k4是在0和1之間取值的常數，其中，k3和k4較大。

式（3）和式（4）是AGA根據適應度值調節后的交叉率和變異率，它較好地解決遺傳算法中全局搜索和局部搜索的平衡問題，提高了收斂速度。

5.1 雜交

雜交運算是遺傳算法擴大優秀基因影響的重要方法。但本文使用的編碼方法中，如果使用簡單的單點交叉方法，無疑很大概率上將產生不合法的無效子代。如圖1中的5個點，兩個父代{1、2、3、4}和{4、5、8、10}做交叉運算，無論交叉點在哪都會產生含有2個4號線段的非法子代，不滿足條件1。

為了改善這種情況，本文摒棄了雙父代雜交而采用一種"群體精英父代雜交"的方法[6]。因為雜交運算就是為了使優秀基因快速繁殖，擴大影響，所以不妨直接判定哪些基因是有較大概率優秀的。舉例說明判斷方法，選擇所有f′＞favg的父代個體，這些個體明顯都是優秀的，從這些優秀父代中提取出共有的或出現次數較多的基因，因為優秀父代中含有優秀基因的可能大，所以這些共有的基因就更可能是優秀基因。保留這些基因，在剩余的基因位上隨機產生新的基因。最后從產生的這些新個體和f′＜favg的低適應度父代中選出適應度高的一部分作為子代，它們與開始的那些優秀父代一起合成新的子代。因為實際上并沒有使用單點雜交的方法，所以不使用式（3）。

5.2 變異

按式（4）計算，如果一個父代個體要變異時，從其中隨機取一條線段除去換上一條新的線段。為了提高變異操作提供新基因的效率，防止無方向性的變異產生大量冗余，新的線段要有一個端點不變。如圖5所示，當除去線段12時，新產生的線段必須以節點3或6為端點，不算線段12，節點3、節點6分別還可以與其他M-2個節點產生共2M-4個子代個體，當然其中有很多新個體是不合法的，從合法的子代個體中選擇適應度最高的遺傳到下一代。這樣，經過幾代變異后，個體就會逐漸趨于所求目標。

圖5 個體變異過程Fig.5 The mutation process of individuals

為了防止局部收斂，即使產生的子代個體適應度不如父代個體，也要淘汰父代個體。

5.3 精英保留

根據上述方法，在進化中很可能導致高適應度個體被意外的破壞，減緩進化速度甚至導致局部收斂。所以每次進化前取出當代個體中適應度最高的一個個體直接進入下一代，保證最優基因的安全。

6 仿真實驗

選取一組數據（見表1）進行仿真實驗，種群數量取50個，計算100代。

表1 20個點的編號和坐標Tab.1 Serial numbers and coordinates of 20 points

得到仿真結果如圖6所示。

圖6為分別截取了運行到不同代數時的結果。圖6（a）表示所有點的位置及所有可能的連線，圖6（b）～圖6（d）中數字含義，括號內的數字表示運行代數，括號外是此時線段的總長度。圖6（d）顯示最終總長度為1087.77。

圖6 仿真結果Fig.6 Simulation result

7 結 論

綜上所述，此方法可以有效地解決全局最短路徑問題。相對于“旅行商問題”單一起點終點的“一筆畫”情況和繁復的編碼解碼運算，本文的方法更具有廣泛性。因為節省了一般的編碼解碼過程，所以運算更加快捷，結果更易識別。隨著約束條件的改變，只需相應的修改目標函數即可，不會影響程序的其他功能。該方法可以適用多類工程設計，如Zigbee無線模塊組網、城鄉間道路和配電網設置、農田灌溉點之間的管道連接、多目標的運輸問題等等。

[1]章文俊，程浩忠，王一，等.基于樹形結構編碼單親遺傳算法的配電網優化規劃[J].電工技術學報，2009，24（5）:154-160.ZHANG Wen-jun， CHENG Hao-zhong， WANG Yi，et al.Distribution network optimal planning based on tree structure encoding partheno-genetic algorithm [J].Transactions of China Electrotechnical Society， 2009（5）:154-160.

[2]何忠華，孟祥瑞.基于節點編碼的最小生成樹算法[J].黑龍江科技信息， 2008（34）:90.HE Zhong-hua，MENG Xiang-rui.Minimum spanning tree algorithm based on node-encoding [J].Heilongjiang Science and Technology Information， 2008（34）:90.

[3]馬孝義，范興業，趙文舉，等.基于整數編碼遺傳算法的樹狀灌溉管網優化設計方法[J].水利學報，2008，39（3）:373-397.MA Xiao-yi， FAN Xing-ye， ZHAO Wen-ju，et al.Tree-type pipe network optimization design method based on integer coding genetic algorithm[J].Journal of Hydraulic Engineering，2008， 39（3）:373-397.

[4]田小梅，龔靜.遺傳算法在度約束最小生成樹問題中的應用 [J].湖南環境生物職業技術學院學報，2009，15（3）:1-4.TIAN Xiao-mei，GONG Jing.Applications of genetic algorithm to degree-constrained minimum spanning tree[J].JournalofHunan EnvironmentBiologicalPolytechnic，2009，15（3）:1-4.

[5]陸鎖軍，郭釗俠，方建安.基于多父輩交叉的次序編碼遺傳算法及其性能[J].東華大學學報：自然科學版，2008，34（4）:449-453.LU Suo-jun， GUO Zhao-xia， FANG Jian-an.On the performance of order based genetic algorithm with multiparent crossover[J].Journal of Donghua University:Natural Science，2008， 34（4）:449-453.

[6]胡宏銀，朱紹文，張大斌，等.用實數編碼的遺傳算法構造斜決策樹[J].計算機科學，2001，28（2）:108-110.HU Hong-yin， ZHU Shao-wen， ZHANG Da-bin，et al.Oblique decision tree construction with decimal-coded genetic algorithm[J].Computer Science， 2001， 28（2）:108-110.

[7]Srinivas M，Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithm [J].IEEE Transactions on Systems：Man and Cybernetics， 1994， 24（4）:656-667.