PERBANDINGAN KINERJA ALGORITMA GENETIK DAN ALGORITMA BRANCH AND BOUND PADA TRAVELLING SALESMAN PROBLEM Nico Saputro dan Suryandi Wijaya Jurusan Ilmu Komputer – Universitas Katolik Parahyangan
[email protected] Abstrak Makalah ini membahas penerapan algoritma genetik untuk mencari solusi Traveling Salesman Problem (TSP). Pembahasan difokuskan kepada bagaimana merepresentasikan TSP ke dalam algoritma genetik serta melakukan eksperimen dengan menggunakan algoritma genetik untuk mencari solusi TSP. TSP yang digunakan adalah TSP simetris yaitu jarak antara kota asal ke kota tujuan sama dengan jarak dari kota tujuan ke kota asal. Selanjutnya, akan dibandingkan hasil yang diperoleh oleh algoritma genetik dan algoritma branch and bound dengan metode Hungaria. Perbandingan dilakukan terhadap solusi akhir dan kecepatan pencarian solusi. Kata kunci : algoritma genetik, algoritma branch and bound, metode Hungaria, TSP simetris 1.
Pendahuluan Travelling Salesman Problem (TSP) merupakan permasalahan pedagang keliling dalam mencari lintasan terpendek dari N buah kota, dengan syarat kota yang ada hanya boleh dikunjungi satu kali (Snyder,2004). Metode brute force dapat dipergunakan untuk memecahkan TSP dengan memeriksa semua jalur, akan tetapi hal ini efektif bila jumlah kota sedikit (Winston,1994).Waktu yang diperlukan untuk menyelesaikan TSP semakin meningkat jika jumlah kota yang harus dikunjungi semakin banyak (combinatorial explosion). Algoritma Branch and bound dan algoritma genetik merupakan algoritma yang diharapkan dapat menghindari terjadinya combinatorial explosion. Pada algoritma branch and bound ruang solusi dapat dipersempit dengan digunakannya sebuah fungsi heuristic yaitu jika ada suatu pencarian lintasan yang tidak berguna maka pencarian tersebut tidak akan ditelusuri lebih lanjut. Fungsi Heuristic adalah sebuah teknik yang mengembangkan efisiensi dalam proses searching yang memungkinkan pengorbanan kelengkapan dalam proses searching itu sendiri (Winston, 1994). Pada TSP, fungsi heuristic pada algoritma branch and bound ditujukan pada saat memilih sub-tur (jika salesman tidak mengunjungi seluruh kota yang ada pada TSP secara urut) mana yang akan diproses lebih lanjut. Dalam hal ini fungsi heuristic diterapkan untuk memilih sub-tur dimana jumlah kota yang dipilih adalah jumlah kota yang paling minimal dengan jarak tempuh terkecil. Penggunaan fungsi Heuristic akan menghemat waktu, karena fungsi ini hanya akan memproses subtur terkecil (sub-tur dengan jumlah kota terkecil dan jarak tempuh terkecil), sedangkan sub-tur lainnya tidak akan diproses lebih lanjut. Algoritma genetik merupakan algoritma pencarian, cara kerjanya meniru mekanisme dari seleksi alam dan genetika. Telah banyak penelitian
dilakukan untuk menguji validitas algoritma genetik dalam optimasi fungsi serta berbagai aplikasi kontrol. Terbukti algoritma genetik dapat diterapkan dalam penyelesaian masalah yang memerlukan pencarian efektif dan efisien. Hal ini didukung oleh penggunaan perhitungan yang relatif sederhana namun memiliki kekuatan dalam pencarian. Algoritma genetik dalam melakukan pencarian solusi juga tidak melakukan pencarian ke seluruh ruang solusi. Ruang solusi dimana algoritma genetik bekerja sangat dipengaruhi oleh proses seleksi dan proses rekombinasi serta parameter-parameter genetik seperti ukuran populasi, jumlah generasi, probabilitas crossover, dan probabilitas mutasi. Algoritma branch and bound dan algoritma genetik sebagai dua buah algoritma yang mengorbankan kelengkapan pencarian tentunya menarik untuk dibandingkan kinerjanya. Oleh karena itu, tujuan dari penelitian adalah untuk membandingkan kinerja algoritma genetik dan algoritma branch and bound. Perbandingan dilakukan terhadap solusi akhir dan kecepatan pencarian solusi dari kedua algoritma ini. 2.
Algoritma Branch and Bound Algoritma Branch and Bound memakai representasi matriks bujursangkar n x n. Isi setiap elemen matriks bergantung dari permasalahan yang dihadapi. Pada TSP isi elemen matriks menggambarkan jarak yang harus ditempuh oleh salesman dari masing-masing kota dengan baris dan kolom menggambarkan jarak antar kota. Langkah-langkah Branch and Bound (Winston,1994) adalah sebagai berikut : 1. Buatlah sebuah rute yang membentuk tur (salesman berangkat dari kota asal lalu kembali ke kota asal dengan masing-masing kota dikunjungi sebanyak satu kali) secara acak yang
2.
3.
4.
5.
6.
harus dimulai dari kota pertama dan hitung jaraknya. Nilai ini digunakan sebagai batas atas. Rumuskan suatu model penugasan metode Hungaria dengan penambahan M (bilangan positif yang sangat besar) sebagai elemen diagonal. Selesaikanlah model penugasan tersebut dengan metode Hungaria dan hitung jarak yang diperoleh. Tuliskan jarak tersebut pada simpul pohon saat ini. Nilai ini digunakan sebagai batas bawah. Jika solusi membentuk sebuah tur lanjutkan ke langkah 4, tetapi jika membentuk sub-tur (salesman tidak mengunjungi seluruh kota yang ada pada TSP secara urut) lanjutkan ke langkah 5. Jika nilai yang diperoleh lebih kecil dari nilai batas atas saat itu, jadikanlah nilai ini sebagai batas atas yang baru. Lanjutkan ke langkah 6. Buatlah cabang dengan jarak dan sub-tur terkecil. Cabang tersebut memberikan persoalan penugasan yang baru dengan satu dari lintasan pada sub-tur tersebut diubah nilainya agar tidak dilalui kembali (diberi nilai M). Kemudian kembali ke langkah 3. Jika semua pohon sudah ditelusuri semua cabangnya, ambil batas atas sebagai solusi optimal. Jika belum, kembali ke langkah 3.
Metode Hungaria merupakan metode yang efisien untuk menyelesaikan masalah pencarian nilai minimum (Winston,1994). Cara kerja metode Hungaria : 1. Kurangi setiap elemen pada masing-masing baris dengan elemen matriks terkecil pada masing-masing baris tersebut. Lakukan hal yang sama untuk elemen matrik pada tiap kolom. 2. Tariklah garis lurus yang sejajar baris dan kolom yang melalui semua nilai nol dengan jumlah garis minimum. Jika jumlah garis lurus ini sama dengan jumlah baris atau kolom maka solusi optimal sudah diperoleh. Jika jumlah garis ini lebih kecil dari jumlah baris atau kolom, lanjutkan ke langkah 3. 3. Kurangi nilai setiap elemen matriks yang tidak dilalui garis dengan nilai terkecil dari elemen matriks yang tidak dilalui garis dan tambahkan nilai terkecil ini pada setiap nilai pada perpotongan yang dilalui oleh 2 garis, kemudian kembali ke langkah 2. Solusi optimal dapat dibaca dari matriks dengan melihat baris yang hanya memiliki satu nilai nol, atau kolom yang juga hanya memiliki satu nilai nol.
3.
Algoritma Genetik pada TSP Teknik encoding yang dipilih adalah permutation encoding. Panjang kromosom sama dengan jumlah kota yang dikunjungi salesman. Posisi gen (locus) menunjukkan urutan kota yang dikunjungi salesman. Nilai gen (allele) menunjukkan nama kota yang dikunjungi salesman. Operator genetik yang digunakan adalah operator Reproduksi memakai metode Elitism dengan Rank Selection, operator crossover Precedence Preservative Crossover (PPX) dan operator mutasi order changing. Operator reproduksi Elitism dipakai untuk mencegah hilangnya kromosom terbaik dan Rank Selection dipakai untuk memilih sekumpulan kromosom dengan nilai fitness tinggi yang akan digunakan untuk proses rekombinasi. Operator PPX menjamin bahwa kromosom anak hasil crossover tidak akan memiliki allele yang sama. Kromosom baru disusun secara acak dari allele kromosom induk. Angka acak 1 atau 2 dipakai untuk memilih induk. Jika 1 diturunkan allele paling kiri dari induk pertama, jika 2 diturunkan allele paling kiri dari induk kedua. Selanjutnya allele yang telah terpilih tadi dihapus dari kedua induk. Proses dilakukan sampai allele di kedua induk habis (Saputro, 2004). Operator order changing bekerja dengan memilih 2 locus secara acak, kemudian allelenya dipertukarkan. Fitness merupakan ukuran kualitas dari suatu kromosom. Pada TSP, digunakan fitness berupa jumlah jarak antar kota, semakin kecil fitness semakin baik kromosom-nya dan semakin baik pula solusi yang direpresentasikan oleh kromosom tersebut. Fungsi fitness yang dipakai adalah :
i a 1 f (n) k (i, i 1) k (a,1) i 1
(1)
dengan : f(n) = fungsi fitness n = generasi saat ini k = jarak antar kota i = urutan gen a = panjang kromosom Cara kerja algoritma genetik adalah sebagai berikut (Man, 1999) : 1. [Start] Buat populasi acak dari n kromosom. 2. [Fitness] Evaluasi fitness tiap kromosom yang terdapat pada populasi. Semakin baik fitness, semakin unggul kromosom tersebut. 3. [New Population] Buat populasi baru dengan mengulangi langkah 4 sampai ukuran populasi terpenuhi. 4. [Replace] Gunakan populasi baru ini untuk menggantikan populasi lama.
5.
6.
[Reproduction] Pilih 2 induk kromosom dari populasi berdasarkan nilai fitness. [Crossover] Berdasarkan peluang crossover, lakukan crossover terhadap induk untuk mendapatkan keturunan baru. Jika tidak ada crossover, maka keturunan baru merupakan salinan (exact copy) dari induknya. [Mutation] Berdasarkan peluang mutasi, lakukan mutasi terhadap keturunan baru ini. [Accepting] Tempatkan keturunan baru ini di dalam populasi baru. [Test] Jika kondisi akhir terpenuhi, stop, hasil akhir adalah solusi terbaik pada populasi saat ini. [Loop] Ulangi langkah 2.
4.
Eksperimen dan Pembahasan Ada 2 eksperimen yang dilakukan yaitu mencari kombinasi probabilitas crossover (Pc) dan probabilitas mutasi (Pm) terbaik untuk ukuran populasi 100 dan jumlah generasi 1000. Selanjutnya berdasarkan kombinasi Pc dan Pm yang dipilih, dilakukan eksperimen untuk jumlah kota yang bervariasi. Pada eksperimen pertama, digunakan kasus uji dengan jumlah kota 10 buah dan dengan matriks jarak seperti pada table 4.1. Eksperimen di ulang sebanyak 20 kali untuk setiap kombinasi Pc dan Pm. Hasil eksperimen 1 dapat dilihat pada table 4.2
1 2 3 4 5 6 7 8 9 10
1 -1 14 23 25 36 42 50 10 25 32
2 14 -1 17 23 30 36 90 22 67 84
Tabel 4.1 Matriks Jarak 3 4 5 6 7 23 25 36 42 50 17 23 30 36 90 -1 29 35 28 40 29 -1 17 11 30 35 17 -1 6 20 28 11 6 -1 10 40 30 20 10 -1 33 44 55 66 77 89 32 65 12 86 12 90 45 31 74
8 10 22 33 44 55 66 77 -1 55 23
9 25 67 89 32 65 12 86 55 -1 12
10 32 84 12 90 45 31 74 23 12 -1
Kriteria pemilihan kombinasi Pc dan Pm adalah berdasarkan patokan jarak yang diperoleh dari algoritma branch and bound untuk kasus uji yang sama dan kecepatan pencarian solusi yang diukur dari rata-rata generasi. Untuk kasus uji pada table 4.1, total jarak yang di dapat dari algoritma branch and bound adalah sebesar 188. Berdasarkan criteria pemilihan yang ditetapkan, maka di pilih kombinasi Pc dan Pm berikut : 1. Pc = 92%, Pm = 1% (jarak terkecil dan generasi terkecil)
2.
Pc = 83%, Pm = 0.5% (terbanyak hasil dari Algoritma Genetik (AG) lebih baik dari Algoritma Branch and Bound (ABB)).
Tabel 4.2 Hasil eksperimen 1 Parameter Min Max AG ≤ (Pc,Pm) ABB 1. (80%,0.5%) (185,1) (230,64) 3 2. (80%,1%) (176,655) (224,192) 4 3. (81%,0.5%) (166,932) (234,440) 3 4. (81%,1%) (169,1) (225,198) 5 5. (82%,0.5%) (185,914) (225,600) 4 6. (82%,1%) (166,402) (239,836) 3 7. (83%,0.5%) (178,215) (229,113) 7 8. (83%,1%) (166,1) (220,1) 5 9. (84%,0.5%) (173,541) (229,577) 4 10. (84%,1%) (168,568) (223,386) 2 11. (85%,0.5%) (161,266) (239,29) 6 12. (85%,1%) (181,747) (228,559) 4 13. (86%,0.5%) (166,747) (230,503) 6 14. (86%,1%) (181,1) (223,132) 1 15. (87%,0.5%) (181,1) (224,265) 1 16. (87%,1%) (170,185) (227,911) 4 17. (88%,0.5%) (184,863) (229,751) 1 18. (88%,1%) (186,820) (222,338) 3 19. (89%,0.5%) (176,802) (218,90) 4 20. (89%,1%) (169,398) (229,87) 4 21. (90%,0.5%) (169,867) (222,936) 4 22. (90%,1%) (181,523) (231,774) 5 23. (91%,0.5%) (188,1) (239,960) 1 24. (91%,1%) (167,941) (229,1) 5 25. (92%,0.5%) (157,775) (226,555) 3 26. (92%,1%) (157,270) (231,1) 4 27. (93%,0.5%) (187,206) (234,1) 1 28. (93%,1%) (157,664) (228,245) 4 29. (94%,0.5%) (176,1) (216,1) 4 30. (94%,1%) (181,125 (234,42) 3 31. (95%,0.5%) (192,1) (228,655) 0 32. (95%,1%) (181,960) (227,707) 3 Keterangan : - Min/Max : jarak minimal/minimal yang didapat setelah 20 kali percobaan, dalam bentuk (jarak minimal, generasi ditemukannya jarak tersebut) - AG ≤ ABB : banyaknya hasil eksperimen di mana hasil AG lebih baik daripada ABB. No
Eksperimen kedua memakai kedua kombinasi parameter yang diperoleh pada eksperimen 1. Jumlah kota yang dipakai adalah 10, 15, 16, 17, 18, 19, dan 20 kota. Eksperimen di ulang sebanyak 20 kali. Ukuran populasi yang digunakan tetap 100 dengan jumlah generasi bervariasi. Hasil eksperimen dapat dilihat pada tabel 4.3.
Algoritma Branch and Bound
Info Jarak Waktu
10 Kota 188 0:3:343
Tabel 4.3 Hasil eksperimen 2 15 Kota 16 Kota 17 Kota 342 301 373 1:0:422 1:15:328 2:4:672
Algoritma Genetik Pc = 92% dan Pm = 1% Jarak 206 407 Jumlah Waktu 0:0:500 0:0:703 generasi Iterasi 1 1 = 100 Rata2 Jarak 224.85 480.6 Jarak 183 406 Jumlah Waktu 0:2:500 0:3:719 generasi Iterasi 1 1 = 500 Rata2 Jarak 212.7 467.65 Jarak 181 389 Jumlah Waktu 0:4:125 0:5:891 generasi Iterasi 305 55 = 800 Rata2 Jarak 210.4 445.8 Jarak 157 413 Jumlah Waktu 0:5:422 0:7:47 generasi Iterasi 270 644 = 1000 Rata2 Jarak 206.45 461.5
467 0:0:843 46 532.3 451 0:4:438 327 501.55 418 0:8:984 364 464.6 425 0:7:438 495 478.15
544 0:0:860 1 591.05 494 0:4:297 171 551.35 498 0:10:656 461 547.15 443 0:7:906 650 523.35
18 Kota 285 2:39:969
19 Kota 322 3:32:844
20 Kota 326 6:2:625
606 0:0:906 92 607.95 461 0:4:922 255 564.9 505 0:7:515 214 553.05 503 0:8:797 103 545.45
618 0:0:922 10 663.85 605 0:4:812 315 665.35 530 0:7:531 1 612.9 560 0:9:0 997 628.85
644 0:0:922 72 705.9 538 0:4:891 441 644.55 517 0:7:922 326 644.95 563 0:9:485 958 650.5
Algoritma Genetik Pc = 83% dan Pm = 0.5% Jarak 196 420 472 514 495 609 Jumlah Waktu 0:0:485 0:0:719 0:0:906 0:0:859 0:0:969 0:0:860 generasi Iterasi 1 1 1 38 13 1 = 100 Rata2 Jarak 222.7 482.1 512.1 574.8 591.15 669.2 Jarak 172 381 418 510 450 574 Jumlah Waktu 0:2:484 0:3:468 0:3:875 0:5:109 0:4:625 0:4:969 generasi Iterasi 125 199 440 98 166 25 = 500 Rata2 Jarak 207.95 457.15 501 549.65 551.2 631.25 Jarak 173 413 481 499 517 551 Jumlah Waktu 0:4:47 0:5:578 0:6:375 0:7:640 0:7:141 0:9:562 generasi Iterasi 723 56 54 460 300 237 = 800 Rata2 Jarak 201.6 468.9 491 549 538.95 612.75 Jarak 178 390 418 500 496 536 Jumlah Waktu 0:5:521 0:7:234 0:7:406 0:7:829 0:8:218 0:9:109 generasi Iterasi 1 628 372 374 35 628 = 1000 Rata2 Jarak 199.5 446.85 484.2 548.35 551.15 614.55 Keterangan : - Waktu : 0:16:344 = 0 menit 16 detik 344 milidetik - Jarak : jarak minimal yang didapat setelah dilakukan pengujian - Iterasi : iterasi ketika ditemukannya jarak minimal - Rata2 Jarak : rata-rata jarak yang didapat algoritma genetik setelah dilakukan 20 kali percobaan
Berdasarkan eksperimen yang telah dilakukan terlihat bahwa algoritma genetik lebih baik daripada algoritma branch and bound untuk 10 kota. sedangkan untuk jumlah kota lainnya algoritma genetik tidak pernah mendapatkan hasil yang lebih baik dari algoritma branch and bound.
628 0:0:938 97 706.3 593 0:4:766 1 670.8 545 0:7:531 166 644.9 578 0:9:281 593 660.2
Rute terpendek dari 10 kota dengan data jarak seperti pada table 4.1 pada masing-masing algoritma adalah sebagai berikut : - Rute Terpendek AG : 1-8-2-3-10-9-6-7-5-4-1 Jarak : 188 - Rute Terpendek ABB : 1-8-2-3-10-9-6-5-4-7-1 Jarak : 157
5. Kesimpulan Berdasarkan hasil eksperimen, algoritma branch and bound lebih baik dalam mencari rute terpendek dari TSP pada kasus jumlah kota 15-20 karena ruang solusi pencarian yang sudah semakin besar, walaupun waktu pencarian akan bertambah secara eksponensial seiring dengan kenaikan jumlah kota sedangkan algoritma genetik hanya bisa menemukan solusi lebih baik dari algoritma branch and bound pada jumlah kota 10. Algoritma genetik baik digunakan jika waktu pencarian terbatas tetapi jumlah kota sangat besar, karena kecepatan pencarian solusi algoritma genetik lebih baik dibandingkan algoritma branch and bound. DAFTAR PUSTAKA Man, K.F, Genetic Algorithms concepts and design, Springer, 1999 Obitko, Marek, Genetic Algorithms, http://cs.felk.cvut.cz/~xobitko/ga/intro.html Saputro, N., Yento, 2004, Pemakaian Algoritma Genetik untuk Penjadwalan Job Shop Dinamis Non Deterministik, Jurnal Teknik Industri, Vol. 6, no. 1, hlm. 61-70 Snyder, L.V., Daskin, M.S. “A Random-Key Genetic Algorithm for the Generalized Travelling Salesman Problem”. Department of Industrial Engineering and Management Sciences NorthWestern University. 2004. Taha, A, Hamdy., “Operations Research An Introduction”, 6th Edition, Prentice-Hall, Inc, 1997. Winston, W.L. “Operations Research, Application and Algorithms”. 3rd Edition. Indiana University. 1994.
