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 | 각 도시의 공간 분리 지리 위치 (위도 및 경도). |
| distance.txt | 도시들 사이의 유체 거리. |
| Road_distance.txt | 도시 사이의 도로에 의한 거리. |
| Travel_Time.txt | 한 도시에서 다른 도시로 여행하는 데 시간이 걸립니다. |
개미 콜로니 시스템 (ACS)에서, 다수의 인공 개미가 처음에는 무작위 도시에 배치됩니다. 각 개미는 투어 (TSP의 실행 가능한 솔루션)를 구축합니다. 국가 전환 규칙 (욕심 많은 규칙)을 적용하여 다음 도시를 선택합니다. 이 규칙은 새로운 가장자리 탐색과 누적 된 지식의 착취 사이의 균형을 제공합니다.
일정한 양의 페로몬은 가장 유리한 경로에서 각 단계에서 각 개미에 의해 퇴적됩니다 (최고의 투어).
Elitist 접근법을 사용하여 학습 매개 변수를 제어하려고합니다. 최고의 경로 (품질)를 찾는 개미는 다른 개미보다 더 많은 보상을받습니다. 더 많은 페로몬이 더 나은 경로에 퇴적되어 특정 투어에 중요성을 제공하고 최적의 솔루션을 얻는 시간을 줄입니다.
경로의 품질에 기초하여 퇴적 된 페로몬의 양.
Maxmin Method는 빠른 실행 시간이있는 최적의 솔루션에 가깝습니다. 이것은 단계를 통해 퇴적 된 페로몬에 대한 양을 변화시킴으로써 달성된다.
처음에는 체중이 높아서 빠른 학습 속도를 제공합니다. 체중은 75% 완료까지 점차 감소합니다. 그런 다음 결과를 Global Best Tour 와 비교하여 가중치를 적용하여 미세 조정 된 모델.
각 단계의 끝에서, 무게는 최대 및 최소 페로몬 제한 내에 결합되어 유행을 실행하는 용액을 방지합니다.
페로몬의 양은 반복의 처음 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) 에 따라 다릅니다.
그림 : 도시를 통한 최적의 경로의 흔적
