MENENTUKAN JALUR TERPENDEK MENGGUNAKAN ALGORITMA SEMUT
TUGAS AKHIR
Diajukan sebagai Salah Satu Syarat Untuk Memperoleh Gelar Sarjana Jurusan Teknik Informatika
Disusun Oleh : Nama
: I’ing Muttakhiroh
NIM
: 03 523 124
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNOLOGI INDUSTRI UNIVERSITAS ISLAM INDONESIA YOGYAKARTA 2007
LEMBAR PENGESAHAN PEMBIMBING
MENENTUKAN JALUR TERPENDEK MENGGUNAKAN ALGORITMA SEMUT
TUGAS AKHIR
Disusun Oleh : Nama
: I’ing Muttakhiroh
NIM
: 03 523 124
Yogyakarta, 2007 Pembimbing,
________________________ Taufiq Hidayat, ST, MCS.
ii
LEMBAR PERNYATAAN KEASLIAN HASIL TUGAS AKHIR
Saya yang bertandatangan di bawah ini,
Nama
: I’ing Muttakhiroh
NIM
: 03 523 124
Menyatakan bahwa seluruh komponen dan isi dalam Laporan Tugas Akhir ini adalah hasil karya saya sendiri. Apabila di kemudian hari terbukti bahwa ada beberapa bagian dari karya ini adalah bukan hasil karya saya sendiri, maka saya akan siap menanggung resiko dan konsekuensi apapun
Demikian pernyataan ini saya buat, semoga dapat dipergunakan sebagaimana mestinya.
Yogyakarta, 2007
____________________ I’ing Muttakhiroh
iii
LEMBAR PENGESAHAN PENGUJI
MENENTUKAN JALUR TERPENDEK MENGGUNAKAN ALGORITMA SEMUT TUGAS AKHIR Disusun Oleh : Nama
: I’ing Muttakhiroh
NIM
: 03 523 124
Telah Dipertahankan di Depan Sidang Penguji sebagai Salah Satu Syarat untuk Memperoleh Gelar Sarjana Jurusan Teknik Informatika Fakultas Teknologi Industri Universitas Islam Indonesia
Yogyakarta, 2007
Tim Penguji,
________________________
Ketua
________________________
Anggota I
Mengetahui, Ketua Jurusan Teknik Informatika Universitas Islam Indonesia
Yudi Prayudi, S.Si., M.Kom. iv
PERSEMBAHAN
Untuk jalan hidupku, ISLAM. Semoga karya kecil ini mampu memberi sumbangsih bagi kembalinya peradaban dan kejayaan islam Untuk ibu,ibu,ibu,bapak dan kakak-kakakku serta keponakan-keponakan yang telah menjadi guru pertama di hidupku. Yang telah menemaniku tumbuh dan berkembang, Tanpamu karya ini tak kan hadir. Cintaku padamu akan kupelihara sepanjang waktu. Untuk siapapun,dimanapun yang mempunyai mimpi untuk mengembalikan hidup sebagaimana wajarnya hidup. Sebuah revolusi telah menanti.
MOTTO
v
1. Barang siapa menolong agama Allah,niscaya Allah akan menolong dan meneguhkan kedudukannya [Muhammad:7] 2. Maka sesungguhnya bersama kesulitan ada kemudahan [Al insyiroh:5] 3. …kemudian akan kembali khilafah di atas manhaj nubuwwah..” [HR. imam Ahmad] 4. Berpikir yang terbaik, berupaya yang terbaik, dan berharap yang terbaik 5. If you do the best, GOD will take the rest 6. In time so difficult don’t ever say “GOD I have big problem” but instead “ hey problem, I have a big GOD” and everything will be alright 7. Proses bukanlah omong kosong. Ialah rangkaian kisah yang secara langsung berhadap-hadapan dengan tuhan. 8. “lebih baik di asingkan daripada menyerah pada kemunafikan” [Gie] 9. “idealisme adalah nyawa bagi jiwa yang bebas,bagi jiwa yang merdeka” [penulis] 10. Bahagia adalah saat menjadi manusia seutuhnya. Just give and give. [inspirited by JM]
vi
KATA PENGANTAR
Assalamu’alaikum Wr.Wb Alhamdulillah, segala puji bagi Allah SWT atas segala rahmat, hidayah dan inayah-Nya, sehingga penulisan laporan tugas akhir yang berjudul Menentukan Jalur Terpendek Menggunakan Algoritma Semut dapat penulis selesaikan dengan baik. Sholawat serta salam juga dipanjatkan kepada Nabi Muhammad SAW beserta para kerabat dan sahabat-sahabatnya. Laporan tugas akhir ini disusun sebagai salah satu syarat guna memperoleh gelar Sarjana Teknik Informatika pada Universitas Islam Indonesia. Dan juga sebagai sarana untuk mempraktekkan secara langsung ilmu dan teori yang telah diperoleh selama menjalani masa studi di Jurusan Teknik Informatika Fakultas Teknologi Industri Universitas Islam Indonesia. Penyusunan laporan tugas akhir ini tidak lepas dari bimbingan, dukungan dan bantuan baik materiil maupun spirituil dari berbagai pihak. Oleh karena itu dalam
kesempatan
ini
dengan
segala
kerendahan
hati,
penulis
ingin
menyampaikan ucapan terima kasih yang sebesar-besarnya kepada: a. Bapak, ibu dan kakak atas segala do’a, pengorbanan, kasih sayang, serta dorongan baik spirituil maupun materiil sehingga penulis bisa melakukan yang terbaik.
vii
b. Bapak Edy Suandi Hamid, selaku Rektor Universitas Islam Indonesia dan seluruh jajaran Rektorat Universitas Islam Indonesia. c. Bapak Fathul Wahid, ST., M.Sc, selaku Dekan Fakultas Teknologi Industri Universitas Islam Indonesia. Terima kasih atas masukan dan motivasi selama ini. d. Bapak Yudi Prayudi, S.Si., M.Kom, selaku Ketua Jurusan Teknik Informatika. Terima kasih atas kemudahan dan dukungan yang telah diberikan. e. Bapak Taufik Hidayat, ST, MCS selaku dosen pembimbing dan kepala laboratorium yang telah memberikan pengarahan, bimbingan, serta masukan selama pelaksanaan tugas akhir dan penelitian serta penulisan laporan. f. Dosen-dosen Jurusan Teknik Informatika serta Mas Misbah. Terima kasih atas semua ilmu pengetahuan dan motivasi serta bantuannya. g. Teman-teman PIT’ers (Fajra,Nyunyuk,BoBo,Endro,Ice tea) yang selalu memberi
motivasi,
kemampuan penulis.
menemani
dan
membantu
mengembangkan
Lanjutkan terus penelitiannya. Pompa terus
semangatnya. h. Teman-teman Lab Informatika Terpadu, Mas Romi dan Mas Andan, atas kebersamaannya. i. Kawan-kawan diskusi dan ‘hidup’ ku yang telah mengisi ruang kosong dalam hati dan jiwaku. Kaulah guru hidupku. Semangatmu selalu menyertai langkahku.
viii
j. Keluarga At-taghyiir yang terlanjur menjadi satu dalam hidupku k. Teman-teman informatika 2003, teman ‘berlima’, dan sahabat sahabatku yang belum tersebut di manapun mereka berada. Terima kasih atas do’a,dukungan dan sayangmu. l. Semua pihak yang telah memberikan bantuan dan dorongan atas terciptanya karya ini. Semoga Allah SWT melimpahkan rahmat dan hidayahnya kepada semua pihak yang telah membantu terselesaikannya penulisan laporan tugas akhir ini. Hanya Dialah sebaik-baik pembalas. Penulis menyadari bahwa dalam penyusunan laporan tugas akhir ini masih jauh dari sempurna, maka dengan segala keterbukaan penulis mengharapkan segala kritik dan saran yang membantu proses penyempurnaan di masa mendatang. Akhir kata semoga laporan ini dapat bermanfaat bagi penulis dan pembaca. Wassalamu’alaikum Wr.Wb.
Yogyakarta, 2007
I’ing Muttakhiroh
SARI
ix
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 jika dibandingkan dari hasil yang diperoleh, metode heuristik lebih variatif. Dalam metode heuristik terdapat beberapa algoritma,salah satunya adalah algoritma semut (AntCo). Algoritma semut adalah algoritma yang diadopsi dari perilaku koloni semut. Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Koloni semut dapat menemukan rute terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada lintasan yang telah dilewati. Semakin banyak semut yang melewati suatu lintasan, maka akan semakin jelas bekas jejak kakinya. Algoritma Semut sangat tepat digunakan untuk diterapkan dalam penyelesaian masalah optimasi, salah satunya adalah untuk menentukan jalur terpendek,dengan menganalogikan titik awal sebagai sarang semut dan titik tujuan sebagai sumber makanan semut. Algoritma semut cukup efektif dalam penentuan jalur terpendek, karena hasil perhitungan yang didapatkan cukup akurat. Namun demikian, semakin banyak data yang diolah tingkat akurasi nya akan semakin menurun. Selain jumlah kota, nilai parameter juga cukup mempengaruhi akurasi hasil perhitungan. Kata kunci: Pencarian jalur terpendek, Heuristik, Algoritma Semu, AntCo
DAFTAR ISI x
Lembar pengesahan………………………………………………………..ii Lembar pernyataan keaslian……………………………………………….iii Lembar pengesahan penguji……………………………………………….iv Persembahan……………………………………………………………….v Motto……….…………………………………………………...................vi Kata pengantar……...…………………………………………...................vii Sari…….………………………………………………………...................x Daftar isi….…………………………………..……………………………xi Daftar gambar………………..…………..……………………... ………...xiv Daftar tabel……………………………………………………...................xv BAB I PENDAHULUAN............................................................................1 1.1
Latar Belakang……….........................................................1
1.2
Rumusan Masalah………....................................................3
1.3
Batasan Masalah……….......................................................3
1.4
Tujuan Penelitian………......................................................4
1.5
Manfaat Penelitian………....................................................4
1.6
Metodologi Penelitian……………………………………...4 1.6.1 Metode Pengumpulan data…………………………5 1.6.2 Metode pengembangan sistem……………………..5
1.7
Sistematika penulisan……………………………...............5
BAB II LANDASAN TEORI......................................................................8 2.1
Teori graf………………………………………………….8 2.1.1 Defnisi graf………………………………………..8 2.1.2 Macam –macam graf...............................................8 2.1.3 Representasi graf……………………………........10 xi
2.2
Permasalahan optimasi……………………………...........13 2.2.1 Penyelsaian masalah optimasi…………................13 2.2.2 Permasalahan jalur terpendek…………………….13
2.3
Algoritma semut………………………………………….15
BAB III METODOLOGI...........................................................................28 3.1
Analisa kebutuhan perangkat lunak………………………28 3.1.1 Metode analisis…………………………………..28 3.1.2 Hasil analisis……………………………………..28 3.1.2.1 Analisis kebutuhan proses………………..29 3.1.2.2 Analisis kebutuhan masukan……………..29 3.1.2.3 Analisis kebutuhan keluaran……………..31 3.1.3 Kebutuhan antar muka…………………………...31 3.1.4 Analisis kebutuhan perangkat lunak……………..32 3.1.5 Analisis kebutuhan perangkat keras……………...32
3.2
Perancangan perangkat lunak…………………………….33 3.2.1 Metode perancangan……………………………..33 3.2.2 Hasil perancangan………………………………..34 3.2.2.1 Perancangan antar muka………………….40
3.3
Implementasi perangkat lunak…………………………...41 3.3.1 Batasan implementasi………………………........42 3.3.2 Implementasi antar muka………………………..42 3.3.2.1 Halaman utama…………………………..42 3.3.2.2 Halaman komputasi……………………...43
xii
3.3.3 Implementasi prosedural………………………...44 BAB IV HASIL DAN PEMBAHASAN………………………………..48 4.1
Pengujian program………………………………............48 4.1.1 Pengujian tidak normal……………….................48
4.2
Analisis kinerja sistem…………………………………..49 4.2.1 Analisis berdasarkan jumlah titik………………….49 4.2.2 Analisis berdasarkan nilai parameter………………52
BAB V KESIMPULAN DAN SARAN....................................................55 5.1
Kesimpulan……………………………………………....55
5.2
Saran…………………………………………………......55
DAFTAR GAMBAR
Gambar 2.1 Graf berarah dan berbobot…………………………...9 xiii
Gambar 2.2 Graf tidak berarah dan berbobot……………………..9 Gambar 2.3 Graf berarah dan tidak berbobot…………………….10 Gambar 2.4 Graf tidak berarah dan tidak berbobot………………10 Gambar 2.5 Senarai kedekatan graf ABCDEFG………………....13 Gambar 2.6 Graf ABCDEFG…………………………………….14 Gambar 2.7 Perjalanan semut menemukan sumber makanan……16 Gambar 3.1 Use Case Diagram ShortAntCo……………………..35 Gambar 3.2 Class Diagram Short AntCo………………………...36 Gambar 3.3 Sequence Diagram ShortAntCo 1…………………...37 Gambar 3.4 Sequence Diagram ShortAntCo 2..………………….38 Gambar 3.5 Activity Diagram……..……………………………..39 Gambar 3.6 Flow Chart Diagram………………………………...40 Gambar 3.7 Perancangan Halaman Utama Short AntCo………...41 Gambar 3.8 Implementasi Halaman utama Short AntCo.……….43 Gambar 3.9 Halaman Komputasi………………………………...44 Gambar 4.2 Peringatan jika field tidak diisi……………………...49 Gambar 4.2 Data kecil……………………………………………50 Gambar 4.3 Data Sedang…………………………………………50 Gambar 4.4 Data Besar…………………………………………...51 Gambar 4.5 Salah satu data graph pengujian……………………..53
DAFTAR TABEL
xiv
Tabel 2.1 Tabel matriks Kedekatan………………………………..11 Tabel 4.1 Tabel hasil pengujian……………………………………51
xv
DAFTAR PUSTAKA
[KUS03]
Kusumadewi, S. 2003. Artificial Intelligence (Teknik dan Aplikasinya), Yogyakarta: Graha Ilmu.
[KUS05]
Kusumadewi, S, & Hari, p. 2005. Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik, Yogyakarta: Graha Ilmu.
[EFE03]
Efendi, R. 2003. Penerapan algoritma semut untuk pemecahan masalah spanning tree pada kasus pemasangan jaringan kabel telepon. Skripsi, tidak diterbitkan. Yogyakarta : Fakultas Teknologi Industri Jurusan Teknik Informatika, Universitas Islam Indonesia.
[ZUH02]
Zuhri,Z. 2002. Optimasi rute dengan algoritma semut.,makalah system cerdas, volume 1, Nomor 1. Yogyakarta : Universitas Islam Indonesia.
[DOR96]
Dorigo,M. 1996. The Ant System: Optimization by a colony of cooperating agents. IEEE transactions on Systems, Man, and Cybernetics–Part B, Vol.26, No.1.
[DOR96]
Dorigo,M dan Gambardella,L.M. 1996.
Ant Colony System: A
Cooperative Learning Approach to theTraveling Salesman Problem.Belgium : Université Libre de Bruxelles.
