Algoritma DSA (Differential Search 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 memiliki beberapa variasi cara perhitungan morfogenesis yaitu:
- B-DSA (BIJECTIVE DSA)
- S-DSA (SURJECTIVE DSA)
- E1-DSA (ELITIST DSA jenis pertama)
- E2-DSA (ELITIST DSA jenis kedua)
- Hybrid-DSA
Variasi yang dibahas kali ini adalah variasi S-DSA (SURJECTIVE DSA). Pada saat proses morfogenesis, setiap individu atau superorganisme akan bergerak menuju ke arah superorganisme yang cukup baik.
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.
Sedangkan Grafik fungsi Himmelblau untuk sebaran titik dengan rentang minimal -2 dan maksimal 2 adalah sebagai berikut.
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 superorganisme yang digunakan
Diasumsikan dalam kasus ini, jumlah superorganisme adalah 10
jumlahSuperorganisme = 10;
* Tentukan jumlah maksimal iterasi yang digunakan
Diasumsikan dalam kasus ini, jumlah maksimal iterasi adalah 500 kali
jumlahIterasi = 500;
* 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
jumlahDimensi = 2;
* 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
minPosisi = -2; maksPosisi = 2;
Langkah-langkah penggunaan algoritma ini adalah
* Lakukan proses perhitungan dengan metode DSA (Differential Search Algorithm)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 3)
[posisiTerbaik,nilaiFungsiTerbaik] = SDSA( ...
jumlahSuperorganisme, jumlahIterasi, jumlahDimensi, Lb, Ub);
Memasuki perhitungan pada fungsi SDSA
1. Lakukan inisialisasi individu superorganisme pada posisi acak,
Kemudian hitung nilai fungsi pada posisi tersebut
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini
for i = 1:jumlahSuperorganisme,
posisi(i,:) = Lb + (Ub-Lb).* rand(1,jumlahDimensi);
nilaiFungsi(i) = HitungNilaiFungsi(posisi(i,:));
end
* Gunakan fungsi ini untuk menghitung nilai fungsi dengan rumus:
f(x, y) = (x ^ 2 + y – 11) ^ 2 + (x + y ^ 2 – 7) ^ 2
function z = HitungNilaiFungsi(u) z = (u(1)^2 + u(2) - 11) ^ 2 + (u(1) + u(2)^2 - 7) ^ 2;
2. Catat posisi terbaik dengan nilai fungsi tertinggi sementara
[nilaiFungsiTerbaik,I] = max(nilaiFungsi); posisiTerbaik = posisi(I,:);
3. Lakukan perhitungan sebanyak jumlah iterasi (poin 3a – 3i)
for iterasi = 1:jumlahIterasi, . . .
3a. Tentukan 2 faktor nilai untuk digunakan dalam proses morfogenesis
Nilai default yang digunakan adalah nilai acak antara 0 sampai dengan 0.3
p1=0.3*rand; p2=0.3*rand;
3b. Lakukan proses pembuatan arah tujuan dari masing-masing superorganisme
Penjelasan lebih lanjut tentang fungsi ini dapat dilihat pada skrip dibawah ini
daftarArah = HitungArah(posisi,jumlahSuperorganisme,nilaiFungsi);
* Gunakan fungsi ini untuk menghitung daftar arah tujuan dari masing-masing superorganisme
function daftarArah = HitungArah(posisi,jumlahSuperorganisme,nilaiFungsi)
%S-DSA (SURJECTIVE DSA)
%Superorganisme akan bergerak menuju ke arah superorganisme yang cukup baik
%Lakukan pengurutan superorganisme berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
%Kemudian cari indeks acak dari perkalian antara nilai acak dengan jumlah superorganisme
%Sehingga indeks yang lebih baik (lebih rendah) akan lebih memiliki peluang untuk terpilih
idx=ones(jumlahSuperorganisme,1);
[~, nilaiFungsiTerurut]=sort(nilaiFungsi, 'descend');
for i=1:jumlahSuperorganisme,
idx(i)=nilaiFungsiTerurut(randi(ceil(rand*jumlahSuperorganisme),1));
end;
daftarArah=posisi(idx,:);
return
3c. Lakukan proses pemetaan posisi dimensi yang digunakan
Posisi pada dimensi acak tertentu akan bernilai 1,
dan nantinya pemetaan ini akan digunakan dalam proses morfogenesis
Penjelasan lebih lanjut tentang fungsi ini dapat dilihat pada skrip dibawah ini
map = HitungMap(jumlahSuperorganisme,jumlahDimensi,p1,p2);
* Gunakan fungsi ini untuk menghitung pemetaan posisi dimensi yang digunakan
Pemetaan ini dilakukan untuk mencari individu manakah yang termasuk individu aktif / pasif
Individu yang aktif nantinya akan mengalami mutasi,
dan kemudian dapat dicari posisi superorganisme yang baru
function map=HitungMap(jumlahSuperorganisme,jumlahDimensi,p1,p2)
map=zeros(jumlahSuperorganisme,jumlahDimensi);
if rand
3d. Tentukan faktor skala untuk digunakan dalam proses morfogenesis
faktor skala dapat dihitung menggunakan metode Brownian, invers distribusi gamma, atau distribusi Levy
Dalam kasus ini akan digunakan cara distribusi Levy
faktorSkala=1./gamrnd(1,0.5); % pseudo-stable walk
3e. Lakukan proees morfogenesis pada masing-masing superorganisme untuk mendapatkan posisi yang baru
posisi baru = pop + (map * F) * (selisih arah dan posisi superorganisme)
posisiBaru = posisi + (faktorSkala.*map) .* (daftarArah-posisi);
3f. Jika posisi baru ternyata diluar batas yang diperbolehkan,
maka kembalikan posisinya agar masuk dalam batas tersebut
Kemudian hitung nilai fungsi pada posisi yang baru
for i=1:jumlahSuperorganisme
tmpPosisi=posisiBaru(i,:);
I=tmpPosisiUb;
tmpPosisi(J)=Ub(J);
posisiBaru(i,:)=tmpPosisi;
nilaiFungsiBaru(i) = HitungNilaiFungsi(posisiBaru(i,:));
end
3g. Bandingkan nilai fungsi antara posisi baru dengan posisi superorganisme yang ada
Cari indeks dimana posisi baru memiliki nilai fungsi lebih tinggi dari nilai fungsi posisi superorganisme
Ganti semua posisi dan nilai fungsi dari posisi superorganisme pada indeks tersebut sesuai dengan posisi dan nilai fungsi pada posisi baru
idxLebihBaik = nilaiFungsiBaru>nilaiFungsi;
nilaiFungsi(idxLebihBaik) = nilaiFungsiBaru(idxLebihBaik);
posisi(idxLebihBaik,:) = posisiBaru(idxLebihBaik,:);
3h. Hitung nilai fungsi terbaik yang terdapat pada posisi superorganisme yang baru
[nilaiFungsiSuperorganismeTerbaik,idxTerbaik]=max(nilaiFungsi);
3i. Jika nilai fungsi tersebut ternyata lebih baik dari nilai fungsi terbaik secara umum,
maka ambil posisi yang baru sebagai posisi yang terbaik
if nilaiFungsiSuperorganismeTerbaik > nilaiFungsiTerbaik,
posisiTerbaik = posisi(idxTerbaik,:);
nilaiFungsiTerbaik = nilaiFungsiSuperorganismeTerbaik;
end
Hasil akhir adalah:
Algoritma DSA (Differential Search Algorithm): S-DSA (SURJECTIVE DSA)
Contoh: Mencari posisi dengan pengembalian nilai fungsi maksimal
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
Jumlah superorganisme = 10
Jumlah maksimal iterasi = 500
Jumlah dimensi = 2
Batas minimal posisi = -2
Batas maksimal posisi = 2
Iterasi: 5, Posisi terbaik: -0.346 -0.86271, Nilai Fungsi terbaik: 181.4808
Iterasi: 7, Posisi terbaik: -0.28255 -0.99032, Nilai Fungsi terbaik: 181.5726
Iterasi: 13, Posisi terbaik: -0.30135 -0.86271, Nilai Fungsi terbaik: 181.5729
Iterasi: 16, Posisi terbaik: -0.28846 -0.87009, Nilai Fungsi terbaik: 181.5898
Iterasi: 19, Posisi terbaik: -0.27447 -0.89068, Nilai Fungsi terbaik: 181.6078
Iterasi: 24, Posisi terbaik: -0.26463 -0.94819, Nilai Fungsi terbaik: 181.6111
Iterasi: 27, Posisi terbaik: -0.26463 -0.92431, Nilai Fungsi terbaik: 181.6157
Iterasi: 32, Posisi terbaik: -0.27384 -0.93069, Nilai Fungsi terbaik: 181.6157
Iterasi: 38, Posisi terbaik: -0.26888 -0.92479, Nilai Fungsi terbaik: 181.6164
Iterasi: 46, Posisi terbaik: -0.271 -0.92479, Nilai Fungsi terbaik: 181.6165
Iterasi: 49, Posisi terbaik: -0.27108 -0.92431, Nilai Fungsi terbaik: 181.6165
Iterasi: 51, Posisi terbaik: -0.27041 -0.92431, Nilai Fungsi terbaik: 181.6165
Iterasi: 57, Posisi terbaik: -0.27127 -0.92392, Nilai Fungsi terbaik: 181.6165
Iterasi: 59, Posisi terbaik: -0.27063 -0.92311, Nilai Fungsi terbaik: 181.6165
Iterasi: 67, Posisi terbaik: -0.27068 -0.92311, Nilai Fungsi terbaik: 181.6165
Iterasi: 68, Posisi terbaik: -0.27084 -0.92311, Nilai Fungsi terbaik: 181.6165
Iterasi: 76, Posisi terbaik: -0.27084 -0.923, Nilai Fungsi terbaik: 181.6165
Iterasi: 80, Posisi terbaik: -0.27082 -0.92306, Nilai Fungsi terbaik: 181.6165
Iterasi: 81, Posisi terbaik: -0.27086 -0.92306, Nilai Fungsi terbaik: 181.6165
Iterasi: 84, Posisi terbaik: -0.27086 -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 92, Posisi terbaik: -0.27084 -0.92303, Nilai Fungsi terbaik: 181.6165
Iterasi: 97, Posisi terbaik: -0.27084 -0.92303, Nilai Fungsi terbaik: 181.6165
Iterasi: 99, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 101, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 113, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 114, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 115, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 121, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 123, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 138, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 143, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165
Posisi Terbaik: -0.27084 -0.92304
Nilai Fungsi Terbaik =181.6165
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.