Bab 4 Metode Pencarian dan pelacakan 1

BAB 4

Metode Pencarian dan Pelacakan 1

Metode Pencarian dan Pelacakan

• Hal penting dalam menentukan keberhasilan sistem cerdas adalah kesuksesan dalam pencarian.

• Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space).

• Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.

• Untuk mengukur perfomansi metode pencarian, terdapat 4 kriteria yang dapat digunakan :

Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?

Time complexity : berapa lama waktu yang diperlukan? [semakin cepat, semakin baik]

Space complexity : berapa banyak memori yang diperlukan

Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

4.1 Metode Pencarian Buta (Blind Search) :

4.1.1 Pencarian melebar pertama (Breadth – First Search)

• Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1

• Mulai dari akar terus ke level 1 dari kiri ke kanan

• Kemudian ke level selanjutnya hingga solusi ditemukan

• Keuntungan

– Tidak akan menemui jalan buntu

– Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti

yang paling baik

– Jika ada satu solusi maka bread-first search akan menemukannya

• Kelemahannya

– Membutuhkan memori yang cukup banyak

– Membutuhkan waktu yang cukup lama

4.1.2 Pencarian mendalam pertama (Depth-First Search)

• Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel

• Keuntungan

– Memori yang relatif kecil

– Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi

4.2 Metode Pencarian Heuristik

• Pencarian buta tidak selalu dapat diterapkan dengan baik

– Waktu aksesnya yang cukup lama

– Besarnya memori yang diperlukan

• Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar.

• Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan disebut fungsi heuristic

• Aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine

• Contoh pada masalah 8 puzzle

keadaan awal                                                                             

Tujuan :

Keadaan Awal Tujuan Pencarian Heuristik

• Operator

– Ubin kosong geser ke kanan

– Ubin kosong geser ke kiri

– Ubin kosong geser ke atas

– Ubin kosong geser ke bawah

• Langkah Awal

Gambar

• Langkah Awal hanya 3 operator yang bisa digunakan

– Ubin kosong digeser ke kiri, ke kanan dan ke atas.

• Jika menggunakan pencarian buta, tidak perlu mengetahui operasi apa yang akan dikerjakan (sembarang)

• Pada pencarian heuristik perlu diberikan informasi khusus dalam domain tersebut

• Untuk jumlah ubin yang menempati posisi yang benar jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih baik)

• Untuk jumlah ubin yang menempati posisi yang salah jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

• Menghitung total gerakan yang diperlukan untuk mencapai tujuan jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

Pencarian Heuristik

• Ada metode pencarian heuristik

– Pembangkit & Pengujian (Generate and Test)

– Pendakian Bukit (Hill Climbing)

4.2.1 Pembangkit & Pengujian (Generate and Test)

• Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

Algoritma:

– Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).

– Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.

– Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.

Contoh : Traveling Salesman Problem (TSP)

Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali.

Contoh : Traveling Salesman Problem (TSP)

• Generate & test akan membangkitkan semua solusi yang mungkin:

– A – B – C – D

– A – B – D – C

– A – C – B – D

– A – C – D – B, dll

Kelemahan dari Pembangkit & Pengujian (Generate and Test) yaitu ;

– Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian

– Membutuhkan waktu yang cukup lama dalam pencariannya

4.2.2 Pendakian Bukit (Hill Climbing)

• Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik.

• Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan.

• Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

Simple Hill Climbing

Algoritma

– Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

– Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:

• Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

• Evaluasi keadaan baru tersebut.

• Jika keadaan baru merupakan tujuan, keluar.

• Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.

• Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

Contoh TSP

• Operator : Tukar kota ke-i dengan kota ke-j (Tk i,j)

• Untuk 4 kota:

– Tk 1,2 : tukar kota ke-1 dengan kota ke-2.

– Tk 1,3 : tukar kota ke-1 dengan kota ke-3.

– Tk 1,4 : tukar kota ke-1 dengan kota ke-4.

– Tk 2,3 : tukar kota ke-2 dengan kota ke-3.

– Tk 2,4 : tukar kota ke-2 dengan kota ke-4.

– Tk 3,4 : tukar kota ke-3 dengan kota ke-4.

• Untuk N kota, akan ada operator sebanyak:

Daftar Pustaka:

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

https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/

BAB 3 PENGENALAN LOGICAL AGENT

BAB 3

PENGENALAN LOGICAL AGENT

Logic merupakan jantung dari program, para pemrogram mempunyai keyakinan bahwa sebuah computer 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

Knowledge based agent

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 sentence yang diekspresikan dalam sebuah bahasa yakni knowledge representation language

1. Representasi Pengetahuan yang bersifat general.
2. Kemampuan beradaptasi sesuai temuan fakta.
3. 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 inferensi.

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

 2.2 Wumpus World

Aturan main Wumpus :

• Performance measure: emas +1000, mati -1000, gerak -1, panah -10
• Environment: Matriks 4x4 kamar. Initial state [1,1]. Ada gold, wumpus dan pit yang lokasinya dipilih secara acak.

Percept:

Breeze: kamar di samping lubang jebakan ada hembusan angin

Glitter: kamar di mana ada emas ada kilauan/sinar

Smell: kamar di samping Wumpus berbau busuk

•  Action: maju, belok kiri 90◦ , kanan 90◦ , tembak panah (hanya 1!), ambil benda

Sifat Wumpus :

·         (Fully) observable? Tidak, hanya bisa persepsi local

·         Deterministic? Ya, hasil tindakan jelas & pasti

·         Episodic? Tidak, tergantung action sequence

·         Static? Ya, gold, wumpus, pit tidak bergerak

·         Discrete? Ya

·         Single agent? Tidak

 2.3 Logic in general-Models and entailment

Logic adalah bahasa formal untuk merepresentasikan informasi sedemikian hingga kesimpulan dapat dibuat  dalam pembuatan kesimpulan pasti harus menggunakan bahasa yg benar dalam pembuatan bahasa yang tepat Syntax mendefinisikan kalimat-kalimat pada bahasa  kemudian Semantics mendefinisikan arti kalimat; misal, mendefinisikan kebenaran sebuah kalimat

Entailment berarti sesuatu fakta bisa disimpulkan dari (kumpulan) fakta lain Entailment dapat juga berarti sebuah hubungan antar kalimat ( syntax) yang didasarkan pada semantics kemudian Model adalah sebuah “dunia” di mana kebenaran suatu sentence bisa diuji.

Contoh:

Entailment :

 KB mengandung sentence “Anto ganteng” dan “Ani cantik”.

KB |= α1: “Anto ganteng dan Ani cantik”

 KB 2 α2: “Anto pintar”

x + y = 4 |= 4 = x + y

Contoh :

Model :

M(α) adalah himpunan semua model dari α

KB= Anto ganteng dan Ani cantik.

 α = Anto ganteng

Sumber :

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

http://larasdewilaras.blogspot.co.id/2016/10/bab-3-pengenalan-logical-agents.html

BAB 2 PENGENALAN INTELLIGENT AGENTS

BAB 2

PENGENALAN INTELLIGENT AGENTS

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

Dalam kecerdasan buatan,  intelligent agent (IA) adalah sebuah entitas otonom yang mengamati dan bertindak atas lingkungan (yaitu membutuhkan agen) dan mengarahkan aktivitasnya untuk mencapai tujuan  yaitu rasional.

STRUKTUR AGENT INTELLIGENCE

Tugas AI adalah untuk merancang sebuah agent yaitu sebuah fungsi yang mengimplementasikan pemetaan 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.

Hubungan antara agen, arsitektur, dan program dapat disimpulkan :

-          Mapping : Hubungan antara Percepts and Action.

-          Tugas dari AI adalah men-design Agent Program : merupakan sebuah function yang mengimplementasikan agent mapping dari percepts to action.

-          Architecture menerima percepts dari sensor, menjalankan program, melakukan aksi yang dipilih action ke effectors.

-          Agent = Architecture + Program

-          PAGE = Percepts, Actions, Goal(s) and Environment.

2.2  AGEN RASIONAL

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, dan lain-lain.

Agen rasional untuk setiap deretan persepsi yang mungkin, sebuah agen rasional hendaklah memilih satu tindakan ang diharapkan memaksimalkan ukuran performance-nya, dengan adanya bukti yang diberikan oleh deretan persepsi dan apapunpengetahuan 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 sedemikianhingga dapat memeroleh infoemasi yang berguna (pengumpulan infoemasi, eksplorasi). Sebuah agen adalah otonom (autonomous) apabila perilakunya ditentukan oleh pengalamannya sendiri (dengan kemampuan belajar dan beradaptasi)

2.3  PEAS (Perfomance measure, Environment, Actuators, Sensors)

PEAS: Performance measure, Environment, Actuators, Sensors

Pertama-tama harus menentukan pengaturan untuk desain agen cerdas.

Pertimbangkan, misal : tugas merancang supir taksi otomatis: 

•  Performance measure: Aman, cepat, legal, perjalanan menyenangkan, maksimumkan keuntungan.
• Environment: Jalan, trafik lain, pejalan kaki, pelanggan
•  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 sukucadang dalam kotak yang benar.
• Environment: ban berjalan dengan sukucadang, kotak
• Actuators: Pergelangan dan tangan tersambung
• Sensors: Kamera, joint angle sensor.
• 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 agent              

·         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 lingkugannya adalah strategic)

·         Episodic (vs. Sequential): pengalaman agen dibagi ke dalam “episode-episode” atomik (setiapepisode 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.

·         Jenis lingkungan sangat menentukan rancangan agen

·         Dunia nyata (tentu saja) partially observable, stochastic, sequentil, dynamic, continuous, multi-agent.

2.5 Tipe Agent

Simple Reflex Agents

Gambar diatas menunjukkan struktur Simple reflex agent, struktur yang paling sederhana dalam bentuk skema, menunjukkan bagaimana aturan condition action memungkinkan agen untuk membuat sambungan dari persepsi untuk bertindak. Persegi panjang untuk menunjukkan keadaan internal saat proses keputusan agen, dan oval untuk mewakili latar belakang informasi yang digunakan dalam proses. Secara ringkat dapat disampaikan sebagai berikut:

-           Memiliki rule base dalam bentuk "aksi-kondisi"

-          Memiliki komponen untuk mengekstrak Fitur

-          Tidak ada akses untuk menyelesaikan keadaan dunia

-          Pekerjaan hanya jika keputusan yang tepat dapat dilakukan atas dasar persepsi saat ini

Model Based Reflex Agent

Pengetahuan tentang "bagaimana dunia bekerja" disebut model dari dunia, maka bentuk ini dinamakan "model based reflex agent". Sebuah model based reflex agent harus menjaga semacam internal model yang tergantung pada sejarah persepsi dan dengan demikian mencerminkan setidaknya beberapa aspek yang tidak teramati negara saat ini. Kemudian memilih tindakan dengan cara yang sama sebagai agen refleks. Model ini lebih kuat daripada simple reflex agent

Goal-Based Agents

Goal based agents memperluas pada kemampuan model-based agents, dengan menggunakan "goal" informasi. Tujuan informasi menggambarkan kondisi yang diinginkan. Hal ini memungkinkan agen cara untuk memilih di antara beberapa kemungkinan, memilih satu yang mencapai negara tujuan. Search dan planing adalah sub bidang kecerdasan buatan yang ditujukan untuk urutan tindakan menemukan bahwa mencapai tujuan agen. Dalam beberapa kasus goal-based agent tampaknya kurang efisien; itu lebih fleksibel karena pengetahuan yang mendukung keputusan diwakili secara eksplisit dan dapat dimodifikasi.

Utility-Based Agents

“Goal” tidak cukup untuk menghasilkan perilaku berkualitas tinggi. Ada banyak urutan tindakan  untuk mencapai tujuan, tetapi beberapa yang lebih cepat, lebih aman, lebih dapat diandalkan, atau lebih murah daripada yang lain. Tujuan hanya memberikan perbedaan antara kondisi "bahagia" dan "tidak bahagia", sedangkan ukuran kinerja yang lebih umum harus memungkinkan perbandingan beberapa urutan kondisi yang berbeda jika agen ingin mencapai tujuan. Terminologi yang dipergunakan untuk mengatakan bahwa jika satu kondisi lebih disukai daripada kondisi yang lain, itu mempunyai utilitas yang lebih tinggi untuk agent.

SUMBER :

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

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