Antara optimisasi, heuristik dan metaheuristik

Karena ada beberapa pertanyaan tentang perbedaan antara metode optimisasi, heuristik dan metaheuristik, maka saya tertarik untuk menulis perbedaan tentang ketiganya (atau bisa juga persamaannya :D).

Definisi optimisasi bisa dibaca di postingan saya sebelumnya tentang pengantar optimisasi. Metode optimisasi bisa dibagi menjadi metode eksak (exact method atau analitical method) dan metode pendekatan (approximate method).

Ciri yang paling khas dari exact method adalah bahwa metode ini akan menghasilkan penyelesaian optimal. Bagaimana bisa tahu bahwa hasil yang diperoleh adalah hasil optimal ? Pembuktiannya dilakukan secara analitis menggunakan metode matematis.

Sedangkan metode pendekatan tidak menjamin bahwa hasil penyelesaiannya adalah yang optimal (makanya disebut metode pendekatan). Tetapi, meskipun metode ini tidak menjamin hasil optimal, tetapi umumnya hasil penyelesaiannya cukup baik. Walaupun definisi baik ini juga sulit, karena  bersifat kualitatif. Sehingga seringkali untuk mengukur kualitas baik ini, maka diadakan perbandingan hasil dengan menggunakan metode lain. Suatu metode dikatakan lebih baik jika dia menghasilkan penyelesaian yang lebih bagus daripada metode lainnya.

Metode pendekatan ada bermacam-macam, salah duanya metode heuristik dan metaheuristik. Definisi heuristik dan metaheuristik dapat dilihat di artikel definisi metaheuristik. Metaheuristik pada sebenarnya adalah metode pendekatan yang didasarkan pada metode heuristik. Sehingga tidak heran bahwa metode heuristik sering kali diintegrasikan di dalam metode metaheuristik.

Perbedaan utaman dari metode heuristik dan metaheuristik adalah : metode heuristik bersifat problem dependent sedangkan metode metaheuristik bersifat problem independent. Lalu apakah yang dimaksud dengan problem dependent dan problem independent itu?

Problem dependent artinya bergantung pada permasalahan, jadi metode heuristik itu hanya bisa dipakai untuk jenis permasalahan terntentu. Misalnya, metode nearest neighborhood (NN) termasuk metode heuristik. Metode hanya bisa dipakai pada permasalahan yang mengenal konsep neighborhood/tetangga, misalnya pada Traveling Salesman Problem maupaun Vehicle Routing Problems. Contoh lainnya, COMSOAL (Computer Method for Sequencing Operations for Assembly Lines) hanya dipakai untuk persoalan sequencing assembly line.

Sedangkan problem independent berarti tidak bergantung pada jenis permasalahan. Jadi penerapan metode metaheuristik tidak bergantung pada jenis permasalahan, alias bisa dipakai untuk berbagai jenis permasalahan. Contoh dari metode metaheuristik adalah algoritma genetik (GA), particle swam optimization (PSO), Ant Colony Optimization (ACO), Soccer Games Optimization (SGO) – promo dikit gapapalah ya :D,  dll. Meskipun bisa dipakai untuk berbagai jenis permasalahan, tetapi kemampuan mengadopsi metode tersebut untuk jenis permasalahan tertentu berpengaruh besar terhadap kualitas penyelesaian yang dihasilkan. Oleh karena itulah, seringkali metode metaheuristik akan mengintegrasikan metode heuristik didalam implementasinya. Misalnya, untuk menyelesaikan persoalan TSP, metode algoritma genetik menyisipkan konsep  nearest neighborhood didalam implementasinya.

Demikian sekilas tentang optimisasi, heuristik dan metaheuristik.