TSP_ACO
1.0.0
Ant Colony Optimization（ACO）は、Swarm Intelligenceの分野でのメタヒューリスティックな手法です。さまざまな組み合わせ最適化の問題を解決するために使用されます。
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 | 各都市の地理的な場所（緯度と経度）を分離しました。 |
| distance.txt | 都市間のユークレディアンの距離。 |
| road_distance.txt | 都市間の道路による距離。 |
| travel_time.txt | ある都市から別の都市に旅行するのに時間がかかります。 |
Ant Colony System（ACS）では、多くの人工アリが最初にランダムな都市に配置されています。各アリはツアー（TSPの実行可能な解決策）を構築します。州の移行規則（貪欲なルール）を適用することにより、次の都市を選択します。このルールは、新しいエッジの探索と蓄積された知識の搾取のバランスを提供します。
一定の量のフェロモンは、最も好ましいルートの各ステップで各アリによって堆積されます（ベストツアー）
エリート主義的アプローチを使用して、学習パラメーターを制御しようとします。最高のルート（品質）を見つけるアリは、他のアリよりも多く報われます。より多くのフェロモンがより良いルートに堆積し、その特定のツアーを重要視し、最適なソリューションを得るための時間を短縮します。
ルートの品質に基づいて堆積したフェロモンの量。
Maxminメソッドは、両方の世界を最大限に活用することを目的としています。これは、迅速な実行時間を備えた最適なソリューションに近いものです。これは、手順から堆積したフェロモンに量を変更することによって達成されます。
最初は体重が高く、迅速な学習率が得られます。体重は75％の完了まで徐々に減少します。次に、結果をGlobal Bestツアーと比較して重量を適用して微調整した場合、モデル。
各ステップの終わりに、ウェイトは最大および最小フェロモンの制限内にバインドされ、流れが迷っているのを防ぎます。
フェロモンの量は、反復の最初の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 ()ACOの助けを借りて、移動距離を最小限に抑えようとしながら、すべての都市をカバーする最適なパスを生成します。また、結果は、パスの最適化に使用されるアルゴリズムのパラメーターとエッジの重み(travel time, distance, road_distance)に依存します。
図：都市を通る最適な経路の痕跡
