Eksperimen Algoritma Heuristik ACO pada Dataset TSPLIB

"Penelitian yang kuat membutuhkan data yang kredibel dan terstandardisasi. TSPLIB menyediakan landasan ilmiah yang solid untuk menguji ketangguhan sebuah algoritma."

1️⃣ Mengenal TSPLIB

📌 Apa Itu TSPLIB?

TSPLIB adalah singkatan dari Traveling Salesman Problem Library. Ini merupakan sebuah pustaka dataset yang terstandardisasi dan diakui secara global, berisi berbagai contoh masalah untuk Traveling Salesman Problem (TSP) dan varian-variannya. Diciptakan oleh Gerhard Reinelt, TSPLIB menjadi fondasi bagi para peneliti dan praktisi di bidang riset operasi dan ilmu komputer, menyediakan basis data yang konsisten untuk perbandingan algoritma.

Secara historis, TSPLIB dikelola oleh Universitas Heidelberg. Namun, komunitas pengembang modern telah membuatnya lebih mudah diakses melalui repositori seperti GitHub, yang memungkinkan peneliti untuk mengunduh dan mengintegrasikan dataset dengan cepat ke dalam proyek mereka, mempercepat siklus eksperimen dan pengembangan. Silakan download di : https://github.com/mastqe/tsplib

2️⃣ Dataset yang Digunakan sebagai Benchmark

📌 Pilihan Dataset untuk Uji Ketangguhan Algoritma

Kami menggunakan tiga dokumen dari TSPLIB sebagai benchmark: 'pr264.tsp', 'att532.tsp', dan 'rat575.tsp'. Ketiganya dipilih karena secara kolektif merepresentasikan tantangan yang beragam, menjadikannya pilihan yang sangat baik untuk menguji ketangguhan sebuah algoritma.

pr264.tsp: Masalah dengan 264 simpul. Tipe jaraknya adalah EUC_2D (Euclidean 2D standar). Ukurannya yang sedang dan metrik jarak yang jujur menjadikannya kasus uji yang ideal.
att532.tsp: Populer karena keunikannya, problem ini memiliki 532 simpul. Tipe jaraknya adalah ATT, sebuah fungsi "pseudo-Euclidean" yang dimodifikasi. Menggunakan dataset ini menguji kemampuan algoritma untuk menangani fungsi jarak non-standar.
rat575.tsp: Dataset ini berukuran lebih besar, dengan 575 simpul. Tipe jaraknya adalah EUC_2D. Ukurannya yang lebih besar menjadikannya ujian yang baik untuk skalabilitas dan efisiensi sebuah algoritma.

3️⃣ Hasil Eksperimen: Performa ACO pada Dataset pr264.tsp

Tabel Hasil (Data untuk pr264.tsp)

Eksperimen	Bobot Total	Jumlah Edge	Gap dari Kruskal
1. Kruskal MST (Ground Truth)	41142.24	263	0%
2. ACO TSP Path Same (β=2, ρ=0.5)	49247.37	263	19.70%
3. ACO TSP Path Tuned (β=2, ρ=0.3)	49220.11	263	19.63%
4. ACO MST Same (β=2, ρ=0.5)	42534.20	263	3.38%
5. ACO MST Tuned (β=1, ρ=0.1)	302434.04	263	635.09%
6. ACO TSP Path Deg3 Same (β=2, ρ=0.5, max_deg=3)	50718.01	263	23.27%
7. ACO TSP Path Deg3 Tuned (β=2, ρ=0.3, max_deg=3)	50122.95	263	21.83%
8. ACO MST Deg3 Same (β=2, ρ=0.5, max_deg=3)	41684.61	263	1.32%
9. ACO MST Deg3 Tuned (β=1, ρ=0.1, max_deg=3)	283589.90	263	589.29%

4️⃣ Analisis Hasil dan Kesimpulan

✅ Insight dari Perbandingan Kruskal vs. ACO

Kruskal sebagai Ground Truth: Algoritma Kruskal (nilai 41142.24) memberikan solusi optimal yang menjadi tolok ukur untuk semua perbandingan.
Performa ACO-TSP: Baik dengan parameter standar maupun yang disetel, ACO-TSP menunjukkan gap yang signifikan (sekitar 20%) dari solusi optimal. Ini wajar, mengingat masalah TSP secara intrinsik jauh lebih sulit daripada MST.
Keunggulan ACO-MST: Algoritma ACO-MST dengan parameter standar ('Same') memberikan hasil yang jauh lebih baik dengan gap hanya 3.38%. Ini menunjukkan bahwa ACO bekerja sangat efektif untuk masalah MST yang lebih terstruktur.
Efek Batasan Derajat: Ketika batasan derajat (max_deg=3) ditambahkan, nilai gap pada kedua algoritma (TSP dan MST) meningkat. Ini menunjukkan bahwa batasan tersebut memperkenalkan kompleksitas tambahan pada masalah, yang berdampak pada kinerja algoritma.
Penyetelan Parameter yang Buruk: Hasil untuk ACO MST Tuned (gap 635.09%) menunjukkan pentingnya penyetelan parameter yang benar. Penyetelan yang salah dapat secara drastis menurunkan kinerja algoritma.

💡 Mengapa ACO-MST Bisa Sangat Mendekati Kruskal?

Meskipun ACO bersifat probabilistik dan tidak menjamin solusi optimal, dalam kasus-kasus tertentu seperti pada 'ACO MST Deg3 Same', hasilnya bisa sangat mendekati Kruskal (gap 1.32%). Ini terjadi karena:

Struktur masalah MST yang lebih sederhana, memandu semut untuk memilih edge dengan bobot rendah secara konsisten.
Parameter yang tepat memungkinkan algoritma dengan cepat menkonvergensikan solusi yang hampir optimal, karena probabilitas untuk memilih edge yang benar sangat dominan.