Pencarian Berbentuk heuristik Search dan Eksplorasi.

Pencarian Berbentuk /heuristik search dan Eksplorasi.

Nama : Rendy Noviantono

Kelas : 3KA10

Npm : 15115757

1.1 Pencarian

Pencarian merupakan kegiatan mendefinisikan ruang masalah untuk

masalah yang dihadapi. Ruang masalah ini dapat digambarkan sebagai himpunan

keadaan (state) atau bisa juga sebagai himpunan rute dari keadaan awal (initial

state) menuju keadaan tujuan (goal state). Langkah kedua adalah mendefinisikan

aturan produksi yang digunakan untuk mengubah suatu state ke state lainnya.

Langkah terakhir adalah memilih metode pencarian yang tepat sehingga dapat

menemukan solusi terbaik dengan usaha yang minimal.

Metode-metode pencarian pada teknik searching diantaranya[8] :

1. Pencarian tidak berbekal informasi / buta (Blind/Un-informed Search)

a. Breadth-First Search (BFS)

b. Depth-First Search (DFS)

c. Depth-Limited Search (DLS)

d. Uniform Cost Search (USC)

e. Iterative-Deepening Search (IDS)

f. Bi-Directional Search (BDS)

2. Pencarian berbekal informasi (Heuristik)

a. Generate-and-Test

b. Hill Climbing

c. Simulated Annealing

d. Best-First Search (BFS)

e. Greedy Best-First Search

f. A* (A star)

1.2 Metode Pencarian Heuristic

Kata Heuristic berasal dari sebuah kata kerja Yunani, heuriskein, yang

berarti „mencari‟ atau „menemukan‟. Dalam dunia pemrograman, sebagian orang

menggunakan kata heuristic sebagai lawan kata dari algoritmik, di mana kata

heuristic ini diartikan sebagai suatu proses yang mungkin dapat menyelesaikan  suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat

ditemukan. Heuristic memperbaiki proses pencarian solusi walaupun tidak harus

sampai mengatasi kasus terburuk (worst case scenario). Heuristik ini

mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan

mengorbankan kelengkapan (completeness). Algoritma ini biasanya mencari

solusi yang dekat dengan solusi terbaik dan proses pencariannya cepat dan mudah.

Terkadang algoritma ini dapat menjadi akurat dan menemukan solusi terbaik,

tetapi algoritma ini tetap disebut heuristic hingga solusi terbaik itu terbukti untuk

menjadi yang terbaik. Fungsi heuristic h(n) adalah perkiraan biaya termurah dari

node n ke node tujuan. Fungsi heuristic melambangkan cost yang akan

dikeluarkan agent jika memilih node tertentu.

1.3 Metode A* Heuristic

Metode A* dikembangkan oleh Peter Hart, Nils Nilsson, dan Bertram

Raphael, mereka juga menyebut metode tersebut dengan sebutan algoritma A,

dengan menggunakan metode ini dan dengan heuristic yang tepat menghasilkan

sebuah hasil yang optimal, yaitu A*. Secara umum, depth-first search (DFS) dan

breadth-first search (BFS) adalah dua kasus spesial dari metode A*. Algoritma

Djikstra‟s merupakan kasus yang paling special dari A*, di mana h(x) = 0 untuk

semua x [8].

Metode A* tanpa fungsi heuristic yang baik akan memperlambat pencarian

dan dapat menghasilkan rute yang tidak tepat. Fungsi heuristic yang sempurna

akan membuat metode A* langsung menuju final node tanpa harus mencari

kearah lain. Sehingga jika fungsi heuristicnya terlalu underestimate akan

menyebabkan algoritma ini beranggapan bahwa ada rute lain yang lebih baik.

Untuk fungsi heuristic yang underestimate, bila nilainya terlalu rendah akan

menyebabkan algoritma ini seperti algortima Djikstra’s yang mencari ke segala

arah yang mungkin. Hal ini dikarenakan tidak ada informasi yang cukup

mengenai masalah yang dihadapi, sehingga menyebabkan metode A* melakukan

pencarian lebih banyak dan lebih lama.

Berdasarkan ilmu komputer, A* (disebut “A star”) adalah sebuah graph

atau metode tree search yang digunakan untuk mencari jalan dari sebuah node

awal ke node tujuan (goal node) yang telah ditentukan, metode ini menggunakan

“estimasi heuristic” h(x) pada setiap node untuk mengurutkan setiap node x

berdasarkan estimasi rute terbaik yang melalu node tersebut. Dalam prosesnya

metode ini akan mengunjungi setiap node berdasarkan urutan yang dihasilkan dari

estimasi heuristic ini. Metode A* adalah salah satu contoh dari metode best-first

search.

Masalah pencarian rute di mana metode A* sering digunakan, A* secara

bertahap membangun semua rute yang mengarah mulai dari titik awal sampai

akhirnya mencapai titik akhir. Metode A* hanya membangun rute yang mungkin

digunakan untuk mencapai tujuan. Untuk mengetahui rute mana yang

memungkinkan mengarah ke titik akhir, A* menggunakan estimasi heuristic jarak

dari sembarang node ke node tujuan. Dalam kasus pencarian rute, ini bisa jadi

sama dengan jarak lurus antara dua titik, di mana biasanya merupakan perkiraan

dari jarak jalan.

Hubungan antara heuristic dengan algoritma A* [8]:

1. Apabila h(n) selalu bernilai 0, maka hanya g(n) yang akan berperan, dan

A* berubah menjadi Algoritma Dijkstra, yang menjamin selalu akan

menemukan jalur terpendek.

2. Apabila h(n) selalu lebih rendah atau sama dengan ongkos perpindahan

dari titik n ke tujuan, maka A* dijamin akan selalu menemukan jalur

terpendek. Semakin rendah nilai h(n), semakin banyak titik-titik yang

diperiksa A*, membuatnya semakin lambat.

3. Apabila h(n) tepat sama dengan ongkos perpindahan dari n ke tujuan,

maka A* hanya akan mengikuti jalur terbaik dan tidak pernah memeriksa

satupun titik lainnya, membuatnya sangat cepat. Walaupun hal ini belum

tentu bisa diaplikasikan ke semua kasus, ada beberapa kasus khusus yang

dapat menggunakannya.

4. Apabila h(n) kadangkala lebih besar dari ongkos perpindahan dari n ke

tujuan, maka A* tidak menjamin ditemukannya jalur terpendek, tapi

prosesnya cepat.

5. Apabila h(n) secara relatif jauh lebih besar dari g(n), maka hanya h(n)

yang memainkan peran, dan A* berubah menjadi BFS.

1.4 Aplikasi Metode A* Heuristic

Metode A* biasanya diaplikasikan dalam kasus pathfinding. Terdapat

beberapa hal yang perlu didefinisikan terlebih dahulu dalam kasus pathfinding

dengan penerapan algoritma A*. Adapun istilah-istilah yang akan dibahas yaitu

path, open list, closed list, nilai f, g dan n.

Algoritma ini menggunakan dua senarai yaitu open dan closed. open

adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul yang

pernah dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih

sebagai simpul terbaik (best node) dengan kata lain, open berisi simpul-simpul

masih memiliki peluang untuk terpilih sebagai simpul terbaik, sedangkan closed

adalah senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan

dan sudah pernah terpilih sebagai simpul terbaik. Artinya, closed berisi simpulsimpul

yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih

sudah tertutup).

1. Open list adalah list yang menyimpan kemungkinan path yang akan

diperiksa. Open list dibuat terurut berdasarkan nilai f. Open list digunakan

untuk menentukan secara selektif (berdasarkan nilai f) jalan yang dikira

lebih dekat menuju pada path tujuan. Open berisi simpul-simpul yang

masih memiliki peluang untuk terpilih sebagai simpul terbaik (best node).

2. Closed adalah senarai (list) untuk menyimpan simpul-simpul yang sudah

pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik (best

node) atau senarai yang menyimpan jalan yang sudah diperiksa dari open

list. Artinya, closed berisi simpul-simpul yang tidak mungkin terpilih

sebagai simpul terbaik (peluang untuk terpilih sudah tertutup). Kedua list

(open list dan closed list) ini bertujuan juga untuk menghindari

penelusuran jalan (rute) berulangkali yang memang sudah diidentifikasi

agar tidak masuk kembali ke dalam open list.

3. Nilai F adalah cost perkiraan suatu path yang teridentifikasi. Nilai F

merupakan hasil dari f(n).

4. Nilai G hasil dari fungsi g(n), adalah banyaknya langkah yang diperlukan

untuk menuju ke path sekarang.

5. Nilai N untuk setiap simpul (node) harus memiliki informasi nilai h(n),

yaitu estimasi harga simpul tersebut dihitung dari simpul tujuan yang

hasilnya menjadi nilai H.

Fungsi f sebagai estimasi fungsi evaluasi terhadap node n, dapat dituliskan

[8] :

f(n) = g(n) + h(n)….[2.1]

dengan :

f(n) = fungsi evaluasi ( jumlah g(n) dengan h(n) )

g(n) = biaya (cost) yang dikeluarkan dari keadaan awal sampai keadaan n

h(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n

Pergerakan diagonal diperbolehkan, maka digunakan fungsi heuristic

Non-Manhattan Distance. Maka fungsi heuristic yang digunakan adalah sebagai

berikut :

h_diagonal(n) = – (abs(n.x-goal.x) + abs(n.y-goal.y))….[2.2]

h_orthogonal(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))….[2.3]

h(n) = h_diagonal(n) + (h_orthogonal (n) – (2 * h_diagonal(n)))….[2.4]

dengan :

x = representasi titik absis

y = representasi titik ordinat

2.3.3.4 Metode Simplified Memory-Bounded A* (SMA*)

Simplified Memory-Bounded A* (SMA*) merupakan pengembangan dari

algoritma A*. Algoritma SMA* merupakan penggabungan dari greedy search

yang meminimalisir perkiraan pencarian harga dan uniform cost search yang

meminimalisir harga sampai selesai [8].

Algoritma SMA* bersifat admissible. Ini berarti apabila solusi ada, solusi

yang ditemukan pertama adalah solusi yang optimal. SMA* bersifat admissible

bila memenuhi syarat-syarat, yaitu: di dalam graph state space setiap node

memiliki successor yang terbatas, setiap arc pada graph memiliki biaya yang

lebih besar dari 0, dan heuristic untuk setiap node n, h(n) < h*(n). SMA *

dikatakan complete dan optimal dengan mengasumsikan sebuah heuristic yang

admissible dan konsisten.

Simplified Memory-Bounded A* ini dikembangkan karena algoritma A*

menggunakan banyak memory sehingga menghabiskan memory untuk pencarian.

Algoritma ini menjalankan best first search selama memory masih tersedia,

apabila memory penuh maka node dengan nilai terburuk dibuang, namun nilai

terbaik disimpan pada node atasnya. Jika ruang memory mencukupi untuk semua

node pada tree dalam jalur pencarian, maka repeated states tidak akan diulang

sehingga pencarian akan menjadi optimal.

Aturan-aturan SMA* [8]:

1. Jika mempunyai lebih dari satu simpul, maka pilih salah satu yang

mempunyai f-cost terkecil. Jangan hapus dulu simpul tersebut sebelum

mengeceknya terlebih dahulu, karena bisa jadi simpul tersebut akan

dipakai dulu oleh simpul yang lain.

2. Jika hasil f-cost dari suksesor baru yang telah dibangkitkan hasilnya lebih

kecil, maka suksesor-suksesor sebelumnya dihapus. Tetapi jika lebih

besar, maka lanjutkan dulu pencarian ke suksesor yang lebih kecil,

sebelum menghapus suksesor yang lebih besar tersebut.

3. Jika menemukan state di level yang lebih dangkal, dan mmpunyai f-cost

lebih besar, maka state tersebut juga harus dihapus.

REFERENSI : http://elib.unikom.ac.id/files/disk1/623/jbptunikompp-gdl-aerajatras-31102-10-13.unik-2.pdf