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

TUGAS BONUS

 SOLUSI KNAPSACK PROBLEM DENGAN METODE GREEDY

   Di kehidupan sehari-hari, kita sering dipusingkan dengan media penyimpanan yang terbatas padahal diharuskan menyimpan beberapa objek kedalam media tersebut. Bagaimana caranya mengatur objek yang dipilih dan seberapa besar objek tersebut disimpan?

Dari permasalahan tersebut, munculah suatu permasalahan yang dikenal dengan “Permasalahan Knapsack” atau “Knapsack Problem”. Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum.

Jenis-Jenis Knapsack Problem:

·         0/1 Knapsack problem
Setiap barang hanya tersedia 1 unit, take it or leave it.

·         Fractional Knapsack problem
Barang boleh dibawa sebagian saja (unit dalam pecahan). Versi problem ini menjadi masuk akal apabila barang yang tersedia dapat dibagi-bagi misalnya gula, tepung, dan sebagainya.

·         Bounded Knapsack problem
Setiap barang tersedia sebanyak N unit (jumlahnya terbatas).

·         Unbounded Knapsack problem
Setiap barang tersedia lebih dari 1 unit, jumlahnya tidak terbatas

Nah, dalam menyelesaikan masalah ini saya akan menggunakan Metode Greedy. Apa itu Greedy? Definisi : Metode yang digunakan untuk memecahkan persoalan optimasi dengan pencarian solusi optimum. 

   Ada 2 macam persoalan optimasi:

  

   1.  Maksimasi (maximization)
   2.  Minimasi (minimization)

Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin. Prinsip greedy: “take what you can get now!”.

 metode greedy memiliki 3 pilihan strategi pengangkutan, yaitu:

1. Greedy by Profit

Strategi ini mengharapkan keuntungan maksimal dengan cara memasukan barang atau objek dengan nilai keuntungan terbesar terlebih dahulu ke dalam kantong atau knapsack. Jadi strategi ini hanya mempertimbangkan jumlah keuntungan dari sekumpulan barang, dengan catatan berat barang yang akan dibawa tidak melebihi kapasitas kantong yang kita miliki.

2. Greedy by weight 

Pada strategi ini, kita berusaha memasukan barang sebanyak-banyaknya kedalam kantong, jadi barang atau objek yang dimasukan terlebih dahulu adalah barang dengan bobot paling ringan terlebih dahulu, dengan harapan dengan banyaknya barang atau objek yang terangkut kita bisa mendapatkan keuntungan sebesar-besarnya.

3. Greedy by density

Strategi ini mengharapkan keuntungan sbesar-besarnya dengan memasukan barang  yang memiliki keuntungan per unit terbesar (Pi/Wi) terlebih dahulu kedalam kantong. 

Contoh 1:

Tinjau persoalan 0/1 Knapsack dengan n = 4. w₁ = 6;   p₁ = 12

                        w₂ = 5;    p₁ = 15

                        w₃ = 10;  p₁ = 50

                        w₄ = 5;    p₁ = 10

                        Kapasitas knapsack W = 16

Properti objek				Greedy by			Solusi Optimal
I	wi	pi	pi /wi	profit	weight	density
1	6	12	2	0	1	0	0
2	5	15	3	1	1	1	1
3	10	50	5	1	0	1	1
4	5	10	2	0	1	0	0
Total bobot				15	16	15	15
Total keuntungan				65	37	65	65

Pada contoh 1, algoritma greedy dengan strategi pemilihan objek berdasarkan profit dan density memberikan solusi optimal, sedangkan pemilihan objek berdasarkan berat tidak memberikan solusi optimal.

Contoh 2:

persoalan  Knapsack lain dengan 6 objek:

w₁ = 100;  p₁ = 40

                        w₂ = 50;    p₂ = 35

                        w₃ = 45;    p₃ = 18

                        w₄ = 20;    p₄ = 4

w₅ = 10;    p₅ = 10

                        w₆ = 5;      p₆ = 2

                        Kapasitas knapsack W = 100

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi /wi	profit	weight	density
1	100	40	0,4	1	0	0	0
2	50	35	0,7	0	0	1	1
3	45	18	0,4	0	1	0	1
4	20	4	0,2	0	1	1	0
5	10	10	1,0	0	1	1	0
6	5	2	0,4	0	1	1	1
Total bobot				100	80	85	100
Total keuntungan				40	34	51	55

Pada contoh 2, terlihat algoritma greedy dengan ketiga strategi pemilihan objek tidak berhasil memberikan solusi optimal.  Solusi optimal permasalah ini adalah X = (0, 1, 1, 0, 0, 0) dengan total keuntungan = 55.

Kesimpulan: Algoritma greedy tidak selalu berhasil menemukan solusi optimal untuk masalah 0/1 Knapsack.

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.

Solusi dengan algoritma greedy:

  Refrensi 

1. hendryprihandono.wordpress.com/2009/01/03/knapsack-problem-dengan-algoritma-dan-metode-greedy/
2. kevinkarundeng.wordpress.com/2012/11/05/contoh-soal-algoritma-greedy-dan-knapsack-problem/
3. bloglogika.blogspot.co.id/2011/01/knapsack-problem.html