基于LabVIEW仿真的全局最短路徑的遺傳算法設(shè)計
加入技術(shù)交流群
判斷矩陣A1、3、4、5的行向量線性不相關(guān)，秩是列數(shù)4，也就是被選中的線段個數(shù)即每個個體的基因數(shù)。個體{1、2、5、10}因為1、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))；否則，該個體非法。本文引用地址：http://www.ex-cimer.com/article/202494.htm
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ù)
因為目標(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 雜交
雜交運算是遺傳算法擴(kuò)大優(yōu)秀基因影響的重要方法。但本文使用的編碼方法中，如果使用簡單的單點交叉方法，無疑很大概率上將產(chǎn)生不合法的無效子代。如圖1中的5個點，兩個父代{1、2、3、4}和{4、5、8、10}做交叉運算，無論交叉點在哪都會產(chǎn)生含有2個4號線段的非法子代。不滿足條件1。
評論