Alur Kerja ACO untuk TSP – Contoh Kota A, B, C

Inisialisasi

• Kota: A, B, C.
• Jarak: A–B = 10, A–C = 15, B–C = 20.
• Feromon awal semua jalur: τ = 0.1.
• Parameter: α = 1, β = 2, ρ = 0.5, Q = 100.
• Jumlah semut = 1, jumlah iterasi = 1.

Pemilihan kota awal

Satu kota dipilih secara acak sebagai posisi awal semut.

Misal kota awal terpilih adalah B. Rute = [B], sudah dikunjungi = {B}.

Dari B memilih kota berikutnya

Kandidat: A dan C.

• Visibilitas η = 1 / jarak
  Arahan B→A: η = 1/10 = 0.1
  Arahan B→C: η = 1/20 = 0.05
• Nilai ketertarikan
  value(B→A) = 0.1 × 0.1² = 0.001
  value(B→C) = 0.1 × 0.05² = 0.00025
• Probabilitas
  Total = 0.00125
  P(B→A) = 0.8, P(B→C) = 0.2

Misal bilangan acak r = 0.45, sehingga r jatuh pada interval B→A. Kota berikut adalah A. Rute = [B, A].

Dari A menuju kota terakhir

Satu-satunya kota yang belum dikunjungi adalah C, sehingga dipilih C. Rute lengkap: B → A → C, dengan total jarak 10 + 15 = 25.

Pembaruan feromon

• Penguapan:
  τ baru = (1 − ρ) × 0.1 = 0.05 untuk semua jalur.
• Penambahan pada jalur yang dilewati B–A dan A–C:
  Δτ = Q / cost = 100 / 25 = 4
  τ(B–A) = 0.05 + 4 = 4.05
  τ(A–C) = 0.05 + 4 = 4.05
  τ(B–C) tetap 0.05

Pada iterasi berikutnya, jalur yang membentuk rute B–A–C menjadi jauh lebih menarik bagi semut lain karena feromonnya lebih tinggi dan jaraknya relatif pendek.