Google+ Followers

15 October 2009

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)




  1. 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 skakdan 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.      Perbaikinilai �temperatur�
T sesuai
annealing schedule




  1. Best_So_Far adalah kondisi yang dimaksud.



 



 






No comments: