Algoritma SCE (Shuffled Complex Evolution) 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 jumlah kelompok individu yang digunakan
Nantinya nilai ini akan digunakan untuk menghitung ukuran populasi
Diasumsikan dalam kasus ini, jumlah individu adalah 10
jumlahKelompok = 10;
* Tentukan jumlah individu yang digunakan dalam masing-masing kelompok
Nilai minimal yang diperbolehkan adalah sesuai dengan jumlah dimensi yang digunakan, tetapi boleh lebih dari itu
Nantinya nilai ini akan digunakan untuk menghitung ukuran populasi dan jumlah induk dalam kelompok tersebut
Diasumsikan dalam kasus ini, jumlah individu adalah 5
jumlahIndividuPerKelompok = 5;
* Tentukan alpha, yaitu jumlah anak yang dihasilkan dari induk
Diasumsikan dalam kasus ini, nilai alpha adalah 3
alpha = 3;
* Tentukan beta, yaitu jumlah maksimal iterasi dalam sekali proses CCE
Diasumsikan dalam kasus ini, nilai beta adalah 5
beta = 5;
Langkah-langkah penggunaan algoritma ini adalah
* Lakukan proses perhitungan dengan metode SCE (Shuffled Complex Evolution)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 2)
[posisiTerbaik,nilaiFungsiTerbaik] = SCE( ...
jumlahIterasi, jumlahDimensi, minPosisi, maksPosisi, ...
jumlahKelompok, jumlahIndividuPerKelompok, alpha, beta);
Memasuki perhitungan pada fungsi SCE
* Memasuki proses inisialisasi parameter, matriks, dan variabel yang digunakan (poin 1a – 1g)
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. Hitung ukuran populasi yang digunakan
ukuranPopulasi = jumlahIndividuPerKelompok * jumlahKelompok;
1c. Lakukan pengurutan indeks individu dalam masing-masing kelompok, yang disimpan ke dalam matriks indeks (I)
Jika ukuran populasi adalah 6 dan memiliki 2 kelompok, maka proses ini akan menghasilkan matriks dengan nilai
I = [1 3 5]
[2 4 6]
I = reshape(1:ukuranPopulasi, jumlahKelompok, []);
1d. Hitung parameter q, yaitu jumlah induk dalam masing-masing kelompok
q = max(round(0.3 * jumlahIndividuPerKelompok), 2);
1e. 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;
1f. Urutkan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
daftarNilaiFungsi = [populasi.NilaiFungsi]; [~, idxTerurut]=sort(daftarNilaiFungsi, 'descend'); populasi = populasi(idxTerurut);
1g. Ambil individu terbaik sebagai posisi terbaik sementara
posisiTerbaik=populasi(1).Posisi; nilaiFungsiTerbaik=populasi(1).NilaiFungsi;
* Lakukan proses pencarian posisi terbaik (poin 2)
2. Lakukan perhitungan sebanyak jumlah iterasi (poin 2a – 2d)
for i=1:jumlahIterasi . . .
2a. Lakukan inisialisasi daftar kelompok yang digunakan sebanyak parameter jumlah kelompok
daftarKelompok = cell(jumlahKelompok, 1);
2b. Lakukan perhitungan sebanyak jumlah kelompok (poin 2b1 – 2b3)
for j = 1:jumlahKelompok . . .
2b1. Ambil kelompok dalam populasi dengan indeks populasi sesuai dengan urutan dalam matriks indeks (I)
daftarKelompok{j} = populasi(I(j,:));
2b2. Lakukan proses perhitungan dengan metode CCE (Competitive Complex Evolution)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2b2a – 2b2b)
daftarKelompok{j} = CCE(daftarKelompok{j}, posisiTerbaik, nilaiFungsiTerbaik, ...
minPosisi, maksPosisi, q, alpha, beta);
Memasuki perhitungan pada fungsi CCE
* Memasuki proses inisialisasi parameter, matriks, dan variabel yang digunakan (poin 2b2a)
2b2a1. Hitung ukuran populasi yang digunakan dalam fungsi ini,
yaitu sebanyak ukuran dari parameter populasi
ukuranPopulasi = numel(populasi);
2b2a2. Hitung probabilitas seleksi pada populasi ini
P = 2*(ukuranPopulasi+1-(1:ukuranPopulasi))/(ukuranPopulasi*(ukuranPopulasi+1));
2b2a3. Hitung nilai minimal dan nilai maksimal dari posisi yang terdapat dalam populasi
nilaiPosisiMinimal = populasi(1).Posisi;
nilaiPosisiMaksimal = populasi(1).Posisi;
for i = 2:ukuranPopulasi
nilaiPosisiMinimal = min(nilaiPosisiMinimal, populasi(i).Posisi);
nilaiPosisiMaksimal = max(nilaiPosisiMaksimal, populasi(i).Posisi);
end
* Memasuki perhitungan utama dari fungsi CCE (poin 2b2b)
2b2b. Lakukan perhitungan sebanyak parameter beta, yaitu jumlah maksimal iterasi pada fungsi ini (poin 2b2b1 – 2b2b3)
for i = 1:beta . . .
2b2b1. Lakukan pemilihan induk sebanyak parameter q, yaitu jumlah induk dalam populasi
Pemilihan induk dilakukan secara acak
Probabilitas masing-masing individu sesuai dengan parameter probabilitas seleksi yang telah ditentukan sebelumnya
dan pastikan tidak ada induk dengan indeks yang sama
daftarIdxInduk = zeros(q,1); tmpP = P; for j=1:q daftarIdxInduk(j) = randsample(numel(tmpP), 1, true, tmpP); tmpP(daftarIdxInduk(j)) = 0; end daftarInduk = populasi(daftarIdxInduk);
* Berikut adalah proses untuk menghasilkan anak dari induk yang sudah terpilih (poin 2b2b2)
2b2b2. Lakukan perhitungan sebanyak parameter alpha, yaitu jumlah anak yang dihasilkan dari induk (poin 2b2b2a – 2b2b2d)
for k=1:alpha . . .
2b2b2a. Urutkan daftar induk berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
daftarNilaiFungsi = [daftarInduk.NilaiFungsi]; [~, idxTerurut]=sort(daftarNilaiFungsi, 'descend'); daftarIdxInduk = daftarIdxInduk(idxTerurut);
2b2b2b. Hitung nilai centroid pada masing-masing dimensi pada daftar induk
Centroid dihitung dengan cara mencari nilai rata-rata pada masing-masing dimensi
Centroid = 0; for i=1:q-1 Centroid = Centroid + daftarInduk(i).Posisi; end Centroid = Centroid/(q-1);
* Memasuki proses perhitungan nilai reflected (poin 2b2b2c)
2b2b2c1. Hitung posisi reflected,
yaitu posisi centroid ditambah dengan jarak antara posisi centroid dan daftar induk terburuk
Reflected.Posisi = 2 * Centroid - daftarInduk(end).Posisi;
2b2b2c2. Jika posisi reflected ternyata memiliki posisi diluar batas yang diperbolehkan,
maka ambil nilai posisi acak pada sebagai posisi reflected
if ~(all(Reflected.Posisi>=minPosisi) & all(Reflected.Posisi<=maksPosisi)) Reflected.Posisi = unifrnd(minPosisi, maksPosisi, jumlahDimensi); end
2b2b2c3. Hitung nilai fungsi pada posisi tersebut
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya
Reflected.NilaiFungsi = HitungNilaiFungsi(Reflected.Posisi);
2b2b2c4. Jika nilai fungsi reflected ternyata lebih baik dari nilai fungsi induk terburuk,
maka ambil posisi reflected untuk menggantikan posisi induk terburuk
Jika tidak maka lakukan proses perhitungan nilai contracted
if Reflected.NilaiFungsi > daftarInduk(end).NilaiFungsi daftarInduk(end) = Reflected; else HitungContracted = true; end
* Lakukan proses perhitungan nilai reflected apabila kondisi sebelumnya terpenuhi (poin 2b2b2d)
if HitungContracted . . .
2b2b2d1. Hitung posisi contracted,
yaitu posisi ditengah-tengah antara centroid dan daftar induk terburuk
Contracted.Posisi = (Centroid + daftarInduk(end).Posisi)/2;
2b2b2d2. Hitung nilai fungsi pada posisi tersebut
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya
Contracted.NilaiFungsi = HitungNilaiFungsi(Contracted.Posisi);
2b2b2c3. Jika nilai fungsi contracted ternyata lebih baik dari nilai fungsi induk terburuk,
maka ambil posisi contracted untuk menggantikan posisi induk terburuk
Jika tidak maka lakukan proses penghapusan induk terburuk
if Contracted.NilaiFungsi > daftarInduk(end).NilaiFungsi daftarInduk(end) = Contracted; else Penghapusan = true; end
* Lakukan proses penghapusan apabila kondisi sebelumnya terpenuhi (poin 2b2b2e)
if Penghapusan . . .
2b2b2e. Beri nilai posisi acak pada posisi induk terburuk
Kemudian hitung nilai fungsi pada posisi tersebut
Jika nilai fungsi pada posisi acak tidak lebih baik dari nilai fungsi induk terburuk,
maka tidak perlu menggunakan posisi acak ini
tmpPosisi = unifrnd(minPosisi, maksPosisi, jumlahDimensi); tmpNilaiFungsi = HitungNilaiFungsi(tmpPosisi); if tmpNilaiFungsi > daftarInduk(end).NilaiFungsi daftarInduk(end).Posisi = tmpPosisi; daftarInduk(end).NilaiFungsi = tmpNilaiFungsi; end
2b2b3. Lakukan update posisi dan nilai fungsi dari populasi dengan indeks induk yang telah ditentukan sebelumnya
populasi(daftarIdxInduk) = daftarInduk;
2b3. Lakukan update kelompok populasi dengan nilai kelompok yang sudah dihitung sebelumnya
populasi(I(j,:)) = daftarKelompok{j};
2c. Urutkan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
daftarNilaiFungsi = [populasi.NilaiFungsi]; [~, idxTerurut]=sort(daftarNilaiFungsi, 'descend'); populasi = populasi(idxTerurut);
2d. Jika nilai fungsi pada populasi yang sedang dihitung lebih baik dari nilai fungsi terbaik
maka ambil posisinya sebagai posisi terbaik
if populasi(1).NilaiFungsi > nilaiFungsiTerbaik nilaiFungsiTerbaik = populasi(1).NilaiFungsi; posisiTerbaik = populasi(1).Posisi; end
Hasil akhir adalah:
Algoritma SCE (Shuffled Complex Evolution) 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 Jumlah Kelompok = 10 Jumlah individu per kelompok = 5 alpha = 3 beta = 5 Iterasi: 1, Posisi terbaik: -0.25821 -0.94161, Nilai Fungsi terbaik: 181.6112 Iterasi: 2, Posisi terbaik: -0.26975 -0.92204, Nilai Fungsi terbaik: 181.6165 Iterasi: 4, Posisi terbaik: -0.27142 -0.9218, Nilai Fungsi terbaik: 181.6165 Iterasi: 5, Posisi terbaik: -0.27116 -0.92298, Nilai Fungsi terbaik: 181.6165 Iterasi: 7, Posisi terbaik: -0.27088 -0.92298, Nilai Fungsi terbaik: 181.6165 Iterasi: 8, Posisi terbaik: -0.27086 -0.92302, Nilai Fungsi terbaik: 181.6165 Iterasi: 9, Posisi terbaik: -0.27084 -0.92303, Nilai Fungsi terbaik: 181.6165 Iterasi: 11, Posisi terbaik: -0.27085 -0.92304, Nilai Fungsi terbaik: 181.6165 Iterasi: 12, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165 Iterasi: 13, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165 Iterasi: 14, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165 Iterasi: 16, Posisi terbaik: -0.27084 -0.92304, Nilai Fungsi terbaik: 181.6165 Iterasi: 17, 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.