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
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 1 Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui, Pembimbing I
Pembimbing II
Yufis Azhar, M.Kom NIDN. 0728088701
Yuda Munarko, S.Kom, M.Sc NIP. 108.0611.0443
i
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 1 Teknik Informatika Universitas Muhammadiyah Malang Disusun Oleh : FATMAWATI PUSPITASARI 201010370311026 Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis pengujian pada tanggal 17 Juli 2014 Menyetujui, Penguji I
Penguji II
Eko Budi Cahyono, S.Kom.,MT. NIP. 10895040330
Wahyu A. Kusuma,M.Kom NIDN. 0720068701
Mengetahui Ketua Jurusan Teknik Informatika
Yuda Munarko, S.Kom, M.Sc NIP. 108.0611.0443
ii
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 NIDN. 0728088701
Fatmawati Puspitasari 201010370311026
iii
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.
vi
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 Puspitasari 201010370311026
vii
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
BAB II
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
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
viii
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 ................................... BAB III
17
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
ix
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
BAB IV
Pelajaran .........................................................
39
3.4.6.4 Rancangan Tampilan Editor Guru..................
39
3.2.3.5 Rancangan Tampilan Penjadwalan.................
40
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
x
BAB V
4.3.6. Kode Program Generasi ...............................................
53
4.4 Pengujian interface aplikasi Algoritma Genetika ..................
53
4.5 Tahap Pengujian.....................................................................
54
KESIMPULAN DAN SARAN 5.1 Kesimpulan.............................................................................
56
5.2 Saran.......................................................................................
57
DAFTAR PUSTAKA .....................................................................................
58
LAMPIRAN
xi
DAFTAR GAMBAR Gambar 2.1
Ilustrasi Representasi Penyelesaian Permasalahan dalam Algoritma Genetika .................................................................
10
Gambar 2.2 Siklus algoritma genetika yang diperkenalkan oleh David Goldberg ................................................................................... Gambar 2.3
11
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
xii
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 ..........................................................
Gambar 4.9
46
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
xiii
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
xiv
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/algoritmagenetik.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.
58
