TSP_ACO

Travelling Salesman Masalah Menggunakan Optimalisasi Koloni Semut

Perkenalan

Optimalisasi Koloni Ant

Ant Colony Optimization (ACO) adalah teknik meta-heuristik di bidang intelijen Swarm. Ini digunakan untuk menyelesaikan masalah optimasi kombinatorial yang berbeda.

ACO didasarkan pada perilaku koloni semut dan kemampuan pencarian mereka untuk optimasi kombinatorial. Analisis perilaku alami koloni semut menunjukkan bahwa semut bergerak di sepanjang distribusi feromon yang kaya di jalan mereka. Algoritma meniru perilaku ini.

Masalah Salesman Bepergian

Travelling Salesman Problem (TSP) adalah masalah algoritmik klasik yang berfokus pada optimasi.

Solusi yang lebih baik sering kali berarti solusi yang lebih murah, lebih pendek, atau lebih cepat.

Masalahnya menggambarkan seorang salesman yang harus bepergian di antara N -kota sehingga ia mengunjungi setiap kota sekali selama perjalanannya. Setiap kota terhubung ke kota -kota lain dan tautan memiliki bobot tetap (biaya perjalanan, jarak dll.)

Dataset

Dataset terdiri dari 225 kota di bagian barat laut dan tengah dari sub benua India.

Struktur Dataset

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

Deskripsi file

Mengajukan	Keterangan
location_ll.txt	Ruang memisahkan lokasi geo (garis lintang dan bujur) dari setiap kota.
Distance.txt	Jarak Eucledian antara kota -kota.
road_distance.txt	Jarak melalui jalan darat antara kota -kota.
travel_time.txt	Waktu untuk melakukan perjalanan dari satu kota ke kota lainnya.

Algoritma

Sistem koloni semut

Dalam sistem koloni semut (ACS), sejumlah semut buatan pada awalnya ditempatkan di kota -kota acak. Setiap semut membangun tur (solusi yang layak dari TSP). Ini memilih kota berikutnya dengan menerapkan aturan transisi negara (aturan serakah). Aturan ini memberikan keseimbangan antara eksplorasi tepi baru dan eksploitasi akumulasi pengetahuan.

Sejumlah feromon konstan disimpan oleh setiap semut pada setiap langkah pada rute yang paling menguntungkan (Tur Terbaik)

Elitis

Menggunakan pendekatan elitis, kami mencoba mengontrol parameter pembelajaran. Semut yang menemukan rute (kualitas) terbaik lebih dihargai daripada semut lainnya. Lebih banyak feromon disimpan pada rute yang lebih baik, memberikan pentingnya tur tertentu dan mengurangi waktu untuk mendapatkan solusi yang optimal.

Jumlah feromon yang disimpan berdasarkan kualitas rute.

Maxmin

Metode Maxmin bertujuan untuk mendapatkan yang terbaik dari kedua dunia, solusi dekat dengan optimal dengan waktu eksekusi yang cepat. Ini dicapai dengan memvariasikan jumlah feromon yang disimpan melalui langkah -langkah.

Awalnya beratnya tinggi, memberikan tingkat pembelajaran yang cepat. Beratnya secara bertahap berkurang hingga selesai 75%. Kemudian model jika disesuaikan dengan menerapkan bobot dengan membandingkan hasil dengan tur terbaik global .

Pada akhir setiap langkah, bobot terikat dalam batas feromon maks dan min untuk mencegah solusi untuk menyesali.

Jumlah feromon secara bertahap berkurang untuk 75% iterasi pertama. Maka jumlahnya tergantung pada kualitasnya dibandingkan dengan tur terbaik.

Parameter

 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"
}

Penggunaan

 # 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 ()

Hasil

Dengan bantuan ACO, kami menghasilkan jalur optimal untuk menutupi semua kota sambil mencoba meminimalkan jarak perjalanan. Juga hasilnya tergantung pada parameter algoritma dan bobot tepi (travel time, distance, road_distance) yang digunakan untuk mengoptimalkan jalur.

Gambar: Jejak jalur optimal melalui kota -kota