diklatkerja | Mengenal Pengertian, Fungsi dari Heuristik dalam Ilmu Komputer

Heuristik

Dalam optimasi matematika dan ilmu komputer, adalah teknik yang dirancang untuk memecahkan masalah lebih cepat ketika metode klasik terlalu lambat atau untuk menemukan solusi perkiraan ketika metode klasik gagal untuk menemukan solusi yang tepat. . Hal ini dicapai dengan perdagangan optimalitas, kelengkapan, akurasi, atau presisi untuk kecepatan. Di satu sisi, itu bisa dianggap sebagai jalan pintas.

Fungsi heuristik,

fungsi yang memberi peringkat alternatif dalam algoritma pencarian pada setiap langkah percabangan berdasarkan informasi yang tersedia untuk memutuskan cabang mana yang akan diikuti. Misalnya, mungkin mendekati solusi yang tepat.

Definisi dan motivasi

Tujuan dari heuristik adalah untuk menghasilkan solusi dalam kerangka waktu yang wajar yang cukup baik untuk memecahkan masalah yang dihadapi. Solusi ini mungkin bukan yang terbaik dari semua solusi untuk masalah ini, atau mungkin hanya mendekati solusi yang tepat. Tapi tetap berharga karena menemukannya tidak membutuhkan waktu yang lama.

Heuristik dapat menghasilkan hasil sendiri, atau mereka dapat digunakan bersama dengan algoritma optimasi untuk meningkatkan efisiensinya (misalnya, mereka dapat digunakan untuk menghasilkan nilai benih yang baik). Hasil tentang NP-hardness dalam ilmu komputer teoretis menjadikan heuristik satu-satunya pilihan yang layak untuk berbagai masalah optimasi kompleks yang perlu diselesaikan secara rutin dalam aplikasi dunia nyata. Heuristik mendasari seluruh bidang Kecerdasan Buatan dan simulasi komputer berpikir, karena mereka dapat digunakan dalam situasi di mana tidak ada algoritma yang diketahui.

Trade-off

Kriteria trade-off untuk memutuskan apakah akan menggunakan heuristik untuk memecahkan masalah yang diberikan meliputi:

Optimalitas: Ketika ada beberapa solusi untuk masalah yang diberikan, apakah heuristik menjamin bahwa solusi terbaik akan ditemukan? Apakah benar-benar perlu untuk menemukan solusi terbaik?
Kelengkapan: Ketika ada beberapa solusi untuk masalah yang diberikan, dapatkah heuristik menemukan semuanya? Apakah kita benar-benar membutuhkan semua solusi? Banyak heuristik hanya dimaksudkan untuk menemukan satu solusi.
Akurasi dan presisi: Dapatkah heuristik memberikan interval kepercayaan untuk solusi yang diklaim? Apakah bilah kesalahan pada solusi terlalu besar?
Waktu eksekusi: Apakah ini heuristik paling terkenal untuk memecahkan masalah jenis ini? Beberapa heuristik berkumpul lebih cepat daripada yang lain. Beberapa heuristik hanya sedikit lebih cepat daripada metode klasik, dalam hal ini 'overhead' dalam menghitung heuristik mungkin berdampak negatif.

Dalam beberapa kasus, mungkin sulit untuk memutuskan apakah solusi yang ditemukan oleh heuristik cukup baik, karena teori yang mendasari heuristik tidak terlalu rumit.

Contoh

Masalah yang lebih sederhana

Salah satu cara untuk mencapai perolehan kinerja komputasi yang diharapkan dari heuristik terdiri dari pemecahan masalah yang lebih sederhana yang solusinya juga merupakan solusi untuk masalah awal.

Masalah penjual keliling

Contoh pendekatan dijelaskan oleh Jon Bentley untuk memecahkan masalah penjual keliling (TSP):

Diberikan daftar kota dan jarak antara setiap pasangan kota, apa rute terpendek yang mungkin mengunjungi setiap kota tepat satu kali dan kembali ke kota asal?

sehingga dapat memilih urutan menggambar menggunakan pen plotter. TSP dikenal sebagai NP-hard sehingga solusi optimal untuk masalah ukuran sedang pun sulit untuk dipecahkan. Sebaliknya, algoritma serakah dapat digunakan untuk memberikan solusi yang baik tetapi tidak optimal (ini adalah perkiraan untuk jawaban yang optimal) dalam waktu yang cukup singkat. Heuristik algoritma serakah mengatakan untuk memilih apa pun yang saat ini merupakan langkah terbaik berikutnya terlepas dari apakah itu mencegah (atau bahkan membuat tidak mungkin) langkah baik nanti. Ini adalah heuristik dalam praktik yang mengatakan itu adalah solusi yang cukup baik, teori mengatakan ada solusi yang lebih baik (dan bahkan dapat mengatakan seberapa jauh lebih baik dalam beberapa kasus).

Mencari

Contoh lain dari heuristik membuat algoritma lebih cepat terjadi pada masalah pencarian tertentu. Awalnya, heuristik mencoba setiap kemungkinan pada setiap langkah, seperti algoritma pencarian ruang penuh. Tapi itu bisa menghentikan pencarian kapan saja jika kemungkinan saat ini sudah lebih buruk daripada solusi terbaik yang sudah ditemukan. Dalam masalah pencarian seperti itu, heuristik dapat digunakan untuk mencoba pilihan yang baik terlebih dahulu sehingga jalur yang buruk dapat dihilangkan lebih awal (lihat pemangkasan alfa-beta). Dalam kasus algoritma pencarian terbaik-pertama, seperti pencarian A*, heuristik meningkatkan konvergensi algoritma sambil mempertahankan kebenarannya selama heuristik dapat diterima.

Newell dan Simon: hipotesis pencarian heuristik

Dalam pidato penerimaan Penghargaan Turing mereka, Allen Newell dan Herbert A. Simon membahas hipotesis pencarian heuristik: sistem simbol fisik akan berulang kali menghasilkan dan memodifikasi struktur simbol yang diketahui sampai struktur yang dibuat cocok dengan struktur solusi. Setiap langkah berikutnya tergantung pada langkah sebelumnya, sehingga pencarian heuristik mempelajari jalan apa yang harus dikejar dan mana

perlu diabaikan dengan mengukur seberapa dekat langkah saat ini dengan solusi. Oleh karena itu, beberapa kemungkinan tidak akan pernah dihasilkan karena kemungkinannya kecil untuk menyelesaikan solusi.

Metode heuristik dapat menyelesaikan tugasnya dengan menggunakan pohon pencarian. Namun, alih-alih menghasilkan semua cabang solusi yang mungkin, heuristik memilih cabang yang lebih mungkin menghasilkan hasil daripada cabang lainnya. Ini selektif pada setiap titik keputusan, memilih cabang yang lebih mungkin menghasilkan solusi.

Perangkat lunak antivirus

Perangkat lunak antivirus sering menggunakan aturan heuristik untuk mendeteksi virus dan bentuk malware lainnya. Pemindaian heuristik mencari kode dan/atau pola perilaku yang umum pada kelas atau keluarga virus, dengan seperangkat aturan yang berbeda untuk virus yang berbeda. Jika file atau proses eksekusi ditemukan berisi pola kode yang cocok dan/atau melakukan rangkaian aktivitas tersebut, pemindai menyimpulkan bahwa file tersebut terinfeksi. Bagian paling canggih dari pemindaian heuristik berbasis perilaku adalah bahwa ia dapat bekerja melawan virus yang sangat acak yang memodifikasi/bermutasi (polimorfik) yang tidak dapat dengan mudah dideteksi dengan metode pemindaian string yang lebih sederhana. Pemindaian heuristik memiliki potensi untuk mendeteksi virus di masa depan tanpa mengharuskan virus untuk pertama kali terdeteksi di tempat lain, diserahkan ke pengembang pemindai virus, dianalisis, dan pembaruan deteksi untuk pemindai yang diberikan kepada pengguna pemindai.

Jebakan

Beberapa heuristik memiliki teori dasar yang kuat; mereka diturunkan secara top-down dari teori atau diperoleh berdasarkan data eksperimental atau dunia nyata. Yang lain hanyalah aturan praktis berdasarkan pengamatan atau pengalaman dunia nyata bahkan tanpa melihat teori. Yang terakhir terkena lebih banyak jebakan.

Ketika heuristik digunakan kembali dalam berbagai konteks karena telah terlihat "berfungsi" dalam satu konteks, tanpa terbukti secara matematis untuk memenuhi serangkaian persyaratan tertentu, ada kemungkinan bahwa kumpulan data saat ini tidak selalu mewakili kumpulan data masa depan ( lihat: overfitting) dan "solusi" yang diklaim itu ternyata mirip dengan kebisingan.

Analisis statistik dapat dilakukan ketika menggunakan heuristik untuk memperkirakan kemungkinan hasil yang salah. Untuk menggunakan heuristik untuk memecahkan masalah pencarian atau masalah knapsack, perlu untuk memeriksa apakah heuristik tersebut dapat diterima. Diberikan fungsi heuristik $h(v_{i},v_{g})$ dimaksudkan untuk mendekati jarak optimal sebenarnya $d^{\star }(v_{i},v_{g})$ ke simpul tujuan $v_{g}$ dalam grafik berarah $G$ berisi $n$ total simpul atau simpul berlabel $v_{0},v_{1},\cdots ,v_{n}$ "diterima" berarti secara kasar bahwa heuristik meremehkan biaya untuk tujuan atau secara formal bahwa $h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})$ untuk semua $(v_{i},v_{g})$ di mana ${i,g}\in [0,1,...,n]$

Jika heuristik tidak dapat diterima, heuristik mungkin tidak akan pernah menemukan tujuannya, baik dengan berakhir di jalan buntu grafik $G$ atau dengan melompat-lompat di antara dua node $v_{i}$ dan $v_{j}$ dengan ${i,j}\neq g$ .

Disadur dari : en.wikipedia.org