In [ ]:
In [2]:
import numpy as np
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
import seaborn as sns
import string
import os
import warnings
from collections import defaultdict
INDEX=30
# Suppress warnings for cleaner output
warnings.filterwarnings('ignore', category=DeprecationWarning)
warnings.filterwarnings('ignore', category=UserWarning)
# Set matplotlib style for better plots
try:
plt.style.use('seaborn-v0_8-darkgrid')
except:
plt.style.use('seaborn-darkgrid')
sns.set_palette("husl")
# ==================== HELPER FUNCTIONS ====================
def generate_two_letter_labels(n):
labels = []
for i in range(n):
first = i // 26
second = i % 26
label = string.ascii_uppercase[first] + string.ascii_uppercase[second]
labels.append(label)
return labels
# ==================== 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
# ==================== PSO BASE CLASS ====================
"""
🔄 PARTICLE SWARM OPTIMIZATION (PSO) - MAIN DIFFERENCES FROM ACO:
**ACO (Ant Colony Optimization):**
- Uses PHEROMONE trails (chemical signals)
- Ants build solutions following pheromone + heuristic
- Pheromone EVAPORATES over time
- Good solutions DEPOSIT more pheromone
- Probabilistic construction
**PSO (Particle Swarm Optimization):**
- Uses PARTICLE position & velocity (physics-inspired)
- Particles MOVE in search space
- Each particle has PERSONAL BEST (pbest)
- Swarm has GLOBAL BEST (gbest)
- Velocity updated by: INERTIA + COGNITIVE + SOCIAL
- Position updated by adding velocity
"""
class PSO:
def __init__(self, dist_matrix, n_particles=10, n_iterations=50, w=0.7, c1=1.5, c2=1.5):
"""
Initialize PSO Algorithm
**KEY PSO PARAMETERS (Different from ACO):**
- n_particles: Number of particles (like n_ants in ACO)
- n_iterations: Number of iterations
- **w (inertia weight)**: Momentum factor [0-1]
* High w = more exploration
* Low w = more exploitation
- **c1 (cognitive coefficient)**: Learning from own best [0-2]
* Trust in personal experience
- **c2 (social coefficient)**: Learning from swarm best [0-2]
* Trust in collective intelligence
**NO pheromone matrix like ACO!**
**NO alpha, beta, rho parameters!**
"""
self.dist_matrix = dist_matrix
self.n_nodes = len(dist_matrix)
self.n_particles = n_particles
self.n_iterations = n_iterations
# **PSO-SPECIFIC PARAMETERS (Not in ACO)**
self.w = w # Inertia weight
self.c1 = c1 # Cognitive coefficient
self.c2 = c2 # Social coefficient
# **PARTICLES instead of pheromone (Main difference!)**
self.particles = []
self.velocities = []
self.pbest_positions = [] # Personal best for each particle
self.pbest_costs = []
self.gbest_position = None # Global best
self.gbest_cost = float('inf')
def _initialize_particle(self, max_degree=None):
"""
Initialize a random particle (solution)
This is similar to ACO's ant construction but creates initial population
"""
raise NotImplementedError("Subclass must implement _initialize_particle")
def _calculate_cost(self, edges):
"""Calculate total cost of edges"""
return sum(self.dist_matrix[i][j] for i, j in edges)
def _apply_velocity_tsp(self, position, velocity, pbest, gbest):
"""
**CORE PSO MECHANISM for TSP Path (Different from ACO!)**
In PSO, we don't use pheromone probability like ACO.
Instead, we use VELOCITY to guide LOCAL SEARCH operations.
**PSO Update Rules:**
1. velocity = w*velocity + c1*r1*(pbest-position) + c2*r2*(gbest-position)
2. position = position + velocity
For discrete problems (TSP/MST), we interpret:
- velocity = intensity/number of local search operations
- position update = apply 2-opt or edge swap
**Guidance from pbest and gbest:**
- Extract good edges from pbest and gbest
- Bias local search to preserve these good edges
"""
# Convert velocity to number of local search operations
# Higher velocity = more operations
n_operations = min(5, max(1, int(abs(velocity) / 50) + 1))
# Reconstruct path from edges
path = self._edges_to_path(position)
if path is None:
return position
best_path = path.copy()
best_cost = self._calculate_cost(position)
# Extract good edges from pbest and gbest for guidance
good_edges = set()
if pbest:
good_edges.update(pbest)
if gbest:
good_edges.update(gbest)
# **Apply local search operations (guided by velocity)**
for _ in range(n_operations):
# 2-opt move
i = np.random.randint(1, len(path) - 1)
j = np.random.randint(i + 1, len(path))
# Reverse segment [i:j]
new_path = path[:i] + path[i:j][::-1] + path[j:]
new_edges = self._path_to_edges(new_path)
new_cost = self._calculate_cost(new_edges)
# **PSO guidance: prefer moves that include good edges**
edge_quality = sum(1 for e in new_edges if e in good_edges or (e[1], e[0]) in good_edges)
# Accept if improved or maintains good edges
if new_cost < best_cost:
best_path = new_path
best_cost = new_cost
return self._path_to_edges(best_path)
def _apply_velocity_mst(self, position, velocity, pbest, gbest):
"""
**CORE PSO MECHANISM for MST (Different from ACO!)**
Similar to TSP but uses edge swap instead of 2-opt
"""
n_operations = min(5, max(1, int(abs(velocity) / 50) + 1))
best_edges = position.copy()
best_cost = self._calculate_cost(position)
# Extract good edges from pbest and gbest
good_edges = set()
if pbest:
good_edges.update(pbest)
if gbest:
good_edges.update(gbest)
# **Apply edge swap operations (guided by velocity)**
for _ in range(n_operations):
# Remove random edge
if len(best_edges) < 2:
continue
edge_idx = np.random.randint(len(best_edges))
removed_edge = best_edges[edge_idx]
temp_edges = [e for i, e in enumerate(best_edges) if i != edge_idx]
# Check connectivity
G = nx.Graph()
G.add_edges_from(temp_edges)
if not nx.is_connected(G):
# Find components and reconnect
components = list(nx.connected_components(G))
if len(components) == 2:
comp1, comp2 = components
# Find best reconnection edge
best_reconnect = None
best_reconnect_cost = float('inf')
for u in comp1:
for v in comp2:
cost = self.dist_matrix[u][v]
# **PSO guidance: prefer edges from pbest/gbest**
if (u, v) in good_edges or (v, u) in good_edges:
cost *= 0.8 # Bias towards good edges
if cost < best_reconnect_cost:
best_reconnect_cost = cost
best_reconnect = (u, v)
if best_reconnect:
new_edges = temp_edges + [best_reconnect]
new_cost = self._calculate_cost(new_edges)
if new_cost < best_cost:
best_edges = new_edges
best_cost = new_cost
return best_edges
def _edges_to_path(self, edges):
"""Convert edges to path (for TSP)"""
if not edges:
return None
# Build adjacency
adj = defaultdict(list)
for i, j in edges:
adj[i].append(j)
adj[j].append(i)
# Start from any node
start = edges[0][0]
path = [start]
visited = {start}
current = start
while len(visited) < self.n_nodes:
next_nodes = [n for n in adj[current] if n not in visited]
if not next_nodes:
break
next_node = next_nodes[0]
path.append(next_node)
visited.add(next_node)
current = next_node
return path if len(path) == self.n_nodes else None
def _path_to_edges(self, path):
"""Convert path to edges"""
return [(path[i], path[i+1]) for i in range(len(path) - 1)]
def _update_velocity_and_position(self, particle_idx, apply_velocity_func):
"""
**MAIN PSO UPDATE MECHANISM (Completely different from ACO!)**
**ACO:** Uses pheromone trails
**PSO:** Uses velocity and personal/global best
**PSO Velocity Update Formula:**
v(t+1) = w*v(t) + c1*r1*(pbest - x) + c2*r2*(gbest - x)
Components:
1. **w*v(t)**: INERTIA - keep moving in same direction
2. **c1*r1*(pbest-x)**: COGNITIVE - pull towards personal best
3. **c2*r2*(gbest-x)**: SOCIAL - pull towards global best
Where:
- w = inertia weight
- c1 = cognitive coefficient (self-confidence)
- c2 = social coefficient (swarm confidence)
- r1, r2 = random numbers [0,1]
"""
position = self.particles[particle_idx]
velocity = self.velocities[particle_idx]
pbest = self.pbest_positions[particle_idx]
gbest = self.gbest_position
# **STEP 1: Calculate velocity components**
# Inertia component
inertia = self.w * velocity
# Cognitive component (learn from own best)
r1 = np.random.random()
cognitive_influence = self.c1 * r1 * (self.pbest_costs[particle_idx] -
self._calculate_cost(position))
# Social component (learn from swarm best)
r2 = np.random.random()
social_influence = self.c2 * r2 * (self.gbest_cost -
self._calculate_cost(position))
# **STEP 2: Update velocity**
# **This is the HEART of PSO (not in ACO!)**
new_velocity = inertia + cognitive_influence + social_influence
# **STEP 3: Update position using velocity**
# Apply velocity through local search
new_position = apply_velocity_func(position, new_velocity, pbest, gbest)
# **STEP 4: Update personal best if improved**
new_cost = self._calculate_cost(new_position)
if new_cost < self.pbest_costs[particle_idx]:
self.pbest_positions[particle_idx] = new_position
self.pbest_costs[particle_idx] = new_cost
# **STEP 5: Update global best if improved**
if new_cost < self.gbest_cost:
self.gbest_position = new_position
self.gbest_cost = new_cost
# Update particle state
self.particles[particle_idx] = new_position
self.velocities[particle_idx] = new_velocity
return new_cost
# ==================== PSO TSP PATH (FAIR - NO CYCLE) ====================
class PSO_TSP_Path(PSO):
"""
PSO for TSP Hamiltonian Path (n-1 edges, no cycle)
**Comparison with ACO_TSP_Path:**
- ACO: Builds path using pheromone probability
- PSO: Builds initial population, then moves particles using velocity
"""
def _initialize_particle(self, max_degree=None):
"""Initialize a random TSP path"""
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]
# Check degree constraint
if max_degree and degrees[current] >= max_degree:
return None, float('inf')
# Filter valid candidates
if max_degree:
candidates = [n for n in unvisited if degrees[n] < max_degree]
else:
candidates = unvisited
if not candidates:
return None, float('inf')
# **PSO: Random selection (no pheromone like ACO)**
# Initial population just needs diversity
distances = [self.dist_matrix[current][c] for c in candidates]
probs = 1.0 / (np.array(distances) + 1e-10)
probs = probs / probs.sum()
next_node = np.random.choice(candidates, p=probs)
tour.append(next_node)
unvisited.remove(next_node)
if max_degree:
degrees[current] += 1
degrees[next_node] += 1
# Convert to edges (PATH - no cycle back to start)
edges = [(tour[i], tour[i+1]) for i in range(len(tour)-1)]
cost = self._calculate_cost(edges)
return edges, cost
def run(self, max_degree=None):
"""
**PSO MAIN ALGORITHM (Different from ACO!)**
**ACO Algorithm:**
1. Initialize pheromone
2. For each iteration:
- Ants build solutions using pheromone probability
- Update pheromone (evaporate + deposit)
**PSO Algorithm:**
1. Initialize particle swarm (random solutions)
2. For each iteration:
- Update velocity (inertia + cognitive + social)
- Update position (apply velocity)
- Update pbest and gbest
"""
#print(f"[PSO] Initializing {self.n_particles} particles...")
# **INITIALIZATION PHASE**
for _ in range(self.n_particles):
position, cost = self._initialize_particle(max_degree)
if position is None:
# Retry if infeasible
for _ in range(5):
position, cost = self._initialize_particle(max_degree)
if position is not None:
break
if position is None:
position = []
cost = float('inf')
self.particles.append(position)
self.velocities.append(0.0) # Initial velocity = 0
self.pbest_positions.append(position)
self.pbest_costs.append(cost)
# Update global best
if cost < self.gbest_cost:
self.gbest_cost = cost
self.gbest_position = position
#print(f"[PSO] Initial best cost: {self.gbest_cost:.2f}")
# **MAIN PSO LOOP**
for iteration in range(self.n_iterations):
# **Update each particle**
for p in range(self.n_particles):
self._update_velocity_and_position(p, self._apply_velocity_tsp)
#if (iteration + 1) % 10 == 0:
#print(f"[PSO] Iteration {iteration+1}/{self.n_iterations}, "
#f"Best: {self.gbest_cost:.2f}")
return self.gbest_cost, self.gbest_position
# ==================== PSO MST ====================
class PSO_MST(PSO):
"""
PSO for Minimum Spanning Tree
**Comparison with ACO_MST:**
- ACO: Builds MST using pheromone on edges
- PSO: Builds initial MST population, then optimizes using velocity
"""
def _initialize_particle(self, max_degree=None):
"""Initialize a random MST"""
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')
# **PSO: Select based on distance (no pheromone like ACO)**
distances = [self.dist_matrix[i][j] for i, j in candidates]
probs = 1.0 / (np.array(distances) + 1e-10)
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 = self._calculate_cost(edges)
return edges, cost
def run(self, max_degree=None):
"""Run PSO for MST"""
#print(f"[PSO] Initializing {self.n_particles} particles...")
# Initialize swarm
for _ in range(self.n_particles):
position, cost = self._initialize_particle(max_degree)
if position is None:
for _ in range(5):
position, cost = self._initialize_particle(max_degree)
if position is not None:
break
if position is None:
position = []
cost = float('inf')
self.particles.append(position)
self.velocities.append(0.0)
self.pbest_positions.append(position)
self.pbest_costs.append(cost)
if cost < self.gbest_cost:
self.gbest_cost = cost
self.gbest_position = position
#print(f"[PSO] Initial best cost: {self.gbest_cost:.2f}")
# Main PSO loop
for iteration in range(self.n_iterations):
for p in range(self.n_particles):
self._update_velocity_and_position(p, self._apply_velocity_mst)
#if (iteration + 1) % 10 == 0:
#print(f"[PSO] Iteration {iteration+1}/{self.n_iterations}, "
# f"Best: {self.gbest_cost:.2f}")
return self.gbest_cost, self.gbest_position
# ==================== VISUALIZATION ====================
def visualize_solution(dist_matrix, edges, node_labels, title, save_path=None):
"""Visualize graph solution"""
G = nx.Graph()
for i, label in enumerate(node_labels):
G.add_node(label)
for i, j in edges:
u = node_labels[i]
v = node_labels[j]
weight = dist_matrix[i][j]
G.add_edge(u, v, weight=weight)
plt.figure(figsize=(12, 10))
pos = nx.spring_layout(G, seed=42, k=2)
nx.draw_networkx_nodes(G, pos, node_color='lightblue',
node_size=800, alpha=0.9)
nx.draw_networkx_edges(G, pos, width=3, alpha=0.6, edge_color='darkblue')
nx.draw_networkx_labels(G, pos, font_size=10, font_weight='bold')
edge_labels = {(u, v): f'{data["weight"]:.0f}' for u, v, data in G.edges(data=True)}
nx.draw_networkx_edge_labels(G, pos, edge_labels, font_size=8)
plt.title(title, fontsize=16, fontweight='bold', pad=20)
plt.axis('off')
plt.tight_layout()
if save_path:
plt.savefig(save_path, dpi=150, bbox_inches='tight')
plt.close()
# ==================== LOAD DATASET ====================
def load_datasets_from_csv(num_vertices=10, datasetKolomMax=31, folder_name='results_pso'):
if not os.path.exists(folder_name):
os.makedirs(folder_name)
NF = f'dataset/dataset{num_vertices}.csv'
try:
df = pd.read_csv(NF)
expected_edges = num_vertices * (num_vertices - 1) // 2
datasets = []
for ii in range(1, datasetKolomMax):
COL = f'NamaFile{ii}'
if COL not in df.columns:
break
weights = df[COL].tolist()
if len(weights) < expected_edges:
break
G = nx.complete_graph(num_vertices)
for i, (u, v) in enumerate(G.edges()):
G[u][v]['weight'] = weights[i]
if num_vertices <= 20:
node_labels = [letter for letter in string.ascii_uppercase[:num_vertices]]
else:
node_labels = generate_two_letter_labels(num_vertices)
G = nx.relabel_nodes(G, {i: node_labels[i] for i in range(num_vertices)})
nodes = sorted(G.nodes())
n = len(nodes)
node_to_idx = {node: idx for idx, node in enumerate(nodes)}
dist_matrix = np.zeros((n, n))
for u, v, data in G.edges(data=True):
i = node_to_idx[u]
j = node_to_idx[v]
weight = data['weight']
dist_matrix[i][j] = weight
dist_matrix[j][i] = weight
datasets.append((dist_matrix, node_labels, G))
return datasets
except FileNotFoundError:
print(f"Creating sample dataset...")
os.makedirs('dataset', exist_ok=True)
n_edges = expected_edges
data = {f'NamaFile{i}': np.random.randint(10, 100, size=n_edges)
for i in range(1, min(datasetKolomMax, 11))}
df_new = pd.DataFrame(data)
df_new.insert(0, 'Nomor', range(1, n_edges + 1))
df_new.to_csv(NF, index=False)
return load_datasets_from_csv(num_vertices, datasetKolomMax, folder_name)
# ==================== MAIN EXECUTION ====================
if __name__ == "__main__":
print("="*80)
print("PSO COMPARISON: TSP PATH vs MST (SAME n-1 EDGES) "+str(INDEX)+" Vertex")
print("="*80)
# Configuration
num_vertices = INDEX
datasetKolomMax = 31
folder_name = 'results_pso'
# Load datasets
print("\nLoading datasets from CSV...")
datasets = load_datasets_from_csv(num_vertices, datasetKolomMax, folder_name)
if not datasets:
print("Error loading datasets!")
exit(1)
print(f"Loaded {len(datasets)} datasets with {num_vertices} vertices each")
# Initialize results
results = {
'Dataset': [],
'Kruskal': [],
'PSO_TSP_Path_Same': [],
'PSO_TSP_Path_Tuned': [],
'PSO_MST_Same': [],
'PSO_MST_Tuned': [],
'PSO_TSP_Path_Deg3_Same': [],
'PSO_TSP_Path_Deg3_Tuned': [],
'PSO_MST_Deg3_Same': [],
'PSO_MST_Deg3_Tuned': []
}
# Store first dataset solutions for visualization
first_solutions = {}
print("\n" + "="*80)
print("RUNNING EXPERIMENTS...")
print("="*80)
for idx, (dist_matrix, node_labels, G_complete) in enumerate(datasets):
print(f"\nDataset {idx+1}:")
results['Dataset'].append(f"D{idx+1}")
# Kruskal
kruskal_cost, kruskal_edges = kruskal_mst(dist_matrix)
results['Kruskal'].append(kruskal_cost)
print(f" Kruskal MST: {kruskal_cost:.2f} ({len(kruskal_edges)} edges)")
if idx == 0:
first_solutions['kruskal'] = (kruskal_edges, kruskal_cost)
# PSO TSP Path Same (w=0.7, c1=1.5, c2=1.5)
#print(f" Running PSO TSP Path Same...")
pso_tsp_same = PSO_TSP_Path(dist_matrix, n_particles=10, n_iterations=50,
w=0.7, c1=1.5, c2=1.5)
cost, edges = pso_tsp_same.run()
results['PSO_TSP_Path_Same'].append(cost)
print(f" PSO TSP Path Same: {cost:.2f} ({len(edges) if edges else 0} edges)")
if idx == 0 and edges:
first_solutions['tsp_same'] = (edges, cost)
# PSO TSP Path Tuned (w=0.6, c1=2.0, c2=1.0)
#print(f" Running PSO TSP Path Tuned...")
pso_tsp_tuned = PSO_TSP_Path(dist_matrix, n_particles=15, n_iterations=50,
w=0.6, c1=2.0, c2=1.0)
cost, edges = pso_tsp_tuned.run()
results['PSO_TSP_Path_Tuned'].append(cost)
print(f" PSO TSP Path Tuned: {cost:.2f} ({len(edges) if edges else 0} edges)")
# PSO MST Same
#print(f" Running PSO MST Same...")
pso_mst_same = PSO_MST(dist_matrix, n_particles=10, n_iterations=50,
w=0.7, c1=1.5, c2=1.5)
cost, edges = pso_mst_same.run()
results['PSO_MST_Same'].append(cost)
print(f" PSO MST Same: {cost:.2f} ({len(edges) if edges else 0} edges)")
if idx == 0 and edges:
first_solutions['mst_same'] = (edges, cost)
# PSO MST Tuned (w=0.8, c1=1.2, c2=1.8)
#print(f" Running PSO MST Tuned...")
pso_mst_tuned = PSO_MST(dist_matrix, n_particles=12, n_iterations=50,
w=0.8, c1=1.2, c2=1.8)
cost, edges = pso_mst_tuned.run()
results['PSO_MST_Tuned'].append(cost)
print(f" PSO MST Tuned: {cost:.2f} ({len(edges) if edges else 0} edges)")
# With Degree=3 constraints
for name, pso_class, params in [
('TSP_Path_Deg3_Same', PSO_TSP_Path, {'w': 0.7, 'c1': 1.5, 'c2': 1.5, 'n_particles': 10}),
('TSP_Path_Deg3_Tuned', PSO_TSP_Path, {'w': 0.6, 'c1': 2.0, 'c2': 1.0, 'n_particles': 15}),
('MST_Deg3_Same', PSO_MST, {'w': 0.7, 'c1': 1.5, 'c2': 1.5, 'n_particles': 10}),
('MST_Deg3_Tuned', PSO_MST, {'w': 0.8, 'c1': 1.2, 'c2': 1.8, 'n_particles': 12})
]:
#print(f" Running PSO {name}...")
pso = pso_class(dist_matrix, n_iterations=50, **params)
cost, edges = pso.run(max_degree=3)
if cost == float('inf'):
for _ in range(5):
cost, edges = pso.run(max_degree=3)
if cost != float('inf'):
break
results[f'PSO_{name}'].append(cost if cost != float('inf') else None)
edge_count = len(edges) if edges and cost != float('inf') else 0
print(f" PSO {name}: {cost:.2f} ({edge_count} edges)" if cost != float('inf')
else f" PSO {name}: No solution")
# Create DataFrame
df = pd.DataFrame(results)
print("\n" + "="*80)
print("RESULTS TABLE")
print("="*80)
print(df.to_string(index=False))
# Summary statistics
print("\n" + "="*80)
print("SUMMARY STATISTICS")
print("="*80)
def calc_stats(values):
clean_values = [v for v in values if v is not None and v != float('inf')]
if not clean_values:
return None, None, None, None
return (np.mean(clean_values), np.std(clean_values),
min(clean_values), max(clean_values))
summary_data = []
for col in df.columns:
if col != 'Dataset':
mean, std, min_val, max_val = calc_stats(df[col])
summary_data.append({
'Algorithm': col,
'Mean': mean,
'Std': std,
'Min': min_val,
'Max': max_val
})
summary = pd.DataFrame(summary_data)
print(summary.to_string(index=False))
# COMPARISON ANALYSIS
print("\n" + "="*80)
print("✅ PSO COMPARISON ANALYSIS (n-1 edges)")
print("="*80)
kruskal_mean = summary.iloc[0]['Mean']
pso_tsp_path_same_mean = summary.iloc[1]['Mean']
pso_mst_same_mean = summary.iloc[3]['Mean']
print(f"\nEdge Count: n-1 = {num_vertices - 1} edges")
print(f"\n1. Kruskal (Optimal): {kruskal_mean:.2f}")
print(f"2. PSO TSP Path: {pso_tsp_path_same_mean:.2f}")
print(f"3. PSO MST: {pso_mst_same_mean:.2f}")
tsp_gap = ((pso_tsp_path_same_mean / kruskal_mean) - 1) * 100
mst_gap = ((pso_mst_same_mean / kruskal_mean) - 1) * 100
print(f"\nGap from Optimal:")
print(f" PSO TSP Path vs Kruskal: {tsp_gap:+.2f}%")
print(f" PSO MST vs Kruskal: {mst_gap:+.2f}%")
print(f"\n✅ Fair comparison karena:")
print(f" • Same edge count: {num_vertices - 1} edges")
print(f" • No cycle: TSP Path & MST both are paths/trees")
print(f" • Apple-to-apple: Both connect all nodes without cycle")
# VISUALIZE FIRST DATASET
print("\n" + "="*80)
print("VISUALIZING FIRST DATASET RESULTS")
print("="*80)
dist_matrix_1, node_labels_1, G_complete_1 = datasets[0]
# 1. Visualize Complete Graph
print("\n1. Visualizing Complete Graph...")
plt.figure(figsize=(12, 10))
pos = nx.spring_layout(G_complete_1, seed=42, k=2)
nx.draw_networkx_nodes(G_complete_1, pos, node_color='lightgray',
node_size=800, alpha=0.6)
nx.draw_networkx_edges(G_complete_1, pos, width=1, alpha=0.2,
edge_color='gray')
nx.draw_networkx_labels(G_complete_1, pos, font_size=10, font_weight='bold')
edge_labels = {(u, v): f'{data["weight"]:.0f}'
for u, v, data in G_complete_1.edges(data=True)
if data['weight'] < 50}
nx.draw_networkx_edge_labels(G_complete_1, pos, edge_labels, font_size=7)
plt.title('Complete Graph - Dataset 1 (All Edges)',
fontsize=16, fontweight='bold', pad=20)
plt.axis('off')
plt.tight_layout()
plt.savefig(f'{folder_name}/complete_graph.png', dpi=150, bbox_inches='tight')
print(" ✓ Saved: complete_graph.png")
print(" 📊 Displaying graph...")
plt.show() # ← DISPLAY GRAPH
plt.close()
# 2. Visualize Kruskal MST
if 'kruskal' in first_solutions:
print("\n2. Visualizing Kruskal MST...")
edges, cost = first_solutions['kruskal']
visualize_solution(dist_matrix_1, edges, node_labels_1,
f'Kruskal MST - Dataset 1 (Weight={cost:.0f}, {len(edges)} edges)',
f'{folder_name}/kruskal_mst.png')
print(" ✓ Saved: kruskal_mst.png")
print(" 📊 Displaying graph...")
# Display the saved graph
img = plt.imread(f'{folder_name}/kruskal_mst.png')
plt.figure(figsize=(12, 10))
plt.imshow(img)
plt.axis('off')
plt.tight_layout()
plt.show()
plt.close()
# 3. Visualize PSO TSP Path
if 'tsp_same' in first_solutions:
print("\n3. Visualizing PSO TSP Path...")
edges, cost = first_solutions['tsp_same']
visualize_solution(dist_matrix_1, edges, node_labels_1,
f'PSO TSP Path - Dataset 1 (Weight={cost:.0f}, {len(edges)} edges)',
f'{folder_name}/pso_tsp_path.png')
print(" ✓ Saved: pso_tsp_path.png")
print(" 📊 Displaying graph...")
img = plt.imread(f'{folder_name}/pso_tsp_path.png')
plt.figure(figsize=(12, 10))
plt.imshow(img)
plt.axis('off')
plt.tight_layout()
plt.show()
plt.close()
# 4. Visualize PSO MST
if 'mst_same' in first_solutions:
print("\n4. Visualizing PSO MST...")
edges, cost = first_solutions['mst_same']
visualize_solution(dist_matrix_1, edges, node_labels_1,
f'PSO MST - Dataset 1 (Weight={cost:.0f}, {len(edges)} edges)',
f'{folder_name}/pso_mst.png')
print(" ✓ Saved: pso_mst.png")
print(" 📊 Displaying graph...")
img = plt.imread(f'{folder_name}/pso_mst.png')
plt.figure(figsize=(12, 10))
plt.imshow(img)
plt.axis('off')
plt.tight_layout()
plt.show()
plt.close()
# 5. Creating comparison plots
print("\n5. Creating comparison plots...")
fig, axes = plt.subplots(2, 2, figsize=(16, 12))
# Plot 1: Fair Comparison (n-1 edges)
ax1 = axes[0, 0]
fair_data = [
[v for v in df['Kruskal'].values if v is not None],
[v for v in df['PSO_TSP_Path_Same'].values if v is not None],
[v for v in df['PSO_MST_Same'].values if v is not None]
]
bp1 = ax1.boxplot(fair_data, labels=['Kruskal\n(Optimal)', 'PSO TSP Path\n(Same)', 'PSO MST\n(Same)'],
patch_artist=True)
colors = ['lightgreen', 'lightblue', 'lightcoral']
for patch, color in zip(bp1['boxes'], colors):
patch.set_facecolor(color)
ax1.set_title('✅ Fair Comparison: PSO (All n-1 edges)',
fontsize=14, fontweight='bold')
ax1.set_ylabel('Total Weight', fontsize=12)
ax1.grid(True, alpha=0.3)
# Plot 2: With Degree Constraint
ax2 = axes[0, 1]
deg_data = [
[v for v in df['PSO_TSP_Path_Deg3_Same'].values
if v is not None and v != float('inf')],
[v for v in df['PSO_MST_Deg3_Same'].values
if v is not None and v != float('inf')]
]
if all(len(d) > 0 for d in deg_data):
bp2 = ax2.boxplot(deg_data, labels=['PSO TSP Path\nDeg3', 'PSO MST\nDeg3'],
patch_artist=True)
for patch, color in zip(bp2['boxes'], ['lightblue', 'lightcoral']):
patch.set_facecolor(color)
ax2.set_title('PSO with Degree Constraint = 3',
fontsize=14, fontweight='bold')
ax2.set_ylabel('Total Weight', fontsize=12)
ax2.grid(True, alpha=0.3)
else:
ax2.text(0.5, 0.5, 'Insufficient data for\nDegree=3 constraint',
ha='center', va='center', fontsize=12)
ax2.set_title('PSO with Degree Constraint = 3',
fontsize=14, fontweight='bold')
# Plot 3: Bar comparison
ax3 = axes[1, 0]
means = [m if m is not None else 0 for m in summary['Mean'].values[:5]]
colors_bar = ['green', 'blue', 'lightblue', 'purple', 'orchid']
bars = ax3.bar(range(len(means)), means, color=colors_bar, alpha=0.7)
ax3.set_xticks(range(len(means)))
ax3.set_xticklabels(['Kruskal', 'PSO TSP\nSame', 'PSO TSP\nTuned',
'PSO MST\nSame', 'PSO MST\nTuned'], fontsize=9)
ax3.set_title('PSO Mean Performance (n-1 edges)',
fontsize=14, fontweight='bold')
ax3.set_ylabel('Mean Weight', fontsize=12)
ax3.grid(True, alpha=0.3, axis='y')
for bar, val in zip(bars, means):
if val > 0:
ax3.text(bar.get_x() + bar.get_width()/2, bar.get_height() + 5,
f'{val:.0f}', ha='center', va='bottom', fontsize=9)
# Plot 4: Edge count verification
ax4 = axes[1, 1]
edge_counts = [num_vertices - 1, num_vertices - 1, num_vertices - 1]
labels_edge = ['Kruskal', 'PSO TSP Path', 'PSO MST']
bars4 = ax4.bar(labels_edge, edge_counts,
color=['green', 'blue', 'purple'], alpha=0.7)
ax4.set_title('✅ Edge Count Verification (Fair!)',
fontsize=14, fontweight='bold')
ax4.set_ylabel('Number of Edges', fontsize=12)
ax4.axhline(y=num_vertices - 1, color='r', linestyle='--',
label=f'n-1 = {num_vertices - 1}')
ax4.legend()
ax4.grid(True, alpha=0.3, axis='y')
for i, (label, count) in enumerate(zip(labels_edge, edge_counts)):
ax4.text(i, count + 0.1, str(count), ha='center', va='bottom',
fontsize=12, fontweight='bold')
plt.tight_layout()
plt.savefig(f'{folder_name}/pso_comparison.png', dpi=300, bbox_inches='tight')
print(" ✓ Saved: pso_comparison.png")
print(" 📊 Displaying comparison plots...")
plt.show() # ← DISPLAY COMPARISON PLOTS
plt.close()
# Additional: PSO vs ACO Comparison Plot
print("\n6. Creating PSO vs ACO comparison...")
# Try to load ACO results if available
try:
df_aco = pd.read_csv('results/fair_aco_results.csv')
fig, axes = plt.subplots(1, 2, figsize=(16, 6))
# MST Comparison
ax1 = axes[0]
mst_comparison = [
[v for v in df['Kruskal'].values if v is not None],
[v for v in df_aco['ACO_MST_Same'].values if v is not None],
[v for v in df['PSO_MST_Same'].values if v is not None]
]
bp1 = ax1.boxplot(mst_comparison,
labels=['Kruskal\n(Optimal)', 'ACO MST', 'PSO MST'],
patch_artist=True)
colors = ['lightgreen', 'lightyellow', 'lightblue']
for patch, color in zip(bp1['boxes'], colors):
patch.set_facecolor(color)
ax1.set_title('MST Performance: Kruskal vs ACO vs PSO',
fontsize=14, fontweight='bold')
ax1.set_ylabel('Total Weight', fontsize=12)
ax1.grid(True, alpha=0.3)
# Calculate means for annotation
aco_mst_mean = np.mean([v for v in df_aco['ACO_MST_Same'].values
if v is not None])
pso_mst_mean = np.mean([v for v in df['PSO_MST_Same'].values
if v is not None])
kruskal_mean_val = np.mean([v for v in df['Kruskal'].values
if v is not None])
aco_gap = ((aco_mst_mean / kruskal_mean_val) - 1) * 100
pso_gap = ((pso_mst_mean / kruskal_mean_val) - 1) * 100
ax1.text(0.5, 0.98, f'ACO Gap: +{aco_gap:.2f}% | PSO Gap: +{pso_gap:.2f}%',
transform=ax1.transAxes, ha='center', va='top',
bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.5))
# TSP Comparison
ax2 = axes[1]
tsp_comparison = [
[v for v in df_aco['ACO_TSP_Path_Same'].values if v is not None],
[v for v in df['PSO_TSP_Path_Same'].values if v is not None]
]
bp2 = ax2.boxplot(tsp_comparison, labels=['ACO TSP Path', 'PSO TSP Path'],
patch_artist=True)
colors = ['lightyellow', 'lightblue']
for patch, color in zip(bp2['boxes'], colors):
patch.set_facecolor(color)
ax2.set_title('TSP Path Performance: ACO vs PSO',
fontsize=14, fontweight='bold')
ax2.set_ylabel('Total Weight', fontsize=12)
ax2.grid(True, alpha=0.3)
# Calculate TSP gaps
aco_tsp_mean = np.mean([v for v in df_aco['ACO_TSP_Path_Same'].values
if v is not None])
pso_tsp_mean = np.mean([v for v in df['PSO_TSP_Path_Same'].values
if v is not None])
aco_tsp_gap = ((aco_tsp_mean / kruskal_mean_val) - 1) * 100
pso_tsp_gap = ((pso_tsp_mean / kruskal_mean_val) - 1) * 100
ax2.text(0.5, 0.98,
f'ACO Gap: +{aco_tsp_gap:.2f}% | PSO Gap: +{pso_tsp_gap:.2f}%',
transform=ax2.transAxes, ha='center', va='top',
bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.5))
plt.tight_layout()
plt.savefig(f'{folder_name}/pso_vs_aco_comparison.png',
dpi=300, bbox_inches='tight')
print(" ✓ Saved: pso_vs_aco_comparison.png")
print(" 📊 Displaying PSO vs ACO comparison...")
plt.show() # ← DISPLAY PSO vs ACO
plt.close()
except FileNotFoundError:
print(" ⓘ ACO results not found, skipping ACO vs PSO comparison")
# Save results
df.to_csv(f'{folder_name}/{str(INDEX)}pso_results.csv', index=False)
print("\n ✓ Saved: pso_results.csv")
print("\n" + "="*80)
print("✅ COMPLETED!")
print("="*80)
print(f"\nFiles saved to '{folder_name}/' folder:")
print(" 📊 pso_results.csv - Numerical results")
print(" 📈 pso_comparison.png - PSO comparison plots")
print(" 🌐 complete_graph.png - Full graph visualization")
print(" 🌳 kruskal_mst.png - Kruskal MST result")
print(" 🛤️ pso_tsp_path.png - PSO TSP Path result")
print(" 🌲 pso_mst.png - PSO MST result")
if os.path.exists(f'{folder_name}/pso_vs_aco_comparison.png'):
print(" 🔄 pso_vs_aco_comparison.png - PSO vs ACO comparison")
print("\n💡 KEY FINDINGS:")
print(f" • All methods use n-1 = {num_vertices - 1} edges (FAIR!)")
print(f" • PSO TSP Path: NO cycle (like MST)")
print(f" • Kruskal: {kruskal_mean:.2f} (optimal)")
print(f" • PSO TSP Path: {pso_tsp_path_same_mean:.2f} ({tsp_gap:+.2f}%)")
print(f" • PSO MST: {pso_mst_same_mean:.2f} ({mst_gap:+.2f}%)")
print("\n🔬 PSO CHARACTERISTICS:")
print(" • Uses velocity and position updates")
print(" • Personal best (pbest) + Global best (gbest)")
print(" • NO pheromone matrix (unlike ACO)")
print(" • Direct communication via gbest")
print(" • Iterative improvement approach")
================================================================================
PSO COMPARISON: TSP PATH vs MST (SAME n-1 EDGES) 30 Vertex
================================================================================
Loading datasets from CSV...
Loaded 30 datasets with 30 vertices each
================================================================================
RUNNING EXPERIMENTS...
================================================================================
Dataset 1:
Kruskal MST: 1158.00 (29 edges)
PSO TSP Path Same: 3779.00 (29 edges)
PSO TSP Path Tuned: 3869.00 (29 edges)
PSO MST Same: 2441.00 (29 edges)
PSO MST Tuned: 1585.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4333.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3597.00 (29 edges)
PSO MST_Deg3_Same: 2555.00 (29 edges)
PSO MST_Deg3_Tuned: 2000.00 (29 edges)
Dataset 2:
Kruskal MST: 799.00 (29 edges)
PSO TSP Path Same: 3252.00 (29 edges)
PSO TSP Path Tuned: 3747.00 (29 edges)
PSO MST Same: 1013.00 (29 edges)
PSO MST Tuned: 923.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3689.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3464.00 (29 edges)
PSO MST_Deg3_Same: 839.00 (29 edges)
PSO MST_Deg3_Tuned: 1052.00 (29 edges)
Dataset 3:
Kruskal MST: 1780.00 (29 edges)
PSO TSP Path Same: 4555.00 (29 edges)
PSO TSP Path Tuned: 4090.00 (29 edges)
PSO MST Same: 2617.00 (29 edges)
PSO MST Tuned: 2456.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4358.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 4661.00 (29 edges)
PSO MST_Deg3_Same: 3001.00 (29 edges)
PSO MST_Deg3_Tuned: 2399.00 (29 edges)
Dataset 4:
Kruskal MST: 1246.00 (29 edges)
PSO TSP Path Same: 3612.00 (29 edges)
PSO TSP Path Tuned: 3573.00 (29 edges)
PSO MST Same: 1579.00 (29 edges)
PSO MST Tuned: 1961.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4176.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3568.00 (29 edges)
PSO MST_Deg3_Same: 2044.00 (29 edges)
PSO MST_Deg3_Tuned: 1284.00 (29 edges)
Dataset 5:
Kruskal MST: 1411.00 (29 edges)
PSO TSP Path Same: 3628.00 (29 edges)
PSO TSP Path Tuned: 4300.00 (29 edges)
PSO MST Same: 1574.00 (29 edges)
PSO MST Tuned: 1789.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4466.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 4033.00 (29 edges)
PSO MST_Deg3_Same: 1749.00 (29 edges)
PSO MST_Deg3_Tuned: 1690.00 (29 edges)
Dataset 6:
Kruskal MST: 1105.00 (29 edges)
PSO TSP Path Same: 3017.00 (29 edges)
PSO TSP Path Tuned: 3340.00 (29 edges)
PSO MST Same: 2194.00 (29 edges)
PSO MST Tuned: 1495.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3335.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3152.00 (29 edges)
PSO MST_Deg3_Same: 1717.00 (29 edges)
PSO MST_Deg3_Tuned: 2207.00 (29 edges)
Dataset 7:
Kruskal MST: 1270.00 (29 edges)
PSO TSP Path Same: 4207.00 (29 edges)
PSO TSP Path Tuned: 3835.00 (29 edges)
PSO MST Same: 2544.00 (29 edges)
PSO MST Tuned: 1911.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4026.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 4158.00 (29 edges)
PSO MST_Deg3_Same: 2339.00 (29 edges)
PSO MST_Deg3_Tuned: 1740.00 (29 edges)
Dataset 8:
Kruskal MST: 1367.00 (29 edges)
PSO TSP Path Same: 4068.00 (29 edges)
PSO TSP Path Tuned: 3840.00 (29 edges)
PSO MST Same: 2771.00 (29 edges)
PSO MST Tuned: 2194.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3640.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3876.00 (29 edges)
PSO MST_Deg3_Same: 2239.00 (29 edges)
PSO MST_Deg3_Tuned: 2214.00 (29 edges)
Dataset 9:
Kruskal MST: 1209.00 (29 edges)
PSO TSP Path Same: 3533.00 (29 edges)
PSO TSP Path Tuned: 3445.00 (29 edges)
PSO MST Same: 1362.00 (29 edges)
PSO MST Tuned: 1532.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3116.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3447.00 (29 edges)
PSO MST_Deg3_Same: 1824.00 (29 edges)
PSO MST_Deg3_Tuned: 1396.00 (29 edges)
Dataset 10:
Kruskal MST: 878.00 (29 edges)
PSO TSP Path Same: 3023.00 (29 edges)
PSO TSP Path Tuned: 2653.00 (29 edges)
PSO MST Same: 1768.00 (29 edges)
PSO MST Tuned: 1660.00 (29 edges)
PSO TSP_Path_Deg3_Same: 2769.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 2667.00 (29 edges)
PSO MST_Deg3_Same: 1139.00 (29 edges)
PSO MST_Deg3_Tuned: 1005.00 (29 edges)
Dataset 11:
Kruskal MST: 1357.00 (29 edges)
PSO TSP Path Same: 3537.00 (29 edges)
PSO TSP Path Tuned: 3705.00 (29 edges)
PSO MST Same: 1938.00 (29 edges)
PSO MST Tuned: 1463.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3214.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3806.00 (29 edges)
PSO MST_Deg3_Same: 1658.00 (29 edges)
PSO MST_Deg3_Tuned: 2076.00 (29 edges)
Dataset 12:
Kruskal MST: 1115.00 (29 edges)
PSO TSP Path Same: 3874.00 (29 edges)
PSO TSP Path Tuned: 3646.00 (29 edges)
PSO MST Same: 1949.00 (29 edges)
PSO MST Tuned: 1597.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3723.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3880.00 (29 edges)
PSO MST_Deg3_Same: 1738.00 (29 edges)
PSO MST_Deg3_Tuned: 1340.00 (29 edges)
Dataset 13:
Kruskal MST: 760.00 (29 edges)
PSO TSP Path Same: 2400.00 (29 edges)
PSO TSP Path Tuned: 2854.00 (29 edges)
PSO MST Same: 1006.00 (29 edges)
PSO MST Tuned: 852.00 (29 edges)
PSO TSP_Path_Deg3_Same: 2761.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 2888.00 (29 edges)
PSO MST_Deg3_Same: 981.00 (29 edges)
PSO MST_Deg3_Tuned: 1116.00 (29 edges)
Dataset 14:
Kruskal MST: 804.00 (29 edges)
PSO TSP Path Same: 2905.00 (29 edges)
PSO TSP Path Tuned: 2828.00 (29 edges)
PSO MST Same: 870.00 (29 edges)
PSO MST Tuned: 986.00 (29 edges)
PSO TSP_Path_Deg3_Same: 2689.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 2934.00 (29 edges)
PSO MST_Deg3_Same: 1032.00 (29 edges)
PSO MST_Deg3_Tuned: 1050.00 (29 edges)
Dataset 15:
Kruskal MST: 793.00 (29 edges)
PSO TSP Path Same: 3325.00 (29 edges)
PSO TSP Path Tuned: 3300.00 (29 edges)
PSO MST Same: 1335.00 (29 edges)
PSO MST Tuned: 1256.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3393.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3419.00 (29 edges)
PSO MST_Deg3_Same: 2243.00 (29 edges)
PSO MST_Deg3_Tuned: 1103.00 (29 edges)
Dataset 16:
Kruskal MST: 1370.00 (29 edges)
PSO TSP Path Same: 4145.00 (29 edges)
PSO TSP Path Tuned: 4189.00 (29 edges)
PSO MST Same: 2280.00 (29 edges)
PSO MST Tuned: 2460.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3989.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3345.00 (29 edges)
PSO MST_Deg3_Same: 3154.00 (29 edges)
PSO MST_Deg3_Tuned: 2124.00 (29 edges)
Dataset 17:
Kruskal MST: 1182.00 (29 edges)
PSO TSP Path Same: 3478.00 (29 edges)
PSO TSP Path Tuned: 3639.00 (29 edges)
PSO MST Same: 2053.00 (29 edges)
PSO MST Tuned: 1439.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3895.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3567.00 (29 edges)
PSO MST_Deg3_Same: 1582.00 (29 edges)
PSO MST_Deg3_Tuned: 1935.00 (29 edges)
Dataset 18:
Kruskal MST: 1410.00 (29 edges)
PSO TSP Path Same: 4420.00 (29 edges)
PSO TSP Path Tuned: 4004.00 (29 edges)
PSO MST Same: 1450.00 (29 edges)
PSO MST Tuned: 2118.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4668.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 4058.00 (29 edges)
PSO MST_Deg3_Same: 1770.00 (29 edges)
PSO MST_Deg3_Tuned: 2045.00 (29 edges)
Dataset 19:
Kruskal MST: 1108.00 (29 edges)
PSO TSP Path Same: 3682.00 (29 edges)
PSO TSP Path Tuned: 3639.00 (29 edges)
PSO MST Same: 1808.00 (29 edges)
PSO MST Tuned: 1882.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3232.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3639.00 (29 edges)
PSO MST_Deg3_Same: 1834.00 (29 edges)
PSO MST_Deg3_Tuned: 1652.00 (29 edges)
Dataset 20:
Kruskal MST: 1085.00 (29 edges)
PSO TSP Path Same: 3090.00 (29 edges)
PSO TSP Path Tuned: 3286.00 (29 edges)
PSO MST Same: 1809.00 (29 edges)
PSO MST Tuned: 1732.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3468.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3265.00 (29 edges)
PSO MST_Deg3_Same: 1829.00 (29 edges)
PSO MST_Deg3_Tuned: 1605.00 (29 edges)
Dataset 21:
Kruskal MST: 1147.00 (29 edges)
PSO TSP Path Same: 3127.00 (29 edges)
PSO TSP Path Tuned: 3109.00 (29 edges)
PSO MST Same: 1706.00 (29 edges)
PSO MST Tuned: 1425.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3095.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3110.00 (29 edges)
PSO MST_Deg3_Same: 1939.00 (29 edges)
PSO MST_Deg3_Tuned: 1637.00 (29 edges)
Dataset 22:
Kruskal MST: 1364.00 (29 edges)
PSO TSP Path Same: 2996.00 (29 edges)
PSO TSP Path Tuned: 3456.00 (29 edges)
PSO MST Same: 1392.00 (29 edges)
PSO MST Tuned: 1576.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3335.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3752.00 (29 edges)
PSO MST_Deg3_Same: 1562.00 (29 edges)
PSO MST_Deg3_Tuned: 1974.00 (29 edges)
Dataset 23:
Kruskal MST: 1080.00 (29 edges)
PSO TSP Path Same: 3283.00 (29 edges)
PSO TSP Path Tuned: 3017.00 (29 edges)
PSO MST Same: 1205.00 (29 edges)
PSO MST Tuned: 1292.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3541.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3370.00 (29 edges)
PSO MST_Deg3_Same: 1102.00 (29 edges)
PSO MST_Deg3_Tuned: 1237.00 (29 edges)
Dataset 24:
Kruskal MST: 1301.00 (29 edges)
PSO TSP Path Same: 4085.00 (29 edges)
PSO TSP Path Tuned: 3905.00 (29 edges)
PSO MST Same: 2276.00 (29 edges)
PSO MST Tuned: 2370.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3955.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3768.00 (29 edges)
PSO MST_Deg3_Same: 2487.00 (29 edges)
PSO MST_Deg3_Tuned: 2469.00 (29 edges)
Dataset 25:
Kruskal MST: 854.00 (29 edges)
PSO TSP Path Same: 2917.00 (29 edges)
PSO TSP Path Tuned: 2879.00 (29 edges)
PSO MST Same: 1458.00 (29 edges)
PSO MST Tuned: 1369.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3481.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 2943.00 (29 edges)
PSO MST_Deg3_Same: 1079.00 (29 edges)
PSO MST_Deg3_Tuned: 997.00 (29 edges)
Dataset 26:
Kruskal MST: 1322.00 (29 edges)
PSO TSP Path Same: 3794.00 (29 edges)
PSO TSP Path Tuned: 3954.00 (29 edges)
PSO MST Same: 1908.00 (29 edges)
PSO MST Tuned: 2056.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4089.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3666.00 (29 edges)
PSO MST_Deg3_Same: 2387.00 (29 edges)
PSO MST_Deg3_Tuned: 2234.00 (29 edges)
Dataset 27:
Kruskal MST: 1247.00 (29 edges)
PSO TSP Path Same: 4234.00 (29 edges)
PSO TSP Path Tuned: 3600.00 (29 edges)
PSO MST Same: 2120.00 (29 edges)
PSO MST Tuned: 1973.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4215.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 4131.00 (29 edges)
PSO MST_Deg3_Same: 2824.00 (29 edges)
PSO MST_Deg3_Tuned: 2366.00 (29 edges)
Dataset 28:
Kruskal MST: 1031.00 (29 edges)
PSO TSP Path Same: 3487.00 (29 edges)
PSO TSP Path Tuned: 3317.00 (29 edges)
PSO MST Same: 1031.00 (29 edges)
PSO MST Tuned: 1220.00 (29 edges)
PSO TSP_Path_Deg3_Same: 3455.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3403.00 (29 edges)
PSO MST_Deg3_Same: 1368.00 (29 edges)
PSO MST_Deg3_Tuned: 1290.00 (29 edges)
Dataset 29:
Kruskal MST: 1395.00 (29 edges)
PSO TSP Path Same: 3766.00 (29 edges)
PSO TSP Path Tuned: 4113.00 (29 edges)
PSO MST Same: 2114.00 (29 edges)
PSO MST Tuned: 2379.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4181.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3661.00 (29 edges)
PSO MST_Deg3_Same: 1518.00 (29 edges)
PSO MST_Deg3_Tuned: 2478.00 (29 edges)
Dataset 30:
Kruskal MST: 1375.00 (29 edges)
PSO TSP Path Same: 3825.00 (29 edges)
PSO TSP Path Tuned: 4275.00 (29 edges)
PSO MST Same: 2508.00 (29 edges)
PSO MST Tuned: 1749.00 (29 edges)
PSO TSP_Path_Deg3_Same: 4042.00 (29 edges)
PSO TSP_Path_Deg3_Tuned: 3924.00 (29 edges)
PSO MST_Deg3_Same: 2201.00 (29 edges)
PSO MST_Deg3_Tuned: 2300.00 (29 edges)
================================================================================
RESULTS TABLE
================================================================================
Dataset Kruskal PSO_TSP_Path_Same PSO_TSP_Path_Tuned PSO_MST_Same PSO_MST_Tuned PSO_TSP_Path_Deg3_Same PSO_TSP_Path_Deg3_Tuned PSO_MST_Deg3_Same PSO_MST_Deg3_Tuned
D1 1158.0 3779.0 3869.0 2441.0 1585.0 4333.0 3597.0 2555.0 2000.0
D2 799.0 3252.0 3747.0 1013.0 923.0 3689.0 3464.0 839.0 1052.0
D3 1780.0 4555.0 4090.0 2617.0 2456.0 4358.0 4661.0 3001.0 2399.0
D4 1246.0 3612.0 3573.0 1579.0 1961.0 4176.0 3568.0 2044.0 1284.0
D5 1411.0 3628.0 4300.0 1574.0 1789.0 4466.0 4033.0 1749.0 1690.0
D6 1105.0 3017.0 3340.0 2194.0 1495.0 3335.0 3152.0 1717.0 2207.0
D7 1270.0 4207.0 3835.0 2544.0 1911.0 4026.0 4158.0 2339.0 1740.0
D8 1367.0 4068.0 3840.0 2771.0 2194.0 3640.0 3876.0 2239.0 2214.0
D9 1209.0 3533.0 3445.0 1362.0 1532.0 3116.0 3447.0 1824.0 1396.0
D10 878.0 3023.0 2653.0 1768.0 1660.0 2769.0 2667.0 1139.0 1005.0
D11 1357.0 3537.0 3705.0 1938.0 1463.0 3214.0 3806.0 1658.0 2076.0
D12 1115.0 3874.0 3646.0 1949.0 1597.0 3723.0 3880.0 1738.0 1340.0
D13 760.0 2400.0 2854.0 1006.0 852.0 2761.0 2888.0 981.0 1116.0
D14 804.0 2905.0 2828.0 870.0 986.0 2689.0 2934.0 1032.0 1050.0
D15 793.0 3325.0 3300.0 1335.0 1256.0 3393.0 3419.0 2243.0 1103.0
D16 1370.0 4145.0 4189.0 2280.0 2460.0 3989.0 3345.0 3154.0 2124.0
D17 1182.0 3478.0 3639.0 2053.0 1439.0 3895.0 3567.0 1582.0 1935.0
D18 1410.0 4420.0 4004.0 1450.0 2118.0 4668.0 4058.0 1770.0 2045.0
D19 1108.0 3682.0 3639.0 1808.0 1882.0 3232.0 3639.0 1834.0 1652.0
D20 1085.0 3090.0 3286.0 1809.0 1732.0 3468.0 3265.0 1829.0 1605.0
D21 1147.0 3127.0 3109.0 1706.0 1425.0 3095.0 3110.0 1939.0 1637.0
D22 1364.0 2996.0 3456.0 1392.0 1576.0 3335.0 3752.0 1562.0 1974.0
D23 1080.0 3283.0 3017.0 1205.0 1292.0 3541.0 3370.0 1102.0 1237.0
D24 1301.0 4085.0 3905.0 2276.0 2370.0 3955.0 3768.0 2487.0 2469.0
D25 854.0 2917.0 2879.0 1458.0 1369.0 3481.0 2943.0 1079.0 997.0
D26 1322.0 3794.0 3954.0 1908.0 2056.0 4089.0 3666.0 2387.0 2234.0
D27 1247.0 4234.0 3600.0 2120.0 1973.0 4215.0 4131.0 2824.0 2366.0
D28 1031.0 3487.0 3317.0 1031.0 1220.0 3455.0 3403.0 1368.0 1290.0
D29 1395.0 3766.0 4113.0 2114.0 2379.0 4181.0 3661.0 1518.0 2478.0
D30 1375.0 3825.0 4275.0 2508.0 1749.0 4042.0 3924.0 2201.0 2300.0
================================================================================
SUMMARY STATISTICS
================================================================================
Algorithm Mean Std Min Max
Kruskal 1177.433333 231.457798 760.0 1780.0
PSO_TSP_Path_Same 3568.133333 501.681555 2400.0 4555.0
PSO_TSP_Path_Tuned 3580.233333 444.241802 2653.0 4300.0
PSO_MST_Same 1802.633333 516.072959 870.0 2771.0
PSO_MST_Tuned 1690.000000 435.138982 852.0 2460.0
PSO_TSP_Path_Deg3_Same 3677.633333 519.989198 2689.0 4668.0
PSO_TSP_Path_Deg3_Tuned 3571.733333 427.957625 2667.0 4661.0
PSO_MST_Deg3_Same 1857.800000 593.440219 839.0 3154.0
PSO_MST_Deg3_Tuned 1733.833333 491.018743 997.0 2478.0
================================================================================
✅ PSO COMPARISON ANALYSIS (n-1 edges)
================================================================================
Edge Count: n-1 = 29 edges
1. Kruskal (Optimal): 1177.43
2. PSO TSP Path: 3568.13
3. PSO MST: 1802.63
Gap from Optimal:
PSO TSP Path vs Kruskal: +203.04%
PSO MST vs Kruskal: +53.10%
✅ Fair comparison karena:
• Same edge count: 29 edges
• No cycle: TSP Path & MST both are paths/trees
• Apple-to-apple: Both connect all nodes without cycle
================================================================================
VISUALIZING FIRST DATASET RESULTS
================================================================================
1. Visualizing Complete Graph...
✓ Saved: complete_graph.png
📊 Displaying graph...
2. Visualizing Kruskal MST... ✓ Saved: kruskal_mst.png 📊 Displaying graph...
3. Visualizing PSO TSP Path... ✓ Saved: pso_tsp_path.png 📊 Displaying graph...
4. Visualizing PSO MST... ✓ Saved: pso_mst.png 📊 Displaying graph...
5. Creating comparison plots... ✓ Saved: pso_comparison.png 📊 Displaying comparison plots...
6. Creating PSO vs ACO comparison... ⓘ ACO results not found, skipping ACO vs PSO comparison ✓ Saved: pso_results.csv ================================================================================ ✅ COMPLETED! ================================================================================ Files saved to 'results_pso/' folder: 📊 pso_results.csv - Numerical results 📈 pso_comparison.png - PSO comparison plots 🌐 complete_graph.png - Full graph visualization 🌳 kruskal_mst.png - Kruskal MST result 🛤️ pso_tsp_path.png - PSO TSP Path result 🌲 pso_mst.png - PSO MST result 💡 KEY FINDINGS: • All methods use n-1 = 29 edges (FAIR!) • PSO TSP Path: NO cycle (like MST) • Kruskal: 1177.43 (optimal) • PSO TSP Path: 3568.13 (+203.04%) • PSO MST: 1802.63 (+53.10%) 🔬 PSO CHARACTERISTICS: • Uses velocity and position updates • Personal best (pbest) + Global best (gbest) • NO pheromone matrix (unlike ACO) • Direct communication via gbest • Iterative improvement approach
In [ ]: