ALGORITMA HEURISTIK

A.      Pengertian algoritma

Dalam matematika dan komputasi, algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.

Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.

Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.

B.      Jenis jenis algoritma

Terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan dalam banyak algoritma yang berbeda.

§  Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.

§  Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal (, dan mengandung beberapa bagian permasalahan yang tumpang tindih . Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.

§  Metode serakah. Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.

C.      Algoritma heuristik

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).

Untuk dapat menerapkan heuristik tersebut dengan baik dalam suatu domain tertentu, diperlukan suatu 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.

Jenis-jenis Heuristic Searching:

-          Generate and Test.

-          Hill Climbing.

-          Best First Search.

-          Alpha Beta Prunning.

-          Means-End-Anlysis.

-          Constraint Satisfaction

                                I.            GENERATE AND TEST

                Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang akan dibicarakan. Pendekatan ini meliputi langkah–langkah

sebagai berikut :

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

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

c.       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 kurang efisien untuk masalah yang besar atau kompleks

                              II.            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). 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 :

a.       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.

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

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

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

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

3.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.

4.Kembalilah ke langkah 2.

                            III.            BEST FIRST SEARCH

Pencarian terbaik pertama (Best First Search) merupakan suatu cara yang menggabungkan keuntungan atau kelebihan dari pencarian Breadth-First Search dan Depth-First Search. Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya. Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal

state, yang dinyatakan dengan :

f’ = g + h’ dimana f’ = prakiraan cost dari initial ke goal g = cost dari initial state ke current state

h’ = prakiraan cost dari current state ke goal state