Sekilas Tentang Metaheuristics

Setiap hari para insinyur menghadapi problem yang semakin kompleks yang tersebar dalam beberapa area aplikasi seperti dalam operations research, desain sistem mekanik, image processing, problem assignment dan routing komponen. Masalah-masalah yang harus diselesaikan sering kali harus diformulasikan sebagai masalah optimasi. Apalagi kalau problem optimasinya mempunyai konstrain, maka parameter-parameter yang ada harus memenuhi konstrain ini. Banyak sekali permasalahan optimasi dalam kehidupan sehari-hari yang sulit diselesaikan dengan teknik kalkulus atau analitik. Pendekatan metaheuristik, sebagai kelanjutan dari heuristik, muncul karena permasalahan riil yang ada susah diselesaikan dengan teknik yang berdasarkan kalkulus. Kesulitan bisa dari segi waktu komputasi yang lama, atau penyelesaian melalui cara analitik tidak bisa dilakukan. Belakangan ini banyak sekali pendekatan baru yang lahir baik yang masuk dalam evolutionary algorithm atau bioinspired algorithm atau teknik-teknik lain yang berusaha meniru fenomena di kasus lain. Diantaranya adalah algoritma genetika, simulated annealing, tabu search, ant colony, particle swarm optimization dan sebagainya.

Heuristik (heuristics) suatu teknik yang didesain untuk memecahkan masalah dengan sedikit mengabaikan apakah solusinya bisa dibuktikan benar, tetapi biasanya menghasilkan solusi yang bagus, dalam arti optimal mendekati optimal. Heuristik dimaksudkan untuk mendapatkan hasil yang secara komputasi lebih cepat dengan konsekuensi mengurangi kepresisian atau akurasi. Jadi kecepatan penghitungan biasanya lebih baik (dibandingkan optimasi eksak) dengan sedikit mengorbankan akurasi. Walaupun pada kenyataannya solusinya bisa juga mempunyai akurasi yang tinggi. Pendekatan heuristik biasanya sangat spesifik untuk problem tertentu. Sehingga, diperlukan algoritma yang lain untuk problem yang berbeda. Tentu saja ini kurang menguntungkan.

Metaheuristik adalah metoda untuk mencari solusi yang memadukan interaksi antara prosedur pencarian lokal dan strategi yang lebih tinggi untuk menciptakan proses yang mampu keluar dari titik-titik local optima dan melakukan pencarian di ruang solusi untuk menemukan solusi global. Metaheuristik (metaheuristics), dalam definisi aslinya, adalah metoda untuk mencari solusi yang memadukan interaksi antara prosedur pencarian lokal dan strategi yang lebih tinggi untuk menciptakan proses yang mampu keluar dari titik-titik local optima dan melakukan pencarian di ruang solusi untuk menemukan solusi global. Metaheuristik biasanya berupa prosedur umum yang bisa diterapkan untuk berbagai problem. Tentu saja diperlukan berbagai modifikasi agar suatu metoda metaheuristik sesuai dapat menyelesaikan masalah khusus yang dihadapi. Selain itu, dalam metaheuristik ada prosedur yang memanfaatkan satu atau lebih titik-titik tetangga (neighborhood structures) sebagai acuan menuju solusi lain. Di dalam metaheuristik biasanya ada heuristik di dalamnya. Sejalan dengan perkembangannya, metoda ini juga mencakup penggunaan strategi untuk mengatasi suatu pencarian baru dimana pencarian sering terjebak dalam local optima dalam suatu ruang solusi yang kompleks.

Ada dua kelas problem optimasi yaitu problem dengan variabel diskret dan problem dengan variabel kontinyu. Salah satu contoh yang sering ditemui untuk problem diskrit adalah traveling salesman problem: dimana seorang salesman harus mengunjungi sejumlah kota dan dia ingin mencari rute dengan jarak total minimum dimana dia harus mengunjungi setiap kota sekali saja sebelum kembali ke kota asal. Sedangkan contoh problem dengan variabel kontinyu adalah ketika seorang insinyur harus enentukan diameter pipa untuk sistem pemipaan sehingga ongkos pemasangan pipa ini minimum.

Tidak jarang juga kita temui permasalahan dimana nilai variabelnya adalah campuran diskrit dan kontinyu. Misalkan harus diputuskan di lokasi mana saja akan dibangun sejumlah gudang penyimpanan untuk suatu produk atau barang. Untuk tiap gudang harus ditentukan berapa kapasitasnya, sehingga permintaan untuk daerah yang dilayani oleh setiap gudang bisa dipenuhi dan ongkos pembangunan gudang serta distribusi barangnya minimum. Dalam contoh ini keputusan dilokasi mana harus dibangun adalah nilai diskrit, sedang kapasitas gudang adalah nilai kontinyu. Pembedaan ini perlu karena akan menentukan suatu problem sulit diselesaikan atau tidak. Walaupun tidak ada batasan yang cukup jelas bagaimana suatu problem optimasi disebut sulit tetapi pengelompokkan berikut semoga bisa membantu:

1.       Problem optimasi diskrit, dimana tidak ada informasi mengenai algoritma polynomial yang eksak dimana waktu komputasinya proporsional terhadap Nn, N adalah jumlah parameter yang dicari, dan n suatu konstanta integer. Sering juga disebut sebagai non polynomial (NP-hard, dimana tidak ada nilai n sehingga waktu komputasi dibatasi oleh suatu polynomial dengan pangkat n.

2.       Problem optimasi dengan variabel kontinyu, dimana suatu algoritma tidak mengenali dimana posisi nilai global optimum (solusi terbaik) dalam jumlah komputasi yang sudah dilakukan.

Ada karakteristik umum yang biasa dimiliki oleh pendekatan metaheuristik:

1.  Biasanya stokhastik: menggunakan bilangan random yang nilainya stokhastik untuk menentukan keputusan dalam salah satu langkah dalam algoritma. Ini memungkinkan untuk mengatasi permasalahan banyaknya kemungkinan solusi dalam masalah kombinatorial.

2.       mumnya tidak mempunyai masalah dengan penghitungan gradient dari fungsi tujuan.

3.   Biasanya diinspirasi oleh analogi fisik (simulated annealing), biologi (evolutionary algorithms) atau ethology (ant colony, particle swarm).

4.     Mempunyai kelemahan umum: kesulitan mengatur nilai parameter dan komputasi yang lama, namun waktu komputasi ini juga kadang menjadi keunggulan dibanding optimasi eksak.

Kecenderungan yang ada sekarang adalah adanya kombinasi/hybrid antar metoda. Dengan kombinasi ini diharapkan dapat diambil keunggulan dari suatu metoda dan secara simultan menghilangkan kekurangan dari metoda yang lain. Sudah banyak dilakukan hibridisasi antar metoda seperti GA dengan PSO atau Harmony Search dengan PSO.

 





untuk lebih jelasnya mengenai metaheuristik bisa dibaca sendiri di buku handbook of metaheuristics yang bisa di download disini