.jpg)
- Jaringan Syaraf: sistem dengan kemampuan pengenalan pola yang sangat kuat
- Sistem Fuzzy: teknik-teknik untuk pertimbangan di bawah ketidakpastian, telah digunakan secara meluas dalam industri modern dan sistem kendali produk konsumen.
- Komputasi Evolusioner: menerapkan konsep-konsep yang terinspirasi secara biologis seperti populasi, mutasi dan “survival of the fittest” untuk menghasilkan pemecahan masalah yang lebih baik.
Searching di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.
Teknik searching sendiri terbagi menjadi dua, yaitu:
- Blind searching
- Heuristic searching
Blind Searching
Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
- Membangkitkan simpul berdasarkan urutan
- Kalau ada solusi maka solusi akan ditemukan
- Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).
Blind Searching sendiri dibagi menjadi tiga macam yaitu :
- BFS (Breadth First Search)
- DFS (Depth-first Search)
- UCS (Uniform Cost Search)
Breadth First Search yaitu model pencarian yang memakai metode melebar. Untuk mencari hasilnya, model BFS ini menggunakan teknik pencarian persoalannya dengan cara membuka node (titik) pada tiap levelnya. Pencarian dilakukan pada semua simpul dalam setiap level secara berurutan dari kiri ke kanan. Jika pada suatu level belum ditemukan solusi, maka pencarian akan dilanjutkan pada level berikutnya. Demikian seterusnya sampai ditemukan solusi.
DFS (Depth-first Search) sering disebut juga pencarian mendalam. Sesuai dengan namanya “pencarian mendalam”, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemuakn “goal”nya dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target/goal.
DFS memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node.
Salah satu cara sederhana untuk mewujudkan algoritma DFS adalah dengan menggunakan Stack.
Algoritma DFS sebagai berikut :
Begin
Push node awal pada stack, yang ditunjukkan dengan stack_top
While stack tidak kosong do
Begin
Pop stack untuk mendapatkan stack_top element
If stack_top_element = Tujuan
Return
Sukses dan stop
Else push turunan (cabang) stack_top element ke dalam stack
End while
End
Begin
Push node awal pada stack, yang ditunjukkan dengan stack_top
While stack tidak kosong do
Begin
Pop stack untuk mendapatkan stack_top element
If stack_top_element = Tujuan
Return
Sukses dan stop
Else push turunan (cabang) stack_top element ke dalam stack
End while
End
Pada Algoritma DFS itu menunjukkan bahwa "Proses akan diterus-kan sampai stack dalam keadaan kosong."
Konsepnya hampir sama dengan BFS, bedanya adalah bahwa BFS menggunakan urutan level dari yang paling rendah sampai yang paling tinggi. Sedangkan UCS menggunakan urutan biaya dari yang paling kecil sampai dengan yang terbesar. UCS berusaha menemukan solusi dengan total biaya terendah yang dihitung berdasarkan biaya dari simpul asal menuju ke simpul tujuan. Biaya dari simpul asal ke suatau simpul n dilambangkan sebagai g(n). Perhatikan UCS menemukan solusi terbaik. Karena mengikuti konsep BFS, maka UCS menjamin ditemukannya solusi dan solusi yang ditemukannya selalu yang terbaik. Dengan kata lain, UCs adalah complete dan optimal.
Heuristic Search
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching:
PENDAKIAN BUKIT (Hill Climbing)
Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya 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.
Algoritma Simple HillClimbing
Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
Sumber :
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching:
- Generate and Test.
- HillClimbing.
- Best First Search.
- Alpha Beta Prunning,Means-End-Anlysis,Constraint Satisfaction, Simulated Anealing, dll
PEMBANGKITAN dan PENGUJIAN (Generate and Test)
Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal. Algoritma:
- Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).
- Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
- Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.
PENDAKIAN BUKIT (Hill Climbing)
Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya 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.
Algoritma Simple HillClimbing
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 dari pada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
- Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
PENCARIAN TERBAIK PERTAMA(Best-First Search)
Metode ini merupakan kombinasi dari metode depth-first search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.
Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan :
f’(n) = g(n)+ h’(n)
dimana f’ = Fungsi evaluasi
g = cost dari ini tial state ke current state
h’ = prakiraan cost dari current state ke goal state
