Metode Pencarian dan Pelacakan

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 :

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

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

3.      Space complexity : berapa banyak memori yang diperlukan

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

• Dua teknik pencarian dan pelacakan

– Pencarian buta (blind search)

• Pencarian melebar pertama (Breadth – First Search)

• Pencarian mendalam pertama (Depth – First Search)

– Pencarian terbimbing (heuristic search)

• Pendakian Bukit (Hill Climbing)

• Pencarian Terbaik Pertama (Best First Search)

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

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

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 4 metode pencarian heuristik

– Pembangkit & Pengujian (Generate and Test)

– Pendakian Bukit (Hill Climbing)

– Pencarian Terbaik Pertama (Best First Search)

– Simulated Annealing

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

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:

Steepest Ascent Hill Climbing

• Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri.

• Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.

• Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.

• Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri.

• Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.

• Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.

Algoritma

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

• Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang.

• Tentukan SUCC sebagai nilai heuristic terbaik dari successorsuccessor.

• Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:

• Gunakan operator tersebut dan bentuk keadaan baru.

• Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah.

• Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang, ubah node SUCC menjadi keadaan sekarang.

Sumber :

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

Pengenalan Intelligent Agent

Agent dan Lingkungannya

Agent adalah segala sesuatu yang dapat melihat/mengartikan/mengetahui lingkungannya melalui alat sensor dan bertindak melalui alat aktuator. 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 inframerah sebagai sensors; berbagai motor penggerak 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 menjadi tindakan.

Konsep Rasionalitas

Rational agent adalah agent yang melakukan sesuatu yang benar. Setiap kolom pada tabel (Vacuum-cleaner world) diselesaikan/dikerjakan dengan benar.

Rasional tergantung pada 4 hal :

• Kemampuan yang terukur
• Pengetahuan lingkungan sebelumnya/terdahulu
• Tindakan
• Urutan persepsi

DEF : untuk setiap urutan persepsi yang mungkin, rational agent harus memilih tindakan yang diharapkan dapat memaksimalkan kemampuan dengan memberikan bukti yang dihasilkan dari urutan persepsi dan pengetahuan yang dimiliki oleh agent.

Agent dapat bertindak sesuai dengan yang diharapkan untuk memodifikasi persepsi akan datang dengan mendapatkan informasi yang berguna (pengumpulan informasi dan eksplorasi). Agent dikatakan autonomous, jika perilakunya ditentukan oleh pengalamannya sendiri (dengan kemampuan untuk belajar dan beradaptasi)

Task Environtment (PEAS)

To design a rational agent we must specify its task environment. PEAS description of the environtment :

• Performance
• Environment
• Actuators
• Sensors

Contoh-contoh.

Agent : Sistem Diagnosis Medis

   - Perfomance measure: kesembuhan pasien, biaya minim, sengketa

   - Environment: pasien, pegawai rumah sakit

   - Actuators: layar monitor (pertanyaan, test, perawatan)

   - Sensors: keyboard (gejala, temuan, pertanyaan pasien)

Agent : Part-picking robot

   - Performance measure: % komponen pada tempat penampungan yang sesuai

   - Environment: Conveyor belt with parts, bins

   - Actuators: Joined arm and hand

   - Sensors: Kamera, joint angle sensors

Agent : Interactive English tutor

   - Performance measure: Maximize student's score on test

   - Environment: Set of students

   - Actuators: Screen display (exercises, suggestions, corrections)

   - Sensors: Keyboard

Tipe-Tipe Lingkungan Agents

1. Fully vs. partially observable : Lingkungan sepenuhnya dapat diamati ketika sensor-sensor dapat mendeteksi semua aspek yang relevan dalam memilih tindakan.
2. Deterministic vs. stochastic : Ketika tahap lingkungan berikutnya sepenuhnya ditentukan oleh tindakan yang sudah dilakukan.
3. Episodic vs. sequential : Pengalaman agent dapat dibagi menjadi tahapan-tahapan yang kecil dimana agent akan menerima dan melakukan satu tindakan. Pilihan tindakan tergantung hanya pada episode itu sendiri.
4. Static vs. dynamic : Jika lingkungan dapat berubah ketika agent sedang memilih tindakan, lingkungan dikatakan dynamic. Semi-dynamic, jika perfoma agent berubah ketika lingkungan tetap sama.
5. Discrete vs. continuous : This distinction can be applied to the state of the environment, the way time is handled and to the percepts/actions of the agent.
6. Single vs. multi-agent : Does the environment contain other agents who are also maximizing some performance measure that depends on the current agent’s actions?

Agent types

1. Goal-based
2. Utility-based
3. Learning

1. Goal-based

Tujuan-tujuan tertentu dapat dicapai dengan cara-cara berbeda. Beberapa lebih baik, memiliki manfaat yang lebih tinggi. Fungsi utililas memetakan urutan kedudukan (a sequence of states) dengan

angka real.

Meningkatkan tujuan-tujuan :

   - Memilih tujuan dari tujuan-tujuan yang berbenturan

   - Memilih dengan tepat beberapa tujuan memiliki kemungkinan berhasil.

2. Utility-based

Agent membutuhkan tujuan untuk mengetahui situasi mana yang diharapkan. Akan menjadi sulit ketika urutan yang panjang dari tindakan-tindakan (actions) dibutuhkan untuk mencari tujuan. Typically investigated in search and planning research. Major difference: future is taken into account. Is more flexible since knowledge is represented explicitly and can be manipulated.

3. Learning

Semua program-program agent terdahulu mendeskripsikan metode untuk memilih tindakan-tindakan (actions).

   – Yet it does not explain the origin of these programs.

   – Learning mechanisms can be used to perform this task.

   – Teach them instead of instructing them.

   – Advantage is the robustness of the program toward initially unknown environments.

Sumber : 

http://alfiyani18.blogspot.co.id/2016/10/blog-post_94.html

Pengenalan Intelegensi Buatan

KECERDASAN BUATAN

Kecerdasan Buatan adalah salah satu cabang Ilmu pengetahuan berhubungan dengan pemanfaatan mesin untuk memecahkan persoalan yang rumit dengan cara yang lebih manusiawi. Hal Ini biasanya dilakukan dengan mengikuti/mencontoh karakteristik dan analogi berpikir dari kecerdasan/Inteligensia manusia, dan menerapkannya sebagai algoritma yang dikenal oleh komputer.

Perbedaan antara kecerdasan buatan dengan kecerdasan alami adalah kecerdasan buatan lebih bersifat permanen, sedangkan kecerdasan alami dapat berubah (hal ini karena sifat manusia yang pelupa). Kecerdasan buatan lebih mudah disalin dan dipindah daripada kecerdasan alami. Menyediakan layanan computer lebih mudah dan murah daripada mendatangkan seseorang untuk mengerjakan sejumlah pekerjaan dalam waktu yang sangat lama. Kecerdasan buatan bersifat konsisten karena merupakan bagian dari teknologi computer, sedangkan kecerdasan alami dapat berubah-ubah.

 Perbandingan antara komputasi Kecerdasan Buatan & Pemrograman Konvensional.

Sejarah Kecerdasan Buatan

Pada awal abad 17, Rene Descartes mengemukakan bahwa tubuh hewan bukanlah apa-apa melainkan hanya mesin-mesin yang rumit. Tahun 1950-an adalah periode usaha aktif dalam AI. Program AI pertama yang bekerja ditulis pada 1951 untuk menjalankan mesin Ferranti Mark I di University of Manchaster (UK): sebuah program permainan naskah yang ditulis oleh Christopher Strachey dan program permainan catur yang ditulis oleh John McCarthy membuat istilah "kecerdasan buatan" pada konferensi pertama yang disediakan untuk pokok persoalan ini, pada 1956. Dia juga menemukan bahasa pemrograman Lisp. Alan Turing memperkenalkan 'Turing Test' sebagai sebuah cara untuk mengoperasionalkan test perilaku cerdas.

Lingkup Kecerdasan Utama

 

Lingkup utama kecerdasan buatan :

1.  Pengolahan bahasa alami (natural language processing) : Diman user dapat berkomunikasi dengan komputer menggunakan bahasa sehari-hari, misal bahasa Inggris, bahasa Indonesia, bahasa Jawa, dan lain-lain.

2. Sistem pakar (expert system) : Komputer sebagai sarana untuk menyimpan pengetahuan para pakar sehingga komputer memiliki keahlian menyelesaikan permasalahan dengan meniru keahlian yang dimiliki pakar.  

3. Pengenalan ucapan (speech recognition): Manusia dapat berkomunikasi dengan komputer menggunakan suara.

  

4. Robotika & Sistem Sensor.

5. Computer Vision : Menginterpretasikan gambar atau objek-objek tamak melalui komputer.

6. Intelligent computer-aided intruction : komputer dapat digunakan sebagai tutor yang dapat melatih dan mengajar.

7. Game playing.

 Soft Computing adalah kumpulan teknik – teknik perhitungan dalam ilmu komputer, inteligensia semu, machine learning dan beberapa disiplin ilmu teknik lainnya, yang berusaha untuk mempelajari, memodelkan, dan menganalisa fenomena yang sangat rumit.

Sumber :

http://divtor.blogspot.co.id/2016/10/pengenalan-intelegensi-buatan-m1.html