Deskripsi
Optimasi
Optimasi adalah proses mencari solusi optimal (minimum atau maksimum) dengan memperhatikan batasan yang ada. Ada dua kategori utama masalah optimasi: optimasi tanpa konstrain(unconstrained optimization) dan optimasi dengan konstrain (constrained optimization). Optimasi dengan konstrain secara umum lebih sulit diselesaikan.
Kebanyakan masalah optimasi adalah masuk kategori kedua: optimasi dengan konstrain.
Optimasi menjadi penting di dunia modern dan makin penting. Ada dua pendekatan: optimasi eksak dan optimasi heuristik.
Banyak sekali permasalahan optimasi dalam kehidupan sehari-hari yang sulit diselesaikan dengan teknik kalkulus atau eksak/analitik.
Pendekatan metaheuristik, sebagai kelanjutan dari heuristik, muncul karena permasalahan riil yang ada tidak mudah diselesaikan dengan teknik yang berdasarkan kalkulus atau pendekatan eksak.
Kesulitan bisa dari segi waktu komputasi yang lama, atau penyelesaian melalui cara analitik tidak bisa dilakukan.
Heuristik dan Metaheuristik
Heuristik (heuristics) suatu teknik pendekatan atau coba-coba 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.
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 menentukan diameter pipa untuk sistem pemipaan sehingga ongkos pemasangan pipa ini minimum.
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. Umumnya 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 namun waktu komputasi 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.
