Contoh Fungsi Heuristik Pada Artificial Intelligence (AI)
Pada artikel ini akan dibahas fungsi heuristik pada Artificial Intelligence (AI). Banyak sekali metode metode yang termasuk heuristic search, fungsi heuristik memainkan peranan yang sangat menentukan. Suatu fungsi dapat diterima sebagai fungsi heuristik jika biaya perkiraan yang dihasilkan tidak melebihi dari biaya sebenarnya. Ketika fungsi heuristik membeikan biaya perkiraan yang melebihi biaya sebenarnya (overestimate), maka proses pencarian bsia tersesat dan membuat heuristic search menjadi tidak optimal.
Suatu fungsi heuristik dikatakan baik jika membebrikan biaya perkiraan yang mendekati baiya sebenarnya. Semakin mendekati biaya sebenearnya, fungsi heuristik tersebut semakin baik. Perhatikan dua contoh kasus dibawah ini untuk menentukan fungsi heuristik yang baik.
1. Masalah Pencarian Rute Terpendek
Terdapat emapt kota dengan koordinat petanya (20,10), B (35,10), C(55,10) dan D(65,10). Busur AB menyatakan jalan raya dengan panjang 20 km, busur BC dengan panjang 50 km, dan usur CD dengan panjang 10 km.
Dalam kasus pencarian rute terpendek, biaya sebenarnya adalah panjang jalan raya yang sebenarnya. Sedangkan fungsi heuristik yang bisa digunakan adalah jarak garis lurus yang bisa di hitung menggunakan rumus.
Dengan menggunakan rumus fungsi heuristik, maka jarak garis lurus dari A ke B adalah 15 (dAb = 15) dan haraj garis lurus dari B ke C adalah (dBC = 20). Jika dibandingkan dengan panjang jalan yang sebenarnya, dAB sangat mendekati jarak sebenarnya sedangkan dBC jauh lebih kecil (understimate) dibandingkan dengan jarak sebenarna. Tetapi, dCD sama dengan jarak sebenarnya. Rumus pada persamaan menjamin bahwa jarak perkiraan yang dihasilkan pasti lebih kecil atau sama dengan jarak sebenarnya. Sehingga persamaan tersebut dapat digunakan sebagai fungsi heursitik. Di dunia nyata terdapat banyak jalan raya yang bentuknya memutar ataupun jalan satu arah sehingga kita harus berputar dulu untuk ketempat tujuan. Dengan kondisi tersebut, persamaan akan adakah perasamaan lain yang lebih baik yang dapat digunakan dalamm fungsi heuristik ? Jika ada dan memberikan nilai yang lebih mendekati biaya sebenarnya dibandingkan persamaan 2.5, maka lebih baik kita menggunakan fungsi heuristik tersebut.
2. Masalah 8-Puzzle
Pada permasalah permainan 8 puzzle, terdapat delapan angka yang bisa di geser ke kiri, kanan, atas atau bawah. Jika diketahui goal state dan operator, kita dapat menentukan fungsi heuristik yang dapat digunakan
Terdapat dua jenis fungsi heuristik yang bisa digunakan :
- h1 = jumlah kotak yang posisinya salah. Pada masalah di atas, angka 1,2, dan 3 sudah berada pada posisi yang benar. Sedangkan lima angka yang lain berada di posisi yang salah. Jadi h1 = 5.
- h2 = jumlah langkah yang diperlukan masing-masing kotak menuju posisi yang benar goal satete. Biasanya disebut City Block Distance atau Manhattan Distance. Untuk masalah di atas , angka 1,2 dan 3 membutuhkan 0 langkah, Angka 4,5,6,7, dan 8 membutuhkan 2 langkah. Sedangkan angka 6 membutuhkan 3 langkah.
Kedua fungsi di atas dapat digunakan sebagai fungsi heuristik karena total langkah yang diperlukan daru satu state menuju goal state minimal sama dnegan jumlah posisis yang salah (h1) atau sama dengan total langkah yang diperlukan masing-masing kota menuju posisi yang benar di goal state (h2). Selanjutnya, karena setiap angka yang posisinya salah maka membutuhkan minimal satu langkah untuk mencapai posisi yang benar, maka dapat dijamin bahwa nilai h2 selalu lebih besar atau sama dengan nilai h1. mana yang lebih baik, h1 atau h2 ? Ini menjelaskan bahwa h2 yang bernilai lebih (terutama ketika solusi berada di level yang dalam). Untuk solusi yang berada di level 24, A* dengan h2 harus membangkitkan node (30 kali lebih sedikit). Dapat disimpulkan bahwa heuristik terbaik adalah yang paling mendekati biaya sebenarnya (tetapi tidak pernah melebihi biaya sebenarnya). Oleh karena itu kita menemukan lebih dari satu fungsi heuristik, maka pilihlah fungsi heuristik yang memberikan biaya perkiraan yang paling mendekati biaya sebenarnya.
Kesimpulan
Metode metode yang termasuk dalam lind search membutuhkan memori yang sangat besar untuk menyelesaikan masalah yang sederhana. Dengan kecepatan dalam memori komputer yang terbatas, saat ini blind search belum memungkinkan untuk diimplementasikan ke dalam dunia nyata. Satu satunya metode yang mungkin bisa digunakan adlah Iterative Deepening Search (IDS) karena membutuhkan memori yang angat sedikit meskipun waktu prosesnya sangat lama.
Diantara metode metode pencarian yang termausk dalam heuristic search, A* adalah pilihan yang terbaik ketika kita dapat menemukan sebuah fungsi heuristic untuk masalah yang akan diselesaikan. Tetapi jika tida da fungsi heuristic, A* tidak bisa digunakan. Lebih jauh, kita dapat memilih sauatu variasi A* yang paling sesuai dengan masalah yang akan diselesaikan dan sumber daya( waktu dan memori) yang kita miliki.
Ketika ditemukan lebih dari satu jenis fungsi heuristik, maka fungsi heuristik yang paling mendekati biaya sebenarnya akan memberikan performansi terbaik.
Ketika memori yang tersedia sangat terbatas, misalkan pada PDA(Personal Digital Assistant), maka variasi variasi A*, seperti IDA* dan SMA*, dapat digunakan sebagai alternatif lain yang menjajikan. Tetapi, perlu diperhitungkan jumlah memori dan kecepatan prosesor yang ada.
Untuk maslaah yang memiliki satu jenis goal, maka bi-directional search bisa dianggap sebagai alternatif terbaik ketika ruang maslaahnya sangat besar. Modified Bi-Directional A* (MBDA*) memberikan performansi sangat baik untuk ruang masalah yang sangat besar. Modified Bi-Directional A* ini juga bisa menggunakan variasi A* yang lain. Misalnya Beam A* maupun Weightig A* sehingga kita bisa menyebutnya sebagai Modified Bi-Directional Beam A* atau Modified Bi Directional Weighting A*.
Simulated Annealing (SA) merupakan algoritma yang selalu maju (pada setiap iterasi selalu menghasilkan simpul di level yang lebih dalam). SA bekerja dengan hanya memperhitungkan sibling (simpul yang memiliki parent yang sama). Sehingga tidak pernah mundur untuk mencari jalur yang lebih baik. Ketika memori dan kecepatan prosesor sangat terbatas dan solusi yang diharapkan tidak harus optimal, maka Simulated Annealing (SA) adalah pilihan yang paling tepat di antara semua algoritma heuristic search.
Untuk memilih metode pencarian yang tepat, dipelrukan identifikasi maslah yang sangat detail dan berbeda-beda untuk setiap masalah (yang terkadang angat unik). Tetapi langkah langkah umum yang biasa di gunakan adalah :
- Seberapa besar ruang amasalah ?
- Berapaka faktor percabangan (b) dan kedalaman solusinya (d)?
- Berapa kecepatan prosesor dan memori yang tersedia?
- Apakah solusinya harus optimal ?
- Bisakah ditemukan fungsi heuristiknya ?
- Terdapat satu macam goal atau lebih ?
Post a Comment for "Contoh Fungsi Heuristik Pada Artificial Intelligence (AI)"