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.^[1]

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.^[2][3][4] 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.^[5][6][7][8] Survei mengenai aspek penelitian multi-faset DE dapat ditemukan dalam beberapa jurnal artikel.^[9][10]

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 ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ adalah fungsi fitness yang harus diminimalkan (perhatikan bahwa maksimalisasi dapat dilakukan dengan mempertimbangkan fungsi ${\displaystyle 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 ${\displaystyle f}$ tidak diketahui. Adapun tujuan optimasi yang dilakukan adalah menemukan solusi ${\displaystyle \mathbf {m} }$ sedemikan sehingga ${\displaystyle f(\mathbf {m} )\leq f(\mathbf {p} )}$ untuk semua ${\displaystyle \mathbf {p} }$ dalam ruang pencarian, yang berarti ${\displaystyle \mathbf {m} }$ adalah minimum global.

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

• Pilih parameter ${\displaystyle {\text{NP}}\geq 4}$, ${\displaystyle {\text{CR}}\in [0,1]}$, dan ${\displaystyle 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 ${\displaystyle NP=10n}$, ${\displaystyle CR=0.9}$, dan ${\displaystyle F=0.8}$.
  • Kinerja optimasi sangat dipengaruhi oleh pemilihan parameter-parameter ini.
• Inisialisasi semua agen ${\displaystyle \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 ${\displaystyle \mathbf {x} }$ dalam populasi:
    • Pilih tiga agen ${\displaystyle \mathbf {a} ,\mathbf {b} }$, dan ${\displaystyle \mathbf {c} }$ dari populasi secara acak, agen-agen ini harus merupakan agen yang berbeda dan juga harus berbeda dari agen ${\displaystyle \mathbf {x} }$ (${\displaystyle \mathbf {a} }$ disebut sebagai "basis" vektor).
    • Pilih sebuah indeks acak ${\displaystyle R\in \{1,\ldots ,n\}}$ yang ${\displaystyle n}$ merupakan dimensi dari masalah yang sedang dioptimasi
    • Hitung potensi posisi baru dari agen, ${\displaystyle \mathbf {y} =[y_{1},\ldots ,y_{n}]}$ sebagaimana berikut:
      • Untuk setiap ${\displaystyle i\in \{1,\ldots ,n\}}$, pilih sebuah angka acak dengan distribusi seragam ${\displaystyle r_{i}\sim U(0,1)}$
      • Jika ${\displaystyle r_{i}<CR}$ atau ${\displaystyle i=R}$ maka tetapkan ${\displaystyle y_{i}=a_{i}+F\times (b_{i}-c_{i})}$. Jika tidak, tetapkan ${\displaystyle y_{i}=x_{i}}$ (Indeks ${\displaystyle R}$ selalu diganti untuk menjamin perbedaan minimal).
    • Jika${\displaystyle f(\mathbf {y} )\leq f(\mathbf {x} )}$ maka ganti agen ${\displaystyle \mathbf {x} }$ dalam populasi dengan solusi kandidat ${\displaystyle \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 ${\displaystyle {\text{NP}}}$, ${\displaystyle {\text{CR}}}$ Dan ${\displaystyle 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.^[4][5] dan Liu dan Lampinen.^[11] Analisis konvergensi matematis mengenai pemilihan parameter dilakukan oleh Zaharie.^[12]

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: ${\displaystyle f{\tilde {(}}x)=f(x)+\rho \times \mathrm {CV} (x)}$ . Di Sini, ${\displaystyle \mathrm {CV} (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 ${\displaystyle \rho }$ . Jika ${\displaystyle \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.^[13] 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

Artikel ini tidak memiliki konten kategori. Bantulah dengan menambah kategori yang sesuai sehingga artikel ini terkategori dengan artikel lain yang sejenis.