Perpustakaan judul masih dalam tahap pengembangan, admin siap menampung kritik dan saran
Pencarian Jalur Terpendek Travelling Salesman Problem Menggunakan Algoritma Ant Colony System
Sofwan Fauzi NIM. (2010) | Tugas Akhir | Teknik Komputer , Teknik Komputer
Bagikan
Ringkasan
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.
Ringkasan Alternatif
Shortest path search problem from a number of nodes in this study includes the optimization Travelling Salesman Problem, TSP curve closed which node of origin and destination node is the same. Each node may only pass once. When viewed from a computational point of this issue at a glance it looks simple. However, if the number of nodes it will be difficult enough and requires a long time.
One of the most appropriate algorithms to solve this problem is Ant Colony System, ACS. ACS is inspired by the behavior of ant colonies that leave the nest for food and had to return their nests. At the time of walking, ants leave a pheromone that serves has information for the next ants. In this research, the ACS program will be made to find the shortest route from n-node and comparing the ACS with genetic algorithms, AG.
Some tests have been performed on the ACS and AG to enter up 75 nodes. From the test results, it can be concluded that the ACS will prove more optimal than AG.