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

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

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

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


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

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

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