TUGAS 2 (PROBLEM SOLVING, SEARCH)

Missionaries and Cannibals Problem

Problem adalah kata yang digunakan untuk menggambarkan suatu keadaan yang bersumber dari hubungan antara dua faktor atau lebih yang menghasilkan situasi yang membingungkan. (wikipedia)

Problem didefinisikan dalam 4 item:

1.   Initial State, yaitu memutuskan apa yang harus dilakukan dengan mencari urutan tindakan yang mengarah pada keadaan (state) yang diinginkan

2.    Successor function / Action, yaitu kombinasi dari berbagai "tindakan nyata"

3.    Goal test, yaitu merumuskan tujuan yang ingin dicapai

4.    Path cost, yaitu menetapkan besarnya biaya untuk setiap jalur yang ada.

Penjelasan Game

Game “Missionaries and Cannibals” merupakan salah satu game bergenre puzzle yang terkenal di dunia. Game ini bercerita tentang tiga orang misionaris dan tiga kanibal yang ingin menyebarang sungai. Untuk menyebrangi sungai tersebut disediakan perahu yang dapat digunakan oleh kanibal maupun misionaris. Pemain dikatakan berhasil memainkan permainan ini jika sampai akhir permainan jumlah misionaris dan kanibal masing masing tiga. Dan aturan pokok yang menjadi ciri dari permainan ini, yaitu jumlah kanibal tidak boleh lebih dari jumlah misionari di berbagai sisi. Jika jumlah kanibal lebih banyak dari misionari, maka kanibal akan memakan misionari dan permainan berakhir.

Game ini terasa lebih sulit dimainkan oleh pemain jika diberi aturan-aturan yang harus dipatuhi. ini dia aturan-aturan tersebut:

• Ada tiga misionaris dan tiga kanibal yang harus menyebrang sungai.

• Hanya disediakan satu perahu.

• Perahu bisa berjalan jika ada minimal satu orang atau satu kanibal (satu penumpang).

• Perahu maksimaum berisi dua (1 kanibal/1 misionaris /2 kanibal /2 misionaris) 

• Jumlah kanibal tidak boleh lebih banyak dari jumlah misionaris di salah satu sisi daratan.

• Jika jumlah kanibal lebih banyak dari jumlah misionaris pada suatu sisi daratan maka kanibal akan memakan misionaris. 

• Pemain berhasil menyelesaikan permainan jika semua misionaris dan semua kanibal ada di sisi seberang yang menjadi tujuan. 

Salah satu metode yang dipakai dalam pemecahan masalah pada game missionaries and cannibals ini adalah dengan Breadth First Search (BFS). Secara umum, prinsip pencarian solusi dengan algoritma Breadth First Search (BFS) dimulai dengan simpul akar (simpul akar terlebih dahulu dimasukkan dalam antrian, lalu di pop()), lalu mengekspansi simpul-simpul anak dari dari simpul akar, dan memasukkan simpul anak dalam sebuah antrian. Antrian tadi digunakan untuk memberikan tanda pada simpul – simpul tetangga yang nantinya akan dikunjungi berdasarkan urutan yang ada pada antrian. 

Penjabaran langkah-langkahnya sebagai berikut:

1.    Akar dimasukkan dalam antrian (Simpul paling awal yang akan dikunjungi). 

2.    Simpul yang ada pada awal antrian diambil dan dilakukan pengecekan untuk mengetahui status simpul tersebut sebagai solusi permasalahan atau tidak, dan mengekspansi anak-anaknya jika ada. 

3.    Jika simpul yang sudah dicek tadi merupakan solusi permasalahan, pencarian selesai dan hasil dikembalikan. 

4.    Jika simpul yang sudah dicek sebelumnya bukan merupakan solusi permasalahan, semua simpul yang bertetanggan dengan simpul tadi (simpul anak) dimasukkan kedalam antrian.

5.    Jika antrian ternyata telah kosong dan semua simpul sudah dicek maka status pencarian selesai dan berarti solusi tidak ditemukan. 

6.    Hal ini dilakukan secara berulang (simpul berisi solusi ditemukan/sampai antrian kosong).

Agar mempermudah penggambaran, maka dibuat notasi untuk tiap-tiap simpul/state. Untuk state awal, notasinya adalah `(0,0)|(3,3)K` yang artinya, di sisi kiri ada 0 Misionaris 0 Kanibal, dan disisi kana nada 3 Misionaris, 3 Kanibal dan perahu. State akhir notasinya adalah `K(3,3)|(0,0)`.

Gambar Puzzle:

Runtutan langkah-langkah dari state awal hingga solusi dapat diperolah dengan melakukan backtrack tiap parent dari simpul solusi ke simpul state awal.

Berikut pohon state yang dibuat, dari simpul state awal hingga simpul solusi: 

Kesimpulan

Algoritma Breadth-First Search (BFS) dapat diterapkan dalam berbagai macam masalah untuk melakukan pencarian solusi, salah satunya pada puzzle Missionaries and Cannibals. Algoritma BFS melakukan pencarian pada graf atau pohon dengan cara melebar, yang tentu memerlukan memori dan langkah pencarian yang lebih banyak dibandingkan dengan Depth-First Search (DFS). Keuntungan menggunakan BFS adalah langkah dari state awal ke state akhir optimal (terpendek). 

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:

• https://id.wikipedia.org/wiki/Masalah

• http://slideplayer.info/slide/2379321/

• http://rizalcare.blogspot.co.id/2009/05/tree

• http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-007.pdf

TUGAS 1 PENDAHULUAN

TOPIK 3 : PEAS dalam Intelligent Agent

    Setelah sebelumnya saya telah memposting alat yang menggunakan metode kecerdasan buatan, Pembahasan kali ini adalah teori tentang Intelligent Agent itu sendiri. Apa itu agent? Agent adalah segala sesuatu yang dapat dipandang sebagaimana mengamati lingkungannya melalui sensor dan bertindak atas lingkungan yang melalui efektor. Agen manusia memiliki mata, telinga, dan organ lain untuk sensor. Tangan, kaki, mulut, dan bagian tubuh lainnya untuk efektor.

  Dalam kecerdasan buatan, IA adalah sebuah entitas otonom yang mengamati dan bertindak atas lingkungan (yaitu membutuhkan agen) dan mengarahkan aktivitasnya untuk mencapai tujuan yaitu rasional. (Russel & Norvig 2003) mengartikan Rational Agent yang mengerjakan segala sesuatu hal dengan benar. Agen Intelligent menurut Nikola Kasabov agent harus menunjukan karateristik berikut:

• Mengakomodasi pemecahan masalah baru aturan bertahap
• Beradaptasi online dan real time
• Mampu menganalisis sendiri dalam hal perilaku, kesalahan dan kesuksesan
• Belajar dan meningkatkan melalui interaksi dengan lingkungan (perwujudan)
• Belajar dengan cepat dari sejumlah besar data
• Memiliki penyimpanan memori berbasis contoh dan kapasitas pengambilan
• Memiliki parameter untuk mewakili umur pendek dan jangka panjang memori

 Tugas AI adalah untuk merancang sebuah agent yaitu sebuah fungsi yang mengimplementasikan pemetaaan agen dari persepsi terhadap tindakan. Program ini akan berjalan pada beberapa jenis perangkat komputasi, yang disebut  arsitektur. Secara umum arsitektur membuat persepsi dari sensor yang tersedia untuk program, menjalankan program dan umpan pilihan program aksi terhadap efektor seperti yang dihasilkan.

     Konsep Rasionalitas:

• Rasionalitas ≠ kemahatahuan (omniscience) adalah agent mengetahui akibat yang terjadi dari suatu tindakan

PEAS itu sendiri memiliki arti yang berbeda tergantung pada system apa yang akan dibuat. Menurut Russell & Norvig – bab 2:

PEAS

·         To design a rational agent we must specify its task environment.

·         PEAS description of the environtment:

-          Performance : tindakan yang dilakukan

-          Environment : berhubungan dengan lingkungan

-          Actuators : alat yang digunakan

-          Sensors : pancaindera dari alat tersebut

PEAS - contoh 1, Taxi Otomatis:

Definisi lingkungan berdasarkan PEAS

-          Performance

Keamanan, tujuan, keuntungan, kelegalan,kenyamanan..

-          Environment

Jalan protocol, jalan lainnya, trotoar, cuaca..

-          Actuators

Kemudi, akselerasi, rem, klakson, speaker..

-          Sensors

Video, sonar, speedometer, engine sensors, keyboard, GPS..

PEAS – contoh 2, Sistem Diagnosis Medis:

Definisi lingkungan berdasarkan PEAS

-          Performance measure

Kesembuhan pasien, biaya minim, sengketa..

-          Environment

Pasien, pegawai, rumah sakit..

-          Actuators

Layar monitor (pertanyaan, test, perawatan, rujukan)

-          Sensors

Keyboard (gejala, temuan, pertanyaan pasien)

PEAS – contoh 3, Part-picking robot:

Definisi lingkungan berdasarkan PEAS

-          Performance measure

Komponen pada tempat penampungan yang sesuai

-          Environment

Conveyor belt with parts, bins

-          Actuators

Jointed arm and hand

-          Sensors

Camera, joint angle sensors

Simple Reflex Agents

Agen reflex sederhana merupakan agen yang paling sederhana karena hanya menerapkan teknik kondisi-aksi. Jadi, jika terjadi tertentu maka agen akan secara sederhana memberikan aksi tertentu.

Model-Based Reflex Agents

Agen reflex sederhana dapat melakukan tindakanya dengan baik jika lingkungan yang memberikan kesan tidak berubah-ubah. Misalkan untuk kasus agen pengendara taxi, agen tersebut hanya dapat menerima kesan dari mobil dengan model terbaru saja. Jika mobil model lama, agen tersebut tidak bias menerima kesannya sehingga agen tersebut tidak melakukan tindakan pengereman. Agen reflex model ini menjaga keadaan dunianya menggunakan model internal kemudian memilih tindakan seperti agen reflex sederhana.

Model-based, goal-based agent

Suatu agen tertentu harus diberikan informasi tentang tujuan yang merupakan keadaan yang ingin dicapai oleh agen. Dengan demikian, agen akan bekerja hingga mencapai tujuannya. Pencarian dan perencanaan adalah dua deretan pekerjaan yang dilakukan untuk mencapai tujuan agen. Agen refleks berbasis tujuan ini menambahkan informasi tentang tujuan tersebut.

Model-Based Utility-Based Agents

Agen refleks berbasis tujuan tidak membedakan keadaan yang bagus dengan keadaan yang tidak bagus untuk agen. Pada agen refleks berbasis kegunaan ini memikirkan kondisi yang bagus untuk agen sehingga agen dapat melakukan tugasnya jauh lebih baik.

Learning Agent

Learning agents belajar dari pengalaman, meningkatkan kinerja bertanggung jawab untuk membuat perbaikan elemen kinerja bertanggung jawab untuk memilih tindakan eksternal kritikus memberikan umpan balik tentang bagaimana agen bekerja.

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:

•  http://artikel-teknologi-informasi.blogspot.co.id/2012/11/pengertian-agent-pada-ai-artificial.html

•  http://hadieswd.blogspot.co.id/2015/03/kecerdasan-buatan-intelligent-agents.html

•  Artificial Intelligence A Modern Approach (3rd Edition)

•  http://slideplayer.info/slide/2891046/

•  http://slideplayer.info/slide/2602854/

TUGAS 1 PENDAHULUAN

SISTEM PAKAR DIAGNOSA PENYAKIT DIABETES MELLITUS MENGGUNAKAN METODE FORWARD CHAINING BERBASIS WEB

1. Latar Belakang Gan..

Setiap hari bahkan tahun pertambahan penderita Diabetes makin meningkat. Berdasarkan data yang dihimpun oleh WHO (World Health Organization), Secara mengejutkan Indonesia berada pada urutan ke-4 untuk jumlah penderitanya di dunia.  Tentunya ini bukan kabar yang menggembirakan, dari data tahun 2006, jumlah penderita Diabetes Mellitus di Indonesia kurang lebih 14 juta jiwa. Dari jumlah itu baru 50% yang tahu tanpa dilakukan tindakan dan sekitar 30% diantaranya melakukan pengobatan secara teratur. Menurut penelitian epidemiologi, prevalensi diabetes di Indonesia berkisar antara 1,5% sampai 2,3%.

Klasifikasi etiologis Diabetes Mellitus menurut ADA tahun 2005 yaitu:

·         Diabetes Mellitus tipe 1

·         Diabetes Mellitus tipe 2

·         Diabetes Mellitus tipe lain

·         Diabetes Mellitus kehamilan

        Di Indonesia, belum diketahui secara pasti jumlah kasus Diabetes Mellitus tipe 1. Hal ini karena letak geografis Indonesia berada di khatulistiwa atau factor genetik yang tidak mendukung. Beda dengan Diabetes Mellitus tipe 2 yang meliputi lebih dari 90% jumlah populasi penderita diabetes, factor lingkungan sangat berperan (Sudoyo, 2006). Tanpa disadari jika dibiarkan penyakit ini akan mengakibatkan gangguan kesehatan yang lebih parah. Peningkatan jumlah penyakit ini disebabkan oleh pola hidup tak sehat dan berimbang serta keterlambatan penanganan diagnosis.

        Oleh karena itu diperlukan segera sistem sebagai alat bantu dalam diagnosa untuk menentukan pasien itu mengidap Diabetes Mellitus atau tidak. Sistem yang digunakan adalah Sistem pakar diagnosa penyakit Diabetes Mellitus dengan metode forward chaining. Dalam hal ini system pakar merupakan salah satu teknik kecerdasan buatan yang dapat menirukan proses penalaran manusia menawarkan hasil yang lebih spesifik untuk dimanfaatkan karena system pakar berfungsi secara konsisten seperti memberi dokter memberi nasihat dan menemukan solusi terhadap pemecahan masalah penyakit Diabetes Mellitus.

        2. Tujuannya Gan..

Sistem dapat mendiagnosa penyakit Diabetes Mellitus dan memberikan solusinya berdasarkan gejala yang dirasakan pasien atau user dengan metode forward chaining. Dan sistem dapat menyediakan layanan akses informasi mengenai penyakit Diabetes Mellitus dan informasi layanan diagnose serta solusinya.

        3. Metode

Perkalian inferensiasi yang menghubungkan masalah dan solusi disebut rantai (chain). Suatu rantai yang dicari atau dilewati dari masalah untuk mendapat solusi disebut forward chaining. Sedangkan suatu rantai yang dilintasi dari hipotesa kembali ke fakta yang mendukung hipotesa tersebut adalah backward chaining. Metode pemecahan masalah dalam system pakar adalah arah penelusuran dan topologi penelusuran.

        4. Hasilnya Gan..

Setelah pembuatan aplikasi identifikasi penyakit Diabetes Mellitus berdasarkan sistem pakar dilakukan, dapat dilihat sejauh mana aplikasi tersebut dapat diterima masyarakat. Hasilnya didasarkan pada:

·      Aplikasi sistem pakar keseluruhan

·      Kemudahan pemakaian

·      Kecepatan dalam memproses masalah

·      Hasil akurat dari penyakit itu sendiri

       5. Kesimpulan

·   Penggunaan metode forward chaining dengan proses penelusuran dapat digunakan untuk pembuatan Sistem Pakar Diagnosa Penyakit Diabetes Mellitus.

·    Keluaran dari sistem adalah diagnose berupa tipe penyakit diabetes mellitus dengan disertai solusi untuk penyembuhan penyakit.

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 :

Skripsi “SISTEM PAKAR DIAGNOSA PENYAKIT DIABETES MELLITUS MENGGUNAKAN METODE FORWARD CHAINING BERBASIS WEB”, Halim Perdana Putra-0903015063, 2014.