CONSTRAINT SATISFACTION PROBLEM (CSP) Tugas 4 AI

HALLO …

Assalamualaikum …

Kembali lagi dengan blog saya ini :d. kali ini saya akan memposting Tugas 4 AI dengan Bahasan yaitu CSP (CONSTRAINT SATISFACTION PROBLEM). Yuk langsung saja di cek guys postingannya, Kita berbagi-bagi ilmu :d . Perlu di ingat postingan ini untuk memenuhi Tugas 4 pada Mata Kuliah Pengantar Kecerdasan Tiruan (AI) pada universitas Muhammadiyah Prof.DR.Hamka.

CONSTRAINT SATISFACTION PROBLEM..

 

apa sih CSP itu? Constraint Satisfaction Problem merupakan sebuah pendekatan untuk menyelesaikan suatu masalah dengan tujuan menemukan keadaan atau objek yang memenuhi sejumlah persyaratan atau kriteria.

Constraint Satisfaction Problem juga adalah suatu permasalahan seseorang harus mencari nilai untuk set variabel (finite) yang memenuhi set constraint (finite). Komponen-komponen yang terdapat pada Constraint Satisfaction Problem adalah Variabel yang merupakan penampung dapat diisi berbagai nilai, Constraint yang merupakan suatu aturan yang ditentukan untuk mengatur nilai boleh diisikan ke variabel, atau kombinasi variable, Domain yang merupakan kumpulan nilai legal dapat diisi ke variable, Solusi yang merupakan assignment nilai-nilai dari domain ke setiap variabel tidak ada constraint yang dilanggar. Serta Assignment & Solusi.

Komponen-komponen yang ada di CSP: 

1.      Set Variabel
Merupakan sesuatu yang memiliki nilai bervariasi, kemudian dapat juga didefiniskan sebagai hal yang berbeda beda dalam bahasa pemprograman yang diwakili oleh simbol untuk variasi nilai tertentu.

2.      Set Domain
Merupakan kumpulan nilai legal yang dapat diisi ke variabel. 

3.      Set Constraint/Batasan
Menspesifikan kombinasi nilai yang diperbolehkan.

4.      Assignment >>> pemberian nilai pada suatu variabel.

5.      Solusi >>> pemberian nilai-nilai pada setiap variabel yang memenuhi semua constraint yang  telah ditetapkan untuk persoalan, sehingga nilainilai variabel tersebut merupakan solusi untuk persoalan.

Contoh permasalahan CSP yang akan saya bahas ini adalah Timetabling yang mengenai PENJADWALAN MATAKULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIKA DAN METODE CONSTRAINT SATISFACTION

Mengingat masalah penjadwalan perkuliahan di Perguruan Tinggi merupakan masalah NPhard secara komputasi. Pada penelitian ini metode Algoritma Genetika dipadukan dengan metode Constraint Satisfaction Problem, dengan kromosom yang dihasilkan metode Algoritma Genetika diproses dengan metode Constraint Satisfaction Problem. Dengan cara ini dapat batasan-batasan pada penjadwalan yang harus dipenuhi dapat dijamin tidak terlanggar. Hal ini akan membuat proses heuristic pada Algoritma Genetika menjadi terarah dan membuat keseluruhan proses menjadi lebih efisien.

Permasalahan penjadwalan pengajaran klasik didefinisikan sebagai berikut

[1]: Terdapat sejumlah mkelas c1, ..., cm, n guru t1, ..., tn, dan p periode 1, ..., p. Terdapat pula matriks integer non negative Rm_n, yang disebut matriks requirements, dengan rij adalah jumlah pelajaran yang diberikan oleh guru tj pada kelas ci. Permasalahan penjadwalan adalah mengalokasikan kelas pada periode sedemikian sehingga tidak ada pengajar dan kelas yang dijadwalkan terjadi pada satu pelajaran pada saat yang sama.

Definisi klasik ini belum dapat memenuhi kebutuhan penjadwalan perkuliahan di Perguruan Tinggi seperti:

·         Seorang dosen terkadang hanya dapat mengajar pada jam-jam dan hari-hari tertentu.

·         Setiap mata kuliah yang diajarkan memiliki alokasi semester sehingga perlu pengaturan agar penjadwalan matakuliah pada semester yang sama tidak bersamaan dan mahasiswa pada semester tersebut dapat mengikuti semua matakuliah yang dialokasikan kepadanya.

·         Dalam satu hari seorang dosen seharusnya maksimal mengajar dua kelas. Masalah penjadwalan perkuliahan di Perguruan Tinggi merupakan masalah NP-hard secara komputasi, sehingga sejumlah penelitian  menerapkan metode heuristic untuk melakukan otomasi terhadap masalah penjadwalan. Masalah penjadwalan perkuliahan berbeda dari satu universitas ke universitas, bahkan dari satu jurusan ke jurusan lain pada universitas yang sama.

Faktor-faktor yang berpengaruh dalam pembentukan jadwal meliputi:

1. Dosen

Seorang dosen tidak dapat mengajar beberapa mata kuliah pada jam yang sama. Selain itu, seorang dosen terkadang hanya dapat mengajar pada jam-jam dan hari-hari tertentu saja, sehingga perlu untuk memesan jadwal khusus yang tidak dapat diganggu mata kuliah yang lain.

2. Ruang

Mengingat jumlah ruang yang dimiliki terbatas, maka perlu diperhatikan ruang yang tersedia agar tidak menggangu jalannya perkuliahan. Jadwal harus hanya mengakomodasi ruang yang ada.

3. Waktu

Waktu merupakan batasan berapa menit yang diperlukan untuk satu jam kuliah. Selain itu, ada hari-hari yang jam kuliah dibatasi sampai dengan jam tertentu (misalnya jam kuliah hari Jumat dibatasi mulai jam 07.30 sampai jam 11.00 dan dimulai kembali jam 13.00). Dengan batasan-batasan waktu ini, jadwal hanya akan berada pada waktu yang ditentukan.

4. Matakuliah

Mengingat setiap matakuliah memiliki semester mata kuliah itu diajarkan, maka perlu adanya aturan yang membatasi penjadwalan matakuliah, agar mata-kuliah itu sesuai dengan aturan-aturan penjadwalan. Aturan-aturan yang harus diperhatikan dalam membuat jadwal meliputi:

_ Tidak boleh ada satu ruang yang diisi dua kali dalam satu waktu yang sama.

_ Tidak boleh ada Nomor Induk Pegawai (NIP) dosen yang sama pada hari dan jam yang sama.

_ Kemunculan matakuliah pada semester yang sama dibatasi maksimal dua kali pada satu hari.

_ Pada masing-masing semester, mahasiswa harus dapat mengambil matakuliah sesuai dengan kurikulum yang ditentukan jurusan sehingga jika mahasiswa mengambil matakuliah sesuai kurikulum tidak ada matakuliah yang tidak bisa diambil karena jadwal yang bersamaan dengan jadwal matakuliah lain pada semester yang sama.

_ Matakuliah dengan kode matakuliah yang sama (kelas paralel) harus ada pada hari yang sama, kecuali jika dosennya sama.

_ Jarak matakuliah antarsemester dengan semester berikutnya pada jam yang sama harus lebih besar dari jarak yang ditetapkan pengguna. Ini berguna untuk memberikan keleluasaan mahasiswa mengambil matakuliah yang tidak berada pada semester mahasiswa tersebut, misalnya kasus mahasiswa mengulang suatu matakuliah atau mahasiswa yang memiliki Indeks Prestasi tinggi mengambil suatu matakuliah lain di semester lebih tinggi.

_ Dalam satu hari, dosen mengajar maksimal dua kelas.

Metode Algoritma Genetika :

Gambar 1 : Flowchart Proses Algoritma Genetika

Hal-hal yang dilakukan pada proses inisialisasi Algoritma Genetika adalah:

1. Menginisialisasi tabel hasil dengan menghapus data yang lama dan mengisikan data default.

2. Mendata setting paramater Algoritma Genetika dari database.

3. Mendata matakuliah yang ditawarkan dan matakuliah dari database sebagai data kromosom.

4. Membentuk kromosom sebagai populasi awal.

5. Memproses preprocessing untuk memperkirakan apakah jadwal dapat dibuat. Proses ini melakukan penghitungan jumlah data yang dibutuhkan untuk membuat jadwal dan membandingkannya dengan jumlah domain yang tersedia. Jika domain tersebut mencukupi, proses pembuatan jadwal dapat dilanjutkan; sedangkan jika domain tidak mencukupi, jadwal dianggap tidak dapat dibuat dan proses dibatalkan.

Model Algoritma Genetika yang akan digunakan untuk melakukan optimasi adalah sebagai berikut:

1. Seleksi.

Pada seleksi, dilakukan penilaian atas nilai fitness. Akibatnya, fitness yang memiliki kualitas kromosom paling baik memiliki kemungkinan terpilih ke dalam generasi selanjutnya lebih besar. Seleksi yang dipakai di sini adalah seleksi yang menggunakan metode roulette wheel. Pada seleksi ini perlu diperhatikan jumlah maksimal populasi sebagai input, agar populasi tidak menjadi terlalu besar dan memakan banyak waktu, dan populasi juga tidak menjadi terlalu kecil dan mengakibatkan kromosom terlalu mirip sehingga operasi kromosom tidak akan banyak berpengaruh.

2. Crossover.

Crossover yang digunakan adalah penyilangan dua titik dengan permutasi. Pemilihan kromosom yang akan di-crossover-kan ditentukan oleh probabilitas yang ditentukan dalam setting parameter Algoritma Genetika. Banyak gen yang ditukar juga mengikuti setting parameter Algoritma Genetika. Dalam melakukan penyilangan, setiap dua kromosom akan menghasilkan dua offspring baru hasil penyilangan.

3. Mutasi.

Mutasi dilakukan setelah operasi kromosom ini dilakukan dengan menukar gen secara random. Dalam proses ini perlu diperhatikan tingkat mutasi dan tingkat probabilitas terjadi mutasi. Jika sering terjadi mutasi, antar generasi selanjutnya akan kehilangan kemiripan dan pencarian akan menjadi acak. Tetapi, jika mutasi terlalu sedikit, kromosom akan menjadi terlalu mirip dan kromosom baru akan muncul terlalu lama pada populasi.

4. Penentuan Fitness.

Penentuan fitness pada dasarnya adalah pemberian nilai kuantitatif yang mewakili kualitas dari kromosom. Hal pertama yang dilakukan proses ini adalah proses Pembuatan Jadwal sesuai kromosom yang dipilih dengan memprosesnya dengan Constraint Satisfaction Problem, dan hasilnya akan diberi nilai fitness.Fungsi fitness yang dibuat merupakan rata-rata waktu tunggu antarkuliah mahasiswa dalam satu minggu sehingga semakin kecil waktu tunggu maka akan semakin baik (waktu tunggu antar kuliah mahasiswa menjadi minimal).

Metode CSP

Gambar 2 : Flowchart Pembuatan Jadwal dengan menggunakan CSP

Data pesan jadwal yang sudah dibuat. Setelah data pesan jadwal valid maka dilakukan pembuatan jadwal menggunakan CSP. Gambar 2 menunjukkan flowchart pembuatan jadwal dengan menggunakan CSP yang dilakukan. Proses yang terjadi dalam pembuatan jadwal pada Gambar 2 dapat diuraikan sebagai berikut:

1.      Menginisialisasi, yaitu persiapan data yang dibutuhkan oleh Constraint Satisfaction.

2.      Memilih variabel yang ingin diisikan, jika melakukan pemilihan dengan menggunakan MRV maka diambil variabel yang memiliki domain paling sedikit, jika tidak menggunakan MRV akan diambil secara berurutan sesuai urutan pada variabel.

3.      Memilih nilai yang masih valid dari domain untuk variabel yang dipilih.

4.      Meng-assignment variabel dan domain ke dalam solusi, kemudian mengurangi domain valid dari setiap variabel berdasarkan constraint yang dimiliki variable yang di-assign.

5.      Jika solusi sudah terbentuk, dilanjutkan ke langkah

6.      Jika solusi belum ditemukan kembali ke langkah 2.

7.      Jika setiap variabel sudah terisi, solusi sudah terbentuk, kemudian CSP akan memberikan hasilnya kembali ke Algoritma Genetika untuk dievaluasi.

Model Constraint Satisfaction yang digunakan untuk menyelesaikan masalah penjadwalan adalah sebagai berikut:

1. Penelusuran dengan Backtracking (BT).

Algoritma backtracking menggunakan Constructive methods, yang berarti mengembangkan solusi partial sedikit demi sedikit dengan tetap menjaga consistency, sehingga mencapai consistent complete assignment.

2. Forward Checking (FC).

Forward checking berkerja dengan membuat suatu tabel yang menyatakan nilai domain yang masih tersedia untuk setiap variabel. Kemudian pada tabel ini dihilangkan domain yang sudah tidak boleh diambil lagi.

3. Minimum Remaining Value (MRV).

Minimum remaining value dapat bekerja bersamaan dengan FC dengan memilihkan variabel yang diisikan. Variabel yang dipilih adalah variabel yang memiliki domain paling sedikit. Pertimbangan yang digunakan adalah variabel yang jumlah domain-nya paling sedikit mempunyai kesempatan gagal lebih besar. Hal ini dapat memotong percabangan tree yang tidak perlu dan mempercepat waktu pembuatan jadwal.

Referensi :

1.      Werra, D.D.: An Introduction to Timetabling. European Journal of Operational Research 19(2) (1985) 151–162

2.      Arntzen, H., Løkketangen, A.: A Local Search Heuristic for a University Timetabling Problem. Technical report, Dalle Molle Institute for Artificial Intelligence (2007) Diakses 31 August 2007, http://www.idsia.ch/Files/ttcomp2002/arntzen.pdf.

3.      Chiarandini, M., Birattari, M., Socha, K., Rossi- Doria, O.: An Effective Hybrid Algorithm for University Course Timetabling. Journal of Scheduling 9(5) (2006) 403–432

4.      http://web.csulb.edu/~obenli/DSS/node7.html