Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Hill Climbing Algorithm

No description
by

Yunindyo Prabowo

on 15 December 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Hill Climbing Algorithm

Heuristic Search
Problem Set
Metode Hill Climbing dibagi menjadi dua jenis, yaitu Simple Hill Climbing dan Steepest-Ascent Hill Climbing. Metode Steepest-Ascent Hill Climbing ini merupakan pengembangan dari metode Simple Hill Climbing. Bedanya adalah Simple Hill Climbing menentukan next state dengan membandingkan current state dengan satu successor dan successor pertama yang lebih baik akan dipilih menjadi next state. Sedangkan Steepest-Ascent akan membandingkan current state dengan semua succesors yang ada didekatnya. Sehingga dalam Steepest-Ascent Hill Climbing, next statenya merupakan successor yang paling baik atau paling mendekati tujuan


PENDAHULUAN
HILL CLIMBING ALGORITHM
SIMPLE HILL CLIMBING
Simple Hill Climbing
STEEPEST-ASCENT Hill Climbing
$1.25
Wednesday, December 16, 2015
A11.4505
PRESENTED BY
Problem Set
STEEPEST ASCENT HILL CLIMBING
Algoritma Steepest Ascent Hill Climbing hampir sama dengan simple hill climbing , namun pada algoritma ini seluruh nilai suksesor dibandingkan untuk mendapatkan nilai terbaik.
Hill Climbing Algorithm

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).
Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

INTRODUCE OF CLIMBING HILL ALGORITHM
Types of Hill Climbing Algorithm
a. Mulai dari keadaan awal, lakukan
pengujian : jika merupakan tujuan, maka
berhenti; dan jika tidak, lanjutkan dengan
keadaan sekarang sebagai keadaan awal.
b. Kerjakan langkah-langkah berikut sampai
solusi ditemukan, atau sampai tidak ada
operator baru yang akan diaplikasikan pada
keadaan sekarang :
1. Cari operator yang belum pernah
digunakan; gunakan operator ini untuk
mendapatkan keadaan yang baru.
2. Evaluasi keadaan baru tersebut.
a. Jika keadaan baru merupakan tujuan,
keluar.
b. Jika bukan tujuan namun nilainya lebih
baik dari keadaan sekarang, maka
jadikan keadaan baru tersebut menjadi
keadaan sekarang
3. Jika keadaan baru tidak lebih baik daripada
keadaan sekarang, maka lanjutkan iterasi.

1. Mulai dari keadaan awal, lakukan pengujian : jika merupakan tujuan maka akan berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal
2. Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang.
a. Tentukan SUCC sebagai nilai heuristik terbaik dari successor – successor
b. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:
i. Gunakan operator tersebut dan bentuk keadaan baru
ii. Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai heuristiknya denngan SUCC. Jika lebih baik, jadikan nilai keadaan heuristik baru tersebut sebagai SUCC. Namun, jika tidak lebih baik, nilai SUCC tidak berubah
iii. Jika SUCC lebih baik dri pada nilai heuristik keadaan sekarang, ubah node SUCC menjadi keadaan sekarang
TSP Problem with Simple Hill Climbing
ABCD (10)
BACD (9)
CBAD (8)
DBCA (12)
ACBD (12)
ADCB (9)
ABDC (8)
ABCD (10)
CABD (9)
DACB (10)
BCAD (10)
DABC (8)
CADB (8)
ABDC (8)
BCDA (9)
BDAC (8)
BADC (6)
BDAC (10)
BADC (9)
Sebagai ilustrasi teknik pencarian simple hill climbing digunakan contoh masalah TSP pada masalah generate and test . Operator yang digunakan adalah operator yang dapat menghasilkan kombinasi lintasan kota yang berbeda-beda, yaitu dengan cara menukar posisi masing-masing kota. Untuk mempermudah penukaran posisi, kita cukup menukar posisi 2 kota, operator untuk kombinasi lintasan dengan menukar posisi 2 kota dapat dihitung dengan kalkulasi
Yaitu :
1. (1,2) menukar posisi kota kesatu dan kedua
2. (1,3) menukar posisi kota kesatu dan ketiga
3. (1,4) menukar posisi kota kesatu dengan keempat
4. (2,3) menukar posisi kota kedua dengan kota ketiga
5. (2,4) menukar posisi kota kedua dengan keempat
6. (3,4) menukar posisi kota ketiga dengan keempat

(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
Permasalahan yang mungkin timbul pada Simpel Hill Climbing :

1. Algoritma akan berhenti kalau men-capai
nilai optimum local.
2. Urutan penggunaan operator akan sangat
berpengaruh pada penemuan solusi.
3. Tidak diijinkan untuk melihat satupun
langkah sebelumnya.
TSP Problem with Steepest Ascent Hill Cllimbing Algorithm
ABCD (10)
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
BACD (9)
CBAD (8)
DBCA (12)
ACBD (12)
ADCB (9)
ABDC (8)
ABCD (10)
CABD (9)
DACB (10)
BCAD (10)
BADC (6)
BDAC (10)
TSP Problem with Steepest Ascent Hill Cllimbing Algorithm
ABCD (10)
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
BACD (9)
CBAD (8)
DBCA (12)
ACBD (12)
ADCB (9)
ABDC (8)
BCAD (10)
ABCD (10)
DBAC (9)
CABD (9)
CBDA (9)
CDAB (6)
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
DCAB (9)
ADCB (9)
BDAC (8)
CADB (8)
CDBA (8)
CBAD (8)
Permasalahan yang timbul Pada stepest-ascent hill climbing
LOCAL OPTIMUM : Keadaan dimana semua tetangga lebih buruk atau sama dengan dirinya. Sering muncul ketika sudah mendekati solusi.
Hill Climbing Algorithm
PENUTUP
Kelebihan Dan Kekurangan
Kelebihan :
Kekurangan :

Implementasi algoritma Hill Climbing
Game Number Puzzle Slider
current node
← MAKE NODE(initial state)
loop
neighbor
← the best successor of current node
if
value(neighbor) ≤ value(current node) then current node ← neighbor
else

return
current node

General Hill Climbing Algorithm
Plateu : Keadaan semua tetangga sama dengan dirinya.



Ridge : Local Optimum yang lebih disebabkan karena ketidakmampuan untuk menggunakan 2 operator sekaligus.
Optimasi pencarian jarak terdekat pada peta (Romanian Problem)

Pencarian rute pada robot mobil standalone
News Today
Quotes Of Today
-> SEPTIAN IDHI PANGESTU
A11.2013.07669


-> SOFYAN DAUD
A11.2013.07656


->YUNINDYO PRABOWO
A11.2013.07657
Algoritmnya relative sederhana dibanding metode pencarian maupun optimasi lainnya.
Penggunaan memori lebih sedikit karena tidak menyimpan keseluruhan kemungkinan , hanya menyimpan state yg terpilih
Dapat terjebak di local maksimum sehingga tidak mendapatkan solusi yang maksimal
Membutuhkan waktu yang relative lama karena ada kemungkinan algoritma ini mengunjungi semua state sebelum memilih langkah selanjutnya.
Full transcript