tugas 4 csp

Constraint Satisfaction Problem

   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.

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.

Contoh permasalahan CSP ini adalah Penjadwalan Mata pelajaran.
Dalam proses penjadwalan mata pelajaran ada beberapa hal yang harus diperhatikan:

• Pertama, terdapat jadwal-jadwal di mana guru yang bersangkutan tidak bisa mengajar. 
• Kedua, distribusi jadwal perkuliahan diharapkan dapat merata tiap harinya untuk setiap kelas. 
• Ketiga, pekerjaan penjadwalan mata pelajaran ini akan semakin berat jika melibatkan semakin banyak kelas per angkatannya. 
• Keempat, terdapat mata pelajaran tertentu yang menggunakan ruang laboratorium yang harus dijadwalkan pada ruang laboratorium.

Solusi untuk memecahkan masalah tersebut adalah dengan Algoritma Genetika. Ciri-ciri permasalahan yang dapat dikerjakan dengan menggunakan Algoritma Genetika adalah masalah tersebut mempunyai fungsi tujuan optimalisasi non linear dengan banyak kendala non linear. Selanjutnya, masalah tersebut mempunyai kemungkinan solusi yang jumlahnya tak terhingga. Kombinasi dari mata pelajaran, guru, dan kelas memiliki kemungkinan yang sangat banyak sehingga algoritma genetika dapat digunakan dalam permasalahan ini. Terakhir, masalah tersebut mempunyai multi-objective dan multi-criteria, sehingga diperlukan solusi yang dapat secara bijak diterima oleh semua pihak.

Ada faktor-faktor yang berpengaruh dalam pembentukan jadwal antara lain:

-          guru

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

-          kelas

Mengingat jumlah kelas yang dimiliki, agar tidak menggangu jalannya pelajaran Jadwal harus hanya mengakomodasi kelas yang ada.

-          Waktu

Waktu merupakan batasan berapa menit yang diperlukan untuk satu matpel. Selain itu sekolah dibatasi dari hari Senin sampai hari Sabtu dan setiap harinya pun dibatasi mulai jam 07.00 sampai jam 13.00. Dengan batasan-batasan waktu ini, jadwal hanya akan berada pada waktu yang ditentukan.

-          Mata pelajaran

Mengingat setiap mataelajaran memiliki pelajaran yang diajarkan, maka perlu adanya aturan yang membatasi penjadwalan matpel, agar sesuai dengan aturan-aturan penjadwalan.

Selain itu, ada beberapa aturan yang harus diperhatian dalam membuat jadwal meliputi:

- Satu kelas tidak boleh diisi oleh dua mata pelajaran dalam satu waktu yang sama

- Satu guru tidak boleh mengajar dua mata pelajaran dalam satu waktu yang sama

Faktor-faktor yang menyebakan Algoritma Genetika menjadi metode alternatif sebagai solusi masalah penjadwalan tersebut adalah pemadatan waktu. Pagi hari merupakan waktu yang cukup berharga untuk menambah nilai fitness. Oleh karena itu, penjadwalan dilakukan semenjak pagi untuk menambah alternatif solusi optimum. Berikutnya adalah frekuensi mengajar guru. Penjadwalan menginginkan agar tugas mengajar guru merata setiap harinya. Tidak terlalu padat dan tidak juga terlalu lengang. Hal ini dapat mempengaruhi kinerja mengajar guru yang bersangkutan.

Dengan Algoritma Genetika diharapkan dapat diperoleh penjadwalan mata pelajaran yang optimal yaitu kondisi di mana terjadi kombinasi terbaik untuk pasangan mata pelajaran dan guru pengajar secara keseluruhan, tidak adanya permasalahan tabrakan jadwal baik pada sisi guru, waktu maupun ketersediaan ruang yang cukup secara fasilitas untuk seluruh mata pelajaran. Penjadwalan dapat memberikan solusi yang dapat digunakan oleh guru, siswa, mata pelajaran yang terlibat dalam kegiatan belajar mengajar..

Dengan bantuan Algoritma Genetik penyusunan penjadwalan mata pelajaran dapat dioptimalkan. Program dapat mencari solusi penjadwalan pada waktu yang dapat digunakan baik oleh guru maupun ruangan yang terlibat dalam suatu mata pelajaran. Di samping itu, program dapat meminimalkan tingginya frekuensi mengajar seorang guru. Proses penjadwalan mata pelajaran menggunakan Algoritma Genetik ini dapat diterapkan pada kasus-kasus penjadwalan Dengan menggunakan metode best fitness, maka Algoritma Genetik akan selalu menunjukkan kenaikan fitness atau dengan kata lain generasi selanjutnya lebih baik atau minimal sama dengan generasi sebelumnya.

Dalam kasus ini, Constraint Satisfaction Problem berfungsi sebagai pemberi batasan dalam penjadwalan yang dihasilkan oleh Algoritma Genetika. Metode Algoritma Genetika dipadukan dengan metode Constraint Satisfaction Problem karena kromosom yang dihasilkan pada metode Algoritma Genetika dapat diproses dengan metode Constraint Satisfaction Problem sehingga dapat ditemukan batasan-batasan pada penjadwalan yang harus dipenuhi dengan cepat dan akurat.

Tulisan ini dibuat untuk memenuhi tugas  mata kuliah Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST, MT . Prodi Teknik Informatika Fakultas Teknik UHAMKA.

Referensi:

1. lidya1859.blogspot.co.id/2011/10/algoritma-genetika-dan-metode.html
2. www.scribd.com/document/28430259/Penerapan-Algoritma-Backtracking
3. informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-47.pdf