Evolusi diferensial

**Evolusi diferensial** (bahasa Inggris: *Differential evolution* atau disingkat **DE**) adalah algoritma evolusioner yang digunakan untuk mengoptimalkan suatu masalah dengan cara berulang kali mencoba memperbaiki solusi kandidat  berdasarkan suatu ukuran kualitas tertentu. Metode semacam ini umumnya dikenal sebagai metaheuristik, karena hanya membuat sedikit atau bahkan tidak ada asumsi tentang masalah yang dioptimalkan dan mampu menjelajahi ruang solusi kandidat yang sangat luas. Namun, algoritma metaheuristik seperti DE tidak menjamin solusi optimal akan ditemukan.

DE digunakan untuk fungsi multidimensi bernilai riil, tanpa memanfaatkan gradien dari masalah yang sedang dioptimalkan. Hal ini berarti DE tidak mensyaratkan masalah optimasi yang dapat didiferensiasikan, sebagaimana metode optimasi klasik, seperti penurunan gradien dan metode kuasi-Newton. Oleh karena itu, DE juga dapat digunakan pada masalah optimasi yang bahkan tidak bersifat , bising (*noisy*), berubah seiring waktu, dan lain sebagainya.

DE mengoptimalkan suatu masalah dengan mempertahankan populasi solusi kandidat, lalu menciptakan solusi kandidat baru dengan menggabungkan solusi yang sudah ada menggunakan rumus. Kemudian, DE hanya mempertahankan solusi kandidat mana pun yang memiliki skor atau *fitness* terbaik. Dengan demikian, masalah optimasi diperlakukan sebagai sebuah kotak hitam (*black box*) yang hanya mengembalikan ukuran kualitas suatu solusi kandidat sehingga gradien tidak diperlukan.

## Sejarah
Storn dan Price memperkenalkan Evolusi diferensial pada tahun 1995. Sejumlah buku telah diterbitkan mengenai aspek teoretis dan praktis penggunaan DE, termasuk dalam komputasi paralel, optimasi multiobjektif, dan optimasi dengan kendala. Selain itu, buku-buku tersebut juga memuat tinjauan berbagai aplikasinya. Survei mengenai aspek penelitian multi-faset DE dapat ditemukan dalam beberapa jurnal artikel.

## Algoritma
Varian dasar algoritma DE bekerja dalam bentuk populasi solusi kandidat yang disebut **agen**. Agen-agen ini kemudian digerakkan di dalam ruang pencarian dengan menggunakan rumus matematika sederhana untuk mengombinasikan posisi agen-agen lain yang ada dalam populasi. Jika posisi baru suatu agen menghasilkan perbaikan, maka posisi tersebut diterima dan menjadi bagian dari populasi. Jika tidak, posisi baru tersebut akan diabaikan. Proses ini diulangi terus menerus, dengan harapan bahwa solusi yang pada akhirnya ditemukan adalah solusi yang memuaskan meskipun tidak terjamin.

Secara formal, misal f: \mathbb{R}^n \to \mathbb{R} adalah fungsi *fitness* yang harus diminimalkan (perhatikan bahwa maksimalisasi dapat dilakukan dengan mempertimbangkan fungsi h := -f). Fungsi ini menerima sebuah solusi kandidat sebagai argumen dalam bentuk vektor bilangan riil dan juga mengembalikan sebuah bilangan riil sebagai keluaran yang menyatakan nilai *fitness* dari solusi kandidat tersebut. Gradien dari f tidak diketahui. Adapun tujuan optimasi yang dilakukan adalah menemukan solusi \mathbf{m} sedemikan sehingga f(\mathbf{m}) \leq f(\mathbf{p}) untuk semua \mathbf{p} dalam ruang pencarian, yang berarti \mathbf{m} adalah minimum global.

Misal \mathbf{x} \in \mathbb{R}^n menyatakan solusi kandidat (agen) dalam populasi. Maka algoritma dasar DE dapat dijelaskan sebagai berikut:

* Pilih parameter \text{NP} \geq 4, \text{CR} \in [0,1], dan F \in [0,2].
** **NP**: ukuran populasi, yaitu jumlah agen dalam satu populasi atau "induk" (*parents*).
** **CR**: probabilitas persilangan (*crossover*).
** ***F***: bobot diferensial.
** Pengaturan yang umum digunakan adalah NP = 10n, CR = 0.9, dan F = 0.8.
** Kinerja optimasi sangat dipengaruhi oleh pemilihan parameter-parameter ini.
* Inisialisasi semua agen \mathbf{x} dengan posisi acak dalam ruang pencarian.
* Ulangi langkah-langkah berikut hingga kriteria penghentian (*termination criterion)* terpenuhi (misalnya jumlah iterasi tercapai atau nilai *fitness* memadai):
** Untuk setiap agen \mathbf{x} dalam populasi:
*** Pilih tiga agen \mathbf{a},\mathbf{b}, dan \mathbf{c} dari populasi secara acak, agen-agen ini harus merupakan agen yang berbeda dan juga harus berbeda dari agen \mathbf{x} (\mathbf{a} disebut sebagai "basis" vektor).
*** Pilih sebuah indeks acak R \in \{1, \ldots, n\} yang n merupakan dimensi dari masalah yang sedang dioptimasi
*** Hitung potensi posisi baru dari agen, \mathbf{y} = [y_1, \ldots, y_n] sebagaimana berikut:
**** Untuk setiap i \in \{1,\ldots,n\}, pilih sebuah angka acak dengan distribusi seragam r_i \sim U(0,1)
**** Jika r_i  atau i = R maka tetapkan y_i = a_i + F \times (b_i-c_i). Jika tidak, tetapkan y_i = x_i (Indeks R selalu diganti untuk menjamin perbedaan minimal).
*** Jikaf(\mathbf{y}) \leq f(\mathbf{x}) maka ganti agen \mathbf{x} dalam populasi dengan solusi kandidat \mathbf{y} (yang sama atau lebih baik.
* Setelah proses selesai, pilih agen dalam populasi dengan nilai *fitness* terbaik, dan kembalikan sebagai solusi kandidat terbaik yang ditemukan.

## Pemilihan parameter

Pemilihan parameter DE \text{NP}, \text{CR} Dan F dapat berdampak besar pada kinerja optimasi. Oleh karena itu, pemilihan parameter DE yang menghasilkan kinerja baik telah menjadi subjek banyak penelitian. Aturan praktis untuk pemilihan parameter dirancang oleh Storn dkk. dan Liu dan Lampinen.  Analisis konvergensi matematis mengenai pemilihan parameter dilakukan oleh Zaharie.

## Penanganan kendala
Evolusi diferensial juga dapat digunakan untuk optimasi dengan kendala. Salah satu metode yang umum adalah dengan memodifikasi fungsi target agar mencakup penalti atas setiap pelanggaran kendala, yang dinyatakan sebagai: f\tilde(x) = f(x) + \rho \times \mathrm(x) . Di Sini, \mathrm(x) merepresentasikan pelanggaran kendala, yang dapat berupa penalti L1 (besar pelanggaran secara langsung) atau penalti L2 (kuadrat dari besar pelanggaran).

Namun, metode ini memiliki beberapa kekurangan. Salah satu tantangan yang signifikan adalah pemilihan koefisien penalti yang tepat \rho . Jika \rho diatur terlalu rendah, penerapan batasan mungkin tidak efektif. Sebaliknya, jika terlalu tinggi, proses konvergensi dapat sangat melambat atau bahkan terhenti. Terlepas dari tantangan-tantangan ini, pendekatan ini tetap banyak digunakan karena kesederhanaannya dan karena tidak memerlukan perubahan pada algoritma evolusi diferensial itu sendiri.

Terdapat strategi alternatif, seperti proyeksi ke himpunan feasible (*feasible set*) atau reduksi dimensi, yang dapat digunakan pada kasus dengan kendala berbentuk *box* atau kendala linear. Namun, dalam konteks kendala nonlinier secara umum, metode yang paling andal biasanya melibatkan fungsi penalti.

## Varian
Varian algoritma DE terus dikembangkan dalam upaya untuk meningkatkan kinerja optimasi. Arah pengembangan DE dapat diuraikan sebagai berikut:

* Skema baru untuk melakukan persilangan dan mutasi agen
* Berbagai strategi untuk penanganan kendala
* Strategi adaptif yang secara dinamis menyesuaikan ukuran populasi, parameter F dan CR
* Algoritma khusus untuk optimasi skala besar
* Algoritma multi-objektif dan banyak-objektif
* Teknik untuk menangani variabel biner/integer

## Lihat juga

* Algoritma koloni lebah buatan
* CMA-ES
* Strategi evolusi
* Algoritma genetika

## Referensi