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 kontinu, 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  adalah fungsi fitness yang harus diminimalkan (perhatikan bahwa maksimalisasi dapat dilakukan dengan mempertimbangkan fungsi ). 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  tidak diketahui. Adapun tujuan optimasi yang dilakukan adalah menemukan solusi  sedemikan sehingga  untuk semua  dalam ruang pencarian, yang berarti  adalah minimum global.

Misal  menyatakan solusi kandidat (agen) dalam populasi. Maka algoritma dasar DE dapat dijelaskan sebagai berikut:

 Pilih parameter , , dan .
 NP: ukuran populasi, yaitu jumlah agen dalam satu populasi atau "induk" (parents).
 CR: probabilitas persilangan (crossover).
 F: bobot diferensial.
 Pengaturan yang umum digunakan adalah , , dan .
 Kinerja optimasi sangat dipengaruhi oleh pemilihan parameter-parameter ini.
 Inisialisasi semua agen  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  dalam populasi:
 Pilih tiga agen , dan  dari populasi secara acak, agen-agen ini harus merupakan agen yang berbeda dan juga harus berbeda dari agen  ( disebut sebagai "basis" vektor).
 Pilih sebuah indeks acak  yang  merupakan dimensi dari masalah yang sedang dioptimasi
 Hitung potensi posisi baru dari agen,  sebagaimana berikut:
 Untuk setiap , pilih sebuah angka acak dengan distribusi seragam 
 Jika  atau  maka tetapkan . Jika tidak, tetapkan  (Indeks  selalu diganti untuk menjamin perbedaan minimal).
 Jika maka ganti agen  dalam populasi dengan solusi kandidat  (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 
jmpl|Lanskap kinerja yang menunjukkan performa agregat DE dasar pada permasalahan uji Sphere dan Rosenbrock ketika parameter  dan  berbeda, dan  =0,9.
Pemilihan parameter DE ,  Dan  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:  . Di Sini,  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  . Jika  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