PENERAPAN ALGORITMA GENETIKA UNTUK PENJADWALAN UJIAN TUGAS AKHIR PADA JURUSAN TEKNIK INFORMATIKA UNIVERSITAS MUHAMMADIYAH MALANG
TUGAS AKHIR Sebagai Persyaratan Guna Meraih Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh: Yeny Nur Aeni 08560383
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2013 i
LEMBAR PERSETUJUAN PENERAPAN ALGORITMA GENETIKA UNTUK PENJADWALAN UJIAN TUGAS AKHIR PADA JURUSAN TEKNIK INFORMATIKA UNIVERSITAS MUHAMMADIYAH MALANG
TUGAS AKHIR
Oleh : Yeny Nur Aeni 08560383
Telah Direkomendasikan Untuk Diajukan Sebagai Judul Tugas Akhir Di Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui, Pembimbing I
Pembimbing II
Yuda Munarko, S.Kom, M.Sc
Nur Hayatin, S.ST
NIP : 108.0611.0443
NIP : 108.0907.0476
ii
LEMBAR PENGESAHAN PENERAPAN ALGORITMA GENETIKA UNTUK PENJADWALAN UJIAN TUGAS AKHIR PADA JURUSAN TEKNIK INFORMATIKA UNIVERSITAS MUHAMMADIYAH MALANG
TUGAS AKHIR
Diajukan Untuk Memenuhi Persyaratan Guna Meraih Gelar Sarjana Strata Satu Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh : Yeny Nur Aeni 08560383
Tugas Akhir ini telah diuji dan dinyatakan lulus oleh tim penguji pada tanggal 31 Januari 2013 Mengetahui/Menyetujui Penguji I
Penguji II
Gita Indah Marthasari, ST NIP : 108.0611.0442
Lailatul Husniah, S.ST NIDN : 0730108401
Mengetahui Ketua Jurusan Teknik Informatika
Eko Budi Cahyono, S.Kom, MT NIP : 108.9504.0330
iii
LEMBAR PERNYATAAN Yang bertanda tangan di bawah ini:
Nama Tempat / Tgl Lahir NIM Fakulats / Jurusan
: Yeny Nur Aeni : Pacitan, 12 Oktober 1989 :08560383 : Teknik / Teknik Informatika
Dengan ini saya menyatakan bahwa Tugas Akhir dengan judul “PENERAPAN ALGORITMA GENETIKA UNTUK PENJADWALAN UJIAN TUGAS AKHIR PADA JURUSAN TEKNIK INFORMATIKA UNIVERSITAS MUHAMMADIYAH MALANG ” beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis orang lain, baik sebagian maupun keseluruhan, kecuali dalam bentuk kutipan yang telah disebutkan sumbernya. Demikian surat pernyataan ini saya buat dengan sebenar-benarnya. Apabila kemudian ditemukan adanya pelanggaran terhadap etika keilmuan dalam karya saya ini, atau ada klaim dari pihak lain terhadap keaslian karya saya ini maka saya siap menanggung segala bentuk resiko/sanksi yang berlaku.
Malang, Februari 2013 Yang Membuat Pernyataan
Yeny Nur Aeni Mengetahui, Dosen Pembimbing I
Dosen Pembimbing II
Yuda Munarko, S.Kom, M.Sc NIP : 108.0611.0443
Nur Hayatin, S.ST NIP : 108.0907.0476
4
DAFTAR ISI Lembar Persetujuan ................................................................................................. ii Lembar Pengesahan ............................................................................................... iii Lembar Pernyataan.................................................................................................. 4 Abstraksi ................................................................ Error! Bookmark not defined. Abstract .................................................................. Error! Bookmark not defined. Kata Pengantar ....................................................... Error! Bookmark not defined. Lembar Persembahan ............................................. Error! Bookmark not defined. Daftar Isi.................................................................................................................. 5 Daftar Gambar ......................................................................................................... 7 Daftar Tabel .......................................................................................................... 10 BAB I PENDAHULUAN ...................................... Error! Bookmark not defined. 1.1 1.2 1.3 1.4 1.5
LATAR BELAKANG ..............................ERROR! BOOKMARK NOT DEFINED. RUMUSAN MASALAH ..........................ERROR! BOOKMARK NOT DEFINED. TUJUAN ..............................................ERROR! BOOKMARK NOT DEFINED. BATASAN MASALAH ...........................ERROR! BOOKMARK NOT DEFINED. METODOLOGI PENYELESAIAN MASALAH ............ERROR! BOOKMARK NOT DEFINED. 1.6 SISTEMATIKA PENULISAN ...................ERROR! BOOKMARK NOT DEFINED. BAB II LANDASAN TEORI ................................ Error! Bookmark not defined. 2.1 PENJADWALAN ...................................ERROR! BOOKMARK NOT DEFINED. 2.2 KECERDASAN BUATAN.......................ERROR! BOOKMARK NOT DEFINED. 2.3 ALGORITMA GENETIKA ......................ERROR! BOOKMARK NOT DEFINED. 2.3.1 Sejarah Algoritma Genetika................. Error! Bookmark not defined. 2.3.2 Aplikasi Algoritma Genetika ............... Error! Bookmark not defined. 2.3.3 Struktur Umum Algoritma Genetika ... Error! Bookmark not defined. 2.3.4 Komponen-komponen Utama Algoritma Genetika .. Error! Bookmark not defined. 2.3.4.1 Teknik Penyandian (Pengkodean) Error! Bookmark not defined. 2.3.4.2 Prosedur Inisialisasi (membangkitkan populasi awal) ......... Error! Bookmark not defined. 2.3.4.3 Fungsi Evaluasi ............................ Error! Bookmark not defined. 2.3.4.4 Seleksi .......................................... Error! Bookmark not defined. 2.3.4.5 Crossover ...................................... Error! Bookmark not defined. 2.3.4.6 Mutasi ........................................... Error! Bookmark not defined. 2.3.4.7 Parameter Genetika ...................... Error! Bookmark not defined. 5
BAB III PERANCANGAN SISTEM .................... Error! Bookmark not defined. 3.1 ANALISA MASALAH ...........................ERROR! BOOKMARK NOT DEFINED. 3.2 ANALISA DATA ..................................ERROR! BOOKMARK NOT DEFINED. 3.3 PERANCANGAN ALUR PROSES ............ERROR! BOOKMARK NOT DEFINED. 3.3.1 Desain Flowchart ................................. Error! Bookmark not defined. 3.3.2 Desain Flowchart Algoritma Genetika Error! Bookmark not defined. 3.3.3 Use Case .............................................. Error! Bookmark not defined. 3.3.4 Activity Diagram ................................. Error! Bookmark not defined. 3.3.5 Sequence Diagram ............................... Error! Bookmark not defined. 3.3.6 Class Diagram ...................................... Error! Bookmark not defined. 3.4 DESAIN DATABASE.............................ERROR! BOOKMARK NOT DEFINED. 3.5 DESAIN INTERFACE ............................ERROR! BOOKMARK NOT DEFINED. BAB IV IMPLEMENTASI DAN HASIL PENGUJIAN .... Error! Bookmark not defined. 4.1 SPESIFIKASI KEBUTUHAN HARDWARE DAN SOFTWARE ................. ERROR! BOOKMARK NOT DEFINED. 4.2 IMPLEMENTASI SISTEM .......................ERROR! BOOKMARK NOT DEFINED. 4.2.1. Pembuatan Basis Data ...................... Error! Bookmark not defined. 4.2.2. Pembuatan Fungsi Koneksi Database ............ Error! Bookmark not defined. 4.2.3. Pembuatan Class-Class yang Dibutuhkan ...... Error! Bookmark not defined. 4.3 PENGUJIAN .........................................ERROR! BOOKMARK NOT DEFINED. 4.3.1 Pengujian Fungsional ........................... Error! Bookmark not defined. 4.3.1.1 Form Utama .................................. Error! Bookmark not defined. 4.3.1.2 Form Data Dosen .......................... Error! Bookmark not defined. 4.3.1.3 Form Data Mahasiswa .................. Error! Bookmark not defined. 4.3.1.4 Form Data Slot Waktu .................. Error! Bookmark not defined. 4.3.1.5 Form Data Mengajar Dosen ......... Error! Bookmark not defined. 4.3.2 Pengujian Algoritma ............................ Error! Bookmark not defined. 4.3.1.1 Pembentukan Populasi Awal ........ Error! Bookmark not defined. 4.3.1.2 Perhitungan Nilai Fitness ............. Error! Bookmark not defined. 4.3.1.3 Seleksi Orang Tua ........................ Error! Bookmark not defined. 4.3.1.4 Crossover ...................................... Error! Bookmark not defined. 4.3.1.5 Mutasi ........................................... Error! Bookmark not defined. 4.3.1.6 Cetak Laporan .............................. Error! Bookmark not defined. 4.3.3 Pengujian Hasil .................................... Error! Bookmark not defined. 4.3.3.1 Pengujian Generasi ....................... Error! Bookmark not defined. 4.3.3.2 Pengujian Fitness .......................... Error! Bookmark not defined. 4.3.3.3 Pengujian Unit .............................. Error! Bookmark not defined. 4.3.3.4 Pengujian Integrasi ....................... Error! Bookmark not defined. 6
BAB V KESIMPULAN DAN SARAN ................. Error! Bookmark not defined. 5.1 5.2
KESIMPULAN ......................................ERROR! BOOKMARK NOT DEFINED. SARAN ................................................ERROR! BOOKMARK NOT DEFINED.
DAFTAR PUSTAKA ............................................................................................. 9
DAFTAR GAMBAR Gambar 2. 1 Siklus Algoritma Genetika oleh David Goldberg .. Error! Bookmark not defined. Gambar 2. 2 Contoh pengkodean biner.................. Error! Bookmark not defined. Gambar 2. 3 Contoh Pengkodean Pohon ............... Error! Bookmark not defined. Gambar 3. 1 Flowchart Penjadwalan ..................... Error! Bookmark not defined. Gambar 3. 2 Flowchart Algoritma Genetika .......... Error! Bookmark not defined. Gambar 3. 3 Representasi Kromosom ................... Error! Bookmark not defined. Gambar 3. 4 Use Case Diagram Penjadwalan ....... Error! Bookmark not defined. Gambar 3. 5 Activity Diagram Mengelola Data ... Error! Bookmark not defined. Gambar 3. 6 Activity Diagram Proses Penjadwalan ............ Error! Bookmark not defined. Gambar 3. 7 Activity Diagram Generate Laporan . Error! Bookmark not defined. Gambar 3. 8 Sequence Diagram Penjadwalan Secara Umum .... Error! Bookmark not defined. Gambar 3. 9 Sequence Diagram Mengelola Data .. Error! Bookmark not defined. Gambar 3. 10 Sequence Diagram Proses Penjadwalan ........ Error! Bookmark not defined. Gambar 3. 11 Sequence Diagram Cetak Laporan .. Error! Bookmark not defined. Gambar 3. 12 Class Diagram Jadwal Ujian ........... Error! Bookmark not defined. Gambar 3. 13 Entity Relationship Diagram .......... Error! Bookmark not defined. Gambar 3. 14 Form Utama Jadwal Ujian............... Error! Bookmark not defined. Gambar 4. 1 Data Tabel MySQL ........................... Error! Bookmark not defined. Gambar 4. 2Script Koneksi Basis Data .................. Error! Bookmark not defined. Gambar 4. 3 Class-Class yang Dibutuhkan ........... Error! Bookmark not defined. Gambar 4. 4 Form Utama....................................... Error! Bookmark not defined. Gambar 4. 5 Form Data Dosen .............................. Error! Bookmark not defined. Gambar 4. 6 Form Data Mahasiswa dan Dosen Pembimbing .... Error! Bookmark not defined. Gambar 4. 7 Form Data Slot .................................. Error! Bookmark not defined. Gambar 4. 8 Form Data Mengajar Dosen .............. Error! Bookmark not defined. Gambar 4. 9 Pasangan Mahasiswa ......................... Error! Bookmark not defined. Gambar 4. 10 Pasangan Dosen .............................. Error! Bookmark not defined. Gambar 4. 11 Pelanggaran Generasi 1 ................... Error! Bookmark not defined. Gambar 4. 12 Nilai Fitness Generasi 1 .................. Error! Bookmark not defined. Gambar 4. 13 Fitness relatif tiap populasi ............. Error! Bookmark not defined. Gambar 4. 14 Fitness kumulatif tiap populasi ....... Error! Bookmark not defined. 7
Gambar 4. 15 Bilangan Acak ................................. Error! Bookmark not defined. Gambar 4. 16 Nilai Pc dan acak ............................. Error! Bookmark not defined. Gambar 4. 17 Orang tua ......................................... Error! Bookmark not defined. Gambar 4. 18 Kromosom yang mengalami crossover ......... Error! Bookmark not defined. Gambar 4. 19 Kromosom sebelum dan sesudah crossover .. Error! Bookmark not defined. Gambar 4. 20 Kromosom yang Mengalami Seleksi Mutasi Error! Bookmark not defined. Gambar 4. 21 Pasangan dosen sebelum dan sesudah GA .... Error! Bookmark not defined. Gambar 4. 22 Nilai fitness dalam 10 generasi ....... Error! Bookmark not defined. Gambar 4. 23 Nilai fitness dalam 10 generasi dalam grafik Error! Bookmark not defined. Gambar 4. 24 Menu generate laporan .................... Error! Bookmark not defined. Gambar 4. 25 Individu terbaik generasi ke-6 ......... Error! Bookmark not defined. Gambar 4. 26 Jadwal Akhir ................................... Error! Bookmark not defined. Gambar 4. 27 Jadwal Final..................................... Error! Bookmark not defined. Gambar 4. 28 Menu cetak laporan ......................... Error! Bookmark not defined. Gambar 4. 29 Jadwal ujian dalam interface ........... Error! Bookmark not defined. Gambar 4. 30 Perintah print jadwal ....................... Error! Bookmark not defined. Gambar 4. 31 Pengujian terhadap generasi ............ Error! Bookmark not defined. Gambar 4. 32 Pengujian terhadap populasi............ Error! Bookmark not defined. Gambar 4. 33 Pengujian terhadap nilai fitness....... Error! Bookmark not defined.
8
DAFTAR PUSTAKA Buliali, Joko Lianto. 2008. Penjadwalan Matakuliah dengan Menggunakan Algoritma Genetika dan Metode Constraint Satisfaction. Institut Teknologi Sepuluh Nopember. Kusumadewi, Sri. 2003. Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Graha Ilmu. Sahal, Mochammad. 2000. Pembuatan Software Penjadwalan Kuliah dan Ujian di Jurusan Teknik Elektro FTI-ITS Surabaya dengan Menggunakan Algoritma Genetika. Institut Teknologi Sepuluh Nopember. Santoso, Arif Agung. 2011. Implementasi Algoritma Genetika Untuk Menyusun Jadwal Mata Pelajaran Pada SMA Negeri 1 Srengat. Universitas Brawijaya. Saptono, Fajar. 2007. Perancangan Algoritma Genetika Untuk Menentukan Jalur Terpendek. Yogyakarta: Seminar Nasional Aplikasi Teknologi Informasi. Setemen, Komang. 2008. Kombinasi Algoritma Genetika dan Tabu Search dalam Pembuatan Tabel Jadwal Mata Kuliah. Institut Teknologi Sepuluh Nopember. Suyanto. 2006. Evolutionary Computation-Komputasi Berbasis Evolusi dan Genetika. Yogyakarta: Graha Ilmu.
9
DAFTAR TABEL Tabel 2. 1 Terminologi Algoritma Genetika .......... Error! Bookmark not defined. Tabel 2. 2 Probabilitas Seleksi dan Nilai Fitness ... Error! Bookmark not defined. Tabel 2. 3 single-point crossover ........................... Error! Bookmark not defined. Tabel 2. 4 mulit-point crossover ............................ Error! Bookmark not defined. Tabel 2. 5 Crossover Seragam ............................... Error! Bookmark not defined. Tabel 2. 6 Mutasi pada Pengkodean Biner............. Error! Bookmark not defined. Tabel 2. 7 Mutasi pada Pengkodean Permutasi ..... Error! Bookmark not defined. Tabel 3. 1 Slot waktu yang tersedia di Jurusan Teknik Informatika UMM ... Error! Bookmark not defined. Tabel 3. 2 Nilai Prioritas ........................................ Error! Bookmark not defined.
10
Tabel 4. 1 Data Mahasiswa dan Dosen Pembimbing ........... Error! Bookmark not defined. Tabel 4. 2 Pelanggaran dalam 10 generasi ............. Error! Bookmark not defined. Tabel 4. 3 Tabel Pengujian Unit ............................ Error! Bookmark not defined. Tabel 4. 4 Tabel Pengujian Integrasi...................... Error! Bookmark not defined. Tabel 4. 5 Tabel Pengujian Validasi ...................... Error! Bookmark not defined.
11
