Heuristik berasal dari kata Yunani heuriskein yang berarti seni untuk menemukan strategi dalam menyelesaikan persoalan sedangkan meta berarti metodologi tingkat tinggi atau lanjut (Talbi, 2009). Didalam 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.
Menurut Talbi (2009), metaheuristik dapat didefinisikan sebagai metode lanjut (advanced) berbasis heuristic untuk menyelesaikan persoalan optimisasi secara efficient. Di dalam wikipedia, metaheuristik didefinisikan sebagai metode optimisasi yang dilakukan dengan memperbaiki kandidat penyelesaian secara iteratif sesuai dengan fungsi objektifnya. Metode ini mampu menghasilkan penyelesaian yang baik dalam waktu yang cepat (acceptable), tetapi tidak menjamin bahwa penyelesaian yang dihasilkan merupakan penyelesaian terbaik (optimal). Metode metaheuristik banyak dipakai dalam optimisasi stokastik (optimisasi stokastim merupakan optimisasi yang memiliki derajat ketidakpastian atau random).
Menurut Blum and Roli (Blum & Roli, 2003), metaheuristik memiliki beberapa karakteristik dasar yaitu:
a) Metaheuristik adalah strategi yang memandu proses pencarian
b) Tujuan dari metaheuristik adalah untuk menjelajahi ruang pencarian secara efficient untuk menemukan solusi optimal.
c) Teknik metaheuristik berkisar dari prosedur pencarian local yang sederhana sampai proses pembelajaran yang komplek
d) Meteheuristik adalah metode pendekatan dan biasanya non-deterministik
e) Metaheuristik dapat terdiri dari penggabungan beberapa mekanisme supaya proses pencarian tidak terjebak dalam daerah terbatas di ruang pencarian.
f) Konsep dasar dari metaheuristik memungkinkan pendeskripsian secara abstrak
g) Metaheuristik bersifat general/umum sehingga dapat diterapkan dalam berbagai macam persoalan
h) Metaheuristik dapat menggunakan domain pengetahuan khusus dalam bentuk heuristik yang dikendalikan dengan strategi tingkat lanjut
i) Metaheuristik dapat menggunakan pengalaman yang didapat selama proses pencarian untuk menuntun proses pencarian.
Dalam menentukan apakah metaheuristik adalah metode yang sesuai untuk menyelesaikan suatu permasalahan, ada beberapa hal yang perlu diperhatikan misalnya kompleksitas permasalahan, ukuran input, struktur input dan waktu yang diperlukan untuk menyelesaikan masalah tersebut. Secara umum metehauristik dipakai untuk masalah-masalah yang komplek dan tidak bisa diselesaikan dengan mudah secara analitikal/eksak. Tidaklah terlalu bermanfaat menggunakan metaheuristik untuk persoalan yang dengan mudah dan cepat dapat diselesaikan secara eksak (penyelesaian eksak merupakan penyelesaian terbaik, tetapi seringkali metode ini tidak dapat diterapkan pada permasalahan optimisasi, sehingga dipakailah metode pendekatan).
Demikian sekilas tentang definisi metaheuristik.
Duniaku 
boleh tau referensinya dari mana? ku lagi belajar metaheuristics
Salam Topa:
Tulisan saya diatas banyak diambil dari buku berikut ini:
Talbi, E.-G. (2009). Metaheuristik: from design to implementation. Hoboken, New Jersey: John Wiley & Son, Inc
Semoga membantu
seberapa komplek suatu masalah diselesaikan dengan metaheuristik?
lalu mengapa ada heuristik dan metaheuristik? apa perbedaan di antara keduanya?
terima kasih atas jawabannya… ^-^
Hi Tika, terima kasih atas pertanyaannya. Akan saya coba untuk menjawabnya..
Untuk pertanyaan pertama, sampai saat ini belum ada pembatasan yang pasti tentang seberapa kompleks suatu permasalahan layak diselesaikan dengan metode metaheurisik.
Yang perlu diingat adalah, jika ada metode eksak yang bisa berkerja dengan baik untuk menyelesaikan suatu permasalahan, maka metode metaheuristik tidak diperlukan. Jadi metode metaheuristik sebaiknya tidak menjadi pilihan pertama dalam menyelesaikan permasalahan optimisasi.
Meskipun begitu, ada beberapa permasalahan yang umum di selesaikan menggunakan metode metaheuristik, misalnya adalah NP-hard problem.
Contoh dari NP-hard problem adalah: TSP, VRP, assembly line balancing problems. Untuk skala kecil, metode eksak dapat dipakai untuk menyelesaiakan permasalahan ini secara baik (misalnya menggunakan metode branch and bound). Akan tetapi, dalam skala besar, penggunaan metode eksak (misalnya metode branch and bound) akan memerlukan waktu yang lama (waktu yg diperlukan eksponensial terhadap ukuran inputnya), sehingga metode metaheuristik dipakai untuk mempercepat proses penyelesaian.
persamaan-persamaan multi variabel dengan derajat yang tinggi juga sulit diselesaikan menggunakan metode derivatif yang konvensional, sehingga metode metaheuristik dapat dipakai untuk menyelesaikan permasalah tersebut.
Untuk pertanyaaan kedua: metode heuristik lebih bersifat ‘problem spesific’ sehingga hanya diterapkan untuk jenis permasalahan tertentu.
Sedangkan metaheuristik lebih bersifat umum, sehingga dapat dipakai untuk berbagai macam jenis permasalahan optimisasi. Kata ‘meta’ sendiri artinya adalah ‘higher level’. Biasanya, metode heuristik diadopsi didalam metode metaheuristik, untuk meningkatkan performa dari metaheuristik.
Sebagai contoh: metode ‘nearest neighbour’ merupakan metode Heuristik. Metode ini hanya dipakai pada permasalahan yang dapat direpresentasikan dalam besaran jarak (misalnya TSP).
Sedangkan Algoritma Genetik merupakan metode metaheuristik. Metode ini dapat dipakai untuk menyelesaikan beragam permasalahan, misalnya TSP, penjadwalan, optimasi konstruksi bangunan, optimisasi layout pabrik dll.
Contoh metode heuristik yang diadopsi didalam metode metaheusristik adalah, pengunaan metode ‘nearest neighbour’ untuk inisialisasi populasi didalam metode Algoritma Genetik.
Demikian jawaban dari saya, semoga dapat membantu…
terima kasih banyaaaaak 🙂
sama-sama… 🙂
1. apa yang dimaksud dengan NP-hard? apa bedanya dengan NP-complete??
2. metode analitikal itu benarkah metode yang menghasilkan jawaban yang PASTI optimal atau tidak?? apa yg dimaksud dgn analitikal?? maksudnya jawabannya PASTI gt bukan trial and error kah?? contoh mtode analitikal lainnya : Ford Fulkerson method, linear programming??
3. metaheuristik itu tral andd error kah??
terimakasih sebelumnya atas jawabannya..
dan jg artikel yang membantu ini.. ^^,
Hi Silvy, terima kasih atas pertanyaannya. Akan saya coba untuk menjawabnya..
1. Saya akan menjawabnya dari sudut pandang sebagai berikut:
NP = permasalahan optimisasi yang penyelesaiannya dapat diverifikasi/dibuktikan berada dalam batasan waktu polinomial ( O (n ^ k) dimana n adalah ukuran permasalahannya dan k adalah suatu konstanta).
Di dalam NP, ada permasalahan yang sudah bisa diselesaikan dalam batasan waktu polinomial (algorithma untuk menyelesaikan persoalan tersebut dalam batasan waktu polinomial sudah diketahui) dan ada juga permasalahan yang algorithma untuk menyelesaikannya dalam batasan waktu polinomial belum diketahui (tetapi juga tidak bisa dibuktikan bahwa algorithma tersebut tidak ada).
NP-hard = secara informal di definisikan sebagai permasalahan optimisasi yang setidak-tidaknya sesulit permasalahan NP yang tersulit.
Maksudnya adalah sebagai berikut:
– algorithma yang bisa menyelesaikan permasalahan tersebut dalam batasan waktu polinomial belum diketahui.
– di dalam NP-hard, ada permasalahan yang sudah bisa dibuktikan dapat diselesaikan dalam batasan waktu polinomial dan ada juga yang belum bisa (mungkin tidak bisa) dibuktikan apat diselesaikan dalam batasan waktu polinomial.
NP-complete : adalah permasalahan yang masuk kategori NP sekaligus NP-hard (irisan antara NP dan NP-hard).
Jadi disini maksudnya:
– penyelesaian permasalahan NP-complete dapat diverifikasi/dibuktikan berada dalam batasan waktu polinomial,
– algorithma yang bisa menyelesaikan permasalahan tersebut dalam batasan waktu polinomial belum diketahui (tetapi juga tidak bisa dibuktikan bahwa algorithma tersebut tidak ada).
2. metode analitikal adalah metode yang PASTI menghasilkan jawaban optimal.
Analitikal maksudnya adalah jawaban yang di berikan dapat di buktikan secara matematis sebagai jawaban yang optimal.
Metode analitical seringkali disebut juga dengan “exact method”
saya tidak mengerti pertanyaan Silvy “maksudnya jawabannya PASTI gt bukan trial and error kah??”
tapi kemungkinan yang dimaksud disini adalah jawaban optimal (exact solution). dan jawaban optimal itu bukan trial atau error.
linear programming termasuk dalam metode analitical.
3. Metaheuristic pada dasarnya adalah metode approximasi, jd termasuk dalam merode trial and error. hanya saja disini trial-nya sudah di arahkan secara cerdas.
Demikian jawaban dari saya, semoga membantu …
terimaaaakasiih banyaakkk yaaa… 😀
hmmm..bisa kasih contoh NP sama NP hard??
combinatorial problem??
thx again…:p
Contoh untuk:
1. NP : menentukan apakah 2 graph adalah isomorphic
2. NP-hard : Travelling salesman problem.
ok thx
assalamualaikum wr.wb..
skripsi saya tentang Ant Colony Optimization (ACO), saya bingung ini termasuk algoritma Heuristic, metaheuristic, atau algoritma optimasi??
terus,, perbedaan yang paling signifiikan dan contoh dari masing-masing algoritma yang saya sebutkan di atas apa??
terimakasih 🙂
Halo Dini, terima kasih atas pertanyaannya. Saya coba menjawab. Untuk memudahkan, saya mencoba menjelaskan perbedaan ketiga algoritma yang DIni sebutkan.
Algoritma optimasi merupakan suatu metode untuk menyelesaikan permasalahan optimisasi. Algoritma ini dibagi menjadi: metode eksak (exact method/metode analitikal) dan metode pendekatan (approximate method).
Exact method menjamin bahwa hasil penyelesaian yang diperoleh adalah optimal, sedangkan approximate method tidak menjamin bahwa hasil yang diperoleh adalah hasil optimal (meskipun tidak optimal, tetapi memiliki kualitas yang baik).
Nah, metode heuristik termasuk approximate method.
Sedangkan metaheuristic adalah approximate method yang bisa dipakai untuk berbagai jenis permasalahan optimisasi. Dan metode ini memang didasarkan pada metode heuristik, hanya saja dia general purpose gitu (makanya disebut meta-heuristik).
Perbedaan utama heuristik dan metaheuristik adalah : metode heuristik it problem dependent (bergantung pada permasalahan/ hanya bisa dipakai untuk jenis permasalahan tertentu) sedangkan metode metaheuristik itu problem independent (bisa dipakai untuk berbagai jenis permasalahan).
Baik heuristik maupun metaheuristik keduanya adalah jenis algoritma optimisasi.
Sedangkan Ant Colony Optimization (ACO) termasuk metode metaheuristik, lebih spesifiknya population based metaheuristics dan masuk kategori swarm intelligence algorithm.
Untuk klasifikasi metode metaheuristik, bisa dilihat di artikel saya tentang klasifikasi metaheuristik
Demikian jawaban dari saya, semoga membantu
ow.. begitu 🙂 oke jadi sedikit paham saya, berarti saya menyebut ACO di proposal skripsi saya sebagai algoritma mettaheuristic saja ya 🙂 kayaknya lebihh cocok maknanya..
kalau boleh minta email panjenengan pak?? 🙂 mungkin bisa ngobrol via email..
ada lagi yang saya tanyakan,, klo algoritma seperti ACO, swam, GA, bee colony itu kan kita belum bisa mengatakan itu solusi yang terbaik ya?? benar gak pemahhaman saya??
Iya. bisa di sebut algoritma metaheuristik saja.
Mungkin lebih tepatnya bukan solusi terbaik, tetapi solusi optimal. Solusi terbaik kadang masih bersifat relatif, artinya terbaik dari yang ada/yang bisa didapat. Kalau pengertiannya seperti itu, ya metode metaheuristik bisa menghasilkan solusi terbaik (solusi terbaik dari alternatif solusi yang ada). tapi kalau optimal, pengertiannya global, artinya terbaik dari semua kemungkinan penyelesaian yang ada di dalam ruang pencarian (search space).
email saya : wongcilik_1@yahoo.co.uk
Salam
oke terimakasih infonya pak 🙂
pak.. metaheuristic itu metode apa algoritma ya??
saya bingung..
secara teknis sebenarnya metode dan algoritma tidak memiliki perbedaan yang jelas dan sering dipakai bergantian.
Akan tetapi menurut pemahaman saya, metode merupakan prosedur yang bersifat umum sedangkan algoritma sering dilekatkan pada suatu prosedur spesifik untuk menyelesaikan permasalahan.
Untuk istilah metaheuristik, saya lebih suka menyebutnya metode, karena metaheuristik ini lebih ke tataran konseptual saja.
Dan metode metaheuristik terdiri dari banyak jenis metode yang lebih spesifik, yang orang sering menyebutnya dengan istilah algoritma, misalnya algoritma genetik, algoritma differential evolution, dll.
Tapi perlu diingat, bahwa pendapat ini bukan satu-satunya. Orang lain bisa saja memiliki pendapat yang berbeda.
Semoga membantu
Salam
boleh mintak sumber buku tentang metaheuristic pak??
pakai buku yang pengarangnya Talbi itu ya pak?
oke.. terima kasih jawabannya..
berarti algoritma adalah salah satu contoh dari metode??
saya menyebut ACO sebagai algoritma optimasi berdasarkan metaheuristic bener tidak kira2?? 🙂
bisa dibilang begitu sih, karena kalau metode, menurut saya tidak harus dipakai untuk menyelesaikan masalah, misalnya metode membaca cepat, tetapi kalau algoritma, selalu dipakai untuk menyelesaikan masalah.
untuk pengantar metaheuristik, buku nya Talbi menurut saya bagus …
mas mau tanya tentang penggunaan tabu search dalam constrained binary quadratic programming dalam pencarian clique parition.
1. itu konsepnya bagaimana?
2. lebih baik menggunakan tabu search atau branch and bound untuk kasus tersebut?
trimakasih banyak
maaf mbak, saya belum pernah menangani permasalahan constrained binary quadratic programming, jai saya tidak paham juga. Kalau tentang konsep tabu search bisa lihat di sini
Salam
trimakasih mas 🙂
maaf mas mau tanya lagi.
kalau pencarian clique partion itu pakai metoda apa ya ?
sejujurnya, saya belum pernah menyelesaikan masalah itu mbak. Tapi rasanya ada algoritma heuristic yang sering dipakai untuk menyelesaikannya. Ini ada artikel yang saya pikir bisa bermanfaat untuk menelusuri metode2 untuk memecahkan permasalahan tersebut
Click to access TCS07.pdf
jadi metode metaheuristik ini untuk menyelesaikan masalah yg lebih kompleks gitu yaa mas??..
klo mau nylesein permasalahan VRP menggunakan ACO gitu brarti harus disisipkan metode nearest neighborhood gitu atau gmn??..
makasiiihh sebelumnyaa..
iya, metode metaheuristik seringkali dipakai untuk menyelesaikan masalah yg sulit diselesaikan menggunakan metode eksak.
VRP sering diselesaikan dengan metaheuristik juga, misalnya pakai ACO.
Tidak harus disisipi NN, tergantung mendekodekan permasalahannya bagaimana … Untuk mengetahui jenis2 pendekodean untuk VRP, bisa baca-baca jurnal ttg VRP …
mendekodekan itu maksudnya membuat variable2 nya gitu kah mas??..
mendekodekan itu memetakan/merepresentasikan permasalahan ke dalam metode optimisasinya, termasuk menentukan variabel-variabelnya …
okeeeeeee makasiiiihh mas..
Halo.. terima kasih atas tulisannya… mau bertanya, keunggulan metode tabu search dibandingkan dengan metode methaheuristik lainnya apa menurut Anda? thx
Maaf gi balas. lama ga buka blog.
Tabu Search relatif mudah diimplementasikan.