ALGORITMA GENETIKA UNTUK MENYELESAIKAN PERMASALAHAN PENJADWALAN PERKULIAHAN DAN PRAKTIKUM SKRIPSI
RIDHA APRIANI 071402019
PROGRAM STUDI TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA 2012
Universitas Sumatera Utara
ALGORITMA GENETIKA UNTUK MENYELESAIKAN PERMASALAHAN PENJADWALAN PERKULIAHAN DAN PRAKTIKUM
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Teknologi Informasi
RIDHA APRIANI 071402019
PROGRAM STUDI TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA 2012
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
ALGORITMA GENETIKA : UNTUK MENYELESAIKAN PERMASALAHAN PENJADWALAN PERKULIAHAN DAN PRAKTIKUM SKRIPSI : RIDHA APRIANI : 071402019 : SARJANA (S1) TEKNOLOGI : INFORMASI TEKNOLOGI INFORMASI : ILMU KOMPUTER: DAN TEKNOLOGI INFORMASI Diluluskan di Medan, Juli 2012
Komisi Pembimbing
:
Pembimbing 2 Pembimbing 1
M Fadly Syahputra,B,Sc.M.Sc.IT NIP. 19830129 200912 1 003
Drs. Sawaluddin, M.I.T. NIP.19591231 199802 1 001
Diketahui/Disetujui oleh Program Studi S1 Teknologi Informasi Ketua,
Prof.Dr.Opim Salim Sitompul, M.Sc. NIP 196108171987011001
Universitas Sumatera Utara
iii
PERNYATAAN
ALGORITMA GENETIKA UNTUK MENYELESAIKAN PERMASALAHAN PENJADWALAN KULIAH DAN PRAKTIKUM SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Juli 2012
Ridha Apriani 071402019
Universitas Sumatera Utara
iv
PENGHARGAAN
Puji dan syukur penulis panjatkan kehadirat Allah SWT, serta shalawat dan salam kepada junjungan kita nabi Muhammad SAW, karena atas berkah, rahmat dan hidayahnya penulis dapat menyelesaikan penyusunan skripsi ini.
Dalam penulisan skripsi ini penulis banyak mendapatkan bantuan serta dorongan dari pihak lain. Dalam kesempatan ini dengan segala kerendahan hati, penulis mengucapkan terima kasih kepada: 1. Kedua orang tua penulis, yaitu Ayahanda Drs. Ardianta, M.Si dan Ibunda
Nurhasni Muluk atas segala limpahan kasih penulisng yang telah diberikan, memberikan motivasi untuk tetap semangat, membimbing dan terus mendukung penulis sehingga dapat menyelesaikan skripsi ini.
Kepada
saudari-saudari penulis, kakanda Juli Rizkia, SE dan adinda Fajriani yang selama ini memberikan motivasi kepada penulis dalam menyelesaikan skripsi ini beserta segenap keluarga yang telah banyak memberikan motivasi dan nasehat kepada penulis. 2. Ketua Program Studi Teknologi Informasi, Bapak Prof. Dr. Opim Sitompul,
M.Sc dan Sekretaris Program Studi Teknologi Informasi juga selaku dosen pembimbing pertama penulis, Bapak Drs. Sawaluddin, M.IT, Dekan dan Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 3. Bapak M.Fadly Syahputra,B.Sc.M.Sc.IT selaku dosen pembimbing kedua
penulis yang telah meluangkan waktu, tenaga, pikiran dan memberikan masukan kepada penulis dalam penyelesaian skripsi ini. 4. Ibu DR. Erna Budhiarti Nababan, M.IT dan Bapak Syahril Efendy,S.Si.,M.I.T
selaku selaku dosen pembanding yang telah banyak memberikan petunjuk, saran dan kritik dalam menyelesaikan skripsi ini.
Universitas Sumatera Utara
v
5. Bapak Dr. Poltak Sihombing, M.Kom, Bapak Romi Fadillah Rahmat,
B.Comp.Sc, M.Sc, seluruh dosen dan pegawai pada Program Studi Teknologi Informasi. 6. Teman-teman mahasiswa Teknologi Informasi stambuk 2007 yang telah memberikan semangat dan dukungan yang telah diberikan kepada penulis. 7. Da Harkamil Fitri yang selalu memberikan semangat dan dukungan kepada
penulis untuk menyelesaikan skripsi ini. 8. Bg Tommy, Mas teddy, mas ahmad, kk rury dan yang telah memberikan
informasi mengenai algoritma dalam skripsi ini dan kepada semua pihak yang yang tidak dapat penulis sebutkan satu persatu, terima kasih atas dukungan, ide, dan saran kepada penulis dalam penyelesaian skripsi ini.
Dalam penyusunan skripsi ini penulis menyadari bahwa masih banyak kekurangan, untuk itu penulis mengharapkan saran dan kritik yang bersifat membangun dari semua pihak demi kesempurnaan skripsi ini.
Akhir kata penulis mengharapkan semoga skripsi ini dapat bermanfaat dan membantu semua pihak yang memerlukannya.
Universitas Sumatera Utara
vi
ABSTRAK
Pada umumnya penjadwalan dilakukan dengan cara manual. Cara ini memiliki keakuratan yang kurang baik dan menyebabkan terjadinya tabrakan jadwal. Pada penjadwalan kuliah dan praktikum sering terjadi tabrakan jadwal mengajar dosen, tabrakan jadwal pada sisi mahasiswa, tabrakan waktu kuliah kuliah dengan waktu praktikum, dan ketersediaan ruangan yang cukup. Pada skripsi ini dijelaskan bagaimana penjadwalan perkuliahan dan praktikum dijadwalkan dengan menggunakan algoritma genetika. Algoritma genetika adalah algoritma pencarian heuristik yang didasarkan atas mekanisme dari seleksi alam yang lebih dikenal dengan proses evolusi biologis. Algoritma genetika digunakan untuk mendapatkan jadwal yang optimal yaitu dengan proses inisialisasi populasi, evaluasi fitness, seleksi, crossover dan mutasi. Data pada skripsi ini berupa data pengajar, data mata kuliah, data ruangan dan data waktu yang diambil dari database jurusan teknologi informasi Universitas Sumatera Utara. Data tersebut terlebih dahulu melalui tahapan proses dari algoritma genetika untuk mendapatkan hasil yang sesuai. Hasil dari penelitian ini yaitu menghasilkan jadwal yang optimal dengan menjadwalkan keseluruhan data matakuliah, dosen, ruangan, hari dan waktu. Kata kunci: penjadwalan, algoritma genetika, optimasi.
Universitas Sumatera Utara
vii
GENETIC ALGORITHM TO SOLVE THE PROBLEMS OF LECTURES AND PRACTICUMS SCHEDULLING
ABSTRACT
In generally scheduling is done manually. This method has poor accuracy and a schedule caused collisions. In the lecture and lab scheduling caused collision schedule and teaching faculty, collision on the students schedule, a collision course with the time in college lab, and the availability of sufficient class. In this research explain about how the scheduling of lectures and practicums are scheduled by using Genetic Algorithm. The Genetic algorithm is a heuristic search algorithm based on the mechanism of natural selection which known biology evolution process. Genetic algorithm is used to get an optimal schedule is the process of population initialization, fitness evaluation, selection, crossover and mutation. The data of this research are lecturers, subjects, class and time taken from the database of information technology at University of North Sumatra. The data in advance through the process of genetic algorithm to obtain the appropriate result. The results of this research is generates the optimal schedule with the overall schedule of data subjects, faculty, classroom, day and time. Keys: Schedulling, Genetic Algorithm, Optimaziation.
Universitas Sumatera Utara
viii
DAFTAR ISI
Persetujuan Pernyataan Penghargaan Abstrak Abstrack Daftar Isi Daftar Tabel Daftar Gambar Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan Bab 2 LANDASAN TEORI 2.1 Pengertian Penjadwalan 2.2 Pengertian Algoritma Genetika 2.3 Struktur Umum Algoritma genetika 2.4 Proses Algoritma Genetika 2.5 Komponen-Komponen algoritma Genetika 2.6 Teknik Pengkodean 2.6.1 Pengkodean Biner 2.6.2 Pengkodean Nilai 2.6.3 Pengkodean Pohon 2.6.4 Pengkodean Permutasi 2.7 Operator dalam Algoritma Genetika 2.7.1 Seleksi 2.7.1.1 Seleksi Roullete Wheel 2.7.1.2 Seleksi Ranking 2.7.1.3 Seleksi Tournament 2.7.1.4 Seleksi Steady State 2.7.2 Penyilangan (Crossover) 2.7.2.1 Penyilangan (Crossover) Satu Titik 2.7.2.2 Penyilangan (Crossover) Banyak Titik 2.7.2.3 Penyilangan (Crossover) Seragam 2.7.2.4 Penyilangan (Crossover) dengan permutasi 2.7.2.4.1 Partial-Mapped Crossover (PMX) 2.7.2.4.2 Order Crossover (OX) 2.7.2.4.3 Cycle Crossover (CX) 2.7.3 Mutasi 2.7.3.1 Mutasi Pengkodean Biner 2.7.3.2 Mutasi Pengkodean Nilai
Halaman ii iii iv vi vii viii xi xii 1 1 3 3 4 4 4 5 7 7 7 9 12 13 14 14 15 15 16 17 17 17 18 19 19 20 20 21 21 22 22 23 24 25 25 25
Universitas Sumatera Utara
ix
2.7.3.3 Mutasi Pengkodean Permutasi 2.7.3.4 Mutasi Pengkodean Pohon 2.8 Parameter Genetik
26 27 28
Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Masalah 3.2 Analisis Sistem 3.3 Proses Algoritma Genetika Pada Penjadwalan 3.3.1 Membangkitkan Populasi Awal 3.3.1.1 Representasi Kromosom 3.3.1.2 Inisialisasi Populasi 3.3.2 Evaluasi Fitness 3.3.3 Seleksi 3.3.4 Crossover 3.3.5 Mutasi 3.4 Perancangan Sistem 3.4.1 Rancangan Data 3.4.1.1 Struktur Tabel 3.4.1.2 Skema Relasi 3.4.2 Rancangan Arsitektural 3.4.2.1 Perancangan DFD (Data Flow Diagram) 3.4.2.2 DFd Level 0 3.4.2.3 DFD Level 1 3.4.2.4 Kamus Data 3.4.3 Rancangan Prosedural 3.4.3.1 Pemodelan Sistem 3.4.3.2 Proses Algoritma Genetika 3.4.4 Rancangan Antar Muka 3.4.4.1 Rancangan Menu Utama 3.4.4.2 Rancangan Menu Utama File 3.4.4.3 Rancangan Tampilan Form Matakuliah 3.4.4.4 Rancangan Tampilan Form Dosen 3.4.4.5 Rancangan Tampilan Form Ruangan 3.4.4.6 Rancangan Tampilan Form Asisten 3.4.4.7 Rancangan Tampilan Form Pengajar 3.4.4.8 Rancangan Tampilan Form Waktu 3.4.4.9 Rancangan Tampilan Form Kelas 3.4.4.10 Rancangan Tampilan Form Mengajar 3.4.4.11 Form Generate_Jadwal
30 30 31 31 31 32 33 36 37 38 39 40 40 40 43 44 44 45 46 54 55 55 57 59 59 60 61 62 63 64 65 66 67 68 69
Bab 4 IMPLEMENTASI DAN PENGUJIAN 4.1 Komponen Utama Penjadwalan 4.2 Implementasi Sistem 4.2.1 Spesifikasi Perangkat Keras dan Perangkat Lunak yang Digunakan 4.2.2 Tampilan Implementasi Program 4.3 Pengujian Sistem 4.3.1 Hasil Pengujian Parameter Genetika
70 70 80 81 81 95 95
Universitas Sumatera Utara
x
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
97 97 98
Daftar Pustaka Lampiran A: Listing Program
99 95
Universitas Sumatera Utara
xi
DAFTAR TABEL
Tabel 2.1 Contoh Pengkodean Biner Tabel 2.2 Contoh Pengkodean Nilai Tabel 2.3 Contoh Pengkodean Permutasi Tabel 2.4 Contoh Crossover Seragam Tabel 2.5 Contoh Mutasi Pengkodean Biner Tabel 2.6 Contoh Mutasi Pengkodean Nilai Tabel 2.7 Contoh Mutasi Pengkodean Permutasi Tabel 2.8 Contoh Mutasi Pengkodean Pohon Tabel 3.1 Representasi Kromosom Tabel 3.2 Persentase Fitness Tabel 3.3 Data Kelas Tabel 3.4 Data Dosen Tabel 3.5 Data Asisten Tabel 3.6 Data Ruang Tabel 3.7 Data Matakuliah Tabel 3.8 Data Waktu Tabel 3.9 Data Hari Tabel 3.10 Data Mengajar Tabel 3.11 Data Pengajar Tabel 3.12 Data Kromosom2 Tabel 3.13 Simbol-Simbol DFD Tabel 3.14 Spesifikasi Proses DFD Level 0 Tabel 3.15 Spesifikasi Proses DFD Level 1 Tabel 3.16 Spesifikasi Proses DFD Level 1 Proses 1 Tabel 3.17 Spesifikasi Proses DFD Level 1 Proses 2 Tabel 3.18 Spesifikasi Proses DFD Level 1 Proses 3 Tabel 3.19 Spesifikasi Proses DFD Level 1 Proses 4 Tabel 3.20 Kamus Data Proses Algoritma Genetika Tabel 4.1 Daftar Mengajar Tabel 4.2 Daftar Pengajar Tabel 4.3 Daftar Waktu Tabel 4.4 Daftar Hari Tabel 4.5 Ruang Kuliah dan Laboratorium Tabel 4.6 Daftar Kelas Tabel 4.7 Daftar Data Mata Kuliah dan Mata Kuliah Praktikum Tabel 4.8 Hasil pengujian parameter genetika
Halaman 15 15 16 22 25 26 26 28 32 37 41 41 41 41 41 42 42 42 42 43 44 45 47 48 50 52 53 54 70 72 73 73 73 74 75 96
Universitas Sumatera Utara
xii
DAFTAR GAMBAR
Gambar 2.1 Individu dalam Algoritma Genetika Gambar 2.2 Siklus Algoritma Genetika Gambar 2.3 Pengkodean Pohon Gambar 2.4 Seleksi Roda Roulette Gambar 2.5 Seleksi Rangking (situasi sebelum ranking) Gambar 2.6 Seleksi Rangking (situasi sesudah ranking) Gambar 2.7 Contoh Crossover Satu Titik Gambar 2.8 Contoh Crossover Banyak Titik Gambar 2.9 Contoh Partial-Mapped Crossover (PMX) Gambar 2.10 Contoh Order Crossover (OX) Gambar 2.11 Contoh Cycle Crossover (CX) Gambar 2.12 Contoh Inversion Mutation Gambar 2.13 Contoh Insertion Mutation Gambar 2.14 Contoh Exchange Mutation Gambar 3.1 Inisialisasi Populasi Gambar 3.2 Probabilitas Seleksi Roullete Wheel Gambar 3.3 Ilustrasi Crossover Satu Titik Gambar 3.4 Ilustrasi Mutasi Exchange Gambar 3.5 Relationship Database Penjadwalan Gambar 3.6 DFD Level 0 Gambar 3.7 DFD Level 1 Gambar 3.8 DFD Level 1 Proses 1 Gambar 3.9 DFD level 1 Proses 2 Gambar 3.10 DFD level 1 Proses 3 Gambar 3.11 DFD Level 1 Proses 4 Gambar 3.12 Flowchart Sistem Penjadwalan Secara Umum Gambar 3.13 Flowchart Algoritma Genetika Gambar 4.1 Tampilan HalamanLogin Gambar 4.2 Tampilan Menu Utama Gambar 4.3 Tampilan Form Matakuliah Gambar 4.4 Tampilan Form Dosen Gambar 4.5 Tampilan Form Ruangan Gambar 4.6 Tampilan Form Asisten Gambar 4.7 Tampilan Form Waktu Gambar 4.8 Tampilan Form Kelas Gambar 4.9 Tampilan Form Mengajar Gambar 4.10 Tampilan Form Pengajar Gambar 4.11 Tampilan Form Generate_Jadwal Gambar 4.12 Tampilan Form Jadwal_KuliahPrak Gambar 4.13 Tampilan Output Jadwal Kuliah dan Praktikum Gambar 4.14 Tampilan Form Grafik Gambar 4.15 Tampilan Form Info_Sistem
Halaman 12 14 16 18 18 19 20 21 23 23 24 26 27 27 35 38 39 39 43 45 46 48 49 51 53 56 57 82 82 83 84 85 86 87 88 89 90 91 92 93 94 95
Universitas Sumatera Utara
