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

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

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

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


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

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

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