基于LabVIEW仿真的全局最短路徑的遺傳算法設計
加入技術交流群
判斷矩陣A1、3、4、5的行向量線性不相關，秩是列數4，也就是被選中的線段個數即每個個體的基因數。個體{1、2、5、10}因為1、2、5構成了回路，可以得到
，其判斷矩陣A1、2、5、10中對應的3個行向量必定是同樣的關系，則這3個行向量線性相關。所以判斷矩陣A1、2、5、10的秩必然小于列數4。由矢量圖能看出，每多一條回路，判斷矩陣的秩就會減少1。當出現重復編號時，如{1、1、2、5}，則有2個行向量相同，其判斷矩陣A的秩必然也小于列數4。綜上，Point[]是已知的。由Point[]可以得到Line[](如圖3(a))。任意給定4條線的個體，由Line[]和Point[]得到判斷矩陣A，如果rank(A)=M-1，則滿足3個條件(如圖3(b))；否則，該個體非法。本文引用地址：http://www.104case.com/article/202494.htm
3 初始種群獲取
根據上面的說明，本文在獲取初始種群時，每一個個體首先是從M(M-1)／2條線段中隨機取出M-1條。取得的方法是：
1)建立M(M-1)／2階布爾數組，數組里每個元素是假常量；
2)產生一個0～1的隨機數與M(M-1)／2相乘并向下取整，隨機得到一個整數n，則n∈[0，M(M-1)／2-1]；
3)將布爾數組中第n個元素替換為真常量；
4)重復2、3步直到布爾數組中有了M-1個真常量；
5)依次提取布爾數組中的每個真常量的索引值并加1。
其取得方法的框圖如圖4所示。
得到的M-1階常數數組就是一個隨機產生的初始個體，而且此個體直接滿足條件1和條件2。對這樣的個體進行合法性判斷，如果不合法舍去重新產生新個體。如果合法保留再生成下一個個體。用for循環來控制種群大小。
4 適應度函數
因為目標函數是求最小值，而且D肯定大于0，所以不妨直接以目標函數的倒數作為適應度函數。
5 遺傳策略
本文基于Srinivas提出的自適應遺傳算法(Adaptive GA，簡稱AGA)提出新的編碼方式下的遺傳策略。
式中，pc表示交叉率，Pm表示變異率，fmax表示種群最大適應度值favg表示種群平均適應度值，f表示在要交叉的兩個個體中較大的適應度值，f表示要變異的個體適應度值。k1，k2，k3，k4是在0和1之間取值的常數，其中，k3和k4較大。
式(3)和式(4)是AGA根據適應度值調節后的交叉率和變異率，它較好地解決遺傳算法中全局搜索和局部搜索的平衡問題，提高了收斂速度。
5．1 雜交
雜交運算是遺傳算法擴大優秀基因影響的重要方法。但本文使用的編碼方法中，如果使用簡單的單點交叉方法，無疑很大概率上將產生不合法的無效子代。如圖1中的5個點，兩個父代{1、2、3、4}和{4、5、8、10}做交叉運算，無論交叉點在哪都會產生含有2個4號線段的非法子代。不滿足條件1。
評論