ALGORITMA SEMUT UNTUK MENCARI JALUR TERPENDEK
YAAYU 060803040
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
UNIVERSITAS SUMATERA UTARA
ALGORITMA SEMUT UNTUK MENCARI JALUR TERPENDEK SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
YAAYU 060803040
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA 2012
UNIVERSITAS SUMATERA UTARA
PERSETUJUAN
Judul Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: ALGORITMA SEMUT UNTUK MENCARI JALUR TERPENDEK : SKRIPSI : YAAYU : 060803040 : SARJANA (S!) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Dituliskan di Medan, 27 Juni 2012
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Dra. Elly Rosmaini, M.Si NIP. 19600520 198503 2 002
Drs. James P. Marbun, M.Kom NIP. 19580611 198603 1 002
Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua,
Prof. Dr. Tulus, M.Si NIP. 19620901 198803 1 002
UNIVERSITAS SUMATERA UTARA
PERNYATAAN
ALGORITMA SEMUT UNTUK MENCARI JALUR TERPENDEK
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 27 Juni 2012
YAAYU 060803040
UNIVERSITAS SUMATERA UTARA
PENGHARGAAN
Dengan segala kerendahan hati penulis memanjatkan puji dan syukur kepada Tuhan Yang Maha Pemurah dan Maha Penyayang, dengan limpahan karunia-Nya kertas kajian ini mampu diselesaikan dalam yang telah ditetapkan. Ucapan terima kasih saya sampaikan kepada Drs. James P. Marbun, M.Kom. dan Dra. Elly Rosmaini, M.Si. selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan panduan dan penuh keprcayaan kepada saya untuk menyempurnakan kajian ini. Panduan ringkas dan padat serta profesional telah diberikan kepada saya agar penulis dapat menyelesaikan tugas ini. Ucapan terima kasih juga ditujukan kepada ketua dan sekretaris Departemen Prof. Dr. Tulus, M.Si. dan Dra. Mardiningsih M.Si., Bapak dan Ibu Dosen di Departemen Matematika FMIPA USU dan Staf Administrasi Departemen Matematika FMIPA USU. Penulis mengucapkan terima kasih terkhusus kepada kedua orangtua tercinta, Alm. Ayahanda Hadi Wasito dan Ibunda Latifa atas do’a, kasih sayang, keprcayaan serta dukungan moril maupun materil yang menjadi sumber inspirasi dan motivasi bagi penulis untuk tetap semangat dalam perkuliahan dan penulisan skripsi ini. Penulis juga mengucapkan terima kasih kepada adik-adik penulis Nur Laila, Wijannatun dan Nurjannah atas do’a dan dukungannya. Penulis juga mengucapkan terima kasih kepada sahabat-sahabat penulis (Ade Junita Parinduri, Laila Syafitri, Siti Sahara, Misna Wati, Novi Juanda Lubis, M. Haikal dan Rini Andria Ningsih) buat persahabatan, kebersamaan, dukungan, dan motivasinya bagi penulis selama perkuliahan dan penulisan skripsi ini. Pehulis juga mengucapkan terima kasih kepada Abang dan Kakak senior atas nasehat, motivasi dan bantuannya selama perkuliahan serta dalam penyusunan skripsi ini dan juga kepada adik-adik junior yang telah membantu dan memotivasi penulis dalam menyelesaikan penulisan skripsi ini. Semoga Allah SWT membalas segala kebaikan yang telah diberikan kepada penulis.
UNIVERSITAS SUMATERA UTARA
ABSTRAK
Secara umum, pencarian jalur terpendek dapat dibagi menjadi dua metode yaitu metode konvensional dan metode heuristik. Metode konvensional cenderung lebih mudah dipahami daripada metode heuristik, tetapi metode heuristik lebih variatif dan waktu perhitungan yang diperlukan lebih singkat. Pada metode heuristik terdapat beberapa algoritma, salah satunya algoritma semut. Algoritma semut adalah algoritma yang diadopsi dari perilaku koloni semut. Secara alamiah koloni semut mampu menemukan jalur terpendek dalam perjalanan dari sarang menuju sumber makanan berdasarkan jejak kaki pada jalur yang telah dilaluinya. Semakin banyak semut yang melewati suatu jalur, maka akan semakin jelas bekas jejak kakinya. Algoritma semut tepat digunakan untuk diterapkan dalam penyelesaian masalah optimasi, salah satunya adalah untuk menentukan jalur terpendek.
UNIVERSITAS SUMATERA UTARA
ANT ALGORITHM FOR FIND THE SHORTEST PATH
ABSTRACT
In general, the search for the shortest path can be divided into two methods, namely conventional methods and heuristic methods. Conventional methods tend to be more easily understood than the heuristic method, but more varied and heuristic methods the computation time required is shorter. In the heuristic method, there are several algorithms, one of which ant algorithms. Ant algorithm is an algorithm that was adopted from the behavior of ant colonies. Ant colonies naturally able to find the shortest path on the way from nest to food sources based on a path of footprints that have been passed. The more ants that pass through a lane, it will be more clearly exfootprint. Ant algorithm is used to apply the proper completion of the optimization problem, one of which is to determine the shortest path.
UNIVERSITAS SUMATERA UTARA
DAFTAR ISI Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv v vi vii viii x
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Pembatasan Masalah 1.4 Tinjauan Pustaka 1.5 Tujuan Penelitian 1.6 Kontribusi Penelitian 1.7 Metode Penelitian
1 1 3 3 4 7 7 7
Bab 2 Landasan Teori 2.1 Teori Dasar Graf 2.1.1 Graf Berbobot (Weighted Graph) 2.1.2 Representasi Graf 2.2 Optimisasi 2.2.1 Pengertian Optimisasi 2.2.2 Pengertian Nilai Optimasi 2.2.3 Macam-Macam Permasalahan Optimisasi 2.2.4 Penyelesaian Masalah Optimisasi 2.3 Jalur Terpendek (Shortest Path) 2.3.1 Penerapan Algoritma Semut 2.3.2 Contoh Kasus
8 8 11 11 14 14 14 14 15 16 16 16
Bab 3 Pembahasan 3.1 Algoritma Semut 3.2 Cara Kerja Semut Mencari Jalur Terpendek 3.3 Analisis Algoritma Semut Untuk Mencari Nilai Optimal Menggunakan Graf 3.4 Penyelesaian Masalah dengan Algoritma Semut
18 18 19
Bab 4 Kesimpulan dan Saran 4.1 Kesimpulan 4.2 Saran
39 39 39
Daftar Pustaka
40
21 24
UNIVERSITAS SUMATERA UTARA
DAFTAR TABEL
Halaman Tabel 3.1
Jarak Antarkota d ij
Tabel 3.2
Visibilitas Antarkota η =
Tabel 3.3 Tabel 3.4 Tabel 3.5
25
1 d ij Probabilitas Kota untuk Dikunjungi Siklus Ke-1 Kasus 1 Panjang Jalur Semut Siklus Ke-1 Kasus 1 Perubahan Harga Intensitas Jejak Kaki Semut τ ij
25 26 26
Antarkota Siklus Ke-2 Kasus 1 Probabilitas Kota untuk Dikunjungi Siklus Ke-2 Kasus 1 dengan τ ij Telah Diperbaharui
27
Tabel 3.7 Tabel 3.8
Panjang Jalur Semut Siklus Ke-2 Kasus 1 Perubahan Harga Intensitas Jejak Kaki Semut τ ij
27
Antarkota Siklus Ke-3 Kasus 1 Probabilitas Kota untuk Dikunjungi Siklus Ke-3 Kasus 1 dengan τ ij Telah Diperbaharui
28
Tabel 3.9
Panjang Jalur Semut Siklus Ke-3 Kasus 1 Probabilitas Kota untuk Dikunjungi Siklus Ke-1 Kasus 2 Panjang Jalur Semui Siklus Ke-1 Kasus 2 Perubahan Harga Intensitas Jejak Kaki Semut τ ij
28 29 29
Antarkota Siklus Ke-2 Kasus 2 Tabel 3.14 Probabilitas Kota untuk Dikunjungi Siklus Ke-2 Kasus 2 dengan τ ij Telah Diperbaharui
30
Tabel 3.15 Panjang Jalur Semut Siklus Ke-2 Kasus 2 Tabel 3.16 Perubahan Harga Intensitas Jejak Kaki Semut τ ij
30
Antarkota Siklus Ke-3 Kasus 2 Tabel 3.17 Probabilitas Kota untuk Dikunjungi Siklus Ke-3 Kasus 2 dengan τ ij Telah Diperbaharui
31
Tabel Tabel Tabel Tabel
Panjang Jalur Semut Siklus Ke-3 Kasus 2 Probabilitas Kota untuk Dikunjungi Siklus Ke-1 Kasus 3 Panjang Jalur Semui Siklus Ke-1 Kasus 3 Perubahan Harga Intensitas Jejak Kaki Semut τ ij
31 32 32
Antarkota Siklus Ke-2 Kasus 3 Tabel 3.22 Probabilitas Kota untuk Dikunjungi Siklus Ke-2 Kasus 3 dengan τ ij Telah Diperbaharui
33
Tabel 3.23 Panjang Jalur Semut Siklus Ke-2 Kasus 3 Tabel 3.24 Perubahan Harga Intensitas Jejak Kaki Semut τ ij
33
Antarkota Siklus Ke-3 Kasus 3 Tabel 3.25 Probabilitas Kota untuk Dikunjungi Siklus Ke-3 Kasus 3 dengan τ ij Telah Diperbaharui
34
Tabel 3.26 Panjang Jalur Semut Siklus Ke-3 Kasus 3
34
Tabel 3.6
Tabel Tabel Tabel Tabel
3.10 3.11 3.12 3.13
3.18 3.19 3.20 3.21
27
28
30
31
33
34
UNIVERSITAS SUMATERA UTARA
Tabel 3.27 Probabilitas Kota untuk Dikunjungi Siklus Ke-1 Kasus 4 Tabel 3.28 Panjang Jalur Semui Siklus Ke-1 Kasus 4 Tabel 3.29 Perubahan Harga Intensitas Jejak Kaki Semut τ ij
35 35
Antarkota Siklus Ke-2 Kasus 4 Tabel 3.30 Probabilitas Kota untuk Dikunjungi Siklus Ke-2 Kasus 4 dengan τ ij Telah Diperbaharui
36
Tabel 3.31 Panjang Jalur Semut Siklus Ke-2 Kasus 4 Tabel 3.32 Perubahan Harga Intensitas Jejak Kaki Semut τ ij
36
Antarkota Siklus Ke-3 Kasus 4 Tabel 3.33 Probabilitas Kota untuk Dikunjungi Siklus Ke-3 Kasus 4 dengan τ ij Telah Diperbaharui
37
Tabel 3.34 Panjang Jalur Semut Siklus Ke-3 Kasus 3
37
36
37
UNIVERSITAS SUMATERA UTARA
DAFTAR GAMBAR
Halaman Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 2.6 Gambar 2.7
Graf G(4,5) Graf Berarah Graf Tak-berarah Graf Terhubung Graf Tak-terhubung Graf Berbobot Dua Buah Graf dengan Matriks ketetanggaannya Masing-Masing Gambar 2.8 Graf dengan Matriks Bersisian Gambar 2.9 Graf dengan Daftar ketetanggaan Gambar 2.10 Graf Berarah dan Berbobot Gambar 3.1 Jalur Awal Semut Menuju Tempat Makanan Gambar 3.2 Jalur Optimal Semut Menuju Tempat Makanan Gambar 3.3 Jalur Awal Semut Menuju Tempat Makanan Gambar 3.4 Jalur Semut Menuju Sarang Gambar 3.5 Jalur Semut Menuju Makanan pada Iterasi Ke-1 Gambar 3.6 Jalur Semut Menuju Sarang pada Iterasi Ke-2 Gambar 3.7 Jalur Optimal Semut Untuk Menuju Tempat Makanan Gambar 3.8 Contoh Kasus
8 9 10 10 10 11 12 13 13 17 19 20 21 22 22 23 23 26
UNIVERSITAS SUMATERA UTARA
