PERBANDINGAN ALGORITME ANT COLONY OPTIMIZATION DENGAN ALGORITME GREEDY DALAM TRAVELING SALESMAN PROBLEM Djasli Djamarus, Meiril Mediawan Laboratorium Informatika Dasar Jurusan Teknik Informatika FTI - USAKTI Jl. Kyai Tapa No. 1 Grogol Jakarta 11440 Email:
[email protected]
Traveling Salesman Problem (TSP) is a classic NP (Non deterministic Polynomial) problem where a person has to make a tour to all known places exactly once, with a minimum cost. If there are N places to visit, there will be a number of (N-1)! routes to explore. Knowing the distance among all places, of course the shortest route can be determined. However, if there are so many places to visit, the number of route will increase very fast as the factorial function (much higher function compare to polynomial), of which the exploration to all routes in a deterministic approach will take a very long time. This limitation invites researchers to develop a new type of algorithm known as stochastic approach. Although there is no guarantee the best solution will be found, this type of algorithm propose an approximately solution in a much shorter time. In this work the Ant Colony Optimization (ACO), one of the stochastic algorithms, is apply to the TSP, the result is compare to the greedy algorithm in solving the same problem. Kata kunci: Optimization algorithm ant colony traveling salesman problem
Pendahuluan Dalam kehidupan sehari-sehari seorang manusia akan selalu dihadapi dengan berbagai pilihan, dimana berdasarkan pilihan yang ada ia harus memilih salah satu yang terbaik untuknya. Traveling Salesman Problem (TSP) merupakan suatu permasalahan pemilihan rute perjalanan, dimana pilihan rute yang ada harus melewati tepat
TeknoInfo, Vol. 02 No. 1, 2008
hanya satu kali seluruh tempat yang ada dalam permasalahan, dengan biaya sekecil mungkin. Dengan pendekatan brute force, masalah TSP tersebut dapat diselesaikan dengan cara menghitung beban (dapat berupaya biaya, waktu atau jarak) dari setiap rute yang ada, untuk kemudian memilih rute yang memberikan biaya terkecil. Namun demikian, pendekatan brute force ini hanya dapat dipergunakan bila tempat yang akan dikunjungi tidaklah banyak. Hal ini disebabkan karena jumlah kemungkinan rute yang ada akan tumbuh dengan cepat mengikuti fungsi faktorial, yaitu (N-1)!, dimana N adalah jumlah tempat yang akan dikunjungi. Dengan perkataan lain masalah TSP ini merupakan masalah yang mempunyai kompleksitas sebagai fungsi faktorial, O(n!), yang pertumbuhannya sangat cepat. Berdasarkan kompleksitas penyelesaiannya, permasalahan yang ada dalam dunia komputasi dapat dikategorikan menjadi dua, yaitu permasalahan dengan kompleksitas sebagai fungsi polynomial atau lebih rendah, yang dikategorikan sebagai P (Polynomial) Problem dan permasalahan dengan kompleksitas yang lebih tinggi dari fungsi polynomial, (seperti fungsi eksponensial dan faktorial) yang dikategorikan sebagai NP (Non deterministic Polynomial) Problem. Berbeda dengan masalah-masalah yang mempunyai kompleksitas fungsi polynomial (dikenal sebagai P Problem), masalah yang mempunyai kompleksitas tinggi, seperti fungsi eksponensial dan faktorial, sampai dengan saat ini masih belum mempunyai pemecahan yang dapat diterapkan untuk setiap permasalahan. Pada umumnya masalah-masalah tersebut didekati dengan pendekatan deterministik untuk menghasilkan solusi pendekatan (approximate) yang mendekati solusi pasti (exact) yang ideal. Dalam penelitian ini, untuk menyelesaikan permasalahan TSP yang simitris akan digunakan dua algoritme untuk mencari solusi pendekatan,
27
yaitu pendekatan yang menggunakan algoritme greedy (greedy algorithm) dan pendekatan yang menggunakan algoritme Ant Colony Optimization (ACO), untuk kemudian dibandingkan hasilnya.
Algoritme Greedy Algoritme greedy merupakan suatu algoritme yang melakukan pentahapan dalam mencari solusi yang diinginkan. Dalam setiap tahap dicari solusi terbaik untuk saat itu tanpa memperhitungkan kondisi yang akan ditemui setelah tahap tersebut (local optimal). Dengan mengasumsikan apa-apa yang telah dilakukan merupakan yang terbaik, dalam algoritme greedy tidak ada langkah untuk memperhitungkan kembali langkah-langkah yang lebih dahulu. (Levitin, 2003)
dimodelkan sebagai masalah pencarian lintasan (path) pada suatu graph. Dengan paradigma ini, suatu graph dianggap sebagai lintasan dari semut, dimana vertex merupakan titik percabangan lintasan. Setiap saat ketika semut akan meninggalkan vertex i, semut tersebut akan mengambil keputusan lintasan (i,j) mana yang akan ditempuhnya berdasarkan probabilistik p(i,j) yang dapat dinyatakan sebagai:
p(i,j) =
(i, j)
(i , j )
jadj ( i )
dimana (i , j ) adalah jumlah pheromone yang telah terakumulasi pada lintasan (i,j)
Solusi yang dihasilkan dari algoritme greedy seringkali bukan merupakan solusi yang optimal. Namun demikian dalam beberapa hal, algoritme greedy dapat memberikan solusi terbaik dari masalah yang dihadapi (Cormen, 1992). Suatu hal yang merupakan kelebihan dari teknik ini adalah singkatnya waktu yang diperlukan dalam menyelesaikan masalah. Masalah-masalah yang dapat diselesaikan dengan algoritme greedy ini antara lain adalah pencarian minimum spanning tree (MST) pada suatu graph, pencarian jarak terpendek dari satu vertex ke vertex lainnya yang ada pada suatu graph (shortest path), pengkodean Huffman, dll. Secara umum algoritme greedy dapat dituliskan seperti pada Gambar 1.
Set Solusi S sebagai himpunan kosong Untuk setiap tahap i = 1 sampai dengan n, lakukan Ambil pilihan terbaik Pi dari kemungkinan yang ada Gabungkan Pi sebagai bagian dari solusi return S
Gambar 1 Bentuk umum Algoritme Greedy
Ant Colony Optimization Algoritme ant system (Ant System Algorithm) merupakan suatu algoritme yang dinspirasikan oleh cara sekumpulan semut (ant colony) dalam mencari jalan pada waktu mengumpulkan makanannya (Dorigo & Stutzle, 2004). Dengan menggunakan suatu zat kimia yang disebut pheromone, sekumpulan semut mampu mencari jalan terpendek dari sarangnya ke tempat makanan berada. Algoritme ini merupakan algoritme yang bersifat probabilistik yang diharapkan dapat memecahkan berbagai masalah komputasi yang dapat
28
Secara umum, cara kerja dari Algoritme Ant Sistem untuk mendapatkan lintasan terpendek dapat diuraikan sebagai berikut (Dorigo & Gambardella, 1997): i Dalam mengambil keputusan dalam memilih jalur mana yang akan dipilih, seekor semut akan dipengaruhi oleh jumlah pheromone yang ada (probabilistik berdasarkan distribusi pheromone), semakin banyak pheromone yang ada pada suatu lintasan maka semut akan cenderung untuk memilih lintasan yang lebih banyak pheromonenya. Dengan demikian ketika sampai pada persimpangan (Gambar 2A), maka semut akan memilih jalur yang jumlahnya pheromonenya lebih banyak. Pada saat awal dimana belum ada pheromone yang diletakkan oleh kawanan semut tersebut, maka bila ada persimpangan, dimana terdapat dua jalur alternatif, maka probabilistik kemungkinan untuk memilih jalur tersebut masing-masing adalah 50% (Gambar 2B). ii Karena lintasan yang menuju ke atas lebih panjang dari lintasan yang menuju kebawah, maka mudah dimengerti bahwa dalam waktu yang sama, semut yang mengambil lintasan bawah akan lebih sering melakukan perjalanan pergi-pulang antara sarang dengan lokasi makanan. Dengan demikian maka jumlah pheromone yang diletakkan pada lintasan akan lebih banyak dibandingkan dengan jumlah pheromone yang ada pada lintasan atas (Gambar 2C dan 2D).
Perbandingan Algoritme Ant Colony Optimization dengan Algoritme Greedy dalam Traveling Salesman Problem (Djasli Djamarus, Meiril Mediawan)
vertex tersebut sebagai bobot (weight) dari edge tersebut. Dalam penelitian permasalahan yang akan diselesaikan adalah permasalahan TSP yang bersifat simitris, yaitu TSP yang dapat digambarkan sebagai graph tak berarah. Dengan demikian bobot antara vertex i dengan j sama dengan bobot antara vertex j dengan i, w(i,j) = w(j,i). Gambar 4 memperlihatkan model TSP simitris dengan 4 vertex. Gambar 2 Pencarian lintasan terpendek oleh sekumpulan semut (Dorigo & Gambardella, 1997) iii Berdasarkan hal tersebut, maka setelah sekian lama jalur bawah akan mempunyai probabilitas yang lebih tinggi untuk dipilih oleh semutsemut yang berada di persimpangan. Dampak dari hal ini maka suatu saat sangat sedikit atau bahkan tidak ada lagi semut yang akan melintasi jalur atas. Hal ini berarti secara bersama-sama sekumpulan semut mempunyai kemampuan untuk mendapatkan lintasan terpendek Algoritme Ant Sistem yang dipergunakan untuk menyelesaikan masalah optimasi seperti halnya TSP, disebut sebagai Ant Colony Optimization (ACO). Secara umum ACO algorithm (algoritme ACO) dapat dituliskan seperti pada Gambar 3.
Set parameter Initialisasi jumlah pheromone awal pada setiap edge Selama kriteria berhenti belum tercapai Lakukan pencarian solusi berdasar akumulasi pheromone Update jumlah pheromone Bila diperlukan, lakukan optimisasi lokal
Gambar 3 Bentuk umum algoritme ACO
Traveling Salesman Problem Traveling Salesman Problem (TSP) merupakan suatu masalah yang sangat mudah dimengerti, namun mempunyai kompleksitas tinggi (NP Problem). Oleh karenanya masalah TSP sangat sering dipergunakan sebagai ujicoba suatu algoritme yang ditujukan untuk mencari penyelesaian masalah NP Problem (Stutzle & Dorigo, 1999). Sebagai suatu model, TSP dapat digambarkan sebagai suatu graph G yang terdiri atas sejumlah vertex dan edge, G = (V,E), dimana vertex menggambarkan tempat yang akan dikunjungi, dan edge menggambarkan lintasan antar vertex yang dihubungkan. Dalam TSP, semua vertex terhubung dengan vertex yang lain dan diketahui jarak antar
TeknoInfo, Vol. 02 No. 1, 2008
Gambar 4 Graph sebagai model TSP
Algoritme Greedy untuk TSP Dengan menggunakan algoritme greedy, suatu lintasan yang melalui seluruh vertex yang ada, bisa didapat dengan memulai langkah awal dari vertex manapun juga untuk kemudian memilih vertex selanjutnya selain vertex yang telah dipilih yang berjarak terpendek. Pseudocode untuk mencari solusi TSP dengan algoritme greedy, diperlihatkan pada Gambar 5.
Tetapkan sembarang rute S sebagai solusi Lakukan sebanyak jumlah vertex dengan parameter k = 1 sampai dengan n Set himpunan Solusi kandidat Sk sebagai himpunan kosong Set P sebagai himpunan seluruh vertex Pilih vertex vk sebagai vertex awal yang dikunjungi Gabungkan vk sebagai anggota S, SS { vk } Keluarkan vk dari P, PP – { vk } Selama masih ada vertex pada P, P ≠ Ø Cari vertex vi P yang terdekat dengan vk Gabungkan vi sebagai bagian dari solusi, SS { vi } Keluarkan vi dari P, PP– { vi } Posisikan vi sebagai vk, vkvi Bila Sk lebih baik dari S, ganti S dengan Sk , SSk return S
Gambar 5 Algoritme Greedy untuk TSP
29
Solusi yang diberikan oleh algoritme greedy bersifat deterministik, sehingga untuk suatu kasus tertentu akan menghasilkan jawaban yang selalu sama. Namun demikian, meskipun pada setiap tahap akan dipilih edge eij yang menghubungkan vertex i yang diketahui, dengan vertex j terdekat, namun perjumlahan jarak yang terpilih dengan algoritme greedy tersebut, r = e12 + e23 + ... + eij + ... + ej1 belum tentu merupakan jumlah jarak terpendek.
Algoritme ACO untuk TSP Pencarian solusi masalah TSP dengan menggunakan ACO,dimulai dengan meletakkan seekor semut pada sembarang vertex awal. Selanjutnya semut tersebut akan memilih vertex berikutnya berdasarkan pengaruh jumlah pheromone yang terakumulasi pada setiap edge yang berpangkal pada vertex tersebut. Semut kemudian seolah-olah melalui edge tersebut untuk menuju vertex berikutnya, dengan meletakkan sejumlah pheromone (local updating) berdasarkan formula:
Hasil Percobaan Data yang dipergunakan untuk mencoba kedua algoritme tersebut di hasilkan dari suatu program generator yang menghasilkan suatu graph yang terdiri atas 10 vertex, dimana jarak antar vertex adalah seperti Tabel 1. Tabel 1 Matriks jarak antar vertex yang dipergunakan A
B
C
D
E
F
G
H
I
J
A
0
46
13
96
54
82
52
87
93
34
B
46
0
89
18
36
36
23
36
19
32
C
13
89
0
21
44
50
32
88
31
16
D
96
18
21
0
54
22
60
73
49
73
E
54
36
44
54
0
6
81
48
19
67
F
82
36
50
22
6
0
94
33
76
11
G
52
23
32
60
81
94
0
73
28
29
H
87
36
88
73
48
33
73
0
57
61
I
93
19
31
49
19
76
28
57
0
32
J
34
32
16
73
67
11
29
61
32
0
π(r,s) ← (1-ρ) * π(r,s) + Σ Δ π(r,s)
Set jumlah semut, pheromone awal pada setiap edge, jumlah iterasi Lakukan sebanyak jumlah iterasi yang diinginkan Lakukan untuk setiap semut Letakkan setiap semut pada setiap kota awal Lakukan pencarian kota berikutnya Lakukan local updating Sampai semua semut mengunjungi semua kota Catat rute terpendek yang didapat Lakukan global updating Sampai batas iterasi
Gambar 6 Algoritme ACO untuk TSP Selanjutnya pada setiap akhir iterasi akan dilakukan evaluasi untuk menentukan lintasan yang terbaik, dan untuk membuat lintasan tersebut menjadi sedikit kurang disenangi pada iterasi berikutnya, maka dilakukan global updating yang diaplikasikan hanya kepada lintasan yang terbaik sampai dengan iterasi tersebut dengan mengunakan formula: -1
π(r,s) ← (1- α)* π(r,s)+ α*(Lbest)
Pseudocode untuk mencari solusi TSP dengan Algorotme ACO, diperlihatkan pada Gambar 6.
Dengan mencoba sejumlah 2, 4, 6, 8, 10 semut dan iterasi sebanyak 5, 10, 15, 20, 25 dan jumlah percobaan sebanyak 30 kali, maka didapat hasil perbandingan sebagai yang terlihat pada Gambar 7, 8, 9, 10 dan 11. Pada gambar-gambar tersebut, sumbu X dipergunakan untuk menyatakan parameter jumlah semut, sedangkan sumbu Y memperlihatkan persentase hasil yang lebih baik, lebih buruk ataupun sama antara pencarian rute terpendek dengan algoritme ACO dan dan dengan algoritme greedy. Terlihat bahwa kinerja algoritme ACO 100 90 80 70 60 50 40 30 20 10 0
Lebih Baik Lebih Buruk Sama Dengan
Semut = 2
Semut = 4
Semut = 6
Semut = 8
Semut = 10
Gambar 7 Hasil perbandingan dengan banyak iterasi = 5 100 90 80 70 60 50 40 30 20 10 0
Lebih Baik Lebih Buruk Sama Dengan
Semut = 2
Semut = 4
Semut = 6
Semut = 8
Semut = 10
Gambar 8 Hasil perbandingan dengan banyak iterasi = 10
30
Perbandingan Algoritme Ant Colony Optimization dengan Algoritme Greedy dalam Traveling Salesman Problem (Djasli Djamarus, Meiril Mediawan)
Selain itu, jumlah iterasi yang dilakukan juga dapat meningkatkan kualitas solusi.
100 80 Lebih Baik
60
Lebih Buruk
40
Sama Dengan 20 0
Semut = 2
Semut = 4
Semut = 6
Semut = 8
Semut = 10
Gambar 9 Hasil perbandingan dengan banyak iterasi = 15
Dalam percobaan yang dilakukan, kinerja algoritme ACO baru dapat melebihi algoritme greedy ketika jumlah semut yang dipergunakan lebih banyak dari 8. Bila saja jumlah semut lebih sedkit dari 8, algoritme ACO hanya memperlihatkan solusi yang lebih baik dengan jumlah iterasi yang lebih dari 20.
Daftar Pustaka 100 80 60
Lebih Baik
40
Lebih Buruk
20
Sama Dengan
0 Semut = 2
Sem ut = 4
Semut = 6
Sem ut = 8 Semut = 10
Gambar 10 Hasil perbandingan dengan banyak iterasi = 20 100 80 Lebih Baik
60
Lebih Buruk
40
Sama Dengan
20 0
Semut = 2
Semut = 4
Semut = 6
Semut = 8
Cormen, T.H., Leiserson, C.E., & Rivest R.L. (1994). Introduction to algorithms. USA: The MIT Press. Dorigo, M., Maniezzo, V., & Colorni, A.(1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transaction on Systems, Man, and Cybernetics – Part B, 26 (1), 1 – 13. Dorigo, M., & Gambardella, L.M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transaction on Evolutionary Computation, 1 (1). Dorigo, M., & Stutzle, T. (2004). An colony optimization. USA: The MIT Press.
Semut = 10
Gambar 11 Hasil perbandingan dengan banyak iterasi = 25
Kesimpulan Berdsarkan percobaan yang dilakukan terlihat bahwa kualitas solusi yang diberikan oleh algoritme ACO, akan merupakan fungsi dari jumlah semut yang dipergunakan dalam algoritme tersebut. Semakin banyak semut yang dipergunakan maka semakin baik kualitas solusi dari algoritme ACO.
TeknoInfo, Vol. 02 No. 1, 2008
Levitin, A. (2003). Introduction to the design and analysis of algorithms. USA: Addison-Wesley Pearson International Edition. Stutzle, T., & Dorigo, M. (1999). ACO algorithms for the traveling talesman problem. In J. K. Miettinen, M. Makela, P. Neittaanmaki, & J. Periaux, (Eds.), Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications. John Wiley & Sons.
31
