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

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

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

要連接M個(gè)點(diǎn)并使總距離最短，則至少要有M-1條線(xiàn)段，那么目標函數即總距離


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

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

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