4. METODE PENCARIAN DAN PELACAKAN 1

Searching di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.
Teknik searching sendiri terbagi menjadi dua, yaitu:

1.       Blind searching

2.       Heuristic searching 

4.1 Metode Pencarian Buta (Blind Search)

Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:

·         Membangkitkan simpul berdasarkan urutan.

·         Kalau ada solusi maka solusi akan ditemukan.

·         Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

4.1.1 Breadth First Search

BFS (Breadth First Search) yaitu model pencarian yang memakai metode melebar. Untuk mencari hasilnya, model BFS ini menggunakan teknik pencarian persoalannya dengan cara membuka node (titik) pada tiap levelnya. Dimulai pada node n, dan dilanjutkan n+1. Pencarian akan terus dilakukan dari akar kiri ke kanan hingga hasil ditemukan. Metode ini memiliki keuntungan dan kekurangan, yaitu:

Ø  Keuntungan:

·         Tidak akan menemui jalan buntu.

·         Jika ada satu solusi, maka breadth first akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

Ø  Kekurangan:

·         Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.

·         Membutuhkan waktu yang cukup lama karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1).

4.1.2 Depth First Search

DFS (Depth-first Search) sering disebut juga pencarian mendalam. Sesuai dengan namanya “pencarian mendalam”, DFS tidak mencari solusi per level. Metode ini melakukan pencarian pada semua node "anaknya" sebelum dilakukan pencarian ke node-node lain yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi, dan proses terus diulang hingga solusi ditemukan. DFS memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node dan jika pencarian tepat, akan menemukan solusi tanpa harus menguji lebih banyak node. Namun, metode ini tetap memiliki kelemahan, yaitu memungkinkan hasil tidak ditemukan, dan setiap 1 kali pencarian hanya akan menghasilkan satu solusi.

4.2 Metode Pencarian Heuristik

Heuristic Search merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan). Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu. Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).
Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).
Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

4.2.1 Generate and Test

Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang akan dibicarakan. Ini adalah gabungan dari pencarian depth first dengan pelacakan mundur. Nilai dari pengujian ini berupa "ya" atau "tidak".
Pendekatan ini meliputi langkah–langkah sebagai berikut :

1. Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.
2. Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).
3. Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.

Jika pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya (bila ada).  Namun, jika ruang problema sangat besar, maka proses ini akan membutuhkan waktu yang lama.
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.

4.2.2 Hill Climbing

Hill Climbing (mendaki bukit) merupakan salah satu variasi metode buat dan uji (generate and test) dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search). Perbedaannya ada pada feedback dari prosedur test untuk pembangkitan keadaan berikutnya. Tes yang dilakukan berupa fungsi heuristik akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap keadaan lain yang memungkinkan.
Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah ya atau tidak. Dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :

1. Buatlah solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke langkah berikutnya.
2. Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.
3. Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :
1. Kirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.
2. Jika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah.
3. Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan.
4. Kembalilah ke langkah 2.

Masalah-masalah yang mungkin timbul pada prosedur Hill Climbing :

·         Maksimum lokal adalah suatu keadaan yang lebih baik daripada semua tetangganya namun masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya.

·         Daratan  (Plateau) adalah suatu daerah datar dari ruang pencarian (search) dimana semua himpunan keadaan tetangganya memiliki nilai yang sama.

·         Punggung (Ridge) adalah suatu daerah ruang pencarian (search) yang lebih tinggi daripada daerah sekitarnya, namun tidak dapat dibalikkan oleh langkah–langkah tunggal ke arah manapun.

Solusinya:

·         Melakukan langkah balik (backtracking) ke simpul yang lebih awal dan mencoba bergerak ke arah yang lain.

·         Melakukan lompatan besar ke suatu arah untuk mencoba bagian ruang pencarian yang baru.

·         Menerapkan dua atau lebih aturan sebelum melakukan uji coba. Ini bersesuaian dengan bergerak ke beberapa arah sekaligus.

Kelemahan pada sistem ini adalah algoritma akan berhenti ketika mencapai optimum local, urutan penggunaan operator akan sangat berpengaruh, dan tidak diijinkan untuk melihat langkah sebelumnya.

Referensi:

http://adamspahalerang.blogspot.co.id/2012/10/analisa-teknik-searching-dalam.html

http://buatugasai.blogspot.co.id/2013/04/metode-pencarian-dan-pelacakan_4.html  

http://www.scribd.com/doc/52500558/Metode-Pencarian-Dan-Pelacakan-prolog

http://www.slideshare.net/ceezabramovic/metode-pencarian-heuristik

3. PENGENALAN LOGICAL AGENTS

Logic merupakan jantung dari program, para pemrogram mempunyai keyakinan bahwa sebuah komputer dapat dibuat mengerti logika, maka computer dapat dibuat untuk berfikir, karena logika kelihatannya menjadi inti dari kecerdasan.

1  Problem solving agent hanya bisa menyelesaikan masalah yang lingkungannya accessible.

2  Kita membutuhkan agen yang dapat menambah pengetahuan dan menyimpulkan keadaan.

3  Agent yang akan membantu seperti ini kita beri nama knowledge based agent.

3.1 Knowledge Based Agents

Komponen utama dari knowledge based agent adalah knowledge basenya. Knowledge base (KB) adalah kumpulan representasi fakta tentang lingkungan atau dunia yang berhubungan atau menjadi daerah bekerjanya agen. Setiap representasi dalam KB disebut sebagai sebuah kalimat yang diekspresikan dalam sebuah bahasa yakni knowledge representation language.

Ø  Representasi Pengetahuan yang bersifat general.

Ø  Kemampuan beradaptasi sesuai temuan fakta.

Ø  Kemampuan menyimpulkan sesuatu dari pengetahuan yang sudah ada.

Syarat Representasi KB:

1.       Representational Adequacy
Kemampuan merepresentasikan semua pengetahuan yang dibutuhkan dalam domainnya

2.       Inferential Adequacy
Kemampuan memanipulasi struktur pengetahuan untuk membentuk struktur baru dalam menampung pengetahuan baru hasil inferens.

3.        Inferential Efficiency
Kemampuan untuk manambahkan informasi untuk mempercepat pencarian dalam inferensi.

4.       Acquisitional Efficiency
Kemampuan untuk menambah informasi baru secara mudah.

Pengetahuan yang dimiliki agent tidak berguna jika ia tidak melakukan apapun karenanya kita perlu menambahkan aturan agar dia dapat bergerak (complete the knowledge base). Beberapa tahapan yang dilakukan dalam menyusun knowledge based agent:

Ø  Untuk dapat menyusun sebuah knowledge based agent maka kita harus terlebih dulu bisa menyusun knowledge basenya itu sendiri.

Ø  Untuk menyusun knowledge base kita perlu menentukan bagaimana cara kita merepresentasikan pengetahuan kita (knowledge representation).

Ø  Knowledge representation kita harus merupakan bentuk yang mudah disimpan dan digunakan pada komputer. Dalam perkuliahan ini kita menggunakan beberapa macam knowledge representation language.

3.2 Wumpus World

Ø  Environment sederhana, berguna untuk menguji dan menjelaskan logical agent.

Ø  Gua gelap dengan banyak ruangan yang dihubungkan dengan lorong-lorong.

Ø  Agent masuk ke gua untuk mengambil emas yang ada di salah satu ruangan.

Ø  Wumpus (monster) bersembunyi di salah satu ruangan. Jika agent bertemu, ia akan menjadi santapannya.

Ø  Terdapat ruang-ruang yang memiliki lubang jebakan yang dapat membunuh agent.

Ø  Agent hanya punya 1 panah yang bisa membunuh wumpus dari jarak jauh.

Sifat dari Wumpus World:

Ø  Fully observable? Tidak, hanya bisa berpresepsi lokal.

Ø  Deterministic? Ya, hasil tindakan jelas dan pasti.

Ø  Episodic? Tidak, tergantung action sequence.

Ø  Static? Ya, gold, wumpus, pit tidak bergerak.

Ø  Discrete? Ya.

Ø  Single agent? Ya.

3.3 Logic in general-Models and Entailment

Logics adalah bahasa formal untuk merepresentasikan fakta sedemikian shg kesimpulan (fakta baru, jawaban) dapat ditarik. Ada banyak metode inference yang diketahui. Kita bisa membangun agent Wumpus World dengan logika: memanfaatkan perkembangan logika oleh ahli matematika, filsafat selama ratusan tahun.

Entailment artinya bahwa sesuatu mengikuti dari yang lain.

KB ╞

·         Knowledge base KB entails kalimat α jika dan hanya jika α adalah true pada semua dunia dimana KB bernilai true.

·         Misal, KB “the Giants won” dan “the Reds won”  entails “Either the Giants won or the Reds won”

·         Misal, x+y = 4 entails 4 = x+y

Entailment adalah sebuah hubungan antar kalimat (syntax) yang didasarkan pada semantik.

Models à m adalah sebuah  model pada sebuah kalimat α jika α bernilai true pada m

·         M(α) adalah kumpulan semua model pada α.

·         KB ╞ α iff M(KB) Í M(α).

·         Misal: KB = Giants won and Reds won , α = Giants won

Referensi:

https://rinnooberta.wordpress.com/2013/10/18/2-logical-agents/

http://slidegur.com/doc/3649399/pertemuan-ix  

http://slideplayer.info/slide/3300290/

http://share.its.ac.id/pluginfile.php/1369/mod_resource/content/1/8._Propotional_Logic.pdf

2. PENGENALAN INTELLIGENT AGENTS

Pengertian sebuah Agents adalah segala sesuatu yang dipandang sebagaimana mengamati lingkungannya melalui sensor dan bertindak atas lingkungan yang melalui efektor. Agen manusia memiliki mata, telinga, dan organ lain untuk sensor, dan tangan, kaki, mulut, dan bagian tubuh lainnya untuk efektor. Sebuah pengganti agen robot kamera dan berbagai pencari inframerah untuk sensor dan berbagai motor untuk efektor.

2.1 Agents dan Lingkungannya

•  Agents adalah segala sesuatu yang dapat melihat/ mengartikan/ mengetahui (perceiving) linkungannya melalui alat sensor (sensors) dan bertindak (acting) melalui alat aktuator (actuators)

•  Manusia sebagai agent : mata, telinga dan organ lainnya sebagai sensors; tangan, kaki, mulut dan bagian tubuh lainnya sebagai actuators

• Robot sebagai agent : kamera dan pejejak infra merah sebagai sensors; berbagai motor pengerak sebagai actuators
•  Software sebagai agent : tekanan pada keyboard, isi file dan paket paket pada jaringan sebagai masukan sensors; tampilan pada layar, penulisan file dan pengiriman paket jaringan sebagai keluaran actuators.

• Fungsi agent (f) adalah pemetaan dari urutan persepsi (percept) menjadi tindakan (actions)

[f: P* -> A]

• Program agent berjalan pada arsitektur fisik untuk menghasilkan fungsi agent (f) agent = architecture + program

2.2 Rasionalitas

Sebuah agen haruslah mengarah kepada “lakukan hal yang benar", berdasarkan kepada apa yang dapat dipahaminya dan tindakan yang dapat dilakukannya. Tindakan yang benar adalah tindakan yang akan menyebabkan agen tersebut paling berhasil. Pengukuran Performance: Sebuah kriteria objektif untuk keberhasilan sebuah perilaku agen.

Misalnya: Ukuran performance dari sebuah agen vacuum-cleaner dapat berupa besarnya jumlah debu yang dibersihkan, jumlah waktu yang dihabiskan, jumlah listrik yang dikonsumsi, jumlah kebisingan yang dihasilkan, dll.

Agen rasional : Untuk setiap deretan persepsi yang mungkin, sebuah agen rasional hendaklah memilih satu tindakan yang diharapkan memaksimalkan ukuran performance-nya, dengan adanya bukti yang diberikan oleh deretan presepsi dan apapun pengetahuan terpasang yang dimiliki agen itu.

Rasionalitas berbeda dari omniscience (tahu segala/all-knowing dengan pengetahuan tak berhingga).

Agen dapat melakukan tindakan untuk memodifikasi persepsi masa depan sedemikian hingga dapat memperoleh informasi yang berguna (pengumpulan informasi, eksplorasi)

Sebuah agen adalah otonom (autonomous) apabila perilakunya ditentukan oleh pengalamannya sendiri (dengan kemampuan belajar dan beradaptasi).

2.3 PEAS (Performance Measure, Environment, Actuators, Sensors)

Pertama-tama harus menentukan pengaturan untuk desain agen cerdas.

Pertimbangkan, misalnya Agen:  Tugas merancang supir taksi otomatis.

·         Performance measure: Aman, cepat, legal, perjalanan menyenangkan, maksimumkan keuntungan.

·         Environment: Jalan, trafik lain, pejalan kaki, pelangan.

·         Actuators: Kemudi, gas, rem, lampu sign, horn.

·         Sensors: Kamera, sonar, speedometer, GPS, odometer, engine sensors, keyboard.

Agen:  Sistem pendiagnosa medis.

·       Performance measure: Pasien sehat, biaya minimal, sesuai aturan/hukum (lawsuits).

·       Environment: Patient, hospital, staff.

·       Actuators: Screen display (questions, tests, diagnoses, treatments, referrals).

·       Sensors: Keyboard (entry of symptoms, findings, patient's answers)

Agent: Robot pengutip-sukucadang

·      Performance measure: Persentase suku cadang dalam kotak yang benar.

·      Environment: ban berjalan dengan suku cadang, kotak.

·      Actuators: Pergelangan dan tangan tersambung.

·      Sensors: Kamera, joint angle sensors.

Agen: Tutor Bahasa Inggeris Interaktif

• Performance measure: Memaksimalkan nilai mahasisa pada waktu ujian.
• Environment: Sekumpulan mahasiswa.
• Actuators: Layar display (exercises, suggestions, corrections).
• Sensors: Keyboard.

2.4 Tipe-Tipe Lingkungan Agen

Ø  Fully observable (vs. partially observable): Sensor-sensor sebuah agen memberinya akses ke keadaan lengkap lingkungannya pada setiap jangka waktu.

Ø  Deterministic (vs. stochastic): Keadaan lingkungan berikutnya sepenuhnya ditentukan oleh keadaan sekarang dan tindakan yang dilaksanakan oleh agen. (Jika lingkungan itu deterministik kecuali untuk tindakan agen-agen lain, maka lingkungannya adalah strategic).

Ø  Episodic (vs. sequential): Pengalaman agen dibagi kedalam "episode-episode" atomik (setiap episode terdiri dari si agen memahami (perceiving) dan kemudian melaksanakan satu tindakan, dan pilihan tindakan dalam tiap episode hanya tergantung pada episode itu sendiri.

Ø  Static (vs. dynamic): Lingkungan tidak berubah selagi agen direncanakan (deliberating). (Lingkungan adalah semidynamic jika lingkungan itu sendiri tidak berubah dengan berjalannya waktu tetapi skor performa agen berubah).

Ø  Discrete (vs. continuous): Sejumlah terbatas persepsi dan tindakan yang khas dan terdefinisi baik.

Ø  Single agent (vs. multiagent): Sebuah agen yang mengoperasikan dirinya sendiri dalam sebuah lingkungan.

Tipe lingkungan sangat menentukan rancangan agen. Dunia nyata (tentu saja) partially observable, stochastic, sequential, dynamic, continuous, multi-agent.

  

2.5 Tipe-Tipe Agen

Perilaku agen: tindakan yang dilakukan setelah diberikan sembarang sekuen persepsi.

Ø  Tugas AI adalah merancang program agen yang mengimplementasikan fungsi agen yang memetakan persepsi ke tindakan.

Ø  Diasumsikan program ini berjalan di beberapa alat komputasi yang dilengkapi sensors dan actuators (disebut arsitektur). Agent = arsitektur + program.

Ø  Program yang dipilih harus sesuai dengan arsitektur tersebut.

Cth: Action: Walk à arsitekturnya hendaklah memiliki kaki.

Empat jenis dasar untuk menambah generalitas:

o    Simple reflex agents

o    Model-based reflex agents

o    Goal-based agents

o    Utility-based agents

Referensi:

https://yanneevelynip.wordpress.com/2013/10/20/intelligent-agent-kecerdasan-buatan/

http://nisayuniza.blogspot.co.id/2015/04/kecerdasan-buatan-intelligent-agents.html