Breaking News
Home » Kecerdasan Buatan » Contoh Perhitungan Algoritma Genetika Penjadwalan
'Penjadwalan' - Algoritma Genetika Penjadwalan dengan PHP

Contoh Perhitungan Algoritma Genetika Penjadwalan

Algoritma Genetika Penjadwalan

Penerapan algoritma genetika dalam penjadwalan sangat sering digunakan, baik untuk penjadwalan shift kerja, penjadwalan ujian, atau penjadwalan mata kuliah. Algoritma genetika memberikan solusi yang tidak bisa dipecahkan dengan metode konvensional. Kali ini rumahsoftware akan lebih memfocuskan ke penjadwalan mata kuliah, walaupun nanti juga bisa diterapkan ke penjadwalan yang lainnya.

Kasus Penjadwalan Mata Kuliah

Dalam penjadwalan mata kuliah, algoritma genetika berfungsi untuk menentukan waktu (hari dan jam) serta ruang yang sesuai untuk setiap kuliah sehingga tidak bentrok dengan kuliah lain. Kuliah yang dimaksudkan di sini adalah kombinasi antara kelas, dosen, dan mata kuliah. Data yang harus disiapkan antara lain:

  • Data waktu, mencatat hari dan jam yang tersedia dalam 1 minggu.
  • Data kuliah, adalah kombinasi dari mata kuliah, data dosen dan data kelas. Dimana 1 dosen dapat mengajar lebih dari 1 mata kuliah dan lebih dari 1 kelas, 1 mata kuliah terdapat lebih dari 1 kelas.
  • Data Ruang, berisi daftar ruang yang bisa digunakan baik lab maupun ruang teori.

Langkah Algoritma Genetika Penjadwalan

Sebelum melangkah ke step-step bagaimana algoritma genetika dalam penjadwalan, temen-temen harus tahu penentuan nilai fitness. Dalam kasus penjadwalan, fitness ditentukan oleh:

  • Clash Ruang (CR), jumlah jadwal yang ruang yang sama di waktu yang sama
  • Clash Class (CC), jumlah jadwal yang kelas yang sama di waktu yang sama
  • Clash Dosen (CD), jumlah jadwal yang dosen sama mengajar di waktu yang sama

Sehingga perhitungan fitness adalah:

F = 1 / (1 + CR + CC + CD)

Fitnes terbaik adalah fitnes yang bernilai paling besar (tidak ada bentrok) sehingga nilainya harusnya 1. Semakin banyak bentrok (clash) maka fitness akan semakin kecil. Dalam beberapa kasus juga bisa ditambahkan Absen Dosen, yaitu penentuan kapan dosen itu tidak bisa mengajar.

Setelah penentuan aturan nilai fitness, maka dilanjutkan dengan langkah algoritma genetika:

Pembangkitan Generasi Awal

Sebelum pembangkitan generasi awal, ada beberapa pengaturan yang harus dibuat ketika merancang aplikasi diantaranya:

  • Jumlah Kromosom
    Kromosom adalah kumpulan gen-gen (kombinasi antara kuliah, ruang, dan waktu) sejumlah kuliah yang ada. Di awal ditentukan jumlah kromosom yang dibangkitkan. Satu kromosom ada satu solusi, sehingga semakin banyak kromosom yang dibangkitkan semakin banyak pilihan solusi (jadwal) yang dihasilkan, yang nantinya akan dipilih satu yang terbaik.Kromosom akan disimpan ke dalam sebuah array dengan format seperti berikut:

Kromosom 1 = {[0, 3, 5], [1, 5, 13], … [30, 4, 0]}

Dapat dilihat Kromosom 1 memiliki 30 gen yang artinya terdapat 30 kuliah. Setiap gen adalah kombinasi [kuliah, ruang, waktu]. Dalam gen data dimasukkan dalam angka (indeks dimulai dari 0). Gen [0, 3, 5] artinya kuliah ke satu, ruang ke 3 dan waktu ke 5. Tapi harus diperhatikan semakin banyak kromosom dibangkitkan maka semakin berat dam lambat proses generate jadwal.

  • Maksimal Generasi
    Proses algoritma akan berhenti jika sudah mencapai nilai fitness 1 (tidak ada bentrok). Jika masih bentrok akan diulang lagi generasi berikutnya. Terkadang dalam generate jadwal bisa saja tidak menemukan fitness 1, hal ini bisa terjadi karena jumlah kuliah banyak sedangkan ruang dan waktu sedikit dan tidak memungkinkan untuk membuat jadwal yang tidak bentrok. Untuk mengatasi hal inilah diatur maksimal generasi sehingga program tidak akan berhenti jika sudah di generasi terakhir walaupun fitness belum mencapai 1.
  • Crossover Rate
    Mengatur prosentase kromosom yang akan dipindah silang (rentang 0-100).
  • Mutation Rate
    Mengatur prosentase gen yang akan diganti (mutasi).

Seleksi

Proses seleksi adalah pemilihan kromosom yang mana yang akan digunakan untuk proses algoritma berikutnya. Seleksi ditentukan berdasarkan nilai fitness kromosom. Semakin besar fitness semakin besar kesempatan kromosom untuk terpilih.

Metode yang digunakan untuk seleksi adalah Roullete Wheel. Cara kerjanya adalah:

  • Hitung nilai fitness dari masing-masing individu
    Misal terdapat 4 kromosom yang dibangkitkan dengan masing-masing fitness:
    Kromosom 1 = 0.8
    Kromosom 2 = 0.3
    Kromosom 3 = 0.5
    Kromosom 4 = 0.4
  • Hitung total fitness dari semua individu
    Total fitness adalah 0.8 + 0.3 + 0.5 + 0.4 = 2
  • Hitung probabilitas masing-masing individu
    Probabilitas didapat dari nilai fitness dibagi dengan total fitness, hasilnya:
    P 1 = 0.8 / 2 = 0.4
    P 2 = 0.3 / 2 = 0.15
    P 3 = 0.5 / 2 = 0.25
    P 4 = 0.4 / 2 = 0.2
  • Dari probabilitas tersebut, hitung jatah masing-masing individu pada angka 1 sampai 100
    Penentuan jatah dilakukan dengan mencari komulatif dari probabilitas:
    PK 1 = 0 + 0.4 = 0.4
    PK 2 = 0.4 + 0.15 = 0.55
    PK 3 = 0.55 + 0.25 = 0.80
    PK 4 = 0.80 + 0.2 = 1
  • Bangkitkan bilangan acak antara 0 – 1 sejumlah kromosom
  • Dari bilangan acak yang dihasilkan, tentukan individu mana yang terpilih dalam proses seleksi.
    Misal bilangan pertama adalah 0.2 maka kromosom 1 terpilih (kromosom 1 antara 0-0.4), jika bilangan berikutya adalah 0.7 maka kromosom 3 yang terpilih (kromosom 3 antara 0.55 sampai 0.80). Dapat dilihat bahwa kemungkinan besar Kromosom 1 untuk terpilih labih besar karena rentangannya nilainya paling panjang. Kromosom yang dipilih sebanyak jumlah kromosom awal, tapi bisa saja ada kromosom yang sama terpilih dan ada kromosom yang tidak terpilih.

Pindah Silang (Crossover)

Pindah silang merupakan pertukaran gen antara dua buah kromosom. Kromosom yang menjadi induk dipilih secara acak sebanyak crossover rate yang sudah diatur di awal. Misal ada 10 kromosom dengan dengan CR 70%, maka induk yang digunakan adalah 7. Dari 7 induk ini akan dipasangkan dua dua yang menghasilkan 1 individu baru. Pasangan induk yang terjadi adalah 7 pasang yaitu, induk1 dan induk2, induk 2 dan induk 3, dan seterusnya sampe induk 7 dengan induk 1. Setiap induk akan berpasangan 2 kali.

Metode pindah silang yang digunakan adalah One Point Crossover dimana setiap pasangan akan dipilih 1 buah bilangan acak antara 1 sampe jumlah gen dalam kromosom. Misal dalam kromosom terdapat 50 gen, dan bilangan acak dibangkitkan nilainya 20, maka kromosom baru yang diciptakan adalah gen 0-19 dari induk1 dan 20-49 dari induk2, begitu juga untuk pasangan yang lain.

Mutasi

Mutasi adalah penggantian gen. Gen yang dimutasi hanya diganti ruang, dan waktunya saja, untuk kuliahnya tetap. Jumlah gen yang diganti tergantung Mutation Rate (MR). Misal ada 5 kromosom dengan gen 10 masing-masing kromosom, dengan MR 50 persen. Maka:

Total Gen : 5 * 10 (jumlah kromosom * jumlah gen per kromosom) = 50 gen
Jumlah Mutasi = 50% * 50 = 25 gen.

Cara mutasi adalah membangkitkan bilangan acak antara 1 sampe total gen (50) sebanyak 25 kali. Misal bilangan acak pertama adalah 12 maka akan diambil kromosom kedua gen ke dua (karena kromosom pertama hanya sampe 10, kurang lagi 2 diambil di kromosom ke 2). Sehingga ruang dan waktu gen ke dua di kromosom ke dua akan diganti dengan mengambil data ruang dan waktu secara acak.

Source Code Algoritma Genetika Penjadwalan

TugasAkhir.Id menyediakan source code aplikasi algoritma genetika penjadwalan yang berbasis web, baik dengan PHP native atau dengan framework (CodeIgniter). Adapun komponen yang ada pada source code antara lain:

  • Login, untuk membatasi akses ke dalam aplikasi.
  • Halaman Utama, menampilkan menu-menu untuk navigasi ke semua fitur AG Penjadwalan.
  • Hari, mengolah data hari yang bisa ditambah, diubah, dan dihapus.
  • Jam, mengolah data jam yang bisa ditambah, diubah, dan dihapus.
  • Waktu, mengolah data waktu yang bisa ditambah, diubah, dihapus dan dicetak.
  • Mata kuliah, mengolah data mata kuliah yang bisa ditambah, diubah, dan dihapus.
  • Dosen, mengolah data dosen yang bisa ditambah, diubah, dan dihapus.
  • Kelas, mengolah data kelas yang bisa ditambah, diubah, dan dihapus.
  • Data Kuliah, mengolah data kuliah yang bisa ditambah, diubah, dihapus dan dicetak. Data kuliah merupakan gabungan antara mata kuliah, dosen, dan kelas.
  • Ruang, mengolah data ruang yang bisa ditambah, diubah, dan dihapus.
  • Generate Jadwal, meng-generate jadwal otomatis dengan algoritma genetika.
  • Hasil, menampilkan jadwal haril generate dengan algoritma genetika, yang bisa dicetak langsung.
  • Password, mengubah password user yang login.

Check Also

Contoh Perhitungan SPK Metode AHP

Contoh Perhitungan SPK Metode AHP

Contoh perhitungan spk metode ahp dengan mengambil studi kasus pemilihan lokasi warnet terbaik. Dalam perhitungan …

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *