PLANNING GRAPH & POP SOLUTION..

Penyelesaian selanjutnya dari planning ini adalah:

2. Birthday Dinner (Graph Plan)

Langkah awal dengan meletakkan di kondisi awal.

 Masukan action yang dapat dilakukan dan hubungkan dengan Initial State.

 Setelah itu, masukan hasil dari action yang dapat kita lakukan.

 

Selanjutnya, membuat mutex dari Graph Plan ini, alasannya bahwa tindakan dapat mutex adalah karena efek yang tidak konsisten. Dapat dilihat Clean mutex dengan Carry membuat Clean menjadi salah. Begitu juga dengan Garbage mutex dengan Carry dan Dolly membuat Garbage menjadi salah. Begitu juga dengan Quiet mutex dengan Dolly membuat quiet menjadi salah.

 

Alasan lain dari mutex adalah karena adanya gangguan: suatu action meniadakan precondition dari action lain. Dapat dilihat Carry mutex dengan Cook dan Dolly dan meniadakan precondition hasilnya, begitu juga dengan Wrap mutex dengan Dolly dan meniadakan precondition hasilnya

 

Pertama-tama, setiap proposisi mutex dengan bentuk yang negatif. Kemudian Karena alasan lain dari mutex adalah karena dukungan tidak konsisten. Jadi, Garbage mutex dengan not Clean dan not Quiet (karena untuk mendapatkan Garbage kita harus mempertahankan itu, yang mutex dengan Carry dan Dolly). Dinner mutex dengan not Clean (karena Cook dan Carry mutex pada level sebelumnya). Present mutex dengan not Quiet (karena Warp dan Dolly mutex pada level sebelumnya). Begitu juga dengan not Clean dan not Quiet (karena Carry dan Dolly mutex pada level sebelumnya).

 

Kita coba dengan cara lain, kita akan mendapatkan not Garbage dengan action Carry, dan Dinner dengan action Cook, tetapi Carrry dan Cook mutex jadi gagal.

 

Coba dengan cara lain, kita akan mendapatkan not Garbage dengan action Dolly, dan Dinner dengan action Cook, serta Present dengan action Wrap, tetapi Doly dan Wrap mutex.

 

Dikarenakan tidak ada cara lain untuk mendapatkan goal kita akan menggunakan depth two plan, yaitu menambahkan dua level lagi pada Graph.

 

Pada tahap ini kita mendapatkan mutex sama seperti di level sebelumnya

 

Pada level ini kita juga mendapatkan mutex yang sama dengan level sebelumnya, tetapi terdapat perbedaan yaitu pada level ini Dinner tidak mutex dengan Carry,karena kita bisa mendapatkan Dinner dengan membiarkannya dan tetap bisa melakukan Carry. Begitu juga dengan Present tidak mutex dengan Dolly karena kita bisa mendapatkan Present dengan membiarkannya dan dapat tetap melakukan Dolly.

 

Setelah selesai dengan mutex, kita mencari lagi dengan cara seperti gambar diatas dan akhirnya dapat berhasil dengan cara seperti yang ditunjukan oleh gambar diatas.

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. http://whitenote03.blogspot.co.id/2016/10/penyelesaian-masalah-menggunakan.html
2. http://dantikpuspita.com/konsep-dan-pengertian-dasar-graph-graf/
3. https://ocw.mit.edu/...and.../Lecture12FinalPart1.pdf
4. https://en.wikipedia.org/wiki/Graphplan  

PLANNING GRAPH & POP SOLUTION..

Di pembahasan kali ini saya akan membahas penyelesaian suatu contoh kasus Planning dengan menggunakan Partial Order Planning dan Graph Plan.

Apa itu planning?

Planning adalah suatu metode penyelesaian masalah dengan cara memecah masalah ke dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadi sebuah solusi lengkap dengan tetap mengingat dan menangani interaksi yang ada antar sub masalah.  Berikut ini adalah contoh dari permasalahan dan solusi jawabannya..

1. Shopping (POP)

 
Langkah awal:

 

Tahap selanjutnya menambahkan go(HDW) sebagai (X1) untuk mencapai untuk mencapai at(HDW) dan menambahkan go(SM) sebagai (X₂) untuk mencapai at(SM).

Langkah selanjutnya kita bisa menjalankan langkah actian go(X₁) dan precond Go(HDW), dengan menggunakan effect at(Home). Serta menjalankan langkah action go(X₂) dan precond Go(SM), dengan menggunkan effect at(Home) seperti gambar diatas.

Setelah selesai dengan langkah sebelumnya, kita harus memperhatikan masalah apa saja yang mungkin terjadi yang bisa kita lihat pada gambar diatas. Pada gambar diatas, masalah terjadi dapat kita lihat pada bulatan yang ditunjuk oleh tanda panah, kita dapat memperhatikan bahwa Go(SM) tidak bisa tersambung ke at(Home) sebagai akibat sudah dimiliki oleh at(X₁), dan juga berlaku sebaliknya untuk Go(HDW).

 

Solusi yang dapat kita ambil, mungkin kita bisa memerlukan Go(SM) terjadi setelah Go(HDW). Kita bisa memutuskan untuk memenuhi at(X₂) dengan hasil at(HDW) Go(HDW) dan at(HDW) Go(HDW), tetapi jika kita menuju at(HDW) Go(HDW) kita tidak bisa menuju at(HDW) Sells(HDW,D).

Solusi yang dapat kita ambil dengan menempatkan Go(SM) antara GO(HDW) dan at(HDW) yang ditunjukan oleh tanda panah pada gambar diatas. Tetapi jika seperti itu kita harus menuju dua kali ke Go(HDW) karena sehabis ke Go(HDW) kita menuju Go(SM) dan balik lagi ke Go(HDW) untuk Buy(Drill).

Solusi yang dapat diambil dengan meletakan Go(SM) terjadi setelah Buy(Drill). Dengan menandakan nya dengan garis putus putus berwarna merah untuk memastikan bahwa hal ini terjadi.

Setelah kita berada di GO(SM) kita bisa Buy(Milk) dan Buy(Bananas) dan terakhir menuju at(Home).

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. http://whitenote03.blogspot.co.id/2016/10/penyelesaian-masalah-menggunakan.html
2. http://dantikpuspita.com/konsep-dan-pengertian-dasar-graph-graf/
3. https://ocw.mit.edu/...and.../Lecture12FinalPart1.pdf
4. https://en.wikipedia.org/wiki/Graphplan  

CONSTRAINT SATISFACTION PROBLEM..

Assalamualaikum sahabat ku yang baik hatinya!

Kali ini saya akan membahas tentang 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.

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 Kuliah.
Dalam proses penjadwalan mata kuliah ada beberapa hal yang harus diperhatikan:

• Pertama, terdapat jadwal-jadwal di mana dosen yang bersangkutan tidak bisa mengajar. 
• Kedua, distribusi jadwal perkuliahan diharapkan dapat merata tiap harinya untuk setiap kelas. 
• Ketiga, pekerjaan penjadwalan mata kuliah ini akan semakin berat jika melibatkan semakin banyak kelas per angkatannya. 
• Keempat, terdapat mata kuliah 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 kuliah, dosen, 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:

-          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.

-          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.

-          Waktu

Waktu merupakan batasan berapa menit yang diperlukan untuk satu sks mata kuliah. Selain itu, perkuliahan dibatasi dari hari Senin sampai hari Sabtu dan setiap harinya pun dibatasi mulai jam 07.30 sampai jam 22.00. Dengan batasan-batasan waktu ini, jadwal hanya akan berada pada waktu yang ditentukan.

-          Matakuliah

Mengingat setiap matakuliah memiliki semester mata kuliah itu diajarkan, maka perlu adanya aturan yang membatasi penjadwalan mata kuliah, agar mata kuliah itu sesuai dengan aturan-aturan penjadwalan.

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

- Satu ruang tidak boleh diisi oleh dua mata kuliah dalam satu waktu yang sama

- Satu dosen tidak boleh mengajar dua mata kuliah 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 dosen. Penjadwalan menginginkan agar tugas mengajar dosen merata setiap harinya. Tidak terlalu padat dan tidak juga terlalu lengang. Hal ini dapat mempengaruhi kinerja mengajar dosen yang bersangkutan.

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

Dengan bantuan Algoritma Genetik penyusunan penjadwalan mata kuliah dapat dioptimalkan. Program dapat mencari solusi penjadwalan pada waktu yang dapat digunakan baik oleh dosen maupun ruangan yang terlibat dalam suatu mata kuliah. Di samping itu, program dapat meminimalkan tingginya frekuensi mengajar seorang dosen. Proses penjadwalan mata kuliah menggunakan Algoritma Genetik ini dapat diterapkan pada kasus-kasus penjadwalan dengan multi angkatan dan multi ruangan. 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.

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

Solusi dengan algoritma greedy:

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.

Referensi:

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
4. nurmaghany.blogspot.co.id/2012/01/knapsack-algoritma.html