PENYELESAIAN TRAVELLING SALESMAN PROBLEM ( TSP ) DENGAN MENGGUNAKAN ARTIFICIAL BEE COLONY
Rendra Firman Pratama, Purwanto, dan Mohammad Yasin e-mail:
[email protected] Universitas Negeri Malang ABSTRAK: Travelling Salesman Problem (TSP) adalah pencarian rute terpendek atau jarak minimum oleh seorang salesman dari suatu kota ke n-kota tepat satu kali dan kembali ke kota awal keberangkatan. TSP dapat diterapkan pada graph komplit berbobot yang memiliki total bobot sisi minimum, dimana bobot pada sisi adalah jarak. Rute TSP ini memuat semua titik pada graph tersebut tepat satu kali. 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 Artificial Bee Colony.Dalam implementasi skripsi ini, Artificial Bee Colony akan diterapkan untuk menyelesaikan permasalahan TSP. Artificial Bee Colony merupakan algoritma yang didasarkan kecerdasan berkelompok dari lebah dalam mencari sumber makanan. Tujuan dari penulisan skripsi ini adalah mengetahui penerapan Artificial Bee Colony untuk permasalahan TSP. Dari hasil penulisan ini diperoleh bahwa Artificial Bee Colony mampu menyelesaikan permasalahan TSP dengan baik.
Kata kunci : Graph, Travelling Salesman Problem (TSP), Artificial Bee Colony Pendahuluan Matematika adalah salah satu ilmu yang merupakan dasar dari ilmu – ilmu pengetahuan yang lain. Tidak dipungkiri, kontribusi matematika sangat besar dalam perkembangan IPTEK. Salah satu cabang ilmu dalam matematika yang penerapannya bisa kita rasakan dalam kehidupan sehari –hari adalah graph. Banyak materi dalam graph yang mempunyai manfaat untuk diterapkan dalam kehidupan sehari – hari, salah satunya adalah Travelling Salesman Problem (TSP). TSP sendiri merupakan permasalahan dari seorang sales, dimana sales tersebut harus melewati kota tujuan tepat satu kali dan kembali ke kota asal keberangkatan. Banyak algoritma yang telah dibahas dan digunakan untuk pencarian solusi dari masalah TSP ini. Pada skripsi ini membahas penyelesaian permasalahan TSP dengan menggunakan Artificial Bee Colony. Artificial Bee Colony adalah salah satu algoritma yang didasarkan pada kecerdasan berkelompok. Menurut Chong (2006) Artificial Bee Colony mampu menyelesaikan permasalahan TSP lebih baik dibandingkan dengan algoritma lain yang juga didasarkan pada kecerdasan berkelompok. Dalam Artificial Bee Colony ada beberapa tahapan yang harus dilakukan untuk memperoleh solusi dari permasalahan TSP. Tahapan – tahapan itu meliputi pembentukan rute, inisialisasi, tahap Lebah Pekerja (Employed Bee Phase ), tahap evaluasi populasi, tahap Lebah Penjaga ( Onlooker Bee Phase ), tahap Lebah Pengintai ( Scout Bee Phase ).
Pembahasan Artificial Bee Colony untuk Travelling Salesman Problem (TSP) Penyelesaian permasalahan TSP dengan menggunakan Artificial Bee Colony melalui beberapa tahapan. Tahapan – tahapan itu didasarkan pada perilaku lebah dalam mencari sumber makanan dan menginformasikan letak sumber makanan tersebut pada lebah yang lain. Berikut tahapan – tahapan dari Artificial Bee Colony. 1. Pembentukan rute Untuk pembentukan rute dalam masalah Travelling Salesman Problem pada kasus ini digunakan metode Nearest Neighboor . Rute – rute yang terbentuk menjadi kumpulan sumber makanan dimana sumber – sumber makanan tersebut akan dijadikan acuan dalam penyelesaian Travelling Salesman Problem menggunakan Artificial Bee Colony. 2. Inisialisasi Dalam tahap inisialisasi ini semua rute yang sudah terbentuk dianggap sebagai sumber makanan dan akan diseleksi oleh para lebah untuk menentukan rute mana yang terbaik dan merupakan solusi dari permasalahan. Pada tahap ini diberikan nilai percobaan dari setiap kemungkinan solusi sama dengan 0. Proses inisialisasi dari kemungkinan solusi (sumber makanan) dilakukan secara random dengan persamaan sebagai berikut : xij = x j min + rand (0,1).( x j max − x j min ) Keterangan : •
xij = inisialisasi kemungkinan solusi ke-i dengan parameter ke-j
•
xjmin = nilai kemungkinan solusi terkecil berdasarkan parameter j
•
xjmax = nilai kemungkinan solusi terbesar berdasarkan parameter j
•
rand(0,1) = nilai random antara 0 sampai 1
•
i = 1 . . . SN, SN adalah jumlah kemungkinan solusi (sumber makanan)
•
j = 1. . .D, D adalah jumlah parameter yang digunakan.
3.
Tahap Lebah Pekerja ( Employed Bee Phase ) Setelah penginisialisasian selesai para lebah pekerja bertugas untuk memperluas nilai dari setiap kemungkinan solusi yang ada dengan menggunakan persamaan sebagai berikut : vij = xij + φij .( xkj − xij ) Keterangan : •
vij = nilai perluasan kemungkinan solusi ke-i dengan parameter j
•
xij = nilai kemungkinan solusi ke-i dengan parameter j
•
i = 1 . . . SN, SN adalah jumlah kemungkinan solusi (sumber makanan)
•
j = 1. . .D, D adalah jumlah parameter yang digunakan.
•
k = 1. . .SN, SN adalah jumlah parameter yang digunakan.
φij = bilangan real random antara [-1,1] • Setelah setiap kemungkinan solusi diperluas, akan diaplikasikan greedy selection antara nilai kemungkinan solusi xi dengan nilai baru hasil perluasan yaitu vi . Jika nilai vi lebih kecil dari nilai xi maka nilai vi tersebut akan dianggap sama dengan nilai xi dan nilai percobaan tetap bernilai 0. Jika tidak, nilai xi yang disimpan dan nilai percobaan ke-i ditambah dengan 1. Proses ini berulang sampai jumlah perluasan sama dengan jumlah sumber makanan.(Pan.2009). 4.
Tahap evaluasi populasi Setelah setiap kemungkinan solusi diperluas dan dibandingkan dengan nilai awal inisialisasi, tahap berikutnya adalah penghitungan kualitas dari setiap kemungkinan solusi menggunakan fungsi fitness sebagai berikut : 1 , f ( xi ) ≥ 0 fitness( x ) (1 + f ( xi )) i
1 + f ( xi ) , f ( xi ) < 0
Keterangan : •
i = 1 . . . SN, SN adalah jumlah kemungkinan solusi (sumber makanan)
5.
Tahap Lebah Penjaga ( Onlooker Bee Phase) Setelah semua perluasan untuk setiap kemungkinan solusi di tahap lebah pekerja terpenuhi dan telah dihitung masing – masing nilai probability, informasi yang diperoleh lebah pekerja akan ditunjukkan kepada lebah penjaga. Lebah penjaga yang menerima informasi tersebut bertugas untuk menghitung nilai probability dari setiap kemungkinan solusi yang ada dengan menggunakan rumus sebagai berikut : fitnessi pi = SN ∑ fitnessi i =1
Keterangan :
•
fitnessi = nilai fitness solusi ke-i
•
∑ fitness = jumlah dari nilai fitness ke- i sampai SN
SN i
i =1
Setelah nilai probability dari setiap kemungkinan solusi dihitung, lebah penjaga akan memilih kemungkinan solusi mana yang akan ditelusuri lebih lanjut oleh Lebah Pengintai dengan menggunakan metode roulette-wheel .
6.
Tahap Lebah Pengintai ( Scout Bee Phase ) Untuk mengaplikasi metode roullete-wheel , dipilih bilangan real secara random antara [0,1] untuk setiap kemungkinan solusi. Jika nilai pi lebih besar dari bilangan random yang ditentukan, maka lebah penjaga akan menugaskan lebah pengintai untuk memperluas kembali kemungkinan solusi yang terpilih tersebut sesuai dengan tahap lebah pekerja sebelumnya. Setelah kemungkinan solusi terpilih diperluas, akan diaplikasikan greedy selection antara nilai kemungkinan solusi xi dengan nilai baru hasil perluasan yaitu vi. Jika nilai vi lebih kecil dari nilai xi maka nilai vi tersebut akan dianggap sama dengan nilai xi. Jika tidak, nilai vi yang disimpan dan nilai percobaan ke-i ditambah dengan 1. Proses ini berulang
sampai jumlah perluasan sesuai dengan kemungkinan solusi. Setelah semua kemungkinan solusi memiliki nilai percobaan, akan dipilih kemungkinan solusi dengan nilai percobaan maksimum dan kemungkinan solusi tersebut menjadi pilihan solusi terbaik. Proses kembali menuju tahap lebah pekerja (Employed Bee Phase) dan berulang sampai kriteria pembatas terpenuhi, dimana kriteria pembatas yang dimaksud adalah jumlah lebah dalam colony. Untuk mempermudah pemahaman tentang Artificial Bee Colony, berikut flowchart dari tahapan – tahapan Artificial Bee Colony :
Flowchart Artificial Bee Colony untuk TSP
Uji Coba Program Pada penulisan skripsi ini dibuat juga alat bantu program untuk menyelesaikan permasalahan TSP dengan Artificial Bee Colony. Alat bantu program ini dibuat menggunakan Software Borland Delphi 7. Akan dilakukan uji coba program yang telah dibuat. Terdapat suatu permasalahan TSP dengan 5 titik, diman atitik ke-0 adalah titik asal. Berikut gambar permasalahan TSP :
Gambar Permasalahan TSP
Untuk hasil penyelesaian permasalahan TSP diatas sebagai berikut:
Gambar Penyelesaian TSP dengan program Artificial Bee Colony
Dari gambar diatas dapat kita lihat solusi dari permasalahan TSP tersebut menghasilkan rute 0 – 3 – 1 – 4 – 2 – 0 dengan panjang rute 21. Kesimpulan dan Saran Kesimpulan 1. Artificial Bee Colony mampu menyelesaikan permasalahan TSP dengan menggunakan tahapan yang diberikan. 2. Pembuatan program Artificial Bee Colony sebagai alat bantu perhitungan sangat membantu para sales untuk menentukan rute perjalanan yang lebih minimum dalam setiap permasalahan Travelling Salesman Problem yang ditemui. Program Artificial Bee Colony ini mampu menyelesaikan masalah Travelling Salesman Problem dengan jumlah konsumen yang besar. Saran 1. Perlu adanya percobaan lebih lanjut untk penerapan Artificial Bee Colony 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.
Daftar Rujukan Amin, Aulia A.,Ikhsan, Mukhamad., Wibisono, Lastiko. 2003. Travelling Salesman Problem. ITB. Chong, C. S. , Sivakumar, A.I , Low, M. Y. H. And Gay, K.L. 2006. “A Bee Colony Optimization Algorithm To Job Shop Scheduling”. [online]. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.3897&rep= rep1&type=pdf. Desiani, A., Arhami, M.2005. Konsep Kecerdasan Buatan. Yogyakarta: Andi. Garfinkel, RS dan Nemhauser, GL. 1972. Integer Programming. New York: John Wiley & Sons. Habibi, Bakhtiar. 2006. Penyelesaian Travelling Salesman Problem dengan menggunakan Simullated Annealing. Skripsi tidak diterbitkan. Malang: Universitas Negeri Malang. Herdhiyanto, Ferry. 2005. Penyelesaian Travelling Salesman Problem dengan menggunakan Algoritma Koloni Semut. Skripsi tidak diterbitkan. Malang: Universitas Negeri Malang. Karaboga, Darvis, 2005. An idea based on Honey Bee Swarm for Numerical Optimization. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department. Kusumadewi, Sri. 2003. Artificial Intelegence: Teknik dan aplikasinya. Yogyakarta: Graha Ilmu. Pan, Jeng-Shyang, 2009. Enhanced Artificial Bee Colony Optimization. Singh, Anshul, 2012. Augmentation of Travelling Salesman Problem using Bee Colony Optimization.
