Algoritma CMA-ES (Covariance Matrix Adaptation – Evolution Strategy)

Algoritma CMA-ES (Covariance Matrix Adaptation – Evolution Strategy) 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 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

Lb = minPosisi * ones(1,jumlahDimensi);
Ub = maksPosisi * ones(1,jumlahDimensi);

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses perhitungan dengan metode CMA-ES (Covariance Matrix Adaptation – Evolution Strategy)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 2)

[posisiTerbaik,nilaiFungsiTerbaik] = CMAES( ...
    jumlahIterasi, jumlahDimensi, minPosisi, maksPosisi, Lb, Ub);

Memasuki perhitungan pada fungsi CMAES

*Memasuki proses inisialisasi parameter, matriks, dan variabel yang digunakan (poin 1a – 1h)

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, step, dan nilai fungsi pada individu baru sebanyak jumlah iterasi
Untuk individu pertama, beri nilai posisi acak, dan hitung nilai fungsi pada posisi acak tersebut
Kemudian masukkan individu ini sebagai posisi terbaik sementara

individuBaru.Posisi=[];
individuBaru.Step=[];
individuBaru.NilaiFungsi=[];

individu=repmat(individuBaru,jumlahIterasi,1);
individu(1).Posisi=unifrnd(minPosisi,maksPosisi,ukuranDimensi);
individu(1).Step=zeros(ukuranDimensi);
individu(1).NilaiFungsi=HitungNilaiFungsi(individu(1).Posisi);

posisiTerbaik=individu(1).Posisi;
nilaiFungsiTerbaik=individu(1).NilaiFungsi;

1c. Hitung ukuran populasi yang digunakan

ukuranPopulasi=(4+round(3*log(jumlahDimensi)))*10;

1d. Hitung jumlah induk yang digunakan
Nilai yang digunakan adalah setengah dari ukuran populasi

jumlahInduk=round(ukuranPopulasi/2);

1e. Hitung bobot induk
Nantinya perhitungan step individu akan dilakukan menggunakan bobot ini sebanyak jumlah induk

bobotInduk=log(jumlahInduk+0.5)-log(1:jumlahInduk);
bobotInduk=bobotInduk/sum(bobotInduk);

1f. Hitung jumlah solusi efektif
Nilai ini akan digunakan dalam perhitungan parameter kontrol step dan update kovarians yang akan dijelaskan setelah ini

jumlahSolusiEfektif=1/sum(bobotInduk.^2);

1g. Hitung parameter kontrol step yang digunakan, yaitu sigma0, sigmaC, sigmaD, dan ENN
Kemudian lakukan inisialisasi variabel ps dan sigma sebanyak jumlah iterasi
Beri nilai awal sigma pertama dengan nilai sigma0

sigma0=0.3*(maksPosisi-minPosisi);
sigmaC=(jumlahSolusiEfektif+2)/(jumlahDimensi+jumlahSolusiEfektif+5);
sigmaD=1+sigmaC+2*max(sqrt((jumlahSolusiEfektif-1)/(jumlahDimensi+1))-1,0);
ENN=sqrt(jumlahDimensi)*(1-1/(4*jumlahDimensi)+1/(21*jumlahDimensi^2));

ps=cell(jumlahIterasi,1);
ps{1}=zeros(ukuranDimensi);
sigma=cell(jumlahIterasi,1);
sigma{1}=sigma0;

1h. Hitung paramter update kovarians yang digunakan, yaitu cc, cl, alpha_mu, cmu, hth
Kemudian lakukan inisialisasi variabel pc dan C sebanyak jumlah iterasi
Beri nilai awal C pertama dengan nilai matriks identitas

cc=(4+jumlahSolusiEfektif/jumlahDimensi)/(4+jumlahDimensi+2*jumlahSolusiEfektif/jumlahDimensi);
c1=2/((jumlahDimensi+1.3)^2+jumlahSolusiEfektif);
alpha_mu=2;
cmu=min(1-c1,alpha_mu*(jumlahSolusiEfektif-2+1/jumlahSolusiEfektif)/((jumlahDimensi+2)^2+alpha_mu*jumlahSolusiEfektif/2));
hth=(1.4+2/(jumlahDimensi+1))*ENN;

pc=cell(jumlahIterasi,1);
pc{1}=zeros(ukuranDimensi);
C=cell(jumlahIterasi,1);
C{1}=eye(jumlahDimensi);

* Lakukan proses pencarian posisi terbaik (poin 2)

2. Lakukan perhitungan sebanyak jumlah iterasi (poin 2a – 2c)

for i=1:jumlahIterasi    
. . .

* Lakukan inisialisasi populasi yang digunakan dalam perhitungan (poin 2a)

2a. Lakukan perhitungan sebanyak ukuran populasi (poin 2a1 – 2a5)

for j=1:ukuranPopulasi
. . .

2a1. Beri nilai awal step dengan nilai step acak
Pengacakan step menggunakan teknik multivariate normal acak

populasi(j).Step=mvnrnd(zeros(ukuranDimensi),C{i});

2a2. Hitung nilai posisi dengan rumus:
posisi = posisi individu terpilih + sigma individu terpilih * nilai step acak sebelumnya

populasi(j).Posisi=individu(i).Posisi+sigma{i}*populasi(j).Step;

2a3. Jika posisi tersebut ternyata diluar batas yang diperbolehkan,
maka kembalikan posisinya agar masuk dalam batas tersebut

tmpPosisi=populasi(j).Posisi;

I=tmpPosisiUb;
tmpPosisi(J)=Ub(J);

populasi(j).Posisi=tmpPosisi;

2a4. Hitung nilai fungsi pada posisi tersebut
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

populasi(j).NilaiFungsi=HitungNilaiFungsi(populasi(j).Posisi);

* 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;

2a5. Jika nilai fungsi pada populasi yang sedang dihitung lebih baik dari nilai fungsi terbaik
maka ambil posisinya sebagai posisi terbaik

if populasi(j).NilaiFungsi > nilaiFungsiTerbaik
	nilaiFungsiTerbaik = populasi(j).NilaiFungsi;
	posisiTerbaik = populasi(j).Posisi;
end

2b. Lakukan pengurutan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

daftarNilaiFungsi=[populasi.NilaiFungsi];
[~, idxTerurut]=sort(daftarNilaiFungsi, 'descend');
populasi=populasi(idxTerurut);

2c. Selama perhitungan belum dilakukan sebanyak jumlah iterasi, maka lakukan perhitungan berikut (poin 2c1 – 2c8)

if i~=jumlahIterasi
. . .

* Lakukan proses penghitungan nilai individu pada iterasi berikutnya (poin 2c1 – 2c5)

2c1. Hitung nilai awal step individu berikutnya dengan rumus:
step = E(bobot induk * nilai step pada posisi terbaik dalam populasi

individu(i+1).Step=0;
for j=1:jumlahInduk
	individu(i+1).Step=individu(i+1).Step+bobotInduk(j)*populasi(j).Step;
end

2c2. Kemudian hitung nilai posisi individu tersebut dengan rumus:
posisi = posisi individu sebelumnya + sigma * nilai step individu ini

individu(i+1).Posisi=individu(i).Posisi+sigma{i}*individu(i+1).Step;

2c3. Jika posisi tersebut ternyata diluar batas yang diperbolehkan,
maka kembalikan posisinya agar masuk dalam batas tersebut

tmpPosisi=individu(i+1).Posisi;

I=tmpPosisiUb;
tmpPosisi(J)=Ub(J);

individu(i+1).Posisi=tmpPosisi;

2c4. Hitung nilai fungsi pada posisi tersebut
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya

individu(i+1).NilaiFungsi=HitungNilaiFungsi(individu(i+1).Posisi);

2c5. Jika nilai fungsi pada individu ini lebih baik dari nilai fungsi terbaik
maka ambil posisi individu ini sebagai posisi terbaik

if individu(i+1).NilaiFungsi > nilaiFungsiTerbaik
	nilaiFungsiTerbaik = individu(i+1).NilaiFungsi;
	posisiTerbaik = individu(i+1).Posisi;
end

2c6. Lakukan proses perhitungan parameter kontrol step pada iterasi berikutnya
Parameter yang dihitung adalah ps dan sigma

ps{i+1}=(1-sigmaC)*ps{i}+sqrt(sigmaC*(2-sigmaC)*jumlahSolusiEfektif)*individu(i+1).Step/chol(C{i})';
sigma{i+1}=sigma{i}*exp(sigmaC/sigmaD*(norm(ps{i+1})/ENN-1))^0.3;

2c7. Lakukan proses perhitungan parameter update kovarians pada iterasi berikutnya
Parameter yang dihitung adalah pc dan C

if norm(ps{i+1})/sqrt(1-(1-sigmaC)^(2*(i+1)))

2c8. Lakukan perhitungan berikut apabila matriks kovarians bukan bernilai positif

Metode yang digunakan adalah Eigenvector
[V, E]=eig(C{i+1});
if any(diag(E)<0)
	E=max(E,0);
	C{i+1}=V*E/V;
end

Hasil akhir adalah:
Algoritma CMA-ES (Covariance Matrix Adaptation - Evolution Strategy)
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


Iterasi: 1, Populasi: 22, Posisi terbaik: -0.67512     -0.6378, Fitness terbaik: 177.8661
Iterasi: 1, Populasi: 43, Posisi terbaik: -0.09517      -1.481, Fitness terbaik: 179.5769
Iterasi: 1, Populasi: 47, Posisi terbaik: -0.25084    -0.87834, Fitness terbaik: 181.5862
Iterasi: 4, Populasi: 20, Posisi terbaik: -0.25489    -0.98179, Fitness terbaik: 181.587
Iterasi: 4, Populasi: 37, Posisi terbaik: -0.27065    -0.97788, Fitness terbaik: 181.5918
Iterasi: 4, Individu: 5, Posisi terbaik: -0.2496    -0.96658, Fitness terbaik: 181.5952
Iterasi: 5, Populasi: 14, Posisi terbaik: -0.29871    -0.89322, Fitness terbaik: 181.5955
Iterasi: 5, Individu: 6, Posisi terbaik: -0.2704    -0.94087, Fitness terbaik: 181.6139
Iterasi: 6, Populasi: 12, Posisi terbaik: -0.27977    -0.92486, Fitness terbaik: 181.6146
Iterasi: 6, Populasi: 35, Posisi terbaik: -0.26898    -0.93785, Fitness terbaik: 181.6147
Iterasi: 6, Populasi: 56, Posisi terbaik: -0.2682    -0.93464, Fitness terbaik: 181.6154
Iterasi: 6, Individu: 7, Posisi terbaik: -0.27406    -0.92648, Fitness terbaik: 181.6161
Iterasi: 7, Individu: 8, Posisi terbaik: -0.27159    -0.92134, Fitness terbaik: 181.6165
Iterasi: 9, Individu: 10, Posisi terbaik: -0.27063    -0.92292, Fitness terbaik: 181.6165
Iterasi: 10, Individu: 11, Posisi terbaik: -0.27073    -0.92288, Fitness terbaik: 181.6165
Iterasi: 11, Individu: 12, Posisi terbaik: -0.27083    -0.92329, Fitness terbaik: 181.6165
Iterasi: 12, Populasi: 34, Posisi terbaik: -0.27076    -0.92288, Fitness terbaik: 181.6165
Iterasi: 12, Individu: 13, Posisi terbaik: -0.27087    -0.92319, Fitness terbaik: 181.6165
Iterasi: 13, Populasi: 3, Posisi terbaik: -0.27087    -0.92306, Fitness terbaik: 181.6165
Iterasi: 13, Populasi: 22, Posisi terbaik: -0.27084    -0.92308, Fitness terbaik: 181.6165
Iterasi: 13, Populasi: 34, Posisi terbaik: -0.27083    -0.92306, Fitness terbaik: 181.6165
Iterasi: 13, Individu: 14, Posisi terbaik: -0.27084    -0.92305, Fitness terbaik: 181.6165
Iterasi: 15, Individu: 16, Posisi terbaik: -0.27084    -0.92305, Fitness terbaik: 181.6165
Iterasi: 16, Populasi: 17, Posisi terbaik: -0.27084    -0.92303, Fitness terbaik: 181.6165
Iterasi: 16, Populasi: 38, Posisi terbaik: -0.27084    -0.92304, Fitness terbaik: 181.6165
Iterasi: 17, Individu: 18, Posisi terbaik: -0.27085    -0.92304, Fitness terbaik: 181.6165
Iterasi: 18, Individu: 19, Posisi terbaik: -0.27084    -0.92304, Fitness terbaik: 181.6165
Iterasi: 19, Populasi: 34, Posisi terbaik: -0.27085    -0.92304, Fitness terbaik: 181.6165
Iterasi: 19, Individu: 20, Posisi terbaik: -0.27084    -0.92304, Fitness terbaik: 181.6165
Iterasi: 20, Populasi: 45, Posisi terbaik: -0.27084    -0.92304, Fitness terbaik: 181.6165
Iterasi: 24, Individu: 25, Posisi terbaik: -0.27084    -0.92304, Fitness terbaik: 181.6165


Posisi Terbaik: -0.27084    -0.92304
Nilai Fungsi Terbaik =181.6165

Contoh modul / source code menggunakan Matlab dapat didownload disini:
Download Now!



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.
Bagikan ini:
Facebook
Twitter
WhatsApp
Surat elektronik