TSP_ACO下載TSP_ACO源代碼下載

TSP_ACO

其他源碼

1.0.0

下載

使用螞蟻殖民地優化的旅行推銷員問題

介紹

螞蟻菌落優化

螞蟻菌落優化（ACO）是蜂群智能領域的一種元熱療法技術。它用於解決不同的組合優化問題。

ACO基於螞蟻菌落的行為及其對組合優化的搜索能力。對螞蟻菌落的自然行為的分析表明，螞蟻沿其路徑上豐富的信息素分佈移動。該算法模仿了這種行為。

旅行推銷員問題

旅行推銷員問題（TSP）是一個側重於優化的經典算法問題。

更好的解決方案通常意味著更便宜，更短或更快的解決方案。

問題描述了一位推銷員必須在N城市之間旅行，以便他在旅途中一次訪問每個城市。每個城市都連接到其他城市，鏈接具有固定的權重（旅行成本，距離等）

數據集

該數據集由印度亞洲大陸西北和中部地區的225個城市組成。

數據集結構

 tsp dataset/
    ├── distance.txt
    ├── location_ll.txt
    ├── location_map.jpg
    ├── location_map_satellite_image.jpg
    ├── names.txt
    ├── road_distance.txt
    └── travel_time.txt

文件說明

文件	描述
location_ll.txt	每個城市的空間分開的地理位置（緯度和經度）。
距離	城市之間的Eucledian距離。
road_distance.txt	城市之間的道路距離。
travel_time.txt	時間花時間從一個城市到另一個城市。

演算法

螞蟻菌落系統

在螞蟻菌落系統（ACS）中，最初將許多人造螞蟻放置在隨機城市。每個螞蟻都會建立遊覽（TSP的可行解決方案）。它通過應用州過渡規則（貪婪規則）來選擇下一個城市。該規則在探索新邊緣與累積知識的開發之間提供了平衡。

每個螞蟻在最有利的路線上，每個螞蟻都沉積恆定的信息素（最佳旅行）

精英

使用精英方法，我們嘗試控制學習參數。找到最佳路線（質量）的螞蟻得到了比其他螞蟻的獎勵。更多的信息素存放在更好的路線上，重視該特定的旅行，並減少了獲得最佳解決方案的時間。

根據路線質量沉積的信息素量。

MAXMIN

Maxmin方法旨在獲得兩全其美的最佳狀態，這是一個快速執行時間的接近最佳解決方案。這是通過改變通過步驟沉積的信息素的數量來實現的。

最初，重量很高，可以快速學習率。重量逐漸減少至75％的完成。然後，如果通過將結果與全球最佳巡迴賽進行比較來施加權重進行微調。

在每個步驟的末尾，權重綁定在最大和最小信息素限制內，以防止解決方案誤入歧途。

對於前75％的迭代，信息素量逐漸減少。然後，與最佳旅行相比，金額取決於質量。

參數

 params = {
    '_colony_size' : "number of ants in the colony"  ( default = 15 ),
    '_steps' : "iteration to run through" ( default = 50 ),
    '_mode' : "mode of algorithm to run the model"
}

用法

 # Import model
from aco_tsp import SolveTSPUsingACO

# Setup parameters
_colony_size = 15
_steps = 50

# Select mode
# ['ACS', 'Elitist', 'MaxMin']
_mode = 'ACS'

# Nodes (latitude and longitude)
_nodes = [( 20.05961 , 77.949783 ), ( 17.075451 , 74.628664 ), ..., ( 19.4133545 , 80.0059101 )]
s
# Model setup and run
model = SolveTSPUsingACO (
    mode = _mode ,
    colony_size = _colony_size ,
    steps = _steps ,
    nodes = _nodes
)

runtime , distance = model . run ()