Sabtu, 23 Maret 2019

Heuristik dan Metaheuristik




Heuristik (yunani heuriskein) yaitu  seni untuk menemukan strategi dalam menyelesaikan persoalan sedangkan meta berarti metodologi tingkat tinggi atau lanjut (Talbi, 2009).  Di dalam ilmu komputer, metode heuristik merupakan suatu teknik untuk penyelesaian permasalahan yang tidak menekankan pada pembuktian apakah solusi yang didapatkan adalah benar (pembuktian apakah suatu solusi adalah benar merupakan fokus dari metode penyelesaian analitik), tetapi lebih menekankan pada performa komputasi dan kesederhanaan. Metode heuristik  merupakan suatu metode penyelesaian yang menggunakan konsep pendekatan.


Tulisan ini copy paste, hanya sekedar sebagai referensi saja 

Menurut Blum dan Roli (2003), metaheuristik memiliki beberapa karakteristik dasar yaitu:
  1. Metaheuristik adalah strategi yang memandu proses pencarian.
  2. Tujuan dari metaheuristik adalah untuk menjelajahi ruang pencarian secara efficient untuk menemukan solusi optimal.
  3. Teknik metaheuristik berkisar dari prosedur pencarian local yang sederhana sampai proses pembelajaran yang komplek.
  4. Meteheuristik adalah metode pendekatan dan biasanya non-deterministik.
  5. Metaheuristik dapat terdiri dari penggabungan beberapa mekanisme supaya proses pencarian tidak terjebak dalam daerah terbatas  di ruang pencarian.

Metode metahuristik adalah metode optimisasi yang dilakukan dengan memperbaiki kandidat penyelesaian secara iteratif sesuai dengan fungsi objektifnya (Talbi. 2009). Metode ini mampu menghasilkan penyelesaian yang baik dalam waktu yang cepat (acceptable), tetapi tidak menjamin bahwa penyelesaian yang dihasilkan merupakan penyelesaian terbaik (optimal). Metaheuristik ini menekankan pada proses eksplorasi (pencarian global) dan eksploitasi (pencarian lokal).

Metode metaheuristik pada masa modern ini sering diinspirasi dari kejadian-kejadian alami baik dari tingkah laku hewan, tumbuhan dan juga konsep evolusi. Metode metaheuristik yang menggunakan konsep evolusi diinspirasi dari hukum Darwin, bahwa yang bertahan adalah yang paling kuat atau yang paling baik. Teknik evolusi digunakan pada algoritma genetika (Genetic Algorithm) dan Differential Evolution (DE) untuk membantu menemukan solusi optimal suatu permasalahan. Adapun algoritma yang didasarkan pada teknik swarm intelligence yaitu seperti halnya Particle Swarm Optimization (PSO), Ant Colony Optimization, Artificial Bee Colony, Chuckoo Search, Firefly, and Bat Algorithm.

ref:
C. Blum, A, Roli. 2003. Metheuristic in Combinatorial Optimization: Overview in conceptual comparison. ACM Computing Surveys, 35(3):268-308
Talbi. 2009. Metaheuristics: From Design to Implementation. Wiley. New York.

Tidak ada komentar: