基于蟻群算法的旅行商問題的研究

李輝

摘 要：群居性昆蟲行為的研究為計算機科學家提供了設計分布式控制和優化算法的有力方法。對以蟻群算法為代表的群集智能的研究已經逐漸成為一個研究熱點。蟻群算法在實際的生活中有很大的用處，比如求解旅行商問題，文章介紹了一種求解復雜TSP的蟻群算法，闡述了該算法的基本原理及實現過程，并且在本文中嘗試用編碼的形式將基本蟻群算法應用到求解旅行商問題中去。

關鍵詞：基本蟻群算法；信息素；旅行商問題

1 意義和目標

近年來，許多學者對蜜蜂、螞蟻等一些昆蟲的行為進行了大量的研究，特別是他們的集體行為，而這些動物一般都是群居昆蟲。每個昆蟲的能力雖然十分有限，但昆蟲群體的能力卻遠遠超過所有個體能力的總和。比如，螞蟻群可以快速建立起巢穴與食物之間的最短路徑。令人驚奇的是，每只螞蟻并不直接比較每條路徑，而僅僅只是遵守信息素釋放/跟隨規則就能找到最佳路徑。螞蟻群的這種能力很自然地引起了計算機科學家的興趣。旅行商問題的定義并不統一，一般廣泛認為這樣定義：假若有多個城市，而這多個城市的距離為已知條件，這個距離也可以理解為多個城市之間的開銷，若要得到某一個旅行商走遍所有城市的一條回路，但必須滿足所有城市之間的距離的和為最小，也可以是城市之間的開銷達到最小值的這樣的一條回路。求解TSP問題的算法較多，但文章使用基本蟻群算法來解決旅行商問題。……