Algoritma ACO (Ant Colony Optimization) 27

Algoritma ACO (Ant Colony Optimization) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik tujuan dengan jarak paling rendah.
Ant Colony Optimization adalah teknik probabilitas untuk menyelesaikan permasalahan, berdasarkan tingkah laku semut dalam sebuah koloni yang mencari sumber makanan. Teknik ini dapat digunakan untuk menemukan solusi dari permasalahan kompleks untuk mendapatkan jalur optimal dalam grafik.

Diasumsikan ada sebaran titik yang harus dilalui semuanya
semua titik terhubung secara langsung dengan titik-titik lainnya, dan semua jalurnya dapat dilalui 2 arah
Jarak yang dihasilkan untuk masing-masing titik akan diambil secara acak antara angka 1 sampai 8
Tentukan Jalur yang harus diambil untuk mengelilingi semua titik dengan jarak terpendek

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan alpha dan beta
Alpha dan Beta adalah koefisien yang digunakan untuk perhitungan taueta
Semakin besar nilai alpha, semakin besar nilai taueta
Semakin besar nilai beta, semakin kecil nilai taueta

Private Const alpha As Integer = 3
Private Const beta As Integer = 2

* Tentukan rho dan Q
rho dan Q adalah koefisien yang digunakan untuk perhitungan feromon
Semakin besar nilai rho, semakin kecil nilai feromon
Semakin besar nilai beta, semakin besar nilai feromon

Private Const rho As Double = 0.01
Private Const Q As Double = 2.0

* Tentukan jumlah titik yang harus dilalui
Diasumsikan dalam kasus ini, ada 8 titik yang harus dilalui

Const jumlahTitik As Integer = 8

* Tentukan jumlah semut yang melakukan pencarian jalur
Nantinya setiap semut akan melalui semua titik yang telah disebutkan diatas
Diasumsikan dalam kasus ini, ada 10 semut yang melakukan pencarian jalur

Const jumlahSemut As Integer = 10

* Tentukan banyak iterasi yang digunakan dalam perhitungan
Nantinya setiap semut akan melakukan perulangan ini untuk melakukan pencarian jalur
Diasumsikan dalam kasus ini, jumlah iterasi adalah 100 kali

Const iterasi As Integer = 100

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan Array Jarak untuk setiap titik yang tersedia
Sesuai asumsi diatas, jarak untuk tiap titik akan dihitung secara acak dengan angka 1 sampai 8

Dim Jarak(jumlahTitik - 1)() As Integer
For i As Integer = 0 To Jarak.Length - 1
	Jarak(i) = New Integer(jumlahTitik - 1) {}
Next i
For i As Integer = 0 To jumlahTitik - 1
	For j As Integer = i + 1 To jumlahTitik - 1
		Dim d As Integer = random.Next(1, 8)
		Jarak(i)(j) = d
		Jarak(j)(i) = d
	Next j
Next i

2. Tentukan Array Semut yang digunakan untuk melakukan pencarian jalur
Setiap semut pada Array Semut akan memiliki array Jejak untuk mencatat jalur-jalur yang dilewati
Beri nilai jejak acak sebagai jejak awal mula dari setiap semut

Dim Semut(jumlahSemut - 1)() As Integer
For k As Integer = 0 To jumlahSemut - 1
	Dim titikAwal As Integer = random.Next(0, jumlahTitik)

	Dim Jejak(jumlahTitik - 1) As Integer

	For i As Integer = 0 To jumlahTitik - 1
		Jejak(i) = i
	Next i

	For i As Integer = 0 To jumlahTitik - 1
		Dim r As Integer = random.Next(i, jumlahTitik)
		Dim tmp As Integer = Jejak(r)
		Jejak(r) = Jejak(i)
		Jejak(i) = tmp
	Next i

	Dim idx As Integer = 0
	For i As Integer = 0 To Jejak.Length - 1
		If Jejak(i) = titikAwal Then
			idx = i
		End If
	Next i

	Dim temp As Integer = Jejak(0)
	Jejak(0) = Jejak(idx)
	Jejak(idx) = temp

	Semut(k) = Jejak
Next k

3. Cari Jejak Terbaik dan Jarak Terpendek dari setiap jejak awal pada semua semut
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim JejakTerbaik() As Integer = CariJejakTerbaik(Semut, Jarak)
Dim JarakTerpendek As Double = cariJarakTerpendek(JejakTerbaik, Jarak)

* Gunakan Fungsi ini untuk mencari Jejak Terbaik yang memiliki Jarak Terpendek
Jejak terbaik adalah jejak yang memiliki jarak terpendek
Perhitungan mengenai jarak terpendek dilakukan oleh fungsi cariJarakTerpendek

Private Function cariJarakTerpendek(ByVal Jejak() As Integer, ByVal Jarak()() As Integer) As Double
	Dim hasil As Double = 0.0
	For i As Integer = 0 To Jejak.Length - 2
		hasil += Jarak(Jejak(i))(Jejak(i + 1))
	Next i
	Return hasil
End Function

* Gunakan Fungsi ini untuk mencari jarak terpendek pada setiap jejak.
Jarak terpendek dihitung dari jumlah Jarak yang ditempuh pada Array Jejak

Private Function CariJejakTerbaik(ByVal Semut()() As Integer, ByVal Jarak()() As Integer) As Integer()
	Dim JarakTerpendek As Double = cariJarakTerpendek(Semut(0), Jarak)
	Dim idxJarakTerpendek As Integer = 0
	For k As Integer = 1 To Semut.Length - 1
		Dim totalJarak As Double = cariJarakTerpendek(Semut(k), Jarak)
		If totalJarak < JarakTerpendek Then
			JarakTerpendek = totalJarak
			idxJarakTerpendek = k
		End If
	Next k
	Dim jumlahTitik As Integer = Semut(0).Length

	Dim hasilJejakTerbaik(jumlahTitik - 1) As Integer
	Semut(idxJarakTerpendek).CopyTo(hasilJejakTerbaik, 0)
	Return hasilJejakTerbaik
End Function

4. Tentukan Array feromon
Feromon digunakan untuk perhitungan pencarian titik berikutnya
Beri nilai awal feromon dengan nilai yang sangat rendah sekali, yaitu 0.01

Dim Feromon(jumlahTitik - 1)() As Double
For i As Integer = 0 To jumlahTitik - 1
	Feromon(i) = New Double(jumlahTitik - 1) {}
Next i
For i As Integer = 0 To Feromon.Length - 1
	For j As Integer = 0 To Feromon(i).Length - 1
		Feromon(i)(j) = 0.01
	Next j
Next i

5. Lakukan proses pencarian jalur sebanyak n iterasi (poin 5a - 5c)

5a. Lakukan proses pencarian jejak baru pada setiap semut
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

UpdateSemut(Semut, Feromon, Jarak, alpha, beta)

5a1. Lakukan perulangan pada setiap semut
Lakukan pencarian jejak baru ke semua titik-titik lain secara acak

5a1a. Untuk semut dengan index k, yang berada pada titik titikX, hitung probabilitas untuk berpindah ke semua titik tujuan

Dim taueta(jumlahTitik - 1) As Double
Dim jumlahTaueta As Double = 0.0
For j As Integer = 0 To taueta.Length - 1
	If j = titikX Then
		taueta(j) = 0.0 'Peluang untuk berpindah ke titik diri sendiri adalah 0
	ElseIf titikTerpakai(j) = True Then
		taueta(j) = 0.0 'Peluang untuk berpindah ke titik titikTerpakai adalah 0
	Else
		taueta(j) = Math.Pow(feromon(titikX)(j), alpha) * Math.Pow((1.0 / Jarak(titikX)(j)), beta)
		If taueta(j) < 0.0001 Then
			taueta(j) = 0.0001
		ElseIf taueta(j) > (Double.MaxValue / (jumlahTitik * 100)) Then
			taueta(j) = Double.MaxValue / (jumlahTitik * 100)
		End If
	End If
	jumlahTaueta += taueta(j)
Next j

Dim probabilitas(jumlahTitik - 1) As Double
For j As Integer = 0 To probabilitas.Length - 1
	probabilitas(j) = taueta(j) / jumlahTaueta
Next j

5a1b. Untuk semut dengan index k, yang berada pada titik titikX, tentukan titik acak berikutnya

Dim NilaiKumulatif(probabilitas.Length) As Double
For j As Integer = 0 To probabilitas.Length - 1
	NilaiKumulatif(j + 1) = NilaiKumulatif(j) + probabilitas(j)
Next j

Dim p As Double = random.NextDouble()

For j As Integer = 0 To NilaiKumulatif.Length - 2
	If p >= NilaiKumulatif(j) AndAlso p < NilaiKumulatif(j + 1) Then
		titikSelanjutnya = j
		Exit For
	End If
Next j

5b. Lakukan proses perubahan nilai feromon pada masing-masing jarak antar titik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

UpdateFeromon(Feromon, Semut, Jarak, rho, Q)

5b1. Update semua nilai feromon untuk setiap jalur
Cari jarak terpendek pada jalur tersebut
Jika titik-titiknya bersebelahan dan jaraknya bersebelahan, maka nilai feromon akan semakin besar

For i As Integer = 0 To feromon.Length - 1
	For j As Integer = i + 1 To feromon(i).Length - 1
		For k As Integer = 0 To Semut.Length - 1
			Dim jarakTerpendek As Double = cariJarakTerpendek(Semut(k), Jarak)
			Dim faktorPengecil As Double = (1.0 - rho) * feromon(i)(j)
			Dim faktorPembesar As Double = 0.0
			If isBersebelahan(i, j, Semut(k)) = True Then
				faktorPembesar = (Q / jarakTerpendek)
			End If

			feromon(i)(j) = faktorPengecil + faktorPembesar

			If feromon(i)(j) < 0.0001 Then
				feromon(i)(j) = 0.0001
			ElseIf feromon(i)(j) > 100000.0 Then
				feromon(i)(j) = 100000.0
			End If

			feromon(j)(i) = feromon(i)(j)
		Next k
	Next j
Next i

5c. Cari Jejak Terbaik dan Jarak Terpendek dari jejak semut yang telah mengalami perubahan
Apabila jarak terpendek ternyata lebih baik (rendah) daripada jarak terpendek terbaik, maka ambil nilai jejak nya sebagai jejak terbaik

Dim JejakTerbaikSkrg() As Integer = CariJejakTerbaik(Semut, Jarak)
Dim JarakTerpendekSkrg As Double = cariJarakTerpendek(JejakTerbaikSkrg, Jarak)
If JarakTerpendekSkrg < JarakTerpendek Then
	JarakTerpendek = JarakTerpendekSkrg
	JejakTerbaik = JejakTerbaikSkrg
	Console.WriteLine("Jarak Terpendek terbaru " & JarakTerpendek.ToString("F1") & " ditemukan pada iterasi " & n)
End If

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.