Algoritma CSO (Cuckoo Search Optimization) 10

Algoritma CSO (Cuckoo Search Optimization) 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 spesies cuckoo yaitu sebuah parasit yang meletakkan telurnya di sarang burung lain (yang tentu saja bukan spesies cuckoo). Jika induk burung menemukan telur yang bukan dari dirinya sendiri, maka induk burung tersebut akan membuang telur parasit tersebut atau membangun sarang baru ditempat lain. Cuckoo yang berhasil tumbuh nantinya akan mencari sarang burung lain sebagai tempat peletakan telur. Proses tersebut berulang sampai semua cuckoo sudah berkumpul pada sebuah sarang burung.

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 cuckoo yang digunakan
Diasumsikan dalam kasus ini, akan digunakan 5 cuckoo sebagai populasi awal

jumlahCuckoo = 5;

* Tentukan jumlah minimal dan maksimal telur yang dihasilkan oleh masing-masing cuckoo
Nantinya masing-masing cuckoo akan menghasilkan telur acak diantara batas ini
Diasumsikan dalam kasus ini, masing-masing cuckoo akan menghasilkan telur minimal 2 buah dan maksimal 4 buah

jumlahMinimalTelur = 2;
jumlahMaksimalTelur = 4;

* 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 telur 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 batas minimal nilai fungsi yang diperbolehkan
Jika nilai fungsi terbaik yang terakhir kurang dari batas minimal nilai ini,
maka perhitungan akan dihentikan
Diasumsikan dalam kasus ini, batas minimal nilai fungsi adalah minus tak terhingga

batasMinimalNilaiFungsi = -inf;

* Tentukan radius, yaitu koefisien untuk menghitung radius dari masing-masing telur
Diasumsikan dalam kasus ini, radius bernilai 5

radius = 5;

* Tentukan jumlah maksimal cuckoo yang diperbolehkan dalam sekali perulangan
Hal ini ditujukan untuk menyimpan cuckoo terbaik saja, sedangkan sisanya akan dibuang
Diasumsikan dalam kasus ini, jumlah maksimal cuckoo adalah 10

jumlahMaksimalCuckoo = 10;

* Tentukan batas minimal perbedaan keragaman posisi telur
Jika posisi telur yang baru tidak terlalu memiliki keragaman, maka perhitungan akan dihentikan
Diasumsikan dalam kasus ini, batas minimal perbedaan posisi telur adalah nilai yang sangat rendah, yaitu 0.000000000001

batasMinimalPerbedaanPosisiTelur = 1e-13;

* Tentukan jumlah cluster yang digunakan
Cluster digunakan untuk mengelompokan telur dari masing-masing cuckoo pada setiap kali perulangan
Diasumsikan dalam kasus ini, cluster hanya digunakan 1 saja untuk mempermudah perhitungan

jumlahCluster = 1;

* Tentukan Lambda, yaitu koefisien untuk menghitung pergerakan cuckoo dewasa menuju tempat peletakan telur
Nilai yang direkomendasikan adalah 2
Diasumsikan dalam kasus ini, nilai Lambda adalah 9

Lambda = 9;

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses perhitungan dengan metode CSO (Cuckoo Search Optimization)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 3)

[posisiCuckooTerbaik, nilaiFungsiTerbaik] = CSO( ...
    jumlahCuckoo, jumlahMinimalTelur, jumlahMaksimalTelur, jumlahIterasi, ...
    jumlahDimensi, minPosisi, maksPosisi, ...
    batasMinimalNilaiFungsi, radius, jumlahMaksimalCuckoo, ...
    batasMinimalPerbedaanPosisiTelur, jumlahCluster, Lambda);

Memasuki perhitungan pada fungsi CSO

1. Inisialisasi Populasi sebanyak jumlah cuckoo
Kemudian hitung titik pusat peletakan telur dari masing-masing cuckoo

populasi = cell(jumlahCuckoo,1);
for i = 1:jumlahCuckoo    
    populasi{i}.titikPusat = ( maksPosisi-minPosisi )*rand(1,jumlahDimensi) + minPosisi;
end

2. Beri nilai awal posisi cuckoo dengan nilai acak,
kemudian beri nilai fungsi awal dengan nilai yang sangat rendah
Masukkan masing-masing nilai sebagai nilai terbaik awal mula

posisiCuckoo = (maksPosisi - minPosisi)*rand(1,jumlahDimensi) + minPosisi;
nilaiFungsi = -1e20;
posisiCuckooTerbaik = posisiCuckoo;
nilaiFungsiTerbaik = nilaiFungsi;

3. Lakukan perulangan sebanyak jumlah iterasi, dan selama nilai fungsi tidak kurang dari batas minimal nilai fungsi (poin 3a – 3l)

while ( (iterasi <= jumlahIterasi) && (-nilaiFungsi > batasMinimalNilaiFungsi) )
. . .

3a. Tentukan jumlah telur secara acak pada masing-masing cuckoo

for i = 1:jumlahCuckoo        
	populasi{i}.jumlahTelur = floor( (jumlahMaksimalTelur - jumlahMinimalTelur) * rand + jumlahMinimalTelur );
end

3b. Hitung total telur yang dihasilkan dari perhitungan sebelumnya

totalTelur = 0;
for i = 1:jumlahCuckoo
	totalTelur = totalTelur + populasi{i}.jumlahTelur;
end

3c. Hitung radius peletakan telur dari masing-masing telur yang dihasilkan masing-masing cuckoo

for i = 1:jumlahCuckoo
	populasi{i}.radiusPeletakanTelurPerTelur = populasi{i}.jumlahTelur/totalTelur * ( radius * (maksPosisi-minPosisi) );
end

3d. Catat nilai radius untuk masing-masing telur

for i = 1:jumlahCuckoo
	populasi{i}.nilaiDalamRadiusPerTelur = populasi{i}.radiusPeletakanTelurPerTelur * rand(populasi{i}.jumlahTelur,1);
end

3e. Lakukan perhitungan untuk menentukan posisi yang baru dari masing-masing telur (poin 3e1)

3e1. Lakukan perhitungan pada masing-masing cuckoo (poin 3e1a – 3e1d)

3e1a. Hitung sudut pencarian dengan analogi seperti membagi lingkaran sebanyak n sama besar
Sudut pencarian yang dihasilkan adalah dalam bentuk radian
Sudut ini digunakan untuk menentukan arah tujuan titik yang baru dalam radius

sudutPencarian = linspace(0,2*pi,jumlahNilaiDalamRadius);

3e1b. Untuk masing-masing nilai radius,
Hitung posisi telur yang baru dengan mempertimbangkan arah tujuan titik dalam masing-masing radius

posisiBaruTelur = [];
for j = 1:jumlahNilaiDalamRadius
	nilaiTambah = zeros(1,jumlahDimensi);
	for k = 1:jumlahDimensi
		nilaiAcak = floor(2*rand)+1;
		nilaiTambah(k) = (-1)^nilaiAcak * tmpNilaiRadius(j)*cos(sudutPencarian(j)) + tmpNilaiRadius(j)*sin(sudutPencarian(j));
	end
	posisiBaruTelur = [posisiBaruTelur; tmpTitikPusat +  nilaiTambah ];
end        

3e1c. Jika posisi yang baru ternyata diluar batas minimal dan maksimal posisi,
maka kembalikan posisinya agar masuk dalam batas

posisiBaruTelur(find(posisiBaruTelur>maksPosisi)) = maksPosisi;
posisiBaruTelur(find(posisiBaruTelur

3e1d. Masukkan posisi tersebut sebagai posisi telur yang baru
populasi{i}.posisiBaruTelur = posisiBaruTelur;

3f. Setelah menentukan posisi dari masing-masing telur

Lakukan pengecekan untuk menghilangkan telur pada posisi yang sama (poin 3f1)

3f1. Lakukan perhitungan pada masing-masing cuckoo (poin 3f1a - 3f1b)

3f1a. Bandingkan posisi telur dalam masing-masing cuckoo (poin 3f1a1 - ef1a2)
while idxTelur1 <= size(tmpPosisiBaruTelur,1) || idxTelur2 <= size(tmpPosisiBaruTelur,1)
. . .

3f1a1. Jika kedua telur berada dalam posisi yang sama, maka buang telur kedua
if all((tmpPosisiBaruTelur(idxTelur2,:) == tmpPosisiBaruTelur(idxTelur1,:)))
	tmpPosisiBaruTelur(idxTelur1,:) = [];
end

3f1a2. Lanjutkan perhitungan ke telur berikutnya

Apabila sudah tidak ada telur berikutnya, maka lanjutkan perhitungan ke cuckoo berikutnya
idxTelur1 = idxTelur1 + 1;
if idxTelur1 > size(tmpPosisiBaruTelur,1) && idxTelur2 <= size(tmpPosisiBaruTelur,1)
	idxTelur2 = idxTelur2 + 1;
	idxTelur1 = idxTelur2 + 1;
	
	if idxTelur1 > size(tmpPosisiBaruTelur,1)
		break
	end
end

3f1b. Simpan posisi telur yang tidak mengalami pembuangan
populasi{i}.posisiBaruTelur = tmpPosisiBaruTelur;

3g. Hitung nilai fungsi masing-masing telur pada masing-masing cuckoo

Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini
for i = 1:jumlahCuckoo
	populasi{i}.nilaiFungsi = himmelblau([populasi{i}.titikPusat ; populasi{i}.posisiBaruTelur]);        
end

* Gunakan fungsi ini untuk menghitung nilai fungsi himmelblau dengan rumus:

f(x, y) = (x ^ 2 + y - 11) ^ 2 + (x + y ^ 2 - 7) ^ 2
function y = himmelblau(x)
y = (x(:,1).^2 + x(:,2) - 11).^ 2 + (x(:,1) + x(:,2).^2 - 7).^ 2;

3h. Lakukan pengecekan apakah jumlah cuckoo yang ada tidak melebihi jumlah maksimal cuckoo

Jika melebihi, maka buang cuckoo dengan nilai fungsi telur terendah (poin 3h1 - 3h4)

3h1. Lakukan perhitungan pada masing-masing cuckoo

Catat semua nilai fungsi dan posisi telur yang ada
for i = 1:jumlahCuckoo
	tmpNilaiFungsi = [tmpNilaiFungsi; populasi{i}.nilaiFungsi];
	tmpPosisiTelur = [tmpPosisiTelur; [populasi{i}.titikPusat; populasi{i}.posisiBaruTelur(:,1:jumlahDimensi)]];
end

3h2. Lakukan pengurutan nilai fungsi berdasarkan nilai tertinggi ke nilai terendah
[nilaiFungsiTerurut, idxNilaiFungsiTerurut] = sort(tmpNilaiFungsi,'descend');

3h3. Tentukan titik pusat cuckoo terbaik, yaitu indeks pertama pada nilai fungsi terurut
titikPusatCuckooTerbaik = tmpPosisiTelur(idxNilaiFungsiTerurut(1),1:jumlahDimensi);

3h4. Jika jumlah cuckoo yang ada tidak melebihi jumlah maksimal cuckoo,

maka lakukan perhitungan berikut (poin 3h4a - 3h4b)
if jumlahCuckoo > jumlahMaksimalCuckoo
. . .

3h4a. Hapus populasi awal
clear populasi

3h4b. Lakukan perhitungan sebanyak jumlah maksimal cuckoo

Masukkan posisi telur, titik pusat dan nilai fungsi secara terurut
for i = 1:jumlahMaksimalCuckoo
	populasi{i}.posisiBaruTelur = tmpPosisiTelur(i,:);
	populasi{i}.titikPusat = tmpPosisiTelur(i,:);
	populasi{i}.nilaiFungsi = nilaiFungsiTerurut(i);
end

3i. Catat nilai fungsi yang baru, yaitu nilai fungsi pada urutan pertama
nilaiFungsi = nilaiFungsiTerurut(1);

3j. Lakukan perhitungan nilai fungsi pada cuckoo pada posisi terbaik

Apabila nilai fungsi nya lebih baik dari nilai fungsi terbaik,

maka ambil posisi cuckoo sebagai posisi terbaik
    cuckooTerbaikSekarang = titikPusatCuckooTerbaik;
    nilaiFungsiSekarang = himmelblau(cuckooTerbaikSekarang);
    
    if nilaiFungsiSekarang > nilaiFungsiTerbaik
        posisiCuckooTerbaik = cuckooTerbaikSekarang;
        nilaiFungsiTerbaik = nilaiFungsiSekarang;
    end

* Setelah proses tersebut, Masing-masing telur nantinya akan menjadi cuckoo

dan akhirnya akan menggantikan cuckoo pada perulangan / iterasi berikutnya

3k. Lakukan pengelompokan data pada cuckoo baru (yang berasal dari telur) (poin 3k1 - 3k6)

3k1. Lakukan perhitungan pada masing-masing cuckoo

Catat semua posisi telur dan cuckoo tujuan dari masing-masing telur yang ada
for i = 1:jumlahCuckoo
	tmpPosisiTelur = [tmpPosisiTelur; populasi{i}.posisiBaruTelur(:,1:jumlahDimensi)];
	tmpCuckooTujuanDariTelur = [tmpCuckooTujuanDariTelur; i*ones(size(populasi{i}.posisiBaruTelur(:,1:jumlahDimensi),1),1) ];
end

3k2. Jika tidak terdapat keragaman dari posisi masing-masing telur, maka hentikan perhitungan

Selain itu lakukan pengelompokan data kedalam cluster menggunakan metode k-means

Penjelasan lebih detail tentang metode K-means dapat dilihat di halaman Algoritma K-Means Clustering
if sum(var(tmpPosisiTelur)) < batasMinimalPerbedaanPosisiTelur
	break
else
	[daftarCluster, CentroidPerCluster] = kmeans(tmpPosisiTelur,jumlahCluster);
end

3k3. Setelah menentukan cluster dari masing-masing telur,

catat posisi telur dan nilai fungsi untuk masing-masing cluster
jumlahTelurPerCuckoo = zeros(numel(populasi),1);
for i = 1:numel(populasi)
	jumlahTelur = size(populasi{i}.posisiBaruTelur,1);
	jumlahTelurPerCuckoo(i) = jumlahTelur;
end
for i = 1:length(daftarCluster)
	cluster{daftarCluster(i)}.daftarPosisi = [cluster{daftarCluster(i)}.daftarPosisi; populasi{tmpCuckooTujuanDariTelur(i)}.posisiBaruTelur(end-jumlahTelurPerCuckoo(tmpCuckooTujuanDariTelur(i))+1,1:jumlahDimensi)];
	cluster{daftarCluster(i)}.daftarNilaiFungsi   = [cluster{daftarCluster(i)}.daftarNilaiFungsi; populasi{tmpCuckooTujuanDariTelur(i)}.nilaiFungsi(end-jumlahTelurPerCuckoo(tmpCuckooTujuanDariTelur(i))+1)];
	jumlahTelurPerCuckoo(tmpCuckooTujuanDariTelur(i)) = jumlahTelurPerCuckoo(tmpCuckooTujuanDariTelur(i)) - 1;
end

3k4. Tentukan mean dari masing-masing cluster
daftarMean = zeros(jumlahCluster,1);
for i = 1:jumlahCluster
	daftarMean(i) = mean(cluster{i}.daftarNilaiFungsi);
end

3k5. Lakukan pengurutan mean berdasarkan nilai tertinggi ke nilai terendah
[daftarMeanTerurut, idxDaftarMeanTerurut] = sort(daftarMean,'descend');
idxClusterTerbaik = idxDaftarMeanTerurut(1);

3k6. Setelah mengetahui indeks cluster terbaik,

maka gunakan posisi cuckoo terbaik pada cluster tersebut sebagai posisi tujuan dari cuckoo sekarang
[nilaiFungsiPadaClusterTerbaik, idxPosisiTelurTerbaik] = max(cluster{idxClusterTerbaik}.daftarNilaiFungsi);
posisiCuckoo  = cluster{idxClusterTerbaik}.daftarPosisi(idxPosisiTelurTerbaik,1:jumlahDimensi);

3l. Setelah mengetahui titik tujuan dari masing-masing cuckoo,

maka masing-masing cuckoo akan bergerak menuju posisi tersebut untuk meletakkan telur (poin 3l1)

3l1. Lakukan perhitungan pada masing-masing cluster (poin 3l1a - 3l1d)
for i = 1:size(cluster,1)
. . .

3l1a. Lakukan perhitungan posisi yang baru pada masing-masing cuckoo
tmpPosisi = cluster{i}.daftarPosisi;
for j = 1:size(tmpPosisi,1)
	tmpPosisi(j,:) = tmpPosisi(j,:) + Lambda * rand(1,jumlahDimensi) .*  (posisiCuckoo  - tmpPosisi(j,:));
end

3l1b. Jika posisi yang baru ternyata diluar batas minimal dan maksimal posisi,

maka kembalikan posisinya agar masuk dalam batas
tmpPosisi(find( tmpPosisi>maksPosisi )) = maksPosisi;
tmpPosisi(find( tmpPosisi

3l1c. Lakukan update daftar posisi cluster dengan posisi yang baru

Kemudian hitung kembali mean sebagai titik pusat cluster tersebut
cluster{i}.daftarPosisi = tmpPosisi;
cluster{i}.titikPusat = mean(tmpPosisi);

3l1d. Hitung jumlah cuckoo yang baru
jumlahCuckooBaru = jumlahCuckooBaru + size(cluster{i}.daftarPosisi,1);

3m. Hapus populasi yang lama

Kemudian masukkan masing-masing cuckoo yang baru ke dalam populasi
clear populasi
populasi = cell(jumlahCuckoo,1);
idxjumlahCuckoo = 1;
for i = 1:size(cluster,1)
	tmpPosisi = cluster{i}.daftarPosisi;
	
	for j = 1:size(tmpPosisi,1)
		populasi{idxjumlahCuckoo}.titikPusat = cluster{i}.daftarPosisi(j,1:jumlahDimensi);
		idxjumlahCuckoo = idxjumlahCuckoo + 1;
	end
end

3n. Hapus 2 cuckoo terakhir dari populasi

Kemudian tambahkan cuckoo dengan posisi cuckoo terbaik

dan tambahkan cuckoo dengan posisi nilai acak disekitar posisi cuckoo terbaik
populasi{end}.titikPusat = posisiCuckooTerbaik;
populasi{end}.nilaiFungsi = himmelblau(populasi{end}.titikPusat);

tmpPosisiCuckooTerbaik = rand(1,jumlahDimensi).*posisiCuckooTerbaik;
tmpPosisiCuckooTerbaik(find( tmpPosisiCuckooTerbaik>maksPosisi )) = maksPosisi;
tmpPosisiCuckooTerbaik(find( tmpPosisiCuckooTerbaik

Hasil akhir adalah:
Algoritma CSO (Cuckoo Search Optimization)
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 Cuckoo                        = 5
Jumlah Minimal Telur                 = 2
Jumlah Maksimal Telur                = 4
Jumlah Iterasi                       = 500
Jumlah Dimensi                       = 2
Batas minimal posisi telur           = -2
Batas maksimal posisi telur          = 2
Batas Minimal Nilai Fungsi           = -Inf
Radius                               = 5
Jumlah Maksimal Cuckoo               = 10
Batas Minimal Perbedaan Posisi Telur = 1e-13
Jumlah Cluster                       = 1
Lambda                               = 9


Iterasi: 1, Telur: 2, Posisi terbaik: -0.47455    -0.87944, Nilai Fungsi terbaik: 180.7266
Iterasi: 2, Telur: 2, Posisi terbaik: -0.31429    -0.71918, Nilai Fungsi terbaik: 181.2339
Iterasi: 4, Telur: 33, Posisi terbaik: -0.25671     -0.8285, Nilai Fungsi terbaik: 181.5276
Iterasi: 25, Telur: 36, Posisi terbaik: -0.27693    -0.84872, Nilai Fungsi terbaik: 181.5698
Iterasi: 31, Telur: 18, Posisi terbaik: -0.23509    -0.90677, Nilai Fungsi terbaik: 181.5829
Iterasi: 37, Telur: 2, Posisi terbaik: -0.23994    -0.90192, Nilai Fungsi terbaik: 181.5882
Iterasi: 38, Telur: 3, Posisi terbaik: -0.27032    -0.87154, Nilai Fungsi terbaik: 181.5935
Iterasi: 46, Telur: 89, Posisi terbaik: -0.28524    -0.88647, Nilai Fungsi terbaik: 181.6029
Iterasi: 48, Telur: 5, Posisi terbaik: -0.28517    -0.93537, Nilai Fungsi terbaik: 181.6098
Iterasi: 50, Telur: 81, Posisi terbaik: -0.27012    -0.92032, Nilai Fungsi terbaik: 181.6164
Iterasi: 243, Telur: 4, Posisi terbaik: -0.27229    -0.92286, Nilai Fungsi terbaik: 181.6165
Iterasi: 477, Telur: 3, Posisi terbaik: -0.27211    -0.92305, Nilai Fungsi terbaik: 181.6165


Posisi Terbaik: -0.27211    -0.92305
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