Pencarian Jalur Terpendek Travelling Salesman Problem Menggunakan Algoritma Ant Colony System
| Main Author: | Fauzi, Sofwan |
|---|---|
| Format: | Thesis PeerReviewed |
| Terbitan: |
Universitas Komputer Indonesia
, 2010
|
| Subjects: | |
| Online Access: |
http://repository.unikom.ac.id/16551/ http://elib.unikom.ac.id/gdl.php?mod=browse&op=read&id=jbptunikompp-gdl-sofwanfauz-22654 |
Daftar Isi:
- Persoalan pencarian rute terpendek dari sejumlah node pada penelitian ini termasuk pada persoalan optimasi travelling salesman problem, TSP kurva tertutup yang node asal dan node tujuan telah ditentukan. Setiap node hanya boleh dilalui satu kali. Bila dipandang dari sudut komputasinya persoalan ini sepintas memang tampak sederhana. Namun, jika jumlah node cukup banyak maka akan sulit dan membutuhkan waktu yang cukup lama. Salah satu algoritma yang paling cocok untuk menyelesaikan masalah ini adalah algoritma Ant Colony System, ACS. ACS terinspirasi berdasarkan perilaku koloni semut yang meninggalkan sarang untuk mencari makanan dan harus kembali ke sarang mereka. Pada saat berjalan, semut meninggalkan pheromone yang berfungsi sebagai informasi untuk semut berikutnya. Pada penelitian ini akan dibuat program ACS untuk mencari rute terpendek dari n-buah node dan membandingkan keoptimuman ACS dengan algoritma genetik, AG. Beberapa pengujian telah dilakukan pada program ACS dan AG dengan menginputkan hingga 75 node. Dari hasil pengujian, dapat disimpulkan bahwa ACS terbukti lebih optimum dibandingkan dengan AG.