Metode Ant Colony Optimization Pada Kasus TSP


Kasus yang diselesaikan

Travellig Salesmen Problem (TSP) merupakan persoalan yang penting dalam sistem distribusi. Masalah travelling salesmen ini secara umum digambarkan sebagai suatu kasus dimana seseorang harus mengunjungi sebuah kota dari suatu pusat fasilitas dan kembali lagi ke tempat pemberangkatan semula, dengan asumsi jarak yang diketahui. Tujuan dari masalah ini adalah untuk meminimalkan total jarak tempuh salesmen.

Untuk menyelesaikan masalah tersebut digunakan algoritma heuristic. Algoritma ant colony optimization (ACO) merupakan salah satu metode heuristic yang menerapkan semut sebagai agen dengan update pheromone nya untuk dapat melakukan proses pencarian solusi yang efektif dan efisien.

Simulasi dilakukan dengan mencari solusi optimal dari TSP dengan jumlah semut adalah 8. Pada algoritma ACO ini titik diumpamakan sebagai semut, dan iterasinya juga dibatasi yaitu 10 iterasi.

Variabel yang digunakan

  • Alpha
  • Beta
Alpha dan Beta adalah koefisien yang digunakan untuk perhitungan teta. Semakin besar nilai alpha, semakin besar nilai teta. Semakin besar nilai beta, semakin kecil nilai teta.
  • rho
  • 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.
  • Jumlah titik
  • Jumlah semut
  • Banyak iterasi
Jumlah titik yang harus dilalui. Jumlah semut yang melakukan pencarian jalur. Banyak iterasi yang digunakan dalam perhitungan. Setiap semut akan melakukan perulangan ini untuk melakukan pencarian jalur.

Coding atau kode program

Module Module1

    Private random As New Random()

    Sub Main()
        Console.WriteLine("Algoritma Ant Colony Optimization")
        Console.WriteLine("Untuk melakukan pencarian jalur terpendek yang melalui semua titik")
        Console.WriteLine("Putri Butarbutar -x- Krisna Madani")
        Console.WriteLine("------------------------------------------------------------------")
        Console.WriteLine("")

        Dim alpha, beta As Integer
        Dim rho, q As Double
        Dim jumlahtitik, jumlahsemut, iterasimaksimal As Integer

        Console.Write("Alpha : ")
        alpha = Console.ReadLine()

        Console.Write("Beta : ")
        beta = Console.ReadLine()

        Console.WriteLine()

        Console.Write("Rho : ")
        rho = Console.ReadLine()

        Console.Write("Q : ")
        q = Console.ReadLine()

        Console.WriteLine()

        Console.Write("Jumlah titik dan semut : ")
        jumlahtitik = Console.ReadLine()
        jumlahsemut = jumlahtitik

        Console.Write("Iterasi maksimal : ")
        iterasimaksimal = Console.ReadLine()

        Console.WriteLine()
        Console.WriteLine("Jarak antar titik :")

        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

                Console.WriteLine("Titik-" & i & " ke titik-" & j & " = " & d)
            Next j
        Next i

        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

        Console.WriteLine()
        Console.WriteLine("Jejak semut awal adalah: ")
        For i As Integer = 0 To Semut.Length - 1
            Console.Write("Semut " & i + 1 & ": ")

            For j As Integer = 0 To 3
                Console.Write(Semut(i)(j) & "-")
            Next j

            For j As Integer = Semut(i).Length - 4 To Semut(i).Length - 1
                Console.Write(Semut(i)(j) & "-")
            Next j

            Console.Write(", total jarak = ")
            Dim totalJarak As Double = cariJarakTerpendek(Semut(i), Jarak)
            Console.Write(totalJarak.ToString("F1"))
            Console.WriteLine("")
        Next i
        Console.WriteLine("")

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

        Console.Write("Jarak terpendek untuk jejak awal mula adalah: " & JarakTerpendek.ToString("F1") & vbLf)
        Console.WriteLine("")

        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

        Console.WriteLine("Lakukan pencarian jalur terpendek: ")
        Dim n As Integer = 0
        Do While n < iterasimaksimal
            UpdateSemut(Semut, Feromon, Jarak, alpha, beta)

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

            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
            n += 1
        Loop

        Console.Write(vbLf & "Jejak terbaik yang ditemukan: ")
        For i As Integer = 0 To JejakTerbaik.Length - 1
            Console.Write(JejakTerbaik(i) & "-")
            If i > 0 AndAlso i Mod 20 = 0 Then
                Console.WriteLine("")
            End If
        Next i
        Console.WriteLine("")
        Console.WriteLine("Jarak dari jejak terbaik yang ditemukan: " & JarakTerpendek.ToString("F1"))

        Console.WriteLine("")
        Console.WriteLine("Sumber : piptools")
        Console.ReadLine()
    End Sub

    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

    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

    Private Sub UpdateSemut(ByVal Semut()() As Integer, ByVal feromon()() As Double, ByVal Jarak()() As Integer, ByVal alpha As Integer, ByVal beta As Integer)
        Dim jumlahTitik As Integer = feromon.Length
        For k As Integer = 0 To Semut.Length - 1
            Dim titikAwal As Integer = random.Next(0, jumlahTitik)
            Dim Jejak(jumlahTitik - 1) As Integer
            Dim titikTerpakai(jumlahTitik - 1) As Boolean
            Jejak(0) = titikAwal
            titikTerpakai(titikAwal) = True

            For i As Integer = 0 To jumlahTitik - 2
                Dim titikX As Integer = Jejak(i)
                Dim titikSelanjutnya As Integer = -1

                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
                    ElseIf titikTerpakai(j) = True Then
                        taueta(j) = 0.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
                
                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
                '----------

                Jejak(i + 1) = titikSelanjutnya
                titikTerpakai(titikSelanjutnya) = True
            Next i

            Semut(k) = Jejak
        Next k
    End Sub

    Private Sub UpdateFeromon(ByVal feromon()() As Double, ByVal Semut()() As Integer, ByVal Jarak()() As Integer, ByVal rho As Double, ByVal Q As Double)
        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
    End Sub

    Private Function isBersebelahan(ByVal titikX As Integer, ByVal titikY As Integer, ByVal Jejak() As Integer) As Boolean
        Dim indexTerakhir As Integer = Jejak.Length - 1
        Dim idx As Integer = 0
        For i As Integer = 0 To Jejak.Length - 1
            If Jejak(i) = titikX Then
                idx = i
            End If
        Next i

        If idx = 0 AndAlso Jejak(1) = titikY Then
            Return True
        ElseIf idx = 0 AndAlso Jejak(indexTerakhir) = titikY Then
            Return True
        ElseIf idx = 0 Then
            Return False
        ElseIf idx = indexTerakhir AndAlso Jejak(indexTerakhir - 1) = titikY Then
            Return True
        ElseIf idx = indexTerakhir AndAlso Jejak(0) = titikY Then
            Return True
        ElseIf idx = indexTerakhir Then
            Return False
        ElseIf Jejak(idx - 1) = titikY Then
            Return True
        ElseIf Jejak(idx + 1) = titikY Then
            Return True
        Else
            Return False
        End If
    End Function

End Module

Tampilan output program

Kesimpulan

Algoritma ant colony optomization menggunakan fungsi heuristik untuk mendapatkan hasil yang optimal sehingga kekurangan dari algoritma ant colony optomization ini adalah waktu proses dalam mendapatkan hasil yang paling optimal sangat tergantung dari jumlah iterasi perhitungan yang digunakan. Pada kasus ini didapatkan hasil dari 10 iterasi dengan 8 titik yaitu jarak terdekat yang didapatkan adalah 14.

Referensi
https://piptools.net/algoritma-aco-ant-colony-optimization/

Belum ada Komentar untuk "Metode Ant Colony Optimization Pada Kasus TSP"

Posting Komentar

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel