In [ ]:
In [ ]:
path_direktori = 'tsplib/'
daftar_problem_file = ['pr264.tsp', 'att532.tsp', 'rat575.tsp']
# Nilai dari tabel jurnal
best_tsp_solutions = {'pr264': 49135, 'att532': 27686, 'rat575': 6773}
table_values_bf2 = {'pr264': 41143, 'att532': 'NA', 'rat575': 6265}
In [1]:
import numpy as np
import pandas as pd
import networkx as nx
import math
from collections import defaultdict
# ==================== PARSER TSPLIB ====================
def load_tsplib_coords(path):
"""
Load koordinat dari file TSPLIB
Returns: header (dict), coords (dict {node_id: (x, y)})
"""
header = {}
coords = {}
in_coords = False
with open(path, 'r', encoding='utf-8', errors='ignore') as f:
for raw in f:
line = raw.strip()
if not line:
continue
if line.upper().startswith('EOF'):
break
if line.upper().startswith('NODE_COORD_SECTION'):
in_coords = True
continue
if not in_coords:
if ':' in line:
k, v = line.split(':', 1)
header[k.strip().upper()] = v.strip()
continue
# Parse koordinat: "id x y"
parts = line.split()
if len(parts) >= 3:
i = int(float(parts[0]))
x = float(parts[1])
y = float(parts[2])
coords[i] = (x, y)
if not coords:
raise ValueError("NODE_COORD_SECTION tidak ditemukan atau kosong.")
return header, coords
def euclidean_distance(a, b):
"""Hitung jarak Euclidean antara 2 titik"""
return math.hypot(a[0] - b[0], a[1] - b[1])
def coords_to_distance_matrix(coords):
"""
Konversi koordinat ke distance matrix
Returns: numpy array distance matrix, list node_ids
"""
node_ids = sorted(coords.keys())
n = len(node_ids)
dist_matrix = np.zeros((n, n))
for i_idx, i in enumerate(node_ids):
for j_idx, j in enumerate(node_ids):
if i != j:
dist_matrix[i_idx][j_idx] = euclidean_distance(coords[i], coords[j])
return dist_matrix, node_ids
# ==================== KRUSKAL ALGORITHM ====================
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def kruskal_mst(dist_matrix):
n = len(dist_matrix)
edges = []
for i in range(n):
for j in range(i+1, n):
edges.append((dist_matrix[i][j], i, j))
edges.sort()
uf = UnionFind(n)
mst_edges = []
total_weight = 0
for weight, u, v in edges:
if uf.union(u, v):
mst_edges.append((u, v))
total_weight += weight
if len(mst_edges) == n - 1:
break
return total_weight, mst_edges
# ==================== ACO BASE CLASS ====================
class ACO:
def __init__(self, dist_matrix, n_ants=20, n_iterations=100, alpha=1, beta=2, rho=0.5):
self.dist_matrix = dist_matrix
self.n_nodes = len(dist_matrix)
self.n_ants = n_ants
self.n_iterations = n_iterations
self.alpha = alpha
self.beta = beta
self.rho = rho
self.pheromone = np.ones((self.n_nodes, self.n_nodes))
def _select_next_node(self, current, unvisited, max_degree=None, degrees=None):
pheromone = self.pheromone[current, unvisited]
heuristic = 1.0 / (self.dist_matrix[current, unvisited] + 1e-10)
if max_degree is not None and degrees is not None:
valid_mask = np.array([degrees[node] < max_degree for node in unvisited])
if not np.any(valid_mask):
return None
pheromone = pheromone * valid_mask
heuristic = heuristic * valid_mask
probabilities = (pheromone ** self.alpha) * (heuristic ** self.beta)
prob_sum = probabilities.sum()
if prob_sum > 0:
probabilities = probabilities / prob_sum
else:
return None
return np.random.choice(unvisited, p=probabilities)
def _update_pheromone(self, solutions, costs):
self.pheromone *= (1 - self.rho)
for solution, cost in zip(solutions, costs):
for i, j in solution:
self.pheromone[i][j] += 1.0 / cost
self.pheromone[j][i] += 1.0 / cost
# ==================== ACO TSP PATH ====================
class ACO_TSP_Path(ACO):
"""TSP Hamiltonian Path - tidak kembali ke awal (n-1 edges)"""
def construct_solution(self, max_degree=None):
start = np.random.randint(self.n_nodes)
tour = [start]
unvisited = list(range(self.n_nodes))
unvisited.remove(start)
degrees = defaultdict(int) if max_degree else None
if max_degree:
degrees[start] = 0
while unvisited:
current = tour[-1]
next_node = self._select_next_node(current, unvisited, max_degree, degrees)
if next_node is None:
return None, float('inf')
tour.append(next_node)
unvisited.remove(next_node)
if max_degree:
degrees[current] += 1
degrees[next_node] += 1
# TIDAK kembali ke awal (PATH)
edges = [(tour[i], tour[i+1]) for i in range(len(tour)-1)]
cost = sum(self.dist_matrix[i][j] for i, j in edges)
return edges, cost
def run(self, max_degree=None):
best_cost = float('inf')
best_solution = None
for iteration in range(self.n_iterations):
solutions = []
costs = []
for ant in range(self.n_ants):
solution, cost = self.construct_solution(max_degree)
if solution is not None:
solutions.append(solution)
costs.append(cost)
if cost < best_cost:
best_cost = cost
best_solution = solution
if solutions:
self._update_pheromone(solutions, costs)
return best_cost, best_solution
# ==================== ACO MST ====================
class ACO_MST(ACO):
def construct_solution(self, max_degree=None):
start = np.random.randint(self.n_nodes)
in_tree = {start}
edges = []
degrees = defaultdict(int) if max_degree else None
while len(in_tree) < self.n_nodes:
candidates = []
for node in in_tree:
if max_degree and degrees[node] >= max_degree:
continue
for next_node in range(self.n_nodes):
if next_node not in in_tree:
if max_degree is None or degrees[next_node] < max_degree:
candidates.append((node, next_node))
if not candidates:
return None, float('inf')
probs = []
for i, j in candidates:
pheromone = self.pheromone[i][j]
heuristic = 1.0 / (self.dist_matrix[i][j] + 1e-10)
prob = (pheromone ** self.alpha) * (heuristic ** self.beta)
probs.append(prob)
probs = np.array(probs)
probs = probs / probs.sum()
selected_idx = np.random.choice(len(candidates), p=probs)
selected_edge = candidates[selected_idx]
edges.append(selected_edge)
in_tree.add(selected_edge[1])
if max_degree:
degrees[selected_edge[0]] += 1
degrees[selected_edge[1]] += 1
cost = sum(self.dist_matrix[i][j] for i, j in edges)
return edges, cost
def run(self, max_degree=None):
best_cost = float('inf')
best_solution = None
for iteration in range(self.n_iterations):
solutions = []
costs = []
for ant in range(self.n_ants):
solution, cost = self.construct_solution(max_degree)
if solution is not None:
solutions.append(solution)
costs.append(cost)
if cost < best_cost:
best_cost = cost
best_solution = solution
if solutions:
self._update_pheromone(solutions, costs)
return best_cost, best_solution
# ==================== MAIN EXECUTION ====================
if __name__ == "__main__":
print("="*80)
print("ACO COMPARISON ON TSPLIB DATASET")
print("="*80)
# Load TSPLIB dataset
tsplib_path = "tsplib/pr264.tsp"
print(f"\nLoading dataset: {tsplib_path}")
header, coords = load_tsplib_coords(tsplib_path)
print(f"\nDataset Info:")
print(f" Name: {header.get('NAME', 'N/A')}")
print(f" Type: {header.get('TYPE', 'N/A')}")
print(f" Dimension: {header.get('DIMENSION', 'N/A')}")
print(f" Edge Weight Type: {header.get('EDGE_WEIGHT_TYPE', 'N/A')}")
print(f" Nodes loaded: {len(coords)}")
# Convert to distance matrix
print("\nConverting to distance matrix...")
dist_matrix, node_ids = coords_to_distance_matrix(coords)
n_nodes = len(node_ids)
print(f"Distance matrix size: {n_nodes} x {n_nodes}")
# Initialize results
results = {
'Algorithm': [],
'Cost': [],
'Edges': [],
'Gap_from_Kruskal_%': []
}
print("\n" + "="*80)
print("RUNNING ALGORITHMS...")
print("="*80)
# 1. Kruskal MST (Baseline)
print("\n1. Running Kruskal MST...")
kruskal_cost, kruskal_edges = kruskal_mst(dist_matrix)
results['Algorithm'].append('Kruskal (Optimal)')
results['Cost'].append(kruskal_cost)
results['Edges'].append(len(kruskal_edges))
results['Gap_from_Kruskal_%'].append(0.0)
print(f" Cost: {kruskal_cost:.2f}, Edges: {len(kruskal_edges)}")
# 2. ACO TSP Path Same
print("\n2. Running ACO TSP Path Same (β=2, ρ=0.5)...")
aco = ACO_TSP_Path(dist_matrix, n_ants=20, n_iterations=100, beta=2, rho=0.5)
cost, edges = aco.run()
gap = ((cost / kruskal_cost) - 1) * 100 if cost != float('inf') else float('inf')
results['Algorithm'].append('ACO_TSP_Path_Same')
results['Cost'].append(cost if cost != float('inf') else None)
results['Edges'].append(len(edges) if edges else 0)
results['Gap_from_Kruskal_%'].append(gap if gap != float('inf') else None)
print(f" Cost: {cost:.2f}, Edges: {len(edges) if edges else 0}, Gap: {gap:.2f}%")
# 3. ACO TSP Path Tuned
print("\n3. Running ACO TSP Path Tuned (β=2, ρ=0.3)...")
aco = ACO_TSP_Path(dist_matrix, n_ants=20, n_iterations=100, beta=2, rho=0.3)
cost, edges = aco.run()
gap = ((cost / kruskal_cost) - 1) * 100 if cost != float('inf') else float('inf')
results['Algorithm'].append('ACO_TSP_Path_Tuned')
results['Cost'].append(cost if cost != float('inf') else None)
results['Edges'].append(len(edges) if edges else 0)
results['Gap_from_Kruskal_%'].append(gap if gap != float('inf') else None)
print(f" Cost: {cost:.2f}, Edges: {len(edges) if edges else 0}, Gap: {gap:.2f}%")
# 4. ACO MST Same
print("\n4. Running ACO MST Same (β=2, ρ=0.5)...")
aco = ACO_MST(dist_matrix, n_ants=20, n_iterations=100, beta=2, rho=0.5)
cost, edges = aco.run()
gap = ((cost / kruskal_cost) - 1) * 100 if cost != float('inf') else float('inf')
results['Algorithm'].append('ACO_MST_Same')
results['Cost'].append(cost if cost != float('inf') else None)
results['Edges'].append(len(edges) if edges else 0)
results['Gap_from_Kruskal_%'].append(gap if gap != float('inf') else None)
print(f" Cost: {cost:.2f}, Edges: {len(edges) if edges else 0}, Gap: {gap:.2f}%")
# 5. ACO MST Tuned
print("\n5. Running ACO MST Tuned (β=1, ρ=0.1)...")
aco = ACO_MST(dist_matrix, n_ants=20, n_iterations=100, beta=1, rho=0.1)
cost, edges = aco.run()
gap = ((cost / kruskal_cost) - 1) * 100 if cost != float('inf') else float('inf')
results['Algorithm'].append('ACO_MST_Tuned')
results['Cost'].append(cost if cost != float('inf') else None)
results['Edges'].append(len(edges) if edges else 0)
results['Gap_from_Kruskal_%'].append(gap if gap != float('inf') else None)
print(f" Cost: {cost:.2f}, Edges: {len(edges) if edges else 0}, Gap: {gap:.2f}%")
# 6. ACO TSP Path Deg3 Same
print("\n6. Running ACO TSP Path Deg3 Same (β=2, ρ=0.5, max_deg=3)...")
aco = ACO_TSP_Path(dist_matrix, n_ants=20, n_iterations=100, beta=2, rho=0.5)
cost, edges = aco.run(max_degree=3)
gap = ((cost / kruskal_cost) - 1) * 100 if cost != float('inf') else float('inf')
results['Algorithm'].append('ACO_TSP_Path_Deg3_Same')
results['Cost'].append(cost if cost != float('inf') else None)
results['Edges'].append(len(edges) if edges else 0)
results['Gap_from_Kruskal_%'].append(gap if gap != float('inf') else None)
if cost == float('inf'):
print(f" No feasible solution found")
else:
print(f" Cost: {cost:.2f}, Edges: {len(edges) if edges else 0}, Gap: {gap:.2f}%")
# 7. ACO TSP Path Deg3 Tuned
print("\n7. Running ACO TSP Path Deg3 Tuned (β=2, ρ=0.3, max_deg=3)...")
aco = ACO_TSP_Path(dist_matrix, n_ants=20, n_iterations=100, beta=2, rho=0.3)
cost, edges = aco.run(max_degree=3)
gap = ((cost / kruskal_cost) - 1) * 100 if cost != float('inf') else float('inf')
results['Algorithm'].append('ACO_TSP_Path_Deg3_Tuned')
results['Cost'].append(cost if cost != float('inf') else None)
results['Edges'].append(len(edges) if edges else 0)
results['Gap_from_Kruskal_%'].append(gap if gap != float('inf') else None)
if cost == float('inf'):
print(f" No feasible solution found")
else:
print(f" Cost: {cost:.2f}, Edges: {len(edges) if edges else 0}, Gap: {gap:.2f}%")
# 8. ACO MST Deg3 Same
print("\n8. Running ACO MST Deg3 Same (β=2, ρ=0.5, max_deg=3)...")
aco = ACO_MST(dist_matrix, n_ants=20, n_iterations=100, beta=2, rho=0.5)
cost, edges = aco.run(max_degree=3)
gap = ((cost / kruskal_cost) - 1) * 100 if cost != float('inf') else float('inf')
results['Algorithm'].append('ACO_MST_Deg3_Same')
results['Cost'].append(cost if cost != float('inf') else None)
results['Edges'].append(len(edges) if edges else 0)
results['Gap_from_Kruskal_%'].append(gap if gap != float('inf') else None)
if cost == float('inf'):
print(f" No feasible solution found")
else:
print(f" Cost: {cost:.2f}, Edges: {len(edges) if edges else 0}, Gap: {gap:.2f}%")
# 9. ACO MST Deg3 Tuned
print("\n9. Running ACO MST Deg3 Tuned (β=1, ρ=0.1, max_deg=3)...")
aco = ACO_MST(dist_matrix, n_ants=20, n_iterations=100, beta=1, rho=0.1)
cost, edges = aco.run(max_degree=3)
gap = ((cost / kruskal_cost) - 1) * 100 if cost != float('inf') else float('inf')
results['Algorithm'].append('ACO_MST_Deg3_Tuned')
results['Cost'].append(cost if cost != float('inf') else None)
results['Edges'].append(len(edges) if edges else 0)
results['Gap_from_Kruskal_%'].append(gap if gap != float('inf') else None)
if cost == float('inf'):
print(f" No feasible solution found")
else:
print(f" Cost: {cost:.2f}, Edges: {len(edges) if edges else 0}, Gap: {gap:.2f}%")
# Create results DataFrame
df = pd.DataFrame(results)
print("\n" + "="*80)
print("FINAL RESULTS")
print("="*80)
print(df.to_string(index=False))
# Save to CSV
output_file = 'tsplib_aco_results.csv'
df.to_csv(output_file, index=False)
print(f"\n✅ Results saved to: {output_file}")
# Summary
print("\n" + "="*80)
print("SUMMARY")
print("="*80)
print(f"Dataset: {header.get('NAME', 'N/A')} ({n_nodes} nodes)")
print(f"Optimal MST (Kruskal): {kruskal_cost:.2f}")
print(f"\nBest unconstrained ACO: ", end="")
unconstrained = df[~df['Algorithm'].str.contains('Deg3')].copy()
best_idx = unconstrained['Cost'].idxmin()
best_row = df.loc[best_idx]
print(f"{best_row['Algorithm']} = {best_row['Cost']:.2f} (Gap: {best_row['Gap_from_Kruskal_%']:.2f}%)")
constrained = df[df['Algorithm'].str.contains('Deg3')].copy()
if not constrained.empty and constrained['Cost'].notna().any():
print(f"\nBest constrained ACO (deg≤3): ", end="")
best_const_idx = constrained['Cost'].idxmin()
best_const_row = df.loc[best_const_idx]
print(f"{best_const_row['Algorithm']} = {best_const_row['Cost']:.2f} (Gap: {best_const_row['Gap_from_Kruskal_%']:.2f}%)")
else:
print(f"\nConstrained ACO (deg≤3): No feasible solutions found")
print("\n" + "="*80)
================================================================================
ACO COMPARISON ON TSPLIB DATASET
================================================================================
Loading dataset: tsplib/pr264.tsp
Dataset Info:
Name: pr264
Type: TSP
Dimension: 264
Edge Weight Type: EUC_2D
Nodes loaded: 264
Converting to distance matrix...
Distance matrix size: 264 x 264
================================================================================
RUNNING ALGORITHMS...
================================================================================
1. Running Kruskal MST...
Cost: 41142.24, Edges: 263
2. Running ACO TSP Path Same (β=2, ρ=0.5)...
Cost: 49247.37, Edges: 263, Gap: 19.70%
3. Running ACO TSP Path Tuned (β=2, ρ=0.3)...
Cost: 49220.11, Edges: 263, Gap: 19.63%
4. Running ACO MST Same (β=2, ρ=0.5)...
Cost: 42534.20, Edges: 263, Gap: 3.38%
5. Running ACO MST Tuned (β=1, ρ=0.1)...
Cost: 302434.04, Edges: 263, Gap: 635.09%
6. Running ACO TSP Path Deg3 Same (β=2, ρ=0.5, max_deg=3)...
Cost: 50718.01, Edges: 263, Gap: 23.27%
7. Running ACO TSP Path Deg3 Tuned (β=2, ρ=0.3, max_deg=3)...
Cost: 50122.95, Edges: 263, Gap: 21.83%
8. Running ACO MST Deg3 Same (β=2, ρ=0.5, max_deg=3)...
Cost: 41684.61, Edges: 263, Gap: 1.32%
9. Running ACO MST Deg3 Tuned (β=1, ρ=0.1, max_deg=3)...
Cost: 283589.90, Edges: 263, Gap: 589.29%
================================================================================
FINAL RESULTS
================================================================================
Algorithm Cost Edges Gap_from_Kruskal_%
Kruskal (Optimal) 41142.242635 263 0.000000
ACO_TSP_Path_Same 49247.371133 263 19.700259
ACO_TSP_Path_Tuned 49220.111521 263 19.634002
ACO_MST_Same 42534.197896 263 3.383275
ACO_MST_Tuned 302434.041542 263 635.093719
ACO_TSP_Path_Deg3_Same 50718.005211 263 23.274771
ACO_TSP_Path_Deg3_Tuned 50122.951042 263 21.828437
ACO_MST_Deg3_Same 41684.607962 263 1.318269
ACO_MST_Deg3_Tuned 283589.899915 263 589.291302
✅ Results saved to: tsplib_aco_results.csv
================================================================================
SUMMARY
================================================================================
Dataset: pr264 (264 nodes)
Optimal MST (Kruskal): 41142.24
Best unconstrained ACO: Kruskal (Optimal) = 41142.24 (Gap: 0.00%)
Best constrained ACO (deg≤3): ACO_MST_Deg3_Same = 41684.61 (Gap: 1.32%)
================================================================================