1
KAJIAN ALGORITMA GENETIKA PADA TRAVELLING SALESMAN PROBLEM SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
WIRA SEPTI ELISYAH TANJUNG 070823003
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
i2
PERSETUJUAN Judul Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: KAJIAN ALGORITMA GENETIKA PADA TRAVELLING SALESMAN PROBLEM : SKRIPSI : WIRA SEPTI ELISYAH TANJUNG : 070823003 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, Juli 2010
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Drs. Marwan Harahap, M.Eng NIP. 19461225 197403 1 001
Drs. Sawaludin, M.IT NIP.19591231 199802 1 001
Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua.
Dr. Saib Suwilo, M.Sc NIP. 19640109 198803 1 004
Universitas Sumatera Utara
ii3
PERNYATAAN
KAJIAN ALGORITMA GENETIKA PADA TRAVELLING SALESMAN PROBLEM
SKRIPSI Saya mengaku bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing – masing disebutkan sumbernya. Medan,
Juli 2010
Wira Septi Elisyah Tanjung 070823003
Universitas Sumatera Utara
iii4
PENGHARGAAN
Puji dan Syukur penulis panjatkan kehadirat Allah SWT yang Maha Pemurah dan Maha Penyayang, karena atas rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan skripsi ini dalam waktu yang ditetapkan. Ucapan terima kasih penulis sampaikan kepada Bapak Drs. Sawaluddin, M.IT dan Bapak Drs. Marwan Harahap, M.Eng, selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan bimbingan kepada saya untuk menyempurnakan skripsi ini. Terima kasih untuk Bapak Drs. Marihat Situmorang, M.Kom dan Bapak Drs. Suwarno Ariswoyo, M.Si yang telah memberikan kritik dan saran yang juga sangat membantu dalam penulisan skripsi ini. Ucapan terima kasih juga ditujukan kepada Ketua dan sekretaris Departemen Dr. Saib Suwilo, M.Sc dan Henry Rani Sitepu, M.Si, Dekan dan Pembantu Dekan serta Dosen dan Pegawai Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, dan teman seangkatan 2007 yang turut memberikan dukungan. Tidak lupa ucapan terima kasih yang sebesar-besarnya kepada Wirdansyah Tanjung (Papa), Dora Nst (Mama), Wira Febriansyah Tanjung ( Abang) selama ini telah memberikan dukungan baik materi dan juga do’a yang sangat bemanfaat bagi penulis. Spesial terima kasih buat Abrar Nazira yang juga telah memberikan support dan mendukung penulis dalam menyelesaikan skripsi ini. Juga kepada sohib-sohibku yang berada di Padepokan FMIPA tercinta yaitu Uci (adkku cynk),Verdi_Fauzi_Maulina (cece)_ayu (iyou kawai)_imel yang bocor abiz, Desni, Arlia, Dini, Debby, B’Ghaly, Rossy yang baik hati, Ade. M_Ihsan_Ega_Erika_hendrik(dogok)_k’valen mereka makhluk Tuhan yang super gokil, dan seluruh teman2 yang namanya tidak dapat disebutkan di Skripsi saya yang bagus ini saya ucapkan terima kasih, Semoga Allah SWT membalas segala budi baik yang sudah kalian berikan. Amin…….. Medan, 18 Juli 2010 Penulis, Wira Septi Elisyah Tanjung
Universitas Sumatera Utara
iv5
ABSTRAK Algoritma Genetika merupakan pencarian hasil terbaik yang berdasarkan atas perkawinan dan seleksi gen secara alami.Algoritma Genetika merupakan perkembangan dalam dunia computer di bidang kecerdasan buatan. Algoritma Genetika merupakan suatu algoritma yang terinspirasi dari teori 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 Travelling Salasman Problem (TSP), dimana seorang salesman harus mengunjungi n kota dengan aturan bahwa ia harus mengunjungi setiap kota sebanyak satu kali, meminimalisasi total jarak perjalannya dan pada akhirnya ia harus kembali kekota asalnya.Masalahnya dalah menentukan jalur yang terpendek dari beberapa kota yang telah ditentukan. Penyelesaiannya dilakukan secara bertahap dengan Algoritma Genetika dengan terlebih dahulu merepresentasikan kedalam bentuk pengkodean nomor urut kota, selanjutnya membangkitkan populasi awal diteruskan dengan proses seleksi, perkawinan silang dan mutasi sampai akhirnya diperoleh jalur terpendek yang diharapkan.
Universitas Sumatera Utara
v6
ABSTRACT Genetic Algorithm is the best search results based on marriage and selection of genes in natural. Algorithm Genetics is the development in the world of computers in the field of artificial intelligence. Genetic Algorithm is an algorithm inspired by Darwin's 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, hybridization and mutation. One problem that can be solved by Genetic Algorithm is a matter of Travelling Salesman Problem (TSP), where a salesman must visit n cities with the rule that she must visit each city, one-time, minimizing the total distance of his journey and eventually worked on; he had to return home. The problem is determine the shortest path from some cities that have been determined. To be settled gradually by Genetic Algorithm with the first representing the serial number into the form of coding, initial population subsequently forwarded to the selection process, hybridization and mutation until finally obtained the expected shortest path.
Universitas Sumatera Utara
vi7
DAFTAR ISI Halaman PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR GAMBAR
i ii iii iv v vi viii
Bab 1
PENDAHULUAN 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Kontribusi Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan
1 1 3 3 4 4 4 5
Bab 2
LANDASAN TEORI 2.1 Algoritma Genetika 2.1.1 Teknik Encoding 2.1.2 Proses Seleksi 2.1.3 Proses Rekombinasi 2.1.4 Proses Mutasi 2.1.5 Kawin Silang 2.2 Mekanisme Algoritma Genetika 2.3 Travelling Salesman Problem (TSP)
6 6 7 8 8 10 12 13 14
Bab 3
PEMBAHASAN 3.1 Algoritma Genetika 3.2 Rancangan Sistem 3.2.1 Perancangan Antarmuka (interface)
17 17 26 28
Universitas Sumatera Utara
8 vii Bab 4
IMPLEMENTASI DAN PENGUJIAN SISTEM 4.1 Implementasi 4.1.1 Tampilan Menu Utama 4.1.2 Tampilan TSP 4.1.3 Tampilan About 4.1.4 Tampilan Help 4.2 Pengujian Sistem
31 31 31 32 32 33 34
Bab 5
KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran
38 38 39
Daftar Pustaka
40
Lampiran A Listing Program
Universitas Sumatera Utara
9 viii
DAFTAR GAMBAR
Gambar 2.1 Gambar 3.1 Gambar 3.2 Gambar 3.3 Gambar 3.4 Gambar 3.5 Gambar 3.6 Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7 Gambar 4.8 Gambar 4.9 Gambar 4.10
Mekanisme Algoritma Genetika Graf Jarak Antar Kota Flowchart Rancangan Sistem Rancangan Menu Utama Rancangan Sistem TSP Rancangan Help Rancangan About Tampilan Menu Utama Tampilan TSP Tampilan About Tampilan Help Tampilan Pengujian Pemasukan Data 5 Kota Tampilan Pengujian Pemasukan Data 10 Kota Tampilan Pengujian Pemasukan Data 20 Kota Tampilan Pengujian Pemasukan Data 50 Kota Tampilan Pengujian Pemasukan Data 70 Kota Tampilan Pengujian Pemasukan Data 100 Kota
Halaman 13 17 27 28 29 30 30 31 32 33 33 34 35 35 36 36 37
Universitas Sumatera Utara
