淺談旅行商問題與蟻群算法

范秋生

（黃岡職業技術學院計算機科學與技術系，湖北 黃岡 438002）

淺談旅行商問題與蟻群算法

范秋生

（黃岡職業技術學院計算機科學與技術系，湖北 黃岡 438002）

蟻群算法是繼模擬退火算法、遺傳算法、禁忌搜索算法、人工神經網絡算法等啟發式搜索算法之后的又一種應用于組合優化問題的算法。根據蟻群算法的特性，求解旅行商問題，利用仿真實驗程序對蟻群求解旅行商問題進行模擬。

蟻群算法；信息素；旅行商問題(TSP)

引言

蟻群算法就是利用群集智能解決組合優化問題的典型例子。它是繼模擬退火算法、遺傳算法、禁忌搜索(Tabu Search)算法、人工神經網絡算法等啟發式搜索算法之后的又一種應用于組合優化問題的算法[1]。

1、旅行商問題(TSP)簡介及旅行商問題描述：

給定n個城市的集合{0，1，2，…，n-1}及城市之間環游的費用 ci(j0 ≤i≤n-1，0≤j≤n-1，i≠j)或者距離。TSP問題是指找到一條經過每個城市一次且回到起點的最小費用的環游。若將每個頂點看成是圖上的節點，費用 為c連ij接頂點Vi、Vj邊上的權，則TSP問題就是在一個具有n個節點的完全圖上找到一條費用最小的Hamilton回路[1]。本文所討論的TSP問題為對稱的TSP問題，而不是非對稱的TSP問題，對于非對稱的TSP問題(ASTP)詳情訪問TSPLIB。

以下是5個城市集的TSP

圖1 -1 對稱的TSP

圖1 -2 非對稱的TSP

旅行商問題的傳統求解算法

當了解TSP問題后，我們會感覺到這種求解最優解的問題不算復雜，并且可以很快地的利用所學的傳統方法進行模擬求解。

大致算法可能如下：

(1)得到問題的規模，即城市的數量大小；……