Senin, 02 Oktober 2017

Pencarian Berbentuk /heuristik search dan Eksplorasi

Strategi pencarian berbentuk/heuristic search stragegy
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.
Jenis-jenis Heuristic Searching :
1.     Greedy Best-First search
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.    A* search
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.
3.    SMA (Simplified Memory-Bounded A*)
SMA* adalah contoh dari sebuah mekanisme pencarian “lossy“. Dalam rangka untuk mengurangi konsumsi memori, hal ini membuang informasi, dengan asumsi bahwa informasi yang dibuang itu tidak penting. Bagaimanapun, tidak ada jaminan bahwa hal itu tidak penting. Dalam semua kasus dengan SMA*, jalur yang ditemukan tidak memiliki jaminan menjadi jalur yang optimal. Pada awal pencarian, node yang tidak menjanjikan bisa saja dibuang.
Menetapkan limit yang besar pada ukuran open list dapat membantu meringankan masalah ini, namun fungsi untuk mengurangi penggunaan memori menjadi terbuang. Pada kasus ekstrem yang lain, dengan memberi limit 1 simpul pada open list, ini bisa mempercepat sekaligus mengurangi penggunaan memori dalam pencarian, namun jalur yang ditemukan bisa tidak optimal .

Fungsi heuristic
Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Algoritma pencarian lokal dan masalah optimisasi
1.     Hill Climbing Search
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 lainnyayang mungkin.
2.    Simulated Annealing Search
Simulated annealing adalah salah satu algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas  dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu. Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, di mana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum.
3.    Local Beam Search
Local Beam Search adalah algoritma pencarian heuristik yang mengeksplorasi grafik dengan memperluas simpul yang paling menjanjikan dalam rangkaian terbatas. Penelusuran beam adalah optimalisasi pencarian terbaik pertama yang mengurangi kebutuhan memori. Pencarian terbaik pertama adalah penelusuran grafik yang memerintahkan semua solusi parsial (negara bagian) menurut beberapa heuristik yang mencoba memprediksi seberapa dekat solusi parsial dengan solusi lengkap (goal state). Tapi dalam pencarian balok, hanya sejumlah solusi parsial terbaik yang telah ditentukan dijaga sebagai kandidat.
4.    Genetic Algorithm
Genetic Algorithm (GA) adalah metaheuristik yang terinspirasi oleh proses seleksi alam yang termasuk dalam kelas yang lebih besar dari algoritma evolusioner (EA). Algoritma genetika biasanya digunakan untuk menghasilkan solusi berkualitas tinggi untuk optimasi dan masalah pencarian dengan mengandalkan operator terinspirasi bio seperti mutasi, crossover dan seleksi.
Agen pencarian online dan lingkungan yang tidak diketahui.
Agen cerdas adalah (intelligent agent) kian populer seiring dengan perkembangan internet. Berbagai nama lain yang juga menyatakan agen cerdas yaitu software agent, wizard, knowbot, dan softbot.
Russel dan norving (1995,  hal 31) mendefinisikan agent sebagai “segala sesuatu yang dapat dipandang menangkap lingkungan melalui efektor.” Sensor adalah bagian yang merangsang tindakan agen, sedangkan efektor adalah bagian yang di gunakan oleh agen untuk melakukan tindakan.
Agen yang berupa perangkat lunak, atau bisa disebut agen cerdas, adalah perangkat lunak yang dapat bertindak seperti orang yang mampu berinteraksi dengan lingkungan. Contoh:
·         Agen sistem operasi
·         Agen spreadsheet
·         Agen perdagangan elektronis
Agen sistem operasi digunakan untuk membantu penggunaan sistem operasi digunakan untuk membantu penggunaan sistem operasi. Contoh, microsoft memiliki sejumlah agen yang dinamakan wizard pada sistem operasi yang di buatnya; misalnya Windows NT. Agen ini digunakan antara lain untuk menambah nama pemakai, mengelola grup pemakai, dan manajemen berkas.
Agen spreadsheet digunakan untuk membuat program spreadsheet menjadi lebih mudah digunakan oleh pemakai. Contoh, Office  Assistant pada excel dapat “mengamati” pemakaidan jika terjadi sesuatu yang perlu untuk dibantu, agen cerdas akan memberikan saran. Agen untuk perdagangan elektronis digunakan untuk membantu pemakai yang akan melakukan belanja secara online.


Daftar Pustaka:



Tidak ada komentar:

Posting Komentar

About Me

Terimakasih telah datang ke blog saya dan selamat membaca.

Popular Posts

Designed ByBlogger Templates