APLIKASI ALGORITMA ANT SYSTEM (AS) DALAM KASUS TRAVELLING SALESMAN PROBLEM (TSP)
Dedy Mulia
PROGRAM STUDI MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH JAKARTA 2011 M/1432 H
APLIKASI ALGORITMA ANT SYSTEM (AS) DALAM KASUS TRAVELLING SALESMAN PROBLEM (TSP)
SKRIPSI
Diajukan Kepada Universitas Islam Negeri (UIN) Syarif Hidayatullah Jakarta Untuk Memenuhi Salah Satu Persyaratan Dalam Memperoleh Gelar Sarjana Sains Fakultas Sains dan Teknologi
Oleh : Dedy Mulia 107094003053
PROGRAM STUDI MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH JAKARTA 2011 M / 1432 H
ii
PERNYATAAN
DENGAN INI SAYA MENYATAKAN BAHWA SKRIPSI INI BENARBENAR HASIL KARYA SENDIRI YANG BELUM PERNAH DIAJUKAN SEBAGAI SKRIPSI ATAU KARYA ILMIAH PADA PERGURUAN TINGGI ATAU LEMBAGA MANAPUN.
Jakarta, 31 Oktober 2011
Dedy Mulia NIM. 107094002843
iv
PERSEMBAHAN Alhamdulillahirobbil’alamin, segala puji bagi Allah, Tuhan Semesta Alam Skripsi ini saya persembahkan untuk Bapakku Abdul Madjid dan Ibuku Masdalifah, Serta Adikku, keluarga besarku, dan Keluarga besar Prodi Matematika, Semoga selalu diridhoi Allah SWT, selalu dalam lindungan-Nya, serta selalu dibukakan pintu rahmat, kasih sayang, dan hidayah-Nya Amin
MOTTO Allah-lah yang menciptakan tujuh langit dan seperti itu pula bumi. Perintah Allah berlaku padanya, agar kamu mengetahui bahwasanya Allah maha kuasa atas segala sesuatu, dan sesungguhnya Allah ilmunya benar-benar meliputi segala sesuatu. (Q.S Ath Thalaq: 12)
”Jadilah orang yang sukses karena sukses adalah hak saya”.
”Jika saya mempunyai seribu ide dan hanya satu yang terwujud dengan baik,saya puas”.
v
ABSTRAK Algoritma semut adalah sebuah metodologi yang dihasilkan melalui pengamatan terhadap semut. Algoritma semut merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik. Algoritma ini terinspirasi oleh perilaku semut dalam menemukan jalur dari koloninya menuju makanan. Di dalam algoritma Semut terdapat sejumlah semut buatan, yang ditugaskan untuk mencari solusi terhadap suatu masalah optimisasi, salah satunya menemukan jalur terpendek. Dalam tulisan ini membahas tentang penggunaan graf dalam algoritma semut untuk mencari solusi optimal pada Traveling Salesman Problem (TSP). Dengan memberikan sejumlah n kota, TSP dapat didefinisikan sebagai suatu permasalahan dalam menemukan jalur terpendek dengan mengunjungi setiap kota yang ada hanya sekali.
Kata Kunci : Algoritma Semut, Graf, dan Travelling Salesman Problem.
vi
ABSTRACT Ant Algorithm is a methodology yielded by perception to ant. Ant Algorithm represents the technique probabilistic to finish the computing problem by finding best path passing the graph. This algorithm is inspirited by ant behavior in finding path from the nest to the food. In Ant algorithm there are number of artificial ants, which is assigned to look for the solution to an optimization problem, one of them is find the shortest path. This article study about graph which is used in Ant algorithm to look for the optimal solution in Traveling Salesperson Problem (TSP). By giving a number of n cities, TSP can be defined as a problem of finding shortest path by visiting each city for once.
Keyword : Ant Algorithm, Graph, and Travelling Salesman Problem.
.
vii
KATA PENGANTAR ﺑﺴﻢ اﷲ اار ﺣﻤﻦ اار ﺣﯿﻢ
Assalamu’alaikum Warahmatullahi Wabarakatuh Alhamdulillah, Segala puji bagi Allah, Tuhan Semesta Alam, yang senantiasa melimpahkan rahmat dan nikmat-Nya kepada kita semua, tak terkecuali pada penulis, hingga penulis dapat menyelesaikan skripsi “Aplikasi Algoritma Ant System (AS) Dalam Kasus Travelling Salesman Problem (TSP)”. Shalawat serta salam senantiasa tercurah kepada Nabi Muhammad SAW, manusia biasa yang menjadi luar biasa karena kecerdasannya, kemuliaan akhlaqnya, keluhuran budi pekertinya, dan insya Allah hingga di akhir hidup nanti, sunnahsunnah Rasulullah tetap subur. Dalam penyusunan skripsi ini, penulis banyak mendapat dorongan, semangat, dan bimbingan serta kritikan dari berbagai pihak. Oleh karena itu, pada kesempatan ini penulis ingin mengucapkan terima kasih kepada : 1. Ayahanda dan ibunda serta adik-adikku yang selalu memberikan do’a, kasih sayang, dukungan dan semangat yang tiada henti-hentinya. 2. Bapak Dr. Syopyansyah Jaya Putra, M.Sis, Dekan Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta 3. Ibu Yanne Irene, M.Si. Ketua Program Studi Matematika Fakultas Sains dan Teknologi UIN Syarif Hidayatullah Jakarta
viii
4. Ibu Yanne Irene, M.Si, selaku pembimbing I dan Suma’inna, M.Si, selaku pembimbing II, yang bersedia dengan senang hati membimbing serta mengarahkan penulis. 5. Seluruh dosen dan karyawan Proram Studi Matematika, yang telah memberikan pengajaran dan ilmunya yang bermanfaat bagi penulis 6. Sahabat-sahabat terbaikku selama mengenyam pendidikan di UIN Jakarta, serta teman-teman se-angkatan dan seperjuangan serta semua pihak yang telah membantu penulis Penulis menyadari bahwa masih banyak kelemahan dan kekurangan yang terdapat pada skripsi ini. Atas dasar itulah penulis memohon maaf yang sebesarbesarnya kepada semua pihak jika terdapat kesalahan yang kurang berkenan. Namun, saran dan kritik selalu penulis harapkan demi perbaikan pada penelitian selanjutnya. Akhir kata, harapan yang besar bahwa skripsi ini dapat bemanfaat dan memberikan kontribusi yang berarti, baik bagi penulis khususnya dan bagi pembaca umumnya. Wassalamu’alaikum Warhmatullahi Wabaraktuh
Jakarta, 31 Oktober 2011
Penulis
ix
DAFTAR ISI
HALAMAN JUDUL ...................................................................................... ii LEMBAR PERSETUJUAN .......................................................................... iii PERNYATAAN ............................................................................................. iv PERSEMBAHAN DAN MOTTO ................................................................. v ABSTRAK...................................................................................................... vi ABSTRACT ................................................................................................... vii KATA PENGANTAR .................................................................................... viii DAFTAR ISI .................................................................................................. x DAFTAR TABEL .......................................................................................... xii DAFTAR GAMBAR ...................................................................................... xiii BAB I
PENDAHULUAN ............................................................................ 1 1.1 Latar Belakang.......................................................................... 1 1.2 Perumusan Masalah .................................................................. 3 1.3 Pembatasan Masalah ................................................................. 3 1.4 Tujuan ..................................................................................... 3 1.5 Manfaat ................................................................................... 4
BAB II LANDASAN TEORI ....................................................................... 5 2.1 Teori Graf ................................................................................. 5 2.2
Jenis Graf ................................................................................ 8
2.3 Lintasan dan Sirkuit Hamilton .................................................. 9 2.4
Representasi Graf ..................................................................... 10
x
2.5 Algoritma Greedy ..................................................................... 12 2.6
Travelling Salesman Problem ................................................... 13
2.7
Algoritma Semut....................................................................... 15 2.7.1 Prinsip Perilaku Semut .................................................... 15 2.7.2 Algoritma Semut Pada Travelling Salesman Problem ....... 17
BAB III METODOLOGI PENELITIAN ..................................................... 19 3.1
Metode Pengumpulan Data ....................................................... 19
3.2 Metode Pengembangan Sistem.................................................. 19 3.3 Perancangan Simulasi ............................................................... 21 3.3.1 Inisialisasi ........................................................................ 21 3.3.2 Pembangunan Solusi......................................................... 22 3.3.3 Pembaharuan Feromon Global .......................................... 23 3.3.4 Perancangan Flowchart ..................................................... 23 3.3.5 Evaluasi Algoritma Semut ................................................ 25 3.3.6 Implementasi TSP dengan Algoritma Semut ..................... 26 BAB IV PERANCANGAN SYSTEM APLIKASI TSP DENGAN AS ....... 30 4.1 Hasil dan Pembahasan Proses Simulasi ..................................... 30 4.2 Perancangan System TSP dengan Algoritma Semut ................. 37 BAB V KESIMPULAN DAN SARAN ........................................................ 42 5.1 Kesimpulan............................................................................... 42 5.2 Saran ........................................................................................ 42 REFERENSI ................................................................................................. 43 LAMPIRAN
xi
DAFTAR TABEL
Tabel 2.1 Matriks Ketetanggan ............................................................... 11 Tabel 2.2 Matriks Bersisian ..................................................................... 11 Tabel 4.1 Koordinat Kota ........................................................................ 31 Tabel 4.2 Jarak Kota ............................................................................... 31 Tabel 4.3 Visibilitas Antar Kota .............................................................. 32 Tabel 4.4 Kunjungan Kota ke-2 Pada Algoritma AS ............................... 33 Tabel 4.5 Kunjungan Kota ke-3 Pada Algoritma AS ............................... 34 Tabel 4.6 Kunjungan Kota ke-4 Pada Algoritma AS ............................... 34 Tabel 4.7 Kunjungan Kota ke-5 Pada Algoritma AS ............................... 35 Tabel 4.8 Kunjungan Kota ke-6 Pada Algoritma AS ............................... 35 Tabel 4.9 Rute yang Ditempuh Oleh Semut pada Algoritma AS .............. 36 Tabel 4.10 Feromon Antar Kota .............................................................. 37
xii
DAFTAR GAMBAR
Gambar 2.1 Contoh Graf..................................................................................... 5 Gambar 2.2 (a) Graf Terhubung dan (b) Graf Tak Terhubung ............................. 7 Gambar 2.3 Graf Tak Berarah ............................................................................. 8 Gambar 2.4 Graf Berarah .................................................................................... 8 Gambar 2.5 (i) Graf Berbobot dan (ii) Graf tak Berbobot ................................... 9 Gambar 2.6 Graf ............................................................................................... 10 Gambar 2.7 Graf dengan 5 Simpul dan 8 Sisi .................................................... 11 Gambar 2.8 Graf ............................................................................................... 12 Gambar 2.9 Graf Lengkap................................................................................. 14 Gambar 2.10 Perjalanan Semut Menentukan Rute Makanan .............................. 17 Gambar 3.1 Flowchart Algoritma Semut Untuk Penyelesaian TSP.................... 24 Gambar 4.1 Graf ............................................................................................... 30 Gambar 4.2 Tampilan Halaman Utama ............................................................. 38 Gambar 4.3 Data Graf Dengan 6 Kota................................................................ 39 Gambar 4.4 Tampilan Hasil Komputasi ............................................................ 40 Gambar 4.5 Tampilan Halaman Hasil ............................................................... 41
xiii
BAB I PENDAHULUAN
1.1. Latar Belakang Traveling Salesman Problem (TSP) dikenal sebagai salah satu masalah optimasi yang banyak menarik perhatian para peneliti sejak beberapa dekade terdahulu [5]. Pada mulanya, TSP dinyatakan sebagai permasalahan dalam mencari jarak minimal sebuah tour tertutup terhadap sejumlah n kota di mana kota-kota yang ada hanya dikunjungi sekali dengan kota awal juga merupakan kota akhir atau tujuan [4]. Pada perkembangannya, ternyata TSP merupakan persoalan yang banyak diaplikasikan pada berbagai persoalan dunia nyata, misalnya: efesiensi pengiriman surat dan barang, perencanaan pemasangan saluran pipa, masalah transportasi, persoalan delivery order (jasa pengantar makanan), dan seterusnya. Terdapat beragam teori algoritma yang dilakukan peneliti untuk menyelesaikan permasalahan TSP seperti, algoritma brute force, algoritma greedy, algoritma genetic, algoritma ant system dll [7]. Berdasarkan penelitian algoritma brute force tidak cukup efisien untuk jumlah simpul yang banyak dan algoritma greedy tidak bisa mendapatkan rute optimal dalam kasus TSP dengan jumlah simpul yang banyak sedangkan algoritma genetic solusi yang dihasilkan belum tentu merupakan solusi yang optimal, karena sangat dipengaruhi oleh bilangan acak yang dibangkitkan. Berdasarkan hasil-hasil
1
penelitian terkait pengguna algoritma Ant System (AS) dalam kasus TSP, antara lain dilakukan oleh Rina Refianti yang berjudul Solusi Optimal TSP dengan Algoritma Ant System, Uzma Septima yang berjudul Implementasi Ant System untuk penyelesaian TSP, dll [7]. Keseluruhannya menyimpulkan bahwa algoritma Ant System (AS) dapat membantu menetapkan langkah-langkah yang paling efektif untuk mencari solusi terbaik menentukan jalur-jalur perjalanan. Untuk algoritma lain tidak dapat menemukan hasil yang efektif dalam kasus TSP. Oleh karen itu, penulis memilih algoritma untuk menyelesaikan masalah TSP yaitu dengan menggunakan algoritma Ant System (AS). Algoritma Ant System (AS) terinspirasi oleh perilaku semut dalam menemukan jalur dari sarangnya menuju makanan [1]. Dalam proses perjalanan semut menuju makanan, terdapat suatu mekanisme untuk mencari lintasan optimal yang akan dilalui semut. Pada awalnya, semut berkeliling secara acak, hingga menemukan makanan. Ketika menemukan makanan mereka kembali ke koloninya sambil memberikan tanda dengan jejak feromon. Setiap semut memiliki feromon, yaitu jejak yang mengidentifikasi sesamanya [1]. Semut lain yang menemukan jalur tersebut tidak akan berjalan dengan acak lagi, melainkan akan mengikuti jejak tersebut dan jika pada akhirnya menemukan makanan kembali menguatkan jejaknya dengan feromon. Seekor semut yang secara tidak sengaja menemukan jalur optimal akan menempuh jalur ini lebih cepat dari rekan-rekannya dan dengan sendirinya meninggalkan feromon lebih banyak dari jalur-jalur yang lebih lambat ditempuh, feromon yang berkonsentrasi tinggi pada akhirnya akan menarik semut-semut lain 2
untuk berpindah jalur, menuju jalur paling optimal, sedangkan jalur lainnya akan ditinggalkan. Pada akhirnya semua semut yang tadinya menempuh jalur yang berbeda-beda akan beralih ke sebuah jalur tunggal yang ternyata paling optimal dari sarang menuju ke tempat makanan.
1.2. Perumusan Masalah Adapun permasalahan yang timbul dari latar belakang adalah menggunakan algoritma Ant System (AS) untuk memecahkan permasalahan TSP berdasarkan jarak yang ditempuh.
1.3. Pembatasan Masalah Agar pembahasan tidak menyimpang, maka perlu dibuat suatu batasan masalah sebagai berikut : 1. Model graf yang digunakan adalah graf berhingga, graf terhubung, graf tak berarah dan graf berbobot. 2. Hanya menentukan rute yang optimal berdasarkan jarak. 3. Hanya menggunakan bahasa pemrograman visual basic 6.0.
1.4 Tujuan 1.
Merancang aplikasi algoritma Ant System (AS) untuk penyelesaian kasus TSP.
3
2. Melakukan evaluasi validasi algoritma Ant System (AS) untuk penyelesaian kasus TSP dengan perhitungan manual. 1.4. Manfaat 1. Manfaat bagi salesman: Mempermudah salesman dapat menentukan rute terpendek yang akan dilaluinya. 1. Manfaat bagi pembaca: Mengetahui bagaimana cara algoritma Ant System (AS) melakukan penyelesaian dalam kasus TSP. 2. Manfaat bagi penulis: Dapat merancang aplikasi algoritma Ant System (AS) dalam menyelesaikan permasalahan TSP.
4
BAB II LANDASAN TEORI
2.1 Teori Graf
Graf G didefinisikan sebagai pasangan himpunan (V, E) ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul {v1, v2, v3,...} dan E himpunan sisi yang mungkin kosong yang elemennya merupakan pasangan tak urut dari elemen-elemen di V [5]. Biasanya elemen E dinotasikan dengan ek = (vi , vj). Simpul dalam graf pada tulisan ini merupakan kota dan sisi merupakan rute atau jalan yang menghubungkan antar kota.
Gambar 2.1 Contoh Graf Keterangan Gambar: G adalah graf dengan: V = { v1, v 2, v3, v4, v5} E = { e2, e3, e4, e5, e6, e7}
5
Dalam teori graf banyak istilah-istilah dasar mengenai graf yang perlu diketahui, antara lain: 1.
Ketetanggaan Dua buah simpul pada graf dikatakan bertetangga bila kedua simpul tersebut terhubung langsung dengan sebuah sisi. Dengan kata lain, vi bertetangga dengan vj pada graf G jika terdapat sisi ( vi,vj ) pada graf G [8]. Berdasarkan Gambar 2.1 , simpul v1 bertetangga dengan simpul v2 dan v3, tetapi simpul v1 tidak bertetangga dengan simpul v4. Simpul v5 bertetangga dengan simpul v4, tetapi simpul v5 tidak bertetangga dengan simpul v2.
2.
Bersisian Jika sebuah sisi menempel pada sebuah simpul sebagai titik ujungnya, maka sisi tersebut dikatakan bersisian dengan simpul tersebut demikian juga sebaliknya [8]. Misalnya e = ( vi,vj ) adalah sisi pada sebuah graf G, maka dapat dikatakan sisi e bersisian terhadap simpul vi dan vj. Contohnya pada Gambar 2.1 yaitu sisi e3 besisian dengan simpul v1 dan v2, tetapi sisi e3 tidak bersisian dengan simpul v3. Sisi e7 bersisian dengan simpul v4 dan vs tetapi sisi e3 tidak bersisian dengan simpul v2.
3.
Lintasan Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan selang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,…, vn-1, en, vn sedemikian senhhingga e1 = (v0 , v1 ), e2 = (v1 , v2 ),. . .
6
, en = (vn , vn+1 ) adalah sisi-sisi dari graf G [5]. Lintasan yang berawal dan berakhir pada simpul yang sama diebut lintasan tertutup, sedangkan lintasan yang tidak berawal dan berakhir pada simpul yang sama disebut lintasan terbuka. Berdasarkan Gambar 2.1, lintasan v1, e3, v2, e2, v4, e6, v 3 adalah lintasan terbuka dan lintasan v1, e3, v2, e2, v4, e6, v3, e4, v1 adalah lintasan tertutup. 4.
Sirkuit Sirkuit merupakan lintasan yang berawal dan berakhir pada simpul yang sama [5]. Dengan kata lain Sirkuit dari suatu graf G adalah suatu lintasan tertutup. Berdasarkan Gambar 2.1, lintasan v1, e4, v3, e5, v1 adalah sebuah sirkuit.
5.
Graf terhubung dan Graf tak terhubung Suatu graf G dikatakan graf terhubung jika untuk setiap pasangan simpul di dalam G terdapat paling sedikit satu lintasan [5]. Sebaliknya jika dalam suatu graf G ada pasangan simpul yang tidak mempunyai lintasan penghubung maka graf yang demikian dinamakan graf tak terhubung [5].
Gambar 2.2 (a) Graf Terhubung dan (b) Graf Tak Terhubung
7
2.2 Jenis Graf Sisi pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis: 1. Graf tak-berarah Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah [5]. Pada graf tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak di perhatikan. Jadi ( vi, vj ) = (vj, vi).
Gambar 2.3 Graf tak berarah
2. Graf berarah Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah [5]. Pada graf berarah, ( vi , vj ) dan (vj , vi), menyatakan duah sisi yang berbeda , dengan kata lain ( vi , vj ) ≠ (vj , vi).
Gambar 2.4 Graf berarah 8
Berdasarkan bobot setiap sisi secara umum graf dibedakan atas 2 jenis: 1. Graf berbobot Graf berbobot adalah graf yang setiap sisinya diberi sebuah bobot atau nilai [8]. 2. Graf tak berbobot Graf tak berbobot adalah graf yang setiap sisinya tidak diberi bobot atau nilai [8].
(i) (ii) Gambar 2.5 (i) Graf berbobot dan (ii) graf tak berbobot
2.3 Lintasan dan Sirkuit Hamilton Lintasan Hamilton adalah lintasan yang melalui tiap simpul di dalam graf G tepat satu kali [3]. Bila lintasan itu kembali lagi ke simpul awal dan membentuk lintasan tertutup, maka lintasan tertutup itu dinamakan Sirkuit Hamilton [3]. Jadi, Sirkuit Hamilton adalah sirkuit yang melalui tiap simpul di dalam graf G tepat satu kali, kecuali simpul awal dan simpul akhir.
9
Gambar 2.6 Contoh Graf
Keterangan Gambar: (a) Graf yang memiliki lintasan Hamilton (misal: c, b, a, d) (b) Graf yang memiliki sirkuit Hamilton (misa: a, b, c, d, a) (c) Graf yang tidak memiliki lintasan maupun sirkuit Hamilton
2.4 Representasi Graf Terdapat beberapa cara mempresentasikan graf, dua di antaranya yang sering digunakan adalah matriks ketetanggaan dan matriks bersisian. 1. Matriks Ketetanggan Matriks ketetanggaan didefinisikan sebagai berikut, misalkan A = (aij) adalah matriks m × m yang didefinisikan oleh, =
1, 0,
Perhatikan Gambar 2.6 menunjukkan graf berarah yang terdiri dari 5 simpul dan 8 sisi serta Tabel 2.1 yang menunjukkan matriks ketetanggannya.
10
Gambar 2.7 Graf dengan 5 simpul dan 8 sisi
Tabel 2.1 Matriks ketetanggan
2. Matriks Bersisian Matriks bersisian didefinisikan sebagai berikut, misalkan B = (bij) adalah matriks m × n yang didefinisikan oleh, =
1, 0,
ℎ
Perhatikan Gambar 2.7 menunjukkan graf berarah yang terdiri dari 5 simpul dan 8 sisi serta Tabel 2.2 yang menunjukkan matriks bersisiannya.
Tabel 2.2 Matriks bersisian
11
2.5 Algoritma Greedy Algoritma greedy adalah algoritma yang memecahkan masalah langkah demi langkah dan merupakan salah satu metode dalam masalah optimasi [7]. Algorima greedy membentuk solusi langkah per langkah sebagai berikut : 1. Pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. 2. Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang terlihat memberikan perolehan terakhir, yaitu dengan membuat pilihan optimum lokal pada setiap langkah dan diharapkan akan mendapatkan solusi optimum global.
Gambar 2.8 ContohGraf Pada Gambar 2.8 terdapat 6 kota jalur yang menghubungkan kota-kota tersebut beserta antar kotanya dari kota A (asal) ke kota F (tujuan). Mula-mula proses berawal dari simpul A sebagai simpul keberangkatan. Terdapat 2 jalur yang memungkinkan yaitu jalur AB dengan jarak 29 dan jalur AD dengan jarak 7, maka AD terpilih karena jaraknya lebih kecil daripada AB. Dari D terdapat 2 jalur yang
12
memungkinkan, yaitu DC dengan jarak 12 dan DE dengan jarak 15. DC terpilih karena jaraknya lebih kecil daripad DC. Dari C terdapat 1 jalur yang , yaitu CF dengan jarak 17, maka yang CF terpilih. Karena simpul tujuan sudah tercapai maka algoritma greedy berhenti. Lintasan terpendeknya adalah A → D → C → F dengan total jarak 36.
2.6 Travelling Salesman Problem Travelling Salesman Problem termasuk persoalan yang diilhami oleh masalah seorang pedagang yang berkeliling mengunjungi sejumlah kota [3]. Deskripsi persoalannya adalah sebagai berikut: diberikan sejumlah dan jarak antar kota. Tentukan sirkuit terpendek yang harus dilalui oleh seseorang pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan. Kota dapat dinyatakan sebagai simpul graf, sedangkan sisi menyatakan jalan yang menghubungkan antar dua kota. Bobot pada sisi menyatakan jarak antara dua kota. Dalam tulisan ini TSP yang dibahas adalah TSP simetris, yaitu jarak dari kota 1 ke kota 2 adalah sama dengan jarak dari kota 2 ke kota 1 dan graf yang direpresentasikan sebagai permasalahannya merupakan graf yang terhubung secara penuh artinya pada setiap simpul yang ada pasti terhubung dengan simpul yang lain [6].
13
Persoalan perjalanan pedagang tidak lain menentukan sirkuit Hamilton yang memiliki
bobot
minimum
pada
sebuah
graf
terhubung.
Pada persoalan TSP ini, jika setiap simpul mempunyai sisi ke simpul yang lain. Pada sebarang graf lengkap dengan n buah simpul (n > 2),jumlah sirkuit Hamilton yang berbeda adalah (n -1)!/2 [5]. Contoh kasus dalam TSP sebagai berikut:
Gambar 2.9 Graf Lengkap
Graf lengkap dengan n = 4 simpul seperti yang ditunjukkan pada Gambar 3.1. Graf tersebut memiliki (4 – 1)!/2 = 3 sirkuit Hamilton , yaitu: I1 = (a, b, c, d, a) atau (a, d, c, b, a) ==> panjang rute = 10 + 12 + 8 + 15 = 45 I2 = (a, c, d, b, a) atau (a, b, d, c, a) ==> panjang rute = 12 + 5 + 9 + 15 = 41 I3 = (a, c, b, d, a) atau (a, d, b, c, a) ==> panjang rute = 10 + 5 + 9 + 8 = 32 Jadi, sirkuit Hamilton terpendek adalah I3 = (a, c,b, d, a) atau (a, d, b, c, a) dengan panjang sirkuit = 10 + 5 + 9 + 8 = 32.
14
2.7 Algoritma Semut Seiring berkembangnya pemikiran, ditemukan sejumlah algoritma dalam AI (Artifical Intelligence) yang mendapat inspirasi dari alam. Algoritma tersebut di antaranya adalah: cara kerja otak yang luar biasa mengilhami neural network, genetic algorithm belajar dari proses evolusi, dan dari semut menyelesaikan masalah optimisasi [3]. Pada tahun 1996, dunia AI diperkenalkan dengan algoritma Semut oleh Moyson dan Manderick dan secara meluas dikembangkan oleh Marco Dorigo, merupakan algoritma yang terinspirasi oleh perilaku semut dalam menemukan jalur dari sarangnya menuju makanan [2]. 2.7.1 Prinsip Perilaku Semut Semut adalah serangga sosial yang hidupnya berkoloni, dapat bekerja sama dengan sesamanya dalam melakukan pekerjaan secara efektif. Perilaku semut dalam menemukan makanan dari sarangnya menghasilkan jalur yang optimal dengan menemukan jalur terpendek [2]. Semut juga mampu mengindera lingkungannya yang kompleks untuk mencari makanan dan kemudian kembali ke sarangnya dengan meninggalkan zat feromon pada jalur-jalur yang mereka lalui [1]. Feromon adalah zat kimia yang berasal dari kelenjar endokrin dan digunakan oleh makhluk hidup untuk mengenali sesama jenis, individu lain, kelompok, dan untuk membantu proses reproduksi. Proses peninggalan feromon ini dikenal sebagai stigmergy, yaitu sebuah proses memodifikasi lingkungan yang tidak hanya bertujuan untuk mengingat jalan pulang ke sarang, tetapi juga memungkinkan para semut berkomunikasi dengan 15
sesamanya [2]. Seiring waktu, bagaimanapun juga jejak feromon akan menguap dan akan mengurangi kekuatan daya tariknya. Lebih lama seekor semut pulang pergi melalui jalur tersebut, lebih lama jugalah feromon menguap [6]. Agar semut mendapatkan jalur optimal dalam perjalanannya, diperlukan beberapa proses: 1. Pada awalnya, semut berkeliling secara acak, hingga menemukan makanan. 2. Ketika menemukan makanan mereka kembali ke sarangnya sambil memberikan tanda dengan jejak feromon. 3. Jika semut-semut lain menemukan jalur tersebut, maka mereka tidak akan bepergian dengan acak lagi, melainkan akan mengikuti jejak tersebut. 4. Jika pada akhirnya mereka pun menemukan makanan, maka mereka kembali dan menguatkan jejaknya. 6. Feromon yang berkonsentrasi tinggi pada akhirnya akan menarik semut-semut lain untuk berpindah jalur, menuju jalur paling optimal, sedangkan jalur lainnya akan ditinggalkan. Gambar 2.10 menujukkan perjalanan semut dalam menemukan jalur terpendek dari sarang ke sumber makanan.
16
Gambar 2.10 Perjalanan semut menentukan rute makanan
2.7.2 Algoritma Semut Pada Traveling Salesman Problem Secara informal, algoritma Semut bekerja sebagai berikut. Setiap semut memulai turnya melalui sebuah kota yang dipilih secara acak (setiap semut memiliki kota awal yang berbeda). Secara berulang kali, satu-persatu kota yang ada dikunjungi oleh semut dengan tujuan untuk menghasilkan tur yang lengkap (yaitu mengunjungi masing-masing kota sekali saja). Semut lebih suka untuk bergerak menuju ke kotakota yang dihubungkan dengan sisi yang pendek atau memiliki tingkat feromon yang tinggi. Setiap semut memiliki sebuah memori, dinamai daftar semut, yang berisi semua kota yang telah dikunjunginya pada setiap tur. Daftar semut ini mencegah semut untuk mengunjungi kota-kota yang sebelumnya telah dikunjungi selama tur tersebut berlangsung.
17
Setelah semua semut menyelesaikan tur mereka dan daftar semut menjadi penuh, sebuah aturan pembaruan feromon dilaksanakan pada setiap semut. Penguapan feromon pada semua sisi dilakukan, dan kemudian setiap semut menghitung panjang tur yang telah mereka lakukan lalu menaruh sejumlah feromon pada sisi-sisi yang merupakan bagian dari tur mereka yang sebanding dengan kualitas dari solusi yang mereka hasilkan. Semakin pendek sebuah tur yang dihasilkan oleh seekor semut, jumlah feromon yang diletakkan pada sisi-sisi yang dilaluinya pun semakin besar, dengan demikian sisi yang merupakan bagian dari tur-tur yang pendek adalah sisi-sisi yang menerima jumlah feromon yang lebih besar. Hal ini menyebabkan
sisi
yang
diberi
feromon
lebih
banyak
akan
lebih
diminati/dipertimbangkan pada tur-tur selanjutnya, dan sebaliknya sisi-sisi yang tidak diberi feromon menjadi kurang diminati. Dan juga, jalur terpendek yang ditemukan oleh semut disimpan dan semua daftar semut dikosongkan kembali.
18
BAB III METODOLOGI PERANCANGAN SISTEM
3.1 Metode Pengumpulan Data Graf yang digunakan untuk menerapkan aplikasi ini adalah berupa data dengan simpulnya adalah kota-kota dan sisinya adalah jarak antar kota tersebut. Data tersebut dapat diperoleh dari data graf yang di input oleh pengguna. Aplikasi ini membutuhkan batuan google map. Fungsi google map disini adalah mendapatkan koordinat lokasi yang hendak di hendak dikunjungi.
3.2 Metode Pengembangan Sistem Tahap pengembangan sistem di kenal juga sebagai tahap mendefinisikan rencana aplikasi. Pada fase ini penulis melakukan identifikasi mengenai ; a. Identifikasi masalah Permasalahan dalam mencari jarak terpendek dari sejumlah kota yang harus dikunjungi tepat sekali tanpa mengunjungi kota yang sama dua kali. Dalam
skripsi ini, penulis
merancang sebuah
aplikasi pemecahan
permasalahan TSP untuk pencarian rute terpendek untuk satu jenis tipe user. Tipe user-nya yang bergerak di bidang jasa pengiriman barang atau surat. User tipe ini misalkan PT.POS atau perusahaan ekspedisi barang seperti TIKI untuk untuk memperoleh jarak terpendek dari lokasi-lokasi yang dikunjungi.
19
b. Analisis kebutuhan masukan Input atau masukan dari aplikasi penentuan jalur terpendek ini, berupa parameter–parameter yang diperlukan dalam algoritma semut yaitu : 1) Data graf berupa banyak kota (n) termasuk koordinat (x,y) yang ditentukan oleh pengguna. 2) Parameter–parameter yang diperlukan dalam perhitungan algoritma semut,yaitu : 1. Tetapan pengendali intensitas jejak semut (α) 2. Tetapan pengendali visibilitas (β) 3. Banyak semut (m) 4. Tetapan penguapan jejak semut (ρ) 5. Jumlah siklus maksimum (NCmax) c. Analisis kebutuhan keluaran Data keluaran yang diperoleh dari aplikasi optimasi TSP ini adalah rute terpendek dari kota-kota yang ditentukan. d. Analisis kebutuhan perangkat lunak Dalam skripsi ini penulis menggunakan beberapa perangkat lunak, antara lain: 1) Microsoft Visual Basic 6.0 2) Kode pemrograman menggunakan notepad
20
e. Analisis kebutuhan perangkat keras Perangkat keras komputer yang digunakan adalah perangkat keras yang dapat mendukung perangkat lunak yang memiliki kemampuan atau tampilan grafis yang cukup baik. Perangkat keras yang digunakan adalah 1) Intel P4 2.4Ghz 2) Memori 256 MB 3) Hardisk 40 GB f. Implementasi perangkat lunak Pada tahap ini penulis melakukan tahapan implementasi dari hasil perancangan yang telah dilakukan. Tahap implementasi ini meliputi: 1) Halaman utama 2) Halaman komputasi 3) Halaman hasil
3.3 Perancangan Simulasi 3.3.1 Inisialisasi Inisialisasi awal feromon (τ0) pada algoritma semut ditentukan melalui persamaan berikut :
τ0 =
(3.1)
keterangan : k
= jumlah semut
Cgreedy = panjang tur yang dihasilkan melalui algoritma greedy
τ0
= feromon awal 21
Nilai visibilitas dinyatakan dengan ηij. Nilai visibilitas ηij dihitung berdasarkan persamaan berikut :
ηij =
(3.2)
keterangan : ηij = invers jarak dari kota i ke kota j dij = jarak dari kota i ke kota j 3.3.2 Pembangunan Solusi Pada aturan ini, semut akan memilih kota secara acak. Aturan ini dinyatakan sebagai berikut :
(3.3)
Keterangan : Pij,k (t) = peluang semut ke-k untuk mengunjungi kota j dari kota i pada iterasi ke-t
τij(t) = inisialisasi feromon antara kota i dan kota j pada iterasi ke-t ηij
= invers jarak dari kota i ke kota j
Jik
= kumpulan kota yang akan dikunjungi oleh semut yang berada pada kota i
α
= parameter yang mengontrol feromon (α ≥ 0 )
β
= parameter yang mengontrol jarak (β ≥ 0 ) 22
3.3.3 Pembaharuan feromon global Setelah semua semut menyelesaikan turnya, feromon akan diperbarui secara menyeluruh dengan menghitung perubahan nilai feromon antar kota. Persamaan perubahan ini adalah: ∆ τij,k =
, jika (i,j) ∈ Tk
(3.4)
Keterangan : ∆ τij,k = jumlah feromon yang di tambahkan oleh k Tk
= rute keseluruhan
Lk
= panjang dari rute keseluruhan
Selanjutnya penguapan feromon pada seluruh sisi TSP dengan menggunakan rumus berikut:
τij (baru) ← (1 – p ) τij + ∆ τij,k
(3.5)
keterangan :
τij (baru) = konsentrasi feromon yang baru τij
= inisialisasi feromon antara kota i dan kota j
p
= parameter laju penguapan feromon ( 0 < p ≤ 1)
∆ τij,k
= jumlah feromon yang di tambahkan oleh semut k
3.3.4 Perancangan Flowchart Flowchart digunakan untuk memperjelas perancangan dan algoritma yang akan dibuat, flowchart dari algoritma Semut dapat dilihat pada Gambar 3.1:
23
Mulai
Input Alamat
Inisialiasi Parameter Jalankan tahap setiap semut Pilih Alamat Berikutnya untuk setiap semut
Semua dikunjungi
Komputasikan panjang perjalanan setiap semut Ubah feromon untuk ya perjalanan terbaik
Iterasi maksimum
Tampilkan hasil
Selesai
Gambar 3.1 Flowchart algoritma semut untuk penyelesaian TSP 24
3.3.5 Evaluasi Algoritma Semut Algoritma Semut untuk mencari jalur terpendek dari sebuah graf pada tulisan ini menggunakan semut sebagai agen,setiap semut memiliki turnya masing-masing mulai dari kota awal dan kembali ke kota tersebut dengan mengunjungi masing-masing kota yang ada hanya sekali, untuk mendapatkan hasil terbaik. Algoritma ini dimulai dengan menempatkan setiap semut pada kota awalnya masing-masing yang diwakili oleh simpul yang ada pada graf tersebut. Tur yang dilakukan oleh setiap semut ini dimulai dari sebuah kota awal dan melewati sisi yang menghubungkan n kota yang ada kemudian kembali lagi ke kota awal tersebut. Setelah ditempatkan pada kota awalnya masing-masing, setiap semut memulai turnya dengan memilih kota berikutnya yang akan dikunjungi dengan persamaan probabilitas. Pemilihan kota ini dipengaruhi oleh panjang sisi yang menghubungkan setiap kota dan jumlah feromon yang berada pada sisi tersebut. Sisi yang lebih pendek akan menerima feromon dalam jumlah yang lebih besar. Setelah menentukan kota berikutnya yang akan dituju, semut berjalan melewati sisi yang menghubungkan kedua kota tersebut dan memperbarui jumlah feromon yang terdapat pada sisi yang dilewatinya. Kemudian semut memasukkan sisi dan kota yang dilewatinya itu kedalam daftar semut untuk menandakan bahwa sisi dan kota tersebut merupakan bagian dari tur mereka. Selanjutnya semut memilih lagi kota berikutnya yang akan dikunjungi. Setelah semua semut menyelesaikan tur mereka, panjang tur dari setiap semut dihitung dan dipilih yang paling pendek. Tur terpendek dari setiap siklus 25
akan menjadi tur terbaik. Dari analisa terhadap algoritma Semut ini, beberapa hal yang penting adalah: 1. Dalam pemilihan kota berdasarkan nilai probabilitas diperlukan nilai parameter q0 yang merupakan sebuah bilangan acak dimana 0 ≤ q0 ≤ 1. 2. Setiap semut harus memiliki daftar semut untuk menyimpan hasil turnya masing-masing. Daftar semut berisi kumpulan sisi dan simpul yang merupakan bagian dari tur setiap semut. Nilai dari masing-masing daftar semut akan dikosongkan kembali setiap kali semut akan memulai turnya. 3. Proses perbaikan jejak feromon dipengaruhi oleh dua parameter yaitu ρ suatu koefisien yang bernilai antara 0 sampai 1 dan Δτ didapat dari hasil perkalian antara panjang tur dengan jumlah simpul yang ada pada graf tersebut.
3.3.6 Implementasi TSP dengan Algoritma Semut Diberikan sejumlah kota dan jarak antar kota. Tentukan sirkuit hamilton yang harus dilalui oleh semut, bila semut itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan. Permasalahan melewati setiap kota tepat satu kali dan kembali ke kota asal adalah meliputi pencarian lintasan terpendek pada sebuah graf Hamilton. Apabila contoh kasus tersebut diubah menjadi persoalan pada graf, maka dapat dilihat bahwa kasus tersebut adalah bagaimana menentukan sirkuit Hamilton yang memiliki bobot minimum pada graf tersebut.
26
Dalam algoritma Semut, diperlukan beberapa variabel dan langkahlangkah untuk menentukan jalur terpendek, yaitu: Langkah 1: Inisialisasi harga parameter-parameter algoritma adalah: 1. Intensitas jejak feromon antar kota dan perubahannya (τij ) 2. Banyak kota (n) termasuk koordinat (x,y) atau jarak antar kota(dij ) 3. Tetapan pengendali intensitas jejak semut (α), nilai α ≥ 0 4. Tetapan pengendali visibilitas (β), nilai β ≥ 0 5. Visibilitas antar kota (ηij ) = 1/dij 6. Banyak semut (k) 7.
Tetapan penguapan jejak feromon (ρ), dimana 0 < p ≤ 1
Langkah 2: Pengisian kota pertama ke dalam daftar semut. Hasil inisialisasi kota pertama setiap semut dalam langkah 1 harus diisikan sebagai elemen pertama daftar semut (DS). Hasil dari langkah ini adalah terisinya elemen pertama daftar semut setiap semut dengan indeks kota tertentu, yang berarti bahwa setiap DS(1) bisa berisi indeks kota antara 1 sampai n sebagaimana hasil inisialisasi pada langkah 1. Langkah 3: Penyusunan rute kunjungan setiap semut ke setiap kota. Semut yang sudah terdistribusi ke sejumlah atau setiap kota, akan mulai melakukan perjalanan dari
27
kota pertama masing-masing sebagai kota asal dan salah satu kota-kota lainnya sebagai kota tujuan. Kemudian dari kota ke dua masing-masing, semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang tidak terdapat pada daftar semut sebagai kota tujuan selanjutnya. Perjalanan semut berlangsung terus menerus sampai semua kota satu persatu dikunjungi atau telah menempati daftar semut. Langkah 4: Perhitungan panjang rute tertutup (length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan ini dilakukan berdasarkan daftar semut masing-masing. Setelah Lk setiap semut dihitung, akan didapat minimal panjang rute tertutup setiap siklus. Kemudian akan dihitung perbaikan jejak feromon atau perubahan harga feromon antar kota. Persamaan perubahan ini adalah: ∆ τij,k (t) =
( )
, jika (i,j) ∈ Tk(t)
(3.6)
Keterangan : ∆ τij,k (t)
= jumlah feromon yang di tambahkan oleh k
Lk(t)
= panjang dari rute keseluruhan
Tk(t)
= rute keseluruhan
28
Langkah 5: Perhitungan jejak feromon antar kota untuk siklus selanjutnya. Nilai jejak feromon pada semua lintasan antar kota ada kemungkinan berubah sebab adanya perbedaan jumlah semut dan penguapan feromon. Selanjutnya nilai feromon dihitung dengan persamaan:
τij (baru) ← (1 – p ) τij + ∆ τij,k (t)
(3.7)
keterangan :
τij (baru)
= konsentrasi feromon yang baru
τij
= inisialisasi feromon antara kota i dan kota j
p
= parameter laju penguapan feromon ( 0 < p ≤ 1)
∆ τij,k (t)
= jumlah feromon yang di tambahkan oleh semut k
Langkah 6: Pengosongan daftar semut, dan ulangi Langkah 2 jika diperlukan. Pengosongan daftar semut dilakukan untuk melakukan pengisian urutan kota yang baru pada siklus selanjutnya, jika jumlah maksimum belum tercapai.
29
BAB IV PERANCANGAN SISTEM APLIKASI TSP DENGAN ALGORITMA AS
4.1 Hasil dan Pembahasan Proses Simulasi Pada bab ini penulis melakukan proses simulasi. Simulasi yang dilakukan dengan menginput jumlah kota beserta koordinat kota dan menginput parameter. Data yang diinput pengguna berupa nilai alpha, beta, rho dan banyaknya semut. Kemudian mencari feromon awal dan visibilatas antar kota, setelah mendapatkan feromon awal dan visibilitas antar kota dapat mencari probabilitas antar setiap kota. Setelah semut mengunjungi semua kota maka didapatkan rute minimum yang ditempuh. Setelah informasi mengenai rute minimum diperoleh, dapat mencari pembaharuan feromon untuk merubah feromon awal menjadi feromon yang baru. Berikut contoh penyelesaian TSP dengan Algoritma Semut: Diketahui sebuah graf : 3
4
6
1
2
5
Gambar 4.1 Contoh Graf
30
Dengan input kota berupa koordinat lokasi: Tabel 4.1 Koordinat Kota Kota keX Y 10 30 1 2
30
50
3
20
10
4
50
10
5
60
50
6
40
30
Dengan jarak kota d(i,j), dihitung dengan bentuk dij =
−
+ (
−
)
, jarak antar kota adalah: Jarak
Kota 1
Tabel 4.2 Jarak Kota Kota 2 Kota 3 Kota 4
Kota 1
0.00
28.28
22.36
44.72
53.85
40.00
Kota 2
28.28
0.00
41.23
44.72
30.00
22.36
Kota 3
22.36
41.23
0.00
30.00
56.57
28.28
Kota 4
44.72
44.72
30.00
0.00
41.23
22.36
Kota 5
53.85
30.00
56.57
41.23
0.00
28.28
Kota 6
40.00
22.36
28.28
22.36
28.28
0.00
Kota 5
Kota 6
Parameter–parameter yang digunakan adalah: Alfa (α)
= 1.00
31
Beta (β)
= 1.00
Rho (ρ)
= 0.10
Banyak semut (k)
=6
Feromon awal dengan menggunkan rumus τij = τ0 =
dengan k = 6
dan berdasarkan perhitungan algoritma greedy jaraknya adalah 172.5 dengan kota-kota yang dilewatinya yaitu, kota 1 → kota 3 → kota 6 → kota 2 → kota 5 → kota 4→ kota 1, sehingga τij = τ0 = 0.034 Dengan menggunakan jarak kota yang telah diketahui dapat dihitung visibilitas antar kota dengan rumus (ηij) = 1/dij: Tabel 4.3 Visibilitas Antar Kota Kota ke-
1
2
3
4
5
6
1
0.00
0.036
0.045
0.023
0.019
0.033
2
0.036
0.00
0.024
0.023
0.033
0.045
3
0.045
0.024
0.00
0.033
0.018
0.036
4
0.023
0.023
0.033
0.00
0.024
0.045
5
0.019
0.033
0.018
0.024
0.00
0.036
6
0.033
0.045
0.036
0.045
0.036
0.00
Enam ekor semut mengawali perjalanan dari kota enam kota yang berbeda. Enam kota yang harus dikunjungi, maka seekor semut memerlukan beberapa langkah agar seluruh kota bisa dikunjungi. Pada setiap langkah, semut akan:
32
1. Memilih kota yang dikunjungi secara acak. 2. Mencatat kota yang telah dikunjungi di dalam memori Kota pertama yang dikunjungi semut adalah kota keberangkatan, dimana S1 berangkat dari kota 1, S2 berangkat dari kota 2, S3 berangkat dari kota 3, S4 berangkat dari kota 4, S5 berangkat dari kota 5, dan S6 berangkat dari kota 6. Kota pertama akan disimpan dalam memori masing-masing lalu semut akan mengunjungi kota berikutnya. Proses dilakukan semut pada iterasi pertama adalah sebagai berikut: 1. Mengunjungi kota ke-2
Sem ut
Tabel 4.4 Kunjungan kota ke -2 pada algoritma AS Probabilitas Kota Kota Kota Kota Kota Kota Kota tujuan (j) 1 2 3 4 5 6 0.000 0.231 0.288 0.148 0.122 0.211 3
S1
Kota awal (i) [1]
Memori
S2
[2]
0.224
0.000
0.149
0.143
0.205
0.279
3
[2 3]
S3
[3]
0.288
0.154
0.000
0.211
0.115
0.231
6
[3 6]
S4
[4]
0.155
0.155
0.223
0.000
0.162
0.305
6
[4 6]
S5
[5]
0.146
0.254
0.138
0.185
0.000
0.166
1
[5 1]
S6
[6]
0.170
0.230
0.185
0.230
0.185
0.000
2
[6 2]
[1 3]
Probabilitas sebuah kota bernilai nol jika kota tersebut sudah ada pada memori. Dari Tabel 4.1 dapat dilihat bahwa S1, S4, dan S6 memilih kota memilih kota dengan probabilitas terbesar, yaitu kota 3, kota 6 dan kota 2. Sedangkan S2, S3, dan S5 memilih kota dengan probabilitas kecil, yaitu kota 3, kota 6, dan kota 1 walaupun kota 6, kota 1, kota 2 memiliki probabilitas paling besar. Hal ini 33
menunjukkan bahwa semut S1, S2, S3, S4, S5, dan S6 pada dasarnya memilih suatu kota secara acak. 2. Mengunjungi kota ke-3
S1
Kota awal (i) [1 3]
Tabel 4.5 Kunjungan kota ke -3 pada algoritma AS Probabilitas Kota Memori Kota Kota Kota Kota Kota Kota tujuan (j) 1 2 3 4 5 6 0.000 0.216 0.000 0.297 0.162 0.325 4 [1 3 4]
S2
[2 3]
0.340 0.000 0.000 0.250
0.136
0.272
1
[2 3 1]
S3
[3 6]
0.207 0.283 0.000 0.283
0.226
0.000
4
[3 6 4]
S4
[4 6]
0.220 0.300 0.240 0.000
0.240
0.000
1
[4 6 1]
S5
[5 1]
0.000 0.263 0.328 0.186
0.000
0.168
2
[5 1 2]
S6
[6 2]
0.310 0.000 0.207 0.198
0.284
0.000
2
[6 2 1]
Semut
3. Mengunjungi kota ke-4
S1
Kota awal (i) [1 3 4]
Tabel 4.6 Kunjungan kota ke -4 pada algoritma AS Probabilitas Kota Memori tujuan Kota Kota Kota Kota Kota Kota (j) 1 2 3 4 5 6 0.000 0.0.25 0.000 0.000 0.260 0.450 6 [1 3 4 6]
S2
[2 3 1]
0.000
0.000
0.000
0.307
0.253
0.440
4
[2 3 1 4]
S3
[3 6 4]
0.329
0.329
0.000
0.000
0.342
0.000
5
[3 6 4 5]
S4
[4 6 1]
0.000
0.360
0.450
0.000
0.190
0.000
2
[4 6 1 2]
S5
[5 1 2]
0.000
0.000
0.250
0.260
0.000
0.450
3
[5 1 2 3]
S6
[6 2 1]
0.000
0.000
0.517
0.264
0.218
0.000
1
[6 2 1 3]
Semut
34
4. Mengunjungi kota ke-5
S1
Tabel 4.7 Kunjungan kota ke -5 pada algoritma AS Kota Probabilitas Kota awal Kota Kota Kota Kota Kota Kota tujuan (i) (j) 1 2 3 4 5 6 [1 3 4 6] 0.000 0.555 0.000 0.000 0.445 0.000 5
[1 3 4 6 5]
S2
[2 3 1 4] 0.000 0.000 0.000 0.000 0.347 0.653
6
[2 3 1 4 6]
S3
[3 6 4 5] 0.365 0.635 0.000 0.000 0.000 0.000
2
[3 6 4 5 2]
S4
[4 6 1 2] 0.000 0.000 0.365 0.000 0.635 0.000
5
[4 6 1 2 5]
S5
[5 1 2 3] 0.000 0.000 0.000 0.478 0.000 0.522
4
[5 1 2 3 4]
S6
[6 4 2 1] 0.000 0.000 0.000 0.647 0.353 0.000
3
[6 2 1 3 4]
Semut
Memori
5. Mengunjungi kota ke-6
S1
Kota awal (i) [1 3 4 6 5]
Tabel 4.8 Kunjungan kota ke -6 pada algoritma AS Probabilitas Kota Kota Kota Kota Kota Kota Kota tujuan (j) 1 2 3 4 5 6 0.000 1.000 0.000 0.000 0.000 0.000 2
[1 3 4 6 5 2]
S2
[2 3 1 4 6]
0.000
0.000
0.000
0.000 1.000 0.000
5
[2 3 1 4 6 5]
S3
[3 6 4 5 2]
1.000
0.000
0.000
0.000 0.000 0.000
1
[3 6 4 5 2 1]
S4
[4 6 1 2 5]
0.000
0.000
1.000
0.000 0.000 0.000
3
[4 6 1 2 5 3]
S5
[5 1 2 3 4]
0.000
0.000
0.000
0.000 0.000 1.000
6
[5 1 2 3 4 6]
S6
[6 2 1 3 4]
0.000
0.000
0.000
0.000 1.000 0.000
5
[6 2 1 3 4 5]
Semut
Memori
35
Seluruh kota telah dikunjungi, pembangunan solusi untuk iterasi pertama telah selesai, S1, S2, S3, S4, S5 dan S6 kembali ke kota masing – masing.
Semut
Tabel 4.9 Rute yang ditempuh oleh semut pada algoritma AS Rute Panjang ∆ τij,k
S1
[1 3 4 6 5 2 1]
161.48
0.00619
S2
[2 3 1 4 6 5 2]
188.85
0.00529
S3
[3 6 4 5 2 1 3]
172.51
0.00579
S4
[4 6 1 2 5 3 4]
207.41
0.00482
S5
[5 1 2 3 4 6 5]
204.20
0.00489
S6
[6 2 1 3 4 5 6]
172.51
0.00579
Berdasarkan Tabel 4.7 diketahui bahwa rute terbaik pada iterasi pertama adalah rute yang ditempuh S1 dengan panjang 161.48. Setelah informasi mengenai rute terbaik diperoleh, pembaharuan feromon akan dilakukan jumlah feromon yang ditambahkan sebesar 0.00619. Feromon pada sisi jalan tersebut: τ13 = τ31 = ((1 – 0.1) x 0.034) + 0.00619 = 0.037 τ34 = τ43 = ((1 – 0.1) x 0.034) + 0.00619 = 0.037 τ 46= τ64 = ((1 – 0.1) x 0.034) + 0.00619 = 0.037 τ65 = τ56 = ((1 – 0.1) x 0.034) + 0.00619 = 0.037 τ52 = τ25 = ((1 – 0.1) x 0.034) + 0.00619 = 0.037 τ21 = τ12 = ((1 – 0.1) x 0.034) + 0.00619 = 0.037 Jika pada iterasi berikutnya tidak ditemukan rute yang lebih baik, maka pembaharuan feromon global tetap dilakukan pada rute terbaik saat ini. Karena
36
terjadi perbedaan feromon, yakni nilai feromon akan berkurang sedikit demi sedikit setiap kali semut meninggalkan suatu kota
Feromon
Kota 1
Tabel 4.10 Feromon Antar Kota Kota 2 Kota 3 Kota 4
Kota 1
0.000
0.037
0.037
0.034
0.034
0.034
Kota 2
0.037
0.000
0.034
0.034
0.037
0.034
Kota 3
0.037
0.034
0.000
0.037
0.034
0.034
Kota 4
0.034
0.034
0.037
0.000
0.034
0.037
Kota 5
0.034
0.037
0.034
0.034
0.000
0.037
Kota 6
0.034
0.034
0.034
0.037
0.037
0.000
Kota 5
Kota 6
Dari Tabel 4.10 dapat diperkirakan bahwa pada iterasi berikutnya, semut pada kota 1 cenderung memilih kota ke 2 atau kota ke 3 dibandingkan kota 4. Semut pada kota 2 cenderung memilih kota ke 1 atau kota ke 5. Setelah semua selesai, langkah terakhir adalah mencatat rute terbaik. Berdasarkan tabel feromon maka disimpulkan jarak dengan menggunakan algoritma semut adalah 161.48. Sedangkan kota-kota yang dilewatinya yaitu, kota 1 → kota 3 → kota 4 → kota 6 → kota 5 → kota 2→ kota 1.
4.2 Perancangan Sistem Penyelesaian TSP dengan Algortima Semut Implementasi dari algoritma semut untuk penyelesaian TSP pada tulisan ini diaplikasikan dalam bahasa pemrograman Visual Basic 6.0, aplikasi dari algoritma semut ini dibatasi hanya pada pencarian jalur terpendek dari data graf
37
yang diinput oleh pengguna. Tampilannya terdiri dari beberapa form yang memiliki fungsi masing-masing yang tampil sesuai dengan urutan yang telah diprogram. 1. Halaman Utama Pada halaman utama terdapat beberapa menu antara lain input kota, parameter algoritma, gambar graf dan hasil perhitungan. Tampilan halaman utama dapat dilihat pada Gambar 4.2.
Gambar 4.2 Tampilan Halaman Utama
38
Gambar 4.3 Data Graf dengan 6 Kota
2. Halaman Komputasi Halaman komputasi digunakan untuk melihat hasil komputasi dari program aplikasi pencarian jalur terpendek. data input adalah jumlah kota, koordinat kota, parameter algoritma termasuk siklus maksimum, alfa, beta, Q, rho dan τ ij. Program akan menampilkan gambar graf dan perhitungan jarak. Berikut tampilan dari halaman komputasi.
39
Gambar 4.4 Tampilan Hasil Komputasi
3. Halaman Hasil Halaman ini menampilkan hasil perhitungan dari probabilitas dari setiap semut untuk mengunjungi kota berikutnya, probabilitas kumulatif, kota yang terpilih, penyimpanan kota pada daftar semut, perbaikan jejak feromon pada setiap siklus dan jalur terpendek yang dihasilkan dari setiap siklus.
40
Gambar 4.5 Tampilan Halaman Hasil
Dapat dilihat dari Gambar 4.5 bahwa lintasan terpendek menggunakan algoritma semut adalah 161.48 km dan kota-kota yang dilewatinya yaitu kota 1 → kota 3 → kota 4 → kota 6 → kota 5 → kota 2→ kota 1. Kesimpulannya hasil perhitungan dari program ini dengan menggunakan algoritma semut dalam kasus TSP akan memberikan hasil yang sama dengan hasil secara manual.
41
BAB V KESIMPULAN DAN SARAN
5.1 Kesimpulan Berdasarkan hasil penelitian mengenai Agoritma Semut dalam kasus TSP dapat di simpulkan bahwa : 1.
Pada penyelesaian TSP dengan Algoritma Semut mampu menghasilkan rute optimal yakni panjang rute terpendek.
2.
Persoalan TSP dapat diselesaikan dengan menggunakan Algoritma Semut dengan menyajikan tabel dan perhitungan matematis pada Algoritma Semut.
3.
Kecanggihan teknologi komputer dapat dimanfaatkan untuk mengaplikasikan persoalan TSP dalam akurasi yang cukup singkat dengan hasil yang cukup akurat, sehingga mempermudah dalam pengambilan keputusan untuk melakukan suatu perjalanan.
5.2 Saran Penulis menyarankan untuk pengembangan penelitian selanjutnya dengan data simpul yang lebih besar dan menggunakan algoritma Semut yang berkembang saat ini seperti Ant Colony System (ACS), ACS-3-Opt dan Ant-Q untuk menyelesaikan persoalan TSP yang lebih kompleks dan menggunakan bahasa pemrograman yang berbeda.
42
REFERENSI
[1]
Alfriany Ndoloe. Lita, “Implementasi Algoritma Ant Untuk Menentukan Jalur Terpendek Dalam Proses Pengiriman Surat Pos Dengan Menggunakan Visual Basic 6.0”. Jurnal Mitra Tahun XIV, vol. 2, (2008).
[2]
Fikri Shahabudin. Muhammad, “Studi dan Impementasi Mengenal Algoritma Semut”. Jurnal Teknik Informatika dan Komputer, vol. 3 (2010).
[3]
Helene Iwo. Maria,
Anna Maria, dan Elfira Yolanda Sinaga,
“Penyelesaian Masalah Travelling Salesman Problem Menggunakan Ant Colony System”. Jurnal Media Informatika, vol. 6, (2008). [4]
Ikhsan. Muhammad, Aulia Rahma Amin, “Travelling Salesman Problem”. Jurnal Presitipasi, vol. 5, (2007).
[5]
Munir. Rinaldi, “Matematika Diskrit”. Bandung: Informatika ITB, 2007.
[6]
Refianti. Rina, “Solusi Optimal Travelling Salesman Problem dengan Algoritma Ant Colony System ”. Journal of Informatics and Computer (2005).
[7]
Septima. Uzma, “Implementasi Algoritma Ant Colony System untuk Penyelesaian Travelling Salesman Problem”. Jurnal Percikan Vol 92 (2008).
[8]
Siang. Jong Jek, “Matematika Diskrit dan Aplikasinya pada Ilmu Komputer”. Edisi keempat. Yogyakarta: ANDI, 2009.
41
LAMPIRAN Pseudo code algoritma semut : Input : Matriks D untuk jarak Inisialisasi Parameter pada Algoritma: α, β, p , τ0 k = n {Jumlah semut sama dengan jumlah kota} begin for i=1:n
// untuk setiap sisi//
for j=1:n if i = j η(i,j) =1/d(i,j)
//Visibility//
τ(i,j) = τ0
//pheromone//
else τ(i,j) = 0 end end end for k =1 : k <Menempatkan semut secara acak untuk memilih kota> end
Loop For t = 1 : tmax
//tmax = nomor iterasi//
For k = 1:k
// untuk setiap semut://
< Membangun rute menurut aturan:
< Menghitung Lk(t), panjang dari rute Tk(t) > End If " Apakah solusi terbaik ditemukan?" End For i = 1 : n For j = 1 : n //untuk setiap edge// < Update feromon trail menurut aturan:
End End
Listing Program 1. Inisialisasi Input Parameter: Ncmax = CInt(Flex.TextMatrix(1, 1)) alpa = CDbl(Flex.TextMatrix(2, 1))
Beta = CDbl(Flex.TextMatrix(3, 1)) rho = CDbl(Flex.TextMatrix(5, 1)) Tij = CDbl(Flex.TextMatrix(6, 1))
2. Insialisasi Input Koordinat Dim x, y, angka As Integer ReDim Kordinat(jlhKota, 2) For x = 1 To Flex.Rows - 1 For y = 1 To Flex.Cols - 1 If Flex.TextMatrix(x, y) = "" Then angka = 0 Else angka = CInt(Flex.TextMatrix(x, y)) End If Kordinat(x, y) = angka Next Next HitungJarak
3. Inisialisasi Daftar Semut isi daftar semut awal cetak "" cetak "Isi Daftar semut Awal " l=0 l=l+1 For k = 1 To N Tabu(k, l) = k Next
4. Probabilitas Semut ke Setiap Kota totP = 0 For u = 1 To N 'cari totP If Not CariDaftarSemut(j, u, T) Then totP = totP + Tho(DaftarSemut(j, T), u) ^ alpa * visib(DaftarSemut(j, T), u) ^ Beta End If Next u 'bagikan kt = "" kt2 = "" ReDim p(N) ReDim q(N) For u = 1 To N If CariDaftarSemut(j, u, T) = False Then p(u) = (Tho(Tabu(j, T), u) ^ alpa * visib (DaftarSemut(j, T), u) ^ Beta) / totP Else p(u) = 0 End If kt = kt & Format(p(u), "#,##0.000") & " " Next 5. Probabilitas Komulatif For u = 1 To N If u = 1 Then q(u) = p(u) Else q(u) = q(u - 1) + p(u)
End If kt2 = kt2 & Format(q(u), "#,##0.000") & " " Next
6. Panjang Jalur Setiap Semut Public Function HitungLk(ByVal s As Integer) As Double Dim pk As Double For a = 1 To UBound(DaftarSemut) - 1 pk = pk + jarak (DaftarSemut (s, a), DaftarSemut s, a + 1)) Next 'akhir + awal pk = pk + jarak(DaftarSemut(s, a), (DaftarSemut(s, 1))) Hitung Lk = pk End Function
7. Penentuan Jalur Terpendek JlrTerpendek(Nc) = 1.79769313486232E+307 temp = 0 For k = 1 To N temp = HitungLk(k) PanjangJalur(k) = temp cetak k & " = " & temp If temp < JlrTerpendek(Nc) Then JlrTerpendek(Nc) = temp End If Next
8. Perbaikan Jejak Feromon For k = 1 To N PanjangJalur(k) = HitungLk(k) For s = 1 To N - 1 Dtho(DaftarSemut(k, s), DaftarSemut(k, s + 1)) = _ Dtho(DaftarSemut(k, s), DaftarSemut(k, s + 1))+ visib(DaftarSemut(k, s), DaftarSemut(k,
s
+
1))
/
PanjangJalur(k)
Next Dtho(DaftarSemut (k, s), DaftarSemut(k, s + 1)) = _ Dtho(DaftarSemut(k, s), DaftarSemut(k, s + 1)) + visib(DaftarSemut(k, N), DaftarSemut(k, 1))/PanjangJalur(k) Next For i = 1 To N kt = "" For k = 1 To N Tho(i, k) = rho * Tho(i, k) + Dtho(i, k) kt = kt & Format(Tho(i, k), "#,##0.0000") & " " Next Next
