Algoritma CA (Cultural 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.
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 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;
* Tentukan ukuran populasi yang digunakan
Diasumsikan dalam kasus ini, ukuran populasi adalah 50
ukuranPopulasi = 50;
* Tentukan probabilitas penerimaan culture ke dalam populasi
Diasumsikan dalam kasus ini, probabilitas penerimaan culture adalah 0.35
Kemudian hitung ukuran populasi terpilih dengan rumus:
nAccept=round(pAccept*nPop);
probabilitasPenerimaanCulture = 0.35; ukuranPopulasiTerpilih=round(probabilitasPenerimaanCulture*ukuranPopulasi);
* Tentukan alpha
Nantinya nilai ini secara tidak langsung digunakan untuk menghitung posisi baru dalam setiap iterasi
Diasumsikan dalam kasus ini, nilai alpha adalah 0.3
alpha = 0.3;
Langkah-langkah penggunaan algoritma ini adalah
* Lakukan proses perhitungan dengan metode CA (Cultural Algorithm)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 2)
[posisiTerbaik,nilaiFungsiTerbaik] = CA( ...
jumlahIterasi, jumlahDimensi, minPosisi, maksPosisi, ...
ukuranPopulasi, ukuranPopulasiTerpilih, alpha);
Memasuki perhitungan pada fungsi CA
* Memasuki proses inisialisasi parameter, matriks, dan variabel yang digunakan (poin 1a – 1f)
1a. Tentukan dimensi ukuran matriks yang digunakan
Dalam kasus ini, matriks ukuran dimensi akan berisi data dengan jumlah baris 1 dan jumlah kolom sebanyak parameter dimensi
ukuranDimensi = [1 jumlahDimensi];
1b. Lakukan inisialisasi posisi dan nilai fungsi pada individu baru sebanyak ukuran populasi
Beri nilai posisi dengan posisi acak, dan hitung nilai fungsi pada posisi acak tersebut
individuBaru.Posisi=[];
individuBaru.NilaiFungsi=[];
populasi=repmat(individuBaru,ukuranPopulasi,1);
for i=1:ukuranPopulasi
populasi(i).Posisi = unifrnd(minPosisi, maksPosisi, ukuranDimensi);
populasi(i).NilaiFungsi = HitungNilaiFungsi(populasi(i).Posisi);
end
* Gunakan fungsi ini untuk menghitung fitness dengan rumus:
f(x, y) = (x ^ 2 + y – 11) ^ 2 + (x + y ^ 2 – 7) ^ 2
function z = HitungFitness(u) z = (u(1)^2 + u(2) - 11) ^ 2 + (u(1) + u(2)^2 - 7) ^ 2;
1c. Urutkan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
daftarNilaiFungsi = [populasi.NilaiFungsi]; [~, idxTerurut]=sort(daftarNilaiFungsi, 'descend'); populasi = populasi(idxTerurut);
1d. Inisialisasi variabel situational dan normative yang terdapat dalam culture
Culture.Situational.NilaiFungsi = -inf; Culture.Normative.MinPosisi = inf(jumlahDimensi); Culture.Normative.MaksPosisi = -inf(jumlahDimensi); Culture.Normative.MinNilaiFungsi = inf(jumlahDimensi); Culture.Normative.MaksNilaiFungsi = inf(jumlahDimensi);
1e. Lakukan penyesuaian culture pada populasi terpilih
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini
populasiTerpilih=populasi(1:ukuranPopulasiTerpilih); Culture=HitungPenyesuaianCulture(Culture,populasiTerpilih);
* Gunakan fungsi ini untuk melakukan penyesuaian culture
variabel situational culture digunakan untuk menyimpan posisi dan nilai fungsi terbaik
variabel normative digunakan untuk menghitung nilai minimal dan maksimal dari masing-masing posisi dan nilai fungsi
dan kemudian menghitung nilai range posisi antara posisi minimal dan maksimal
function Culture = HitungPenyesuaianCulture(Culture,populasiTerpilih)
ukuranPopulasiTerpilih = numel(populasiTerpilih);
jumlahDimensi = numel(populasiTerpilih(1).Posisi);
for i=1:ukuranPopulasiTerpilih
if populasiTerpilih(i).NilaiFungsi > Culture.Situational.NilaiFungsi
Culture.Situational = populasiTerpilih(i);
end
for j=1:jumlahDimensi
if populasiTerpilih(i).Posisi(j)Culture.Normative.MaksPosisi(j) || populasiTerpilih(i).NilaiFungsi>Culture.Normative.MaksNilaiFungsi(j)
Culture.Normative.MaksPosisi(j) = populasiTerpilih(i).Posisi(j);
Culture.Normative.MaksNilaiFungsi(j) = populasiTerpilih(i).NilaiFungsi;
end
end
end
Culture.Normative.RangePosisi = Culture.Normative.MaksPosisi - Culture.Normative.MinPosisi;
1f. Ambil posisi situasional culture sebagai posisi terbaik sementara
posisiTerbaik=Culture.Situational.Posisi; nilaiFungsiTerbaik=Culture.Situational.NilaiFungsi;
* Lakukan proses pencarian posisi terbaik (poin 2)
2. Lakukan perhitungan sebanyak jumlah iterasi (poin 2a – 2d)
for i=1:jumlahIterasi . . .
2a. Lakukan perhitungan pada masing-masing posisi dimensi dalam populasi (poin 2a1 – 2a5)
for i=1:ukuranPopulasi for j=1:jumlahDimensi . . .
2a1. Hitung nilai sigma dengan cara perkalian nilai alpha dengan range posisi normative culture
sigma = alpha * Culture.Normative.RangePosisi(j);
2a2. Hitung nilai delta X dengan cara perkalian nilai sigma dengan nilai distribusi normal acak
deltaX = sigma*randn;
2a3. Jika nilai posisi kurang dari nilai posisi situational culture,
maka nilai delta X adalah nilai absolut dari dirinya sendiri
Jika nilai posisi lebih dari nilai posisi situational culture,
maka nilai delta X adalah nilai negatif absolut dari dirinya sendiri
if populasi(i).Posisi(j) < Culture.Situational.Posisi(j) deltaX = abs(deltaX); elseif populasi(i).Posisi(j) > Culture.Situational.Posisi(j) deltaX = -abs(deltaX); end
2a4. Hitung nilai posisi yang baru dengan rumus:
posisi baru = posisi + delta X
populasi(i).Posisi(j) = populasi(i).Posisi(j) + deltaX;
2a5. Hitung nilai fungsi pada posisi tersebut
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya
populasi(i).NilaiFungsi=HitungNilaiFungsi(populasi(i).Posisi);
2b. Urutkan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
daftarNilaiFungsi = [populasi.NilaiFungsi]; [~, idxTerurut]=sort(daftarNilaiFungsi, 'descend'); populasi = populasi(idxTerurut);
2c. Lakukan penyesuaian culture pada populasi terpilih
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya
populasiTerpilih=populasi(1:ukuranPopulasiTerpilih); Culture=HitungPenyesuaianCulture(Culture,populasiTerpilih);
2d. Jika nilai fungsi pada populasi yang sedang dihitung lebih baik dari nilai fungsi terbaik
maka ambil posisinya sebagai posisi terbaik
if Culture.Situational.NilaiFungsi > nilaiFungsiTerbaik nilaiFungsiTerbaik = Culture.Situational.NilaiFungsi; posisiTerbaik = Culture.Situational.Posisi; end
Hasil akhir adalah:
Algoritma CA (Cultural Algorithm 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 maksimal iterasi = 500 Jumlah dimensi = 2 Batas minimal posisi = -2 Batas maksimal posisi = 2 Ukuran populasi = 50 Ukuran populasi terpilih = 18 alpha = 0.3 Iterasi: 1, Posisi terbaik: -0.51467 -0.55653, Nilai Fungsi terbaik: 179.4124 Iterasi: 2, Posisi terbaik: -0.51467 -0.62966, Nilai Fungsi terbaik: 179.8268 Iterasi: 5, Posisi terbaik: -0.51825 -0.68068, Nilai Fungsi terbaik: 180.0079 Iterasi: 6, Posisi terbaik: -0.51751 -0.75109, Nilai Fungsi terbaik: 180.215 Iterasi: 7, Posisi terbaik: -0.52347 -0.79728, Nilai Fungsi terbaik: 180.2275 Iterasi: 8, Posisi terbaik: -0.055574 -0.80076, Nilai Fungsi terbaik: 180.329 Iterasi: 10, Posisi terbaik: -0.24068 -0.88369, Nilai Fungsi terbaik: 181.5773 Iterasi: 14, Posisi terbaik: -0.26371 -0.93278, Nilai Fungsi terbaik: 181.6149 Iterasi: 22, Posisi terbaik: -0.27217 -0.92104, Nilai Fungsi terbaik: 181.6165 Iterasi: 39, Posisi terbaik: -0.27066 -0.92317, Nilai Fungsi terbaik: 181.6165 Iterasi: 176, Posisi terbaik: -0.27072 -0.92317, Nilai Fungsi terbaik: 181.6165 Iterasi: 231, Posisi terbaik: -0.27084 -0.92319, Nilai Fungsi terbaik: 181.6165 Posisi Terbaik: -0.27084 -0.92319 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.