PENERAPAN ALGORITMA GENETIKA UNTUK MENENTUKAN JALUR TERPENDEK (SHORTEST PATH)
SKRIPSI
RION SIBORO 060803025
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PENERAPAN ALGORITMA GENETIKA UNTUK MENENTUKAN JALUR TERPENDEK (SHORTEST PATH) SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains.
RION SIBORO 060803025
DEPARTEMEN MATEMATIKA FAKUTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: PENERAPAN ALGORITMA GENETIKA UNTUK MENENTUKAN JALUR TERPENDEK (SHORTEST PATH) : SKRIPSI : RION SIBORO : 060803025 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 23 September 2010
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Drs.Ujian Sinulingga, M.Si NIP. 19560303198403 1 004
Dra. Normalina Napitupulu, M.Sc NIP. 19631106198902 2 001
Diketahui/ Disetujui oleh Departemen Matematika FMIPA USU Ketua,
Dr. Saib Suwilo, M.Sc. NIP 196401091988031004
Universitas Sumatera Utara
iii
PERNYATAAN
PENERAPAN ALGORITMA GENETIKA UNTUK MENENTUKAN JALUR TERPENDEK (SHORTEST PATH)
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 23 September 2010
RION SIBORO 060803025
Universitas Sumatera Utara
iv
PENGHARGAAN
Puji dan syukur kehadirat Tuhan Yang Maha Esa atas kasih, rahmat, dan perlindungan-Nya yang memampukan penulis dalam mengerjakan dan menyelesaikan penulisana skripsi ini. Ucapan terima kasih penulis sampaikan kepada Dra. Normalina Napitupulu, M.Sc dan Drs.Ujian Sinulingga, M.Si selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan arahan, nasehat, motivasi, dan kepercayaan kepada penulis dalam mengerjakan skripsi ini. Ucapan terima kasih juga penulis sampaikan kepada Prof. Dr. Herman Mawengkang dan Drs. James P. Marbun, M.Kom selaku dosen pembanding yang banyak memberikan saran dan masukan dalam penyelesaian skripsi ini. Ucapan terima kasih juga penulis sampaikan kepada Dr. Saib Suwilo, M.Sc dan Drs. Henry Rani Sitepu, M.Si, selaku Ketua dan Sekretaris Departemen Matematika FMIPA USU, Bapak, Ibu Dosen dan Staf administrasi Departemen Matematika FMIPA USU. Terima kasih yang teristimewa buat orang tua penulis, ayahanda T. Siboro dan ibunda T. Simbolon yang merupakan kekuatan penulis dalam setiap langkah dan yang menjadi sumber inspirasi dan motivasi untuk tetap semangat dalam perkuliahan dan penulisan skripsi ini, serta buat dukungan moril dan materil yang diberikan kepada penulis. Terima kasih kepada adik-adik penulis yang selama ini menjadi motivasi penulis dalam menyelesaikkan skripsi ini beserta segenap keluarga yang telah banyak memberikan motivasi dan nasehat kepada penulis. Terima kasih juga penulis sampaikan kepada kakanda Meilinda Siahaan, Gindo Widarbakti Sitindaon, Priskilla br Ginting, Hotmauli Veronika Sinaga, Aghni, Sri Rafiqoh, Rina Widyasari, Wesley Tambunan, Endang Marlina Hutajulu serta teman-teman mahasiswa stambuk 2006 yang lainnya buat persahabatan, kebersamaan, dukungan, dan motivasinya bagi penulis selama perkuliahan dan dalam penyelesaian skripsi ini. Kepada adik-adik stambuk 2007, 2008, 2009 dan semua yang tidak dapat disebutkan satu per satu yang mau membantu penulis baik dalam waktu, tenaga dan pikiran dalam pengerjaan skripsi ini. Semoga Tuhan membalas segala kebaikan yang sudah diberikan, dan biarlah kasih dan kemurahan Tuhan yang senantiasa menyertai kita.
Universitas Sumatera Utara
v
ABSTRAK
Algoritma Genetika merupakan suatu algoritma yang terinspirasi dari teori evolusi Darwin dimana dinyatakan bahwa kelangsungan hidup suatu makhluk dipengaruhi aturan bahwa yang kuat adalah yang menang. Algoritma genetika didasarkan pada proses seleksi gen, perkawinan silang dan mutasi. Salah satu masalah yang dapat diselesaikan dengan algoritma genetika adalah persoalan shortest path. Shortest path merupakan suatu jaringan pengarahan perjalanan dimana seseorang pengarah jalan ingin menentukan jalur terpendek antara dua kota berdasarkan jalur alternatif yang tersedia dan titik tujuan hanya satu. Dalam penelitian ini permasalahan yang dibahas adalah mencari jalur terpendek dari 20 verteks dan 41 arc dengan menggunakan bantuan matlab. Eksekusi aplikasi komputer menunjukkan hasil yang optimal.
Universitas Sumatera Utara
vi
APPLICATION OF GENETIC ALGORITHM TO DETERMINE SHORTEST PATH
ABSTRACT
Genetic Algorithm is an algorithm inspired by Darwin's evolutionary theory which stated that influenced the survival of a creature that the strong rule is a win. Genetic algorithms are based on the process of gene selection, crossover and mutation. One problem that can be solved by genetic algorithm is the shortest path problem. Shortest path is a network where the person steering the direction of travel the road to determine the shortest path between two cities on the basis of available alternate routes, where only one destination point. In this research the issues discussed is to find the shortest path from 20 vertices and 41 arcs with the help of matlab. The execution of computer applications show that optimal results.
Universitas Sumatera Utara
vii
DAFTAR ISI
Halaman PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR BAB 1
BAB 2
ii iii iv v vi vii ix x
PENDAHULUAN 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Tinjauan Pustaka
1 1 3 3 3 4 4 5
LANDASAN TEORI 2.1 Graph 2.1.1 Keterhubungan 2.1.2 Representasi Graph 2.1.2.1 Representasi Graph Tidak Berarah dalam Matriks 2.1.2.2 Representasi Graph Berarah dalam Matriks 2.2 Algoritma Genetika 2.2.1 Komponen-Komponen Utama Algoritma Genetika 2.2.1.1 Skema Pengodean 2.2.1.2 Nilai Fitness 2.2.1.3 Seleksi Orang Tua 2.2.1.4 Proses Rekombinasi 2.2.1.5 Proses Mutasi 2.2.1.6 Elitisme 2.3 Penentuan Parameter 2.4 Keunggulan dari Aplikasi Algoritma Genetika dalam Proses Optimasi 2.5 Langkah-langkah Algoritma Sederhana untuk Pencarian Jalur Terpendek 2.6 Matlab 2.6.1 Fungsi M-File
8 8 9 10 10 11 12 14 14 16 17 18 19 19 19 21 21 22 24
Universitas Sumatera Utara
viii
BAB 3
ANALISIS DAN PERANCANGAN APLIKASI
27
3.1
27 27 28 28 28 29 31
Analisis 3.1.1. Analisis Masukan (Input) 3.1.2. Analisis Proses 3.1.3. Analisis Keluaran (Output) 3.1.4. Kebutuhan Perangkat Lunak dan Perangkat Keras 3.1.5. Analisis Algoritma Genetik Jalur Terpendek 3.2. Diagram Alir (Flowchart) BAB 4
HASIL DAN PEMBAHASAN 4.1. 4.2. 4.3. 4.4. 4.5. 4.6. 4.7.
BAB 5
Pengodean Kromosom Prosedur Inisisalisasi Populasi dan Evaluasi individu Probabilitas Fitness Proses Seleksi Perkawinan Silang (Crossover) Mutasi Penentuan Jalur Terbaik dengan uji program
KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran
33 34 38 39 39 40 40 43 43 44
DAFTAR PUSTAKA
45
LAMPIRAN PROGRAM
47
Universitas Sumatera Utara
ix
DAFTAR TABEL
Halaman Tabel 2.1 Matriks Kedekatan Graph Tidak Berarah dan Tidak Berbobot Tabel 2.2 Matriks Kedekatan Graph Berarah dan Tidak Berbobot Tabel 2.3 Pengodean Biner Tabel 2.4 Pengodean Permutasi Tabel 2.5 Pengodean Nilai Tabel 4.1 Populasi awal beserta nilai fitnessnya yang dibangkitkan secara acak Tabel 4.2 Probabilitas Fitness
11 12 14 15 15 35 38
Universitas Sumatera Utara
x
DAFTAR GAMBAR
Halaman Gambar 2.1 Graph Tidak Berarah dan Tidak Berbobot Gambar 2.2 Graph Berarah dan Tidak Berbobot Gambar 2.3 Pengodean Pohon Gambar 2.4 Flowchart Algoritma Genetik Gambar 3.1 Flowchart Algoritma Genetika untuk Jalur Terpendek Gambar 4.1 Graph Berbobot dan Berarah Gambar 4.2 Grafik fitness rata-rata Gambar 4.3 Tampilan sebelum parameter algoritma genetika diinput Gambar 4.4 Tampilan setelah parameter algoritma genetika diinput
10 11 16 22 32 33 41 41 42
Universitas Sumatera Utara
