KECERDASAN BUATAN _ PERTEMUAN 8,9,10,11

 KECERDASAN BUATAN 

   informatika B 2018

PERTEMUAN 8,9,10,11

 HEURISTIC

Kata Heuristic berasal dari dari srbuah kata kerja bahsa Yunani (hyu-RIS-tik) Heuriskein yang berarti mencari atau menemukan.Heuristic juga dapat diartikan  jarak atau nilai yang menyatakan seberapa dekat suatu state ke goal.

Heuristic Function

•fungsi heuristic dapat diterima jika perkiraan biaya yang dihasilkan tidak melebihi biaya sebenarnya.

•Fungsi heuristic yang terlalu  tinggi dapat memebuat proses pencarian menjadi hilang atau mencapai hasil yang tidak optimal.

•Semakin mendekati biaya sebenrnya, semakin baik fungsi heuristiknya.

Adapun jenis-jenis Heuristic Search :

a.Hill Climbing 

Dalam Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristic yang menyediakan pengukuran kedekatan suatu keadaan yang diberi dengan tujuan (goal).

HC Algorithm

  1. Mengevaluasi keadaan awal jika itu adalah  keadaan  tujuan, berhenti jika keadaan saat ini adalah keadaan awal

  2. Ulangi sampaikeadaan saat ini adalah keadaan tujuan atau tidak ada operator baru yang tersedia:

   •Pilih operator baru untuk status ini dan buat status baru.

   •Evaluasi status baru.

  ~ Jika heuristicnya mendekati tujuan maka  jadikan itu sebagai keadaan saat ini.

  ~Jika heuristinya tidak mendekati tujuan maka bisa diabaikan.

Steepest-Ascent Hill Climbing

•Dalam pendakian bukit sederhana, simpul terdekat pertama dipilih, sedangkan

•Di bukit pendakian yang paling curam, semua penerus dibandingkan dan yang paling dekat dengan solusi di pilih.

•Ini menunjukkan bahwa ia memiliki elemen algoritma pertama yang luas.

a. Simulated Annealing (SA)

•SA menggunakan formula probabilitas yang memungkinkan untuk mengeluarkan minimum local

•SA menggunakan formula probabilitas yang biasa disebut dengan konsep coba-coba.

•Status baru yang tidak lebih baik dari status saat ini masih dapat dipilih dengan probabilitas.

b.Best-firs search

•Best-first search menggunakan fungsi evaluasi f (n) untuk setiap node

f (n) memberikan perkiraan untuk total biaya

Perluas simpul n dengan f(n) terkecil 

•Biasanya diimplementasikan menggunakan priority queue (antrian prioritas).

Best-First Search Algorithm

•OPEN : berisi node-node yang sudah dibangkitkan, sudah memiliki fungsi  heuristic  namun belum diuji.Umumnya berupa antrian berprioritas yang berisi  elemen-elemen dengan nilai heuristic tertinggi.

•CLOSED : berisis node-node yang sudah diuji.

c. Greedy best-first search

Pencarian Terbaik Pertama yang paling sederhana Hanya memperhitungkan perkiraan biaya sedangkan biaya sebenarnya tidak dimasukkan ke dalam akun f(n) = h(n). Penilaian nodenya ditentukan berdasarkan heuristiknya yang lengkap  namun tidak optimal. Kompleksitas ruang = 0(bm) sedangkan kompleksitas waktu = 0(bm).

d. A* Search 

Menggabungkan Uniform Cost Search dan Greedy Best-First Search.Hindari  memperluas jalur yang sudah mahal. Fungsi tersebut dihitung dari biaya aktual dan perkiraan biaya f(n) = g(n) + h(n).Performance A* Search yaitu lengkap dan optimal.