PENGENALAN INTELEGENSI BUATAN

PENGENALAN INTELEGENSI BUATAN

Kecerdasan Buatan adalah salah satu cabang Ilmu pengetahuan berhubungan dengan pemanfaatan mesin untuk memecahkan persoalan yang rumit dengan cara yang lebih manusiawi. Hal Ini biasanya dilakukan dengan mengikuti/mencontoh karakteristik dan analogi berpikir dari kecerdasan/Inteligensia manusia, dan menerapkannya sebagai algoritma yang dikenal oleh komputer. Dengan suatu pendekatan yang kurang lebih fleksibel dan efisien dapat diambil tergantung dari keperluan, yang mempengaruhi bagaimana wujud dari perilaku kecerdasan buatan.

INTELEGENSI BUATAN DAN INTELEGENSI ALAMI

Intelegensi buatan lebih bersifat permanen. Intelegensi alami akan cepat mengalami perubahan. Hal ini dimungkinkan karena sifat manusia yang pelupa. Intelegensi buatan tidak akan berubah sepanjang sistem komputer dan program tidak mengubahnya.

Intelegensi buatan lebih mudah diduplikasi dan disebarkan. Mentransfer pengetahuan manusia dari satu orang ke orang lain butuh proses dan waktu lama. Disamping itu suatu keahlian tidak akan pernah bisa diduplikasi secara lengkap. Sedangkan jika pengetahuan terletak pada suatu sistem komputer, pengetahuan tersebuat dapat ditransfer atau disalin dengan mudah dan cepat dari satu komputer ke komputer lain

Intelegensi buatan lebih murah dibanding dengan kecerdasan alami. Menyediakan layanan komputer akan lebih mudah dan lebih murah dibanding dengan harus mendatangkan seseorang untuk mengerjakan sejumlah pekerjaan dalam jangka waktu yang sangat lama.

Intelegensi buatan bersifat konsisten. Hal ini disebabkan karena intelegensi buatan adalah bagian dari teknologi komputer. Sedangkan intelegensi alami senantiasa berubah-ubah.

Intelegensi buatan dapat didokumentasikan. Keputusan yang dibuat komputer dapat didokumentasikan dengan mudah dengan melacak setiap aktivitas dari sistem tersebut. Intelegensi alami sangat sulit untuk direproduksi.

Intelegensi buatan dapat mengerjakan pekerjaan lebih cepat dibanding dengan intelegensi alami

Intelegensi buatan dapat mengerjakan pekerjaan lebih baik dibanding dengan intelegensi alami.

Keuntungan intelegensi alami:

Kreatif. Kemampuan untuk menambah ataupun memenuhi pengetahuan itu sangat melekat pada jiwa manusia. Pada intelegensi buatan, untuk menambah pengetahuan harus dilakukan melalui sistem yang dibangun

Intelegensi alami memungkinkan orang untuk menggunakan pengalaman secara langsung. Sedangkan pada intelegensi buatan harus bekerja dengan input-input simbolik

Pemikiran manusia dapat digunakan secara luas, sedangkan intelegensi buatan sangat terbatas.

 KOMPUTASI INTELEGENSI BUATAN DAN KOMPUTASI KONVENSIONAL
KOMPUTASI KONVENSIONAL

     Teknik pembuatan Program AI sangat berbeda dengan teknik pemrograman menggunakan bahasa konvensional. Dalam software konvensional,kita memerintah komputer bagaimana menyelesaikan suatu masalah.  Dalam komputasi konvensional, kita memberikan data kepada komputer dan program yang telah kita susun terlebih dahulu dengan langkah demi langkah memspesifikasikan cara data digunakan sampai komputer bisa memberikan solusi. Program komputer konvensional didasarkan pada suatu algoritma yang disusun dengan jelas, rinci, serta langkah sampai pada hasil yang sudah ditentukan sebelumnya. program bisa berupa rumus matematika atau prosedur berurutan yang tersusun dengan jelas yang mengarah ke suatu solusi. Algoritma tersebut kemudian dipindahkan ke dalam program komputer. Daftar instruksi disusun berurutan untuk mengarahkan komputer agar bisa sampai pada hasil yang didinginkan. Selanjutnya, algoritma bisa digunakan untuk mengolah data bilangan, huruf, atau kata lainnya.

KOMPUTASI AI

Sebaliknya, software AI tidak didasarkan pada algoritma, tetapi didadasarkan pada representasi dan manipulasi simbol. Didalam AI, sebuah simbol bisa merupakan huruf, kata, atau bilangan yang digunakan untuk menggambarkan objek, proses, dan huungannya. sumber bisa merupakan cetakan atau elektronik. objek bisa berupa orang, benda, ide, pikiran, peristiwa, atau pernyataan suatu fakta. Dengan menggunakan simbol, komputer bisa menciptakan suatu basis pengetahuan yang menyatakan fakta, pikiran, dan hubungannya satu sama lain. berbagai proses digunakan unutk memanipulasi simbol agar mampu memecahkan masalah. Pengolahannya bersifat kuantitatif, bukan kulaitatif seperti halnya komputasi yang didasarkan pada algoritma.

SEJARAH INTELEGENSI BUATAN

A. Era Komputer Elektronik (1941)

Ditemukannya pertama kali alat penyim-panan dan pemprosesan informasi yang disebut komputer elektronik. Penemuan ini menjadi dasar pengembangan program yang mengarah ke KB.

B. Masa Persiapan KB (1943 – 1956)

Tahun 1943, Warren McCulloch dan Walter Pitts

mengemukakan tiga hal, yaitu :

a. pengetahuan fisiologi dasar dan fungsi sel syaraf

dalam otak

b. analisis formal tentang logika proposisi (propositional logic)

c.teori komputasi Turing

Tahun 1950, Norbert Wiener membuat penelitian mengenai prinsip-prinsip teori feedback. Contoh yang terkenal adalah thermostat. Penemuan ini juga merupakan awal dari perkembangan KB.

Tahun 1956, John McCarthy meyakinkan Minsky, Claude Shannon dan Nathaniel Rochester untuk membantunya melakukan penelitian dalam bidang Automata, Jaringan Syaraf dan pembelajaran intelijensia.

Mereka kerjakan projek ini selama dua tahun di Dartmouth. Hasilnya adalah program yang mampu berpikir non-numerik dan menyelesaikan masalah pemikiran yang dinamakan Principia Mathematica. Hal ini menjadikan McCarthy disebut sebagai ”Bapak Kecerdasan Buatan”.

C. Awal Perkembangan Kecerdasan Buatan (1956 – 1969)

Diawali dengan kesuksesan Newell dan Simon dengan sebuah program yang disebut ”General Prbolem Solver”. Program ini dirancang untuk memulai penyelesaian masalah secara manusiawi.

tahun 1958, McCarthy mendefenisikan bahasa pemrograman tingkat tinggi, yaitu LISP, yang sekarang mendominasi pembuatan program-program kecerdasan buatan.

McCarthy membuat program yang dinamakan programs with Common Sense. Di dalam program tersebut, dibuat rancangan untuk menggunakan pengetahu-an dalam mencari solusi.

Tahun 1959, Nathaniel Rochester dari IBM dan mahasiswa-mahasiswanya mengeluarkan program, kecerdasan buatan, yaitu geometry Theorm Prover. Program ini dapat membuktikan suatu teorema menggunakan axioma-axioma yang ada.

Tahun 1963, program yang dibuat James Slagle mampu menyelesaikan masalah integral untuk mata kuliah kalkulus.

Tahun 1968, program analogi buatan Tom Evan menyelesaikan masalah analogi geometris yang ada pada tes IQ.

D. Sistem Berbasis Pengetahuan (1969 – 1979)

Pengetahuan adalah kekuatan pendukung KB. Hal ini dibuktikan dengan program yang dibuat oleh Ed Feigenbaum, Bruce Buchanan dan Joshua Lederberg yang membuat program untuk memecahkan masalah struktur molekul dari informasi yang didapatkan dari spectometer massa.

Program ini dinamakan Dendral Programs yang berfokus pada segi pengetahuan kimia. Dari segi diagnosa medis juga sudah ada yang menemukannya, yaitu Saul Amarel dalam proyek Computer in Biomedicine. Proyek ini diawali dengan keinginan untuk mendapatkan diagnosa penyakit berdasarkan pengetahuan yang ada pada mekanisme penyebab proses penyakit.

E. KB menjadi sebuah industri (1980 – 1988)

Industrialisasi KB diawali dengan ditemukannya ”sistem pakar” (expert system) yang dinamakan R1 yang mampu mengonfigurasi sistem-sistem komputer baru. Program tersebut mulai dioperasikan di Digital Equipment Corporation (DEC), McDermot tahun 1982.

Tahun 1986, program tersebut mampu menghemat biaya US$ 40 juta /tahun.

Tahun 1988, Kelompok KB di DEC menjalankan 40 sistem pakar.

Booming KB ini juga melibatkan perusahaan-perusahaan besar seperti Carnegie Group, Inference, Intellicorp dan Technoledge yang menawarkan software tools untuk membangun sistem pakar.

Perusahaan Hardware seperti LISP Machines Inc, Texas Instruments, Symbolics dan Xerox juga turut berperan dalam membangun workstation yang dioptimasi untuk pembangunan LISP.

F. Era Kembalinya Jaringan Syaraf Tiruan (1986 – Sekarang)

Para ahli fisika seperti Hopfield (1982) menggunakan teknik-teknik mekanika statistika untuk menganalisa sifat-sifat penyimpanan dan optimasi pada jaringan syaraf.

Para ahli psikologi, David Rumelhart dan Geoff Hinton, melanjutkan penelitian mengenai model jaringan syaraf pada memori.

Pada tahun 1985-an, sedikitnya empat kelompok riset menemukan kembali algoritma belajar propagasi balik (Back-Propagation learning). Algoritma ini berhasil diimplementasikan ke dalam ilmu komputer dan psikologi.

LINGKUP INTELEGENSI BUATAN

          Ruang Lingkup Kecerdasan Buatan Dalam kehidupan manusia sehari-hari, kecerdasan buatan dapat membantu dalam berbagai bidang sebagai berikut :

Bidang komunikasi : Komputer dapat menuliskan secara otomatis apa yang  diucapkan pengguna.

Bidang Kesehatan : USG untuk mengetahui kondisi janin yang ada di dalam kandungan ibu hamil,  Sistem pakar untuk mendiagnosa suatu penyakit, untuk melakukan stimulasi atau treatment pada pasien.

Bidang Lalu Lintas Udara : komputer digunakan untuk mengatur signal lalu l;intas penerbangan diudara, memantau radar.

Bidang Pertanian: komputer digunakan untuk mengontrol mesin panen secara otomatis, penyiraman tanaman otomatis dengan jangka waktu yg telah ditentukan oleh user, mesin pembasmi hama secara otomatis.

Pabrik : mengontrol robot yang harus melakukan pekerjaan yang berbahaya jika dilakukan oleh manusia, pekerjaan yang sangat membosankan, memerlukan ketelitian tinggi, pengawasan dan maintenance.

 SOFT COMPUTING

Soft Computing adalah kumpulan teknik – teknik perhitungan dalam ilmu komputer, inteligensia semu, machine learning dan beberapa disiplin ilmu teknik lainnya, yang berusaha untuk mempelajari, memodelkan, dan menganalisa fenomena yang sangat rumit : untuk metoda yang lebih konvensional yang tidak memberikan biaya rendah, analitis dan solusi lengkap. Soft computing berusaha untuk mengintegrasikan beberapa paradigma model perhitungan meliputi artificial neural network, fuzzy logic dan genetic algorithms.

Bagian-bagian dari Soft Computing sendiri adalah :

1. Fuzzy Logic

2. Neural Networks

3. Probabilistic Reasoning

Fuzzy Logic

Fuzzy Logic merupakan suatu representasi dari pengetahuan yang direkonstruksi dengan if-then rules. Sederhananya, Fuzzy Logic adalah suatu metode untuk mengontrol sesuatu. Misalnya rekonstruksi if-then, "Jika cuaca panas, Maka turunkan suhu AC". Disinilah Fuzzy Logic berperan dalam Teknologi Komputer nantinya.

Neural Networks

Kompleksnya pikiran manusia juga merupakan masa depan dari komputer yang menggunakan Soft Computing. Neural Networks adalah tiruan dari jaringan saraf-saraf manusia yang terhubung dan membentuk sistem. Jadi metode ini ditujukan untuk meniru saraf manusia yang kompleks dan dapat menyimpan memori.

Probabilistic Reasoning

Probabilistic Reasoning adalah metode Soft Computing juga untuk membuat komputer atau suatu device mengambil keputusan layaknya makhluk hidup. Jadi, dari semua data-data yang sudah dimiliki, metode ini memberikan pola-pola tertentu untuk mengambil keputusan.

     Banyak contoh-contoh riset yang sekarang mulai mengimplementasikan Soft Computing, seperti AC yang hanya hidup ketika AC tersebut merasakan adanya panas dari sensornya, dan TV yang menggunakan "Eye Recognition" dimana TV tersebut akan Shut Down otomatis ketika yang menonton TV sudah memejamkan mata dan tertangkap sensor TV.

DEFINISI MASALAH DAN RUANG MASALAH

Secara umum, untuk mendeskripsikan masalah dengan baik, hendaknya:

Mendefenisikan suatu ruang keadaan

Menetapkan satu atau lebih keadaan awal

Menetapkan satu atau lebih tujuan

Menetapkan kumpulan aturan

Cara Merepresentasikan Ruang Keadaan

Graph Keadaan : terdiri dari node-node yang menunjukkan keadaan yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator.

Graph Keadaan

[inspic=15,,fullscreen,0]

Pohon Pelacakan

Struktur Pohon digunakan untuk menggambarkan keadaan secara hirarkis. Terdiri atas beberapa node yang terbagi dalam beberapa level.

[inspic=13,,fullscreen,0]

Pohon AND/OR

Pohon AND/OR digunakan untuk memperpendek level pencapaian tujuan.

Contoh : Masalah Teko Air

Ada dua buah teko masing-masing berkapasitas 4 galon (Teko A) dan 3 galon (Teko B). Tidak ada tanda yang menunjukkan batas ukuran pada kedua teko tersebut. Ada sebuah pompa air yang akan digunakan untuk mengisikan air pada kedua teko tersebut. Permasalahan: Bagaimana kita dapat mengisikan tepat 2 galon air ke dalam teko yang berkapasitas 4 galon?

Solusi Teko Air

Isi Teko B sampai penuh

Tuang isi teko B ke dalam teko A

Isi teko B sampai penuh

Tuang isi teko B sampai teko A penuh

Tumpahkan semua isi teko A

Pindahkan isi teko B ke teko A

PENGENALAN INTELLIGENT AGENTS

AGEN DAN LINGKUNGANNYA

         

Agent adalah faktor yang menyebabkan penyakit. Diabetes mellitus bukan penyakit menular yang disebabkan oleh satu agent yang pasti. Kejadian diabetes mellitus lebih tinggi dialami oleh individu yang berasal dari kondisi sosial ekonomi yang baik. Hal ini kemungkinan dikaitkan juga dengan obesitas yang terjadi karena ketidakseimbangan gizi. Prevalensi yang tinggi juga ditunjukkan oleh penderita wanita dari pada pria, dan komplikasi lebih sering terjadi pada penderita usia dewasa dari pada anak – anak.

RASIONALITAS

    

Rasionalitas merupakan konsep normatif yang mengacu pada kesesuaian keyakinan seseorang dengan alasan seseorang untuk percaya, atau tindakan seseorang dengan alasan seseorang untuk bertindak. Namun, istilah "rasionalitas" cenderung digunakan secara berbeda dalam berbagai disiplin ilmu, termasuk diskusi khusus ekonomi, sosiologi, psikologi, biologi evolusioner dan ilmu politik.

      

PEAS (Performance measure, Environment, Actuators, Sensors)

    

PEAS adalah singkatan dari Performance Measure, Environment, Actuators, dan Sensor. Dimana harus dispesifikasikan terlebih dahulu mengenai rancangan intelligent agent.

Misalkan untuk task yang didesain untuk agent pengemudi taksi otomatis:

Performance Measure: Aman, Cepat, Legal, Perjalanan yang nyaman, Keuntungan Maksimal

Environment : Jalan, Lalu lintas kendaraan lain, Pejalan kaki, Pelanggan

Actuators: Setir, Akselerator, Rem, Lampu Sinyal, Klakson

Sensors: Kamera, Sonar, Spedometer, GPS, odometer, sensor mesin, keyboard

TIPE-TIPE LINGKUNGAN AGEN

Agen sosialisasi  berikutnya adalah pendidikan formal atau sekolah. Disini seseorang akan mempelajari hal baru yang tidak diajarkan di dalam keluarga, maupun kelompok sepermainannya. Sekolah memepersiapkannya untuk peran-peran baru dimasa mendatang, saat ia tidak tergantung lagi pada orang tua. Di lingkungan rumah seorang anak mengharapkan bantuan dari orang tuanya dalam melaksanakan berbagai pekerjaan, tetapi di sekolah sebagian besar tugas sekolah harus dilakukan sendiri dengan penuh rasa tanggung jawab.

TIPE-TIPE AGEN

Utility‐based agents

Learning‐based Agent

Simple reflex agents Berdasarkan pada percept terakhir saja

Model‐based agents Memiliki representasi internal mengenai keadaan lingkungan

Goal‐based agents Memiliki informasi mengenai tujuan, memilih tindakan yang mengarah ke tujuan

PENGENALAN LOGICAL AGENTS

Logic merupakan jantung dari program, para pemrogram mempunyai keyakinan bahwa sebuah komputer dapat dibuat mengerti logika, maka computer dapat dibuat untuk berfikir, karena logika kelihatannya menjadi inti dari kecerdasan.

1  Problem solving agent hanya bisa menyelesaikan masalah yang lingkungannya accessible.

2  Kita membutuhkan agen yang dapat menambah pengetahuan dan menyimpulkan keadaan.

3  Agent yang akan membantu seperti ini kita beri nama knowledge based agent.

3.1 Knowledge Based Agents

Komponen utama dari knowledge based agent adalah knowledge basenya. Knowledge base (KB) adalah kumpulan representasi fakta tentang lingkungan atau dunia yang berhubungan atau menjadi daerah bekerjanya agen. Setiap representasi dalam KB disebut sebagai sebuah kalimat yang diekspresikan dalam sebuah bahasa yakni knowledge representation language.

·         Representasi Pengetahuan yang bersifat general.

·         Kemampuan beradaptasi sesuai temuan fakta.

·         Kemampuan menyimpulkan sesuatu dari pengetahuan yang sudah ada.

Syarat Representasi KB:

1.       Representational Adequacy

Kemampuan merepresentasikan semua pengetahuan yang dibutuhkan dalam domainnya

2.       Inferential Adequacy

Kemampuan memanipulasi struktur pengetahuan untuk membentuk struktur baru dalam menampung pengetahuan baru hasil inferens.

3.        Inferential Efficiency

Kemampuan untuk manambahkan informasi untuk mempercepat pencarian dalam inferensi.

4.       Acquisitional Efficiency

Kemampuan untuk menambah informasi baru secara mudah.

Pengetahuan yang dimiliki agent tidak berguna jika ia tidak melakukan apapun karenanya kita perlu menambahkan aturan agar dia dapat bergerak (complete the knowledge base). Beberapa tahapan yang dilakukan dalam menyusun knowledge based agent:

·         Untuk dapat menyusun sebuah knowledge based agent maka kita harus terlebih dulu bisa menyusun knowledge basenya itu sendiri.

·         Untuk menyusun knowledge base kita perlu menentukan bagaimana cara kita merepresentasikan pengetahuan kita (knowledge representation).

·         Knowledge representation kita harus merupakan bentuk yang mudah disimpan dan digunakan pada komputer. Dalam perkuliahan ini kita menggunakan beberapa macam knowledge representation language.

 Wumpus World

·         Environment sederhana, berguna untuk menguji dan menjelaskan logical agent.

·         Gua gelap dengan banyak ruangan yang dihubungkan dengan lorong-lorong.

·         Agent masuk ke gua untuk mengambil emas yang ada di salah satu ruangan.

·         Wumpus (monster) bersembunyi di salah satu ruangan. Jika agent bertemu, ia akan menjadi santapannya.

  Terdapat ruang-ruang yang memiliki lubang jebakan yang dapat membunuh agent.

·         Agent hanya punya 1 panah yang bisa membunuh wumpus dari jarak jauh.

Sifat dari Wumpus World:

·         Fully observable? Tidak, hanya bisa berpresepsi lokal.

·         Deterministic? Ya, hasil tindakan jelas dan pasti.

·         Episodic? Tidak, tergantung action sequence.

·         Static? Ya, gold, wumpus, pit tidak bergerak.

·         Discrete? Ya.

·         Single agent? Ya.

Logic in general-Models and Entailment

Logics adalah bahasa formal untuk merepresentasikan fakta sedemikian shg kesimpulan (fakta baru, jawaban) dapat ditarik. Ada banyak metode inference yang diketahui. Kita bisa membangun agent Wumpus World dengan logika: memanfaatkan perkembangan logika oleh ahli matematika, filsafat selama ratusan tahun.

Entailment artinya bahwa sesuatu mengikuti dari yang lain.

KB ╞

·         Knowledge base KB entails kalimat α jika dan hanya jika α adalah true pada semua dunia dimana KB bernilai true.

·         Misal, KB “the Giants won” dan “the Reds won”  entails “Either the Giants won or the Reds won”

·         Misal, x+y = 4 entails 4 = x+y

Entailment adalah sebuah hubungan antar kalimat (syntax) yang didasarkan pada semantik.

Models à m adalah sebuah  model pada sebuah kalimat α jika α bernilai true pada m

·         M(α) adalah kumpulan semua model pada α.

·         KB ╞ α iff M(KB) Í M(α).

·         Misal: KB = Giants won and Reds won , α = Giants won

Referensi

Sumber: http://slidegur.com/doc/3649399/pertemuan-ix 

http://slideplayer.info/slide/3300290/

METODE PENCARIAN DAN PELACAKAN 1

Searching di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.

Teknik searching sendiri terbagi menjadi dua, yaitu:

1.     Blind searching

2.    Heuristic searching

Metode Pencarian Buta (Blind Search)

Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:

·         Membangkitkan simpul berdasarkan urutan.

·         Kalau ada solusi maka solusi akan ditemukan.

·         Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

Breadth First Search

BFS (Breadth First Search) yaitu model pencarian yang memakai metode melebar. Untuk mencari hasilnya, model BFS ini menggunakan teknik pencarian persoalannya dengan cara membuka node (titik) pada tiap levelnya. Dimulai pada node n, dan dilanjutkan n+1. Pencarian akan terus dilakukan dari akar kiri ke kanan hingga hasil ditemukan. Metode ini memiliki keuntungan dan kekurangan, yaitu:

·         Keuntungan:

·         Tidak akan menemui jalan buntu.

·         Jika ada satu solusi, maka breadth first akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

·         Kekurangan:

·         Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.

·         Membutuhkan waktu yang cukup lama karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1).

 Depth First Search

DFS (Depth-first Search) sering disebut juga pencarian mendalam. Sesuai dengan namanya “pencarian mendalam”, DFS tidak mencari solusi per level. Metode ini melakukan pencarian pada semua node "anaknya" sebelum dilakukan pencarian ke node-node lain yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi, dan proses terus diulang hingga solusi ditemukan. DFS memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node dan jika pencarian tepat, akan menemukan solusi tanpa harus menguji lebih banyak node. Namun, metode ini tetap memiliki kelemahan, yaitu memungkinkan hasil tidak ditemukan, dan setiap 1 kali pencarian hanya akan menghasilkan satu solusi.

 Metode Pencarian Heuristik

Heuristic Search merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan). Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu. Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).

Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).

Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

 Generate and Test

Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang akan dibicarakan. Ini adalah gabungan dari pencarian depth first dengan pelacakan mundur. Nilai dari pengujian ini berupa "ya" atau "tidak".

Pendekatan ini meliputi langkah–langkah sebagai berikut :

Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.

Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).

Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke 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.

 Hill Climbing

Hill Climbing (mendaki bukit) merupakan salah satu variasi metode buat dan uji (generate and test) dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search). Perbedaannya ada pada feedback dari prosedur test untuk pembangkitan keadaan berikutnya. Tes yang dilakukan berupa fungsi heuristik akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap keadaan lain yang memungkinkan.

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

Prosedur Hill Climbing :

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.

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

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.

Kelemahan pada sistem ini adalah algoritma akan berhenti ketika mencapai optimum local, urutan penggunaan operator akan sangat berpengaruh, dan tidak diijinkan untuk melihat langkah sebelumnya.

Referensi:

http://adamspahalerang.blogspot.co.id/2012/10/analisa-teknik-searching-dalam.html

http://buatugasai.blogspot.co.id/2013/04/metode-pencarian-dan-pelacakan_4.html

http://www.scribd.com/doc/52500558/Metode-Pencarian-Dan-Pelacakan-prolog

http://www.slideshare.net/ceezabramovic/metode-pencarian-heuristik