Budi, Penemuan Jalur Terpendek Dengan…73
PENEMUAN JALUR TERPENDEK DENGAN ALGORITMA ANT COLONY
Budi Triandi Dosen Teknik Informatika STMIK Potensi Utama STMIK Potensi Utama, Jl.K.L Yos Sudarso Km 6,5 No.3-A Tanjung Mulia Medan Email :
[email protected]
ABSTRACT Currently, the population in large cities grew dense. Population density often makes the flow of traffic to a standstill. While in real life - the day often made the trip from one region to another by considering the time and cost efficiency, a theme that will be discussed in this invention paper Shortest Path Algorithm using Ant Colony (colony of ants). Ant Colony algorithm was adopted from the behavior of ant colonies, known as the system of ants, ant colonies are naturally able to find the shortest route on their way from nest to food source places. Colony of ants can find shortest route between the nest and food sources based on the trajectory of footprints that have been passed. The more ants through a trajectory, it will be more clearly ex-footprint. The end result of this discussion is the algorithm that is used to determine the shortest path to find the destination city as an alternative route. Keywords: colony of ants, shortest path, alternative route ABSTRAK Saat ini, jumlah penduduk di kota besar semakin bertambah padat. Padatnya penduduk sering membuat arus lalu lintas menjadi macet. Sementara dalam kehidupan sehari – hari sering sekali dilakukan perjalanan dari suatu daerah ke daerah lain dengan mempertimbangkan efisiensi waktu dan biaya, tema yang akan dibahas pada makalah ini Penemuan Jalur Terpendek dengan menggunakan Algoritma Ant Colony (koloni semut). Algoritma Ant Colony diadopsi dari perilaku koloni semut yang dikenal sebagai sistem Semut, Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Koloni semut dapat menemukan rute terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada lintasan yang telah dilalui. Semakin banyak semut yang melalui suatu lintasan, maka akan semakin jelas bekas jejak kakinya. Hasil akhir dari pembahasan ini adalah algoritma yang digunakan mampu menetukan jalur terpendek untuk menemukan kota tujuan sebagai rute alternatif. Kata Kunci : koloni semut, jalur terpendek, jalur alternatif
PENDAHULUAN Saat ini, jumlah penduduk di kota besar semakin bertambah padat. Padatnya penduduk sering membuat arus lalu lintas menjadi macet. Sementara dalam kehidupan sehari – hari sering sekali dilakukan perjalanan dari suatu daerah ke daerah lain dengan mempertimbangkan efisiensi waktu dan biaya. Untuk itu, diperlukan ketepatan dalam menentukan jalur terpendek antar satu daerah ke daerah lain. Hasil penentuan jalur terpendek akan menjadi pertimbangan dalam pengambilan keputusan untuk menentukan jalur yang akan ditempuh. Hasil yang didapat juga memerlukan keakuratan dan kecepatan dengan bantuan komputer.
74. CSRID Journal, Vol.4 No.2 Juni 2012, Hal. 73 - 80
Secara umum, pencarian jalur terpendek dibagi menjadi dua metode yaitu metode Konvensional dan metode Heuristik. Metode Konvensional lebih mudah dipahami dari pada metode Heuristik. Tetapi jika dibandingkan, hasil metode Heuristik lebih bervariasi dan waktu yang diperlukan lebih singkat. Metode Heuristik terdiri dari berbagai macam metode. Salah satunya adalah Algoritma Ant Colony ( Koloni Semut ). Ant Colony diambil dari prilaku koloni semut dalam menemukan jalur terpendek antara sarang dengan sumber makanan. Ant Colony diadopsi dari perilaku koloni semut yang dikenal sebagai sistem Semut (Dorigo, 1996). Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Koloni semut dapat menemukan rute terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada lintasan yang telah dilalui. Semakin banyak semut yang melalui suatu lintasan, maka akan semakin jelas bekas jejak kakinya. Hal ini akan menyebabkan lintasan yang dilalui semut dalam jumlah sedikit, semakin lama akan semakin berkurang kepadatan semut yang melewatinya, atau bahkan akan tidak dilewati sama sekali. Dan sebaliknya, lintasan yang dilalui semut dalam jumlah banyak, semakin lama akan semakin bertambah kepadatan. Mengingat Ant Colony sangat tepat dalam menemukan jalur terpendek, maka penulis mencoba menerapkan Algoritma Ant Colony dalam mencari jalur terpendek. Jalur Terpendek ( Shortest Path ) Jalur terpendek adalah suatu jaringan pengarahan perjalanan dimana seseorang pengarah jalan ingin menentukan jalur terpendek antara dua kota, berdasarkan beberapa jalur alternatif yang tersedia, dimana titik tujuan hanya satu ( sumber : Muttakhiroh, I’ing. (2007) ). Gambar 1 menunjukkan suatu graf ABCDEFG yang berarah dan tidak berbobot.
Gambar 1. Graf ABCDEFG ( Sumber : Muttakhiroh, I’ing. (2007) )
Pada dasarnya permasalahan pencarian jalur terpendek antar kota merupakan pencarian jalur terpendek antar titik yang telah diketahui koordinatnya. Dengan mengetahui konsep pencarian jalur terpendek antar titik, untuk selanjutnya dapat diterapkan pada pencarian jalur terpendek pada berbagai kota yang ingin diketahui. Contoh kasus yang akan diambil adalah pencarian jalur terpendek antara titik A dan titik G. Terdapat dua jenis kasus yang bisa diturunkan dari gambar di atas. Kasus pertama adalah mengetahui jarak antar node yang ditunjukkan dengan garis penghubung antar titik. Kasus yang kedua adalah dengan dengan mengetahui koordinat titik saja. Pada gambar 1, misalkan kita dari kota A ingin menuju Kota G. Untuk menuju kota G, dapat dipilih beberapa jalur yang tersedia : A→B→C→D→E→G A→B→C→D→F→G A→B→C→D→G A→B→C→F→G A→B→D→E→G A→B→D→F→G A→B→D→G A→B→E→G A→C→D→E→G A→C→D→F→G A→C→D→G A→C→F→G
Budi, Penemuan Jalur Terpendek Dengan…75
Pencarian Jalur Terpendek Secara umum, pencarian jalur terpendek dapat dilakukan dengan menggunakan dua metode, yaitu metode konvensional dan metode heuristik. Metode konvensional diterapkan dengan perhitungan matematis biasa, sedangkan metode heuristik diterapkan dengan perhitungan kecerdasan buatan ( sumber : http://journal.uii.ac.id/index.php/Snati/article/view/1623/1398 ). 1. Metode konvensional adalah metode yang menggunakan perhitungan matematis biasa. Ada beberapa metode konvensional yang biasa digunakan untuk melakukan pencarian jalur terpendek, diantaranya: algoritma Djikstra, algoritma Floyd-Warshall, dan algoritma BellmanFord 2. Metode Heuristik adalah sub bidang dari kecerdasan buatan yang digunakan untuk melakukan pencarian dan optimasi. Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam permasalahan optimasi, diantaranya algoritma genetika, algoritma semut, logika fuzzy, jaringan syaraf tiruan, pencarian tabu, simulated annealing, dan lain-lain. Namun pada kerja praktek ini hanya dibatasi dengan menggunakan metode algoritma semut. Sejarah Algoritma Semut Algoritma Semut diadopsi dari perilaku koloni semut yang dikenal sebagai sistem semut (Dorigo, 1996) yang merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik. Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Koloni semut dapat menemukan rute terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada lintasan yang telah dilalui. Semakin banyak semut yang melalui suatu lintasan, maka akan semakin jelas bekas jejak kakinya. Hal ini akan menyebabkan lintasan yang dilalui semut dalam jumlah sedikit, semakin lama akan semakin berkurang kepadatan semut yang melewatinya, atau bahkan akan tidak dilewati sama sekali. Sebaliknya lintasan yang dilalui semut dalam jumlah banyak, semakin lama akan semakin bertambah kepadatan semut yang melewatinya, atau bahkan semua semut akan melalui lintasan tersebut. Gambar 2 menujukkan perjalanan semut dalam menemukan jalur terpendek dari sarang ke sumber makanan.
(a)
(b)
(c)
Gambar 2. Perjalanan Semut Menemukan Sumber Makanan ( Sumber : Wardy, I. S. (2007) )
Pada gambar 2 dapat dijelaskan bahwa pada gambar 2(a), semut menemukan sumber makanan dan menelusuri jalan secarak acak. Setelah sampai ke sumber makanan, semut kembali ke sarang dengan meninggalkan jejak kaki (femoron). Pada gambar 2(b) dapat dilihat semut – semut telah membentuk beberapa jalur untuk mencari jalur terdekat dari sarang ke sumber makanan. Bahkan pada gambar 2(b) sudah tampak jalur terdekat ke sumber makanan ditandai dengan warna orange tua dan agak tebal. Pada gambar 2(c), semut – semut sudah menemukan jalur terdekat dari sarang ke sumber makanan. Pencarian Jalur Terpendek dengan Algoritma Semut Dalam pencarian jalur terpendek dengan algoritma semut, diperlukan beberapa variabel dan langkah - langkah untuk menentukan jalur terpendek ( sumber : Jamilah, Euis Widiani. (2005), yaitu :
76. CSRID Journal, Vol.4 No.2 Juni 2012, Hal. 73 - 80
Langkah 1 : a. Inisialisasi harga parameter-parameter algoritma. Parameter-parameter yang di inisialisasikan adalah : 1. Intensitas jejak semut antar kota dan perubahannya (τij) 2. Banyak kota (n) termasuk koordinat (x,y) atau jarak antar kota (dij) 3. Kota berangkat dan kota tujuan 4. Tetapan siklus-semut (Q) 5. Tetapan pengendali intensitas jejak semut (α), nilai α ≥ 0 6. Tetapan pengendali visibilitas (β), nilai β ≥ 0 7. Visibilitas antar kota = 1/dij (ηij) 8. Banyak semut (m) 9. Tetapan penguapan jejak semut (ρ) , nilai ρ harus > 0 dan < 1 untuk mencegah jejak pheromone yang tak terhingga. 10. Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan, sedangkan τij akan selalu diperbaharui harganya pada setiap siklus algoritma mulai dari siklus pertama (NC=1) sampai tercapai jumlah siklus maksimum (NC=NCmax) atau sampai terjadi konvergensi. b. Inisialisasi kota pertama setiap semut. Setelah inisialisasi τij dilakukan, kemudian m semut ditempatkan pada kota pertama tertentu secara acak. Langkah 2 : Pencatatan kota – kota yang dilalui oleh objek semut. Setiap objek semut yang melakukan pencarian kota tujuan akan mencatat nama kota – kota yang dilaluinya sehingga kita dapat mengetahui jalur perjalanan semut. Kota awal merupakan kota yang pertama kali dicatat. Langkah 3 : Penyusunan rute kunjungan setiap semut ke setiap kota. Sebelum melakukan pemilihan kota tujuan dalam menelusuri kota, dibuat suatu daftar hubungan antar kota. Daftar hubungan kota ini berisikan kota – kota yang memiliki hubungan kota asal perjalanan. Koloni semut yang sudah terdistribusi ke sejumlah atau setiap kota, akan mulai melakukan perjalanan dari kota pertama masing-masing sebagai kota asal dan salah satu kota lainnya sebagai kota tujuan. Kemudian dari kota kedua, masing-masing koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang tidak terdapat pada daftar hubungan kota sebagai kota tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus sampai kota terakhir tidak memiliki hubungan dengan kota lain atau hubungan yang dimiliki oleh kota tersebut sudah tercatat dalam catatan si semut. Untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut :
dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan. Langkah 4 : a. Perhitungan panjang rute setiap semut. Perhitungan panjang rute tertutup (length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan ini dilakukan berdasarkan Panjang Jalur masing-masing dengan persamaan berikut :
Budi, Penemuan Jalur Terpendek Dengan…77
dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan persamaan :
b. Pencarian rute terpendek. Setelah Lk setiap semut dihitung, akan didapat harga minimal panjang rute tertutup setiap siklus atau LminNC dan harga minimal panjang rute tertutup secara keseluruhan atau Lmin. c. Perhitungan perubahan harga intensitas jejak kaki semut antar kota. Koloni semut akan meninggalkan jejak-jejak kaki pada lintasan antar kota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak kaki semut antar kota. Persamaan perubahan ini adalah :
Dengan adalah perubahan harga intensitas jejak kaki semut antar kota setiap semut yang dihitung berdasarkan persamaan.
Langkah 5 : a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya. Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan berubah karena adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung dengan persamaan :
b. Atur ulang harga perubahan intensitas jejak kaki semut antar kota. Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota perlu diatur kembali agar memiliki nilai sama dengan nol. Langkah 6 : Jika Siklus maksimum (Ncmax) belum terpenuhi, algoritma diulang lagi dari langkah 2 dengan harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui. Analisa Menggunakan Metode Ant Colony Contoh penyelesaian kasus Travelling Salesman Problem menggunakan Ant Colony dengan Kota awal A tujuan E :
78. CSRID Journal, Vol.4 No.2 Juni 2012, Hal. 73 - 80
Diketahui suatu graph :
Gambar 3. Graph ABCDE
Dengan jarak antar kota (dij) sebagai berikut: Tabel 1. Jarak Antar Kota
A
B
C
D
A
0
5
7
3
B
5
0
4
C
7
4
0
D
3
E
E
5
5
0
4
4
0
Parameter – parameter yang digunakan adalah : Alfa (α) = 1.00 Beta (β) = 1.00 Rho (ρ) = 0.50 ij awal = 0.01 Maksimum siklus (NCmax) = 2 Tetapan siklus semut (Q) = 1 Banyak semut (m) = 5 Dari jarak kota yang telah diketahui dapat dihitung visibilitas antar kota (ηij) = 1/dij Tabel 2. Penghitungan Visibilitas Antar Kota A
B
C
D
E
0
0.2
0.143
0.33
0
0.25 0 B ke0.2 Siklus -1 : 0 Semua jalur bermula dari Kota A 0 0 C ke0.1 Semut – 1: 0.25 Jalur 0.3 Kota 0 A 0 0 D Semut:
0
A
E -
0
0
0.2
0.25
0.2 0.25 0
Probabilitas dari kota A ke setiap kota berikutnya dapat dihitung dengan persamaan yang mana kota selanjutnya tidak
Budi, Penemuan Jalur Terpendek Dengan…79
boleh terdapat pada jalur semut . untuk Σ[ ij]α.[ηij]β = (0.01*0) + (0.01*0.2) + (0.01*0.143) + (0.01*0.33) = 0.00676. Dengan demikian dapat dihitung probabilitas dari kota A menuju setiap kota = Kota B = (0.01)1.00 . (0.2)1.00 / 0.00676 = 0.295 Kota C = (0.01)1.00 . (0.143)1.00 / 0.00676 = 0.211 Kota D = (0.01)1.00 . (0.33)1.00 / 0.00676 = 0.492 Kota E = 0.00 - Probabilitas Komulatif = 0.295 0.507 1.000 1.000 - Bilangan random yang dibangkitkan = 0.699 maka kota yang terpilih adalah kota D - Jalur = A => D Untuk t=2 - Probabilitas dari kota D ke setiap kota berikutnya dapat dihitung dengan persamaan yang mana kota selanjutnya tidak
boleh terdapat pada jalur semut . untuk Σ[ ij]α.[ηij]β = (0.01*0) + (0.23*0.2) + (0.01*0.143) + (0.01*0.33) = 0.00676. Dengan demikian dapat dihitung probabilitas dari kota D menuju setiap kota = Kota E = (0.01)1.00 . (0.25)1.00 / 0.00676 = 0,369 - Probabilitas Komulatif = 0.369 - Bilangan random yang dibangkitkan = 0.599 maka kota yang terpilih adalah kota E - Jalur = A => D => E Perhitungan akan dilanjutkan hingga semut telah menyelesaikan perjalanannya mengunjungi tiap-tiap kota. Hal ini akan berulang hingga sesuai dengan Ncmax yang telah ditentukan atau telah mencapai konvergen. Kemudian akan ditentukan jarak terpendek dari semut dari masingmasing siklus.
KESIMPULAN Algoritma Ant Colony dapat melakukan optimisasi / pengefisienan waktu dalam penemuan jalur terpendek. Algoritma Semut diadopsi dari perilaku koloni semut yang dikenal sebagai sistem semut, yang merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik, dalam hal ini waktu yang diperlukan oleh setiap algoritma untuk mencapai jalur terpendek tidak berkorelasi positif dengan jumlah titik yang diselesaikan, karena dalam mencari jalur terpendek algoritma ant colony mengunakan semut lebih dari satu. Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Koloni semut dapat menemukan rute terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada lintasan yang telah dilalui. Semakin banyak semut yang melalui suatu lintasan, maka akan semakin jelas bekas jejak kakinya.
DAFTAR RUJUKAN Dorigo,M dan Gambardella,L.M.,1996,Ant Colony System:A Cooperative Learning Approach to theTraveling Salesman Problem, Université Libre de Bruxelles Belgium Jamilah, Euis S.Kom, Algoritma Ant System dalam Minimum Spanning Tree, Universitas Komputer Indonesia, 2005 Mutakhiroh, I., Saptono, F., Hasanah, N., dan Wiryadinata, R,. (2007). Pemanfaatan Metode Heuristik Dalam Pencarian Jalur Terpendek Dengan Algoritma Semut dan Algoritma Genetik. Seminar Nasional Aplikasi Teknologi Informasi. ISSN: 1907-5022. Yogyakarta.
80. CSRID Journal, Vol.4 No.2 Juni 2012, Hal. 73 - 80
Wardy, I. S. (2007). Penggunaan graph dalam algoritma semut untuk melakukan optimisasi, Program studi Teknik Informatika, ITB, Bandung. Wilson, R. J., dan Watkhins, J. J. (1990). Graph An Introductionary Approach, A First Course in Discrete Mathematics. John Willey and Sons, New York.
