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)

cmd16a


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.


Tinggalkan Balasan ke ezrah Batalkan balasan

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

27 pemikiran di “Algoritma ACO (Ant Colony Optimization)

    • pip Penulis

      Algoritma ini seharusnya dapat digunakan untuk melakukan optimasi terhadap kasus apapun termasuk didalamnya adalah optimasi parameter

    • pip Penulis

      Saya belum pernah mendengar secara detail dari kasus tersebut, tetapi seharusnya jika berbicara model pencarian jalur secara umum, algoritma ini tentunya dapat menyelesaikan permasalahan tersebut

    • pip Penulis

      Selama kasus tersebut bersifat optimasi, artinya jawaban yang didapatkan adalah memenuhi beberapa konstrain tertentu dan dihitung menggunakan rumus fitness, maka seharusnya algoritma ini dapat digunakan untuk menyelesaikan permasalahan anda.

  • Wati

    Berdasarkan kode diatas, definisi / variable titikX, titikTerpakai seperti apa ? Diprogram tidak ada untuk kedua variabel tersebut.
    Dan juga method isBersebelahan ?

    • pip Penulis

      Variabel titikX digunakan sebagai lokasi semut pada jalur tertentu yang sudah ditentukan sebelumnya. Jika terdapat jalur A-B-C maka pada lokasi pertama nilai variabel titikX adalah A, pada lokasi kedua nilai variabel titikX adalah B, pada lokasi ketiga nilai variabel titiX adalah C.

      Variabel titikTerpakai digunakan untuk mencatat titik2 mana sajakah sudah sudah dilalui dan belum dilalui. Hal ini bertujuan untuk mencegah titik yang sudah dilalui akan dipilih kembali ke dalam rute berikutnya. Jika sebuah jalur dibentuk dari 3 buah titik A, B, C, maka variabel ini diperlukan untuk mencegah solusi seperti A-B-A, C-B-B, dst.

      Metode isBersebelahan digunakan untuk mengetahui apakah parameter titik pertama dan kedua pada jalur semut bersebelahan atau tidak. Sebagai contoh jika terdapat jalur A-B-C, maka titik A dan titik B adalah bersebelahan sehingga fungsi isBersebelahan akan mengembalikan nilai true, sedangkan titik A dan titik C tidak bersebelahan sehingga fungsi isBersebelahan akan mengembalikan nilai false.

    • pip Penulis

      Bahasa pemrograman yang saya gunakan adalah Visual Basic. Hasil implementasi dapat anda ujicoba secara langsung dengan mengunduh file yang sudah saya sertakan diatas.

    • pip Penulis

      Mengingat algoritma ini merupakan salah satu algoritma yang bertujuan untuk mengoptimasi sesuatu, maka tentunya algoritma ini dapat digunakan untuk mengoptimasi jadwal pelajaran.

    • pip Penulis

      Algoritma ini dapat dikonversi ke dalam bahasa PHP karena tidak memiliki ketergantungan terhadap fungsi2 yang disediakan oleh perangkat lunak tertentu. Tetapi saya tidak memiliki contoh jadi untuk algoritma ini dalam bahasa tersebut.

  • Fensi Destari

    Ini untuk data jarak yang terletak diantara 1-8 naa, itu kalo kita punya data riil. Cara nginput nya kayak gimana ? Terus cara ngrunnya ? Soalnya kalo di klik run langsung, tidak muncul hasil. Terima kasih

    • pip Penulis

      Jika menggunakan data sebenarnya, maka matriks jarak disusun dengan cara menghitung nilai jarak untuk masing-masing titik. Diasumsikan terdapat 4 buah lokasi yaitu A, B, C, D maka matriks yang terbentuk berukuran 3×3 yang disusun setelah menghitung nilai jarak AB, AC, AD, BC, BD, CD.

      File yang saya bagikan adalah skrip bertipe konsol. Setelah anda menjalankan Visual Studio, silahkan membuat proyek baru dengan tipe “Console Application”, kemudian salin isi skrip pada file yang disediakan atau anda bisa menimpa langsung modul kosong pada proyek tersebut.

  • dfperdana

    maaf permisi ijin bertanya, Apa perbedaan antara Algoritma ACO dengan Algoritma pencarian jalur seperti Algoritma B&B? Mohon penjelasannya

    • pip Penulis

      Menurut saya algoritma ACO adalah algoritma untuk menyelesaikan permasalahan optimasi. Walaupun implementasi algoritma lebih sulit, tetapi penggunaan algoritma dapat diterapkan pada permasalahan yang bukan pencarian jalur. Sedangkan algoritma Branch and Bound memiliki implementasi yang lebih rendah tingkat kesulitannya tetapi tidak dapat menyelesaikan permasalahan optimasi.

      • dfperdana

        Izin bertanya kembali, jika terkait dengan permasalahan Travelling Salesman Problem dengan fokus meminimasi jarak tempuh, berarti metode ACO bisa lebih baik untuk memberikan hasil yg lebih optimal dibandingkan dengan metode B&B?

        • pip Penulis

          Saya hanya bisa menyampaikan bahwa peluang algoritma ACO dalam menyelesaikan permasalahan akan lebih baik daripada algoritma Branch and Bound karena tingkat kesulitan implementasi algoritma yang lebih sulit. Tetapi jika tingkat kompleksitas kasus hanya sederhana saja maka secara teori tidak perlu menggunakan algoritma ACO untuk mempersingkat waktu implementasi.

  • lol

    bagaimana cara menjalankannya ? apa langsung di run saja. ini saya buka pakai visual studio, tetapi saat di run tidak mengeluarkan output apapun. mungkin saya salah dimana nya ya?

    • pip Penulis

      File yang saya bagikan adalah skrip bertipe konsol (kesalahan yang terjadi pada tempat anda mungkin disebabkan karena anda tidak menjalankan skrip dalam bentuk konsol). Setelah anda menjalankan Visual Studio, silahkan membuat proyek baru dengan tipe “Console Application”, kemudian salin isi skrip pada file yang disediakan atau anda bisa menimpa langsung modul kosong pada proyek tersebut.