Pencarian Heuristic

PENGETAHUAN TEKNOLOGI SISTEM CERDAS

HEURISTIC SEARCH STRATEGY

DOSEN : ESSY MALAYS SARI SAKTI

  

3KA10

NABILAH AIDAHNANDA GANARI

NPM. 14115887

UNIVERSITAS GUNADARMA

III.1  Strategi Pencarian Berbentuk/Heuristic Search Strategy

·           Best-First Search

Merupakan metode yang membangkitkan suksesor dengan mempertimbangkan harga (didapat dari fungsi heuristik tertentu) dari setiap node, bukan dari aturan baku seperti DFS maupun BFS. Langkah-langkah yang dilakukan oleh algoritma Best First Search. Pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal. Pada langkah 2, node D terpilih karena harganya paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node B paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya akan dibangkitkab semua suksesor B. Demikian seterusnya sampai ditemukan node Tujuan.

Untuk mengimplementasikan algoritma pencarian ini, diperlukan dua buah

senarai, yaitu: OPEN untuk mengelola node-node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE untuk mengelola node-node yang pernah dibangkitkan dan sudah

dievaluasi.

Algoritma selengkapnya adalah sebagai berikut:

1.   Mulailah dengan OPEN yang hanya berisi state awal

2.  Sampai tujuan ditemukan atau tidak ada nya nodes tersisa pada OPEN. Lakukan :

a) Pilih node terbaik pada OPEN

b) Menghasilkan penggantinya.

c) untuk masing-masing pengganti. Lakukan :

−        Jika belum dibuat, evaluasilah, tambahkan ke OPEN dan catat induk

−       Jika telah dihasilkan, ubah induk jika jalur baru ini lebih baik dari yang sebelumnya. Dalam hal ini, perbarui biaya untuk mendapatkan simpul ini dan kepada pengganti yang mungkin dimiliki oleh simpul ini 

·           Greddy Search

Merupakan Best First Search dengan hanya mempertimbangkan harga perkiraan (estimated cost). Sedangkan harga sesungguhnya tidak digunakan. Sehingga solusi yang dihasilkan tidak optimal

pencarian jalur dalam suatu daerah yang direpresentasikan dalam suatu

graph. Node menyatakan kota dan busur menyatakan jarak antar kota (harga sesungguhnya)

dan h’(n) adalah harga perkiraan dari node n menuju node tujuan (G).

Dengan h’(n) = fungsi heuristik (jarak garis lurus dari node n menuju G).

Pada kasus di atas, jalur yang terpilih adalah: I-C-D-G = 140 + 160 + 200 = 500.

Padahal jalur terbaik adalah: I-A-B-G = 75 + 85 + 300 = 460.

·           A* Search

Merupakan algoritma Best First Search dengan menggabungkan Uniform Cost Search dan Greedy Search. Harga yang dipertimbangkan didapat dari harga sesungguhnya ditambah dengan harga perkiraan. Dalam notasi matematika dituliskan: f’(n) = g(n) + h’(n). Dengan penggunaan f’(n), maka algoritma A* adalah Complete dan

Optimal. Pada algoritma ini juga digunakan dua senarai, yaitu: OPEN dan CLOSE.

Pada saat A sebagai Best Node, maka akan dibangkitkan B dan G. Karena B sudah berada di CLOSE maka akan dicek apakah parent dari B harus diganti atau tidak. Karena g(B) melalui A (10 + 10 = 20) lebih kecil daripada g(B) melalui I (25), maka parent dari B harus diganti. Begitu juga dengan f’(B) yang tadinya 85 menjadi 80. Kemudian akan dilakukan propagasi ke semua suksesor B. Dalam hal ini adalah node E yang semula g(E) = 35 menjadi 30 dan f’(E) yang semula 105 menjadi 100, dan node J yang semula g(J) = 75 menjadi 70 dan f’(J) yang semula 95 menjadi 90.

·           Memory Bounded Search

Untuk masalah tertentu, dimana memory komputer (RAM) terbatas, algoritma A*

tidak mampu menyelesaikannya. Terdapat dua algoritma modifikasi A*, untuk mengatasi

masalah memory, yaitu:

a.       Iterative Deepening A* (IDA*)

Iterative Deepening Depth-First Search menggunakan batasan level (kedalaman) dalam setiap iterasi pencariannya. Di sini ide tersebut diterapkan pada algoritma A* dengan membatasi fungsi heuristiknya. Proses pencarian pada setiap iterasi akan mengembalikan nilai f-limit yang baru yang akan digunakan sebagai batasan pencarian untuk iterasi berikutnya[RUS95]. Sama seperti A*, IDA* adalah complete dan optimal.

b.   Simplified Memory Bounded A

adalah algoritma jalur terpendek algoritma A *. Keuntungan utama dari SMA * adalah bahwa ia 

meguaa n memori yang dibatasi.











menjelaskan bagaimana algoritma SMA* melakukan pencarian jalur dengan dibatasi maksimum 3
node yang boleh tersimpan di memori. A adalah node asal, dan D, I, F, J adalah
node-node yang bisa menjadi node tujuan. Dengan batasan 3 node, maka SMA* dapat
menemukan solusi yang paling optimal, yaitu A - B - D. Jika harga node J adalah
19 (lebih kecil dari harga node D (20)), maka SMA* gagal menemukan solusi
optimal. Kecuali jika jumlah node maksimum yang boleh tersimpan di memori
adalah 4.









III.2  Fungsi Heuristic


Pencarian Heuristic merupakan teknik yang mengembangkan efisiensi dalam proses  pencarian 

(pencarian yang lebih simple). Namun kemungkinan juga dapat mengorbankan 


kelengkapan (complateness).Fungsi Heuristic adalah fungsiyang melakukan pemetaan 


(mapping) dari diskripsi keadaan masalah (problema) ke pengukur kebutuhan, umumnya 


direpresentasikan berupa angka. Dalam pencarian state space,heuristik adalah aturan untuk 


memilih cabang-cabang yang paling mungkin menyebabkan penyelesaian permasalahan dapat diterima. 


Heuristic digunakan untuk mengevaluasi keadaan problema individual dan menentukan 


seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.



III.3  Algoritma Pencarian Lokal dan Masalah Optimisasi




·          Hill Climbing


Hill Climbing, yaitu pada feedback dari prosedur test untuk membantu pembangkit menentukan 


yang langsung dipindahkan dalam ruang pencarian. HC sering digunakan jika terdapat fungsi 


heuristic\yang baik untuk mengevaluasi state. Sebagai contoh, anda berada di sebuah kota yang 


tidak dikenal, tanpa peta dan anda ingin menuju ke pusat kota. Cara sederhana adalah gedung


yang tinggi. Fungsi heuristics-nya adalah jarak antara lokasi sekarang dengan gedung yang tinggi 

dan state yang diperlukan adalah jarak yang terpendek




a.       Simple HC



Algoritma : Simple HC

1.      Evaluasi state awal. Jika itu juga merupakan state tujuan, maka kembalikan

dan berhenti. Jika tidak, lanjutkan denganstate  awal sebagai state saat ini


2.     Loop sampai solusi ditemukan atau sampai tidak ada operator baru yang tersisa untuk 

      diterapkan seperti keadaan saat ini:


     a). Pilih operator yang belum diterapkan ke state saat ini dan menerapkannya untuk 

          menghasilkan sebuah negara baru


b).Evaluasi state baru :




−       Jika itu adalah state tujuan, maka kembalikan dan berhenti

−        Jika bukan keadaan tujuan tapi lebih baik dari state saat ini, maka buatlah itu kondisi 

      saat ini.

−        Jika tidak lebih baik dari state saat ini, maka lanjutkan dalam loop



b.       Steepest-Ascent HC



Algoritma : Steepest-Ascent HC

1.      Evaluasi state awal. Jika itu juga merupakan state tujuan, maka kembalikan dan berhenti. Jika 

      tidak, lanjutkan dengan state awal sebagai state saat ini


2.      Loop sampai solusi ditemukan atau sampai iterasi yang lengkap tidak menghasilkan perubahan

      state saat ini:


a). Memberi SUCC menjadi state yang memungkinkan mengganti state saat ini menjadi lebih 

     baik dari SUCC



            b).  Untuk setiap operator yang berlaku untuk state saat ini lakukan:

−        Terapkan operator dan buat state baru

−        Evaluasi state baru. Jika merupakan tujuan state, maka kembalikan dan berhenti. Jika 

      tidak, bandingkan dengan SUCC. Jika lebih baik,maka tetapkan SUCC menjadi state, 

      jika tidak, tinggalkan SUCC

            c). Jiika SUCC lebih baik dari state saat ini, maka tetapkan state saat ini ke SUCC  




·       Simulated Annealing


SA memanfaatkan analogi antara cara pendinginan dan pembekuan metal menjadi sebuah


struktur crystal dengan energi yang minimal (proses penguatan) dan pencarian untuk state tujuan 


minimal dalam proses pencarian. Tidak seperti pendekatan HC (dengan jalan mengikuti sebuah 


turunan yang tetap dalam meminimisasi masalah), SA lebih banyak menjadi jebakan pada local 


minima.




Algoritma: Simulated Annealing


1.     Evaluasi state awal. Jika itu juga merupakan state tujuan, maka kembalikan dan berhenti. Jika 


     tidak, lanjutkan dengan state awal sebagai state saat ini


2.  Inisialisasi BEST-SO-FAR ke state saat ini

3.  Inisialisasi T sesuai dengan jadwal annealing.


4.  Loop sampai solusi ditemukan atau tidak adanya operator yang tersisa
untuk  diterapkan ke state saat ini:


a)  Pilih operator yang belum di terapkan ke state saat ini dan terapkan operator untuk 


     menghasilkan state baru.


b) Evaluasi state baru. Hitung







ΔE = (value of current) – (value of new state)




§        Jika state baru merupakan tujuan, maka kembalukan dan berhenti.


§        Jika bukan tujuan state tetapi lebih baik dari state saat ini, maka jadikan state tersebut


      menjadi state saat ini. Juga tetapkan BEST-SO-FAR menjadi state baru


§        Jika tidak lebih baik dari state saat ini, maka buatlah state saat ini dengan probabiltas p'


      seperti yang didefinisikan di atas. Langkah ini biasanya diimplementasikan dengan 


      memanggil generator bilangan acak untuk menghasilkan angka pada kisaran [0,1]. Jika 


      angka itu kurang dari p ', maka langkah tersebut diterima. Jika tidak melakukan apa-apa.

            c) Revisi sesuai kebutuhan sesuai jadwal annealing.


5.   Kembalikan BEST-SO-FAR sebagai jawaban.


·       Algoritma Genetika (Genetic Algorithm)

    Genetic Algorithm (GA) adalah algoritma pencarian yang didasarkan pada mekanisme 

seleksi alamiah dan genetika alamiah. GA dimulai dengan serangkaian solusi awal 

(kromosom), yang disebut populasi. Populasi ini akan ber-evolusi menjadi populasi yang  

berbeda melalui serangkaian iterasi. Pada akhir iterasi, GA mengembalikan anggota populasi 

yang terbaik sebagai solusi untuk problem tersebut. Pada setiap iterasi (generasi), proses 

evolusi yang terjadi adalah sebagai berikut:




1.   Dua anggota populasi (parent) dipilih berdasarkan pada suatu distribusi populasi. Kedua 

      anggota ini kemudian dikombinasikan atau dikawinkan melalui operator crossover (pindah 

      silang) untuk menghasilkan anak (offspring).

2.   Dengan probabilitas yang rendah, anak ini akan mengalami perubahan oleh operator mutasi.

3.  Apabila anak sesuai untuk populasi tersebut, suatu skema penggantian (replacement scheme) 
    diterapkan untuk memilih anggota populasi yang akan digantikan oleh anak.


4.  Proses ini terus berulang sampai dicapai kondisi tertentu, misalnya sampai jumlah iterasi tertentu.



Sifat-Sifat Khusus GA [GOL89]:

1.  GA bekerja dengan sebuah pengkodean dari kumpulan parameternya sendiri.

  2.  GA mencari dari sebuah populasi titik-titik, bukan dari sebuah titik tunggal.

  3.  GA hanya menggunakan informasi hasil (fungsi objektif), bukan menurunkan dar bantuan 

       pengetahuan lain.

  4.  GA menggunakan kemungkinan aturan transisi, bukan aturan-aturan deterministik.










III.5  Referensi




           [1]  Suyanto,ST. Intelijensia Buatan. Bandung. EBook

           [2]  Luhukay, J. "Pencarian Heuristic Intelegensi Buatan" . Metode pencarian heuristic. 

                 Tersedia : Metode pencarian heuristik- download [Diakses : 5 Okt 2017].


LINK DOWNLOAD FILE