Differential Evolution

Pada kasus optimasi, umumnya orang-orang menginginkan suatu teknik optimasi yang memenuhi empat sayarat. Pertama, mampu mendapatkan nilai global optimum tanpa menghiraukan nilai initial dari parameter sistem. Kedua, bisa mencapai konvergensi nilai solusi dengan cukup cepat. Ketiga, membutuhkan kontrol parameter yang sedikit, sehingga akan mudah digunakan. Keempat, bisa mengatasi permasalahan non-differentiable, nonlinear, dan multimodal (Storn dan Price, 1995). Kemudian dibuatlah algoritma Differential Evolution (DE) yang benar-benar handal, tidak hanya simple tetapi juga ampuh dalam berbagai permasalahan. 

DE pertama kali diperkenalkan oleh Storn dan Price (1995) sebagai metode penyelesaian permasalahan optimasi kontinyu yang berdasarkan populasi (population-based) stokastik. DE terbukti efektif dan tangguh dalam menyelesaikan berbagai macam kasus optimasi, tidak hanya kasus kontinyus tetapi akhir-akhir ini juga permasalahan diskret (Kushida, dkk, 2012). Secara sederhana, langkah dari algoritma Differential Evolution ini hanya membutuhkan dua vektor yang dipilih secara random untuk membuat vektor yang ketiga.

<belum selesai>

Cross Entropy

Metode Cross Entropy termasuk teknik yang cukup baru. Awalnya diterapkan untuk simulasi kejadian langka (rare event). Lalu dikembangkan untuk beberapa kasus seperti optimasi kombinatorial, optimasi kontinyu, machine learning dan beberapa kelas masalah lain. Metoda CE termasuk dalam keluarga teknik Monte Carlo yang bisa digunakan untuk menyelesaikan kasus estimasi maupun optimasi. Dalam hal estimasi, CE memberikan cara yang adaptif untuk menemukan distribusi sampling yang optimal untuk beberapa problem yang cukup luas cakupannya. Jika masalah optimasi bisa kita formulasikan sebagai masalah estimasi maka metoda CE menjadi sangat handal dan berlaku umum sebagai algoritma search stokhastik. Pada bab ini, prinsip-prinsip metode Cross Entropy (CE) akan dijelaskan berdasarkan pada [Boer et al., 2005, Rubinstein and Kroese., 2004].

Algoritma Genetika

Genetic algorithm atau algoritma genetika (GA) masuk dalam kelompok Evolutionary Algoritm. Genetic algorithm didasarkan pada prinsip-prinsip genetika dan seleksi alam. Elemen-elemen dasar dari genetika alam adalah: reproduksi, crossover, dan mutasi. Elemen-elemen ini yang dipakai dalam prosedur GA. Algoritma ini banyak dipakai dalam penyelesaian masalah kombinatorial seperti TSP, VRP hingga permasalahan kontrol. GA termasuk pelopor dalam hal Metaheuristik, banyak algoritma yang belakangan ditemukan mengadopsi beberapa langkah dari GA. Dalam evolution-based approach biasanya akan dibangkitkan sejumlah populasi yang dalam masalah optimasi menjadi solusi awal. Dengan prosedur tertentu seperti mutasi, seleksi, reproduksi dan crossover akhirnya didapatkan solusi akhir dari problem optimasi yang dihadapi. Algoritma yang sangat populer dalam hal ini adalah algoritma genetika. Ini termasuk temuan besar dalam bidang optimasi. Dimana suatu algoritma diciptakan dengan meniru mekanisme evolusi dalam perkembangan makhluk hidup. Dalam GA prosedur pencarian hanya didasarkan pada nilai fungsi obyektif, tidak ada pemakaian gradient. Banyak masalah telah berhasil diselesaikan dengan algoritma ini. Sebagai contoh, antara lain crew scheduling untuk airline. Masalah crew scheduling termasuk masalah kombinatorial yang sulit diselesaikan. GA juga diterapkan untuk portfolio selection, Traveling Salesman Problem,optimized Telecommunications Routing, Trip, Traffic and Shipment Routing. Beberapa istilah dipakai dalam algoritma genetika antara lain [Venkataraman, 2002].

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.