Algoritma Genetika: Contoh Penjadwalan Kuliah

Algoritma Genetika adalah metode optimasi berbasis populasi yang meniru proses evolusi melalui seleksi, crossover, dan mutasi. Pada kasus penjadwalan kuliah, setiap solusi jadwal direpresentasikan sebagai kromosom, kemudian dievaluasi menggunakan fungsi fitness berdasarkan jumlah konflik yang terjadi.

Tutorial ini menggunakan contoh sederhana penjadwalan 4 mata kuliah, 3 dosen, 2 ruang, dan 3 kombinasi hari-jam. Tujuannya adalah mencari jadwal tanpa bentrok dosen, tanpa bentrok ruang, dan tetap memenuhi kapasitas ruang.

Untuk membandingkan pendekatan optimasi lain, lihat juga Hill Climbing dan metode Simpleks.

---

Daftar Isi

• Pengertian Algoritma Genetika
• Mengapa Algoritma Genetika Cocok untuk Penjadwalan
• Istilah Penting
• Representasi Masalah
• Fungsi Fitness dan Penalti
• Tahapan Algoritma Genetika
• Contoh Perhitungan Manual
  • #01 Menentukan Data Mata Kuliah
  • #02 Menentukan Slot Jadwal
  • #03 Membentuk Kromosom
  • #04 Menentukan Aturan Konflik
  • #05 Membentuk Populasi Awal
  • #06 Menghitung Fitness
  • #07 Melakukan Seleksi
  • #08 Melakukan Crossover
  • #09 Melakukan Mutasi
  • #10 Membentuk Generasi Baru
  • #11 Menentukan Jadwal Terbaik
• Pseudocode
• Parameter Penting
• Kelebihan dan Kekurangan
• Kesalahan Umum
• Ringkasan
• FAQ
• Referensi
• Source Code

---

Pengertian Algoritma Genetika

Algoritma Genetika atau Genetic Algorithm (GA) adalah algoritma optimasi yang bekerja dengan sekumpulan kandidat solusi yang disebut populasi.

Setiap kandidat solusi direpresentasikan sebagai kromosom. Kromosom dengan kualitas lebih baik memiliki peluang lebih besar untuk dipertahankan atau digunakan sebagai parent dalam pembentukan generasi berikutnya.

Siklus dasarnya:

Populasi Awal
↓
Evaluasi Fitness
↓
Seleksi Parent
↓
Crossover
↓
Mutasi
↓
Evaluasi Offspring
↓
Generasi Baru
↓
Ulangi sampai kondisi berhenti

Pada kasus penjadwalan, satu kromosom dapat merepresentasikan satu jadwal lengkap.

---

Mengapa Algoritma Genetika Cocok untuk Penjadwalan

Masalah penjadwalan kuliah memiliki banyak kemungkinan kombinasi.

Misalnya suatu jadwal harus mempertimbangkan:

• mata kuliah,
• dosen,
• hari,
• jam,
• ruang,
• kapasitas ruang,
• dan aturan bentrok.

Semakin banyak mata kuliah dan slot yang tersedia, semakin besar ruang pencarian solusi.

Algoritma Genetika tidak memeriksa seluruh kemungkinan satu per satu. GA mencari solusi melalui proses evolusi dari beberapa kandidat jadwal.

Pada implementasi nyata, aturan penjadwalan dapat dibagi menjadi:

• hard constraint, yaitu aturan yang tidak boleh dilanggar;
• soft constraint, yaitu preferensi yang sebaiknya dipenuhi.

Tutorial ini fokus pada hard constraint agar contoh perhitungan manual tetap mudah diikuti.

---

Istilah Penting

---

Representasi Masalah

Pada contoh ini, satu gene merepresentasikan slot jadwal untuk satu mata kuliah.

Urutan gene selalu:

[M1, M2, M3, M4]

Artinya:

• gene ke-1 = jadwal M1,
• gene ke-2 = jadwal M2,
• gene ke-3 = jadwal M3,
• gene ke-4 = jadwal M4.

Contoh:

[S1, S3, S4, S5]

berarti:

M1 → S1
M2 → S3
M3 → S4
M4 → S5

---

Fungsi Fitness dan Penalti

Pada contoh ini digunakan tiga jenis pelanggaran:

1. dosen mengajar dua mata kuliah pada waktu yang sama;
2. dua mata kuliah menggunakan ruang yang sama pada waktu yang sama;
3. kapasitas ruang lebih kecil daripada jumlah mahasiswa.

Setiap pelanggaran diberi penalti:

Total penalti:

Fitness:

Jika tidak ada pelanggaran:

maka:

Semakin kecil penalti, semakin besar fitness.

---

Tahapan Algoritma Genetika

Tahapan yang digunakan:

1. menentukan data mata kuliah;
2. menentukan daftar slot;
3. menentukan representasi kromosom;
4. membentuk populasi awal;
5. menghitung penalti;
6. menghitung fitness;
7. melakukan seleksi;
8. melakukan crossover;
9. melakukan mutasi;
10. membentuk generasi baru;
11. mengulangi proses sampai kondisi berhenti.

---

Contoh Perhitungan Manual

Contoh dibuat sederhana agar seluruh proses dapat diperiksa secara manual.

---

#01 Menentukan Data Mata Kuliah

Digunakan empat mata kuliah.

Perhatikan bahwa:

M1 dan M3 diajar oleh dosen D1

Karena itu M1 dan M3 tidak boleh berada pada waktu yang sama.

---

#02 Menentukan Slot Jadwal

Tersedia dua ruang:

Tersedia tiga waktu:

Senin 08.00
Senin 10.00
Selasa 08.00

Kombinasi waktu dan ruang diberi kode:

Dari kapasitas ruang:

M1 = 35 mahasiswa → tidak boleh di R2
M4 = 40 mahasiswa → tidak boleh di R2

M2 dan M3 masih dapat menggunakan R1 maupun R2.

---

#03 Membentuk Kromosom

Urutan mata kuliah pada kromosom:

[M1, M2, M3, M4]

Contoh kromosom:

[S1, S3, S4, S5]

Interpretasinya:

Jika diterjemahkan:

Jadwal ini tidak memiliki konflik.

---

#04 Menentukan Aturan Konflik

Digunakan tiga hard constraint.

Konflik Dosen

Jika dosen yang sama mengajar dua mata kuliah pada waktu yang sama:

penalti +1

Contoh:

M1 → Senin 08.00
M3 → Senin 08.00

Karena keduanya diajar D1:

penalti dosen = 1

Konflik Ruang

Jika dua mata kuliah menggunakan ruang yang sama pada waktu yang sama:

penalti +1

Contoh:

M1 → S1
M2 → S1

keduanya menggunakan:

Senin 08.00
R1

maka:

penalti ruang = 1

Konflik Kapasitas

Jika kapasitas ruang lebih kecil daripada jumlah mahasiswa:

penalti +1

Contoh:

M4 = 40 mahasiswa
S6 = R2 kapasitas 30

maka:

penalti kapasitas = 1

---

#05 Membentuk Populasi Awal

Misalkan dibentuk empat kromosom awal:

P1 = [S1, S1, S4, S5]
P2 = [S1, S3, S2, S5]
P3 = [S3, S2, S4, S6]
P4 = [S5, S3, S6, S4]

Sebelum melihat tabel fitness, setiap kromosom perlu diperiksa satu per satu.

---

#06 Menghitung Fitness

Evaluasi P1

P1 = [S1, S1, S4, S5]

Interpretasi:

M1 → S1
M2 → S1
M3 → S4
M4 → S5

M1 dan M2 menggunakan slot yang sama:

S1 = Senin 08.00, R1

Terjadi satu konflik ruang.

Tidak ada konflik dosen dan semua kapasitas ruang sesuai.

Maka:

Fitness:

Evaluasi P2

P2 = [S1, S3, S2, S5]

M1:

S1 = Senin 08.00, R1

M3:

S2 = Senin 08.00, R2

M1 dan M3 diajar D1 pada waktu yang sama.

Maka:

penalti dosen = 1

Tidak ada pelanggaran lain.

Evaluasi P3

P3 = [S3, S2, S4, S6]

M1 berada pada:

Senin 10.00

M3 juga:

Senin 10.00

Keduanya diajar D1.

penalti dosen = 1

M4 menggunakan:

S6 = R2

Kapasitas R2:

30

sedangkan mahasiswa M4:

40

Maka:

penalti kapasitas = 1

Total:

Fitness:

Evaluasi P4

P4 = [S5, S3, S6, S4]

M1 dan M3 sama-sama berada pada:

Selasa 08.00

dan diajar D1.

penalti dosen = 1

M4 menggunakan R2:

S4 = Senin 10.00, R2

Kapasitas R2 hanya 30, sedangkan mahasiswa M4 berjumlah 40.

penalti kapasitas = 1

Total:

Fitness:

Hasil evaluasi populasi:

Fitness terbaik pada populasi awal:

0.5000

Belum ada solusi dengan:

fitness = 1

---

#07 Melakukan Seleksi

Contoh ini menggunakan tournament selection.

Misalkan pasangan tournament:

Tournament 1:
P1 vs P3

Tournament 2:
P2 vs P4

Tournament 1:

Fitness P1 = 0.5000
Fitness P3 = 0.3333

Maka:

P1 dipilih

Tournament 2:

Fitness P2 = 0.5000
Fitness P4 = 0.3333

Maka:

P2 dipilih

Parent terpilih:

Parent 1 = P1
Parent 2 = P2

---

#08 Melakukan Crossover

Parent:

P1 = [S1, S1, S4, S5]
P2 = [S1, S3, S2, S5]

Digunakan one-point crossover setelah gene ke-2.

P1 = [S1, S1 | S4, S5]
P2 = [S1, S3 | S2, S5]

Bagian setelah titik crossover ditukar.

Child 1:

C1 = [S1, S1, S2, S5]

Child 2:

C2 = [S1, S3, S4, S5]

Evaluasi Child 1

C1 = [S1, S1, S2, S5]

M1 dan M2 sama-sama menggunakan S1.

penalti ruang = 1

M1 menggunakan Senin 08.00 dan M3 menggunakan S2 yang juga Senin 08.00.

Keduanya diajar D1.

penalti dosen = 1

Total:

Fitness:

Evaluasi Child 2

C2 = [S1, S3, S4, S5]

Interpretasi:

M1 → S1 = Senin 08.00 R1
M2 → S3 = Senin 10.00 R1
M3 → S4 = Senin 10.00 R2
M4 → S5 = Selasa 08.00 R1

Periksa konflik dosen:

M1 = Senin 08.00
M3 = Senin 10.00

Tidak bentrok.

Periksa ruang:

tidak ada dua mata kuliah dengan ruang dan waktu identik

Periksa kapasitas:

M1 → R1 kapasitas 40 untuk 35 mahasiswa
M2 → R1 kapasitas 40 untuk 30 mahasiswa
M3 → R2 kapasitas 30 untuk 25 mahasiswa
M4 → R1 kapasitas 40 untuk 40 mahasiswa

Semua memenuhi.

Maka:

Fitness:

Hasil crossover:

Crossover berhasil menghasilkan satu jadwal tanpa konflik.

---

#09 Melakukan Mutasi

Mutasi dilakukan dengan mengubah salah satu gene menjadi slot lain.

Karena proses mutasi bersifat probabilistik, contoh berikut hanya menunjukkan satu kemungkinan.

Misalkan C1 mengalami mutasi pada gene ke-3.

Sebelum:

C1 = [S1, S1, S2, S5]

Gene ke-3:

S2

diubah menjadi:

S4

Setelah mutasi:

C1' = [S1, S1, S4, S5]

Konflik dosen antara M1 dan M3 sudah hilang karena waktunya berbeda.

Namun M1 dan M2 masih sama-sama menggunakan S1.

Maka:

Fitness:

Mutasi meningkatkan fitness dari:

0.3333

menjadi:

0.5000

Child 2 sudah memiliki fitness 1, sehingga pada contoh ini tidak perlu diubah.

---

#10 Membentuk Generasi Baru

Jika digunakan elitisme, kromosom terbaik dapat langsung dipertahankan.

Contoh generasi baru:

Individu terbaik:

C2 = [S1, S3, S4, S5]

dengan:

Fitness = 1

---

#11 Menentukan Jadwal Terbaik

Kromosom terbaik:

[S1, S3, S4, S5]

Interpretasinya:

Pemeriksaan:

Konflik dosen    = 0
Konflik ruang    = 0
Konflik kapasitas = 0

Total penalti:

Fitness:

Untuk contoh kecil ini, kromosom tersebut memenuhi seluruh hard constraint yang didefinisikan pada tutorial.

---

Pseudocode

input:
    mata_kuliah
    dosen
    ruang
    slot_waktu
    ukuran_populasi
    crossover_rate
    mutation_rate

buat populasi awal

repeat:

    for setiap kromosom:
        hitung konflik_dosen
        hitung konflik_ruang
        hitung konflik_kapasitas

        penalti =
            konflik_dosen +
            konflik_ruang +
            konflik_kapasitas

        fitness =
            1 / (1 + penalti)

    pilih parent

    lakukan crossover

    lakukan mutasi

    evaluasi offspring

    bentuk generasi baru

until:
    fitness target tercapai
    atau generasi maksimum tercapai

return kromosom terbaik

---

Parameter Penting

Pada sistem penjadwalan nyata, hard constraint biasanya dapat diberi penalti lebih besar daripada soft constraint.

Contoh konsep:

Bentrok dosen        → penalti besar
Bentrok ruang        → penalti besar
Kapasitas tidak cukup → penalti besar
Preferensi jam dosen → penalti lebih kecil

Nilai bobot harus ditentukan sesuai kebutuhan sistem, bukan dianggap sebagai nilai baku Algoritma Genetika.

---

Kelebihan dan Kekurangan

Kelebihan

• Dapat menangani ruang pencarian solusi yang besar.
• Fleksibel untuk banyak jenis constraint.
• Representasi fitness dapat disesuaikan dengan kebutuhan.
• Dapat digunakan untuk masalah kombinatorial seperti penjadwalan.
• Tidak membutuhkan turunan fungsi objektif.

Kekurangan

• Tidak menjamin selalu memperoleh optimum global.
• Hasil dapat berbeda karena operasi seleksi, crossover, dan mutasi bersifat stokastik.
• Membutuhkan penentuan parameter yang tepat.
• Fungsi fitness yang kurang baik dapat menghasilkan jadwal yang tidak sesuai kebutuhan.
• Waktu komputasi dapat meningkat jika populasi dan jumlah generasi besar.

Untuk pendekatan pencarian lokal yang lebih sederhana, Anda dapat membandingkannya dengan Hill Climbing.

---

Kesalahan Umum

1. Kromosom Tidak Merepresentasikan Jadwal Secara Jelas

Setiap posisi gene harus mempunyai arti tetap.

Pada contoh:

gene 1 selalu M1
gene 2 selalu M2
gene 3 selalu M3
gene 4 selalu M4

2. Hanya Menghitung Satu Jenis Konflik

Penjadwalan tidak cukup hanya memeriksa bentrok ruang.

Minimal perlu memeriksa constraint yang memang digunakan sistem.

3. Fitness Semakin Besar Justru Semakin Buruk

Jika menggunakan penalti, rumus fitness harus dirancang agar solusi dengan konflik lebih sedikit mendapatkan nilai lebih baik.

4. Tidak Mempertahankan Solusi Terbaik

Tanpa elitisme, solusi terbaik pada satu generasi dapat hilang pada generasi berikutnya.

5. Mutation Rate Terlalu Besar

Mutasi yang terlalu agresif dapat membuat pencarian berubah menjadi terlalu acak.

6. Menganggap Contoh Manual sebagai Parameter Baku

Jumlah populasi, crossover rate, mutation rate, bobot penalti, dan kondisi berhenti perlu disesuaikan dengan kasus sebenarnya.

---

Ringkasan

Kasus menggunakan:

4 mata kuliah
3 dosen
2 ruang
6 slot

Representasi kromosom:

[M1, M2, M3, M4]

Fitness:

Populasi awal belum memiliki solusi bebas konflik.

Setelah seleksi dan one-point crossover diperoleh:

C2 = [S1, S3, S4, S5]

dengan:

Penalti = 0
Fitness = 1

Jadwal akhir:

M1 → Senin 08.00 R1
M2 → Senin 10.00 R1
M3 → Senin 10.00 R2
M4 → Selasa 08.00 R1

Contoh ini menunjukkan bagaimana Algoritma Genetika dapat merepresentasikan dan memperbaiki kandidat jadwal melalui proses evaluasi fitness, seleksi, crossover, dan mutasi.

---

FAQ

Apa fungsi Algoritma Genetika pada penjadwalan kuliah?

Algoritma Genetika digunakan untuk mencari kombinasi jadwal yang memenuhi constraint dengan mengevaluasi banyak kandidat solusi melalui beberapa generasi.

Apa yang menjadi kromosom?

Pada tutorial ini, satu kromosom berisi slot jadwal untuk seluruh mata kuliah.

Apa yang menjadi gene?

Satu gene menyimpan kode slot untuk satu mata kuliah.

Apa itu fitness?

Fitness adalah ukuran kualitas kromosom. Pada contoh ini, fitness meningkat ketika jumlah konflik menurun.

Apa itu penalti?

Penalti adalah nilai yang diberikan ketika jadwal melanggar constraint.

Apakah semua konflik harus memiliki bobot yang sama?

Tidak. Tutorial menggunakan bobot 1 agar perhitungan mudah. Sistem nyata dapat memberikan bobot berbeda sesuai prioritas constraint.

Apa fungsi crossover?

Crossover menggabungkan bagian kromosom dari dua parent untuk menghasilkan kandidat solusi baru.

Apa fungsi mutasi?

Mutasi mengubah satu atau beberapa gene agar populasi tetap memiliki variasi solusi.

Apa fungsi elitisme?

Elitisme mempertahankan individu terbaik agar solusi bagus tidak hilang pada generasi berikutnya.

Apakah Algoritma Genetika selalu menghasilkan jadwal terbaik?

Tidak selalu. GA merupakan metode heuristik/stokastik. Kualitas hasil dipengaruhi representasi kromosom, fungsi fitness, parameter, constraint, dan proses evolusi.

Kapan proses dapat dihentikan?

Proses dapat dihentikan ketika fitness target tercapai, jumlah generasi maksimum tercapai, atau tidak ada perbaikan selama sejumlah generasi.

---

Referensi

1. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.
2. Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press.
3. Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280.

---

Source Code

Berikut source code yang menggunakan Algoritma Genetika pada RumahSourceCode.

Source Code Algoritma Genetika Penjadwalan PHP

Rp750,000

Source Code Algoritma Genetika Menu PHP

Rp750,000

Source Code Algoritma Genetika TSP Codeigniter

Rp1,050,000

Source Code Algoritma Genetika Jadwal Karyawan Codeigniter

Rp750,000

Source Code Algoritma Genetika TSP PHP

Rp750,000

Source Code Algoritma Genetika Penjadwalan CodeIgniter

Rp1,050,000

Source Code Algoritma Genetika Penjadwalan SMP PHP

Rp750,000

Source Code Algoritma Genetika dan Fuzzy Tsukamoto PHP

Rp1,050,000

Source Code Algoritma Genetika Penjadwalan SMA PHP

Rp750,000