分層遞進的改進聚類蟻群算法解決TSP問題
摘要：隨著旅行商問題(TSP)規模的增大,傳統蟻群算法的運行時間會增大,算法的解精度也會降低,并且算法很容易陷入局部最優的情況。提出的分層遞進算法的思想源于分工合作的產品線組裝流程,首先利用改進的密度峰聚類算法確定拐點,從而選舉出聚類中心,根據聚類中心確定包含的數據點;其次將初始的TSP問題分割成較小的簇,這些簇稱為二類TSP問題;再經自適應信息素更新策略的蟻群算法運算,找出每個簇的最優解,進一步將簇與簇之間相近的節點構成的邊斷開;然后兩簇之間斷開的節點重組成全局最優解;最終通過局部優化策略對重組的優化解進一步優化,從而在保證算法解質量的前提下有效地縮短了運行時間。從TSPLIB中選取小規模、大規模基準案例,通過Matlab仿真驗證了改進算法具有更好的魯棒性,特別是在大規模基準案例中顯著地減少了算法運行時間。
注: 保護知識產權,如需閱讀全文請聯系計算機科學與探索雜志社
相關推薦
更多
