2.1. Agen Pemecahan Permasalahan
Pemecahan masalah adalah sebuah
proses dimana suatu situasi diamati kemudian bila ditemukan ada masalah dibuat
penyelesaiannya dengan cara menentukan masalah, mengurangi atau menghilangkan
masalah atau mencegah masalah tersebut terjadi. Menurut Russel dan Norvig,
pengertian agent adalah segala sesuatu yang dapat dipandang
menangkap/mengetahui/menangapi lingkunganya melalui sensor dan bertindak
terhadap lingkunganya melalui efektor. Sensor merupakan bagian yang merangsang
akan merangsang agent (kamera & infra red pada robot) sedangkan efektor
merupakan bagian yang digunakan oleh agent untuk menangapi rangsangan yang
telah diterimanya sebelumnya(motor pada robot). Agen Pemecahan Permasalahan
dapat diartikan sebagai cara atau metode untuk menyelesaikan masalah
berdasarkan lingkungan sekitar dengan cara bertindak sesuai dengan keadaan
lingkungan tersebut.
Agen-agen pemecahan masalah tersebut
terbagi menjadi lima yaitu :
·
Simple
reflex agents: berdasarkan persepsi yg terakhir.
·
Model-based
reflex agents: memiliki representasi internal tentang keadaan sekitar.
·
Goal-based
agents: memiliki informasi tentang tujuan, memilih tindakan yang mencapai
tujuan.
·
Utility-based
agents: melakukan penilaian kuantitatif terhadap suatu keadaan lingkungan.
·
Learning
agents: belajar dari pengalaman, meningkatkan kinerja.
2.2. Pencarian Sebagai Solusi Pemecahan
Masalah
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:
1. 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 :
a. BFS (Breadth First
Search)
b. DFS
(Depth-first Search)
c. UCS (Uniform
Cost Search).
2. Heuristic
Searching
Heuristic Search
merupakan metode pencarian yang memperhatikan nilai heuristik (nilai
perkiraan).Teknik pencarian heuristik (heuristic searching) merupakan suatu
strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu
problema secara selektif, yang memandu proses pencarian yang kita lakukan di
sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan
mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik adalah
sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan
kemungkinan mengorbankan kelengkapan (completeness).Heuristic Search
memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).
Fungsi heuristik
ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan
menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi
yang diinginkan.
Jenis-jenis Heuristic Searching :
- Generate and
Test
- Hill Climbing
- Best First
Search
- Alpha Beta
Prunning
- Means-End-Anlysis
- Constraint
Satisfaction
2.3. Strategi Pencarian yang tidak
berbentuk
Algoritma
ini tidak memberikan informasi apapun tentang permasalah yang ada, tetapi hanya
berfokus memberikan informasi tentang algorima tersebut. Algoritma ini juga
disebut Blind Search. Istilah Blind Search berpedoman bahwa, teknik pencarian
ini tidak memiliki informasi tambahan lain selain dari yang disediakan.
Yang dilakukan
oleh algorima ini adalah melakukan generate dari successor dan membedakan goal
state dari non-goal state. Pencarian ini dilakukan berdasarkan pada urutan mana
saja node yang hendak di-expand.
Macam-macam
Uninformed Search Algorithm :
Breadth First Search(BFS)
Pencarian dengan
metode ini menggunakan teknik dimana langkah pertama yang harus dilakukan
adalah root node di-ekspansi, setelah itu dilanjutkan semua successor dari root
node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf(node
pada level paling bawah yang sudah tidak memiliki successor lagi).
Uniform Cost Search(UCS)
Pencarian dengan
BFS akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan
sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat
kepada nilai tiap path di antara node-node yang ada.
Selain
menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node
dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat
antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan
dalam bentuk priority queue).
Depth First Search(DFS)
Teknik pencarian
dengan metode ini adalah dengan melakukan ekspansi menuju node yang paling
dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari
node itu. Setelah node selesai di ekspansi, maka node tersebut akan
ditinggalkan dan dilakukan ke node paling dalam lainnya yang masih memiliki
successor yang belum di ekspansi.
Depth Limited Search
Pencarian
menggunakan DFS akan berlanjut sampai kedalam paling terakhir dari sebuah tree.
Misalkan yang muncul pada DFS adalah ketikda proses pencarian tersebut menemui
infinite state space. Hal ini bisa diatasi dengan mengisiasikan batas depth
pada level tertentu semenjak awal pencarian. Sehingga node pada level depth
tersebut akan diperlakukan seolah-olah mereka sudah tidak memiliki successor.
Iterative Deepening Depth First Search
Iterative
deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan
dengan depth first tree search, yang akan menemukan berapa depth limit terbaik
untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara
bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.
Bidirectional Search
Pencarian dengan
metode bidirectional search adalah dengan menjalankan dua pencarian secara
simultan, yang satu dikerjakan secara forward dari initial state menuju ke
goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke
initial state. Yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu
di tengah-tengah.
Sumber :
Tidak ada komentar:
Posting Komentar