1
ANALISIS PERFORMANCE ATAS METODE ARITHMETIC CROSSOVER DALAM ALGORITMA GENETIKA
TESIS
ERIANTO ONGKO 127038063
PROGRAM STUDI S2 TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul Tesis
: Analisis
Performance
Atas
Metode
Arithmetic
Crossover Dalam Algoritma Genetika Kategori
: Tesis
Nama Mahasiswa
: ERIANTO ONGKO
Nomor Induk Mahasiswa : 127038063 Program Studi
: Magister (S2) Teknik Informatika
Fakultas
: Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara
Komisi Pembimbing
:
Pembimbing 2,
Pembimbing 1,
Dr. Erna Budhiarti Nababan, M.IT
Prof. Dr. Opim Salim Sitompul, M.Sc
Diketahui/disetujui oleh Program Studi S2 Teknik Informatika Ketua,
Prof. Dr. Muhammad Zarlis, M.Sc NIP: 19570701 198601 1 003
Universitas Sumatera Utara
iii
PERNYATAAN
ANALISIS PERFORMANCE ATAS METODE ARITHMETIC CROSSOVER DALAM ALGORITMA GENETIKA TESIS Saya mengakui bahwa tesis ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan, Januari 2015
Erianto Ongko 127038063
Universitas Sumatera Utara
iv
PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS
Sebagai sivitas akademika Universitas Sumatera Utara, saya yang bertanda tangan di bawah ini Nama
: ERIANTO ONGKO
NIM
: 127038063
Program Studi
: Magister S2 Teknik Informatika
Jenis Karya Ilmiah
: Tesis
Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Sumatera Utara Hak Bebas Royalti Non-Eksklusif (Non-Exclusive Royalty Free Right) atas tesis saya yang berjudul: ANALISIS PERFORMANCE ATAS METODE ARITHMETIC CROSSOVER DALAM ALGORITMA GENETIKA Beserta perangkat yang ada (jika diperlukan). Dengan Hak Bebas Royalti NonEksklusif ini, Universitas Sumatera Utara berhak menyimpan, mengalih media, memformat, mengelola dalam bentuk database, merawat, dan mempublikasikan tesis saya tanpa meminta izin dari saya selama tetap mencantumkan nama saya sebagai penulis dan sebagai pemegang dan/atau sebagai pemilik hak cipta. Demikian pernyataan ini dibuat dengan sebenarnya. Medan, Januari 2015
Erianto Ongko 127038063
Universitas Sumatera Utara
v
Telah diuji pada Tanggal :
PANITIA PENGUJI TESIS Ketua
: Prof. Dr. Opim Salim Sitompul, M.Sc.
Anggota
: 1. Dr. Erna Budhiarti Nababan, M.IT 2. Prof. Dr. Herman Mawengkang 3. Prof. Dr. Muhammad Zarlis, M.Sc. 4. Dr. Marwan Ramli, M.Si
Universitas Sumatera Utara
vi
RIWAYAT HIDUP
DATA PRIBADI Nama Lengkap
: ERIANTO ONGKO
Tempat dan Tanggal Lahir
: Medan, 25 Desember 1990
Alamat
: Jalan Cahaya No. 48 Medan
Telepon/ HP
: -/085261589462
e-Mail
:
[email protected]
DATA PENDIDIKAN SD
: SD Gajah Mada Medan
TAMAT tahun 2002
SMP : SMP Dharma Putra Tangerang
TAMAT tahun 2005
SMA : SMA Methodist 2 Medan
TAMAT tahun 2008
S-1
: Teknik Informatika STMIK IBBI
TAMAT tahun 2012
S-2
: Teknik Informatika USU
TAMAT tahun 2015
Universitas Sumatera Utara
vii
KATA PENGANTAR Sungguh suatu kesempatan yang berharga bagi peneliti untuk menyampaikan puji dan syukur kepada Tuhan Yang Maha Esa sehingga peneliti bisa menyelesaikan penulisan Tesis ini. Tesis ini adalah salah satu persyaratan wajib untuk menyelesaikan perkuliahan dengan konsentrasi bidang Magister Teknik Informatika pada Fasilkom TI USU Medan. Sebagai bahan penelitian, peneliti sendiri mengambil judul “Analisis Performance atas Metode Arithmetic Crossover dalam Algoritma Genetika”. Peneliti melakukan penelitian dengan mengambil data benchmark berlin52.tsp yang bersumber dari TSPLIB. Peneliti berharap agar tesis ini bermanfaat bagi banyak pihak. Dalam menyelesaikan Tesis ini, peneliti telah mendapat banyak bantuan serta masukan dari berbagai pihak. Oleh karena itu, melalui kesempatan yang berbahagia, peneliti ingin berterima kasih kepada: 1. Bapak Prof Dr Syahril Pasaribu, DTMH, MSc (CTM), SpA(K) selaku Rektor Universitas Sumatera Utara atas kesempatan yang telah diberikan kepada peneliti sehingga bisa mengikuti dan menyelesaikan pendidikan program Magister (S2)Teknik Informatika. 2. Bapak Prof. Dr. Muhammad Zarlis, M.Sc selaku Dekan Fasilkom TI dan sekaligus Ketua Program Studi Magister (S2) Teknik Informatika. 3. Bapak M. Andri Budiman, S.T., M.CompSc, M.EM selaku Sekretaris Program Studi Magister (S2) Teknik Informatika. 4. Terima kasih yang terhingga serta penghargaan setinggi-tingginya kepada Bapak Prof. Dr. Opim Salim Sitompul, M.Sc selaku Pembimbing Utama, dan Ibu Dr. Erna Budhiarti Nababan, M.IT selaku Pembimbing Anggota yang telah membimbing dan menuntun peneliti dengan penuh kesabaran hingga selesainya tesis ini. 5. Terima kasih yang terhingga serta penghargaan setinggi-tingginya kepada Bapak Prof. Dr. Muhammad Zarlis, M.Sc, Bapak Prof. Dr. Herman Mawengkang dan Bapak Dr. Marwan Ramli, M.Si selaku pembanding yang telah memberikan masukan dan arahan yang baik demi selesainya tesis ini.
Universitas Sumatera Utara
viii
6. Teristimewa untuk Ibunda peneliti, Kesuma Dewi yang telah dengan penuh kasih sayang membesarkan dan mendidik peneliti serta memberikan dorongan moril maupun materil hingga selesainya perkuliahan peneliti. 7. Terima kasih juga peneliti sampaikan kepada Nenek, Abang, dan Adik peneliti atas doa yang tidak pernah padam untuk peneliti di dalam menjalani kegiatan perkuliahan hingga selesai. 8. Seluruh pegawai dan staf administrasi pada Program Studi Magister (S2) Teknik Informatika pada Fasilkom TI USU Medan yang telah memberikan bantuan dan pelayanan terbaik kepada peneliti selama mengikuti perkuliahan hingga selesai. 9. Kepada seluruh rekan peneliti, Mahasiswa/I KOM C angkatan tahun 2012, terima kasih atas suasana perkuliahan yang baik selama ini dan semoga kita dapat menjalin kerja sama yang baik di masa mendatang. 10. Semua pihak yang tidak dapat peneliti sebutkan namanya satu persatu, terima kasih atas bantuan yang telah diberikan kepada peneliti selama ini. Dengan segala kekurangan dan kerendahan hati, sekali lagi peneliti mengucapkan terima kasih. Semoga kiranya Tuhan Yang Maha Esa membalas segala bantuan dan kebaikan yang telah diberikan. Medan, Januari 2015 Peneliti
Erianto Ongko NIM: 127038063
Universitas Sumatera Utara
ix
ABSTRAK
Algoritma genetika sering digunakan pada masalah praktis yang berfokus pada pencarian parameter-parameter atau solusi yang optimal. Kelebihan algoritma genetika adalah kemampuannya untuk mendapatkan global optima dalam pencarian solusi sehingga sering digunakan dalam optimasi. Salah satu mekanisme yang turut berperan di dalam algoritma genetika adalah proses crossover sebagian dari kromosom induk pertama dengan sebagian kromosom induk kedua lalu menghasilkan kromosom baru. Metode crossover yang akan dianalisis dalam penelitian ini adalah arithmetic crossover dengan studi permasalahan yang digunakan adalah permasalahan Traveling Salesman Problem (TSP). Kromosom offspring (kromosom anak) diperoleh dengan melakukan operasi aritmatika terhadap parent (induk). Algoritma genetika akan berhenti jika sejumlah generasi maksimum tercapai atau level fitness yang ditentukan telah terpenuhi. Tujuan dari penelitian ini adalah mendapatkan hasil analisis performance dari metode arithmetic crossover dengan masalah utama adalah mendapatkan gambaran mengenai kaitan jumlah gen dalam suatu kromosom yang mengalami crossover dengan performance dari algoritma genetika. Kata Kunci: algoritma genetika, arithmetic crossover, fitness
Universitas Sumatera Utara
x
PERFORMANCE ANALYSIS OF THE METHOD ARITHMETIC CROSSOVER IN GENETIC ALGORITHM ABSTRACT
Genetic algorithms are often used in practical problems that focuses on search parameters or the optimal solution. Excess genetic algorithm is its ability to obtain global optima in the search for a solution that is often used in the optimization. One of the mechanisms that play a role in the genetic algorithm is the crossover portion of the first parent chromosome with most second parent chromosome and produce new chromosomes. Crossover method which will be analyzed in this study is the arithmetic crossover used to study the problems is the problem of Traveling Salesman Problem (TSP). Offspring chromosome (child) is obtained by performing arithmetic operations of the parent. Genetic algorithm will stop when the maximum number of generations is reached or a specified level of fitness has been fulfilled. The purpose of this study is to get the performance analysis of the arithmetic crossover method with the main problem is to get an idea of the link between the number of genes in a chromosome that is experiencing a crossover with the performance of the genetic algorithm. Keyword: arithmetic crossover, genetic algorithm, fitness
Universitas Sumatera Utara
xi
DAFTAR ISI
Hal. HALAMAN JUDUL
i
PERSETUJUAN
ii
PERNYATAAN ORISINALITAS
iii
PERSETUJUAN PUBLIKASI
iv
PANITIA PENGUJI
v
RIWAYAT HIDUP
vi
KATA PENGANTAR
vii
ABSTRAK
ix
ABSTRACT
x
DAFTAR ISI
xi
DAFTAR GAMBAR
xiii
DAFTAR TABEL
xiv
BAB I
BAB II
PENDAHULUAN
1
1.1
Latar Belakang
1
1.2
Perumusan Masalah
3
1.3
Batasan Masalah
4
1.4
Tujuan Penelitian
4
1.5
Manfaat Penelitian
4
TINJAUAN PUSTAKA
5
2.1
Algoritma Genetika
5
2.2
Struktur Umum Algoritma Genetika
7
2.3
Teknik Encoding
10
2.4
Operator Genetik
10
2.4.1 Proses Seleksi
11
2.4.2 Pindah Silang (Crossover)
12
2.4.3 Mutasi
16
2.5
Parameter Genetik
17
2.6
Traveling Salesman Problem (TSP)
18
2.7. Penelitian-Penelitian Terkait
19
Universitas Sumatera Utara
xii
2.7.1 Penelitian Terdahulu
19
2.7.2 Perbedaan Penelitian
20
2.7.3 Kontribusi yang Diberikan
21
BAB III METODOLOGI PENELITIAN
22
3.1
Pendahuluan
22
3.2
Data yang Digunakan
22
3.3
Algoritma Genetika terhadap Traveling Salesman Problem
23
3.3.1 Dasar Algoritma Genetika
23
3.3.2 Mendefinisikan Individu
29
3.3.3 Pembangkitan Populasi Awal
29
3.3.4 Seleksi
30
3.3.5 Crossover
31
3.3.6 Mutasi
35
BAB IV HASIL DAN PEMBAHASAN
37
4.1
Pendahuluan
37
4.2
Hasil Pengujian untuk 100 Generasi
37
4.2.1 Pengujian dengan Probabilitas Crossover (PC=0.25)
37
4.2.2 Pengujian dengan Probabilitas Crossover (PC=0.5)
42
Hasil Pengujian untuk 300 Generasi
47
4.3.1 Pengujian dengan Probabilitas Crossover (PC=0.25)
47
4.3.2 Pengujian dengan Probabilitas Crossover (PC=0.5)
51
Hasil Pengujian untuk 500 Generasi
56
4.4.1 Pengujian dengan Probabilitas Crossover (PC=0.25)
56
4.4.2 Pengujian dengan Probabilitas Crossover (PC=0.5)
60
Pembahasan
65
4.3
4.4
4.5
BAB V KESIMPULAN DAN SARAN
68
5.1
Kesimpulan
68
5.2
Saran
69
DAFTAR PUSTAKA
70
Universitas Sumatera Utara
xiii
DAFTAR GAMBAR
Halaman Gambar 2.1.
Siklus Algoritma Genetika
6
Gambar 2.2.
Gambar Diagram Alir Algoritma
7
Gambar 2.3.
Metode Roulette Wheel Selection
12
Gambar 2.4.
Metode Stochastic Universal Sampling
12
Gambar 3.1.
Metode Penelitian
23
Gambar 3.2.
Dasar Algoritma Genetika
24
Gambar 3.3.
Flowchart Whole Arithmetic Crossover
25
Gambar 3.4.
Flowchart Simple Arithmetic Crossover
27
Gambar 3.5.
Flowchart Single Arithmetic Crossover
28
Gambar 3.6.
Jarak Tiap Kota yang Akan Dikunjungi
29
Gambar 4.1.
Hasil Pengujian dengan PC Sebesar 0.25 untuk 100 Generasi
42
Gambar 4.2.
Hasil Pengujian dengan PC Sebesar 0.5 untuk 100 Generasi
46
Gambar 4.3.
Hasil Pengujian dengan PC Sebesar 0.25 untuk 300 Generasi
51
Gambar 4.4.
Hasil Pengujian dengan PC Sebesar 0.5 untuk 300 Generasi
55
Gambar 4.5.
Hasil Pengujian dengan PC Sebesar 0.25 untuk 500 Generasi
60
Gambar 4.6.
Hasil Pengujian dengan PC Sebesar 0.5 untuk 500 Generasi
64
Gambar 4.7.
Hasil Pengujian dengan Menggunakan Metode Whole Arithmetic Crossover dengan Menggunakan PC=0.5 untuk Pengujian dengan 500 Generasi
Gambar 4.8.
66
Hasil Pengujian dengan Menggunakan Metode Simple Arithmetic Crossover dengan Menggunakan PC=0.5 untuk Pengujian dengan 500 Generasi
Gambar 4.9.
66
Hasil Pengujian dengan Menggunakan Metode Single Arithmetic Crossover dengan Menggunakan PC=0.5 untuk Pengujian dengan 500 Generasi
67
Universitas Sumatera Utara
xiv
DAFTAR TABEL
Halaman Tabel 2.1.
Teknik Permutation Encoding
10
Tabel 2.2.
One Point Crossover
13
Tabel 2.3.
Two Point Crossover
13
Tabel 2.4.
Uniform Crossover
14
Tabel 2.5.
Single Arithmetic Crossover
15
Tabel 2.6.
Simple Arithmetic Crossover
15
Tabel 2.7.
Whole Arithmetic Crossover
16
Tabel 2.8.
Contoh Mutasi pada Pengkodean Biner
17
Tabel 2.9.
Contoh Mutasi pada Pengkodean Permutasi
17
Tabel 2.10.
Perbedaan Penelitian
20
Tabel 3.1.
Pembentukan Populasi Awal
30
Tabel 4.1.
Probabilitas Crossover (PC=0.25) untuk Whole Arithmetic Crossover untuk 100 Generasi
Tabel 4.2.
38
Probabilitas Crossover (PC=0.25) untuk Simple Arithmetic Crossover untuk 100 Generasi
Tabel 4.3.
39
Probabilitas Crossover (PC=0.25) untuk Single Arithmetic Crossover untuk 100 Generasi
40
Tabel 4.4.
Hasil Pengujian PC=0.25 untuk 100 Generasi
41
Tabel 4.5.
Probabilitas Crossover (PC=0.5) untuk Whole Arithmetic Crossover untuk 100 Generasi
Tabel 4.6.
43
Probabilitas Crossover (PC=0.5) untuk Simple Arithmetic Crossover untuk 100 Generasi
Tabel 4.7.
44
Probabilitas Crossover (PC=0.5) untuk Single Arithmetic Crossover untuk 100 Generasi
45
Tabel 4.8.
Hasil Pengujian PC=0.5 untuk 100 Generasi
46
Tabel 4.9.
Probabilitas Crossover (PC=0.25) untuk Whole Arithmetic Crossover untuk 300 Generasi
47
Universitas Sumatera Utara
xv
Tabel 4.10.
Probabilitas Crossover (PC=0.25) untuk Simple Arithmetic Crossover untuk 300 Generasi
Tabel 4.11.
48
Probabilitas Crossover (PC=0.25) untuk Single Arithmetic Crossover untuk 300 Generasi
49
Tabel 4.12.
Hasil Pengujian PC=0.25 untuk 300 Generasi
50
Tabel 4.13.
Probabilitas Crossover (PC=0.5) untuk Whole Arithmetic Crossover untuk 300 Generasi
Tabel 4.14.
52
Probabilitas Crossover (PC=0.5) untuk Simple Arithmetic Crossover untuk 300 Generasi
Tabel 4.15.
53
Probabilitas Crossover (PC=0.5) untuk Single Arithmetic Crossover untuk 300 Generasi
54
Tabel 4.16.
Hasil Pengujian PC=0.5 untuk 300 Generasi
55
Tabel 4.17.
Probabilitas Crossover (PC=0.25) untuk Whole Arithmetic Crossover untuk 500 Generasi
Tabel 4.18.
56
Probabilitas Crossover (PC=0.25) untuk Simple Arithmetic Crossover untuk 500 Generasi
Tabel 4.19.
57
Probabilitas Crossover (PC=0.25) untuk Single Arithmetic Crossover untuk 500 Generasi
58
Tabel 4.20.
Hasil Pengujian PC=0.25 untuk 300 Generasi
59
Tabel 4.21.
Probabilitas Crossover (PC=0.5) untuk Whole Arithmetic Crossover untuk 500 Generasi
Tabel 4.22.
61
Probabilitas Crossover (PC=0.5) untuk Simple Arithmetic Crossover untuk 500 Generasi
Tabel 4.23. Tabel 4.24.
62
Probabilitas Crossover (PC=0.5) untuk Single Arithmetic Crossover untuk 500 Generasi
63
Hasil Pengujian PC=0.5 untuk 500 Generasi
64
Universitas Sumatera Utara
