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

最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖(由結(jié)點(diǎn)和路徑組成的)中結(jié)點(diǎn)之間的最短路徑。問題的主要種類有：確定起點(diǎn)的最短路徑問題；確定終點(diǎn)的最短路徑問題；確定起點(diǎn)終點(diǎn)的最短路徑問題；全局最短路徑問題。其中全局最短路徑是求連接圖中所有點(diǎn)的最短路徑，它的限制最少，答案的可能性卻最多。同時當(dāng)加入一定的限制條件后也可以相應(yīng)的轉(zhuǎn)化成前3種問題，所以更值得研究推廣。
    現(xiàn)有的解決最短路徑問題的遺傳算法大多是將圖轉(zhuǎn)化成一棵樹，通過各種遍歷手段，得到與這棵樹唯一對應(yīng)的一個數(shù)組排列(或向量)，并以此作為遺傳算法的種群個體。生成樹以及遍歷方法的優(yōu)劣就決定了該種遺傳算法的好壞。本文并不是提出一種改進(jìn)的生成樹或遍歷的方法，相反，完全隨機(jī)生成樹，不做任何限制，也未對樹進(jìn)行遍歷，只是在遺傳算法對每代種群進(jìn)行優(yōu)勝劣汰時，同時對不合格的個體進(jìn)行淘汰。省略了生成樹以及遍歷的過程，也就相當(dāng)于化簡了編碼解碼過程。

1 問題描述
    在一定區(qū)域內(nèi)分布著一些點(diǎn)，要使用線段將所有點(diǎn)連接到同一個網(wǎng)絡(luò)下。如何連接這些點(diǎn)才能令使用到的所有線段的總長度最短。建立相應(yīng)的數(shù)學(xué)模型。設(shè)有M個點(diǎn)，坐標(biāo)記為Pi(xi，yi)，1≤i≤M則每兩個點(diǎn)之間的距離為
   
    要連接M個點(diǎn)并使總距離最短，則至少要有M-1條線段，那么目標(biāo)函數(shù)即總距離
   

2 編碼
    遺傳算法的編碼很重要，因?yàn)樵谡麄€過程中會不斷地對基因做交叉變異以及適應(yīng)度的運(yùn)算，所以編碼方式直接影響算法的速度。很明顯，編碼后的基因鏈越短，每個基因位上的基因種類越少，算法的運(yùn)行速度越快。使用二進(jìn)制編碼的話，雖然每個基因位上的基因種類只有2種，但如果點(diǎn)的個數(shù)較多，將會使基因鏈過長，在遺傳變異的過程中中間節(jié)點(diǎn)情況太多，使整個過程變得過于復(fù)雜，所以這里選擇用十進(jìn)制編碼的方法。
    一般的編碼方法都是將節(jié)點(diǎn)和線段編號，再通過某種運(yùn)算對用這些編號構(gòu)成的向量進(jìn)行一系列處理，得到較原向量更為簡單或與連接方法能一一對應(yīng)的新向量，并以此作為種群個體。本文的方法中，線段不但有編號，而且具有方向性。利用其方向性線段編號可以直接作為個體使用，省略了一般情況下的編碼解碼過程，所以運(yùn)算更加簡單快捷。
2．1 個體確定
    M個點(diǎn)兩兩相連，共有M(M-1)／2條線段，將所有線段編號。編號的順序規(guī)則為：
    1)從1號點(diǎn)出發(fā)，按順序依次連接2號點(diǎn)、3號點(diǎn)……M號點(diǎn)的線段，編號為1～M-1；
    2)從2號點(diǎn)出發(fā)，按順序依次連接3號點(diǎn)、4號點(diǎn)……M號點(diǎn)的線段，編號為M～2M-3；
    3)直到M-1號點(diǎn)連接M號點(diǎn)的線段為最后一條線段。
    每個基因就是1條線段，那么每個基因就有種可能，要使用數(shù)量最少的線段就連接所有點(diǎn)，需要M-1條線段。如圖1所示網(wǎng)絡(luò)，共有5個點(diǎn)，兩兩相連共有l(wèi)O條線段，形成個體需要其中的4條線段，圖l所示的2個個體對應(yīng)的基因鏈即種群個體分別為{1、3、4、5}和{1、2、5、10}。

2．2 合法性判斷
    很明顯不是任意4條線(以圖l的5個點(diǎn)為例)都適合作為初始種群的個體，所以在使用每個種群個體前判斷其合法性就相當(dāng)于減少了基因的種類，大大化簡了運(yùn)算過程，免去一些不必要的計算，加快收斂速度。合法性可以通過以下3個條件進(jìn)行判斷：
    條件1：不能出現(xiàn)重復(fù)編號。
    如{1、1、2、3}，其實(shí)只有3條線，這個個體必然是錯誤的，在最開始就可以淘汰，不需要進(jìn)入循環(huán)中運(yùn)算。
    條件2：4條線的編號必須從小到大。
    如{1、2、3、5}和{5、3、1、2}是2種不同的種群個體，但實(shí)質(zhì)上是同樣的4條線，進(jìn)行了從小到大的定義后就可以避免產(chǎn)生大量的最優(yōu)解，導(dǎo)致運(yùn)算混亂。
    條件3：必須保證所有點(diǎn)連在一起(或者沒有回路)。
    如{1、2、5、10}(圖l第2個個體)，連接了所有點(diǎn)，但1、2、5構(gòu)成回路導(dǎo)致5個點(diǎn)被分成了兩部分，相當(dāng)于有一部分沒有被連接進(jìn)網(wǎng)絡(luò)，此個體也要直接淘汰。
    為了判斷上述3個條件是否滿足，需要建立2個數(shù)組，點(diǎn)信息數(shù)組Point[]和線信息數(shù)組Line[]。Point[]是二維數(shù)值數(shù)組，按點(diǎn)的編號順序存儲，每一行存有一個點(diǎn)的橫縱坐標(biāo)2個數(shù)。Line[]是二維數(shù)值數(shù)組，按線段的編號順序存儲，每一行存有一條線段信息，包括線段的端點(diǎn)和長度3個數(shù)。圖2為5節(jié)點(diǎn)時LabVIEW前面板的模擬圖及2個數(shù)組的存儲情況。

    條件2易滿足，為滿足條件1和條件3，定義(M-1)xM階判斷矩陣A，表示被選中的線段與各節(jié)點(diǎn)的關(guān)系。每一行對應(yīng)一條線段，每一列依次對應(yīng)M個節(jié)點(diǎn)。在定義Line[]的2個端點(diǎn)時，都是序號小的節(jié)點(diǎn)在前，大的在后，所以不妨把每條線段看成有方向的矢量，從小號節(jié)點(diǎn)指向大號節(jié)點(diǎn)。在矩陣對應(yīng)的位置，起點(diǎn)為-1，終點(diǎn)為1，其他點(diǎn)為O。以圖1為例，2個個體對應(yīng)的判斷矩陣分別為A1、3、4、5和A1、2、5、10。
   
    判斷矩陣A1、3、4、5的行向量線性不相關(guān)，秩是列數(shù)4，也就是被選中的線段個數(shù)即每個個體的基因數(shù)。個體{1、2、5、10}因?yàn)?、2、5構(gòu)成了回路，可以得到，其判斷矩陣A1、2、5、10中對應(yīng)的3個行向量必定是同樣的關(guān)系，則這3個行向量線性相關(guān)。所以判斷矩陣A1、2、5、10的秩必然小于列數(shù)4。由矢量圖能看出，每多一條回路，判斷矩陣的秩就會減少1。當(dāng)出現(xiàn)重復(fù)編號時，如{1、1、2、5}，則有2個行向量相同，其判斷矩陣A的秩必然也小于列數(shù)4。
    綜上，Point[]是已知的。由Point[]可以得到Line[](如圖3(a))。任意給定4條線的個體，由Line[]和Point[]得到判斷矩陣A，如果rank(A)=M-1，則滿足3個條件(如圖3(b))；否則，該個體非法。

3 初始種群獲取
    根據(jù)上面的說明，本文在獲取初始種群時，每一個個體首先是從M(M-1)／2條線段中隨機(jī)取出M-1條。取得的方法是：
    1)建立M(M-1)／2階布爾數(shù)組，數(shù)組里每個元素是假常量；
    2)產(chǎn)生一個0～1的隨機(jī)數(shù)與M(M-1)／2相乘并向下取整，隨機(jī)得到一個整數(shù)n，則n∈[0，M(M-1)／2-1]；
    3)將布爾數(shù)組中第n個元素替換為真常量；
    4)重復(fù)2、3步直到布爾數(shù)組中有了M-1個真常量；
    5)依次提取布爾數(shù)組中的每個真常量的索引值并加1。
    其取得方法的框圖如圖4所示。

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

4 適應(yīng)度函數(shù)
    因?yàn)槟繕?biāo)函數(shù)是求最小值，而且D肯定大于0，所以不妨直接以目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。

5 遺傳策略
    本文基于Srinivas提出的自適應(yīng)遺傳算法(Adaptive GA，簡稱AGA)提出新的編碼方式下的遺傳策略。
   
   
    式中，pc表示交叉率，Pm表示變異率，fmax表示種群最大適應(yīng)度值favg表示種群平均適應(yīng)度值，f表示在要交叉的兩個個體中較大的適應(yīng)度值，f表示要變異的個體適應(yīng)度值。k1，k2，k3，k4是在0和1之間取值的常數(shù)，其中，k3和k4較大。
    式(3)和式(4)是AGA根據(jù)適應(yīng)度值調(diào)節(jié)后的交叉率和變異率，它較好地解決遺傳算法中全局搜索和局部搜索的平衡問題，提高了收斂速度。
5．1 雜交
    雜交運(yùn)算是遺傳算法擴(kuò)大優(yōu)秀基因影響的重要方法。但本文使用的編碼方法中，如果使用簡單的單點(diǎn)交叉方法，無疑很大概率上將產(chǎn)生不合法的無效子代。如圖1中的5個點(diǎn)，兩個父代{1、2、3、4}和{4、5、8、10}做交叉運(yùn)算，無論交叉點(diǎn)在哪都會產(chǎn)生含有2個4號線段的非法子代。不滿足條件1。
    為了改善這種情況，本文摒棄了雙父代雜交而采用一種“群體精英父代雜交”的方法。因?yàn)殡s交運(yùn)算就是為了使優(yōu)秀基因快速繁殖，擴(kuò)大影響，所以不妨直接判定哪些基因是有較大概率優(yōu)秀的。舉例說明判斷方法，選擇所有f>favg的父代個體，這些個體明顯都是優(yōu)秀的，從這些優(yōu)秀父代中提取出共有的或出現(xiàn)次數(shù)較多的基因，因?yàn)閮?yōu)秀父代中含有優(yōu)秀基因的可能大，所以這些共有的基因就更可能是優(yōu)秀基因。保留這些基因，在剩余的基因位上隨機(jī)產(chǎn)生新的基因。最后從產(chǎn)生的這些新個體和f<favg的低適應(yīng)度父代中選出適應(yīng)度高的一部分作為子代，它們與開始的那些優(yōu)秀父代一起合成新的子代。因?yàn)閷?shí)際上并沒有使用單點(diǎn)雜交的方法，所以不使用式(3)。
5．2 變異
    按式(4)計算，如果一個父代個體要變異時，從其中隨機(jī)取一條線段除去換上一條新的線段。為了提高變異操作提供新基因的效率，防止無方向性的變異產(chǎn)生大量冗余，新的線段要有一個端點(diǎn)不變。如圖5所示，當(dāng)除去線段12時，新產(chǎn)生的線段必須以節(jié)點(diǎn)3或6為端點(diǎn)，不算線段12，節(jié)點(diǎn)3、節(jié)點(diǎn)6分別還可以與其他M-2個節(jié)點(diǎn)產(chǎn)生共2M-4個子代個體，當(dāng)然其中有很多新個體是不合法的，從合法的子代個體中選擇適應(yīng)度最高的遺傳到下一代。這樣，經(jīng)過幾代變異后，個體就會逐漸趨于所求目標(biāo)。

    為了防止局部收斂，即使產(chǎn)生的予代個體適應(yīng)度不如父代個體，也要淘汰父代個體。
5．3 精英保留
    根據(jù)上述方法，在進(jìn)化中很可能導(dǎo)致高適應(yīng)度個體被意外的破壞，減緩進(jìn)化速度甚至導(dǎo)致局部收斂。所以每次進(jìn)化前取出當(dāng)代個體中適應(yīng)度最高的一個個體直接進(jìn)入下一代，保證最優(yōu)基因的安全。

6 仿真實(shí)驗(yàn)
    選取一組數(shù)據(jù)(見表1)進(jìn)行仿真實(shí)驗(yàn)，種群數(shù)量取50個，計算100代。

    得到仿真結(jié)果如圖6所示。

    圖6為分別截取了運(yùn)行到不同代數(shù)時的結(jié)果。圖6(a)表示所有點(diǎn)的位置及所有可能的連線，圖6(b)～圖6(d)中數(shù)字含義，括號內(nèi)的數(shù)字表示運(yùn)行代數(shù)，括號外是此時線段的總長度。圖6(d)顯示最終總長度為1087．77。

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