🐜 ACO & ACO-MST: Formula Dasar & Cara Kerja

1️⃣ Formula Dasar ACO

A. Formula Probabilitas Pemilihan Edge

Pij = [τijα × ηijβ] / Σk∈allowed [τikα × ηikβ]

Dimana:

💡 Intuisi:
• α tinggi → lebih percaya pheromone (exploitation)
• β tinggi → lebih percaya heuristic/greedy (exploitation)
• α dan β rendah → lebih random (exploration)

B. Formula Update Pheromone

τij(t+1) = (1 - ρ) × τij(t) + Δτij

Dimana:

Δτij = Q / Lk (jika edge dilalui oleh semut k)
Δτij = 0 (jika edge tidak dilalui)

Dimana:

💡 Intuisi:
• Solusi bagus (L kecil) → deposit besar (Q/L besar)
• Solusi buruk (L besar) → deposit kecil (Q/L kecil)
• ρ besar → cepat lupa (exploration), ρ kecil → lama ingat (exploitation)

2️⃣ Cara Kerja ACO (Generic)

Pseudocode ACO:

INITIALIZE:
    τij = τ0 untuk semua edge (i,j)  // Pheromone awal
    best_solution = NULL
    best_cost = ∞

FOR iteration = 1 to max_iterations:
    FOR ant = 1 to num_ants:
        solution = construct_solution(ant)
        cost = evaluate(solution)
        
        IF cost < best_cost:
            best_cost = cost
            best_solution = solution
    
    update_pheromone(all_solutions)

RETURN best_solution

FUNCTION construct_solution(ant):
    current = random_start_node()
    solution = []
    
    WHILE not_complete:
        next = select_next_node(current, pheromone, heuristic)
        solution.add(edge(current, next))
        current = next
    
    RETURN solution

FUNCTION select_next_node(current, τ, η):
    FOR each allowed node j:
        Pj = [τcurrent,jα × ηcurrent,jβ] / Σ
    
    RETURN random_choice(probabilities)

FUNCTION update_pheromone(solutions):
    // Evaporation
    τij = (1 - ρ) × τij untuk semua edge
    
    // Deposit
    FOR each solution in solutions:
        FOR each edge in solution:
            τedge += Q / solution_cost

3️⃣ Cara Kerja ACO-MST (Khusus untuk MST)

Perbedaan ACO-MST dengan ACO Generic:

Aspek ACO Generic ACO-MST
Goal Various (TSP, VRP, etc) Spanning Tree (connect all, no cycle)
Constraint Problem-specific NO CYCLE!
Edge Count Varies Exactly n-1 edges
Construction Various strategies Prim-like (grow tree from seed)
Edge Selection From current node From ANY node in tree to outside

Pseudocode ACO-MST (Modified):

FUNCTION construct_MST_solution(ant):
    current = random_start_node()
    tree_nodes = {current}
    tree_edges = []
    
    WHILE |tree_nodes| < n:
        // Find all candidate edges from tree to outside
        candidates = []
        FOR each node i in tree_nodes:
            FOR each node j NOT in tree_nodes:
                candidates.add(edge(i, j))
        
        // Calculate probability for each candidate
        FOR each edge(i,j) in candidates:
            Pij = [τijα × ηijβ] / Σall candidates
        
        // Select edge based on probability
        selected_edge = weighted_random_choice(candidates, probabilities)
        
        tree_edges.add(selected_edge)
        tree_nodes.add(selected_edge.destination)
    
    RETURN tree_edges
🔑 Key Difference:
ACO-MST memilih edge dari SEMUA node yang sudah di tree ke node di luar tree.
Ini berbeda dari TSP yang hanya dari current node!

4️⃣ Improvement MST di ACO

🚀 Improvement yang Diterapkan:

A. Cycle Prevention (Built-in Constraint)

Original ACO: Bisa saja create cycle jika tidak careful

ACO-MST Improvement:

// Check: hanya pilih node yang BELUM di tree
FOR each node j NOT in tree_nodes:  // ← CONSTRAINT!
    candidates.add(edge(i, j))

Impact: Guaranteed no cycle!

B. Prim-like Construction (Efficient Tree Building)

Original ACO: Sequential node-by-node (like TSP)

ACO-MST Improvement:

// Select from ANY tree node, not just current
FOR each node i in tree_nodes:  // ← EXPANDED CHOICE!
    FOR each node j NOT in tree_nodes:
        candidates.add(edge(i, j))

Impact: More exploration, better solutions!

C. Exact Edge Count (n-1 Edges)

Original ACO: Edge count varies by problem

ACO-MST Improvement:

WHILE |tree_edges| < n - 1:  // ← EXACT COUNT!
    // Add edge
    tree_edges.add(selected_edge)

Impact: Always valid tree structure!

D. Degree Constraint Support (Optional)

Enhancement: Limit max connections per node

// Only consider if node hasn't reached max degree
IF degree[i] < max_degree AND degree[j] < max_degree:
    candidates.add(edge(i, j))

Application: Real-world constraints (router ports, etc)

E. Parameter Tuning for MST

Discovery: MST works better with different params than TSP

Parameter TSP (Complex) MST (Simpler) Reasoning
β (heuristic) 2-3 1-2 MST less greedy needed
ρ (evaporation) 0.3-0.5 0.1-0.3 MST needs less exploration

Impact: Faster convergence to optimal!

5️⃣ Comparison: TSP vs MST Construction

Visual Comparison:

Step ACO-TSP Construction ACO-MST Construction
1 Start: Node A
In tour: {A}		 Start: Node A
In tree: {A}
2 From A, pick next
Choices: B, C, D
Pick B (greedy)		 From tree {A}, pick edge
Choices: A-B, A-C, A-D
Pick A-C (probabilistic)
3 From B, pick next
Choices: C, D
Pick D		 From tree {A,C}, pick edge
Choices: A-B, A-D, C-B, C-D
Pick C-B (best from tree)
4 From D, pick next
Choices: C
Pick C		 From tree {A,C,B}, pick edge
Choices: A-D, C-D, B-D
Pick B-D
Result Path: A→B→D→C
NOT a cycle yet!		 Tree: A-C, C-B, B-D
Done! (n-1 edges)
Key Insight:
• TSP: Sequential from current node (like following a path)
• MST: From any tree node (like growing a organism)
• MST approach → better exploration of edge space!

6️⃣ Summary: Why ACO-MST Works Well

✅ Success Factors:

  1. Natural Fit: ACO's probabilistic selection matches MST's flexibility
  2. Built-in Constraint: Cycle prevention automatic in tree construction
  3. Prim-like Strategy: Grow from tree → efficient exploration
  4. Greedy Compatible: Heuristic (1/distance) aligns with MST goal
  5. Pheromone Reinforcement: Good edges get stronger over iterations

🎯 Result:

ACO-MST often finds OPTIMAL solution!
(Sometimes matches Kruskal exactly!)