Algoritma ICA (Imperialist Competitive 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.
Algoritma ini mengambil prinsip kompetisi kerajaan dalam menaklukan kerajaan lain, yang dalam hal ini disebut sebagai imperial. Masing-masing imperial pada mulanya akan memiliki sejumlah koloni, kemudian dalam setiap perulangan, masing-masing imperial akan melakukan peperangan untuk memperebutkan koloni terlemah dari imperial yang kalah. Imperial yang sudah tidak memiliki koloni dan kalah dalam berperang nantinya akan menjadi koloni dari imperial pemenang.
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 dimensi permasalahan dalam sebuah solusi
Diasumsikan dalam kasus ini, dimensi bernilai 2 karena ada 2 dimensi yang akan dicari solusinya yaitu x dan y
Const dimensi As Integer = 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
Const minPosisi As Double = -2 Const maksPosisi As Double = +2
* Tentukan jumlah iterasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, jumlah iterasi adalah 500 kali
Const jumlahIterasi As Integer = 500
* Tentukan ukuran populasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, ukuran populasi yang digunakan adalah 20
Const ukuranPopulasi As Integer = 20
* Tentukan jumlah kerajaan, atau disebut juga sebagai imperial
Nantinya setiap imperial akan memiliki koloni dengan jumlah yang berbeda-beda
Diasumsikan dalam kasus ini, jumlah imperial yang digunakan adalah 3
Const jumlahImperial As Integer = 3
* Tentukan nilai beta, yaitu koefisien asimilasi koloni ke dalam imperial
Diasumsikan dalam kasus ini, nilai beta adalah 1.5
Const beta As Double = 1.5
* Tentukan probabilitas revolusi koloni pada imperial koloni tersebut
Diasumsikan dalam kasus ini, probabilitas revolusi adalah 0.05
Const probRevolusi As Double = 0.05
* Tentukan nilai zeta, yaitu koefisien rata-rata nilai fungsi dari koloni dalam imperial
Diasumsikan dalam kasus ini, nilai zeta adalah 0.2
Const zeta As Double = 0.2
Langkah-langkah penggunaan algoritma ini adalah
* Lakukan proses pencarian posisi terbaik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 1 – 7)
Dim posisiTerbaik() As Double = ICA(dimensi, minPosisi, maksPosisi, jumlahIterasi, ukuranPopulasi, _ jumlahImperial, beta, probRevolusi, zeta)
Memasuki perhitungan pada fungsi ICA
* Inisialisasi individu yang digunakan sebanyak ukuran populasi
1. Lakukan perulangan sebanyak ukuran populasi (poin 1a – 1b)
For i As Integer = 0 To ukuranPopulasi - 1 . . .
1a. Beri posisi acak pada masing-masing individu sebanyak jumlah dimensi
For j As Integer = 0 To dimensi - 1 populasi(i).posisi(j) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi Next
1b. Hitung nilai fungsi pada posisi tersebut
Penjelasan tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
populasi(i).nilaiFungsi = hitungNilaiFungsi(populasi(i).posisi)
* Gunakan fungsi ini untuk menghitung nilai fungsi yang diinginkan
Fungsi yang diketahui adalah fungsi Himmelblau, dengan rumus f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2
Public Function HitungNilaiFungsi(x1 As Double, y As Double) As Double Dim hasil As Double = Math.Pow(x1 * x1 + y - 11, 2) + Math.Pow(x1 + y * y - 7, 2) Return hasil End Function
2. Urutkan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
Array.Sort(populasi)
3. Ambil posisi individu pertama sebagai posisi terbaik sementara
Array.Copy(populasi(0).posisi, PosisiTerbaik, dimensi) nilaiFungsiTerbaik = populasi(0).nilaiFungsi
4. Masukkan individu terbaik sebagai posisi awal dari imperial
Sedangkan sisanya akan dianggap sebagai koloni
Dim imperial(jumlahImperial - 1) As Imperial For i As Integer = 0 To jumlahImperial - 1 imperial(i) = New Imperial(populasi(i).posisi, populasi(i).nilaiFungsi) Next Dim daftarKoloni(ukuranPopulasi - jumlahImperial - 1) As Koloni For i As Integer = jumlahImperial To ukuranPopulasi - 1 daftarKoloni(i - jumlahImperial) = populasi(i).Clone Next
5. Masukkan koloni ke dalam imperial secara acak
Teknik yang digunakan adalah teknik Seleksi Roulette (Roulette Wheel Selection)
Sehingga masing-masing imperial dapat memiliki jumlah koloni yang berbeda-beda
For i As Integer = 0 To daftarKoloni.Length - 1 Dim idxImperialAcak As Integer = -1 While idxImperialAcak = -1 idxImperialAcak = RouletteWheelSelection(imperial, rnd) End While imperial(idxImperialAcak).daftarKoloni.Add(daftarKoloni(i)) Next
* Gunakan fungsi ini untuk melakukan teknik Seleksi Roulette (Roulette Wheel Selection)
Nilai yang lebih baik akan memiliki kemungkinan yang lebih besar untuk terpilih
Dalam kasus ini, nilai yang dibandingkan adalah nilai fungsi dari masing-masing earthworm
Public Function RouletteWheelSelection(ByVal imperial() As Imperial, ByVal rnd As Random, Optional isTotalNilaiFungsi As Boolean = False) As Integer Dim bobot(imperial.Length - 1) As Double Dim totalBobot As Double = 0 For i As Integer = 0 To bobot.Length - 1 totalBobot += 1 / IIf(isTotalNilaiFungsi, imperial(i).totalNilaiFungsi, imperial(i).nilaiFungsi) bobot(i) = totalBobot Next Dim probabilitasKumulatif As Double = rnd.NextDouble * totalBobot Dim idxTerpilih As Integer = -1 For i As Integer = 0 To bobot.Length - 1 If bobot(i) > probabilitasKumulatif Then idxTerpilih = i Exit For End If Next Return idxTerpilih End Function
6. Hitung total nilai fungsi dari masing-masing imperial
total nilai fungsi dihitung dengan rumus:
total nilai fungsi = nilai fungsi imperial + zeta * rata2 nilai fungsi koloni
For i As Integer = 0 To jumlahImperial - 1 imperial(i).totalNilaiFungsi = imperial(i).nilaiFungsi If imperial(i).daftarKoloni.Count > 0 Then Dim totalNilaiFungsi As Double = 0 For j As Integer = 0 To imperial(i).daftarKoloni.Count - 1 totalNilaiFungsi += imperial(i).daftarKoloni(j).nilaiFungsi Next totalNilaiFungsi /= imperial(i).daftarKoloni.Count imperial(i).totalNilaiFungsi += zeta * totalNilaiFungsi End If Next
* Lakukan proses pencarian posisi terbaik (poin 7)
7. Lakukan proses perhitungan sebanyak jumlah iterasi (poin 7a – 7f)
Dim iterasi As Integer = 0 Do While iterasi < jumlahIterasi iterasi += 1 . . .
* Memasuki proses asimilasi koloni ke dalam imperial (poin 7a)
7a. Lakukan perulangan pada masing-masing dimensi koloni dalam imperial (poin 7a1 - 7a3)
For i As Integer = 0 To jumlahImperial - 1 For j As Integer = 0 To imperial(i).daftarKoloni.Count - 1 For k As Integer = 0 To imperial(i).daftarKoloni(j).posisi.Length - 1 . . .
7a1. Hitung posisi koloni yang baru dengan rumus:
posisi baru = posisi + beta * nilai acak * selisih posisi imperial dan koloni
imperial(i).daftarKoloni(j).posisi(k) += beta * rnd.NextDouble * (imperial(i).posisi(k) - imperial(i).daftarKoloni(j).posisi(k))
7a2. Jika posisi individu tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
If imperial(i).daftarKoloni(j).posisi(k) < minPosisi Then imperial(i).daftarKoloni(j).posisi(k) = minPosisi ElseIf imperial(i).daftarKoloni(j).posisi(k) > maksPosisi Then imperial(i).daftarKoloni(j).posisi(k) = maksPosisi End If
7a3. Hitung nilai fungsi pada posisi koloni yang baru
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya
imperial(i).daftarKoloni(j).nilaiFungsi = hitungNilaiFungsi(imperial(i).daftarKoloni(j).posisi)
* Memasuki proses revolusi koloni pada imperial (poin 7b1 - 7b2)
7b1. Tentukan nilai sigma, yaitu 10 persen dari selisih posisi maksimal dan posisi minimal
Dim sigma As Double = 0.1 * (maksPosisi - minPosisi)
7b2. Lakukan perhitungan pada masing-masing imperial (poin 7b2a - 7b2e)
For i As Integer = 0 To jumlahImperial - 1 . . .
7b2a. Hitung posisi calon imperial baru dengan rumus:
posisi baru = posisi + sigma * distribusi normal acak
Jika posisi tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
Dim posisiBaru(dimensi - 1) As Double For j As Integer = 0 To dimensi - 1 posisiBaru(j) = imperial(i).posisi(j) + sigma * HitungDistribusiNormalAcak(rnd) If posisiBaru(j) < minPosisi Then posisiBaru(j) = minPosisi ElseIf posisiBaru(j) > maksPosisi Then posisiBaru(j) = maksPosisi End If Next
* Gunakan fungsi ini untuk menghitung distribusi normal acak
Sehingga nilai yang berada ditengah-tengah akan memiliki kemungkinan muncul yang lebih banyak,
dan nilai yang berada dibagian ujung akan memiliki kemungkinan muncul yang lebih sedikit
Public Function HitungDistribusiNormalAcak(ByVal rnd As Random, Optional ByVal mean As Double = 0, Optional ByVal stdDev As Double = 1) As Double Dim u1 As Double = rnd.NextDouble() Dim u2 As Double = rnd.NextDouble() Dim rndStdNormal As Double = Math.Sqrt(-2.0 * Math.Log(u1)) * Math.Sin(2.0 * Math.PI * u2) 'random normal(0,1) Dim rndNormal As Double = mean + stdDev * rndStdNormal 'random normal(mean, stdDev^2) Return rndNormal End Function
7b2b. Tentukan sebuah indeks dimensi acak
Ganti posisi calon imperial pada dimensi tersebut sesuai dengan posisi baru
Dim idxDimensiAcak As Integer = rnd.Next(dimensi) Dim calonImperialBaru As Imperial = imperial(i).Clone calonImperialBaru.posisi(idxDimensiAcak) = posisiBaru(idxDimensiAcak)
7b2c. Hitung nilai fungsi pada posisi calon imperial baru
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya
calonImperialBaru.nilaiFungsi = hitungNilaiFungsi(calonImperialBaru.posisi)
7b2d. Jika nilai fungsi calon imperial baru lebih dari nilai fungsi imperial
Maka ambil posisi imperial baru sebagai posisi imperial yang sebenarnya
If calonImperialBaru.nilaiFungsi > imperial(i).nilaiFungsi Then Array.Copy(calonImperialBaru.posisi, imperial(i).posisi, dimensi) imperial(i).nilaiFungsi = calonImperialBaru.nilaiFungsi End If
7b2e. Lakukan perhitungan pada masing-masing koloni dalam imperial tersebut (poin 7b2e1 - 7b2e4)
For j As Integer = 0 To imperial(i).daftarKoloni.Count - 1 . . .
7b2e1. Tentukan nilai acak antara 0 sampai dengan 1
Lakukan perhitungan berikutnya apabila nilai acak tersebut kurang dari parameter probabilitas revolusi
If rnd.NextDouble <= probRevolusi Then . . .
7b2e2. Lakukan perulangan pada masing-masing dimensi posisi calon koloni baru dengan rumus:
posisi baru = posisi + sigma * distribusi normal acak
Jika posisi tersebut ternyata diluar batas posisi yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut
posisiBaru = New Double(dimensi - 1) {} For k As Integer = 0 To dimensi - 1 posisiBaru(k) = imperial(i).daftarKoloni(j).posisi(k) + sigma * HitungDistribusiNormalAcak(rnd) If imperial(i).daftarKoloni(j).posisi(k) < minPosisi Then imperial(i).daftarKoloni(j).posisi(k) = minPosisi ElseIf imperial(i).daftarKoloni(j).posisi(k) > maksPosisi Then imperial(i).daftarKoloni(j).posisi(k) = maksPosisi End If Next
7b2e3. Tentukan sebuah indeks dimensi acak
Ganti posisi koloni pada dimensi tersebut sesuai dengan posisi calon koloni baru
idxDimensiAcak = rnd.Next(dimensi) imperial(i).daftarKoloni(j).posisi(idxDimensiAcak) = posisiBaru(idxDimensiAcak)
7b2e4. Hitung nilai fungsi pada posisi koloni baru
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya
imperial(i).daftarKoloni(j).nilaiFungsi = hitungNilaiFungsi(imperial(i).daftarKoloni(j).posisi)
* Memasuki proses kompetisi koloni dalam imperial (poin 7c)
7c. Lakukan perhitungan pada masing-masing koloni dalam masing-masing imperial
Jika nilai fungsi sebuah koloni lebih baik dari nilai fungsi imperial,
maka lakukan pertukaran posisi dan nilai fungsi dari imperial dan koloni tersebut
For i As Integer = 0 To jumlahImperial - 1 For j As Integer = 0 To imperial(i).daftarKoloni.Count - 1 If imperial(i).daftarKoloni(j).nilaiFungsi > imperial(i).nilaiFungsi Then Dim tmpPosisi() As Double = imperial(i).daftarKoloni(j).posisi Dim tmpNilaiFungsi As Double = imperial(i).daftarKoloni(j).nilaiFungsi imperial(i).daftarKoloni(j).posisi = imperial(i).posisi imperial(i).daftarKoloni(j).nilaiFungsi = imperial(i).nilaiFungsi imperial(i).posisi = tmpPosisi imperial(i).nilaiFungsi = tmpNilaiFungsi End If Next Next
* Memasuki proses update total nilai fungsi imperial (poin 7d)
7d. Hitung total nilai fungsi dari masing-masing imperial
total nilai fungsi dihitung dengan rumus:
total nilai fungsi = nilai fungsi imperial + zeta * rata2 nilai fungsi koloni
For i As Integer = 0 To jumlahImperial - 1 imperial(i).totalNilaiFungsi = imperial(i).nilaiFungsi If imperial(i).daftarKoloni.Count > 0 Then Dim totalNilaiFungsi As Double = 0 For j As Integer = 0 To imperial(i).daftarKoloni.Count - 1 totalNilaiFungsi += imperial(i).daftarKoloni(j).nilaiFungsi Next totalNilaiFungsi /= imperial(i).daftarKoloni.Count imperial(i).totalNilaiFungsi += zeta * totalNilaiFungsi End If Next
* Memasuki proses kompetisi diantara masing-masing imperial (poin 7e)
7e. Lakukan perhitungan berikutnya apabila jumlah imperial yang ada lebih dari 1 (poin 7e1 - 7e2)
If jumlahImperial > 1 Then . . .
7e1. Tentukan imperial terburuk, yaitu imperial dengan nilai fungsi terendah
Dim idxImperialTerburuk As Integer = 0 Dim imperialTerburuk As Imperial = imperial(idxImperialTerburuk) For i As Integer = 1 To jumlahImperial - 1 If imperial(i).totalNilaiFungsi < imperialTerburuk.totalNilaiFungsi Then idxImperialTerburuk = i imperialTerburuk = imperial(idxImperialTerburuk) End If Next
7e2. Lakukan perhitungan berikut apabila imperial terburuk masih memiliki koloni (poin 7e2a - 7e2c)
If imperialTerburuk.daftarKoloni.Count > 0 Then . . .
7e2a. Tentukan koloni terburuk, yaitu koloni dengan nilai fungsi terendah
Dim idxKoloniTerburuk As Integer = 0 Dim KoloniTerburuk As Koloni = imperialTerburuk.daftarKoloni(idxKoloniTerburuk) For i As Integer = 1 To imperialTerburuk.daftarKoloni.Count - 1 If imperialTerburuk.daftarKoloni(i).nilaiFungsi < KoloniTerburuk.nilaiFungsi Then idxKoloniTerburuk = i KoloniTerburuk = imperialTerburuk.daftarKoloni(idxKoloniTerburuk) End If Next
7e2b. Tentukan imperial pemenang secara acak
Teknik yang digunakan adalah teknik Seleksi Roulette (Roulette Wheel Selection)
Imperial acak yang ditemukan tidak boleh sama dengan imperial terburuk
Dim idxImperialPemenang As Integer = idxImperialTerburuk While idxImperialPemenang = idxImperialTerburuk idxImperialPemenang = RouletteWheelSelection(imperial, rnd, True) End While Dim imperialPemenang As Imperial = imperial(idxImperialPemenang)
7e2c. Pindahkan koloni terburuk dari imperial yang kalah (terburuk) kepada imperial pemenang
imperialPemenang.daftarKoloni.Add(KoloniTerburuk) imperialTerburuk.daftarKoloni.Remove(KoloniTerburuk)
7e3. Lakukan perhitungan berikut apabila imperial terburuk sudah tidak memiliki koloni (poin 7e3a - 7e3c)
. . . ElseIf imperialTerburuk.daftarKoloni.Count = 0 Then . . .
7e3a. Tentukan imperial pemenang secara acak
Teknik yang digunakan adalah teknik Seleksi Roulette (Roulette Wheel Selection)
Imperial acak yang ditemukan tidak boleh sama dengan imperial terburuk
Dim idxImperialPemenang As Integer = idxImperialTerburuk While idxImperialPemenang = idxImperialTerburuk idxImperialPemenang = RouletteWheelSelection(imperial, rnd, True) End While Dim imperialPemenang As Imperial = imperial(idxImperialPemenang)
7e3b. Masukkan posisi dan nilai fungsi imperial terburuk ke dalam koloni imperial pemenang
Dim koloni As New Koloni(dimensi - 1) koloni.posisi = imperialTerburuk.posisi koloni.nilaiFungsi = imperialTerburuk.nilaiFungsi imperialPemenang.daftarKoloni.Add(koloni)
7e3c. Hapus imperial terburuk dari daftar imperial yang ada
Dim tmpImperial(jumlahImperial - 2) As Imperial Dim idxTmpImperial As Integer = 0 For i As Integer = 0 To jumlahImperial - 1 If i <> idxImperialTerburuk Then tmpImperial(idxTmpImperial) = imperial(i).Clone idxTmpImperial += 1 End If Next imperial = tmpImperial jumlahImperial -= 1
7f. Lakukan perhitungan pada masing-masing imperial
Jika nilai fungsi imperial tersebut lebih baik dari nilai fungsi secara umum,
maka ambil posisi imperial tersebut sebagai posisi terbaik
For i As Integer = 0 To jumlahImperial - 1 If imperial(i).nilaiFungsi > nilaiFungsiTerbaik Then Array.Copy(imperial(i).posisi, PosisiTerbaik, dimensi) nilaiFungsiTerbaik = imperial(i).nilaiFungsi End If Next
* Agar dapat menjalankan skrip diatas, maka diperlukan 2 buah Class, yaitu Class Koloni untuk menampung data posisi dan nilai fungsi dari masing-masing koloni, dan Class Imperial untuk menampung data posisi, nilai fungsi, dan daftar koloni yang ada. Deklarasi kedua class tersebut adalah sebagai berikut:
Public Class Imperial Implements ICloneable Public posisi() As Double Public nilaiFungsi As Double Public daftarKoloni As New List(Of Koloni)() Public totalNilaiFungsi As Double Public Sub New(ByVal posisi() As Double, nllaiFungsi As Double) Me.posisi = posisi Me.nilaiFungsi = nllaiFungsi Me.totalNilaiFungsi = 0.0 End Sub 'Gunakan fungsi ini untuk melakukan clone pada masing-masing koloni Public Function Clone() As Object Implements ICloneable.Clone Dim hasilClone As Imperial = TryCast(Me.MemberwiseClone(), Imperial) hasilClone.posisi = DirectCast(posisi.Clone(), Double()) Return hasilClone End Function End Class Public Class Koloni Implements IComparable(Of Koloni) Implements ICloneable Public posisi() As Double Public nilaiFungsi As Double Public Sub New(ByVal dimensi As Integer) Me.posisi = New Double(dimensi - 1) {} Me.nilaiFungsi = 0.0 End Sub 'Gunakan fungsi ini untuk melakukan pengurutan dari nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah) Public Function CompareTo(ByVal KoloniLain As Koloni) As Integer Implements IComparable(Of Koloni).CompareTo If Me.nilaiFungsi > KoloniLain.nilaiFungsi Then Return -1 ElseIf Me.nilaiFungsi < KoloniLain.nilaiFungsi Then Return 1 Else Return 0 End If End Function 'Gunakan fungsi ini untuk melakukan clone pada masing-masing koloni Public Function Clone() As Object Implements ICloneable.Clone Dim hasilClone As Koloni = TryCast(Me.MemberwiseClone(), Koloni) hasilClone.posisi = DirectCast(posisi.Clone(), Double()) Return hasilClone End Function End Class
Hasil akhir adalah: (klik untuk perbesar gambar)
Contoh modul / source code dalam bahasa VB (Visual Basic) 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.