Algoritma DA (Dragonfly Algorithm)


Algoritma DA (Dragonfly Algorithm) adalah salah satu algoritma optimasi yang dapat digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mengenai pencarian posisi dengan pengembalian nilai fungsi maksimal.
Algoritma ini meniru tingkah laku dari hewan capung dalam mencari sumber makanan. Sama seperti algoritma optimasi lain yang sudah dibahas sebelumnya, algoritma ini memiliki 2 fase, yaitu Fase Eksplorasi dan Fase Eksploitasi. Dalam fase eksplorasi capung akan terbang secara berkelompok, dan masing-masing kelompok akan terbang menuju arah yang berbeda. Setelah menemukan calon sumber makanan yang cukup baik, maka setiap kelompok capung akan terbang searah menuju sumber makanan tersebut.
Perlu diketahui bahwa terdapat 5 faktor yang digunakan dalam algoritma ini, yaitu:

  • Faktor Pemisahan
  • Faktor yang menentukan seekor capung akan berpisah dari kelompoknya

  • Faktor Penggabungan
  • Faktor yang menentukan seekor capung bergabung dengan kelompok baru

  • Faktor Penyesuaian
  • Faktor yang menentukan seekor capung menyesuaikan arah terbang pada kelompok yang baru

  • Faktor Sumber Makanan
  • Faktor yang menentukan capung dalam kelompok secara bersama-sama menuju sumber makanan

  • Faktor Predator
  • Faktor yang menentukan capung dalam kelompok secara bersama-sama berpencar untuk menghindari predator



Diasumsikan ada sebaran titik 2 dimensi antara -2 sampai dengan 2
Fungsi yang diketahui adalah fungsi Himmelblau, dengan rumus f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2
Tentukan posisi dimana fungsi tersebut mengembalikan nilai maksimal



Fungsi Himmelblau adalah salah satu fungsi yang dapat digunakan untuk mengoptimasi suatu permasalahan. Fungsi ini memiliki sebuah nilai maksimum pada x = -0.270845, and y = -0.923039 dengan nilai fungsi sebesar f(x,y) = 181.617, dengan asumsi bahwa rentang minimal dan maksimal dari sebaran titik adalah -2 sampai dengan 2

Grafik fungsi Himmelblau yang normal, atau untuk sebaran titik tak terbatas adalah sebagai berikut.
Grafik Himmelblau

Sedangkan Grafik fungsi Himmelblau untuk sebaran titik dengan rentang minimal -2 dan maksimal 2 adalah sebagai berikut.
Grafik Himmelblau -2sd2
Dapat dilihat bahwa pada gambar tersebut, didapatkan area dengan titik tertinggi (berwarna merah) berada pada area x = -0, and y = -1, dimana titik tersebut mengembalikan nilai fungsi tertinggi. Oleh sebab itu digunakan algoritma ini untuk mencari titik di area berwarna merah tersebut.



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah capung / dragonfly yang digunakan
Nilai yang direkomendasikan adalah 10 sampai dengan 40
Diasumsikan dalam kasus ini, bat yang digunakan adalah 15 ekor

* Tentukan jumlah maksimal iterasi yang digunakan
Diasumsikan dalam kasus ini, jumlah maksimal iterasi adalah 500 kali

* Tentukan jumlah dimensi yang digunakan
Diasumsikan dalam kasus ini, jumlah dimensi adalah 2 karena posisi bunga hanya ditentukan dari 2 sumbu yaitu sumbu x dan y

* Tentukan posisi minimal dan maksimal dari fungsi yang akan dihitung
Jika tidak ada batasan posisi, tentu saja posisi yang mendekati tak terhingga akan terpilih karena akan mengembalikan nilai fungsi yang sangat besar
Diasumsikan dalam kasus ini, posisi minimal adalah -2, dan posisi maksimal adalah +2

* Tentukan matriks batas bawah dan batas atas posisi pada masing-masing dimensi yang sudah ditentukan sebelumnya
Matriks ini akan digunakan untuk mengecek apakah posisi serangga yang baru masih berada dalam batas yang diperbolehkan


Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses perhitungan dengan metode DA (Dragonfly Algorithm)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 3)

Memasuki perhitungan pada fungsi DA

1. Lakukan inisialisasi capung pada posisi acak,
Kemudian beri nilai awal fitness nya dengan angka 0

2. Lakukan inisialisasi delta posisi pada posisi acak,
Delta posisi akan digunakan untuk menentukan posisi capung yang baru pada setiap perulangan

3. Lakukan perhitungan pada masing-masing data baru (poin 3a – 3g)

3a. Tentukan radius dari masing-masing capung
Nilai radius akan semakin naik seiring dengan banyaknya iterasi yang sudah dilakukan

3b. Tentukan bobot yang akan digunakan dalam perhitungan delta posisi
Berbeda dengan nilai radius, nilai bobot ini akan semakin turun seiring dengan banyaknya iterasi yang sudah dilakukan

3c. Tentukan nilai bobot iterasi yang akan digunakan pada perhitungan dibawah ini
Nilai bobot ini juga akan semakin turun seiring dengan banyaknya iterasi yang sudah dilakukan
dengan nilai yang paling rendah adalah 0

3d. Tentukan nilai acak untuk bobot pemisahan, penyesuaian, penggabungan, makanan, dan Predator
Kelima bobot ini digunakan untuk menghitung nilai sebenarnya untuk nilai pemisahan, penyesuaian, penggabungan, makanan, dan Predator
dan kemudian nilai ini nantinya digunakan untuk menghitung nilai delta posisi yang baru

* Lakukan perhitungan untuk mendapatkan fitness sumber makanan terbaik dan predator terburuk (poin 3e)

3e. Lakukan perhitungan sebanyak jumlah capung yang ada (poin 3e1 -3e3)

3e1. Hitung nilai fitness pada posisi capung yang ada
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

* Gunakan fungsi ini untuk menghitung fitness dengan rumus:
f(x, y) = (x ^ 2 + y – 11) ^ 2 + (x + y ^ 2 – 7) ^ 2

3e2. Jika nilai fitness lebih baik dari nilai fitness sumber makanan
maka ambil posisi capung tersebut sebagai posisi sumber makanan terbaik

3e3. Jika nilai fitness lebih buruk dari nilai fitness predator
maka ambil posisi capung tersebut sebagai posisi predator terburuk

* Lakukan perhitungan untuk mendapatkan posisi capung yang baru (poin 3f)

3f. Lakukan perhitungan sebanyak jumlah capung yang ada (poin 3f1 – 3f11)

* Lakukan perhitungan berikut untuk mendapatkan solusi tetangga dari capung terpilih (poin 3f1)

3f1. Lakukan perhitungan pada masing-masing capung selain capung yang sedang dihitung

3f1a. Hitung jarak antara kedua capung tersebut
Metode yang digunakan adalah metode Euclidean
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

* Gunakan fungsi ini untuk menghitung jarak Euclidean antara 2 data

3f1b. Jika capung kedua masih berada di dalam radius capung pertama,
maka tambahkan capung kedua sebagai solusi tetangga dari capung pertama

* Lakukan perhitungan berikut untuk mendapatkan nilai pemisahan capung tersebut (poin 3f2)

3f2. Lakukan perhitungan berikut apabila terdapat solusi tetangga sebanyak lebih dari 1

3f2a. Lakukan perhitungan pada masing-masing solusi tetangga yang ada
Hitung selisih dari masing-masing posisi solusi tetanggan dan posisi capung yang ada
Kemudian kalikan dengan angka -1 sebagai jawaban akhir

3f2b. Jika solusi tetangga tidak lebih dari 1, maka nilai pemisahan adalah 0

* Lakukan perhitungan berikut untuk mendapatkan nilai penggabungan capung tersebut (poin 3f3a – 3f3b)

3f3a. Jika terdapat solusi tetangga sebanyak lebih dari 1,
maka nilai sementara adalah semua jumlah posisi solusi tetangga dibagi dengan banyaknya solusi tetangga yang ada
Jika tidak terdapat solusi tetangga lebih dari 1,
maka nilai sementara adalah menggunakan nilai posisi capung yang sedang terpilih

3f3b. Nilai penggabungan akhir adalah nilai sementara dikurangi dengan posisi capung yang sedang terpilih

* Lakukan perhitungan berikut untuk mendapatkan nilai penyesuaian capung tersebut (poin 3f4)

3f4. Jika terdapat solusi tetangga sebanyak lebih dari 1,
maka nilai penyesuaian adalah semua jumlah delta solusi tetangga dibagi dengan banyaknya solusi tetangga yang ada
Jika tidak terdapat solusi tetangga lebih dari 1,
maka nilai penyesuaian adalah menggunakan nilai delta posisi pada perulangan sebelumnya

* Lakukan perhitungan berikut untuk mendapatkan nilai sumber makanan (poin 3f5a – 3f5b)

3f5a. Hitung jarak menuju sumber makanan
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya

3f5b. Jika posisi sumber makanan tersebut masih berada dalam radius capung,
maka nilai sumber makanan adalah posisi sumber makanan tersebut dikurangi dengan posisi capung yang sedang terpilih
Selain itu maka nilai sumber makanan adalah 0

* Lakukan perhitungan berikut untuk mendapatkan nilai predator (poin 3f6a – 3f6b)

3f6a. Hitung jarak menuju predator yang ada
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya

3f6b. Jika posisi predator tersebut masih berada dalam radius capung,
maka nilai predator adalah posisi predator tersebut ditambah dengan posisi capung yang sedang terpilih
Selain itu maka nilai predator adalah 0

3f7. Lakukan perhitungan sebanyak jumlah dimensi yang ada
jika posisi capung berada diluar batas yang diperbolehkan,
maka kembalikan posisinya agar masuk dalam batas tersebut
dan nilai delta posisi diisi dengan angka acak antara 0 sampai dengan 1

3f8. Tentukan nilai maksimal delta untuk digunakan dalam perhitungan delta posisi
Diasumsikan dalam kasus ini, nilai maksimal delta adalah 10 persen dari selisih batas atas dan batas bawah rentang nilai yang ada

* Lakukan perhitungan berikut untuk memperoleh nilai posisi capung yang baru (poin 3f9 – 3f10)

3f9. Lakukan perhitungan dibawah ini jika jarak menuju sumber makanan berada diluar radius capung yang sedang terpilih (poin 3f9a – 3f9b)

3f9a. Lakukan perhitungan berikut apabila terdapat solusi tetangga sebanyak lebih dari 1 (poin 3f9a1)

3f9a1. Lakukan perhitungan pada masing-masing dimensi posisi yang ada (poin 3f9a1a – 3f9a1c)

3f9a1a. Hitung nilai delta posisi yang baru
Perhitungan nilai delta tidak menggunakan nilai sumber makanan dan nilai predator
karena jarak menuju sumber makanan berada di luar radius capung

3f9a1b. Jika nilai delta posisi ternyata diluar batas yang diperbolehkan,
maka kembalikan posisinya agar masuk dalam batas tersebut

3f9a1c. Posisi capung yang baru adalah posisi yang lama ditambah dengan nilai delta posisi yang sudah ditemukan sebelumnya

3f9b. Jika solusi tetangga tidak lebih dari 1,
maka nilai posisi capung yang baru dihitung dengan menggunakan menggunakan fungsi Levy
dan nilai delta posisi akan dikembalikan menjadi 0
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

* Gunakan fungsi ini untuk menghitung jarak terbang serangga
Rumus yang digunakan adalah:
x_i ^ {t+1} = x_i ^ t + L(x_i ^ t-gbest)

3f10. Lakukan perhitungan dibawah ini jika jarak menuju sumber makanan masih berada di radius capung yang sedang terpilih (poin 3f10a)

3f10a. Lakukan perhitungan pada masing-masing dimensi posisi yang ada (poin 3f10a1 – 3f10a3)

3f10a1. Hitung nilai delta posisi yang baru
Perhitungan nilai delta menggunakan semua nilai yang sudah dihitung sebelumnya

3f10a2. Jika nilai delta posisi ternyata diluar batas yang diperbolehkan,
maka kembalikan posisinya agar masuk dalam batas tersebut

3f10a3. Posisi capung yang baru adalah posisi yang lama ditambah dengan nilai delta posisi yang sudah ditemukan sebelumnya

3f11. Lakukan pengecekan apakah posisi capung yang baru masih berada dalam batas yang diperbolehkan
Jika posisi yang baru ternyata diluar batas yang diperbolehkan,
maka kembalikan posisinya agar masuk dalam batas tersebut

3g. Ambil posisi dan nilai fitness sumber makanan sebagai posisi dan nilai fitness terbaik


Hasil akhir adalah:


Contoh modul / source code menggunakan Matlab dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *