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.
Grafik Himmelblau

Sedangkan Grafik fungsi Himmelblau untuk sebaran titik dengan rentang minimal -2 dan maksimal 2 adalah sebagai berikut.
Grafik Himmelblau -2sd2
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

* 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

* Tentukan jumlah maksimal iterasi yang digunakan
Diasumsikan dalam kasus ini, jumlah maksimal iterasi adalah 500 kali

* 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

* 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

* 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

* Tentukan radius, yaitu koefisien untuk menghitung radius dari masing-masing telur
Diasumsikan dalam kasus ini, radius bernilai 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

* 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

* 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

* 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


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)

Memasuki perhitungan pada fungsi CSO

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

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

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

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

3b. Hitung total telur yang dihasilkan dari perhitungan sebelumnya

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

3d. Catat nilai radius untuk masing-masing telur

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

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

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

3e1d. Masukkan posisi tersebut sebagai posisi telur yang baru

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)

3f1a1. Jika kedua telur berada dalam posisi yang sama, maka buang telur kedua

3f1a2. Lanjutkan perhitungan ke telur berikutnya
Apabila sudah tidak ada telur berikutnya, maka lanjutkan perhitungan ke cuckoo berikutnya

3f1b. Simpan posisi telur yang tidak mengalami pembuangan

3g. Hitung nilai fungsi masing-masing telur pada masing-masing cuckoo
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

* Gunakan fungsi ini untuk menghitung nilai fungsi himmelblau dengan rumus:
f(x, y) = (x ^ 2 + y – 11) ^ 2 + (x + y ^ 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

3h2. Lakukan pengurutan nilai fungsi berdasarkan nilai tertinggi ke nilai terendah

3h3. Tentukan titik pusat cuckoo terbaik, yaitu indeks pertama pada nilai fungsi terurut

3h4. Jika jumlah cuckoo yang ada tidak melebihi jumlah maksimal cuckoo,
maka lakukan perhitungan berikut (poin 3h4a – 3h4b)

3h4a. Hapus populasi awal

3h4b. Lakukan perhitungan sebanyak jumlah maksimal cuckoo
Masukkan posisi telur, titik pusat dan nilai fungsi secara terurut

3i. Catat nilai fungsi yang baru, yaitu nilai fungsi pada urutan pertama

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

* 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

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

3k3. Setelah menentukan cluster dari masing-masing telur,
catat posisi telur dan nilai fungsi untuk masing-masing cluster

3k4. Tentukan mean dari masing-masing cluster

3k5. Lakukan pengurutan mean berdasarkan nilai tertinggi ke nilai terendah

3k6. Setelah mengetahui indeks cluster terbaik,
maka gunakan posisi cuckoo terbaik pada cluster tersebut sebagai posisi tujuan dari cuckoo sekarang

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)

3l1a. Lakukan perhitungan posisi yang baru pada masing-masing cuckoo

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

3l1c. Lakukan update daftar posisi cluster dengan posisi yang baru
Kemudian hitung kembali mean sebagai titik pusat cluster tersebut

3l1d. Hitung jumlah cuckoo yang baru

3m. Hapus populasi yang lama
Kemudian masukkan masing-masing cuckoo yang baru ke dalam populasi

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


Hasil akhir adalah:


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.


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

10 pemikiran di “Algoritma CSO (Cuckoo Search Optimization)

    • pip Penulis

      Fungsi tersebut tentu saja dapat digunakan untuk menggantikan fungsi Himmelblau yang saya gunakan dalam pembahasan ini. Yang anda perlu lakukan adalah mengganti skrip fungsi yang sudah ada.

      Silahkan mengganti skrip ini
      y = (x(:,1).^2 + x(:,2) - 11).^ 2 + (x(:,1) + x(:,2).^2 - 7).^ 2;
      Menjadi fungsi yang anda gunakan
      y = x(:,1) .* (3 .^ (x(:,2) + 0.01 * 19.92)) * 0.35077;

      • Made

        Terima kasih.

        Saya menemukan error saat mengganti script function:

        function y = costFunction(x)
        AE = [1.2 2 4.5 3 4 22 2 5 18 4 1 2.1];
        LOC = [3000 2000 4250 10000 15000 40530 4050 31845 114280 23106 1369 1611];
        SF = [19.92 18.83 18.68 10.31 19.28 8.41 7.42 19.73 27.23 20.82 15.36 19.11];
        EM = [0.35077 0.453841835 0.647308126 1.121349587 1.084102861 0.23786807 0.196509112 1.083720964 0.373383092 0.649964747 0.225013699 0.410914058];
        MMRE = 0;
        nDataset = 12;

        A = x(:,1);
        B = x(:,2);

        for j = 1:nDataset
        E(j) = B + 0.01 * SF(j);
        PM(j) = A .* ((LOC(j)/1000) .^ E(j)) * EM(j);
        MRE(j) = ((abs(AE(j) – PM(j))) / AE(j));
        MMRE = MMRE + MRE(j);
        end

        y = MMRE / nDataset;

        Dengan pesan error:
        ??? In an assignment A(I) = B, the number of elements in B and I must be the same.

        Mohon penjelasannya.

        • pip Penulis

          Pesan kesalahan tersebut disebabkan karena anda ingin memasukkan nilai ke dalam variabel dengan dimensi yang tidak sama. Dan karena anda tidak mendeklarasikan ukuran dari beberapa variabel, maka variabel tersebut dianggap berukuran 1 dimensi

          Silahkan ganti skrip ini
          for j = 1:nDataset
          E(j) = B + 0.01 * SF(j);
          PM(j) = A .* ((LOC(j)/1000) .^ E(j)) * EM(j);
          MRE(j) = ((abs(AE(j) – PM(j))) / AE(j));
          MMRE = MMRE + MRE(j);
          end

          menjadi
          for j = 1:nDataset
          E(:,j) = B + 0.01 * SF(j);
          PM(:,j) = A .* ((LOC(j)/1000) .^ E(:,j)) * EM(j);
          MRE(:,j) = ((abs(AE(j) - PM(:,j))) / AE(j));
          MMRE = MMRE + MRE(:,j);
          end

    • pip Penulis

      Untuk memahami cara kerja, maka saya harus memahami terlebih dahulu sistem rekomendasi bagaimanakah yang anda miliki. Silahkan diceritakan lebih lanjut.

      • siti

        Saya baca jurnal judulnya “An effective collaborative movie recommender system with cuckoo search”
        Jadi didalamnya dia memakai collbaorative filtering untuk rekomendasinya dan k-means clustering untuk pengelompokkan data, lalu cuckoo searchnya untuk apa ya?

        • pip Penulis

          Jika hanya dengan membaca judul tersebut, maka saya juga tidak memahami kegunaan algoritma ini dalam topik tersebut.Karena terdapat 2 algoritma lain yaitu Collaborative Filtering dan K-Means clustering, maka tentunya dalam jurnal tersebut dijelaskan cara menghubungkan ketiga algoritma ini dalam memecahkan topik yang tersedia. Silahkan anda baca kembali jurnal tersebut.