03/03/2015
Prio Handoko, S. Kom., M.T.I.
Program Studi Teknik Informatika Universitas Pembangunan Jaya Jl. Boulevard - Bintaro Jaya Sektor VII Tangerang Selatan – Banten 15224
Kompetensi Dasar
Mahasiswa mendapatkan pemahaman mengenai teknik-teknik dasar pencarian dan dapat mempraktekan dalam penyelesaian suatu kasus.
Agenda • Teknik Dasar Pencarian • Teknik Pemecahan Masalah • Strategi Pencarian Mendalam • Pencarian Heuristik
• •
Baik atau tidaknya sebuah sistem AI dalam menyelesaikan permasalahan tergantung kepada teknik pencarian atau pelacakan yang diterapkan. Teknik pencarian dan pelacakan dasar:
• •
Pencarian buta (blind search) Pencarian terbimbing (heuristik search)
1
03/03/2015
• • •
Pencarian merupakan teknik pemecahan masalah Apa itu pencarian?
State 3
Pencarian adalah suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkian ruang keadaan (state space).
State 2
Ruang keadaan: suatu ruang yang berisi semua keadaan yang memungkinkan
Nilai yang diperoleh dari solusi Keadaan tujuan-solusi yang dijangkau dan perlu diperiksa apakah telah mencapai sasaran
State 1
Keadaan sekarang/awal
•
Alur proses pencarian
Memeriksa
Keadaan awal
Mengeksekusi aksi yang dibolehkan untuk meemindahkan ke keadaan berikutnya
Memeriksa jika keadaan baru merupakan solusinya
Eksekusi
Solusi
T
OK?
•
Y
Memecahkan masalah mencari lintasan dari keadaan sekarang Keadaan tujuan Representasi pemecahan masalah:
• • •
Suatu masalah pencarian graph berarah Keadaan node Langkah yang diperbolehkan arc (busur)
Selesai
2
03/03/2015
• •
Pencarian memunginkan tanpa hasil/penyelesaian walaupun ruang keadaan yang mungkin telah terkunjungi seluruhnya (mendalam). Terdapat 2 strategi pencarian yang mendalam (exhaustive search strategy):
• •
Breadth First Search (BFS)
Breadth First Search (BFS)
•
•
Depth First Search (DFS)
Breadth First Search (BFS)
Merupakan pencarian yang dilakukan dengan mengunjungi setiap node secara sistematis pada tiap level hingga keadaan tujuan (goal state) ditemukan. Strategi BFS menelusuri node dalam level yang sama sebelum pindah ke node pada level lainnya secara sistematis.
Breadth First Search (BFS)
Permasalahan BFS
• • •
Membutuhkan memori yang besar Membutuhkan jumlah besar pekerjaan Tidak relevannya operator akan menambah jumlah node yang harus diperiksa
3
03/03/2015
Breadth First Search (BFS)
Breadth First Search (BFS)
Breadth First Search (BFS) Depth First Search (BFS)
•
•
Merupakan pencarian yang dilakukan dari node awal secara mendalam (deep) hingga node yang paling akhir (dead-end) atau sampai ditemukan. Strategi DFS menelusuri dari cabang satu ke cabang lainnya, dari awal sampai akhir
4
03/03/2015
Depth First Search (DFS)
•
Depth First Search (DFS)
Strategi DFS: 1. proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di node terakhir; 2. jika tujuan yang diinginkan belum tercapai, maka pencarian dilanjutkan ke cabang sebelumnya dan turun ke bawah jika masih ada cabangannya;
•
3. kegiatan 1 dan 2 dilakukan terus menerus hingga diperoleh tujuan.
Kelebihan:
• • •
waktu pencapaian ruang kedalaman singkat; lebih efisien; memori yang dibutuhkan relatif sedikit.
Depth First Search (DFS)
Depth First Search (DFS)
5
03/03/2015
BFS - DFS
BFS - DFS
Contoh:
Latihan:
Perhatikan gambar maze disamping ini, kemudian:
Perhatikan gambar maze disamping ini, kemudian:
1. Gambarkan kembali nodenode disamping sebagai sebuah graph! 2. Tentukan jalur terpendek antar node tersebut menggunakan teknik pencarian BFS dan DFS!
1. Gambarkan kembali nodenode disamping sebagai sebuah graph! 2. Tentukan jalur terpendek antar node tersebut menggunakan teknik pencarian BFS dan DFS!
Pencarian heuristik (berdasarkan panduan – informed search)adalah: “metode yang digunakan dalam pencarian ruang keadaan sebagai sebuah aturan untuk melakukan pemilihan cabang-cabang yang paling tepat untuk mencapai solusi permasalahan yang dapat diterima”
Pencarian heuristik memiliki 4 metode pencarian: 1. Generate and Test 2. Hill Climbing 3. Best First Search 4. Simulated Annealing
6
03/03/2015
• • •
Generate and Test Generate and test (pembangkit dan pengujian) merupakan metode yang paling sederhana dalam pencarian heuristik Jika pembangkit solusi yang memungkinkan (possible solution) dikerjakan secara sistematis, maka prosedur akan mencari solusinya (jika memang ada) Algortima metode ini merupakan gabungan antara BFS dan DFS.
Generate and Test Algoritma 1. Bangkitkan suatu solusi. Solusi dapat berupa pembangkitan node-node tertentu dari keadaan awal. 2. Uji solusi tersebut. Hal ini dimaksudkan untuk dapat memastikan apakah solusi tersebut sesuai yang diinginkan dengan cara membandingkan node-node yang dipilih dengan kumpulan tujuan yang diharapkan. 3. Ulangi langkah 1 dan 2 hingga mendapatkan solusi yang diharapkan.
Generate and Test
Generate and Test
Contoh: Permasalahan Travelling Sales Problem (TSP)
Latihan
Diketahui rute perjalanan yang harus dilalui seorang sales adalah seperti gambar di bawah ini. Tentukan lintasan terpendek dari permasalahan tersebut!
Diketahui rute perjalanan yang harus dilalui seorang sales adalah seperti gambar di samping ini. Tentukan lintasan terpendek dari permasalahan tersebut menggunakan metode GaT! 2
A
2 3
3
A
B
1
5
D
3
C
5
1
B
1
4
D
3
C
7
03/03/2015
Hill Climbing – Steepest-Ascent HC Tugas #1. Menggunakan gambar rute yang sama dengan permasalahan sebelumnya, maka tentukan lintasan terpendek dari permasalahan tersebut menggunakan metode GaT! A
3
2
1
5
B
1
C 1
4
•
Hill Climbing Metode ini mirip dengan metode GaT. Pembedanya adalah umpan balik (feedback) yang berasal dari prosedur pengujian digunakan untuk memutuskan arah gerak dari pencarian. Terdapat 2 macam metode HC: 1. Simple HC
2
D
• •
2. Steepest-ascent HC
E
Hill Climbing – Simple HC Contoh • Menggunakan TSP sebelumnya
•
𝑛! Menggunakan rumusan , dimana 2 adalah 2! 𝑛−2 !
konstanta jumlah kota yang saling ditukarkan.
Hill Climbing – Simple HC Latihan Menggunakan gambar rute yang sama dengan permasalahan sebelumnya, maka tentukan lintasan terpendek dari permasalahan tersebut menggunakan metode Simple-HC! A
Bagaimana algoritmanya?
1
3
3
B
2
5
D
4
C
8
03/03/2015
Hill Climbing – Simple HC Tugas #2. Menggunakan gambar rute yang sama dengan permasalahan sebelumnya, maka tentukan lintasan terpendek dari permasalahan tersebut menggunakan metode Simple-HC! 2
A
5
1
B
1 3
C
• •
3 4
• •
Hill Climbing – Steepest-Ascent HC Metode ini mirip dengan metode HC. Pembedanya adalah gerakan pencarian tidak dimulai dari posisi paling kiri Gerakan didasarkan pada nilai heuristik terbaik Contoh menggunakan TSP sebelumnya!
E 2
D
Hill Climbing – Steepest-Ascent HC
Hill Climbing – Steepest-Ascent HC
Contoh
Tugas #3.
Menggunakan gambar rute yang sama dengan permasalahan sebelumnya, maka tentukan lintasan terpendek dari permasalahan tersebut menggunakan metode Steepest-Ascent HC!
Menggunakan gambar rute yang sama dengan permasalahan sebelumnya, maka tentukan lintasan terpendek dari permasalahan tersebut menggunakan metode Steepest-Ascent HC!
A
Bagaimana algoritmanya?
2
5
1
B
1
4
D
3
C
A
3
2
1
5
B
1
C 1
2
D
4
E
9
03/03/2015
• • •
•
Best Fit Search Metode ini merupakan kombinasi dari teknik pencarian BFS dan DFS Pencarian diperkenankan mengunjungi node yang terdapat pada level yang lebih rendah jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristik yang lebih buruk. Jenis pencarian BestFS yang umum digunakan adalah disebut dengan Graf OR
Best Fit Search Contoh:
Best Fit Search Graf OR:
• • • •
Graf yang digunakan untuk menelusuri state space ke setiap node-node yang menjanjikan solusi
Best Fit Search Step 1
Step 2
Step 3
Step 4
Menerapkan fungsi heuristik yang memadai pada setiap simpul Jika salah satu node tersebut merupakan sebuah solusi, maka pencarian berhenti Jika tidak, semua node baru ditambahkan ke himpunan node yang pernah dibuat.
Bagaimana algoritmanya?
10
03/03/2015
Best Fit Search Tugas #4. Gambarkanlah proses pencarian solusi menggunakan Graf OR yang diwakilkan oleh node-node di samping ini.
• • •
Simulasi Annealing Teknik optimalisasi numerik dengan prinsip thermodynamic Simulasi Annealing menggunakan nilai temperatur sebagai referensi heuristik Perhatikan penjelasan berikut!
11
