jurusan teknik informatika fakultas … informatika universitas muhammadiyah malang oleh : fatmawati...
TRANSCRIPT
IMPLEMENTASI ALGORITMA GENETIKA PADA
OPTIMALISASI PENJADWALAN MATA PELAJARAN
(Studi Kasus SMP Negeri 1 Singosari)
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1
Teknik Informatika Universitas Muhammadiyah Malang
Oleh :
Fatmawati Puspitasari
201010370311026
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNIK
UNIVERSITAS MUHAMMADIYAH MALANG
2014
i
LEMBAR PERSETUJUAN
IMPLEMENTASI ALGORITMA GENETIKA PADA
OPTIMALISASI PENJADWALAN MATA PELAJARAN
(Studi Kasus SMP Negeri 1 Singosari)
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui,
Pembimbing I Pembimbing II
Yufis Azhar, M.Kom Yuda Munarko, S.Kom, M.ScNIDN. 0728088701 NIP. 108.0611.0443
ii
LEMBAR PENGESAHAN
IMPLEMENTASI ALGORITMA GENETIKA PADA
OPTIMALISASI PENJADWALAN MATA PELAJARAN
(Studi Kasus SMP Negeri 1 Singosari)
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh :FATMAWATI PUSPITASARI
201010370311026
Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis pengujian padatanggal 17 Juli 2014
Menyetujui,
Penguji I Penguji II
Eko Budi Cahyono, S.Kom.,MT. Wahyu A. Kusuma,M.KomNIP. 10895040330 NIDN. 0720068701
MengetahuiKetua Jurusan Teknik Informatika
Yuda Munarko, S.Kom, M.ScNIP. 108.0611.0443
iii
LEMBAR PERNYATAAN
Yang bertanda tangan dibawah ini :
Nama : Fatmawati Puspitasari
NIM : 201010370311026
Fakultas / Jurusan : Teknik / Teknik Informatika
Judul : IMPLEMENTASI ALGORITMA GENETIKA PADA
OPTIMALISASI PENJADWALAN MATA
PELAJARAN (Studi Kasus SMP Negeri 1 Singosari)
Dengan ini menyatakan bahwa :
1. Seluruh isi adalah karya saya sendiri dan bukan merupakan karya tulis orang
lain, baik sebagian maupun seluruhnya, kecuali dalam bentuk kutipan yang
telah disebutkan sumbernya.
2. Apabila dikemudian hari ternyata tugas akhir saya tulis terbukti hasil
jiplakan, maka saya akan bersedia menanggung segala resiko yang akan
saya terima.
Demikian pernyataan ini dibuat dengan segala kesadaran.
Mengetahui, Malang, 11 Juli 2014
Pembimbing I Yang Membuat Pernyataan
Yufis Azhar, M.Kom Fatmawati PuspitasariNIDN. 0728088701 201010370311026
vi
LEMBAR PERSEMBAHAN
Puji syukur kepada Allah SWT atas rahmat dan karunianya sehingga
penulis dapat menyelesaikan Tugas Akhir ini. Penulis menyampaikan ucapan
terima kasih yang sebesar-besarnya kepada :
1. Allah SWT atas segala rahmad, hidayah dan ridho-Nya, serta tidak lupa
sholawat dan salam kepada junjungan nabi besar Muhammad SAW.
2. Ayahanda Mahmud dan Ibunda Eny Romlah tercinta yang tiada henti
mendoakan dan memberikan nasehat, dukungan moriel dan materiel, serta
semua pengorbanan jiwa raganya demi terselesainya pendidikan S1 yang
saya tempuh, semoga Allah SWT membalas semua pengorbanannya
AMIN.
3. Terima kasih kepada Bpk Yufiz Azhar, M.Kom selaku pembimbing I dan
Bpk Yuda Munarko, S.Kom, M.Sc selaku pembimbing II, yang telah
bersabar untuk membimbing saya sampai terselesaikannya pendidikan S1
yang saya tempuh dengan tepat waktu.
4. Kakak dan adek ( Kristin Betty Vebrianan, S.H, Irawan Setiaji, S.E,
Kharisma Nirmalasari, Kharisna Nirmalasari ) yang sangat saya
banggakan terima kasih atas doa-doanya serta motivasi dan semangat yang
kalian beriakan.
5. Nenek saya H. Erma dan Tumini terima kasih selama ini tiada hentinya
mendoakan dan mendukung saya semoga Allah SWT membalas semuanya
AMIN.
6. Sahabat-sahabat saya ( Irham Yunanda, Fatimatuzzahrah, Annisah Nuryati
Siregar, Khozaini, Mohammad Kadarusman, Irham Krisna Bahari,
Kharisma Putra Borneo ) terima kasih selama telah memberikan semangat
dan dukungan kepada saya.
vii
KATA PENGANTAR
Dengan Memanjatkan puji dan syukur kehadirat Allah SWT atas limpahan
rahmat dan hidayah-NYA sehingga penulis dapat menyelesaikan tugas akhir yang
berjudul : IMPLEMENTASI ALGORITMA GENETIKA PADA
OPTIMALISASI PENJADWALAN MATA PELAJARAN (Studi Kasus SMP
Negeri 1 Singosari).
Di dalam tulisan ini disajikan pokok-pokok bahasan yang meliputi
pendahuluan, dasar teori, perancangan sistem, pengujian, analisa sistem, serta
kesimpulan.
Penulis menyadari sepenuhnya bahwa dalam penulisan tugas akhir ini masih
banyak kekurangan dan keterbatasan. Oleh karena itu peneliti mengharapkan saran
yang membangun agar tulisan ini bermanfaat bagi perkembangan ilmu pengetahuan
kedepan.
Malang, Agustus 2014
Fatmawati Puspitasari201010370311026
viii
DAFTAR ISI
HALAMAN JUDUL
LEMBAR PERSETUJUAN .......................................................................... i
LEMBAR PENGESAHAN ........................................................................... ii
LEMBAR PERNYATAAN ........................................................................... iii
ABSTRAK ...................................................................................................... iv
ABSTRACT.................................................................................................... v
HALAMAN PERSEMBAHAN .................................................................... vi
KATA PENGANTAR.................................................................................... vii
DAFTAR ISI................................................................................................... viii
DAFTAR GAMBAR...................................................................................... xii
DAFTAR TABEL .......................................................................................... xiv
BAB I PENDAHULUAN
1.1. Latar Belakang ....................................................................... 1
1.2. Rumusan Masalah ................................................................. 2
1.3. Batasan Masalah .................................................................... 2
1.4. Tujuan ................................................................................... 3
1.5. Metodologi ............................................................................ 3
1.6. Sistematika Penulisan ........................................................... 4
BAB II LANDASAN TEORI
2.1 Optimalisasi Penjadwalan ...................................................... 6
2.2 Algoritma Genetika................................................................ 6
2.2.1 Pengertian ..................................................................... 6
2.2.2 Permasalahan yang Membutuhkan Algoritma Genetika 7
2.2.3 Aplikasi Algoritma Genetika ........................................ 8
2.2.4 Beberapa Pengertian Dasar ........................................... 9
2.2.5 Siklus Algoritma Genetika............................................ 11
2.2.6 Komponen Algoritma Genetika .................................... 12
2.2.6.1 Skema Pengkodean........................................... 12
ix
2.2.6.2 Nilai Fittness..................................................... 12
2.2.6.3 Seleksi Orang Tua............................................. 13
2.2.6.4 Pindah Silang.................................................... 14
2.2.6.5 Mutasi ............................................................... 15
2.2.6.6 Eliteisme ........................................................... 16
2.2.6.7 Penggantian Populasi........................................ 16
2.2.6.8 Kriteria Penghentian ......................................... 16
2.2.6.9 Contoh Kasus Algoritma Genetik Untuk
Menyelesaikan Masalah ................................... 17
BAB III ANALISA DAN PERANCANGAN SISTEM
3.1 Analisa Masalah .................................................................... 20
3.2 Analisa Kebutuhan ................................................................. 20
3.3 Perancangan Algoritma Genetika .......................................... 21
3.3.1 Pengkodean................................................................... 21
3.3.2 Inisialisasi Kromosom .................................................. 21
3.3.3 Perhitungan Nilai Fitness ............................................ 22
3.3.4 Seleksi........................................................................... 25
3.3.5 Mutasi ........................................................................... 26
3.3.6 Pindah Silang (Crossover) ............................................ 26
3.4 Perancangan Sistem ............................................................... 27
3.4.1 Usecase diagram .......................................................... 27
3.4.2 Activity diagram ........................................................... 28
3.4.2.1 Mengatur data guru.......................................... 28
3.4.2.2 Mengatur data mata pelajaran.......................... 29
3.4.2.3 Login admin ..................................................... 29
3.4.2.4 Mainkan aplikasi penjadwalan ........................ 30
3.4.2.5 Tampil Hasil ..................................................... 30
3.4.3 Sequence diagram......................................................... 31
3.4.3.1 Mengatur Data Guru ......................................... 31
3.4.3.2 Mengatur Mata Pelajaran.................................. 31
3.4.3.3 Mengatur Login Admin ..................................... 32
x
3.4.3.4 Mengatur Mainkan aplikasi penjadwalan ......... 33
3.4.3.5 Mengatur Tampil hasil...................................... 33
3.4.4 Class Diagram .............................................................. 34
3.4.5 Rancangan Desain Database ........................................ 35
3.4.5.1 Entity Relationship Diagram (ERD) .............. 35
3.4.5.2 Tabel Database ............................................... 36
3.4.6 Perancangan Tampilan Antar muka.............................. 38
3.4.6.1 Rancangan Tampilan Login ........................... 38
3.4.6.2 Rancangan Tampilan Menu Utama ................ 38
3.4.6.3 Rancangan Tampilan Halaman Editor Mata
Pelajaran ......................................................... 39
3.4.6.4 Rancangan Tampilan Editor Guru.................. 39
3.2.3.5 Rancangan Tampilan Penjadwalan................. 40
BAB IV IMPLEMENTASI DAN PENGUJIAN
4.1 Kebutuhan Perangkat ............................................................. 41
4.1.1 Perangkat Lunak Yang Digunakan............................... 41
4.1.2 Perangkat Keras Yang Digunakan................................ 41
4.2 Implementasi Program ............................................................ 42
4.2.1 Form Login ................................................................... 42
4.2.2 Form Menu utama......................................................... 42
4.2.3 Form add data guru....................................................... 43
4.2.4 Form add data mata pelajaran ...................................... 43
4.2.5 Form jam ...................................................................... 44
4.2.6 Form mainkan aplikasi penjadwalan ............................ 44
4.2.7 Tampilan Form Hasil.................................................... 45
4.3 Kode Program Algoritma Genetika ....................................... 45
4.3.1 Kode Program Inisialisasi Kromosom.......................... 45
4.3.2. Kode Program Perhitungan Fungsi Fitness.................. 47
4.3.3. Kode Program Seleksi.................................................. 49
4.3.4. Kode Program Pindah Silang (Crossover) ................... 51
4.3.5. Kode Program Mutasi .................................................. 52
xi
4.3.6. Kode Program Generasi ............................................... 53
4.4 Pengujian interface aplikasi Algoritma Genetika .................. 53
4.5 Tahap Pengujian..................................................................... 54
BAB V KESIMPULAN DAN SARAN
5.1 Kesimpulan............................................................................. 56
5.2 Saran....................................................................................... 57
DAFTAR PUSTAKA ..................................................................................... 58
LAMPIRAN
xii
DAFTAR GAMBAR
Gambar 2.1 Ilustrasi Representasi Penyelesaian Permasalahan dalam
Algoritma Genetika ................................................................. 10
Gambar 2.2 Siklus algoritma genetika yang diperkenalkan oleh David
Goldberg ................................................................................... 11
Gambar 2.3 Siklus algoritma genetika Zbigniew Michalewicz hasil
perbaikan dari siklus algoritma genetika yang diperkenalkan
oleh David Goldberg ................................................................ 11
Gambar 2.4 Ilustrasi Metode Roulette-wheel ............................................... 13
Gambar 2.5 Proses pindah silang satu titik .................................................. 14
Gambar 2.6 Proses pindah silang banyak titik ............................................. 15
Gambar 2.7 Proses mutasi pada tingkat kromosom ..................................... 15
Gambar 2.8 Proses mutasi pada tingkat gen................................................. 15
Gambar 2.9 Proses mutasi pada tingkat hanya satu bit yang berubah ......... 15
Gambar 2.10 Hubungan generasi dengan fitness ........................................... 18
Gambar 3.1 Use case diagram ..................................................................... 27
Gambar 3.2 Add data guru............................................................................ 28
Gambar 3.3 Add mata pelajaran ................................................................... 29
Gambar 3.4 Login admin.............................................................................. 29
Gambar 3.5 Mainkan aplikasi penjadwalan ................................................. 30
Gambar 3.6 Tampil Hasil ............................................................................. 30
Gambar 3.7 Add guru ................................................................................... 31
Gambar 3.8 Add data mata pelajaran............................................................ 32
Gambar 3.9 Login admin.............................................................................. 32
Gambar 3.10 Mainkan aplikasi penjadwalan ................................................. 33
Gambar 3.11 Tampil hasil .............................................................................. 34
Gambar 3.12 Class Diagram Aplikasi penjadwalan di SMP Negeri 1
Singosari menggunakan algoritma genetika............................. 34
Gambar 3.13 Entity Relationship diagram..................................................... 36
Gambar 3.14 Rancangan tampilan login ........................................................ 38
Gambar 3.15 Rancangan tampilan menu utama............................................. 39
xiii
Gambar 3.16 Rancangan tampilan editor mata pelajaran .............................. 39
Gambar 3.17 Rancangan tampilan editor guru .............................................. 40
Gambar 3.18 Rancangan tampilan penjadwalan ............................................ 40
Gambar 4.1 Form Login ............................................................................... 42
Gambar 4.2 Form Menu utama .................................................................... 42
Gambar 4.3 Form add data guru .................................................................. 43
Gambar 4.4 Form add data mata pelajaran .................................................. 43
Gambar 4.5 Form jam ................................................................................. 44
Gambar 4.6 Form Aplikasi........................................................................... 44
Gambar 4.7 Tampilan Form hasil ................................................................ 45
Gambar 4.8 Kode program mengambil data dan pembuatan
kromosom dari database .......................................................... 46
Gambar 4.9 Kode program inisialisasi pembagian kromosom tiap
kelas.......................................................................................... 46
Gambar 4.10 Kode program fitness bentrok guru .......................................... 47
Gambar 4.11 Kode program fitness bentrok ruang ........................................ 48
Gambar 4.12 Kode program fitness Jumlah jadwal mengajar guru dalam
sehari melampaui batas mengajar lebih dari 3 jam
pelajaran ................................................................................... 49
Gambar 4.13 Kode program seleksi ............................................................... 50
Gambar 4.14 Kode program untuk menentukan musuh atau gen
pengganti .................................................................................. 51
Gambar 4.15 Kode program pindah silang (crossover) ................................. 52
Gambar 4.16 Kode program mutasi ............................................................... 52
Gambar 4.17 Kode program generasi............................................................. 53
xiv
DAFTAR TABEL
Tabel 2.1 Metode Roulette-wheel.................................................................. 13
Tabel 2.2 Proses Perhitungan Algoritma Genetik ......................................... 17
Tabel 2.3 Hubungan Ukuran Populasi dengan Nilai Fitness ........................ 18
Tabel 2.4 Hubungan Jumlah Generasi dengan Nilai Fitness ........................ 19
Tabel 3.1 Syarat kegiatan belajar .................................................................. 20
Tabel 3.2 Jumlah Jam Tiap Mata Pelajaran Perminggunya .......................... 21
Tabel 3.3 Inisialisasi Kromosom................................................................... 22
Tabel 3.4 Contoh ilustrasi syarat 1 ............................................................... 23
Tabel 3.5 Contoh ilustrasi syarat 2 ............................................................... 23
Tabel 3.6 Contoh ilustrasi syarat 3 ............................................................... 24
Tabel 3.7 Contoh proses mutasi dan crossover ............................................. 25
Tabel 3.8 Penjelasan use case diagram......................................................... 28
Tabel 3.9 Tabel Mata Pelajaran..................................................................... 36
Tabel 3.10 Tabel Guru..................................................................................... 37
Tabel 3.11 Tabel Jam ...................................................................................... 37
Tabel 3.12 Tabel Pesan ................................................................................... 38
Tabel 4.1 Pengujian Interfice ........................................................................ 53
Tabel 4.2 Pengujian Program ........................................................................ 54
58
DAFTAR PUSTAKA
[1] Pradnyana , Nanda Bagus, Dwi Sunaryono, Abdul Munif. 2012. Perancangan
dan Pembuatan Aplikasi Penjadwalan Perkuliahan Menggunakan Algoritma
Genetik dan Teknologi Java API for XML Web Service pada Platform Android.
Surabaya: Institut Teknologi Sepuluh Nopember (ITS).
[2] Mirwan, Muhammad. 2013 . Optimalisasi Koordinasi Pemerintahan Tingkat
Kecamatan Di Kecamatan Kota Bangun Kabupaten Kutai Kartanegara.
Samarinda: Fisip Unmul.
[3] Wati, Dwi Ana Ratna, Yuli Agusti Rochman. 2009. Model Penjadwalan
Matakuliah Secara OtomatisBerbasis Algoritma Particle Swarm Optimization
(PSO). Yogyakarta: Fakultas Teknologi Industri Universitas Islam Indonesia.
[4] Sutojo, T, Edy Mulyanto, Dr. Vincent Suhartono. 2011. Kecerdasan Buatan.
Yogyakarta : Andi.
[5] Cholis, Muhammad Nur. 2012. Aplikasi Penjadwalan Pelajaran Moving Class
Dengan Algoritma Genetika (Studi Kasus Smp Negeri 1 Paiton). Malang:
Jurusan teknik informatika Fakultas teknik Universitas Muhammadiyah
Malang.
[6] Informatika. 2013. Algoritma Genetika. (http://informatika.web.id/algoritma-
genetik.htm di akses pada tgl 11 april jam 21.31).
[7] Yuliani. 2010. Algoritma Genetik Untuk Menyelesaikan Masalah Optimasi
Fungsi Berkendala Dengan Pengkodean Bilangan Bulat. Surabaya: Jurusan
Teknik Informatika Sekolah Tinggi Teknologi Adisutjipto (STTA).
[8] Sri, Widodo Thomas. 2012. Komputasi Evolusioner (Algoritma Genetik,
Pemrograman Genetik, dan Pemograman Evolusioner). Yogyakarta: Graha
Ilmu.