BAB 3 PERANCANGAN PROGRAM
3.1.
Perancangan Database
3.1.1. Conceptual Model Conceptual Model merupakan penggambaran database secara konsep dengan menggunakan ERD. Conceptual Model ditunjukkan oleh Gambar 3.1.
Gambar 3.1. ERD
22 3.1.2. Tabel-tabel Database Secara umum, tabel-tabel dalam database ini dapat dikategorikan menjadi empat, yaitu tabel informasi, tabel Fuzzy Relation, tabel Genetic Algorithms, dan tabeltabel lainnya yang digunakan sebagai bantuan. Selain itu, tabel-tabel juga dapat dibagi menjadi tiga berdasarkan sifat data yang disimpan, yaitu tabel master, tabel proses, dan tabel temporary. Tabel master ditandai dengan huruf “ms” pada awal nama tabel, dimana data dalam tabel ini merupakan master dari data-data yang ada pada tabel lainnya. Tabel proses ditandai dengan huruf “tr” pada awal nama tabel, dan bertujuan untuk menyimpan data-data yang dihasilkan dari sebuah relasi. Tabel temporary ditandai dengan huruf “copy” pada awal nama tabel. Tabel temporary tidak dijabarkan pada uraian berikut ini.
3.1.2.1.Tabel Informasi Tabel dalam kategori ini bertujuan untuk menyimpan data-data yang digunakan sebagai informasi dalam program penjadwalan sidang tugas akhir. Tabel-tabel yang masuk kategori ini ditunjukkan pada Tabel 3.1. sampai Tabel 3.6. Tabel 3.1. Tabel GN_msdosen Name
Type
Dosen_id
Int
Dosen_val
Text
Size 11
Key *
Keterangan Nomor Induk Dosen Nama Dosen
23 Tabel 3.2. Tabel GN_msproposal Name
Type
Size
Key
Int
11
*
Proposal_mahasiswa Int
11
NIM
Proposal_nim
varchar
10
NIM mahasiswa
Pembimbing1_id
Int
11
Kode Pembimbing 1
Pembimbing1_id
Int
11
Kode Pembimbing 2
Proposal_val
Text
Proposal_id
Keterangan Kode Proposal
Judul Proposal
Tabel 3.3. Tabel GN_mstanggal Name
Type
Tanggal_id
Int
Tanggal_val
Text
Size
Key
11
*
Keterangan Kode Tanggal Tanggal yang bisa terpakai
Tabel 3.4. Tabel GN_mssesi Name
Type
Sesi_id
Int
Sesi_val
Text
Size
Key
11
*
Keterangan Kode sesi Sesi yang bisa terpakai
Tabel 3.5. Tabel GN_mskelas Name
Type
Kelas_id
Int
Kelas_val
Text
Size
Key
11
*
Keterangan Kode kelas Kelas yang bisa terpakai
24 Tabel 3.6. Tabel GN_mstopik Name
Type
Topik_id
Int
Topik_val
Text
Size
Key
11
*
Keterangan Kode topik Nama topik
Tabel GN_mstopik digunakan untuk menyimpan topi-topik tugas akhir.
3.1.2.2 Tabel Fuzzy Relation Tabel Fuzzy Relation digunakan untuk menyimpan nilai-nilai yang digunakan dalam perhitungan memakai teori Fuzzy Relation. Hasil perhitungan juga disimpan dalam tabel pada kategori ini. Tabel 3.7. sampai Tabel 3.9. menunjukkan tabel-tabel dalam kategori ini. Tabel 3.7. Tabel GN_trrelasiDT Name
Type
Size
Key *
Keterangan
Relasi_id
Int
11
Kode Relasi
Dosen_id
Int
11
Kode Dosen
Topik_id
Int
11
Kode Topik
Relasi_val
Int
11
Nilai keahlian dosen terhadap topik tugas akhir
Tabel GN_trrelasiDT digunakan untuk menyimpan nilai expertise dosen yang diperoleh dari input-an user.
25 Tabel 3.8. Tabel GN_trrelasiPT Name
Type
Size
Key *
Keterangan
Relasi_id
Int
11
Kode Relasi
Proposal_id
Int
11
Kode Proposal
Topik_id
Int
11
Kode Topik
Relasi_val
Int
11
Nilai Relasi Proposal terhadap Topik
Tabel GN_trrelasiPT digunakan untuk menyimpan nilai content tugas akhir yang diperoleh dari input-an user. Tabel 3.9. Tabel GN_trelasiDP Name
Type
Size
Key *
Keterangan
Relasi_id
Int
11
Kode Relasi
Proposal_id
Int
11
Kode Proposal
Dosen_id
Int
11
Kode Dosen
Relasi_val
Int
11
Nilai Kompetensi Dosen terhadap Proposal
Tabel GN_trrelasiDP digunakan untuk menyimpan hasil perhitungan tingkat kompetensi dosen dengan memakai Fuzzy Relation (Subbab 3.2.).
26 3.1.2.3.Tabel Genetic Algorithms Tabel-tabel yang masuk dalam kategori ini adalah tabel-tabel yang secara langsung dipakai dalam proses Genetic Algorithms. Tabel-tabel ini menyimpan berbagai keterangan yang dibutuhkan dalam men-generate sebuah jadwal sidang tugas akhir. Tabel 3.10. sampai Tabel 3.11. menjelaskan mengenai tabel-tabel dalam kategori ini. Tabel 3.10. Tabel GN_msjadwal Name
Type
Size
Key *
Keterangan
Jadwal_id
Int
11
Kode Jadwal
Tanggal_Id
Int
11
Kode Tanggal
Sesi_Id
Int
11
Kode Sesi
Kelas_Id
Int
11
Kode Kelas
Tabel GN_msjadwal digunakan untuk menyimpan tanggal sidang, sesi, dan kelas yang akan dipakai dalam satu periode sidang tugas akhir. Tabel 3.11. Tabel GN_trberhalangan Name
Type
Size
Key *
Keterangan
Berhalangan_id
Int
11
Kode berhalangan
Dosen_id
Int
11
Kode Dosen
Tanggal_id
Int
11
Kode Tanggal
Sesi_id
Int
11
Kode Sesi
Berhalangan_val
Int
1
Value berhalangan / tidak
27 Tabel GN_trberhalangan digunakan untuk menyimpan jadwal berhalangan dosen. Dari tabel ini, diketahui jadwal dapat hadir seorang dosen. Tabel GN_trcopyhalangan digunakan untuk tabel sementara ketika terjadi perhitungan perubahan jadwal. Tabel 3.12. Tabel GN_trproporsi Name
Type
Size
Key *
Keterangan
Proporsi_id
Int
11
Proposal_id
Int
11
Kode Proposal
Pembimbing1_id
Int
11
Kode Pembimbing 1
Pembimbing2_id
Int
11
Kode Pembimbing 2
KetuaPenguji_id
Int
11
Kode ketua penguji
AnggotaPenguji_id Int
11
Kode anggota penguji
Kompetensi_fc
11
Fitness cost hasil proporsi
Int
Kode Proporsi
Tabel GN_trproporsi digunakan untuk menyimpan susunan mahasiswa dan dosen-dosen penguji, yang selanjutnya dimasukkan ke dalam Tabel GN_trgen (gen-gen pada Genetic Algorihtms). Tabel 3.13. Tabel GN_trgen Name
Type
Size
Key *
Keterangan
Gen_id
Int
11
Kode gen
Jadwal_id
Int
11
Kode Jadwal
Kromosom_index Int
11
Index kromosom
Proporsi_id
Int
11
Kode Proporsi
Jadwal_fc
Int
11
Fitness cost jadwal
28 Tabel GN_trgen ini nantinya akan menjadi hasil akhir yang menentukan jadwal dan proporsi yang terpilih.
3.2.
Perancangan Implementasi Fuzzy Relation Dalam pengembangan software penjadwalan sidang tugas akhir ini, Fuzzy
Relation digunakan untuk menentukan dan menyusun dosen-dosen penguji yang ditugaskan menguji suatu tugas akhir. Penyusunan ini dilakukan dengan harapan agar tugas akhir diuji oleh dosen-dosen yang memiliki keahlian (expertise) yang sesuai dengan topik tugas akhir tersebut. Relasi antara dosen dengan tugas akhir ditentukan dengan melihat relasi antara dosen dengan topik-topik tugas akhir dan tugas akhir dengan topik-topik tugas akhir. Ada tiga hal yang harus diperhatikan yaitu dosen, tugas akhir, dan topik tugas akhir (agar tidak membingungkan, pada uraian berikutnya digunakan kata “topik”). Topik didefinisikan sebagai domain T = {t1,t2,…,tn} di mana dosen dan tugas akhir merupakan fuzzy set yang berada dalam domain T dan didefinisikan sebagai D ={D1,D2,… Dp} dan P={P1,P2,…,Pq} dengan n adalah jumlah topik, p adalah jumlah dosen yang menguji, dan q adalah jumlah tugas akhir yang disidang.
3.2.1. Relasi antara Dosen dan Topik (Nilai Expertise) Dalam relasi ini, dosen D merupakan fuzzy set dari topik T yang berarti setiap dosen memiliki nilai expertise (keahlian) terhadap setiap topik yang ada. Untuk lebih jelas, dapat dilihat pada contoh berikut:
29 Misalkan nilai p = 6 dan n = 8. Ini berarti ada 6 dosen dan 8 topik, yang dapat direpresentasikan dalam bentuk D = {D1,D2,D3,D4,D5,D6} T = {t1,t2,t3,t4,t5,t6}} dan kemudian diberikan nilai fuzzy sebagai berikut, µD1={0.3/t2,0.7/t5,1/t7,1/t8}, µD2={1/t2,0.8/t5,0.8/t7,1/t8}, µD3={0.9/t1,0.9/t3,1/t4,0.8/t6}, µD4={1/t1,0.5/t3,0.8/t4,0.8/t6}, µD5={0.1/t2,1/t4,0.7/t5,1/t8}, µD6={0.9/t2,0.8/t4,1/t5,1/t8}. Arti dari nilai fuzzy di atas, misalnya pada dosen D1, yaitu dosen D1 memiliki nilai expertise terhadap topik t2 sebesar 30%, topik t5 sebesar 70%, topik t7 sebesar 100%, dan topik t8 sebesar 100%. Topik-topik lain yang tidak ditulis memiliki arti bahwa dosen D1 tidak memiliki keahlian untuk topik-topik tersebut (nilai expertise =0%). Arti yang sama berlaku juga untuk dosen-dosen yang lain. Nilai expertise ini di-input-kan oleh user dan disimpan ke dalam table GN_trrelasiDT.
3.2.2. Relasi antara Tugas Akhir dan Topik (Nilai Content) Relasi ini memiliki arti yang sama dengan relasi antara dosen dan topik. Hanya saja pada relasi ini, yang merupakan fuzzy set adalah tugas akhir P, dimana arti dari relasi ini adalah setiap tugas akhir memiliki nilai content (kandungan) terhadap topik. Contoh berikut, menggunakan domain topik T yang sama dengan contoh pada subbab 3.2.1. Misalkan nilai q = 5, sehingga ada 5 tugas akhir yang dapat direpresentasikan sebagai berikut: P = {P1,P2,P3,P4,P5}
30 dan nilai fuzzy tugas akhir P terhadap topik T adalah sebagai berikut : µP1={0.8/t2,0.7/t3,1/t8}, µP2={1/t2,0.8/t4,0.9/t7}, µP3={0.9/t1,1/t3}, µP4={1/t1,0.7/t3,0.8/t5,0.3/t6}, µP5={1/t4}. Nilai tersebut berarti tugas akhir P1 relevan atau memiliki nilai content terhadap topik t2 sebesar 80%, topik t3 sebesar 70%, dan topik t8 sebesar 100%. Pada contoh di atas juga terdapat tugas akhir P5 yang hanya memiliki sebuah nilai yaitu 1/ t4 . Maksudnya adalah tugas akhir P5 benar-benar hanya relevan dengan topik t4 dengan nilai content sebesar 100%. Nilai content ini juga di-input-kan oleh user dan disimpan dalam table GN_trrelasiPT.
3.2.3. Relasi antara Dosen dan Tugas Akhir (Tingkat Kompetensi) Relasi ini menggambarkan tingkat kompetensi dari dosen terhadap tugas akhir. Setiap anggota dalam set dosen dihitung tingkat kompetensinya terhadap setiap anggota dalam set tugas akhir. Untuk menghitung tingkat kompetensi tersebut, digunakan rumus yang telah disesuaikan sebagai berikut,
Sebagai contoh, dengan menggunakan domain T pada contoh 3.2.1., nilai expertise µD1={0.3/t2,0.7/t5,1/t7,1/t8}, µD2={1/t2,0.8/t5,0.8/t7,1/t8}, µD3={0.9/t1,0.9/t3,1/t4,0.8/t6}, µD4={1/t1,0.5/t3,0.8/t4,0.8/t6}, µD5={0.1/t2,1/t4,0.7/t5,1/t8}, µD6={0.9/t2,0.8/t4,1/t5,1/t8}.
31 dan nilai content µP1={0.8/t2,0.7/t3,1/t8}, µP2={1/t2,0.8/t4,0.9/t7}, µP3={0.9/t1,1/t3}, µP4={1/t1,0.7/t3,0.8/t5,0.3/t6}, µP5={1/t4}. maka tingkat kompetensi D1 terhadap P1 dapat dihitung sebagai berikut:
Dengan menggunakan rumus (3.2.), diperoleh tingkat kompetensi semua dosen terhadap tugas akhir seperti ditunjukkan pada tabel 3.14. Tabel 3.14. Tingkat Kompetensi Dosen Terhadap Tugas Akhir D\P
P1
P2
P3
P4
P5
D1
0.52
0.44
0
0.25
0
D2
0.72
0.67
0
0.29
0
D3
0.28
0.30
0.95
0.68
1
D4
0.20
0.30
0.47
0.64
0.80
D5
0.44
0.33
0
0.25
1
D6
0.72
0.63
0
0.29
0.80
Nilai tingkat kompetensi pada Tabel 3.14. tersebut disimpan dalam Tabel GN_trrelasiDP dan digunakan untuk menyusun prioritas setiap dosen terhadap mahasiswa (tugas akhir).
32 3.2.4. Pemilihan Dosen Pembimbing dan Penguji Pemilihan dosen pembimbing dilakukan dengan cara mahasiswa memilih dosen pembimbingnya sendiri. Sedangkan untuk dosen penguji, akan dipilih secara random. Pemilihan dosen penguji pada satu mahasiswa tidak boleh sama dengan salah satu dosen pembimbingnya. Setelah itu, proses optimasi akan dilakukan pada implementasi Genetic Algorithms.
3.3.
Perancangan Implementasi Genetic Algorithms Dalam
merancang
implementasi
Genetic
Algorithms
untuk
software
penjadwalan ini, dibutuhkan lima langkah penting, yaitu pengkodean kromosom, pembuatan populasi awal, proses regenerasi (crossover, dan mutasi), dan pengulangan proses regenerasi dan penyesuaian.
3.3.1. Pengkodean Kromosom (Encoding) Pengkodean kromosom dalam software ini adalah bagaimana suatu susunan jadwal sidang tugas akhir dituliskan dalam bentuk susunan gen-gen dalam kromosom, dimana setiap gen mewakili satu jadwal sidang untuk setiap mahasiswa. Susunan gen inilah yang nantinya mengalami proses crossover, mutasi, dan regenerasi. Tabel database yang dipakai adalah Tabel GN_msjadwal, Tabel GN_msproporsi, dan Tabel GN_trgen. Susunan jadwal sidang tugas akhir dibagi berdasarkan tanggal, sesi, dan ruang sidang seperti yang dapat dilihat pada Tabel 3.15. Data ini disimpan dalam Tabel GN_msjadwal.
33 Tabel 3.15. Susunan Jadwal Sidang Sesi 1
Sesi 2
Sesi 3
Tanggal 1
Ruang 1
Ruang 2
Ruang 1
Ruang 2
Ruang 1
Ruang 2
Tanggal 2
Ruang 1
Ruang 2
Ruang 1
Ruang 2
Ruang 1
Ruang 2
Tanggal 3
Ruang 1
Ruang 2
Ruang 1
Ruang 2
Ruang 1
Ruang 2
Tanggal 4
Ruang 1
Ruang 2
Ruang 1
Ruang 2
Ruang 1
Ruang 2
Mengacu pada Tabel 3.15., susunan gen disusun dalam bentuk matriks tiga dimensi. Susunan gen didefinisikan sebagai berikut: Gen [ 1 . . Jumlah Tanggal, 1 . . Jumlah Sesi, 1 . . Jumlah Kelas ] dimana jumlah tanggal menyatakan banyaknya tanggal sidang, jumlah sesi menyatakan banyak sesi sidang setiap harinya, dan Jumlah kelas menyatakan ruang kelas yang akan dipakai. Contoh bentuk matriks pengkodean gen dari Tabel 3.2 adalah sebagai berikut: [ 1, 1, 1 ] [ 1, 1, 2 ] [ 1, 2, 1 ] [ 1, 2, 2 ] [ 1, 3, 1 ] [ 1, 3, 2 ] [ 2, 1, 1 ] [ 2, 1, 2 ] [ 2, 2, 1 ] [ 2, 2, 2 ] [ 2, 3, 1 ] [ 2, 3, 2 ] [ 3, 1, 1 ] [ 3, 1, 2 ] [ 3, 2, 1 ] [ 3, 2, 2 ] [ 3, 3, 1 ] [ 3, 3, 2 ] [ 4, 1, 1 ] [ 4, 1, 2 ] [ 4, 2, 1 ] [ 4, 2, 2 ] [ 4, 3, 1 ] [ 4, 3, 2 ] Setiap matriks ini pertama-tama bernilai kosong, yang menandakan belum adanya mahasiswa yang disidang pada tanggal, sesi, dan kelas tersebut. Setiap gen pada matriks tersebut akan diisi dengan nilai-nilai berupa NIM, Pembimbing 1, Pembimbing 2, Ketua Penguji, dan Penguji yang diperoleh dari hasil implementasi Fuzzy Relation. Nilai-nilai tersebut didapat dari Tabel database GN_trproporsi. Setelah didapat gen yang terisi, data itu akan disimpan dalam Tabel GN_trgen. Selain itu, setiap gen juga menyimpan
34 fitness cost terhadap jadwal dan fitness cost terhadap tingkat kompetensi (perhitungan fitness cost ini dijelaskan pada Subbab 3.3.2.2 tentang Fitness Cost). Jadi setiap gen nantinya akan memiliki tujuh nilai, yaitu NIM mahasiswa yang disidang, Dosen Pembimbing 1, Dosen Pembimbing 2, Dosen Ketua Penguji, Dosen Penguji, fitness cost jadwal, dan fitness cost kompetensi. Indeks dari gen tersebut menyatakan jadwal sidang (tanggal, sesi, dan ruang sidang) sehingga gen ini dinamakan Gen Jadwal. Dengan penggabungan semua gen-gen yang ada, diperoleh sebuah kromosom (kandidat solusi) dengan gen-gen yang memiliki nilai berupa NIM mahasiswa yang disidang dan dosen-dosen, serta indeks untuk mewakili tanggal, sesi, dan ruang sidang. Kromosom-kromosom inilah yang dipakai dalam seluruh proses Genetic Algorithms pada software ini.
3.3.2. Pembuatan Populasi Awal Setelah melakukan pengkodean, langkah berikutnya dalam Genetic Algorithms adalah membentuk populasi awal yang terdiri dari beberapa kromosom. Langkahlangkah dalam membuat populasi awal adalah pembuatan kromosom dan perhitungan fitness cost.
3.3.2.1.Pembuatan Kromosom Dalam pembentukan kromosom, ada dua hal yang harus dihindari agar kromosom tersebut memiliki fitness cost yang bagus, yaitu: a. Dosen bentrok terhadap jadwal yang sama. Hal ini terjadi bila pada tanggal yang sama dan sesi yang sama, seorang dosen ditugaskan pada dua atau
35 lebih ruang parallel. Kondisi ini tidak dapat ditoleransi sehingga kromosom yang memiliki kondisi seperti ini dianggap tidak valid (semua fitness cost diberi nilai nol). b. Dosen dijadwalkan pada tanggal dan sesi dimana dosen tersebut berhalangan. Kondisi ini masih dapat ditoleransi, namun berakibat pada berkurangnya fitness cost. Dalam pengembangan software ini, jumlah kromosom yang ada dalam populasi sebanyak 2 buah. Cara penyusunan tiap kromosom tersebut adalah : a. Kromosom dengan index nol disusun berdasarkan NIM ascending b. Kromosom dengan index satu disusun berdasarkan NIM descending Pengisian seperti ini bertujuan untuk menghasilkan susunan gen yang berbeda antara kromosom yang satu dengan yang lain. Untuk mendapatkan kromosom dengan fitness cost dengan kompetensi bagus, pengisian dilakukan dengan memperhatikan susunan keempat dosen.
3.3.2.2. Fitness Cost Sebelum menghitung fitness cost, perlu dilakukan penyusunan prioritas, dimana prioritas yang lebih tinggi lebih diutamakan dalam proses seleksi. Urutan prioritas dalam software ini dapat dijelaskan sebagai berikut: a. Prioritas pertama yaitu jadwal berhalangan seorang dosen terhadap jadwal sidang. Jadwal sidang yang diberikan kepada seorang dosen diharapkan tidak bertepatan dengan jadwal berhalangan dosen tersebut, terutama untuk dosen
36 pembimbing dan ketua penguji. Bila seorang dosen tidak berhalangan maka fitness cost didapat dengan mengalikan nilai boolean hadir sebuah nilai tertentu yang dinamakan Koefisien Jadwal. Nilai tersebut dapat dilihat pada Tabel 3.16. Tabel 3.16. Koefisien Jadwal untuk Dosen Dosen Tidak Berhalangan
Koefisien Jadwal (J)
Ketua Penguji (KU)
6
Penguji (U)
4
Dengan menggunakan nilai pada Tabel 3.16., rumus untuk menghitung fitness cost jadwal dapat didefinisikan sebagai berikut : FCjadwal = (JKU X KU) + (JU X U) dimana KU, dan U bernilai 1 jika dosen bisa hadir dan 0 bila dosen berhalangan hadir. Sebagai contoh, misalkan sebuah gen G memiliki dosen KU, U, dengan kondisi dosen U berhalangan hadir dalam sidang. Maka fitness cost dari gen tersebut dapat dihitung sebagai berikut : FCJadwal = (6 x 1) + (4 x 0) = 6 Fitness cost ini memiliki nilai maksimal 10 yang berarti semua dosen bisa hadir dalam sidang. b. Prioritas kedua adalah penentuan dosen yang menguji sebuah tugas akhir. Dosen yang menguji sebuah tugas akhir diharapkan mengerti dan memahami topik dari tugas akhir tersebut. Nilai yang digunakan untuk menghitung fitness cost ini adalah relasi_val dari Tabel GN_trrelasiDP yang merupakan tingkat kompetensi dari dosen. Ketua penguji mendapatkan bobot (K) yang lebih tinggi daripada
37 anggota penguji, sehingga nilai ketua penguji dikalikan 5, sedangkan nilai anggota
penguji dikalikan 2. Rumus untuk menghitung fitness cost kompetensi
dapat didefinisikan sebagai berikut : FCKompetensi = (KKU x NKU) + (KU x NU) dimana N adalah tingkat kompetensi dosen terhadap tugas akhir. Sebagai contoh, misalkan sebuah gen memiliki tingkat kompetensi ketua penguji sebesar 0.85, penguji sebesar sebesar 0.92. Fitness cost gen tersebut dapat dihitung sebagai berikut : FCKompetensi = (5 x 0.85) + (2 x 0.92) = 6.09
3.3.3. Proses Regenerasi Proses regenerasi adalah proses pembentukan kromosom-kromosom baru untuk menggantikan generasi lama dengan dengan tujuan mencari kromosom dengan nilai yang lebih baik. Proses regenerasi dilakukan dengan 2 cara, yaitu crossover, mutasi. Kedua cara ini tidak dilakukan sekaligus dalam setiap generasi, tetapi dilakukan proses pengacakan untuk memilih cara regenerasi untuk setiap generasi. Perbandingan crossover dan mutasi adalah 1:1.
3.3.3.1.Crossover Crossover dilakukan dengan memilih 2 kromosom, asalkan kedua kromosom tidak boleh sama, dan kemudian menukar sebagian gen dari kedua kromosom itu. Metode yang digunakan adalah two-point crossover. 2 buah posisi dipilih secara acak dan semua gen yang berada diantara 2 posisi tersebut ditukar. Setelah melakukan
38 penukaran gen, dilakukan penyesuaian gen-gen yang tidak di-crossover terhadap gengen baru tersebut. Penyesuaian ini dilakukan agar tidak ada nilai NIM yang sama diantara gen dalam 1 kromosom. Crossover hanya terjadi pada level mahasiswa. Contoh crossover : Kromosom 1 000
010
020
030
NIM1
NIM2
NIM3
NIM4
020
030
NIM5
NIM4
100
110
120
130
NIM5
NIM6
NIM7
100
110
120
130
NIM2
NIM6
NIM7
NIM3
Kromosom 2 000
010
NIM1
Misalkan posisi yang dipilih secara acak adalah gen dengan index [0,2,0] dan [1,1,0]. Hasil crossover dari kedua kromosom tersebut adalah : Kromosom 1 000
010
020
030
100
110
120
130
NIM1
NIM2
NIM5
NIM4
NIM2
NIM6
NIM6
NIM7
020
030
100
110
120
130
NIM3
NIM4
NIM5
NIM7
NIM3
Kromosom 2 000 NIM1
010
Penyesuaian yang terjadi pada kromosom 1 adalah : a. Gen [0,1,0] sama dengan gen [1,0,0], maka gen [0,1,0] mengambil nilai gen [1,0,0] sebelum di-crossover, yaitu nilai kosong.
39 Perubahan 1 : 000
010
NIM1
020
030
100
110
120
130
NIM5
NIM4
NIM2
NIM6
NIM6
NIM7
b. Gen [1,2,0] sama dengan gen [1,1,0], maka gen [1,2,0] mengambil nilai gen [1,1,0] sebelum di-crossover, yaitu NIM5. Perubahan 2 : 000
010
NIM1
020
030
100
110
120
130
NIM5
NIM4
NIM2
NIM6
NIM5
NIM7
c. Gen [1,2,0] yang mengalami penyesuaian ternyata sama dengan gen [0,2,0]. Karena gen [0,2,0] mengalam crossover, maka nilai gen [1,2,0] harus mengalami penyesuaian lagi, menjadi NIM3. Penyesuaian yang terjadi pada kromosom 2 adalah : a. Gen [1,3,0] sama dengan gen [0,2,0], maka gen [1,3,0] mengambil gen [0,2,0] sebelum di-crossover, yaitu NIM5. Perubahan 1 000
010
NIM1
020
030
NIM3
NIM4
100
110
120
130
NIM5
NIM7
NIM5
b. Gen [1,3,0] yang mengalami penyesuaian sama dengan gen [1,1,0]. Karena gen [1,1,0] mengalami crossover, maka gen [1,3,0] harus mengalami penyesuaian lagi, sehingga menjadi NIM6. Perubahan 2 000 NIM1
010
020
030
NIM3
NIM4
100
110
120
130
NIM5
NIM7
NIM6
40 c. Gen [1,0,0] memiliki nilai kosong. Karena nilai gen sebelum di-crossover tidak kosong dan gen tersebut tidak sama dengan gen-gen yang di-crossover, maka nilai yang hilang ini harus dicarikan tempat kosong dalam kromosom (Bila nilai gen sebelum di-crossover kosong, tidak perlu dilakukan penyesuaian). Perubahan 3 000
010
020
030
NIM1
NIM2
NIM3
NIM4
100
110
120
130
NIM5
NIM7
NIM3
Jadi setelah mengalami crossover, kedua kromosom tersebut menjadi : Kromosom 1 000
010
NIM1
020
030
100
110
120
130
NIM5
NIM4
NIM2
NIM6
NIM3
NIM7
100
110
120
130
NIM5
NIM7
NIM6
Kromosom 2 000
010
020
030
NIM1
NIM2
NIM3
NIM4
3.3.3.2.Mutasi Mutasi dilakukan dengan cara memilih dua gen secara random dari sebuah kromosom, dan kemudian ditukar nilainya. Mutasi dilakukan terhadap seluruh kromosom yang ada dalam satu generasi. Mutasi dapat terjadi pada dua level yaitu level mahasiswa dan level dosen. Pada level mahasiswa, mutasi menukar seluruh nilai gen (satu jadwal sidang) dari dua gen yang terpilih. Penukaran ini memungkinkan sebuah gen berpindah ke gen yang kosong. Dengan alasan inilah maka gen-gen yang kosong dipertahankan. Contoh mutasi pada level mahasiswa :
41 Kromosom awal : 000
010
020
030
NIM1
NIM2
NIM3
NIM4
100
110
120
130
NIM5
NIM6
NIM7
Misalkan dua gen yang dipilih secara random adalah gen dengan index [0,2,0] dan[1,2,0]. Hasil mutasi dari dua gen tersebut adalah : 000
010
020
030
NIM1
NIM2
NIM6
NIM4
100
110
120
130
NIM5
NIM3
NIM7
Bila dari kromosom awal, gen yang terpilih adalah [0,2,0] dan [1,0,0] yang kosong , maka hasil mutasi menjadi : 000
010
NIM1
NIM2
020
030
100
110
120
130
NIM4
NIM3
NIM5
NIM6
NIM7
Gen yang kosong sekarang berada pada [0,2,0]. Pada level dosen, mutasi dilakukan terhadap nilai dosen penguji dalam gen, baik itu ketua penguji, atau penguji. Gen-gen yang ditukar pada level ini harus merupakan gen yang sudah terisi. Hal ini dilakukan untuk menghindari kondisi yang tidak valid dimana dosen penguji ditempatkan pada gen yang tidak memiliki mahasiswa yang disidang. Contoh mutasi pada level dosen: Kromosom awal (yang ditulis hanya dosen penguji) : 000
001
010
011
AB
DE
AD
BH
100
101
110
CH
BD
111
Misalkan terjadi mutasi pada gen [0,0,1] dosen 1 dan gen [1,0,1] dosen 2, maka kromosom tersebut menjadi :
42 000
001
010
011
AB
HE
AD
BH
100
101
110
CD
BD
111
Pada level ini, kondisi dimana terjadi mutasi pada gen [0,0,1] dan [1,0,0] tidak mungkin terjadi karena sudah dilakukan pengecekan terhadap isi gen. Namun, kondisi tidak valid masih dapat terjadi seperti bila mutasi terjadi pada gen [0,0,1] dosen 1 dan gen [1,1,0] dosen 1. Hasil mutasi adalah sebagai berikut : 000
001
010
011
AB
BE
AD
BH
100
101
110
CH
DD
111
Gen [0,0,1] memiliki dosen B yang juga berada pada gen [0,0,0]. Indeks pertama dan kedua yang menyatakan tanggal dan sesi sidang yang sama namun pada ruang yang berbeda. Kondisi ini adalah kondisi yang tidak valid. Kondisi tidak valid lainnya terjadi juga pada gen [1,1,0] dimana pada gen tersebut Dosen D ditulis dua kali yang berarti pada tanggal, sesi, dan ruang yang sama, ada dua orang Dosen D. Kondisi-kondisi tidak valid ini juga dilihat terhadap dosen pembimbing, sehingga tidak ada dosen yang jadwal menguji dan membimbingnya bentrok ataupun berada dalam satu sidang sebagai pembimbing dan penguji.
3.3.3.3.Pengulangan Proses Regenerasi dan Seleksi (Proses Optimasi) Langkah terakhir adalah melakukan pengulangan proses regenerasi dan seleksi sebanyak input-an dari user. Proses pengulangan ini dapat terus dilakukan user sampai mendapat hasil optimal yang diinginkan.
43 3.4.
Rancangan Layar
3.4.1. Layar Pembuka
Judul Program
Penjelasan singkat mengenai program, dan langkahlangkah untuk memulai program
Tombol ke layar berikut
Gambar 3.2. Rancangan Layar Pembuka Seperti yang terlihat pada Gambar 3.2., layar pembuka hanyalah layar perkenalan saja, terdapat judul program, penjelasan singkat, dan terdapat tombol untuk memulai program.
44 3.4.2. Layar Langkah-1
Judul
Tombol ke Home
Input Tanggal Tombol ke langkah selanjutnya Tampilan data tanggal yang telah diinput
Gambar 3.3. Rancangan Layar Langkah-1. Seperti yang terlihat pada Gambar 3.3., yang akan di-input adalah tanggaltanggal yang akan dipakai untuk proses sidang tugas akhir. Tombol ke Home akan membawa kembali user ke layar pembuka.
45 3.4.3. Layar Langkah-2
Judul
Home
Input Sesi
Langkah sebelumnya Tombol ke langkah selanjutnya
Tampilan Data sesi yang telah diinput
Gambar 3.4. Rancangan Layar-2. Pada Layar-2 ini akan di-input banyak sesi yang akan dipakai dalam sidang tugas akhir.
46 3.4.4. Layar Langkah-3
Judul Home dan Langkahlangkah sebelumn ya
Input Kelas
Tombol ke langkah selanjutnya
Tampilan data kelas-kelas yang telah di-input
Gambar 3.5. Rancangan Layar Langkah-3 Pada Langkah-3 ini, user akan meng-input kelas-kelas mana saja yang akan digunakan untuk pelaksanaan sidang tugas akhir.
47 3.4.5. Layar Langkah-4
Judul
Home Dan langkahlangkah sebelumnya
Generate Jadwal
Tombol ke langkah selanjutnya
Jadwal yang tergenerate
Gambar 3.6. Rancangan Layar Langkah-4 Pada langkah-4 ini jadwal akan di-generate. Sebelum User bisa ke langkah selanjutnya, User harus memilih tombol generate jadwal.
48 3.4.6. Layar Langkah-5
Judul Home Dan langkahlangkah sebelumnya
Input Topik
Tombol ke langkah selanjutnya
Data Topik
Gambar 3.7. Rancangan Layar Langkah-5 Di Langkah-5 ini akan di-input topik-topik apa saja yang akan ditetapkan untuk tugas akhir.
49 3.4.7.
Layar Langkah-6
Judul
Inputan Dosen
Tampilan Data Dosen yang telah Diinput
Tombol ke Langkah Selanjutnya
Gambar 3.8. Rancangan Layar Langkah-6 Pada Langkah-6 ini, akan di-input data tentang dosen. Data ini akan terdiri dari, kompetensi dosen, jadwal bisa hadir sidang atau tidak.
50 3.4.8. Layar Langkah-7
Judul
Inputan Data Mahasiswa dan Proposalnya
Tampilan Data Mahasiswa dan Proposalnya
Tombol ke Langkah Selanjutnya
Gambar 3.9. Rancangan Layar Langkah-7 Pada Langkah-7 ini, akan di-input data tentang mahasiswa dan proposal yang akan disidang.
51 3.4.9. Layar Langkah-8 Judul
Tombol Proses Tombol Regenerasi
Hasil Dari Proses
Tombol untuk mengakhiri program
Gambar 3.10. Rancangan Layar Langkah-8 Pada Langkah-8 ini adalah halaman yang akan menampilkan hasil dari proses yang telah dilakukan, di langkah ini user bisa terus melakukan iterasi sampai mendapat hasil dengan fitness cost yang baik. Tombol proses melakukan proses regenerasi dan seleksi.
52 3.4.10. Layar Akhir
Judul
Restart
Kembali
Gambar 3.11. Rancangan Layar Akhir Pada langkah terakhir ini akan diminta konfirmasi apakah akan mengakhiri program ini atau kembali ke langkah-8 yang menghasilkan hasil proses.
3.5.
Perancangan Modul Di bawah ini adalah Pseudocode dari modul-modul yang ada :
3.5.1. Modul Home (Layar Pembuka) Mulai modul Home Pilih tombol ‘Langkah-1’ Tutup modul Home Panggil modul Langkah-1 Akhir dari modul Home
53 3.5.2. Modul Langkah-1 (Input Tanggal Sidang) Mulai modul Langkah-1 Buka database gene While tidak pilih tombol ‘Langkah-2’ Insert data tanggal ke tabel GN_mstanggal Tampilkan tanggal yang sudah diinput dari tabel GN_mstanggal If pilih tombol ‘Ubah’ Update data tanggal di tabel GN_mstanggal Pilih tombol ‘Langkah-2’ Tutup database gene Tutup modul Langkah-1 Panggil modul Langkah-2 Akhir modul Langkah-1
3.5.3. Modul Langkah-2(Input Banyak Sesi Sidang Setiap Harinya) Mulai modul Langkah-2 Buka database gene While tidak pilih tombol ‘Langkah-3’ Insert banyak sesi ke tabel GN_mssesi Tampilkan sesi yang telah diinput dari tabel GN_mssesi If pilih tombol ‘ubah’ Update banyak sesi di tabel GN_mssesi Pilih tombol ‘Langkah-3’
54 Tutup database gene Tutup modul Langkah-2 Panggil modul Langkah-3 Akhir modul Langkah-2
3.5.4. Modul Langkah-3 (Input Ruang Kelas Yang Dipakai Untuk Sidang) Mulai modul Langkah-3 Buka database gene While tidak pilih tombol ‘Langkah-4’ Insert data nama kelas ke tabel GN_mskelas Tampilkan data nama kelas yang telah diinput dari tabel GN_mskelas If pilih tombol ‘Ubah’ Update data nama kelas pada tabel GN_mskelas Pilih tombol ‘Langkah-4’ Tutup database gene Tutup modul Langkah-3 Panggil modul Langkah-4 Akhir modul Langkah-3
3.5.5. Modul Langkah-4 (Encoding Gen Jadwal) Mulai modul Langkah-4 Buka database gene Pilih tombol ‘Generate Jadwal’
55 i = tanggal_id dari tabel GN_mstanggal j = sesi_id dari tabel GN_mssesi k = kelas_id dari tabel GN_mskelas For i =1 sampai jumlah tanggal; i++ For j = 1 sampai jumlah sesi;j++ For k =1 sampai jumlah kelas; k++ Insert (i,j,k) ke tabel GN_msjadwal Tampilkan jadwal dari tabel GN_msjadwal Pilih tombol ‘Langkah-5’ Tutup modul Langkah-4 Panggil modul Langkah-5 Akhir modul Langkah-4
3.5.6. Modul Langkah-5 (Input Topik Yang Ditentukan Untuk Skripsi) Mulai modul Langkah-5 Buka database gene While tidak pilih tombol ‘Langkah-6’ Insert nama topik ke tabel GN_mstopik Tampilkan nama topik yang telah diinput dari tabel GN_mstopik If pilih tombol ‘Ubah’ Update data nama topik pada tabel GN_mstopik Pilih tombol ‘Langkah-6’ Tutup database gene
56 Tutup modul Langkah-5 Panggil modul Langkah-6 Akhir modul Langkah-5
3.5.7. Modul Langkah-6 (Input Data Dosen) Mulai modul Langkah-6 Buka database gene While tidak pilih tombol ‘Langkah-7’ Insert nama dosen ke tabel GN_msdosen Insert nilai relasi ke tabel GN_trrelasiDT Insert nilai berhalangan dosen pada setiap tanggal dan sesi sidang ke tabel GN_trberhalangan If pilih tombol ‘Modify’ Update nama dosen, nilai relasi, dan nilai berhalangan Pilih tombol ‘Langkah-7’ Tutup database gene Tutup modul Langkah-6 Panggil modul Langkah-7 Akhir modul Langkah-6
3.5.8. Modul Langkah-7 (Input Data Mahasiswa) Mulai modul Langkah-7 Buka database gene
57 While tidak pilih tombol ‘Langkah-8’ Insert
proposal_nim,
proposal_mahasiswa,
nama
proposal,
pembimbing_1, dan pembimbing_2 ke tabel GN_msproposal Insert nilai relasi proposal terhadap setiap topik ke tabel GN_trrelasiPT If pilih tombol ‘Modify’ Update tabel GN_msproposal dan GN_trrelasi Pilih tombol ‘Langkah-8’ Tutup database gene Tutup modul Langkah-7 Panggil modul Langkah-8 Akhir modul Langkah-7
3.5.9. Modul Langkah-8 Mulai modul Langkah-8 Buka database gene Lakukan pilihan tombol sesuai urutan Pilih tombol ‘Hitung Kompetensi’ Panggil modul Hitung Kompetensi Pilih tombol ‘Generate Proporsi’ Panggil modul Generate Proporsi Pilih tombol ‘Generate Chromosome’ Panggil modul Generate Chromosome Tampilkan hasil penjadwalan sementara
58 Pilih tombol ‘Regenerasi’ Panggil modul Regenerasi Tampilkan hasil penjadwalan setelah optimasi Pilih tombol ‘Hapus Data dan Ulang’ If pilih tombol ‘Restart’ Hapus semua isi dalam tabel-tabel pada database gene Tutup database gene Panggil modul Home If pilih tombol ‘Kembali’ Panggil modul Langkah-8 Akhir modul Langkah-8
3.5.10. Modul Hitung Kompetensi Mulai modul Hitung Kompetensi Ambil semua data dari tabel GN_trrelasiDT Ambil semua data dari tabel GN_trrelasi PT Set P = Jumlah dari relasi proposal topik dari table GN_trrelasiPT Untuk setiap relasi proposal-topik { DP = nilai minimum dari relasi dosen-topik(i) dan relasi proposal-topik Relasi dosen-proposal = DP/P
59 Insert data ke tabel GN_trrelasiDP } Akhir modul Hitung Kompetensi
3.5.11. Modul Generate Proporsi Mulai modul Generate Proporsi Ambil semua data dosen dari tabel GN_msdosen Ambil semua data berhalangan dosen dari tabel GN_trberhalangan Ambil semua data proposal dari tabel GN_msproposal Ambil semua data relasi proposal dengan topik dari table GN_trrelasiDP Untuk setiap proposal { If dosen penguji proposal tidak sama dengan dosen pembimbing : Pasangkan dosen penguji pada proposal Random pilih ketua penguji dari 2 dosen penguji Hitung Fitness Cost (kompetensi) penguji = 5*kompetensi ketua penguji + 2*anggota penguji Insert data ke tabel GN_trproporsi } Akhir modul Generate Proporsi
3.5.12. Modul Generate Chromosome Mulai modul Generate Chromosome
60 Ambil semua data dari tabel GN_msjadwal Ambil semua data dari tabel GN_trproporsi Untuk membuat Chromosome index[0] Pasangkan data proporsi dan data jadwal dengan NIM ascending Ulangi untuk setiap nilai proporsi (NIM tidak boleh sama) Hitung Fitnesscost jadwal = 6*nilai hadir (Boolean) ketua penguji + 4*nilai hadir dosen penguji Untuk membuat Chromosome index[1] Pasangkan data proporsi dan data jadwal dengan NIM descending Ulangi untuk setiap nilai proporsi (NIM tidak boleh sama) Hitung Fitnesscost jadwal = 6*nilai hadir (Boolean) ketua penguji + 4*nilai hadir dosen penguji Akhir modul Generate Chromosome
3.5.13. Modul Regenerasi Mulai modul Regenerasi Set x = Random(3) If x = = 0 Panggil modul Mutasi Mahasiswa If x = = 1 Panggil modul Mutasi Dosen If x = = 2 Panggil modul Crossover
61 Akhir modul Regenerasi
3.5.14. Modul Mutasi Mahasiswa Mulai modul Mutasi Mahasiswa Pilih random 2 gen dari Chromosome yang punya best fitnesscost Tukar NIM mahasiswa pada 2 gen tersebut Untuk setiap gen Hitung Fitnesscost jadwal gen Hitung Fitnesscost kompetensi gen Tampilkan Fitnesscost minimum sebagai Fitnesscost kromosom Akhir modul Mutasi Mahasiswa
3.5.15. Modul Mutasi Dosen Mulai modul Mutasi Dosen Pilih random 2 gen dari Chromosome yang punya best fitnesscost Tukar dosen random pada 2 gen tersebut Untuk setiap gen Hitung Fitnesscost jadwal gen Hitung Fitnesscost kompetensi gen Tampilkan Fitnesscost minimum sebagai Fitnesscost kromosom Akhir modul Mutasi Dosen 3.5.16. Modul Crossover Mulai modul Crossover
62 Pilih random 2 nomor index gen jadwal I = no index gen jadwal yang lebih kecil J = no index gen jadwal yang lebih besar For I to J Tukar semua proporsi dalam gen Chromosome[0] dan Chromosome[1] If isi gen dalam 1 Chromosome ada yang sama If gen itu yang tidak mengalami crossover Tukar isi gen itu dengan isi gen sebelum dicrossover Untuk semua gen Hitung Fitnesscost jadwal Hitung Fitnesscost kompetensi Tampilkan Fitnesscost minimum sebagai Fitnesscost kromosom Akhir modul Crossover