Algoritma best first search ini merupakan kombinasi dari algoritma depth first search dengan algoritma breadth first search dengan mengambil kelebihan dari kedua algoritma tersebut. Apabila pada pencarian dengan algoritma hill climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node di level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya pada algoritma best first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node di level yang lebih tinggi memiliki nilai heuristik yang lebih buruk.
Algoritma best first search merupakan salah satu bagian dari tipe informed search. Algoritma ini menggunakan nilai-nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai heuristik terbaik akan dibuka lebih dahulu. Bila goal state belum ditemukan, akan dilakukan pemeriksaan pada simpul berikutnya dengan nilai heuristik terbaik pada kedalaman yang sama. Simpul tersebut kemudian dibuka dan diperiksa apakah terdapat goal state pada cabang-cabangnya. Bila goal state belum ditemukan, akan dilakukan proses yang sama pada simpul berikutnya.
Merupakan metode yang membangkitkan suksesor dengan mempertim- bangkan harga (didapat dari fungsi heuristik tertentu) dari setiap node, bukan dari aturan baku seperti DFS maupun BFS. Gambar 3.4 mengilustrasikan langkah-langkah yang dilakukan oleh 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.
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.
1. OPEN berisi initial state dan CLOSED masih kosong.
2. Ulangi sampai goal ditemukan atau sampai tidak ada di dalam OPEN.
- Ambil simpul terbaik yang ada di OPEN.
- Jika simpul tersebut sama dengan goal, maka sukses
- Jika tidak, masukkan simpul tersebut ke dalam CLOSED
- Bangkitkan semua aksesor dari simpul tersebut
- Untuk setiap suksesor kerjakan.
Algoritma yang menggunakan metode best-first search, yaitu:
- 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. - A*
Algoritma A* merupakan algoritma best first search dengan modifikasian fungsi heuristik, yang akan meminimumkan total biaya lintasan, dan pada kondisi yang tepat akan memberikan solusi yang terbaik dalam waktu yang optimal.
Algoritma A juga membutuhkan dua antrian, yaitu OPEN dan CLOSED. Selain itu, ada juga fungsi heuristik yang memprediksi keuntungan tiap node yang di buat. Yang akan memungkinkan algoritma untuk melakukan pencarian-pencarian lintasan yang lebih di harapkan. Fungsi ini di sebut f’(n) sebagai pendekatan dari fungsi f(n) yang merupakan fungsi evaluasi yang sebenarnya terhadap node n. dalam banyak penarapan, akan lebih baik jika fungsi di definisikan sebagai kombinasi atau jumlah dua komponen yaitu g(n) dan h(n). Fungsi g(n) merupakan ukuran biaya yang di keluarkan dari keadaan awal sampai ke node n. Nilai yang didapat g(n) merupakan jumlahan biaya penerapan setiap aturan yang dilakukan pada sepanjang lintasan trbaik menuju suatu simpul dan bukan merupakan hasil estimasi.
Fungsi h(n) merupakan pengukur biaya tambahan yang harus dikeluarkan dari node n sampai mendapatkan tujuan. Perlu diketahui bahwa g(n), tidak negatif karena bila negatif maka lintasan yang membalik siklus pada graf akan tampak lebih baik dengan semakin panjangnya lintasan.
Secara matematis,fungsi F sebagai estimasi fungsi evaluasi terhadap node ndapat di tuliskan :
f’(n) = g(n) + h’(n)
Dengan f’(n) = fungsi evaluasi
g(n) = biaya yang sudah di keluarkan dari keadaan awal sampai
keadaan n
h’(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n
dari fungsi di atas maka ada beberapa kondisi yang perlu diperhatikan, yaitu:
Jika h = h’, berarti proses pencarian telah sampai ke tujuan ( goal ).
Jika g = h’ = 0 maka f’ random, artinya system tidak dapat di kendalikan.
Jika g = k, k adalah konstanta dan biasanya bernilai 1, h’ = 0, artinya system
menggunakan breadth first search.
2. PROBLEM REDUCTION
Problem reduction atau yang biasa dikenal dengan constraint, intinya adalah berusaha mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan. Sekarang ini sudah diketahui teknik konsistensi ini sangat penting dalam penyelesaian constraint satisfactionproblem yang sangat berat sehingga semua aplikasi komersial penyelesaian constraint satisfactionproblem menggunakan teknik konsistensi ini sebagai langkah dasar. Sejarah konsistensi constraint dapat ditlusuri dari peningkatan efisiensi program pengenalan gambar oleh peneliti di intelejensi semu. Pegenalan gambar melibatkan pemberian label kepada semua garis pada gambar dengan cara yang konsisten. Jumlah kombinasi pemberian label pada garis yang memungkinkan dapat menjadi sangat besar, sementara hanya sedikit yang konsisten pada tahap awal. Dengan demikian memperpendek pencarian untuk pembeian nilai yang konsisten.Untuk mengilustrasikan teknik konsistensi ini akan diberikan sebuah contoh constraint satisfaction problem yang sangat sederhana.
Walaupun teknik konsistensi ini jarang digunakan sendirian untuk menghasilkan solusi, teknik konsistensi ini membantu menyelesaikan constraint satisfactionproblem dalam beberapa cara. Teknik konsistensi ini dapat dipakai sebelum pencarian maupun pada saat pencarian.
Kebanyakan solusi menggunakan pohonOR,dimana lintasan dari awal sampai tujuan tidak terletak pada satu cabang. Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.
Graf AND-OR
Pada dasarnya sama dengan algoritma Best First Search, dengan mempertimbangkan adanya arc AND. Gambar berikut menunjukkan bahwa untuk mendapatkan TV orang bisa dengan cara singkat yaitu mencuri atau membeli asal mempunyai uang.Untuk mendeskripsikan algoritma, digunakan nilai F_UTILITY untuk biaya solusi.
Sebagai contoh, pada Gambar 2.34 Jelas bahwa jalur melalui C selalu lebih baik daripada melalui B. Tetapi jika biaya node E muncul, dan pengaruh perubahan yang diberikan ke node B tidak sebesar pengaruhnya terhadap node C, maka jalur melalui B bisa jadi lebih baik. Sebagai contoh, hasil expand node E, misalkan 10, maka biaya node C menjadi 11 (10+1), dengan demikian biaya node A apabila memilih jalur lewat C adalah 12 (11+1). Tentu saja akan lebih baik memilih jalur melalui node B (11). Tapi tidak demikian halnya apabila kemudian node D diekspan. Bisa jadi jalur dengan melalui node B akan lebih buruk lagi ketimbang jalur dengan melalui node C.
3. CONSTAINT SATISFACTION
Penjadwalan perkuliahan merupakan suatu hal yang sangat kompleks dan rumit untuk dipecahkan. Kompleksitasnya dapat dilihat dari sisi mahasiswa, dosen yang mengajar, mata kuliah yang diajarkan, waktu perkuliahan, dan juga ruangan untuk melaksanakan perkuliahan tersebut. Kemungkinan-kemungkinan tersebut sangat mempengaruhi kinerja keseluruhan aktifitas akademis dalam suatu kampus yang akhirnya berdampak pada kompetensi kampus tersebut.
Dalam proses penjadwalan mata kuliah ada beberapa hal yang harus diperhatikan. Pertama, terdapat jadwal-jadwal di mana dosen yang bersangkutan tidak bisa mengajar. Kedua, distribusi jadwal perkuliahan diharapkan dapat merata tiap harinya untuk setiap kelas. Ketiga, pekerjaan penjadwalan mata kuliah ini akan semakin berat jika melibatkan semakin banyak kelas per angkatannya. Keempat, terdapat mata kuliah tertentu yang menggunakan ruang laboratorium yang harus dijadwalkan pada ruang laboratorium.
Karena itu dibutuhkan sebuah metode optimasi yang dapat diterapkan untuk mengerjakan penjadwalan mata kuliah ini. Metode heuristik biasanya menghasilkan solusi yang baik atau memecahkan masalah yang kompleks. Namun, kesulitan utama dalam menggunakan metode heuristik adalah heuristik bukanlah satu algoritma umum. Dalam pemecahan masalahnya metode ini mengabaikan apakah solusi dapat dibuktikan benar atau tidak. Metode heuristik berfungsi seperti algoritma tetapi tanpa jaminan optimalitas. Algoritma Genetika merupakan salah satu algoritma yang tepat digunakan dalam menyelesaikan masalah optimasi kompleks, yang sulit dilakukan oleh metode konvensional. Akan tetapi Algoritma Genetika menerapkan proses heuristik, sehingga dibutuhkan metode lain untuk membuat proses heuristik pada Algoritma Genetika menjadi terarah dan membuat keseluruhan proses menjadi lebih efisien. Metode yang tepat untuk dikombinasikan dengan Algoritma Genetika adalah Metode Constraint Satisfaction Problem (CSP). Constraint Satisfaction Problem merupakan sebuah pendekatan untuk menyelesaikan suatu masalah dengan tujuan menemukan keadaan atau objek yang memenuhi sejumlah persyaratan atau kriteria.
Constraint Satisfaction Problem adalah suatu permasalahan seseorang harus mencari nilai untuk set variabel (finite) yang memenuhi set constraint (finite). Komponen-komponen yang terdapat pada Constraint Satisfaction Problem adalah Variabel yang merupakan penampung dapat diisi berbagai nilai, Constraint yang merupakan suatu aturan yang ditentukan untuk mengatur nilai boleh diisikan ke variabel, atau kombinasi variable, Domain yang merupakan kumpulan nilai legal dapat diisi ke variable, Solusi yang merupakan assignment nilai-nilai dari domain ke setiap variabel tidak ada constraint yang dilanggar.
Constraint Satisfaction Problem dimulai dari solusi kosong dan diakhiri dengan sebuah solusi yang memenuhi semua constraint (consistent). Pencarian solusi dilakukan dengan mencoba mengisi nilai domain pada setiap variabel satu demi satu tanpa melanggar constraint, sampai solusi ditemukan. Algoritma yang paling banyak dipakai untuk melakukan pencarian sistematik untuk menyelesaikan Constraint Satisfaction Problem adalah backtracking. Algoritma backtracking search (penelusuran kembali) adalah suatu bentuk algoritma depth-first-search. Backtracking dapat dilihat sebagaimana searching dalam tree, karena setiap node mewakili state dan turunan dari setiap node mewakili ekstensi dari state tersebut.
Pada metode backtracking, variabel diisi secara sequential selagi semua variabel relevan dengan constraint yang sudah diinisialisasi. Jika solusi partial melanggar constraint, backtracking melakukan langkah kembali ke solusi partial sebelumnya dan memilih nilai lain yang belum dicoba untuk variabel yang ingin diisikan. Langkah tersebut berguna untuk menghindari eksplorasi lebih lanjut dari solusi partial yang salah. Keuntungan backtracking adalah pemeriksaan consistency hanya perlu dilakukan terhadap assignment yang terakhir dilakukan karena pemeriksaan terhadap assignment yang sebelumnya sudah dilakukan sebelumnya.
Pada algoritma backtracking, teknik look ahead digunakan untuk meramalkan efek pemilihan variabel branching untuk mengevaluasi nilai-nilai variabel tersebut. Forward checking adalah salah satu cara untuk melakukan look ahead. Forward checking mencegah terjadinya konflik dengan melarang nilai-nilai yang belum diisikan ke variable untuk dipakai. Ketika suatu nilai diisikan ke suatu variabel, nilai yang berada di domain dari variabel yang konflik dengan assignment tersebut akan dihilangkan dari domain.
Minimum Remaining Value (MRV) adalah suatu teknik yang dikembangkan untuk menangani masalah kemungkinan besar gagal pada pencarian menggunakan Constraint Satisfaction Problem. Minimum Remaining Value berkerja dengan memilih variabel yang memiliki domain legal dan paling sedikit (memiliki kemungkinan untuk membuat suatu dead-end paling besar) untuk diisikan terlebih dulu.
Algoritma Genetika pada dasarnya adalah program komputer yang mensimulasikan proses evolusi. Algoritma Genetika juga merupakan algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahan masalah (problem solving). Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness.
Algoritma Genetika bekerja menggunakan kode dari parameter yang menjadi permasalahan. Parameter problem tersebut dikodekan menjadi sebuah kromosom. Setiap kromosom terdiri dari bagian-bagian yang disebut gen. Gen-gen ini dapat berupa angka biner (‘1’ dan ‘0’), sehingga kromosom yang terbentuk merupakan sebuah deretan string biner. Pencarian solusi pada algoritma ini melibatkan sejumlah populasi dari titik-titik pada ruang parameter. Setiap titik tersebut disebut individu. Variable dan parameter yang digunakan yaitu fitness (nilai hasil evaluasi Objective Function yang dipakai untuk tolak ukur kualitas kromosom) untuk menentukan tingkat kesesuaian suatu individu dengan kriteria yang ingin dicapai, populasi jumlah individu per generasi, probabilitas terjadinya crossover pada suatu generasi, probabilitas terjadinya mutasi, serta banyaknya generasi yang dilibatkan.
4. MEANS END ANALYSIS
Sarana-Ends Analysis (MEA) adalah teknik yang digunakan dalam Artificial Intelligence untuk mengontrol pencarian dalam program komputer pemecahan masalah.
Ini juga merupakan teknik yang digunakan setidaknya sejak tahun 1950-an sebagai alat kreativitas, yang paling sering disebutkan dalam buku-buku teknik pada metode desain. Sarana-Ends Analysis juga merupakan cara untuk menjernihkan pikiran seseorang ketika memulai sebuah bukti matematis.
Model pembelajaran ini adalah variasi dari pembelajaran dengan pemecahan masalah dengan sintaks:
sajikan materi dengan pendekatan pemecahan masalah berbasis heuristic, elaborasi menjadi sub-sub masalah yang lebih sederhana, identifikasi perbedaan, susun sub-sub masalah sehingga terjadli koneksivitas, pilih strategi solusi
Model Means-Ends Analysis adalah variasi dari pembelajaran dengan pemecahan masalah dengan sintaks:
- sajikan materi dengan pendekatan pemecahan masalah berbasis heuristic,
- elaborasi menjadi sub-sub masalah yang lebih sederhana,
- identifikasi perbedaan,
- susun sub-sub masalah sehingga terjadi koneksivitas,
- pilih strategi solusi.
Cara kerja MEA
Teknik MEA adalah strategi untuk mengontrol pencarian dalam memecahkan masalah. Mengingat keadaan saat ini dan negara tujuan, suatu tindakan yang dipilih akan mengurangi perbedaan antara keduanya. Tindakan ini dilakukan pada keadaan saat ini untuk menghasilkan negara baru, dan proses ini secara rekursif diterapkan untuk negara baru dan negara tujuan.
Perhatikan bahwa, agar MEA menjadi efektif, tujuan-sistem mencari harus memiliki sarana bergaul untuk setiap jenis perbedaan terdeteksi tindakan-tindakan yang relevan untuk mengurangi perbedaan itu. Hal ini juga harus memiliki cara untuk mendeteksi kemajuan itu adalah keputusan (perubahan perbedaan antara ktual dan negara yang diinginkan), karena beberapa urutan mencoba tindakan mungkin gagal dan, karenanya, beberapa urutan alternatif mungkin dicoba.
Ketika pengetahuan tersedia mengenai pentingnya perbedaan, perbedaan yang paling penting adalah dipilih pertama untuk lebih meningkatkan kinerja rata-rata MEA atas lain brute force strategi pencarian. Namun, bahkan tanpa pemesanan perbedaan menurut kepentingan, meningkatkan MEA atas heuristik pencari lainnya
(lagi dalam kasus rata-rata) dengan fokus pemecahan masalah tentang perbedaan yang sebenarnya antara negara saat ini dan bahwa tujuan.
Sumber Referensi:
Tidak ada komentar:
Posting Komentar