penggabungan algoritma genetika dengan ... - …eprints.uns.ac.id/17055/1/awal.pdf ·...

14
perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN TABU SEARCH UNTUK PENGEMBANGAN METODE PENJADWALAN MATA KULIAH DI UNIVERSITAS SEBELAS MARET SURAKARTA SKRIPSI Diajukan untuk Memenuhi Salah Satu Syarat Mencapai Gelar Strata Satu Jurusan Informatika Disusun oleh : Ahmad Miftah Fajrin NIM. M0510003 JURUSAN INFORMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2015

Upload: duongdat

Post on 16-Aug-2019

226 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

i

PENGGABUNGAN ALGORITMA GENETIKA DENGAN TABU SEARCH

UNTUK PENGEMBANGAN METODE PENJADWALAN MATA KULIAH

DI UNIVERSITAS SEBELAS MARET SURAKARTA

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat Mencapai Gelar Strata Satu

Jurusan Informatika

Disusun oleh :

Ahmad Miftah Fajrin

NIM. M0510003

JURUSAN INFORMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SEBELAS MARET

SURAKARTA

2015

Page 2: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

ii

Page 3: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

iii

Page 4: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

iv

MOTTO

Lakukanlah kebaikan tanpa mengharapkan kembali

(Penulis)

Without action, you aren’t going anywhere.

(Mahatma Gandhi)

Page 5: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

v

PERSEMBAHAN

Karya ini Penulis persembahkan kepada:

“Ayah, Ibu, Adik, dan seluruh keluarga besar.”

“Teman-teman Informatika 2010 khususnya Ashar, Aji, Yusuf, Hedik, Cerren,

Adit, Taufik, Viko, April, Lydia, Dian”

Page 6: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

vi

KATA PENGANTAR

Segala puji dan syukur penulis ucapkan kepada Allah SWT, yang hanya karena

rahmat dan karunia-Nya, penulis dapat menyelesaikan Tugas Akhir dengan judul

“Penggabungan Algoritma Genetika dengan Tabu Search untuk Pengembangan

Metode Penjadwalan Mata Kuliah di Universitas Sebelas Maret Surakarta”. Penulis

menyadari akan keterbatasan yang dimiliki. Begitu banyak bantuan dan bimbingan

yang diberikan dalam penyusunan Tugas Akhir ini. Oleh karena itu, penulis

mengucapkan terima kasih kepada :

1. Bapak Drs. Bambang Harjito, M.App.Sc., Ph.D. selaku Ketua Jurusan

Informatika FMIPA UNS sekaligus sebagai anggota penguji yang telah

memberikan masukan, kritik dan saran yang membangun,

2. Bapak Antonius Bima Murti Wijaya S.T.,M.T. Selaku Dosen Pembimbing I

yang telah memberikan pengarahan selama proses penyusunan Tugas Akhir

ini,

3. Bapak Abdul Aziz, S.Kom, M.Cs. selaku Dosen Pembimbing II yang telah

memberikan masukan, kritik dan saran yang membangun,

4. Bapak Drs. YS. Palgunadi, M.Sc. sebagai anggota penguji yang telah

memberikan masukan, kritik dan saran yang membangun

5. Ayah, ibu, dan adik-adikku yang senantiasa memberikan dukungan dan

motivasi,

6. Teman-teman yang senantiasa selalu berbagi pengetahuan, pengalaman, dan

memberikan dukungan dan motivasi.

Semoga Tugas Akhir ini bermanfaat bagi semua pihak yang berkepentingan.

Surakarta, Januari 2015

Penulis

Page 7: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

vii

THE MERGER OF GENETIC ALGORITHM WITH TABU SEARCH

ALGORITHM FOR DEVELOPMENT OF COURSE TIMETABLING METHOD

AT SEBELAS MARET UNIVERSITY

Ahmad Miftah Fajrin

Jurusan Informatika. Fakultas Matematika dan Ilmu Pengetahuan Alam.

Universitas Sebelas Maret

ABSTRACT

University course timetabling is often to be critical concern for most

education institution. Sebelas Maret University (UNS) has developed a

computerized sxystem for a timetabling problem using simple additive weighting

algorithm. However, there are some study programs do not satisfied of the result

because there are many soft constraint are violated.

The purpose of this research is to develop the course timetabling algorithm

by combining the genetic algorithm and tabu search algorithm. Genetic Algorithm

has the power of a good exploitation to produce a visible solution meanwhile tabu

search can increase the power of searching in genetic algorithm and reduce the

possibility of trapped in local optimum

The combining of genetic algorithm with tabu search can decrease the

fitness by 47% for the smallest dataset and 21.3% for the biggest dataset compared

by simple additive weighting algorithm. The merge of genetic algorithm with tabu

search method can be used for the development of course timetabling method at

UNS.

Kata Kunci — Development of Course Timetabling Method, Genetic Algorithm,

Tabu search.

Page 8: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

viii

PENGGABUNGAN ALGORITMA GENETIKA DENGAN TABU SEARCH

UNTUK PENGEMBANGAN METODE PENJADWALAN MATA KULIAH DI

UNIVERSITAS SEBELAS MARET SURAKARTA

Ahmad Miftah Fajrin

Jurusan Informatika. Fakultas Matematika dan Ilmu Pengetahuan Alam.

Universitas Sebelas Maret

ABSTRAK

Penjadwalan mata kuliah sering menjadi bahan perhatian penting bagi setiap

organisasi atau institusi khususnya bagian pendidikan di universitas. Universitas

Sebelas Maret (UNS) telah membangun sistem komputerisasi untuk menyelesaikan

masalah penjadwalan mata kuliah menggunakan algoritma simpe additive

weighting. Akan tetapi, dibeberapa prodi masih ada yang kurang puas karena

banyak soft constraint yang dilanggar.

Tujuan dari penelitian ini adalah mengembangkan algoritma penjadwalan

mata kuliah dengan menggabungkan algoritma genetika dengan tabu search.

Algoritma genetika mempunyai kekuatan exploitation atau pencarian yang baik

sehingga menghasilkan solusi yang layak dan algoritma tabu search akan

meningkatkan kekuatan pencarian di algoritma genetika sehingga dapat

mengurangi kemungkinan terjebak di local optimum.

Penggabungan algoritma genetika dengan tabu search dapat menurunkan

nilai fitness sebesar 47% untuk dataset yang jumlahnya paling kecil dan 21.3%

untuk dataset yang jumlahnya paling besar dibandingkan dengan algoritma simple

additive weighting. Secara umum metode penggabungan algoritma genetika dengan

tabu search dapat digunakan untuk pengembangan metode penjadwalan mata

kuliah di UNS.

Kata Kunci — Pengembangan Metode Penjadwalan Mata Kuliah, Algoritma

genetika, Tabu search.

Page 9: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

ix

DAFTAR ISI

HALAMAN JUDUL ................................................................................................ i

HALAMAN PERSETUJUAN ............................... Error! Bookmark not defined.

HALAMAN PENGESAHAN ................................ Error! Bookmark not defined.

MOTTO ................................................................................................................. iv

PERSEMBAHAN ................................................................................................... v

KATA PENGANTAR ........................................................................................... vi

ABSTRACT .......................................................................................................... vii

ABSTRAK ........................................................................................................... viii

DAFTAR ISI .......................................................................................................... ix

DAFTAR TABEL ................................................................................................. xii

DAFTAR GAMBAR ........................................................................................... xiii

DAFTAR LAMPIRAN ........................................................................................ xiv

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. Sistematika Penulisan ............................................................................... 4

BAB II LANDASAN TEORI ................................................................................ 6

2.1. Landasan Teori ......................................................................................... 6

2.1.1. Penjadwalan Mata Kuliah ..................................................................... 6

2.1.2. Algoritma Simple Additive Weighting .................................................. 6

2.1.3. Algoritma Genetika............................................................................... 7

2.1.3.1. Chromosom Representation .............................................................. 9

2.1.3.2. Initial Population .............................................................................. 9

2.1.3.3. Evaluate Fitness .............................................................................. 11

2.1.3.4. Selection .......................................................................................... 12

2.1.3.5. Crossover ........................................................................................ 13

2.1.3.6. Mutation .......................................................................................... 13

Page 10: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

x

2.1.3.7. Elitism ............................................................................................. 14

2.1.4. Tabu Search ........................................................................................ 14

2.1.5. Hybrid Algoritma Genetika ................................................................ 16

2.2. Penelitian Terkait ................................................................................... 16

2.3. Rangkuman Hasil Penelitian Terdahulu ................................................. 18

BAB III METODOLOGI PENELITIAN ............................................................ 20

3.1. Penentuan Constraint ............................................................................. 20

3.1.1. Hard Constraint .................................................................................. 20

3.1.2. Soft Constraint .................................................................................... 22

3.2. Penentuan Nilai Pinalti ........................................................................... 22

3.3 Desain Constraint ................................................................................... 23

3.4 Desain Algoritma Genetika. ................................................................... 23

3.5 Desain Algoritma Genetika dengan Tabu Search. ................................. 24

3.6 Implementasi .......................................................................................... 25

3.7 Pengujian ................................................................................................ 25

3.7.1 Pengujian Constraint ........................................................................... 25

3.7.2 Pengujian Algoritma ........................................................................... 25

BAB IV HASIL DAN PEMBAHASAN ............................................................. 26

4.1. Tahap Pembahasan ................................................................................. 26

4.1.1. Desain Algoritma Genetika ................................................................ 26

4.1.1.1. Chromomosom Representation ....................................................... 26

4.1.1.2. Initial Population ............................................................................ 26

4.1.1.3. Evaluate Fitness .............................................................................. 29

4.1.1.4. Selection .......................................................................................... 29

4.1.1.5. Crossover ........................................................................................ 31

4.1.1.6. Mutation .......................................................................................... 32

4.1.1.7. Elitsm .............................................................................................. 32

4.1.2. Desain Penggabungan Algoritma Genetika dengan Tabu Search ...... 33

4.2. Tahap Hasil ............................................................................................. 36

4.2.1. Pengujian Constraint .......................................................................... 36

4.2.2. Visualisasi Algoritma ......................................................................... 37

4.2.3. Analisis Empiris .................................................................................. 38

Page 11: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

xi

4.2.3.1. Perbandingan Metode...................................................................... 38

4.2.3.2. Analisis Hasil Perbandingan ............................................................ 43

BAB V KESIMPULAN DAN SARAN ............................................................... 44

5.1. Kesimpulan ............................................................................................. 44

5.2. Saran ....................................................................................................... 44

BAB VI ................................................................................................................. 45

DAFTAR PUSTAKA ........................................................................................... 45

Page 12: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

xii

DAFTAR TABEL

Tabel 3.1 Hard Constraint ..................................................................................... 21

Tabel 3.2 Soft Constraint ...................................................................................... 22 Tabel 4.1 Mata Kuliah Penawaran S1 Informatika ............................................... 26

Tabel 4.2 Chromosom 1 ........................................................................................ 27

Tabel 4.3 Chromosom 2 ........................................................................................ 27

Tabel 4.4 Chromosom 3 ........................................................................................ 27

Tabel 4.5 Chromosom 4 ........................................................................................ 27

Tabel 4.6 Chromosom hasil seleksi ...................................................................... 30

Tabel 4.7 Susunan Parent 1 ................................................................................... 30

Tabel 4.8 Susunan Parent 2 ................................................................................... 30

Tabel 4.9 Susunan Offerspring ............................................................................. 32

Tabel 4.10 Susunan Offerspring Baru ................................................................... 32

Tabel 4.11 Solusi Awal Tabu Search .................................................................... 33

Tabel 4.12 Susunan Tabulist ................................................................................. 33

Tabel 4.13 Hasil Neighbourhood .......................................................................... 35

Tabel 4.14 Hasil Tabulist Baru ............................................................................. 35

Tabel 4.15 Hasil Akhir Gabungan Algoritma Genetika dengan Tabu Search ...... 36

Tabel 4.16 Perbandingan Nilai Fitness di Prodi S1 Informatika. ......................... 38

Tabel 4.17 Hasil Perbandingan Waktu Eksekusi dalam (s) di Jurusan S1

Informatika ............................................................................................................ 39

Tabel 4.18 Hasil Perbandingan Nilai Fitness di Prodi D3 Teknik Informatika. ... 40

Tabel 4.19 Hasil Perbandingan Waktu Eksekusi dalam (s) di Prodi D3 Teknik

Informatika ............................................................................................................ 41

Tabel 4.20 Hasil Perbandingan Nilai Fitness di Prodi S1 Hukum ........................ 41

Tabel 4.21 Perbandingan Waktu Eksekusi dalam (s) di Prodi S1 Hukum............ 42

Tabel 4.22 Perbandingan Fitness dan Waktu di Prodi S1 Informatika, D3

Informatika, S1 Hukum ......................................................................................... 43

Page 13: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

xiii

DAFTAR GAMBAR

Gambar 2.1 General Pseudo-code Algoritma Genetika .......................................... 8

Gambar 2.2 Pseudo-code Initial Population using Population Reduction Method 10

Gambar 2.3 Pseudo-code Evaluate Fitness ........................................................... 11

Gambar 2.4 Pseudo Code Tournament Selection ................................................ 12

Gambar 2.5 Pseudo-code Uniform Crossover ..................................................... 13

Gambar 2.6 Pseudo-code VDM ............................................................................ 14

Gambar 2.7 Pseudo-code Tabu Search ................................................................. 15

Gambar 2.8 General Pseudo-code of Hybrid Genetic Algorithms. ...................... 16 Gambar 3.1 Diagram Metodologi Penelitian. ....................................................... 20

Gambar 3.2 Pseudo-code Modified Algoritma Genetika ...................................... 24

Gambar 3.3 Pseudo-code Gabungan Algoritma Genetika dengan Tabu Search .. 24 Gambar 4.1 Hasil Bilangan Random Offerspring ................................................. 31

Gambar 4.2 Proses Memasukkan Gen dari Parent 1 ke Offerspring .................... 31

Gambar 4.3 Proses Memasukkan Gen dari Parent 2 ke Offerspring .................... 31

Gambar 4.4 Proses 𝑁1 .......................................................................................... 34

Gambar 4.5 Hasil acak Makul Penawaran Pertama .............................................. 34

Gambar 4.6 Hasil acak Makul Penawaran Kedua ................................................. 34

Gambar 4.7 Hasil tukar ruang dan waktu 𝑁2 ....................................................... 34

Gambar 4.8 Grafik perbandingan fitness setiap generasi di Algoritma Genetika,

Gabungan Algoritma Genetika dengan Tabu Search, dan Algoritma Simple additive

weighting ............................................................................................................... 37

Page 14: PENGGABUNGAN ALGORITMA GENETIKA DENGAN ... - …eprints.uns.ac.id/17055/1/AWAL.pdf · perpustakaan.uns.ac.id digilib.uns.ac.id commit to user i PENGGABUNGAN ALGORITMA GENETIKA DENGAN

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

xiv

DAFTAR LAMPIRAN

Lampiran A ........................................................................................................... 48

Lampiran B............................................................................................................ 58

Lampiran C............................................................................................................ 64