METODE PENCARIAN HEURISTIC (HILL CLIMBING)

LATAR BELAKANG

Heuristic seringkali disebut sebagai lawan dari kata algoritmik dalam dunia pemrograman. Heuristic adalah suatu proses yang mungkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat ditemukan. Dengan kata lain, heuristic adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness). Sedangkan fungsi heuristik adalah fungsi yang melakukan pemetaan (mapping) dari diskripsi keadaan masalah (problema) ke pengukur kebutuhan, umumnya dipresentasikan berupa angka. Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Dalam mempelajari metode-metode pencarian heuristik, kata heuristik diartikan sebagai suatu fungsi yang memberikan suatu nilai berupa biaya perkiraan (estimasi) dari suatu solusi. Ada beberapa macam metode pencarian heuristik, yaitu pembangkitan dan pengujian (Generate and Test), Hill Climbing, Best First Search, Alpha Beta Prunning, Means-End-Anlysis, Constraint Satisfaction, dan Simulated Annealing. Dalam metode pencarian heuristik Hill Climbing, ada dua macam metode heuristik yakni Simple Hill Climbing dan Steepest (Ascent Hill Climbing). Dalam makalah ini, penulis akan membahas mengenai metode heuristik Simple Hill Climbing yang disertai dengan contoh algoritma pada metode tersebut pada saat diterapkan pada suatu permasalahan. 

PENGERTIAN

Metode Hill Climbing hampir sama dengan metode pembangkitan & pengujian (Generate and Test), hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. Hill Climbing adalah proses pengujian yang dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. Metode Hill climbing merupakan variasi dari depth-first search. Dengan metode ini, eksplorasi terhadap keputusan dilakukan dengan cara depth-first search dengan mencari path yang bertujuan menurunkan cost untuk menuju kepada goal/keputusan. Yaitu dengan selalu memilih nilai heuristik terkecil. Dalam metode heuristik Hill Climbing, terdapat dua jenis Hill Climbing yang sedikit berbeda, yakni Simple Hill Climbing (Hill Climbing sederhana) dan Steepest-Ascent Hill Climbing (Hill Climbing dengan memilih kemiringan yang paling tajam / curam).

• Dua teknik pencarian dan pelacakan

– Pencarian buta (blind search)

        • Pencarian melebar pertama (Breadth – First Search)

        • Pencarian mendalam pertama (Depth – First Search)

– Pencarian terbimbing (heuristic search)

       • Pendakian Bukit (Hill Climbing)

       • Pencarian Terbaik Pertama (Best First Search)

Pencarian Melebar Pertama (Breadth-First Search)

         • Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1

         • Mulai dari akar terus ke level 1 dari kiri ke kanan

         • Kemudian ke level selanjutnya hingga solusi ditemukan

         • Keuntungan

– Tidak akan menemui jalan buntu

– Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti

yang paling baik

– Jika ada satu solusi maka bread-first search akan menemukannya

         • Kelemahannya

– Membutuhkan memori yang cukup banyak

– Membutuhkan waktu yang cukup lama

Pencarian mendalam pertama (Depth-First Search)

• Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel

• Keuntungan

– Memori yang relatif kecil

– Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi

Pencarian Heuristik

• Pencarian buta tidak selalu dapat diterapkan dengan baik

– Waktu aksesnya yang cukup lama

– Besarnya memori yang diperlukan

• Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar.

• Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan disebut fungsi heuristic

• Aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine

• Contoh pada masalah 8 puzzle

Keadaan Awal Tujuan Pencarian Heuristik

• Operator

– Ubin kosong geser ke kanan

– Ubin kosong geser ke kiri

– Ubin kosong geser ke atas

– Ubin kosong geser ke bawah

• Langkah Awal

Gambar

• Langkah Awal hanya 3 operator yang bisa digunakan

– Ubin kosong digeser ke kiri, ke kanan dan ke atas.

• Jika menggunakan pencarian buta, tidak perlu mengetahui operasi apa yang akan dikerjakan (sembarang)

• Pada pencarian heuristik perlu diberikan informasi khusus dalam domain tersebut

• Untuk jumlah ubin yang menempati posisi yang benar jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih baik)

• Untuk jumlah ubin yang menempati posisi yang salah jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

• Menghitung total gerakan yang diperlukan untuk mencapai tujuan jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

Pencarian Heuristik

• Ada 4 metode pencarian heuristik

– Pembangkit & Pengujian (Generate and Test)

– Pendakian Bukit (Hill Climbing)

– Pencarian Terbaik Pertama (Best First Search)

– Simulated Annealing

Pembangkit & Pengujian (Generate and Test)

• Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

Algoritma:

– Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).

– Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.

– Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.

Contoh : Traveling Salesman Problem (TSP)

Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali.

Contoh : Traveling Salesman Problem (TSP)

• Generate & test akan membangkitkan semua solusi yang mungkin:

– A – B – C – D

– A – B – D – C

– A – C – B – D

– A – C – D – B, dll

Kelemahan dari Pembangkit & Pengujian (Generate and Test) yaitu ;

– Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian

– Membutuhkan waktu yang cukup lama dalam pencariannya

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.

• Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

Simple Hill Climbing

Algoritma

– Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

– Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:

• Cari operator yang belum pernah 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.

Contoh TSP

• Operator : Tukar kota ke-i dengan kota ke-j (Tk i,j)

• Untuk 4 kota:

– Tk 1,2 : tukar kota ke-1 dengan kota ke-2.

– Tk 1,3 : tukar kota ke-1 dengan kota ke-3.

– Tk 1,4 : tukar kota ke-1 dengan kota ke-4.

– Tk 2,3 : tukar kota ke-2 dengan kota ke-3.

– Tk 2,4 : tukar kota ke-2 dengan kota ke-4.

– Tk 3,4 : tukar kota ke-3 dengan kota ke-4.

• Untuk N kota, akan ada operator sebanyak:

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.

• Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.

• Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.

• Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri.

• Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.

• Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.

Algoritma

• Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

• Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang.

• Tentukan SUCC sebagai nilai heuristic terbaik dari successorsuccessor.

• Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:

• Gunakan operator tersebut dan bentuk keadaan baru.

• Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah.

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

Sumber : https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/

                http://web.unair.ac.id/admin/file/f_22572_2_Simple_Hill_Climbing.pdf

TUGAS SISTEM BERBASIS PENGETAHUAN

ARTIFICIAL INTELLIGENCE

→ Apa yang di maksut dengan AI?

 

Kecerdasan Buatan atau kecerdasan yang ditambahkan kepada suatu sistem yang bisa diatur dalam konteks ilmiah atau Intelegensi Artifisial (bahasa inggris: Artificial Intelligence atau hanya disingkat AI) didefinisikan sebagai kecerdasan entitas ilmiah. Sistem seperti ini umumnya dianggap komputer. Kecerdasan diciptakan dan dimasukkan ke dalam suatu mesin (komputer) agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia. Beberapa macam bidang yang menggunakan kecerdasan buatan antara lain sistem pakar, permainankomputer (games), logika fuzzy, jaringan syaraf tiruan dan robotika.
Banyak hal yang kelihatannya sulit untuk kecerdasan manusia, tetapi untuk Informatika relatif tidak bermasalah. Seperti contoh: mentransformasikan persamaan, menyelesaikan persamaan integral, membuat permainan catur atau Backgammon. Di sisi lain, hal yang bagi manusia kelihatannya menuntut sedikit kecerdasan, sampai sekarang masih sulit untuk direalisasikan dalam Informatika. Seperti contoh: Pengenalan Obyek/Muka, bermain sepak bola.
Walaupun AI memiliki konotasi fiksi ilmiah yang kuat, AI membentuk cabang yang sangat penting pada ilmu komputer, berhubungan dengan perilaku, pembelajaran dan adaptasi yang cerdas dalam sebuah mesin. Penelitian dalam AI menyangkut pembuatan mesin untuk mengotomatisasikan tugas-tugas yang membutuhkan perilaku cerdas. Termasuk contohnya adalah pengendalian, perencanaan dan penjadwalan, kemampuan untuk menjawab diagnosa dan pertanyaan pelanggan, serta pengenalan tulisan tangan, suara dan wajah. Hal-hal seperti itu telah menjadi disiplin ilmu tersendiri, yang memusatkan perhatian pada penyediaan solusi masalah kehidupan yang nyata. Sistem AI sekarang ini sering digunakan dalam bidang ekonomi, obat-obatan, teknik dan militer, seperti yang telah dibangun dalam beberapa aplikasi perangkat lunak komputer rumah dan video game.


 → Contoh AI

 Contohnya dalam film Iron Man yaitu J.A.R.V.I.S

Jarvis adalah singkatan dari Just A Rather Very Intelegent System .Jarvis inimerupakan komputer hologram yang dibuat oleh Tony Stark dalam film Ironman.Dalam film iron man Jarvis adalah komputer super pintar yang mampu berkomunikasi dengan Tony Stark sang tuannya ( pencipta ). Tugasnya mengelola segala sesuatu yang berhubungan dengan baju jirah Iron Man, data - data dan mengerjakan apa yang diperintahkan tuannya. Jarvis cukup AI canggih, mampu berinteraksi dengan manusia seperti orang hidup. Ia memiliki pengetahuan ilmiah yang sangat mendalam dan mampu membantu Tony Stark dalam penelitiannya. Tanpa Jarvis maka Tony Stark kesulitan dalam mengoperasikan Iron Man dan pekerjaannya. Jarvis merupakan gabungan antara data dan kecerdasan buatan, sehingga semua perintah ( data processing, robot functioning, mechanical controlling, hacking, dan lain – lain ) dengan input berupa suara dan display hologram apa pun bisa direspon dengan cepat.

Jarvis adalah sebuah program software multi fungsi mampu mengelola lingkungan lokal interior rumah Tony Stark. Ini menggunakan antar muka pengguna yang sangat maju dengan periferal holografik dan input suara, dan mengkomunikasikan data kembali ke user melalui pidato audio, menampilkan holografik dan monitor LCD konvensional. Ini juga mengontrol sejumlah peralatan robot, terutama unit gudang senjata tersembunyi di lantai rumah Stark yang memfasilitasi masuk dan jalan keluar dari sebagian besar Iron Man armor. Jarvis juga telah di adaptasi untuk dimuat ke dalam baju besi Iron Man untuk digunakan sebagai program sistem kontrol. Dalam kapasitas ini mengatur persyaratan komputasi yang kompleks yang diperlukan untuk antar muka pemakai baju besi dengan berbagai sub sistem, serta memberikan kontrol pendukung sistem tersebut dapat berjalan pada baju besi Iron Man. Namun sayang Jarvis saat ini hanya sebatas “rekaan” dari pembuat film Iron Man. Tidak menutup kemungkinan teknologi Jarvis ini ada pada masa depan.

Kita sudah menapaki langkah menuju Jarvis sebenarnya, dengan fungsionalitas dan kecanggihan yang meski pun belum mirip, tapi sudah mendekati. Sebagian dari teknologi Jarvis akan kami jabarkan sebagai berikut :

1. Voice Command

Voice Command ini sudah sangat marak digunakan pada smartphone. Ini adalah fitur di mana kita bisa memerintahkan sebuah ponsel untuk 'mengerjakan' sesuatu melalui perintah suara. Tidak perlu mengoperasikan tombol navigasi, atau pun menyentuh layar touchscreen dengan stylus. Hanya butuh suara Anda, Voice command juga dapat digunakan untuk menjawab atau menolak panggilan, mengubah profil, atau menjalankan aplikasi. Misalkan kita mau pakai aplikasi voice command untuk mengaktifkan Bluetooth. Tinggal edit saja voice command –nya dengan lafal yang mudah kita ucapkan. Misalnya kita ganti dengan kata 'aktifkan' untuk Bluetooth.

2. Komputer Hologram

Pada awal tahun 2011, beredar kabar munculnya teknologi tv hologram. Tapi baru-baru ini, dipenghujung tahun 2011, Microsoft membuat sebuah terobosan dengan teknologi yang di beri nama Microsoft Surface, dimana sebuah kombinasi antara meja, komputer, kamera, serta touch sensivity berukuran sebesar yang memungkinkan pengguna untuk berinteraksi untuk berbagai aktivitas. Pada meja besar yang menggunakan LCD touch screen 40 inci, Microsoft menempatkan sebuah smartphone pada layar, seketika Microsoft Surface akan mengenali perangkat tersebut dan menampilkan informasi mengenai perangkat serta memungkinkan untuk memilih model yang berbeda.

Khayalan tersebut kemungkinan akan terwujud karena kemajuan teknologi di jaman sekarang. Jaman sekarang saja laptop sudah berbentuk minimalis dan di buat sangat sederhana,  namun dengan kemampuan yang sangat canggih. Perkembangan dunia teknologi beberapa tahun terakhir semakin menggeliat, begitu juga dengan konsumsi akan teknologi juga sangat tinggi.  Para produsen dunia teknologi sekarang sudah membuat berbagai proyek di masa depan, merekan menciptakan sebuah produk meskipun masih khayalan. Teknologi laptop yang sekecil handphone mungkinakan tercipta pada beberapa tahun kedepan dengan begitu pesatnya dunia teknologi dunia.

Bila ingin menggunakannya sebagai laptop sebagai layarnya menggunakan kameranya sebagai proyektor yang dapat memunculkan hologram dari dalamnya sehingga dalam menggunakannya kita hanya tinggal menyentuh hologram tersebut. Komputer tersebut dilengkapi dengan kecepatan akses yang tinggi, aksesnya berkecepatan tinggi. Dapat dibawa kemanasaja, karena  yang hanya sebesar handphone. Keyboardnya berada pada hologram ketika kita menghidupkanya. Tombol powernya sekali sentuh langsung menyala. Dunia yang akan dating manusia akan menggunakan tenaga robot dalam membantu kegiatan sehari - harinya. Dunia yang akan dating dunia serba hologram.

3. Cloud Computing

Cloud computing secara kata bila diterjemahkan ke dalam Bahasa Indonesia dapat berbunyi "Komputasi Awan", namun sampai saat sekarang ini "mungkin" belum memiliki definisi ilmiah atau pun pengartian pokok yang jelas kecuali sebuah konsep pemahaman dalam rangka pembuatan kerangka kerja komputasi secara online lokal maupun global dimana terdapat beragam aplikasi maupun data dan media penyimpanan yang dapat diakses dan digunakan secara berbagi dan bersamaan oleh para pengguna yang beragam – mulai dari perseorangan sampai kepada kelas pengguna korporasi ( atau perusahaan ).

Cloud Computing adalah suatu istilah yang banyak digunakan oleh Industi IT yang memiliki arti yang berbeda bagi setiap orang. Namun pada intinya Cloud Computing adalah suatu pergeseran dari perusahaan dalam membeli dan memelihara server dan aplikasi on - premise yang mahal, dan bergerak menuju metode penyewaan IT, sesuai dengan kebutuhan, dari satu penyedia layanan publik.

Cloud Computing adalah suatu istilah yang banyak digunakan oleh Industi IT yang memiliki arti yang berbeda bagi setiap orang. Namun pada intinya cloud computing adalah suatu pergeseran dari perusahaan dalam membeli dan memelihara server dan aplikasi on - premise yang mahal, dan bergerak menuju metode penyewaan IT, sesuai dengan kebutuhan, dari penyedia layanan public cloud.

Hanya dalam beberapa tahun terakhir hal ini telah menjadi layak dan masuk akal bagi perusahaan untuk memindahkan teknologi mereka kesebuah pusat data yang dikelola secara professional oleh pihak luar. Perubahan ini telah didorong oleh mulai tersedianya Internet berkecepatan tinggi yang tidak hanya tersedia di kantor Anda, tetapi juga di rumah, di warung kopi dan di mana saja anda dapat melakukan penerimaan sinyal telepon seluler. Kenyataan ini telah memungkinkan terjadinya konsolidasi yang revolusioner.

4. Kecerdasan Buatan ( Artificial Intelligence )

Kecerdasan Buatan ( bahasa Inggris : Artificial Intelligence atau AI ) di definisikan sebagai kecerdasan entitas ilmiah. Sistem seperti ini umumnya dianggap komputer. Kecerdasan diciptakan dan dimasukkan ke dalam suatu mesin ( komputer ) agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia.

Walaupun AI memiliki konotasi fiksi ilmiah yang kuat, AI membentuk cabang yang sangat penting pada ilmu komputer, berhubungan dengan perilaku, pembelajaran dan adaptasi yang cerdas dalam sebuah mesin. Penelitian dalam AI menyangkut pembuatan mesin untuk mengotomatisasikan tugas - tugas yang membutuhkan perilaku cerdas. Termasuk contohnya adalah pengendalian, perencanaan dan penjadwalan, kemampuan untuk menjawab diagnosa dan pertanyaan pelanggan, serta pengenalan tulisan tangan, suara dan wajah. Hal - hal seperti itu telah menjadi disiplin ilmu tersendiri, yang memusatkan perhatian pada penyediaan solusi masalah kehidupan yang nyata. Sistem AI sekarang ini sering digunakan dalam bidang ekonomi, obat - obatan, teknik dan militer, seperti yang telah dibangun dalam beberapa aplikasi perangkat lunak komputer rumah dan video game.

'Kecerdasan buatan' ini bukan hanya ingin mengerti apa itu sistem kecerdasan, tapi juga mengkonstruksinya.

Kesimpulan :

Jarvis merupakan sebuah sistem komputer yang kompleks dan dilengkapi dengan Voice Command, Komputer Hologram, Cloud Computing, Artificial Intelligence, dan lain – lain. Jarvis merupakan gabungan antara data dan kecerdasan buatan, sehingga semua perintah ( data processing, robot functioning, mechanical controlling, hacking, dan lain – lain ) dengan input berupa suara dan display hologram apa pun bisa direspon dengan cepat. Namun sayang Jarvis saat ini hanya sebatas “rekaan” dari pembuat film Iron Man. Tidak menutup kemungkinan teknologi Jarvis ini ada pada masa depan.

Sumber : 

https://id.wikipedia.org/wiki/Kecerdasan_buatan

 http://tugas-besar-komas-2013.blogspot.co.id/2013/05/teknologi-jarvis.html