Diktat AI Bab II

Diktat

Kecerdasan Artifisial

 

ITHB

 

 

 

 

 

 

Ken Ratri Retno

The Houw Liong

 

 

 

 

BAB II

RUANG
MASALAH DAN PENCARIAN

 

Untuk membangun suatu sistem yang mampu menyelesaikan masalah perlu dipertimbangkan
4 hal :

1. Mendefinisikan masalah dengan tepat. Pendefinisian ini mencakup spesifikasi yang tepat mengenai keadaan awal dan solusi
   yang diharapkan.


2. Menganalisis masalah serta mencari teknik-teknik penyelesaian masalah yang tepat


3. Merepresentasikan pengetahuan yang diperlukan untuk menyelesaikan masalah tersebut.


4. Memilih teknik penyelesaian masalah yang terbaik.

 

2.1 ���� Mendefinisikan Masalah Sebagai Suatu Ruang
Keadaan

Permasalahan yang dihadapi misalnya permainan catur, maka harus ditentukan :

1. Posisi awal pada papan catur ; posisi awal
   setiap permainan catur selalu sama yaitu semua bidak diletakkan di atas papan catur dalam dua sisi yaitu
   kubu putih dan kubu hitam.


2. Aturan-aturan untuk melakukan gerakan secara legal ; aturan-aturan ini sangat berguna untuk menentukan gerakan buah catur , misalnya bidak untuk melangkah dari satu keadaan ke keadaan lain. Misalnya untuk mempermudah posisi buah catur setiap kotak ditunjukkan dengan huruf (a,b,c,d,e,f,g,h) pada arah horisontal dan angka (1,2,3,4,5,6,7,8) pada arah vertikal. Contoh di bawah ini
   menggambarkan aturan di dalam pergerakan
   bidak catur:

JIKA bidak putih pada kotak (e,2)

DAN kotak(e,3) kosong

DAN kotak(e,4) kosong

MAKA gerakkan bidak
putih dari (e,2) ke (e,4)

3. Sasaran
   (goal) : sasaran yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang terhadap lawannya yaitu ditandai dengan posisi raja lawan yang sudah dalam keadaan skak� dan tidak dapat bergerak lagi untuk menghindar.

Contoh di atas
menunjukkan representasi masalah dalam ruang
keadaan yaitu suatu ruang yang berisi semua keadaan
yang mungkin. Kita dapat memulai bermain
catur dengan menempatkan diri pada keadaan awal,
kemudian bergerak dari satu keadaan
ke keadaan yang lain sesuai dengan
aturan yang ada dan mengakhiri permainan jika salah satu telah
tercapai.

Sehingga untuk mendeskripsikan masalah dengan baik maka
harus :

1. Mendefinisikan suatu ruang keadaan


2. Menetapkan satu atau lebih ruang keadaan


3. Menetapkan satu atau lebih sasaran


4. Menetapkan kumpulan aturan

 

2.2 ���� Cara Merepresentasikan
Ruang Keadaan

Beberapa cara untuk merepresentasikan ruang keadaan yaitu.

 

A.     Graph Keadaan

Graph terdiri dari node-node yang menunjukkan keadaan yaitu keadaan awal
dan keadaan baru yang akan
dicapai dengan menggunakan operator, antara node
dihubungkan dengan menggunakan busur panah untuk menunjukkan
arah dari suatu keadaan ke
keadaan berikutnya.

 

Gambar 2.1 Graph Keadaan

 

B.     Pohon Pelacakan

Mengikuti struktur
pohon untuk menggambarkan keadaan secara hierarki, terdiri dari node-node yang memiliki level, mulai dari level 0 yang menunjukkan keadaan awal (akar)
biasanya merupakan obyek, node akar memiliki beberapa percabangan terdiri dari node berikutnya (successor) dan
merupakan node antara. Jika dilakukan pencarian mundur maka dikatakan
bahwa node tersebut memiliki sebelumnya (predecessor). Node
yang tidak memiliki anak dinamakan node daun, yang menunjukkan akhir pencarian, dapat juga berupa
tujuan atau jalan buntu (dead end).

 

 

Gambar 2.2 Pohon Pelacakan

 

 

2.3 ���� Metode Pencarian

Hal penting dalam menentukan keberhasilan sistem berdasar kecerdasan adalah kesuksesan dalam pencarian dan pencocokan. Pada dasarnya ada 2 teknik pencarian yang digunakan yaitu pencarian buta (blind search) dan
pencarian terbimbing (heuristic search).

 

2.3.1 � Pencarian Buta (blind search)

A. Pencarian
Melebar Dahulu (Breadth-First Search)

Pada metode ini semua node pada level ke�n akan dikunjungi
terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar lalu ke
level ke 1 dari arah kiri menuju
kanan hingga solusi ditemukan seperti yang nampak pada gambar di
bawah ini.

Gambar 2.3 Metode Breadth-First Search

 

Algoritma.

1. Buat suatu variable NODE_LIST dan
   tetapkan sebagai keadaan awal


2. Kerjakan langkah-langkah berikut sampai tujuan tercapai atau NODE_LIST kosong :

a)    
Hapus elemen pertama dari NODE_LIST, beri nama E. Jika
NODE_LIST kosong, keluar.

b)    
Untuk setiap langkah yang cocok dengan aturan
E, lakukan ;

1)    
Aplikasikan aturan tersebut untuk membentuk suatu keadaan baru

2)    
Jika keadaan awal adalah
tujuan yang diharapkan sukses dan keluar

3)    
Jika tidak tambahkan keadaan awal yang baru tersebut pada
akhir NODE_LIST

 

Keuntungan

1.     
Tidak akan menemui jalan
buntu

2.     
Jika ada satu solusi,
maka Breadth-First
Search akan menemukannya, dan jika lebih dari
satu solusi maka solusi minimum akan ditemukan.

 

Kerugian

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

2.     
Membutuhkan waktu yang cukup lama di dalam pencarian
karena menguji n level untuk mendapatkan solusi pada level ke n+1.

 

B. Pencarian Kedalaman Dahulu� (Depth-First
Search)

Proses pencarian akan dilakukan pada semua anaknya
sebelum dilakukan pencarian ke node-node pada level yang sama. Pencarian
dimulai dari node akar hingga ke level yang lebih tinggi. Proses diulangi terus
hingga ditemukan solusinya.

Gambar 2.4 Metode Depth-First
Search

 

 

Algoritma

1. Jika keadaan awal adalah
   tujuan yang diharapkan, sukses maka keluar.


2. Jika tidak, kerjakan
   langkah-langkah berikut ini hingga tercapai keadaan sukses atau gagal:

a)    
Bangkitkan keadaan
berikut (succesor) E dari keadaan
awal. Jika tidak ada succesor maka
akan terjadi kegagalan.

b)    
Panggil depth-first search dengan E sebagai
keadaan awal.

c)    
Jika sukses berikan
tanda sukses namun jika tidak ulangi langkah nomor 2.

Keuntungan

1. Membutuhkan memori yang
   relatif lebih kecil karena hanya node-node pada lintasan yang aktif saja
   yang disimpan.


2. Secara kebetulan metode depth-first search akan menemukan
   solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan

1. Memungkinkan tidak
   ditemukan tujuan yang diharapkan


2. Hanya akan mendapat kan
   satu solusi pada setiap pencarian.

 

2.3.2 Pencarian Heuristik

Ada 4 metode Pencarian Heuristik :

1. Bangkitkan dan test (Generate and
   Test)


2. Mendaki bukit (Hill Climbing)


3. Pencarian terbaik dahulu
   (Best first search)


4. Simulated annealing

Pencarian heuristic tidak selalu dapat diterapkan dengan baik karena
membutuhkan waktu akses yang cukup lama serta membutuhkan memori yang besar.
Hal ini dapat diatasi jika ada informasi tambahan dari domain yang
bersangkutan.

 

2.3.2.1 �Generate and Test

Metode ini merupakan penggabungan antara depth-first search dengan
backtracking, yaitu bergerak ke belakang menuju pada suatu keadaan awal. Nilai
pengujian merupakan jawaban �ya� atau �tidak�.

 

Algoritma

1. Bangkitkan suatu
   kemungkinan solusi ; titik tertentu atau lintasan tertentu dari keadaan
   awal.


2. Uji apakan node tersebut
   benar-benar merupakan solusinya dengan cara membandingkan node tersebut
   atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan
   yang diharapkan


3. Jika solusi ditemukan,
   keluar. Jika tidak ulangi kembali langkah pertama.

 

 

2.3.2.2 �Hill Climbing

Metode ini hampir sama dengan Generate
and Test hanya pada proses pengujian dilakukan dengan menggunakan fungsi
heuristik. Pembangkitan keadaan berikutnya sangat tergantung dari feedback prosedur pengetesan. Tes yang
berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan
yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

 

1. Simple
Hill Climbing

Algoritma

1.     
Lakukan pengujian
dari keadaan awal, jika merupakan sasaran maka berhenti; dan jika tidak
lanjutkan dengan keadaan sekarang sebagai keadaan awal.

2.     
Kerjakan
langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada
operator baru yang akan diaplikasikan pada keadaan sekarang;

a)    
Pilih operator yang
belum pernah digunakan, lalu gunakan untuk mendapatkan keadaan baru

b)    
Evaluasi keadaan
baru tersebut;

1)    
Jika keadaan baru
merupakan sasaran, keluar

2)    
Jika bukan tujuan
namun nilainya lebih baik daripada keadaan sekarang maka jadikan keadaan baru
tersebut menjadi keadaan sekarang

3)    
Jika keadaan baru
tidak lebih baik daripada keadaan sekarang maka lanjutkan iterasi.

 

Pada Simple Hill
Climbing ada tiga masalah yang
mungkin yaitu.

1.     
Algoritma akan
berhenti jika mencapai nilai optimum lokal.

2.     
Urutan penggunaan
operator akan sangat berpengaruh pada penemuan solusi.

3.     
Tidak diijinkan
untuk melihat satupun langkah sebelumnya.

 

2. Steepest
Hill Climbing

Hampir sama dengan Hill climbing hanya gerakan pencarian tidak dimulai dari posisi
paling kiri, gerakan selanjutnya dicari berdasarkan nilai heuristik yang
terbaik. Operator tidak menentukan penemuan solusi.

 

2.3.2.3 �Best first search

Merupakan kombinasi dengan mengambil kelebihan dari metode depth-first search dan metode breadth-first search. Pada metode ini,
pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah,
jika node yang lebih tinggi memiliki nilai heuristik yang lebih buruk.
Implementasi motode ini dengan menggunakan graph keadaan.

 

2.3.2.4 �Simulated annealing

Metoda ini dikembangkan berdasarkan mekanika statistik. Biasanya digunakan
untuk menyelesaikan masalah dimana perubahan keadaan dari suatu kondisi ke
kondisi lainnya membutuhkan ruang keadaan yang sangat besar.

Algoritma

1. Evaluasi keadaan awal, jika
   merupakan sasaran maka pencarian berhasil.


2. Inisialisasi Keadaan
   Terbaik Sejauh ini (Best_So_Far)
   untuk keadaan sekarang


3. Inisialisasi T sesuai
   dengan penjadwalan (annealing
   schedule)


4. Kerjakan hingga solusi
   ditemukan atau sudah tidak ada operator baru lagi akan diaplikasikan
   kedalam kondisi sekarang.




1. Gunakan operator yang
   belum pernah digunakan untuk menghasilkan kondisi baru


2. Evaluasi kondisi baru
   dengan menghitung :

Perubahan
�energi� ΔE = E(nilai sekarang) � E(nilai
keadaan baru)

1)    
Jika kondisi baru
merupakan sasaran, maka pencarian berhasil dan keluar

2)    
Jika bukan sasaran
namun memiliki nilai yang lebih baik dari kondisi sekarang, maka tetapkan
kondisi baru sebagai kondisi sekarang, dan inisialisasi sebagai Terbaik Sejauh
ini (Best_So_Far).

3)    
Jika nilai kondisi
baru tidak lebih baik dari kondisi skarang, maka tetapkan kondisi baru sebagai
kondisi sekarang dengan probabilitas:

c.      Perbaiki� nilai �temperatur�
T sesuai annealing schedule

5. Best_So_Far adalah kondisi yang dimaksud.