Jufri, Ahmad (2014) Modifikasi Ant Colony Optimization (ACO) untuk Penentuan Rute Terpendek dari dan ke Kabupaten/Kota di Jawa. Magister thesis, Universitas Brawijaya.
Abstract
Secara umum ada dua pendekatan yang banyak digunakan untuk menyelesaikan permasalahan pencarian jalur terpendek, yaitu deterministik dan probabilistik. ACO merupakan salah satu metode dengan pendekatan probabilistik yang terbukti mampu menyelesaikan permasalahan TSP. Namun salah satu kelemahan dari metode ini adalah kecepatan komputasi. Dalam penelitian ini dilakukan modifikasi algoritma ACO untuk menentukan jalur terpendek dari dan ke Kabupaten/Kota di Jawa. Tujuan penelitian ini adalah meningkatkan kinerja Algoritma ACO, baik dari sisi waktu komputasi maupun pemakaian memori. Fokus dari penelitian ini adalah modifikasi terhadap jumlah Semut yang ditugaskan untuk melakukan perjalanan dari sumber ke tujuan, modifikasi pada intensitas jejak Semut, dan modifikasi probabilitas untuk pemilihan kota berikutnya. Hasil penelitian ini menunjukkan bahwa memodifikasi probabilitas pemilihan kota berikutnya dan intensitas jejak Semut dapat menjaga kualitas solusi yang dihasilkan Algoritma Modifikasi ACO dengan prosentase 99,8% terhadap Algoritma ACO. Dan Modifikasi ACO rata-rata lebih efisien dari Algoritma ACO dengan prosentase 7%. Selain itu waktu yang dibutuhkan untuk menghasilkan rute terpendek rata-rata 3 kali lebih cepat daripada Algoritma ACO yang asli.
English Abstract
In general there are two approaches are widely used to solve the problems of finding the shortest path , ie deterministic and probabilistic . ACO is one of the methods with probabilistic approach proven to solve the problems of TSP . However, one drawback of this method is the computational speed . In this research a modified ACO algorithm to determine the shortest path from and to the District/City in Java . The purpose of this research is to improve the performance of ACO algorithms , both in terms of computing time and memory consumption . The focus of this research is a modification to the number of ants that is assigned to travel from source to destination , modifications to the intensity of the ant trail , and modification of the probability for the next city to be visit . The results of this research show that modifying the probability of the next to be visit and intensity trace Ants can maintain the quality of the resulting solution Modified ACO algorithm with the percentage of 99.8 % of the ACO algorithm . And Modified ACO average more efficient than the ACO algorithm with the percentage of 7 %. In addition, the time required to generate the shortest path on average three times faster than the original ACO algorithm .
| Item Type: | Thesis (Magister) |
|---|---|
| Identification Number: | TES/519.7/JUF/m/041408082 |
| Subjects: | 500 Natural sciences and mathematics > 519 Probabilities and applied mathematics > 519.7 Programming |
| Divisions: | S2/S3 > Magister Teknik Elektro, Fakultas Teknik |
| Depositing User: | Endro Setyobudi |
| Date Deposited: | 07 Jan 2015 16:45 |
| Last Modified: | 07 Jan 2015 16:45 |
| URI: | http://repository.ub.ac.id/id/eprint/157492 |
Actions (login required)
 |
View Item |