PENYELESAIAN TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA SIMPLE HILL CLIMBING Dinda Novitasari1, Arista Welasari2, W. Lisa Yunita3, Nur Alfiyah4, dan Chasandra P.5 Program Studi Informatika, PTIIK, Universitas Brawijaya E-mail:
[email protected],
[email protected],
[email protected],
[email protected], dan
[email protected]
ABSTRACT Travelling Salesman Problem (TSP) merupakan permasalahan pencarian rute perjalanan terpendek atau jarak minimum oleh seorang salesman untuk melewati sejumlah kota dengan jalur tertentu sehingga setiap kota hanya terlewati satu kali dan perjalanan diakhiri dengan kembali ke kota semula. Banyak algoritma telah dikembangkan dalam menyelesaikan permasalahan TSP, namun ada beberapa algoritma yang dirasa kurang dalam hal performasinya. Salah satu algoritma yang mampu menyelesaikan permasalahan TSP adalah Simple Hill Climbing. Simple Hill Climbing merupakan algoritna yang didasarkan pada pemilihan new state secara langsung yang memiliki jalur yang lebih baik (“curam”) daripada jalur-jalur sebelumnya tanpa memperhitungkan jalur-jalur lain yang lebih “curam”. Pendekatan menggunakan algoritma Simple Hill Climbing ini diharapkan mampu memberikan solusi atau penyelesaian dalam perhitungan waktu yang lebih singkat dibandingkan dengan sejumlah algoritma lain yang diterapkan pada komputer dalam bentuk program. Tujuan yang ingin dicapai adalah mengaplikasikan metode heuristik Simple Hill Climbing untuk mensimulasikan dan menyelesaikan permasalahan Travelling Salesman Problem dengan baik untuk mendapatkan rute terpendek. Kata kunci: Travelling Salesman Problem, Simple Hill Climbing, algorima, rute terpendek
I. Pendahuluan 1.1 Latar Belakang Traveling Salesman Problem (TSP) pertama kali diperkenalkan oleh Rand pada tahun 1948, reputasi Rand membuat TSP dikenal dengan baik dan menjadi masalah yang populer. TSP merupakan sebuah permasalan optimasi yang dapat diterapkan pada berbagai kegiatan seperti routing dan penjadwalan produksi. Masalah optimasi TSP terkenal dan telah menjadi standar untuk mencoba algoritma yang komputasional. Pokok permasalahan dari TSP adalah seorang salesman harus mengunjungi sejumlah kota yang diketahui jaraknya satu dengan yang lainnya. Semua kota yang ada harus dikunjungi oleh salesman tersebut dan kota tersebut hanya boleh dikunjungi tepat satu kali. Permasalahannya adalah bagaimana salesman tersebut dapat mengatur rute perjalanannya sehingga jarak yang ditempuhnya merupakan jarak minimum. 1.2 Rumusan Masalah Untuk merencanakan dan membangun suatu sistem pencarian jalur terpendek yang akan dibuat pada Proyek Akhir ini, terdapat permasalahan yang dihadapi yaitu: Pemrograman Algoritma Simple Hill Climbing yang digunakan sebagai metode untuk pencarian jalur terpendek.
1.3 Batasan Masalah Adapun batasan-batasan permasalahan dari Proyek Akhir ini adalah sebagai berikut: a. Pencarian jalur terpendek hanya menggunakan jarak saja, tanpa menghiraukan adanya beban dari tiap jalan. b. Data yang dipakai di dalam sistem ini adalah data yang diolah secara random oleh komputer, sehingga bukan berdasarkan peta daerah tertentu. 1.4 Tujuan Tujuan dari sistem yang dibuat adalah menemukan jalur atau rute manakah yang memiliki total jarak terdekat yang ditempuh oleh salesman dalam simulasi perjalanan. Sehingga diharapkan mampu memberikan informasi kepada salesman tentang jalur manakah yang paling dekat untuk menuju suatu tempat yang diwakili oleh suatu titik asal dan titik tujuan.
II. Landasan Teori 2.1 Hill Climbing Algoritma: 1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang: (a) Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru. (b) Evaluasi keadaan baru tersebut. (i) Jika keadaan baru merupakan tujuan, keluar. (ii) Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. (iii) Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi. Masalah yangakan timbul pada prosedur Hill Climbing: ♦ Local optimum : adalah suatu keadaan yang lebih baik daripada semua tetangganya namun masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya. ♦ Sering muncul ketika sudah mendekati solusi.
Gambar 1 Hill Climbing
♦ Plateau(Daratan) : adalah suatu daerah datar dari ruang pencarian (search) dimana keadaan semua tetangga sama dengann keadaan dirinya ♦ Ridengane (Punggung) : local optimum yang lebih disebabkan karena ketidak mampuan untuk menggunakan 2 operator sekaligus. Solusinya: 1. Melakukan langkah balik (backtracking) ke simpul yang lebih awal dan mencoba bergerak ke arah yang lain. 2. Melakukan lompatan besar ke suatu arah untuk mencoba bagian ruang pencarian yang baru. 3. Menerapkan dua atau lebih aturan sebelum melakukan uji coba. Ini bersesuaian dengan bergerak ke beberapa arah sekaligus. 2.2 Simple Hill Climbing Contoh kasus: Seorang salesman ingin mengunjungi n kota. Jarak tiap kota sudah diketahui seperti terlihat pada gambar 2. Bantu salesman untuk menentukan rute terpendek, dimana setiap kota hanya boleh dikunjungi 1 kali. Misal ada 4 kota dengan jarak sebagai berikut:
Gambar 2 ♦ Operator yang digunakan adalah operator yang bisa menghasilkan kombinasi lintasan kota yang berbeda, yaitu dengan menukar urutan posisi 2 kota dalam suatu lintasan. ♦ Bila ada n kota, maka kombinasi lintasan :
Sehingga kalau ada 4 kota, menjadi: kombinasi. Keenam kombinasi ini akan dipakai semuanya sebagai operator, yaitu: 1. (1,2) tukar urutan posisi kota ke-1 dengan kota ke-2 2. (2,3) tukar urutan posisi kota ke-2 dengan kota ke-3 3. (3,4) tukar urutan posisi kota ke-3 dengan kota ke-4 4. (4,1) tukar urutan posisi kota ke-4 dengan kota ke-1 5. (2,4) tukar urutan posisi kota ke-2 dengan kota ke-4 6. (1,3) tukar urutan posisi kota ke-1 dengan kota ke-3 Pencarian dilihat dari anak kiri, bila nilai heuristik anak kiri lebih baik maka dibuka untuk pencarian selanjutnya, bila tidak baru melihat tetangga dari anak kiri tersebut. Pada pencarian ini, penggunaan urutan dari kombinasi harus konsisten, misalnya pada penyelesaian ini urutan sesuai no. 1 sampai dengan 6 seperti yang ada di atas. Urutan kombinasi yang lain juga diperkenankan, yang penting konsisten untuk semua level. Untuk lebih jelasnya bisa dilihat seperti pada Gambar 3.
Gambar 3 Metode Simple Hill Climbing dengan 6 operator
Keterangan Gambar 3: ♦ Pada Gambar 4.2 terlihat bahwa, pada keadaan awal, lintasan terpilih adalah ABCD (=19).
♦ Pada level pertama, hill climbing akan mengunjungi BACD (=17), BACD memiliki nilai heuristik lebih kecil dibandingkan dengan ABCD (17<19), sehingga BACD menjadi pilihan selanjutnya dengan operator Tukar1,2. ♦ Pada level kedua, hill climbing akan mengunjungi ABCD. Karena operator Tukar1,2 sudah digunakan oleh BACD, maka dipilih node yang lain yaitu BCAD (=15). Karena nilai heuristik BCAD lebih kecil dibanding dengan BACD (15<17), maka node BCAD akan menjadi pilihan selanjutnya dengan operator Tukar2,3. ♦ Kemudian hill climbing akan mengunjungi CBAD (=20). Karena nilai heuristik CBAD lebih besar jika dibanding dengan BCAD (20>17), maka dipilih node lain. ♦ Pencarian menuju ke node BACD, karena operator Tukar2,3 sudah pernah digunakan oleh BCAD, maka dipilih node lain. ♦ Kunjungan berikutnya ke node BCDA (=18). Nilai inipun masih lebih besar dari nilai heuristic BCAD, sehingga dipilih node lain. ♦ Node yang dikunjungi berikutnya adalah DCAB (=19). Nilai heuristik DCAB ternyata juga lebih besar dibanding dengan BCAD, sehingga pencarian dilanjuntukan di node lainnya lagi, yaitu BDAC (=14). Nilai heuristik ini sudah lebih kecil daripada nilai heuristik node BCAD (14<15), maka sekarang node ini yang akan diekplorasi. ♦ Pencarian pertama ditemukan node DBAC (=21), yang lebih besar daripada nilai BDAC. Nilai heuristik yang lebih kecil diperoleh pada node BDCA (=13). Sehingga node BDCA ini akan diekplorasi. ♦ Pencarian pertama sudah mendapatkan node dengan nilai heuristik yang kebih kecil, yaitu DBCA (=12). Sehingga node ini diekplorasi juga. ♦ Dari hasil ekplorasi dengan pemakaian semua operator, ternyata sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibanding dengan nilai heuristik DBCA, sehingga sebenarnya node DBCA (=12) inilah lintasan terpendek yang kita cari (SOLUSI). ♦ Misalkan tidak dipergunakan semua operator, melainkan hanya dipergunakan 4 operator pertama saja, yaitu: (a) Tukar 1,2 (menukar urutan posisi kota ke-1 dengan kota ke-2). (b) Tukar 2,3 (menukar urutan posisi kota ke-2 dengan kota ke-3). (c) Tukar 3,4 (menukar urutan posisi kota ke-3 dengan kota ke-4). (d) Tukar 4,1 (menukar urutan posisi kota ke-4 dengan kota ke-1). Maka pencarian dengan simple hill climbing ini dapat dilihat pada Gambar 4. Lintasan
terpendek yang diperoleh adalah B-C-A-D yaitu sepanjang 15. Di sini kita akan terjebak pada nilai minimum lokal yang disebabkan oleh kurangnya operator yang kita gunakan. Kita tidak dapat memperoleh nilai minimum globalnya yaitu sebesar 12.
Gambar 4 Metode Simple Hill Climbing dengan 4 operator
Kelemahan Simple Hill Climbing : 1. tidak semua solusi dapat ditemukan seperti pada metode generate and test. 2. pembatasan kombinasi operator → penemuan solusi yang tidak maksimal.
III. Pembahasan 3.1 Algoritma Hill climbing search
3.2 Implementasi a. Mencari panjang lintasan Hamiltonian (panjang rute minimum/terpendek)
3.2 Interface a. Rute awal sebelum diacak
b. Rute 2 setelah diacak b. Merubah (random) rute perjalanan
c. Rute 3 setelah diacak
c. Hill Climbing
d. Rute 4 setelah diacak
d. Inisialisasi jumlah Node (Kota)
e. Rute 5 setelah diacak
f. Rute 6 setelah diacak
k. Solusi TSP dengan Simple Hill Climb (Rute terpendek yang didapat)
g. Rute 7 setelah diacak
IV. PENUTUP
h. Rute 8 setelah diacak
i. Rute 9 setelah diacak
j. Rute 10 setelah diacak
a. Kesimpulan 1. Persoalan Travelling Salesman Problem (TSP) dapat diselesaikan dengan menggunakan prinsip array serta algoritma Simple Hill Climbing yang telah divariasikan dengan pemrograman PHP. 2. Seperti pada implementasi di atas, terbukti bahwa algoritma Simple Hill Climbing yang digunakan dapat menyelesaikan permasalahan TSP dengan baik, dengan ditemukannya jarak/ lintasan node minimum (titik yang diumpamakan sebagai kota-kota), yaitu 921 pada 5 kota yang diteliti. 3. Implementasi pada program ini dapat digunakan untuk menyelesaikan kasus TSP dengan node (kota) maksimum mencapai 100. b. Saran 1. Perlu adanya percobaan lebih lanjut untuk penerapan Simple Hill Climbing pada materi graph selain Travelling Salesman Problem. 2. Penggantian metode untuk pembentukan rute agar hasil yang diperoleh lebih baik dan mengurangi jumlah iterasi yang ada. 3. Setiap node (kota) diberi nama, misalnya kota A dan diberi perhitungan jarak antara satu node ke node yang lain agar diketahui perhitungan riil jarak rutenya. DAFTAR PUSTAKA Amin, Aulia A.,Ikhsan, Mukhamad., Wibisono, Lastiko. 2003. Travelling Salesman Problem. ITB. Eka, Dian R., dkk.2012. Modul Bahan Ajar Kecerdasan Buatan. PTIIK UB. Firman, Rendra., dkk. 2012. Penyelesaian Travelling Salesman Problem dengan Menggunakan Artificial Bee Colony. UM. Hill Climbing. (Online). (http://en.wikipedia.org/ wiki/Hill_climbing diakses pada tanggal 09 Januari 2014 pukul 10.14 WIB). Algoritma Simple Hill Climbing. (Online). (http://jemyshombing.com/blog/teori-metodepencarian-hill-climbing diakses pada tanggal 09 Januari 2014 pukul 10.20 WIB).
