Contoh Penggunaan Algoritma Genetika dan NEH
Mata Kuliah Tawar Program Studi Teknik Informatika Kode_mk TKC108 TKC108 TKC118 TKC104 TKC104 TKC104 TKC104 TKC122 TKC122 TKC122 TKC122 TKC126 TKC126 TKC126 TKC264 TKC264 TKC264
Mata Kuliah Aljabar Linear Aljabar Linear Aljabar Linear Struktur Data Struktur Data Struktur Data Struktur Data Riset Operasi Riset Operasi Riset Operasi Riset Operasi Sistem Operasi Sistem Operasi Sistem Operasi Basis Data II Basis Data II Basis Data II
SKS 3 3 3 2 2 2 2 3 3 3 3 3 3 3 3 3 3
Semester 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4
Kelas A B C A B C D A B C D A B C A B C
Dosen Pengampu Mula'ab, S.Si., M.Kom Miftahul Ulum, ST., MT Dwi Kuswanto, S.Pd., MT Kurniawan Eka Permana, S.Kom., M.Sc Kurniawan Eka Permana, S.Kom., M.Sc Abdullah Basuki Rahmat, S.Si., MT Abdullah Basuki Rahmat, S.Si., MT Abdullah Basuki Rahmat, S.Si., MT Eza Rahmanita, ST., MT Eza Rahmanita, ST., MT Abdullah Basuki Rahmat, S.Si., MT Hermawan, ST., M,Kom Hermawan, ST., M,Kom Aeri Rahmad, ST., MT Noor Ifada, ST., MISD Kurniawan Eka Permana, S.Kom., M.Sc Noor Ifada, ST., MISD
Mata Kuliah Tawar Program Studi D3 Manajemen Informatika id M18 M19 M20 M21 M22 M23 M24 M25 M26 M27 M28 M29 M30 M31 M32 M33 M34
Kode_mk TKD111 TKD111 TKD111 TKD112 TKD112 TKD114 TKD114 TKD134 TKD134 TKD134 TKD179 TKD179 TKD179 TKD155 TKD155 TKD163 TKD163
Mata Kuliah Struktur Data Struktur Data Struktur Data Aljabar Linier Aljabar Linier ArOrKom ArOrKom Jarkom Jarkom Jarkom Basdat 1 Basdat 1 Basdat 1 Metnum Metnum SPK SPK
SKS Semester Kelas Dosen Pengampu 3 2 A Fitri Damayanti, S.Kom., M.Kom. 3 2 B Fitri Damayanti, S.Kom., M.Kom. 3 2 C Fitri Damayanti, S.Kom., M.Kom. 2 2 A Achmad Ubaidillah Ms., ST., MT. 2 2 B Achmad Ubaidillah Ms., ST., MT. 2 2 A Budi Dwi Satoto, ST., M.Kom. 2 2 B Meidya Koeshardianto, S.Si., MT. 2 4 A Budi Dwi Satoto, ST., M.Kom. 2 4 B Budi Dwi Satoto, ST., M.Kom. 2 4 C Budi Dwi Satoto, ST., M.Kom. 3 2 A Yeni Kustiyahningsih, S.Kom., M.Kom. 3 2 B Yeni Kustiyahningsih, S.Kom., M.Kom. 3 2 C Yeni Kustiyahningsih, S.Kom., M.Kom. 3 4 A Achmad Ubaidillah Ms., ST., MT. 3 4 B Dwi Kuswanto, S.Pd., MT. 3 4 A Firli Irhamni, ST., M.Kom. 3 4 B Firli Irhamni, ST., M.Kom.
Sebelum membuat kromosom, data yang akan dijadikan kromosom di inisialisasikan dulu. Contoh ini yang di inisialisasikan yaitu daftar mata kuliah dengan kolom “id”, daftar hari dengan kolom “id_hari”, dan jam dengan kolom “shift”. Inisialisasi kromosomnya sebagai berikut: Inisialisasi Kromosom Tabel Matakuliah Id M1 M2 M3 M4
Kode_mk Mata Kuliah TKC108 Aljabar Linear TKC108 Aljabar Linear TKC118 Aljabar Linear
SKS 3 3 3
Semester 2 2 2
Kelas A B C
TKC104
Struktur Data
2
2
A
TKC104
Struktur Data
2
2
B
TKC104
Struktur Data
2
2
C
TKC104
Struktur Data
2
2
D
TKC122
Riset Operasi
3
4
A
M9 M10 M11
TKC122 TKC122
Riset Operasi Riset Operasi
3 3
4 4
B C
TKC122
Riset Operasi
3
4
D
M12 M13 M14 M15 M16
TKC126 TKC126 TKC126 TKC264
Sistem Operasi Sistem Operasi Sistem Operasi Basis Data II
3 3 3 3
4 4 4 4
A B C A
TKC264
Basis Data II
3
4
B
M17
TKC264
Basis Data II
3
4
C
id M18 M19 M20 M21 M22 M23 M24 M25 M26 M27 M28
Kode_mk TKD111 TKD111 TKD111 TKD112 TKD112 TKD114 TKD114 TKD134 TKD134 TKD134
M5 M6 M7 M8
M29 M30
Mata Kuliah Struktur Data Struktur Data Struktur Data Aljabar Linier Aljabar Linier ArOrKom ArOrKom Jarkom Jarkom Jarkom
SKS 3 3 3 2 2 2 2 2 2 2
TKD179
Basdat 1
3
TKD179
Basdat 1
3
TKD179
Basdat 1
3
Dosen Pengampu Mula'ab, S.Si., M.Kom Miftahul Ulum, ST., MT Dwi Kuswanto, S.Pd., MT Kurniawan Eka Permana, S.Kom., M.Sc Kurniawan Eka Permana, S.Kom., M.Sc Abdullah Basuki Rahmat, S.Si., MT Abdullah Basuki Rahmat, S.Si., MT Abdullah Basuki Rahmat, S.Si., MT Eza Rahmanita, ST., MT Eza Rahmanita, ST., MT Abdullah Basuki Rahmat, S.Si., MT Hermawan, ST., M,Kom Hermawan, ST., M,Kom Aeri Rahmad, ST., MT Noor Ifada, ST., MISD Kurniawan Eka Permana, S.Kom., M.Sc Noor Ifada, ST., MISD
Semester Kelas Dosen Pengampu 2 A Fitri Damayanti, S.Kom., M.Kom. 2 B Fitri Damayanti, S.Kom., M.Kom. 2 C Fitri Damayanti, S.Kom., M.Kom. 2 A Achmad Ubaidillah Ms., ST., MT. 2 B Achmad Ubaidillah Ms., ST., MT. 2 A Budi Dwi Satoto, ST., M.Kom. 2 B Meidya Koeshardianto, S.Si., MT. 4 A Budi Dwi Satoto, ST., M.Kom. 4 B Budi Dwi Satoto, ST., M.Kom. 4 C Budi Dwi Satoto, ST., M.Kom. Yeni Kustiyahningsih, S.Kom., 2 A M.Kom. Yeni Kustiyahningsih, S.Kom., 2 B M.Kom. Yeni Kustiyahningsih, S.Kom., 2 C M.Kom.
Ruang RKB A101 RKB A102 RKB A103 RKB A104 RKB A105 RKB A101 RKB A102 RKB A103 RKB A104 RKB A105 RKB A101 RKB A102 RKB A103 RKB A104 RKB A105 RKB A101 RKB A102
Ruang RKB B101 RKB B102 RKB B101 RKB B102 RKB B101 RKB B102 RKB B101 RKB B102 RKB B101 RKB B102 RKB B101 RKB B102 RKB B101
M31 M32 M33 M34
TKD155 TKD155 TKD163 TKD163
Metnum Metnum SPK SPK
3 3 3 3
4 4 4 4
A B A B
Achmad Ubaidillah Ms., ST., MT. Dwi Kuswanto, S.Pd., MT. Firli Irhamni, ST., M.Kom. Firli Irhamni, ST., M.Kom.
Tabel Hari Perkuliahan dari hari Senin sampai Kamis id_hari 1 2 3 4
Hari Senin Selasa Rabu Kamis
Tabel Jam 1 SKS= 50 Menit Shif(jam ke-n)
Jam awal
1
07.00
2
Jam ke…n
3
Jam ke…n
4
Jam ke…n
5
Jam ke…n
Jam Akhir Jika sks=1 maka durasi 50 menit Jika sks=2 maka durasi 100 menit Jika sks=3 maka durasi 150 menit Jika sks=1 maka durasi 50 menit Jika sks=2 maka durasi 100 menit Jika sks=3 maka durasi 150 menit Jika sks=1 maka durasi 50 menit Jika sks=2 maka durasi 100 menit Jika sks=3 maka durasi 150 menit Jika sks=1 maka durasi 50 menit Jika sks=2 maka durasi 100 menit Jika sks=3 maka durasi 150 menit Jika sks=1 maka durasi 50 menit Jika sks=2 maka durasi 100 menit Jika sks=3 maka durasi 150 menit
RKB B102 RKB B101 RKB B102 RKB B101
Tahap 1. Pembentukan Kromosom berdasarkan data diatas: id M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 M12 M13 M14 M15 M16 M17 M18 M19 M20 M21 M22 M23 M24 M25 M26 M27 M28
Kode_mk TKC108 TKC108 TKC118 TKC104 TKC104 TKC104 TKC104 TKC122 TKC122 TKC122 TKC122 TKC126 TKC126 TKC126 TKC264 TKC264 TKC264 TKD111 TKD111 TKD111 TKD112 TKD112 TKD114 TKD114 TKD134 TKD134 TKD134 TKD179
Mata Kuliah Aljabar Linear Aljabar Linear Aljabar Linear Struktur Data Struktur Data Struktur Data Struktur Data Riset Operasi Riset Operasi Riset Operasi Riset Operasi Sistem Operasi Sistem Operasi Sistem Operasi Basis Data II Basis Data II Basis Data II Struktur Data Struktur Data Struktur Data Aljabar Linier Aljabar Linier ArOrKom ArOrKom Jarkom Jarkom Jarkom Basdat 1
SKS 3 3 3 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 3
Kelas A B C A B C D A B C D A B C A B C A B C A B A B A B C A
Dosen Pengampu Mula'ab, S.Si., M.Kom Miftahul Ulum, ST., MT Dwi Kuswanto, S.Pd., MT Kurniawan Eka Permana, S.Kom., M.Sc Kurniawan Eka Permana, S.Kom., M.Sc Abdullah Basuki Rahmat, S.Si., MT Abdullah Basuki Rahmat, S.Si., MT Abdullah Basuki Rahmat, S.Si., MT Eza Rahmanita, ST., MT Eza Rahmanita, ST., MT Abdullah Basuki Rahmat, S.Si., MT Hermawan, ST., M,Kom Hermawan, ST., M,Kom Aeri Rahmad, ST., MT Noor Ifada, ST., MISD Kurniawan Eka Permana, S.Kom., M.Sc Noor Ifada, ST., MISD Fitri Damayanti, S.Kom., M.Kom. Fitri Damayanti, S.Kom., M.Kom. Fitri Damayanti, S.Kom., M.Kom. Achmad Ubaidillah Ms., ST., MT. Achmad Ubaidillah Ms., ST., MT. Budi Dwi Satoto, ST., M.Kom. Meidya Koeshardianto, S.Si., MT. Budi Dwi Satoto, ST., M.Kom. Budi Dwi Satoto, ST., M.Kom. Budi Dwi Satoto, ST., M.Kom. Yeni Kustiyahningsih, S.Kom., M.Kom.
Ruang RKB A101 RKB A102 RKB A103 RKB A104 RKB A105 RKB A101 RKB A102 RKB A103 RKB A104 RKB A105 RKB A101 RKB A102 RKB A103 RKB A104 RKB A105 RKB A101 RKB A102 RKB B101 RKB B102 RKB B101 RKB B102 RKB B101 RKB B102 RKB B101 RKB B102 RKB B101 RKB B102 RKB B101
id_hari 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
shift 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3
M29 M30 M31 M32 M33 M34
TKD179 TKD179 TKD155 TKD155 TKD163 TKD163
Basdat 1 Basdat 1 Metnum Metnum SPK SPK
3 3 3 3 3 3
B C A B A B
Yeni Kustiyahningsih, S.Kom., M.Kom. Yeni Kustiyahningsih, S.Kom., M.Kom. Achmad Ubaidillah Ms., ST., MT. Dwi Kuswanto, S.Pd., MT. Firli Irhamni, ST., M.Kom. Firli Irhamni, ST., M.Kom.
RKB B102 RKB B101 RKB B102 RKB B101 RKB B102 RKB B101
1 2 3 4 1 2
4 5 1 2 3 4
Keterangan: Kolom id menampung data seperti kode_mk, mk, sks, semester, kelas, dosen, ruang. Kolom id_hari menampung data hari yang digunakan untuk perkuliahan seperti, 1=senin, 2=selasa, 3=rabu, 4, kamis Kolom Shift untuk menampung jam ke berapa matakuliah itu di jadwalkan. Pembentukan kromosom diatas dilakukan dengan acak, yang diacak yaitu pada kolom id, id_hari, dan shift. Sehingga itu adalah sebagai populasi awal.
Tahap 2. Membuat Nilai Fitness Kromosom Rumus mencari nilai fitness:
Tujuan mencari nilai fitness adalah seberapa baik kromosom tersebut. Adapun pelanggaran (Penalty) yang mempengaruhi nilai Fitness pada suatu kromosom adalah: 1. Dalam satu waktu dosen tidak boleh mengajar di dua tempat. 2. Ruangan tidak boleh digunakan lebih dari satu matakuliah pada waktu yang sama. Satu Penalty/pelanggaran tersebut bernilai 1. Apabila nilai penalty besar maka nilai fitness yang dihasilkan kecil, sebaliknya jika nilai penalty kecil maka nilai fitness yang dihasilkan besar. Jika suatu kromosom tidak melakukan penalty maka nilai fitnessnya akan bernilai 1, maka kromosom inilah yang menjadi kromosom terbaik.
Tahap 3. Proses NEH Merupakan metode yang dikolaborasikan dengan algoritma genetika. Langkah-langkah: Setelah koromosom mendapatkan nilai fitness, nilai fitness yang kecil dipisah sehingga nilai fitness yang kecil tu diurutkan secara descending.
Tahap 4. Seleksi Kromosom Kemudian nilai fitness yang kecil diseleksi menggunakan metode Roulete Whell Contoh Langkah-langkah Metode Roulette Whell: a. Hitung total fitness (F) seluruh kromosom dalam populasi TF= K13+K16+K3+K6+K8+K10+K14+K15+K18+K19 TF = 0.5 + 0.5 + 0.33 + 0.33 + 0.33 + 0.5 + 0.33 + 0.33 + 0.5 + 0.33 = 3.98 b. Hitung probabilitas seleksi (pk) setiap kromosom Pk1 = 0.5/3.98 = 0.126 Pk2 = 0.5/3.98 = 0.126 Pk3 = 0.33/3.98 = 0.082 Pk4 = 0.33/3.98 = 0.082
Pk5 = 0.33/3.98 = 0.082 Pk6 = 0.5/3.98 = 0.126 Pk7 = 0.33/3.98 = 0.082 Pk8 = 0.33/3.98 = 0.082 Pk9 = 0.5/3.98 = 0.126 Pk10 = 0.33/3.98 = 0.082 c. Hitung probabilitas kumulatif (qk) setiap kromosom q1 = p1 = 0.126 q2 = q1 + p2 = 0.126 + 0.126 = 0.252 q3 = q2 + p3 = 0.252 + 0.082 = 0.334 q4 = q3 + p4 = 0.334 + 0.082 = 0.416 q5 = q4 + p5 = 0.416 + 0.082 = 0.498 q6 = q5 + p6 = 0.498 + 0.126 = 0.624 q7 = q6 + p7 = 0.624 + 0.082 = 0.706 q8 = q7 + p8 = 0.706 + 0.082 = 0.788 q9 = q8 + p9 = 0.788 + 0.126 = 0.914 q10 = q9 + p10 = 0.914 + 0.082 = 0.996 d. Buat bilangan random acak untuk memilih kromosom induk sebanyak jumlah kromosom. r1= 0.504 r2= 0.024 r3= 0.498 r4= 0.198 r5= 0.523 r6= 0.231 r7= 0.729 r8= 0.878 r9= 0.424 r10= 0.162
r1= 0.504 maka kromosom K14 terpilih karena q7 > 0.504 r2= 0.024 maka kromosom K6 terpilih karena q3 > 0.024 r3= 0.498 maka kromosom K13 terpilih karena q6 > 0.498 r4= 0.198 maka kromosom K6 terpilih karena q3 > 0.198 r5= 0.523 maka kromosom K14 terpilih karena q7 > 0.523 r6= 0.131 maka kromosom K3 terpilih karena q2 > 0.131 r7= 0.729 maka kromosom K16 terpilih karena q9 > 0.729 r8= 0.878 maka kromosom K18 terpilih karena q11 > 0.878 r9= 0.424 maka kromosom K13 terpilih karena q6 > 0.424 r10= 0.162 maka kromosom K3 terpilih karena q2 > 0.162
Tahap 5. Crossover pada kromosom Cara Kerja crossover: a. Pilih secara acak dua kromosom yang akan dijadikan kromosom induk. b. Pilih secara acak posisi gen yang akan dikawin silangkan dari kromosom induk. c. Lakukan crossover dengan menempatkan gen pertama populasi induk pertama, kemudian menukarkan gen dengan yang ada pada populasi kedua. Contoh:
Gambar 4.2 Contoh Crossover
Maka setelah dilakukannya proses kawin silang (Crossover) dari kedua kromosom induk (parents) yang terpilih, maka akan menghasilkan kromosom anak (offspring). Tahap 6. Mutasi pada Kromosom Cara Kerja mutasi: a. Pilih acak kromosom yang akan dimutasi. b. Tentukan dua atau lebih gen yang akan dimutasi pada kromosom. c. Cari posisi gen-gen yang terpilih kemudian merubah bit-bitnya.
Contoh:
Gambar 4.3 Contoh Mutasi
Karena proses mutasi juga merupakan salah satu operator dasar dalam algoritma genetika, sehingga sama dengan crossover, mutasi juga memerlukan probabilitas dengan proses yang sama seperti probabilitas crossover. Individu dengan nilai probabilitas lebih kecil dari probabilitas yang telah ditentukan yang akan melewati proses mutasi. Kondisi Selesai Terdapat tiga kondisi selesai yang dapat menghentikan proses algoritma pemograman ini,yaitu: 1. Jika setelah beberapa generasi berturut-turut nilai fitness terbaik dari populasi tidak mengalami perubahan kembali. 2. Jika jumlah generasi maksimum telah tercapai. 3. Jika nilai fitness terbaik minimal telah tercapai.
