Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
MODIFIKASI ALGORITMA SYMBIOTIC ORGANISMS SEARCH UNTUK TRAVELING SALESMAN PROBLEM Muhammad Isnaini Hadiyul Umam1), Budi Santosa2), dan Nurhadi Siswanto3) 1) Program Magister Teknik Industri, Institut Sepuluh Nopember Jl. Jalan Raya ITS, Surabaya, 60111, Indonesia e-mail:
[email protected] 2) Teknik Industri, Institut Sepuluh Nopember 3) Teknik Industri, Institut Sepuluh Nopember
ABSTRAK Teknik optimasi yang paling baru adalah metode Symbiotic Organism Search (SOS). Kendala yang dihadapi dalam penerapan algoritma SOS untuk memecahkan permasalahan TSP terdapat pada fase parasit. Algoritma SOS mengharuskan untuk menciptakan suatu organisme parasit berdasarkan dimensi dari fungsi tujuan yang akan dicari (fungsi kontinyu), sedangkan TSP tidak memiliki dimensi seperti fungsi kontinyu. Penelitian ini akan membahas bagaimana memodifikasi algoritma SOS agar dapat diterapkan untuk memecahkan permasalahan TSP. Mekanisme yang diusulkan untuk mengganti fase parasit ini adalah dengan menggunakan mekanisme mutasi. Setelah dilakukan modifikasi, performansi dari algoritma SOS dievaluasi dengan beberapa data set kemudian hasilnya akan dibandingkan dengan solusi terbaik yang telah diketahui. Setelah dibandingkan dengan algoritma PSO, algoritma SOS mampu memperlihatkan hasil yang sangat baik. Terlihat dari nilai konversi, diversi serta waktu komputasi yang lebih baik dibandingkan PSO. Dari 8 data set yang diujikan SOS mampu unggul sebanyak 6 data set (83%) sedangkan PSO hanya unggul pada 1 data set (17%). Kata kunci: Metaheuristik, Optimasi Kombinatorial, Symbiotic Organism Search, Traveling Salesman Problem.
PENDAHULUAN Optimasi kombinatorial dari dahulu telah sering digunakan untuk memecahkan permasalahan baik dalam ilmu pengetahuan, teknik, dan aplikasi komersial. Semenjak model matematika mulai dipergunakan untuk membantu mengatasi permasalahan pada kehidupan nyata, algoritma telah menjadi penting dalam beberapa tahun terakhir karena fleksibilitasnya untuk menemukan solusi. Salah satu permasalahan kombinatorial di bidang transportasi adalah mencari suatu rute perjalanan terpendek yang dapat ditempuh dari titik awal keberangkat menuju titik tujuan, serta meminimumkan biaya perjalanan dan waktu tempuh perjalanan, permasalah seperti ini dikenal dengan Traveling Salesman Problem (TSP) Moon et al. (2001) mengemukakan bahwa permasalahan TSP telah menjadi perhatian selama dua dekade terakhir dan berbagai macam pendekatan telah diusulkan untuk memecahkan permasalahan tersebut. Kemudian penelitian-penelitian untuk memecahkan permasalahan TSP ini terus dikembangkan dengan modifikasi serta dengan pendekatan baru lainnya seperti particle swarm optimization (Shi et al. 2007), Neural network for Euclidean TSP (Creput & Koukam, 2009), pendekatan 2-opt based on differential evolution (Chiang et al. 2010). Simulated annealing with greedy search (Geng et al. 2011). Ant colony with multidepot multiple TSP (Ghaufurian & Javadian, 2011). Evolutionary Algorithm (Liao et al. ISBN : 978-602-70604-3-2 1
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
2012). Lower tolerance branch and bound (Germs et al. 2012). Genetic algorithm (Rani & Kumar, 2014). Teknik optimasi yang paling baru adalah metode Symbiotic Organism Search atau yang dikenal dengan metode SOS. Metode ini dikembangkan oleh Cheng dan Prayogo pada tahun 2014 yang terinspirasi oleh hubungan biologis antar organisme pada sistem ekologi. Kendala yang dihadapi dalam penerapan algoritma SOS untuk memecahkan permasalahan kombinatorial adalah pada fase parasit algoritma SOS mengharuskan untuk menciptakan suatu organisme parasit dengan menggunakan dimensi dari fungsi tujuan yang akan dicari (fungsi kontinyu), sedangkan TSP tidak memiliki dimensi dari fungsi tujuan untuk itu perlu adanya mekanisme lain yang cocok untuk menggantikan mekanisme pada fase parasit tersebut. Ruskartina (2015) juga mengemukakan bahwa perlu dilakukan modifikasi pada fase parasit dengan menambahkan algoritma pencarian yang lebih spesifik untuk mengatasi permasalahan kombinatorial. Mekanisme yang diusulkan untuk mengganti fase parasit ini adalah dengan menggunakan mekanisme mutasi. Mekanisme mutasi memungkinkan untuk memunculkan individu-individu baru yang bukan berasal dari populasi sebelumnya dengan mengacu pada perubahan atau penggantian elemen dari vektor solusi (Santosa dan Willy, 2011). Penyempurnaan algoritma SOS inilah yang akan dikaji dalam penelitian ini yaitu dengan memodifikasi algoritma SOS agar dapat diterapkan pada permasalahan TSP dengan mengadaptasi mekanisme mutasi untuk menggantikan mekanisme pada fase parasit yang bertujuan untuk dapat menemukan rute terbaik. METODE Algoritma Symbiotic Organisms Search merupakan salah satu metode metaheuristik terbaru yang terinspirasi dari perilaku interaksi yang terlihat di antara organisme di alam semesta. Organisme memiliki sifat dasar yaitu tidak dapat hidup sendiri sehingga sangat memiliki ketergantungan pada spesies lain untuk mempertahankan keberlangsungan hidupnya. Hubungan berbasis ketergantungan ini dikenal sebagai simbiosis. Terdapat beberapa bentuk simbiosis yaitu simbiosis mutualisme, simbiosis komensalisme dan simbiosis parasitisme. Berikut merupakan alir algoritma dari Symbiotic Organisms Search: 1. Inisialisasi Ekosistem = rand x ((ub-lb) + lb)
(1)
Dimana : rand = bilangan secara acak antara 0 sampai 1 ub = nilai batas atas lb = nilai batas bawah 2. REPEAT - Fase Mutualisme - Fase Komensalisme - Fase Parasitisme 3. UNTIL ( Lakukan hingga kriteria terminasi terpenuhi) - Fase Mutualisme Fase SOS ini meniru hubungan mutualistis antar organisme di alam. SOS menggambarkan Xi adalah organisme cocok dengan anggota ekosistem. Organisme lain Xj kemudian dipilih secara acak dari ekosistem untuk berinteraksi dengan Xi. Kedua organisme ISBN : 978-602-70604-3-2 2
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
terlibat dalam hubungan mutualistis dengan tujuan meningkatkan kelangsungan hidup bersama keuntungan dalam ekosistem. Solusi kandidat baru untuk Xi dan Xj dihitung berdasarkan simbiosis mutualistis antara organisme Xi dan Xj, yang dimodelkan pada persamaan (2) dan (3) berikut: (Cheng dan Prayogo, 2014) Xinew = Xi + rand(0,1) * (Xbest - Mutual_Vector * BF1)
(2)
Xjnew = Xj + rand(0,1) * (Xbest - Mutual_Vector * BF2)
(3)
Mutual Vector =
(4)
-
Fase Komensalisme Serupa dengan fase mutualisme, suatu organisme Xj dipilih secara acak dari ekosistem untuk berinteraksi dengan Xi. Dalam hal ini, organisme Xi mencoba untuk mendapatkan keuntungan dari interaksi. Namun, organisme Xj sendiri tidak keuntungan atau menderita hubungan. Solusi calon baru dari Xi dihitung sesuai dengan simbiosis antara organisme komensal Xi dan Xj, yang dimodelkan dalam Persamaan (2). Mengikuti aturan, organisme Xi diperbarui hanya jika fittnes baru lebih baik dari fittnes interaksi sebelumnya. Xinew = Xi + rand(-1,1) * (Xbest - Xj) -
(5)
Fase Parasitisme Pada SOS, organisme Xi diberikan peran yang mirip dengan nyamuk anopheles melalui penciptaan parasit buatan yang disebut ''Parasite Vector''. Parasite Vector dibuat dalam ruang pencarian dengan menduplikasi organisme Xi, kemudian memodifikasi dipilih secara acak dimensi menggunakan nomor acak. Organisme Xj dipilih secara acak dari ekosistem dan berfungsi sebagai tuan rumah untuk parasit vektor. Parasite Vector mencoba untuk menggantikan Xj dalam ekosistem. Kedua organisme kemudian dievaluasi untuk mengukur nilai fitnes mereka. Jika Parasite Vector memiliki nilai fitness yang lebih baik, itu akan membunuh organisme Xj dan menganggap posisinya dalam ekosistem. Jika nilai fitness dari Xj lebih baik, Xj akan memiliki kekebalan dari parasit dan Parasite Vector akan tidak lagi dapat hidup di ekosistem tersebut. - Mutasi pada TSP Mutasi adalah memungkinkan memunculkan individu-individu baru yang bukan berasal dari hasil kawin silang. Mutasi mengacu pada perubahan urutan atau penggantian elemen dari vektor solusi (pada problem TSP) dengan memunculkan nilai baru (optimasi fungsi). Proses ini dilakukan dengan memilih individu mana yang akan dilakukan mutasi dengan menggunakan bilangan acak. Individu yang terpilih selanjutnya akan dilakukan mutasi yaitu dengan menukan urutan rute dari individu tersebut. Penukaran urutan rute dapat dilakukan dengan beberapa cara yaitu swap (menukar), slide (menggeser) dan flip (membalik). Contoh misalkan ada rute 4 - 6 -|2–3–5–1| - 7. Berikut adalah perbedaan ketiga cara mutasi tersebut (Santosa dan Willy, 2011): Swap (menukar) Dengan melakukan proses menukar pada titik 3 dan 6 menjadi 4 – 6 - |1 – 3 – 5 – 2| - 7. Slide (menggeser) Dengan pergeseran rute menjadi 4 – 6 - |3 – 3 – 2 – 1| - 7. Flip (membalik)
ISBN : 978-602-70604-3-2 3
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
Jika dilakukan proses membalik terhadap segmen diantara 2 garis tegak rute akan menjadi 4 – 6 - |1 – 5 – 3 – 2| - 7. HASIL DAN PEMBAHASAN Pada penelitian ini data set yang akan digunakan diambil dari beberapa permasalahan TSP dengan jumlah kota yang berbeda. Dapat dilihat pada tabel berikut ini: Tabel 1. Data Set Data Set
Jumlah Kota
Solusi Optimal
SP11
11 kota
133
UK12
12 kota
1733
LAU15
15 kota
291
GR17
17 kota
2085
WG22
22 kota
842
FRI26
26 kota
937
ATT48
48 kota
10628
SGB128
128 kota
-
Eksperimen dilakukan pada keseluruhan data set yang ada dan dilakukan beberapa kali replikasi untuk tiap-tiap data set tersebut. Replikasi dilakukan karena dalam algoritma heuristik terdapat bilangan random yang akan mempengaruhi penuntunan solusi sehingga perlu dilakukan beberapa kali replikasi untuk melihat perfomansi dari algoritma tersebut. Tabel 2. Pseudocode Algoritma SOS untuk TSP Pseudocode Algoritma SOS untuk TSP Input : Number of population,Upper Bound, Lower bound, maximum iteration Output : Best Route, Total distance Begin Generate ecosystem, calculation initial distance, set IT=1 Repeat while it < itmax for i = 1: ecosize; update best distance and best route Mutualism Phase If distance better than before eco(i; j) ← x (new1;new2) end Commensalism Phase If distance better than before eco(i) ← x (new1) end Parasitism Phase Rand If rand < 0,33 Flip Elseif rand > 0,67 Swap Else ISBN : 978-602-70604-3-2 4
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
Slide end If distance better than before eco(i) ← x (new1) end End It=it+1 If it == itmax break end end
Hasil dari eksperimen dibandingkan dengan algoritma metaheuristik lainnya yaitu Particle Swarm Optimization (PSO). PSO dipilih karena memiliki kedekatan karakteristik dengan algoritma SOS karena sama sama tergabung dalam kelompok population based algorithm. Selain itu algoritma PSO juga memiliki mekanisme penyimpanan solusi terbaik yang pernah ditemukan. Tabel 3. Hasil Penentuan Parameter Tiap-tiap Data Set Data set
Norg
Itmax
Rata-rata Konvergensi
SP11
25
42000
1,5037 x 10-3 -3
1
Rata-rata waktu Komputasi (detik) 15,974
Solusi Terbaik yang Dihasilkan 133
67
16,878
1733
Rata-rata Divergensi
UK12
50
42000
8,424 x 10
LAU15
25
42000
0,016
24
18,036
291
GR17
50
80000
0,01813
107
67,174
2805
WG22
50
50000
0,114
249
34,934
842
FRI26
50
48000
0,325
424
3152,216
1143
ATT48
100
1000000
6,21
73763
1269,236
69123
SGB128
100
500000
0,019
2021
585,3086
111013
Nilai konvergensi menunjukkan seberapa dekat solusi yang dihasilkan dengan solusi optimal. Semakin kecil nilai konvergensi maka kualitas yang dapat dihasilkan dari data set tersebut semakin baik. Sedangkan nilai divergensi menunjukkan sebaran data. Dari tabel 2 dapat dilihat bahwa nilai-nilai konvergensi, divergensi, waktu komputasi serta solusi terbaik yang mampu dihasilkan oleh kedua algoritma tersebut. Tabel 4. Perbandingan Performansi algoritma SOS dan PSO
1
Rata-rata waktu Komputasi (detik) 15,974
Solusi Terbaik yang Dihasilkan 133
77
13,626
210
Data set
Algoritma
Rata-rata Konvergensi
SP11
SOS
1,5037 x 10-3
PSO
8,6115 x 10
-3
SOS
8,424 x 10-3
67
16,878
1733
PSO
0,0547
215
22,584
1756
SOS
0,016
24
18,036
291
UK12
LAU15
Rata-rata Divergensi
ISBN : 978-602-70604-3-2 5
Solusi Optimal 133
1733 291
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
GR17
WG22
FRI26
ATT48
SGB128
PSO
0,29
204
52,814
330
SOS
0,01813
107
67,174
2805
PSO
0,1876
570
125,11
2215
SOS
0,114
249
34,934
842
PSO
0,627
621
70,18
1257
SOS
0,325
424
34,78
1143
PSO
0,219
248
87,706
1100
SOS
6,21
73763
1269,236
69123
PSO
7,321
91348
4173,26e+003
79830
SOS
0,019
2021
585,3086
111013
PSO
0,061
11415
8,2422e+003
116575
2805
842
842
10628
-
Berdasarkan hasil eksperimen secara keseluruhan algoritma SOS dapat dikatakan lebih unggul dari PSO terbukti dengan nilai konvergensi dari algoritma SOS lebih unggul sebanyak 7 data set (SP11, UK12, LAU15, GR17, WG22, ATT48 dan SGB128) dari PSO yang hanya unggul sebanyak 1 data set (FRI26). Hal ini membuktikan bahwa algoritma SOS mampu menghasilkan set solusi yang lebih mendekati solusi optimal dari pada PSO. Dari segi divergensi SOS juga memperlihatkan bahwa lebih baik dari PSO dengan nilai diversi yang lebih kecil dibanding untuk seluruh data set. Namun untuk waktu komputasi PSO mampu unggul pada data set 11 kota lebih cepat dibanding SOS. Performa algoritma SOS tidak lebih baik dibandingkan algoritma PSO untuk permasalahan dengan n! yang besar seperti pada data set 26 kota, 48 kota dan 128 terlihat kedua algoritma tersebut kesulitan dalam menemukan solusi optimal dari data set-data set tersebut. Hal ini dibuktikan dari jumlah iterasi yang sangat besar serta konvergensi yang besar seperti yang tampak pada tabel 2 sehingga waktu komputasi yang dibutuhkan juga menjadi sangat besar. KESIMPULAN DAN SARAN Kesimpulan yang diperoleh setelah melakukan penelitian adalah sebagai berikut: 1. Algoritma SOS telah berhasil dimodifikasi dari yang semula hanya dapat digunakan untuk permasalahan kontiniyus menjadi permasalahan kombinatorial, sehingga dapat diterapkan untuk menyelesaikan permasalahan TSP. 2. Setelah dibandingkan dengan algoritma PSO, algoritma SOS mampu memperlihatkan hasil yang sangat baik. Terlihat dari nilai konversi, diversi serta waktu komputasi yang lebih baik dibandingkan PSO. Dari 8 data set yang diujikan SOS mampu unggul sebanyak 7 data set (83%) sedangkan PSO hanya unggul pada 1 data set (17%). Saran yang diusulkan sebagai acuan untuk penelitian selanjutnya adalah sebagai berikut: 1. Kecepatan untuk menemukan solusi yang konvergen dari algoritma SOS harus lebih ditingkatkan. 2. Perlu dilakukan perbaikan dengan menerapkan pencarian lokal sehingga dapat menghasilkan solusi yang lebih baik khususnya untuk permasalahan dengan jumlah n yang besar.
ISBN : 978-602-70604-3-2 6
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
DAFTAR PUSTAKA Cheng, M, Y,. & Prayogo, D,. 2014. Symbiotic Organisms Search : A New Metaheuristic Optimization Algorithm. Computers and Structures. Chiang, C, W,. Lee, W, P,. Heh, J, S,. 2010. A 2-opt Based differential Evolution for Global Optimization. Applied Soft Computing. Vol. 10, 1200-1207. Creput, J, C,. & Koukam, A,. 2009. A Memetic Neural Network for The Euclidean Traveling Salesman Problem. Neurocomputing. Vol 72, 1250-1264. Geng, X,. Chen, Z,. Yang, W,. Shi, D,. Zhao, K,. 2011. Solving the Traveling Salesman Problem Based On An Adaptive Simulated Annealing Algorithm with Greedy Search. Applied Soft Computing. Vol.11, 3680-3689. Germs,R,. Goldenngorin, B,. Turkensteen, M,. 2012. Lower Tolerance-based Branch and Bound Algorithms for ATSP. Computers & Operations Research. Vol.39, 291-298. Ghaufurian, S,. & Javadian, N,. 2011. An Ant Colony Algorithm for Solving Fixed Destination Multi-depot Multiple Traveling Salesman Problems. Applied Soft Computing. Vol 11, 1256-1262. Liao, Y, F,. Yau, D, H,. Chen, C, L,.2012. Evolutionary Algorithm to Traveling Salesman Problem. Computers and Mathematics with Applications. Vol.64 788-797. Moon,C,. Kim, J,. Choi, G,. Seo, Y. 2002. An Efficient Genetic Algorithm for the Traveling Salesman Problem with Precedence constraints, European Journal of Operational Research, 0377-2217. Rani, K,. & Kumar, V,. 2014. Solving traveling salesman problem using genetic algorithm based on heuristic crossover and mutation operator. International Journal of Research in Engineering & Technology. Vol.2, 27-33. Ruskartina, E,. 2015. Symbiotic Organism Search (SOS) for Solving Capacited Vehicle Routing Problem (CVRP). Tesis. Institut Teknologi Sepuluh Nopember. Santosa, B,. & Willy, P,. 2011, Metode Metaheristik Konsep dan Implementasi, Cetakan Pertama, Penerbit Guna Widya, Surabaya. Shi, X, H,. Liang, Y, C,. Lee, H, P,. Lu, C,. Wang, Q, X. 2007. Particle Swarm Optimizationbased Algorithm for TSP and Generalized TSP. Information Process Letters, Vol 103 ISSUE 5, 169-176.
ISBN : 978-602-70604-3-2 7
