download Makalah Kecerdasan buatan metode generate and text lengkap

Baca Juga

MAKALAH

KECERDASAN BUATAN

OLEH :

NAMA               : AAN KALPIN

 STB                     : 152116

 KELAS                : C

 JURUSAN          : TEKNIK INFORMATIKA

SEKOLAH TINGGI MANAJEMEN DAN INFORMATIKA (STMIK)  DIPANEGARA MAKASSAR JURUSAN TEKNIK INFORMATIKA TAHUN AJARAN
2017/2018

A.   Pembangkit & Pengujian (Generate & Test)

Pada prinsipnya metode ini merupakan penggabungan antara Depth-First Search dengan pelacakan mundur,yaitu bergerak ke belakang menuju pada suatu keadaan awal

Algoritma :

1.      Bangkitkan suatu kemungkinan solusi

2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara mebandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang di harapkan
3. Jika soulsi ditemukan ,keluar.Jika tidak ulangi langkah pertama

Jika pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya (bila ada).  Namun, jika ruang problema sangat besar, maka proses ini akan membutuhkan waktu yang lama. Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.

Kelemahan : Perlu membangkitkan semua kemungkinan sebelum dilakuka pengujian,Membutuhkan Waktu yang lama dalam pencariannya

Contoh:

 “Travelling Salesman Problem (TSP)” Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi tepat  1 kal i. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini: 

Penyelesaian dengan metode Generate and Test

B.    Pendakian Bukit (Hill Climbing)

Metode ini hampir sama dengan metode pembangkitan & pengujian hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan.

Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah ya atau tidak. Dalam prosedurHill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :

1.      Buatlah solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke langkah berikutnya.

2.      Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.

3.      Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :

Ø  Kirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.

Ø  Jika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah.

Ø  Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan.

Ø  Kembalilah ke langkah 2.

Masalah-masalah yang mungkin timbul pada prosedur Hill Climbing :

ü  Maksimum lokal adalah suatu keadaan yang lebih baik daripada semua tetangganya namun masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya.

ü  Daratan  (Plateau) adalah suatu daerah datar dari ruang pencarian (search) dimana semua himpunan keadaan tetangganya memiliki nilai yang sama.

ü  Punggung (Ridge) adalah suatu daerah ruang pencarian (search) yang lebih tinggi daripada daerah sekitarnya, namun tidak dapat dibalikkan oleh langkah–langkah tunggal ke arah manapun.
Solusinya:

ü  Melakukan langkah balik (backtracking) ke simpul yang lebih awal dan mencoba bergerak ke arah yang lain.

ü  Melakukan lompatan besar ke suatu arah untuk mencoba bagian ruang pencarian yang baru.

ü  Menerapkan dua atau lebih aturan sebelum melakukan uji coba. Ini bersesuaian dengan bergerak ke beberapa arah sekaligus.

C.  Steepest Ascent Hill Climbing

Steepest Ascent Hill Climbing sebenarnya hampir sama dengan simple hill climbing hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri

Algoritma :

1.      Mulai dari keadaan awal lakukan pengujian,jiak merupakan tujuan maka 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

3.      Tentukan SUCC sebagai nilai heuristic terbaik dari success or successor

4.      Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang

5.      Gunakan operator tersebut dan bentuk keadaan baru

6.      Evaluasi keadaan baru tersebut

7.      Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang,ubah node SUCC menjadi keadaan sekarang

DAFTAR PUSTAKA

http://aiukswkelasfkelompok6.blogspot.sg/2009/02/pencarian-materi-ini-membahas-tentang.html

http://najibzot.blogspot.sg/p/teknik-searching-kecerdasan-buatan-di.html

http://fryunfirst.blogspot.sg/2015/06/pencarian-heuristik-heuristic-search.html