Tugas Algoritma

Oleh Muldiana Muldiana

297,8 KB 11 tayangan 0 unduhan
 
Bagikan artikel

Transkrip Tugas Algoritma

KATA PENGANTAR Puji syukur kehadirat Tuhan Yang Maha Esa karena berkat dan rahmatnya, penulis bisa menyusun dan menyajikan makalah“KECERDASAN BUATAN”. Penulis juga mengucapkan terima kasih kepada Dosen Mata Kuliah Kecerdasan Buatan yang telah memberikan bimbingannya dalam proses penyusunan makalah ini. Tak lupa penulis mengucapkan terima kasih kepada berbagai pihak yang telah memberikan dorongan dan motivasi. Penulis menyadari bahwa dalam penyusunan makalah ini masih terdapat banyak kekurangan dan jauh dari kesempurnaan. Oleh karena itu, penulis mengharapkan kritik serta saran yang membangun guna menyempurnakan makalah ini dan dapat menjadi acuan dalam menyusun makalah-makalah atau tugastugas selanjutnya. Penulis juga memohon maaf apabila dalam penulisan makalah ini terdapat kesalahan pengetikan dan kekeliruan sehingga membingungkan pembaca dalam memahami maksud penulis. , 27 September 2016 Penulis DAFTAR ISI COVER KATA PENGANTAR……………………………………………………………….. i DAFTAR ISI………………………………………………………………………… ii BAB I PENDAHULUAN 1.1 Latar Belakang…………………………………………………………….. 1 1.2 Batasan Masalah …………………………………………………………... 1 1.3 Tujuan………...…………………………………………………………… 1 1.4 Metode……………………………………………………………………. 2 BAB II PEMBAHASAN 2.1 Pencarian Heuristik (Heuristic Search)……………..…………………….. 3 2.1.1 Generate and Test……………………………………………... 5 2.1.2 Hill Climbing………………………………………………….. 7 2.1.3 Best- First Search……………………………………………… 9 2.1.4 Simulated Annealing……………………………………….... 16 BAB III PENUTUP 3.1 Kesimpulan……………………………………………………………..... 19 DAFTAR PUSTAKA………………………………………………………………. 20 BAB I PENDAHULUAN 1.1 Latar Belakang Dalam ilmu komputer, sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar algoritma yang dipelajari oleh ilmuwan komputer adalah algoritma pencarian. Himpunan semua kemungkinan solusi dari sebuah masalah disebut ruang pencarian. Algortima pencarian brute-force atau pencarian naif/ uninformed menggunakan metode yang sederhana dan sangat intuitif pada ruang pencarian, sedangkan algoritma pencarian informed menggunakan heuristik untuk menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian. Adapun dalam metode pencarian blind atau buta digunakan karena memang tidak ada informasi awal yang digunakan dalam proses pencarian. Algoritma Pencarian ini menggunakan Metode BFS, DFS, dll. 1.2 Batasan Masalah Makalah ini membahas tentang dan Metode Pencarian Heuristik, Generate and Test, Hill Climbing, Simple Hill Climbing, Steepest-Ascent Hill Climbing, Best-First Seacrh, Algoritma A*, Simulated Annealing. 1.3 Tujuan Tujuan dari Pembuatan Makalah ini, antara lain agar : 1. Mahasiswa mampu memahami apa itu Metode Pencarian Heuristik, Generate and Test, Hill Climbing, Simple Hill Climbing, Steepest-Ascent Hill Climbing, Best-First Seacrh, Algoritma A*, Simulated Annealing. 2. Mahasiswa mampu membedakan Metode Pencarian Heuristik, Generate and Test, Hill Climbing, Simple Hill Climbing, Steepest-Ascent Hill Climbing, Best-First Seacrh, Algoritma A*, Simulated Annealing. 1.4 Metode Metode yang digunakan penulis dalam pembuatan Makalah ini adalah dengan mencari referensi di internet. BAB II PEMBAHASAN 2.1 Pencarian Heuristik (Heuristic Search) Heuristic search adalah suatu istilah yang berasal dari bahasa Yunani yang berarti menemukan/ menyingkap. Heuristik adalah suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga sebagai suatu kaidah yang merupakan metoda/ prosedur yang didasarkan kepada pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu. George Poyla (dalam Kristanto. A, 2003) mendefinisikan heuristik sebagai ”studi tentang sebuah metode dan aturan discovery serta invention” dalam pencarian state space, heuristik didefinisikan sebagai aturan untuk memilih cabang-cabang dalam ruang keadaan yang paling tepat untuk mencapai solusi permasalahan yang dapat diterima . Pemecahan masalah AI menggunakan heuristik dalam dua situasi dasar (Setiawan. S, 1993), yaitu : a. Permasalahan yang mungkin tidak mempunyai solusi yang pasti disebabkan oleh ambiguitas (keraguan/ketidakpastian) mendasar dalam pernyataan permasalahan atau data yang tersedia, contohnya diagnosa kedokteran. b. Permasalahan yang boleh jadi memiliki solusi pasti, tetapi biaya komputasinya untuk mendapatkan solusi tersebut mungkin sangat tinggi. Dalam banyak problema (misalnya saja catur), pertumbuhan state space adalah secara kombinatorial eksplosif dengan bayak state yang mungkin meningkat secara eksponensial atau faktorial dengan kedalaman pencarian. Dalam hal ini,exhaustive, yakni teknik pencarian brute force seperti pencarian mendalam pertama dan pencarian meluas pertama mungkin gagal menemukan solusi sehingga heuristik akan menangani kerumitan permasalahan ini dengan panduan pencarian pada sepanjang lintasan yang memeberi harapan melewati state. Dengan mengeliminasi state yang tidak memberi harapan dan turunannya dari ruang tersebut maka algoritma heuristik dapat mengalahkan ledakan kombinatorial dan menemukan penyelesaian yang dapat diterima. Pencarian terbimbing (heuristic search) dibutuhkan karena pencarian buta (blind search) tidak selalu dapat diterapkan dengan baik, hal ini disebabkan waktu aksesnya yang cukup lama serta besarnya memori yang diperlukan. Dalam pencarian ruang keadaan, heuristik dinyatakan sebagai aturan untuk melakukan pemilihan cabang-cabang dalam ruang keadaan yang paling tepat untuk mencapai solusi permasalahan yang dapat diterima. Heuristik dapat digunakan pada beberapa kondisi berikut ini (Siswanto, 2010): · Mengatasi combinatorial explosion. Ada masalah yang kemungkinan arah penyelesaiannya berkembang pesat (bersifat faktorial) sehingga menimbulkan combinatorial explosion. Heuristik merupakan cara untuk menentukan kemungkinan arah penyelesaian masalah secara efisien. · Solusi paling optimal mungkin tidak diperlukan.Dalam suatu keadaan, mungkin lebih baik mendapatkan solusi yang mendekati optimal dalam waktu yang singkat daripada solusi yang paling optimal dalam waktu yang lama. · Pada umumnya hasilnya cukup baik. Sekalipun tidak optimal, tetapi biasanya mendekati optimal. Membantu pemahaman bagi orang yang menyelesaikan persoalan. · Banyak alternatif heuristik yang dapat diterapkan dalam suatu percobaan. Orang yang menyelesaikan persoalan tersebut akan lebih mengerti persoalannya jika mencoba heuristik yang diterapkannya. Salah satu contoh dari heuristik yang baik untuk tujuan umum yang berguna untuk beragam kombinasi permasalahan adalah the nearest neighbour heuristic, yang bekerja dengan cara menyeleksi alternatif yang paling tinggi secara lokal pada setiap langkahnya. Fungsi heuristik yang dirancang dengan baik dapat berperan dalam sebuah bagian yang penting untuk memandu secara efisien proses pencarian menuju ke sebuah solusi. Kadang kala sebuah nilai tinggi dari fungsi heuristik mengindikasikan sebuah posisi yang baik secara relatif, di lain waktu sebuah nilai rendah mengindikasikan sebuah situasi yang menguntungkan. Program yang menggunakan nilai (value) dari fungsi dapat mengusahakan minimal atau maksimal secara tepat. Tujuan dari sebuah fungsi heuristik adalah untuk memandu proses pencarian tujuan yang menguntungkan dengan menganjurkan jalur yang mana yang diikuti pertama kali ketika tersedia lebih dari satu tujuan. Setelah proses berlangsung, akan bisa dihitung sebuah fungsi heuristik yang sempurna dengan cara melakukan sebuah pencarian yang lengkap dari simpul dalam pertanyaan dan menentukan apakah fungsi ini menuju ke sebuah solusi yang baik. Sayangnya, seperti semua kaidah penemuan lainnya, heuristik juga dapat salah. Heuristik hanyalah panduan informasi untuk menebak langkah berikutnya yang harus diambil dalam menyelesaikan suatu permasalahan, dan sering dilakukan berdasarkan eksperimen/ percobaan atau secara intuisi. Oleh karena menggunakan informasi yang terbatas, heuristik jarang dapat memprediksi tingkah laku yang eksak dari ruang keadaan saat dilakukan pencarian. Heuristik dapat membimbing algoritma pencarian untuk mendapatkan solusi suboptimal atau gagal menemukan solusi apapun, karena tidak ada solusi yang dapat menuju keadaan akhir. Heuristik dan perancangan algoritma untuk mengimplementasikan pencarian heuristik telah menjadi inti permasalahan penelitian AI. Game playing dan pemecahan teorema (theorem solving) adalah dua aplikasi paling tua dari AI, kedua-duanya memerlukan heuristik untuk memangkas ruang dari solusi yang mungkin. Metode Heuristic Searching: 1. Generate and Test 2. Hill Climbing a. Simple Hill Climbing b. Steepest-Ascent Hill Climbing 3. Best-First Seacrh a. Algoritma A* 4. Simulated Annealing. 2.1.1 PEMBANGKITAN dan PENGUJIAN (Generate and Test) Metode ini merupakan penggabungan antara Depth First Search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal. Algoritma Generate and Test: · Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal). · Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan. · Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama. 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 2.1.2 PENDAKIAN BUKIT (Hill Climbing) Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. Algoritma Pendakian Bukit (Hill Climbing): · Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru. · Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru. · Evaluasi keadaan baru tersebut : – Jika keadaan baru merupakan tujuan, keluar – Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. – Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi. Hill Climbing dibagi menjadi dua jenis yaitu Simple Hill Climbing (Hill Climbing sederhana) dan SteepestAscent Hill Climbing (Hill Climbing dengan memilih kemiringan yang paling tajam/ curam ). 1) Simple Hill Climbing bekerja dengan cara memilih secara langsung new state yang memiliki keadaan lebih baik dari pada keadaan sebelumnya tanpa memperhitungkan keadaan lain yang lebih “curam”. Pada Simple Hill Climbing, ada 3 masalah yang mungkin: · Algoritma akan berhenti kalau mencapai nilai optimum local · Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi · Tidak diijinkan untuk melihat satupun langkah sebelumnya. Algoritma Simple Hill Climbing: · Evaluasi initial state (keadaan awal). Jika initial state adalah goal state maka jadikan state ini sebagai solusi dan keluar dari program. Jika bukan goal state, lanjutkan proses dengan initial state sebagai current state. · Ulangi sampai solusi ditemukan atau sampai tidak ada operator ( aturan produksi ) baru yang dapat diaplikasikan terhadap current state: o Pilih operator yang belum diaplikasikan terhadap current state dan aplikasikan operator tersebut sehingga menghasilkan new state. o Evaluasi new state: § Jika state ini merupakan goal state maka jadikan state ini sebagai solusi dan keluar dari program. § Jika state ini bukan goal state tetapi lebih baik dari current state maka jadikan state ini sebagai current state baru. § Jika state ini tidak lebih baik dari current state maka kembali ke langkah memilih operator. 2) Steepest-Ascent Hill Climbing Steepest-Ascent Hill Climbing lebih menekankan pada aturan produksinya yaitu Steepest-Ascent Hill Climbing akan mengevaluasi semua state yang berada dibawah current state dan memilih state dengan keadaan paling “curam”. Pada Steepest-Ascent Hill Climbing ada 3 masalah yang mungkin yaitu: · Local optimum: keadaan semua tetangga lebih buruk atau sama dengan keadaan dirinya. · Plateau : Keadaan semua tetangga sama dengan dirinya. · Ridge : Local optimum yang lebih disebabkan karena ketidakmampuan untuk menggunakan 2 operator sekaligus. Algoritma Steepest-Ascent Hill Climbing: · Evaluasi initial state. Jika initial state adalah goal state maka jadikan state ini sebagai solusi dan keluar dari program. Jika bukan goal state, lanjutkan proses dengan initial state sebagai current state. · Ulangi sampai solusi ditemukan atau sampai tidak ada perubahan terhadap current state: o Misalkan SUK adalah suatu state yang menjadi suksesor dari current state. o Untuk setiap operator yang bisa dilakukan terhadap current state, kerjakan : § Aplikasikan semua operator yang ada dan bangkitkan new state. § Evaluasi new state. Jika merupakan goal state, jadikan ini sebagai solusi dan keluar dari program. Jika bukan goal state, bandingkan dengan new state dengan SUK. Jika new state lebih baik dari SUK maka ganti SUK dengan new state. Jika new state tidak lebih baik dari SUK, tidak perlu diganti. · 2.1.3 Jika SUK lebih baik dari current state maka ganti current state dengan SUK. PENCARIAN TERBAIK PERTAMA (Best-First Search) Metode ini merupakan kombinasi dari metode depth-first search dan breadth-first search dengan mengambil kelebihan dari kedua teknik tersebut. Hill climbing tidak diperbolehkan untuk kembali ke node pada lebih rendah meskipun node tersebut memiliki nilai heuristic lebih baik. Pada metode bestfirst search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk. Ada beberapa istilah yang sering digunakan pada metode best-first search, yaitu: o Start node adalah sebuah terminology untuk posisi awal sebuah pencarian. o Curret node adalah simpul yang sedang dijalankan dalam algoritma pencarian jalan terpendek. o Suksesor adalah simpul-simpul yang yang akan diperiksa setelah current node o Simpul (node) merupakan representasi dari area pencarian. o Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan. o Closed list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan. o Goal node yaitu simpul tujuan. o Parent adalah curret node dari suksesor. 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 dibangkitkan semua suksesor B. Demikian seterusnya sampai ditemukan node tujuan. Ilustrasi algoritma best-first search dapat dilihat pada gambar dibawah ini. 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. · OPEN berisi initial state dan CLOSED masih kosong. · Ulangi sampai goal ditemukan atau sampai tidak ada di dalam OPEN. o Ambil simpul terbaik yang ada di OPEN. o Jika simpul tersebut sama dengan goal, maka sukses o Jika tidak, masukkan simpul tersebut ke dalam CLOSED o Bangkitkan semua aksesor dari simpul tersebut o Untuk setiap suksesor kerjakan: § Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke OPEN, dan catat parent. § Jika suksesor tersebut sudah pernah dibangkitkan, ubah parent-nyajika jalur melalui parent ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya perbarui biaya untuk suksesor tersebut dn nodes lain yang berada di level bawahnya. Contoh: Misalkan kita memiliki ruang pencarian seperti pada gambar dibawah. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengan node A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa mengurut nilai untuk setiap node. Algoritma yang menggunakan metode best-first search, yaitu: a. Algoritma A* A* adalah algoritma best-first search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal. Contoh: o Langkah 1: Arena Berikut adalah contoh simple arena yang akan kita gunakan. Warna hijau adalah starting point, warna merah adalah goal/end point, dan biru adalah penghalang. Goal dari aplikasi ini adalah mencari rute dari titik hijau ke merah tanpa melewati penghalang biru o Langkah 2: Movement Cost / Biaya Pergerakan Kita asumsikan setiap langkah dari hijau adalah legal baik vertikal, horizontal, maupun diagonal dengan catatan tidak membentur tembok. Setiap langkah yang diizinkan kita berikan nilai G dimana G adalah cost atau biaya dalam setiap langkah. Dalam kasus ini kita akan berikan nilai 10 untuk setiap langkah vertikal maupun horizontal, dan 14 untuk diagonal. Nilai 14 kita dapatkan dari perhitungan pitagoras dimana 14,1421 = sqrt(sqr(10)+sqr(10)). Hasil data nilai G ini selanjutnya kita gambarkan sbb : Selain dari perhitungan tersebut, kita dapat mengalikan dengan konstanta tertentu untuk memanipulasi biaya, misal : ketika melewati sungai maka G = G * 2. o Langkah 3: Estimated Movement / Estimasi gerakan Langkah selanjutnya kita hitung biaya estimasi pergerakan dan kita simbolkan dengan H. Nilai H ini secara singkat adalah nilai jarak / estimasi biaya dari pergerakan dari suatu titik terhadap titik finish dengan mengabaikan penghalang yang ada. Untuk lebih jelasnya silahkan lihat gambar di bawah : o Langkah 4 : Scoring / Penilaian Setelah nilai G dan H kita dapatkan, maka kita berikan skor dari masing-masing titik yang akan dilalui. Skor kita lambangkan misalnya dengan F dimana nilai F = G + H. Nilai F selanjutnya kita masukkan dalam setiap titik dari setiap langkah yang akan dilalui. Untuk lebih jelasnya lihat gambar di bawah : Dari setiap nilai tersebut kita ambil keputusan dengan mengambil langkah dengan nilai F terkecil. o Langkah 5 : Looping / Perulangan Setelah pergerakan pertama selesai selanjutnya lakukan perulangan dari dari langkah 1 sampai 4. Untuk lebih jelasnya setiap pergerakan akan digambarkan di bawah : b. Greedy Best-First Greedy Best-First adalah algoritma best-first yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni f(n) = h(n). Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak optimal. 2.1.4 SIMULATED ANNEALING Ide dasar simulated annealing terbentuk dari pemrosesan logam. Annealing (memanaskan kemudian mendinginkan) dalam pemrosesan logam ini adalah suatu proses bagaimana membuat bentuk cair berangsur-angsur menjadi bentuk yang lebih padat seiring dengan penurunan temperatur. Simulated annealing biasanya digunakan untuk penyelesaian masalah yang mana perubahan keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat luas, misalkan perubahan gerakan dengan menggunakan permutasi pada masalah Travelling Salesman Problem. Pada simulated annealing, ada 3 parameter yang sangat menentukan, yaitu: tetangga, gain, temperatur, pembangkitan bilangan random. Tetangga akan sangat berperan dalam membentuk perubahan pada solusi sekarang. Pembangkitan bilangan random akan berimplikasi adanya probabilitas. Algoritma Simulated Annealing: · Evaluasi keadaan awal. Jika keadaan awal merupakan tujuan, maka pencarian berhasil dan KELUAR. Jika tidak demikian, lanjutkan dengan menetapkan keadaan awal sebagai kondisi sekarang. · Inisialisasi BEST_SO_FAR untuk keadaan sekarang. · Inisialisasi T sesuai dengan annealing schedule. · Kerjakan hingga solusi ditemukan atau sudah tidak ada operator baru lagi akan diaplikasikan ke kondisi sekarang. o Gunakan operator yang belum pernah digunakan tersebut untuk menghasilkan kondisi baru. o Evaluasi kondisi yang baru dengan menghitung: E = nilai sekarang – nilai keadaan baru. § Jika kondisi baru merupakan tujuan, maka pencarian berhasil dan KELUAR. § Jika bukan tujuan, namun memiliki nilai yang lebih baik daripada kondisi sekarang, maka tetapkan kondisi baru sebagai kondisi sekarang. Demikian pula tetapkan BEST_SO_FAR untuk kondisi yang baru tadi. § Jika nilai kondisi baru tidak lebih baik dari kondisi sekarang, maka tetapkan kondisi baru sebagai kondisi sekarang dengan probabilitas: E / T-p’ e Langkah ini biasanya dikerjakan dengan membangkitkan suatu bilangan random r pada range [0 1]. Jika r < p’, maka perubahan kondisi baru menjadi kondisi sekarang diperbolehkan. Namun jika tidak demikian, maka tidak akan dikerjakan apapun. o Perbaiki T sesuai dengan annealing scheduling. · BEST_SO_FAR adalah jawaban yang dimaksudkan. Operator untuk Penyelesaian TSP dengan Simulated Annealing Ada beberapa operator yang bisa digunakan untuk penyelesaian TSP dengan Simulated Annealing. Berikut adalah salah satu contoh operator untuk menentukan jalur. Misalkan jumlah kota yang akan dikunjungi adalah NC. a. Kota-kota disimpan pada larik L. b. Kita bangkitkan 2 bilangan random antara 1 sampai NC, misalkan kedua bilangan itu adalah N1 dan N2 dengan N1 < N2. c. Depan = L(1) sampai L(N1-1). d. Tengah = L(N1) sampai L(N2). e. Belakang = L(N2+1) sampai L(NC). f. Bangkitkan bilangan random r, apabila r < 0,5; maka: § DepanBaru = Depan. § TengahBaru = Tengah dengan urutan dibalik. § BelakangBaru = Belakang. § Lbaru = [DepanBaru TengahBaru BelakangBaru] g. Jika r = 0,5; maka kerjakan: § Sementara = [Depan Belakang], misalkan memiliki M elemen. § Bangkitkan bilangan random r dengan nilai antara 1 sampai M. § DepanBaru = Sementara(1:r). § TengahBaru = Tengah. § BelakangBaru = Sementara(r+1:M). § Lbaru = [DepanBaru TengahBaru BelakangBaru] BAB 3 PENUTUP 3.1. Kesimpulan Heuristic search adalah suatu istilah yang berasal dari bahasa Yunani yang berarti menemukan/menyingkap. Heuristik adalah suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga sebagai suatu kaidah yang merupakan metoda/prosedur yang didasarkan kepada pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu. Metode Heuristic Searching: 1. Generate and Test 2. Hill Climbing a. Simple Hill Climbing b. Steepest-Ascent Hill Climbing 3. Best-First Seacrh a. Algoritma A* 4. Simulated Annealing. DAFTAR PUSTAKA http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html http://andreas-yoga.blogspot.co.id/2010/04/metode-pencarian.html https://solikhaton.blogspot.co.id/2014/08/makalah-membahas-tentang-algoritma.html http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html http://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html http://agusodow.blogspot.co.id/2012/05/metode-pencarian-hchill-climbing.html http://davinzhu87.blogspot.co.id/2011/09/steepest-ascent-hill-climbing.html http://deisyamalia.blogspot.co.id/2012/03/best-first-search.html http://duniadigit.blogspot.co.id/2013/08/belajar-algoritma-untuk-pencarian-jalur.html https://wahyudisetiawan.wordpress.com/2009/12/22/simulated-annealing/

Judul: Tugas Algoritma

Oleh: Muldiana Muldiana


Ikuti kami