胡明 蔡傳軍 童緒軍
摘 要:為提升蟻群算法的尋優求解能力,文章使用Logistic函數對遺傳算法進行了優化。在優化后的遺傳算法中,對蟻群進行了交叉和變異操作,以實現蟻群算法的智能優化。為驗證改進算法的性能,選擇了100個城市進行尋優測試。實驗結果表明,在采用遺傳算法優化后,該方法使種群平均適應度得到了較好的提升。在尋優求解過程中,蟻群算法中螞蟻信息素的分布密集濃度明顯增加,具備較好的收斂性。同時,在相同迭代次數下,該方法獲得的尋優路徑也最短,具有較為顯著的應用效果。
關鍵詞:遺傳算法;蟻群算法;交叉變異;遺傳算子
中圖分類號:TB472-4 文獻標識碼:A 文章編號:2095-9699(2023)06-0016-05
蟻群算法是群集智能與演化算法中的一種[1-2],用于模擬螞蟻群在尋找巢穴到食物源之間最短路徑的過程。蟻群算法通過模擬螞蟻個體之間的協作來解決復雜的優化問題。在實際應用中,蟻群算法具有并行性和正反饋性等優點。然而,蟻群算法在應用時需要較多的參數[3],且缺乏先驗知識指導,導致初始信息素匱乏,尋找最佳路徑的時間較長,并且容易出現收斂過早或陷入局部極值的情況[4-5]。
為避免蟻群算法出現上述情況,許多學者研究了優化蟻群算法的方法。例如,侯軍燕等[6]人提出了一種將評價權系數和權重系數引入蟻群算法的布局優化方法,通過添加優化參數來實現蟻群算法的智能優化。薛波等[7]人改進了蟻群算法與最短路優化方法,利用反饋搜索智能優化方法調整蟻群算法的全局信息素更新規則,實現蟻群算法的智能優化。雖然這兩種方法都能實現蟻群算法的智能優化,但都存在運算時間過長的問題[8]。為了更好地提升蟻群算法的應用效果,本文設計了一種基于遺傳算法的智能蟻群算法優化方法。
1 智能蟻群算法優化設計
1.1 蟻群算法運行機制
在自然環境中,螞蟻的視力有限,但它們能夠以最短路徑找到食物源,即使路徑中存在遮擋物,螞蟻仍然能夠繞過它們并到達食物源。單個螞蟻在尋找食物時行為簡單,但整個蟻群通過螞蟻之間的協作可以完成復雜的任務[9]。研究表明,在蟻群運動過程中,螞蟻會釋放信息素,并通過信息素的濃度來引導螞蟻朝著信息素濃度高的地方移動,最終到達食物源。圖1展示了蟻群路徑搜索的原理和機制。
以遺傳算法種群的平均適應度作為衡量指標,測試優化前后適應度曲線的趨勢,結果如圖2所示。優化后的遺傳算法種群的平均適應度值要高于優化前的,這表明本文方法對遺傳算法進行了有效的優化處理。
以7個城市問題的信息素分布作為衡量指標,給出智能優化后蟻群算法尋優求解時的信息素分布圖,結果如圖3所示。優化后的蟻群算法在尋優求解時,城市3-6和3-5之間的信息素濃度明顯不同于其他城市之間,可有效輸出最優解。
驗證本文方法尋優能力,以尋優最短距離作為指標,測試智能優化前后算法路徑的變化情況,結果如圖4所示。分析圖4可知,智能優化后的蟻群算法螞蟻行走路徑簡單且沒有交叉繞遠的現象,而未經優化的蟻群算法螞蟻行走路徑明顯較多,這說明本文方法智能優化的蟻群算法可以選擇最短路徑,實現最優解。
進一步驗證尋優求解效果,以最短路徑作為指標,在不同迭代次數測試最短路徑的數值。為了充分比較實驗結果,同時與文獻[6][7]的方法進行對比實驗。實驗結果如表1所示,三種方法的最短路徑數隨著迭代次數的增加而增加,但在迭代次數相同的情況下,本文方法得到的最優路徑始終低于文獻[6]和文獻[7]的方法,這說明本文方法獲取的尋優結果最佳。
以時間復雜度作為指標,驗證三種方法在應用時的復雜性,結果如表2所示。結果表明,本文方法在應用過程中尋找最優解速度較快,所需時間較短。
測試三種方法在應用過程中的收斂性,結果如圖5所示。在三種方法中,本文方法在尋優求解時其損失函數隨著迭代次數的增加而降低,降低幅度最大。當迭代次數超過60次后,本文方法尋優求解的損失函數值趨近于0,說明本文方法得到的結果最為準確。
3 結論
文章針對蟻群算法存在的收斂和容易陷入局部極值情況,設計一種基于遺傳算法的智能優化蟻群算法,通過對蟻群進行交叉和變異的操作來更新蟻群位置,使其能夠準確快速地尋找最優解。經過實驗驗證,文中所使用的方法具有良好的應用效果,未來可以有效解決TSP問題。
參考文獻:
[1]周天清,胡海琴,曾新亮. NOMA-