Algoritma AIS (Artificial Immune System) dengan teknik CLONALG (Clonal Selection Algorithm) 6

Algoritma AIS (Artificial Immune System) dengan teknik CLONALG (Clonal Selection 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.
AIS (Artificial Immune System) / sistem kekebalan buatan adalah salah satu sistem yang dibuat dengan meniru tingkah laku dari sistem kekebalan manusia. Ada beberapa teknik perhitungan yang dapat digunakan pada algoritma ini. Pada contoh kali ini, Algoritma ini akan menggunakan teknik yang dinamakan CLONALG (Clonal Selection Algorithm). CLONALG sendiri adalah algoritma yang sering dipakai untuk perhitungan optimasi, seperti pada contoh kasus yang dibahas kali ini.

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 (kromosom)
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 jumlah antibodi pada saat pertama kali perhitungan
Diasumsikan dalam kasus ini, jumlah antibodi awal hanya ada 5 saja

Const jumlahAntibodi As Integer = 10

Tentukan jumlah clone antibodi, yaitu seberapa banyak antibodi akan melipatgandakan dirinya dalam setiap perulangan
Diasumsikan dalam kasus ini, jumlah clone adalah 2

Const jumlahClone As Integer = 2

Tentukan jumlah iterasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, jumlah iterasi adalah 50 kali

Const jumlahIterasi As Integer = 50

Tentukan faktor mutasi, yaitu faktor untuk menghitung ketertarikan antibodi pada saat mutasi
Semakin besar nilai faktor mutasi, maka semakin kecil nilai ketertarikan antibodi
Diasumsikan dalam kasus ini, faktor mutasi adalah 8

Const faktorMutasi As Double = 8

Tentukan batas minimal selisih perhitungan fitness pada saat proses seleksi clone
Nantinya proses seleksi clone akan berhenti setelah nilai selisih fitness sudah lebih rendah dari nilai ini
Diasumsikan dalam kasus ini, batas minimal selisih fitness adalah 0.01

Const batasMinimalSelisihFitness As Double = 0.01

Tentukan batas nilai ketertarikan antibodi
Antibodi yang memiliki nilai ketertarikan lebih rendah dari nilai ini akan dibuang dari daftar antibodi
Diasumsikan dalam kasus ini, batas nilai ketertarikan antibodi adalah 0.2

Const batasNilaiKetertarikan As Double = 0.2

Tentukan persentase untuk pembuatan antibodi baru pada setiap perulangan
sebagai contoh, jika persentase = 0.5 dan jumlah antibodi pada saat perulangan = 10, maka akan dibuat 5 antibodi baru
Diasumsikan dalam kasus ini, persentase yang digunakan adalah 0.1

Const persentaseAntibodiBaru As Double = 0.5

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

Langkah-langkah penggunaan algoritma ini adalah

1. Inisialisasi nilai awal semua variabel yang diperlukan
Kemudian lakukan inisialisasi untuk semua antibodi yang digunakan

Dim ais As New AIS(dimensi, jumlahAntibodi, faktorMutasi, minPosisi, maksPosisi)

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class AIS untuk menampung semua data seperti daftar antibodi, posisi terbaik dan fitness terbaik yang ditemukan oleh semua antibodi. Deklarasi Class AIS adalah sebagai berikut:

Public Class AIS
    Public daftarAntibodi As ArrayList  'Menampung antibodi yang digunakan

    Private dimensi As Integer          'dimensi permasalahan
    Private jumlahAntibodi As Integer   'jumlah antibodi awal mula
    Private faktorMutasi As Double      'penentu ketertarikan antibodi pada saat mutasi
    Private minPosisi As Double         'posisi minimal pada setiap solusi
    Private maksPosisi As Double        'posisi maksimal pada setiap solusi

    Private posisiTerbaik As Double()   'Posisi terbaik yang ditemukan dari semua antibodi
    Private fitnessTerbaik As Double    'Semakin tinggi semakin baik

    Public Sub New(ByVal dimensi As Integer, ByVal jumlahAntibodi As Integer, _
                   ByVal minPosisi As Double, ByVal maksPosisi As Double, ByVal faktorMutasi As Double)
        daftarAntibodi = New ArrayList()

        Me.dimensi = dimensi
        Me.jumlahAntibodi = jumlahAntibodi
        Me.faktorMutasi = faktorMutasi
        Me.minPosisi = minPosisi
        Me.maksPosisi = maksPosisi

        Me.posisiTerbaik = New Double(dimensi - 1) {}
        Me.fitnessTerbaik = Double.MinValue

        Console.WriteLine("Inisialisasi antibodi awal pada posisi acak")
        'Inisialisasi nilai awal untuk semua antibodi
        BuatAntibodiBaru(jumlahAntibodi)
    End Sub
	
	. . .
End Class

* Gunakan fungsi ini untuk membuat antibodi baru
Penjelasan mengenai langkah-langkah perhitungan dapat dilihat pada keterangan skrip dibawah ini

Public Sub BuatAntibodiBaru(ByVal jumlahAntibodi As Integer, Optional iterasi As Integer = 0, Optional ByVal isProsesInisialisasi As Boolean = True)

Memasuki perhitungan pada fungsi BuatAntibodiBaru (poin 1a – 1d)

1a. Beri posisi acak untuk tiap-tiap antibodi

antibodi = New Antibody(dimensi, minPosisi, maksPosisi, faktorMutasi)

1b. Hitung fitness untuk masing-masing posisi acak

antibodi.fitness = hitungFitness(antibodi.posisi)

1c. Kemudian masukkan antibodi ke dalam daftar antibodi

daftarAntibodi.Add(antibodi)

1d. Apabila nilai fitness posisi acak lebih baik dari nilai fitness terbaik
maka ambil posisinya sebagai posisi terbaik

If antibodi.fitness > fitnessTerbaik Then
	fitnessTerbaik = antibodi.fitness
	antibodi.posisi.CopyTo(posisiTerbaik, 0)

	. . .
End If

* Lakukan proses pencarian posisi terbaik sebanyak jumlah iterasi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 2 – 5)

Dim posisiTerbaik As Double() = ais.AIS(jumlahClone, jumlahIterasi, batasMinimalSelisihFitness, batasNilaiKetertarikan, persentaseAntibodiBaru)

Memasuki perhitungan pada fungsi AIS (poin 2 – 5)

* Lakukan proses perhitungan sebanyak jumlah iterasi (poin 2 – 5)

2 Lakukan proses seleksi clone antibodi dengan teknik CLONALG (Clonal Selection Algorithm)
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 2a – 2f)

ClonalSelection(jumlahClone, batasMinimalSelisihFitness, iterasi)

2a. Hitung nilai normalisasi fitness pada masing-masing antibodi

2a1. Hitung nilai fitness pada masing-masing antibodi
Apabila nilainya lebih dari nilai fitness tertinggi maka ambil nilainya sebagai nilai fitness tertinggi
Apabila nilainya kurang dari nilai fitness terendah maka ambil nilainya sebagai nilai fitness terendah

For i As Integer = 0 To Me.daftarAntibodi.Count - 1
	daftarAntibodi(i).fitness = hitungFitness(daftarAntibodi(i).posisi)

	If daftarAntibodi(i).fitness > fitnessTertinggi Then
		fitnessTertinggi = daftarAntibodi(i).fitness
	ElseIf daftarAntibodi(i).fitness < fitnessTerendah Then
		fitnessTerendah = daftarAntibodi(i).fitness
	End If
Next

2a2. Hitung normalisasi nilai fitness pada masing-masing antibodi
normalisasi dihitung dengan rumus
normalisasi = (fitness - fitnessTerendah) / (fitnessTertinggi - fitnessTerendah)

For i As Integer = 0 To Me.daftarAntibodi.Count - 1
	daftarAntibodi(i).fitnessNormalisasi = (daftarAntibodi(i).fitness - fitnessTerendah) / (fitnessTertinggi - fitnessTerendah)
Next

2b. Lakukan proses clone pada setiap antibodi

2b1. Lakukan proses perhitungan sebanyak jumlah clone pada masing-masing antibodi

2b1a. Lakukan proses clone

daftarClone(j) = daftarAntibodi(i).Clone()

* Gunakan fungsi ini untuk melakukan clone pada antibodi

Public Function Clone() As Object Implements ICloneable.Clone
	Dim hasilClone As Antibody = TryCast(Me.MemberwiseClone(), Antibody)
	hasilClone.posisi = DirectCast(posisi.Clone(), Double())
	Return hasilClone
End Function

2b1b. Kemudian lakukan proses mutasi pada masing-masing clone

daftarClone(j).Mutasi()

* Gunakan fungsi ini untuk melakukan mutasi pada antibodi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Public Sub Mutasi()
	'Faktor mutasi berbanding terbaik dengan nilai fitness pada antibodi, untuk memastikan bahwa solusi yang lebih baik akan bermutasi lebih sedikit

	'Hitung faktor ketertarikan mutasi dengan rumus
	'ketertarikan mutasi =  (1 / faktor mutasi) * konstanta e dipangkatkan (-1 * normalisasi nilai fitness)
	Dim KetertarikanMutasi As Double = (1.0 / faktorMutasi) * Math.Exp(-1 * fitnessNormalisasi)

	'Lakukan perhitungan untuk setiap posisi pada masing-masing antibodi
	For i As Integer = 0 To dimensi - 1
		'Hitung posisi yang baru pada setiap dimensinya
		posisi(i) += KetertarikanMutasi * rnd.NextDouble()

		'apabila nilai posisi baru melebihi batas nilai minimal dan maksimal posisi,
		'maka kembalikan nilai posisi nya agar kembali dalam rentang nilai posisi yang diperbolehkan
		If posisi(i) > maksPosisi Then
			posisi(i) = maksPosisi
		End If
		If posisi(i) < minPosisi Then
			posisi(i) = minPosisi
		End If
	Next
End Sub

2b1c. Hitung nilai fitness untuk clone yang telah bermutasi
Apabila nilai fitness clone lebih baik dari nilai fitness antibodi,
maka ambil clone ini sebagai clone terbaik pada antibodi tersebut

daftarClone(j).fitness = hitungFitness(daftarClone(j).posisi)
If daftarClone(j).fitness > daftarClone(idxCloneTerbaik).fitness Then
	idxCloneTerbaik = j
End If

2b2. Apabila nilai fitness clone lebih baik dari nilai fitness antibodi,
maka clone tersebut akan menggantikan antibodi induk
Jika tidak maka antibodi induk akan tetap berada pada daftar antibodi

If daftarClone(idxCloneTerbaik).fitness > daftarAntibodi(i).fitness Then
	daftarAntibodi.Insert(i, daftarClone(idxCloneTerbaik))
	daftarAntibodi.RemoveAt(i + 1)

2b3. Apabila nilai fitness clone lebih baik dari nilai fitness terbaik
maka ambil posisi clone ini sebagai posisi terbaik

If daftarClone(idxCloneTerbaik).fitness > fitnessTerbaik Then
	fitnessTerbaik = daftarClone(idxCloneTerbaik).fitness
	daftarClone(idxCloneTerbaik).posisi.CopyTo(posisiTerbaik, 0)

2c. Hitung jumlah nilai fitness pada daftar antibodi yang baru

jumlahFitness = 0
For i As Integer = 0 To daftarAntibodi.Count - 1
	Dim c As Antibody = DirectCast(daftarAntibodi(i), Antibody)
	jumlahFitness = jumlahFitness + c.fitness
Next

2d. Hitung rata-rata fitness, yaitu jumlah fitness / jumlah antibodi

rata2FitnessSesudah = jumlahFitness / daftarAntibodi.Count

2e. Hitung selish rata-rata fitness sekarang dengan yang sebelumnya
Jika selisih nilai fitness masih lebih dari atau sama dengan nilai batas minimal selish fitness,
maka simpan nilai rata-rata ini, kemudian ulangi proses seleksi clone
Jika selisih nilai fitness sudah kurang dari batas minimal fitness maka perhitungan seleksi clone sudah selesai

If (rata2FitnessSesudah - rata2FitnessSebelum) >= batasMinimalSelisihFitness Then
	rata2FitnessSebelum = rata2FitnessSesudah
End If

2f. Lakukan perulangan nomor 2a - 2e sampai selisih nilai fitness sudah kurang dari batas minimal fitness

Loop Until (rata2FitnessSesudah - rata2FitnessSebelum) < batasMinimalSelisihFitness

3 Lakukan proses eliminasi batas nilai ketertarikan pada setiap antibodi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3a - 3c)

EliminasiBatasNilaiKetertarikan(batasNilaiKetertarikan)

3a. Hitung nilai ketertarikan pada masing-masing pasangan antibodi

3a1. Rumus perhitungan nilai ketertarikan antara 2 antibodi dihitung dengan metode Euclidean
contoh kasusnya adalah, apabila antibodi A berdimensi 2 berada pada posisi (3.0, 4.0) dan antibodi B (5.0, 9.0),
maka jaraknya adalah sqrt((5 - 3)^2 + (9 - 4)^2) = sqrt(4 + 25) = sqrt(29) = 5.4

Dim ketertarikan As Double = 0.0
For k As Integer = 0 To dimensi - 1
	ketertarikan += (daftarAntibodi(i).posisi(k) - daftarAntibodi(j).posisi(k)) * (daftarAntibodi(i).posisi(k) - daftarAntibodi(j).posisi(k))
Next k
nilaiKetertarikan(i, j) = Math.Sqrt(ketertarikan)

3b. Catat daftar antibodi mula-mula , sebelum dilakukan eliminasi

Dim tmpdaftarAntibodi As Antibody() = New Antibody(daftarAntibodi.Count - 1) {}
For k As Integer = 0 To daftarAntibodi.Count - 1
	tmpdaftarAntibodi(k) = daftarAntibodi(k)
Next

3c. Lakukan perulangan pada setiap antibodi
Apabila nilai ketertarikan antara antibodi i dan j kurang dari batas minimal nilai ketertarikan,
maka lakukan pembuangan antibodi dengan nilai fitness terendah antara i dan j

For i As Integer = 0 To tmpdaftarAntibodi.Length - 1
	For j As Integer = 0 To tmpdaftarAntibodi.Length - 1
		If (i < j) AndAlso (nilaiKetertarikan(i, j) < batasNilaiKetertarikan) Then
			If tmpdaftarAntibodi(i).fitness < tmpdaftarAntibodi(j).fitness Then
				daftarAntibodi.Remove(tmpdaftarAntibodi(i))
			Else
				daftarAntibodi.Remove(tmpdaftarAntibodi(j))
			End If
		End If
	Next
Next

4. Lakukan proses eliminasi antibodi agar jumlah antibodi tetap seperti jumlah semula
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4a - 4b)

EliminasiBatasJumlahAntibodi(persentaseAntibodiBaru, jumlahAntibodiAwalMula)

4a. Tentukan jumlah antibodi baru yang akan dibuat dengan rumus jumlah antibodi sekarang * persentase antibodi baru

jumlahAntibodi = daftarAntibodi.Count
Dim jumlahAntibodiBaru As Integer = CInt(Math.Round(jumlahAntibodi * persentaseAntibodiBaru))

4b. Lakukan pembuangan antibodi dengan nilai fitness terendah apabila jumlah Antibodi sekarang + jumlah Antibodi Baru melebihi jumlah Antibodi awal mula

Do While jumlahAntibodi + jumlahAntibodiBaru > jumlahAntibodiAwalMula
	Dim idxFitnessTerendah As Integer = 0
	For i As Integer = 1 To daftarAntibodi.Count - 1
		If daftarAntibodi(i).fitness < daftarAntibodi(idxFitnessTerendah).fitness Then
			idxFitnessTerendah = i
		End If
	Next

	daftarAntibodi.Remove(daftarAntibodi(idxFitnessTerendah))
	jumlahAntibodi = daftarAntibodi.Count
Loop

5. Lakukan pembuatan antibodi baru sebanyak jumlah antibodi baru
Langkah-langkah perhitungan sama seperti penjelasan pada poin nomor 1 diatas

BuatAntibodiBaru(CInt(Math.Round(jumlahAntibodi * persentaseAntibodiBaru)), iterasi, False)

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Antibody untuk menampung semua data posisi beserta nilai fungsinya. Deklarasi Class Solusi adalah sebagai berikut:

Public Class Antibody
    Implements ICloneable

    Public posisi As Double()
    Public fitness As Double
    Public fitnessNormalisasi As Double

    Private dimensi As Integer
    Private faktorMutasi As Double
    Private minPosisi As Double
    Private maksPosisi As Double
    Private Shared rnd As New Random(0)

    Public Sub New(dimensi As Integer, faktorMutasi As Double, minPosisi As Double, maksPosisi As Double)
        Me.dimensi = dimensi
        Me.faktorMutasi = faktorMutasi
        Me.minPosisi = minPosisi
        Me.maksPosisi = maksPosisi

        posisi = New Double(dimensi - 1) {}
        For i As Integer = 0 To dimensi - 1
            posisi(i) = (maksPosisi - minPosisi) * rnd.NextDouble() + minPosisi
        Next
    End Sub

	. . .
End Class

Hasil akhir adalah: (klik untuk perbesar gambar)

Dapat dilihat bahwa hasil akhir perhitungan tidak sama dengan x = -0.270845, and y = -0.923039, tetapi sangat mendekati posisi tersebut. Jika ingin mendapatkan jawaban yang lebih mirip lagi, maka silahkan lakukan penambahan jumlah iterasi, dengan resiko bahwa perhitungan yang dilakukan akan semakin lama.

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.