天天看點

蟻群算法求解TSP問題

蟻群算法的第一個算法就是螞蟻系統,而螞蟻系統有三種基本模型分别是

蟻周模型、蟻密模型、蟻量模型。三種模型的實作大緻相同,主要差別是在資訊素

的更新方式上。在用螞蟻系統解決t sp問題時,蟻量模型和蟻密模型是螞蟻在建構

一條合法路徑的過程中進行資訊素的更新的,當螞蟻走過一條邊之後,就對該邊進

行資訊素的更新,即為局部更新方式。而蟻周模型是在所有螞蟻都建構了一條合

法路徑之後才對各邊進行資訊素更新的,也即全局更新方式。

  并且這三種模型中螞蟻在自己所走過的路線上釋放的資訊素的量也是有所

不同的,在蟻密模型螞蟻在自己所走過的路上釋放的資訊素是一個常量q,而在蟻

量模型中螞蟻在走過某條邊上釋放的資訊素量等于q/(該條邊的長度);在蟻周

模型中螞蟻是在完整的走過一條路線後再跟新的資訊素,是以其螞蟻在走過的每

條邊上釋放的資訊素是相等的,都等于q/(該條完整路線的總長度);

  其中蟻周模型的性能是做好的,是以用其來解決tsp問題也很友善,在

用蟻周模型解決問題時該注意的績點核心就是:

一、為每條路設定資訊素的初始量。

二、合理的設定好蟻群算法中的各種影響參數(這個直接影響最後效果)。

三、利用輪盤選賭法為每隻螞蟻選擇不重複的下一天邊。

四、在一輪結束後計算每天邊上的資訊素增量。

五、更新全局的資訊素

最後附上用蟻周模型解決tsp問題的簡單實作版本代碼及結果。

有7個城市(城市編号0到6,每兩個城市之間的距離設定為兩編号之和)的測試結果圖:

蟻群算法求解TSP問題

有10個城市(城市編号0到6,每兩個城市之間的距離設定為兩編号之和)的測試結果圖:

蟻群算法求解TSP問題