implementasi algoritma aco (ant colony · pdf fileteori yang telah dipelajari selama kuliah...
TRANSCRIPT
i
IMPLEMENTASI ALGORITMA ACO (ANT COLONY
OPTIMIZATION) UNTUK OPTIMASI PENCARIAN
WEB CONTENT
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Oleh :
Jaka Santosa
NIM. 07560221
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK
UNIVERSITAS MUHAMMADIYAH MALANG 2014
i
ii
LEMBAR PERNYATAAN
Yang bertanda tangan dibawah ini :
NAMA : JAKA SANTOSA
NIM : 07560221
FAK./JUR. : TEKNIK/ INFORMATIKA
Dengan ini saya menyatakan bahwa Tugas Akhir dengan judul
“IMPLEMENTASI ALGORITMA ACO (ANT COLONY
OPTIMIZATION) UNTUK OPTIMASI PENCARIAN WEB CONTENT”
beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis
orang lain, baik sebagian maupun seluruhnya, kecuali dalam bentuk kutipan yang
telah disebutkan sumbernya. Demikian surat pernyataan ini saya buat dengan sebenar-benarnya.
Apabila kemudian ditemukan adanya pelanggaran terhadap etika keilmuan dalam
karya saya ini, atau ada klaim dari pihak lain terhadap keaslian karya sayaini
maka saya siap menanggung segala bentuk resiko/ sanksi yang berlaku.
Mengetahui,
Dosen Pembimbing
Eko Budi Cahyono, S.Kom, MT NIP. 10895040330
Malang, 18Juli 2014
Yang Membuat Pernyataan
Jaka Santosa
iii
vi
KATA PENGANTAR
Syukur Ahamdulillah dipanjatkan kehadirat Allah SWT, karena dengan
limpahan rahmat dan hidayah-Nya sehingga Tugas Akhir ini dapat diselesaikan.
Shalawat teriring salam kita sanjungkan kepangkuan Nabi besar Muhammad
SAW yang telah membawa umat manusia dari alam kebodohan menuju alam
yang berilmu pengetahuan.
Penulisan Tugas Akhir ini bertujuan untuk dapat mengaplikasikan teori-
teori yang telah dipelajari selama kuliah kedalam penelitian ini dan diharapkan
dapat berguna bagi penerapan di lapangan. Disamping itu, Tugas Akhir ini adalah
salah satu syarat dalam menyelesaikan studi pada Jurusan Informatika Program
Studi Strata-1 Teknik Informatika, FT, Universitas Muhammadiyah Malang.
Untuk memenuhi persyaratan tersebut dalam penyusunan hasil penelitian yang
dilaksanakan dalam bentuk laporan diberi judul yaitu “ImplementasiAlgoritma
ACO (Ant Colony Optimization) UntukPencarian Web Content”. Sebagai
Tugas Akhir untuk mendapatkan gelar Sarjana.
Dengan selesainya penulisan tugas akhir ini, diucapkan terima kasih yang
setulus-tulusnya kepada Bapak Eko Budi Cahyono, S.Kom., MT sebagai dosen
pembimbing 1 dan Bapak Agus Eko Minarno, S.Kom.sebagai dosen
pembimbing 2 yang telah banyak memberikan pengarahan dan bimbingannya
selama dalam penyelesaian penulisan Tugas Akhir ini.
Tidak lupa juga diucapkan terima kasih kepada semua pihak yang secara
langsung atau tidak langsung telah membantu dalam menyelesaikan penulisan
Tugas Akhir ini.
1. Allah S.W.T yang telah melimpahkan rahmat serta kelancaran dalam
pengerjaan tugas akhir ini.
2. Bapak YudaMunarko, ST., M.Sc. selaku Ketua Jurusan Teknik Informatika.
vii
3. Seluruh dosen dan staf pengajar Jurusan Teknik Informatika, Universitas
Muhammadiyah Malang.
4. Sahabat-sahabat saya yang telah memberikan dukungan dan semangat dalam
menyelesaikan laporan ini.
5. Seluruh teman-teman di Teknik Informatika khususnya angkatan 2007 yang
memberikan dukungan dalam menyelesaikan laporan ini.
Masih banyak kekurangan dalam penulisan Tugas Akhir ini, disebabkan
keterbatasan kemampuan. Oleh karena itu, kritik dan saran yang bersifat
membangun untuk kesempurnaan pada masa yang akan datang sangat diharapkan.
Akhirul kalam semoga Tugas Akhir ini dapat memberi manfaat bagi kita semua.
Amin Ya Rabbal’ Alamin…
Malang,
JakaSantosa
viii
DAFTAR ISI
HALAMAN PERSETUJUAN ........................................................................... i
HALAMAN PERNYATAAN ........................................................................... ii
HALAMAN PENGESAHAN ..........................................................................iii
ABSTRAKSI .................................................................................................... iv
ABSTRACT ...................................................................................................... v
KATA PENGANTAR ....................................................................................... vi
DAFTAR ISI ................................................................................................... viii
DAFTAR TABEL ............................................................................................. xi
DAFTAR GAMBAR ........................................................................................ xii
BAB IPENDAHULUAN ..................................................................................... 1
1.1. Latar Belakang....................................................................................... 1
1.2. Rumusan Masalah .................................................................................. 3
1.3. Tujuan Masalah ..................................................................................... 3
1.4. Batasan Masalah .................................................................................... 3
1.5. Metodologi ............................................................................................ 3
1.6. Sistematika Penulisan ............................................................................ 5
BAB IILANDASAN TEORI ............................................................................... 6
2.1. Metaheuristik ............................................................................................. 6
2.1.1. Karakteristik Metaheuristik ................................................................. 6
2.1.2. Klasifikasi Metaheuristik..................................................................... 7
2.2. Graph ........................................................................................................ 8
2.2.1. Graph Reguler ..................................................................................... 8
2.2.2. Multigraph .......................................................................................... 9
2.2.3. Walk ................................................................................................... 9
2.2.4. Trail dan Path ...................................................................................... 9
2.2.5. Cycle................................................................................................... 9
2.2.6. Jenis Graph Menurut Arah .................................................................. 9
2.2.6.1. Graph Berarah ............................................................................ 10
2.2.6.2. Graph Tidak Berarah .................................................................. 11
ix
2.3. Konsep Dasar Ant Colony ........................................................................ 11
2.3.1. Ant Colony Optimization .................................................................. 11
2.3.2. Karakteristik Ant Colony Sistem ....................................................... 12
2.3.3. Feromon Ant Colony Sistem ............................................................. 12
2.4. Website ................................................................................................... 13
2.4.1. Klasifikasi Website ........................................................................... 13
2.3.1.1. Website Statis ............................................................................. 13
2.4.1.2. Website Dinamis......................................................................... 14
2.4.2. Arsitektur Website ............................................................................ 14
2.4.3. Mesin Pencari Web ........................................................................... 16
2.4.4. Optimasi Pencarian Content Web ...................................................... 16
2.4.4.1. Algoritma ACO Pencarian Content Web ..................................... 17
BAB IIIANALISA DAN PERANCANGAN ..................................................... 19
3.1. Analisa Kebutuhan .................................................................................. 19
3.2. Arsitektur Sistem ..................................................................................... 20
3.3. Kebutuhan Non-Fungsional ..................................................................... 21
3.4. Kebutuhan Non Fungsional ..................................................................... 21
3.4.1. Use Case Diagram ............................................................................. 21
3.4.2. Activity Diagram.............................................................................. 22
3.4.2.1. Input Absolute Site ..................................................................... 22
3.4.2.2. View Internal Link ...................................................................... 23
3.4.3. Sequence Diagram ............................................................................ 24
3.4.3.1. Sequence Diagram View Internal Link........................................ 24
3.4.4. Class Diagram .................................................................................. 25
3.5. Flowchart ................................................................................................ 25
3.5.1. Flowchart Pencarian Web Content .................................................... 25
3.5.2. Flowchart Read Content Web ............................................................ 26
3.5.3. Flowchart Penentuan Best Location Menggunakan ACO................... 26
3.6. Perancangan Interface .............................................................................. 29
3.6.1. Rancangan Tampilan Splash Screen .................................................. 29
3.6.2. Rancangan Tampilan Menu Utama .................................................... 30
3.6.2.1. Rancangan Tampilan Manual Aplikasi ....................................... 31
x
3.6.2.2. Rancangan Tampilan About ....................................................... 32
3.6.3. Rancangan Tampilan Pencarian Content Web ................................... 32
BAB IVIMPLEMENTASI DAN PENGUJIAN ................................................. 34
4.1. Implementasi Sistem ................................................................................ 34
4.1.1. Lingkungan Implementasi ................................................................. 34
4.2. Implementasi Program ............................................................................. 34
4.2.1. Class netLocation .............................................................................. 35
4.2.1.1. Inisialiasi Variabel Phermone ..................................................... 35
4.2.2. Class AntColony ............................................................................... 36
4.2.2.1. Method AntColony ..................................................................... 36
4.2.2.2. Method AntStep .......................................................................... 36
4.2.2.3. Method NextStep ........................................................................ 37
4.2.3. Class ReadWebsite............................................................................ 37
4.2.3.1. Method GetInternalLink ............................................................ 38
4.2.3.2. Method GetExternalLink ........................................................... 39
4.2.4. Class AntNearDistance ..................................................................... 40
4.2.4.1. Method AntNearDistance ........................................................... 40
4.3. Pengujian Sistem ..................................................................................... 42
4.3.1. Pengujian Fungsionalitas .................................................................. 42
4.3.1.1. Pengujian Halaman Splash Screen .............................................. 42
4.3.1.2. Pengujian Halaman Metu Utama ................................................. 42
4.3.1.3. Pengujian Halaman About Aplikasi ............................................ 43
4.3.1.4. Pengujian Halaman Manual Aplikasi ...... 43Error! Bookmark not defined.
4.3.1.5. Pengujian Halaman Pencarian Content Website ............... 44Error! Bookmark not defined.
4.3.2. Pengujian Blackbox .......................................................................... 50
BAB VKESIMPULAN DAN SARAN............................................................... 52
5.1. Kesimpulan ............................................................................................. 52
5.2. Saran ....................................................................................................... 52
DAFTAR PUSTAKA ........................................................................................ 53
LAMPIRAN ...................................................................................................... 54
BIOGRAFI PENULIS ...................................................................................... 59
xi
DAFTAR TABEL
Tabel 3.1 Komponen Tampilan Splash Screen ................................................... 30
Tabel 3.2 Komponen Tampilan Menu Utama ..................................................... 31
Tabel 3.3 Komponen Tampilan Manual Aplikasi ............................................... 32
Tabel 3.4 Komponen Tampilan Menu About ..................................................... 32
Tabel 3.5 Komponen Tampilan Pencarian Web Content ..................................... 33
Tabel 4.1 Skenario Pengujian Menu Utama ........................................................ 50
Tabel 4.2 Skenario Pengujian Manual Application ............................................. 50
Tabel 4.3 Skenario Pengujian Aplikasi Search Content Web .............................. 51
xii
DAFTAR GAMBAR
Gambar 1.1. Ilustrasi Koloni Semut ..................................................................... 1
Gambar 1.2. Arsitektur Sistem Aplikasi ............................................................... 4
Gambar 2.1 Graph Reguler .................................................................................. 9
Gambar 2.2 Multigraph ........................................................................................ 9
Gambar 2.3 Graph Berarah ................................................................................ 10
Gambar 2.4 Proses Pemilihan Jalur Sesuai Kadar Pheromone ............................ 11
Gambar 2.5. Arsitektur Website ......................................................................... 14
Gambar 3.1. Rancangan Arsitektur Sistem ......................................................... 20
Gambar 3.2. Use Case Diagram ......................................................................... 21
Gambar 3.3 Activity Diagram Input Absolute Site ............................................. 22
Gambar 3.4 Activity Diagram View Internal Link .............................................. 23
Gambar 3.5 Sequence Diagram View Internal Link............................................ 24
Gambar 3.6 Class Diagram Aplikasi .................................................................. 25
Gambar 3.7Flowchart Pembentukan External Link ............................................ 26
Gambar 3.8Flowchart Extract Eksternal Link Menggunakan ACO .................... 27
Gambar 3.9 Tampilan Splash Screen Aplikasi .................................................... 30
Gambar 3.10 Tampilan Menu Utama ................................................................. 30
Gambar 3.11 Tampilan User Manual Aplikasi.................................................... 31
Gambar 3.12 Tampilan Menu About .................................................................. 32
Gambar 3.13 Tampilan Aplikasi Pencarian Web Content ................................... 33
Gambar 4.1. Pengujian Halaman Splash Screen ................................................. 42
Gambar 4.2. Pengujian Halaman Menu Utama ................................................... 43
Gambar 4.3. Pengujian Halaman About Application .......................................... 43
Gambar 4.4. Pengujian Halaman Manual Application ........................................ 44
Gambar 4.5. Pengujian Halaman Manual Application ........................................ 45
Gambar 4.6. Pengujian Hasil Extrak Link Website www.wearemania.net .......... 46
Gambar 4.7. Pengujian Halaman Website www.wearemania.net ........................ 47
Gambar 4.8. Pengujian Hasil Extrak Link Website www.merdeka.com .............. 48
Gambar 4.9. Pengujian Halaman Website www.merdeka.com ........................... 49
xiii
DAFTAR PUSTAKA
Eric Bonabeau, Marco Dorigo, and Guy Theraulaz. (1999). Swarm Intelligence From Natural to Artificial Systems. Santa Fe Institutestudies in the science of complexity. Oxford University Press.
Marco Dorigo And Thomas Stutzle. (2004). Ant Colony Optimization.
Massachusetts London, England : A Bradford Book The MIT Press Cambridge
Osfeld Avi. (2011). Ant Colony Optimization Methods And Applications. Rijeka,
Croatia: InTech. Sunyoto Andi. (2009). Ajax-Membangun Web dengan Teknologi Asynchrounous
Java Script & XML. Yogyakarta. Andi Offset. Talbi, El-Ghazali. (2009). Metaheuristics-From Design to Implementation.
Canada : A JohnWiley & Sons, Inc. Publishers. Wahyudi Bambang. (2004). Pengantar Struktur Data dan Algoritma. Yogyakarta.
Andi Offset. Blum Christian & Roli Andrea.(2003). Metaheuristics in Combinatorial
Optimization: Overview and Conceptual Comparison. http://www.inf.ucv. cl/~bcrawford/MII748/Metaheuristics_Overview_Blum.pdf. Didownload Tanggal 12 Juni2013.
Fielding Roy and Taylor Richard. (2002). Principled Design of the ModernWeb
Architecture. http://www.cs.helsinki.fi/group/java/s12-wepa/resurssit/principled-design-of-the-modern-web-architecture.pdf. Didownload Tanggal 12 September 2013.
Gilmour Stephen and Dras Mark.(2005).Understanding the Pheromone System
within Ant Colony Optimization. http://www.mhieu.info/download/HUST/Detai_DATN_HieuNM/gilmour2005b.pdf. Didownload Tanggal 12 September 2013.
Luis M.de Campos a, Juan M.Fernan, Jose A. Gamez c, Jose M.Puerta. (2002).
Ant colony Optimization LearningBayesian Networks. http://decsai.ugr.es/~lci/journal-papers-pdf/ijar02.pdf. Didownload Tanggal 12 Juni2013
53