基于LabVIEW仿真的全局最短路徑的遺傳算法設(shè)計(jì)
加入技術(shù)交流群
判斷矩陣A1、3、4、5的行向量線性不相關(guān)，秩是列數(shù)4，也就是被選中的線段個(gè)數(shù)即每個(gè)個(gè)體的基因數(shù)。個(gè)體{1、2、5、10}因?yàn)?、2、5構(gòu)成了回路，可以得到
，其判斷矩陣A1、2、5、10中對(duì)應(yīng)的3個(gè)行向量必定是同樣的關(guān)系，則這3個(gè)行向量線性相關(guān)。所以判斷矩陣A1、2、5、10的秩必然小于列數(shù)4。由矢量圖能看出，每多一條回路，判斷矩陣的秩就會(huì)減少1。當(dāng)出現(xiàn)重復(fù)編號(hào)時(shí)，如{1、1、2、5}，則有2個(gè)行向量相同，其判斷矩陣A的秩必然也小于列數(shù)4。綜上，Point[]是已知的。由Point[]可以得到Line[](如圖3(a))。任意給定4條線的個(gè)體，由Line[]和Point[]得到判斷矩陣A，如果rank(A)=M-1，則滿足3個(gè)條件(如圖3(b))；否則，該個(gè)體非法。本文引用地址：http://butianyuan.cn/article/202494.htm
3 初始種群獲取
根據(jù)上面的說明，本文在獲取初始種群時(shí)，每一個(gè)個(gè)體首先是從M(M-1)／2條線段中隨機(jī)取出M-1條。取得的方法是：
1)建立M(M-1)／2階布爾數(shù)組，數(shù)組里每個(gè)元素是假常量；
2)產(chǎn)生一個(gè)0～1的隨機(jī)數(shù)與M(M-1)／2相乘并向下取整，隨機(jī)得到一個(gè)整數(shù)n，則n∈[0，M(M-1)／2-1]；
3)將布爾數(shù)組中第n個(gè)元素替換為真常量；
4)重復(fù)2、3步直到布爾數(shù)組中有了M-1個(gè)真常量；
5)依次提取布爾數(shù)組中的每個(gè)真常量的索引值并加1。
其取得方法的框圖如圖4所示。
得到的M-1階常數(shù)數(shù)組就是一個(gè)隨機(jī)產(chǎn)生的初始個(gè)體，而且此個(gè)體直接滿足條件1和條件2。對(duì)這樣的個(gè)體進(jìn)行合法性判斷，如果不合法舍去重新產(chǎn)生新個(gè)體。如果合法保留再生成下一個(gè)個(gè)體。用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，簡(jiǎn)稱AGA)提出新的編碼方式下的遺傳策略。
式中，pc表示交叉率，Pm表示變異率，fmax表示種群最大適應(yīng)度值favg表示種群平均適應(yīng)度值，f表示在要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值，f表示要變異的個(gè)體適應(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)秀基因影響的重要方法。但本文使用的編碼方法中，如果使用簡(jiǎn)單的單點(diǎn)交叉方法，無疑很大概率上將產(chǎn)生不合法的無效子代。如圖1中的5個(gè)點(diǎn)，兩個(gè)父代{1、2、3、4}和{4、5、8、10}做交叉運(yùn)算，無論交叉點(diǎn)在哪都會(huì)產(chǎn)生含有2個(gè)4號(hào)線段的非法子代。不滿足條件1。
評(píng)論