!pip install loguru
!pip install tsplib95 The history saving thread hit an unexpected error (OperationalError('attempt to write a readonly database')).History will not be written to the database.
Collecting loguru
Downloading loguru-0.7.3-py3-none-any.whl.metadata (22 kB)
Downloading loguru-0.7.3-py3-none-any.whl (61 kB)
[2K [90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━[0m [32m61.6/61.6 kB[0m [31m4.1 MB/s[0m eta [36m0:00:00[0m
[?25hInstalling collected packages: loguru
Successfully installed loguru-0.7.3
Collecting tsplib95
Downloading tsplib95-0.7.1-py2.py3-none-any.whl.metadata (6.3 kB)
Requirement already satisfied: Click>=6.0 in /usr/local/lib/python3.10/dist-packages (from tsplib95) (8.1.7)
Requirement already satisfied: Deprecated~=1.2.9 in /usr/local/lib/python3.10/dist-packages (from tsplib95) (1.2.15)
Collecting networkx~=2.1 (from tsplib95)
Downloading networkx-2.8.8-py3-none-any.whl.metadata (5.1 kB)
Collecting tabulate~=0.8.7 (from tsplib95)
Downloading tabulate-0.8.10-py3-none-any.whl.metadata (25 kB)
Requirement already satisfied: wrapt<2,>=1.10 in /usr/local/lib/python3.10/dist-packages (from Deprecated~=1.2.9->tsplib95) (1.16.0)
Downloading tsplib95-0.7.1-py2.py3-none-any.whl (25 kB)
Downloading networkx-2.8.8-py3-none-any.whl (2.0 MB)
[2K [90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━[0m [32m2.0/2.0 MB[0m [31m54.5 MB/s[0m eta [36m0:00:00[0m:00:01[0m
[?25hDownloading tabulate-0.8.10-py3-none-any.whl (29 kB)
Installing collected packages: tabulate, networkx, tsplib95
Attempting uninstall: tabulate
Found existing installation: tabulate 0.9.0
Uninstalling tabulate-0.9.0:
Successfully uninstalled tabulate-0.9.0
Attempting uninstall: networkx
Found existing installation: networkx 3.3
Uninstalling networkx-3.3:
Successfully uninstalled networkx-3.3
[31mERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.
bigframes 1.17.0 requires tabulate>=0.9, but you have tabulate 0.8.10 which is incompatible.[0m[31m
[0mSuccessfully installed networkx-2.8.8 tabulate-0.8.10 tsplib95-0.7.1— Cell 0: Library Imports and Setup (Extra) —
# Standard library imports
import os # Operating system functionalities, file handling
import json # JSON encoding and decoding
import math # Mathematical functions, distance calculations
import random # Random number generation, for algorithms
import gzip # For handling .gz files
from typing import List, Dict, Tuple, Any # Type hinting for better code clarity
# Third-party library imports
import requests # HTTP requests for downloading files
import tsplib95 # Library for handling TSPLIB files
from tsplib95 import models # Import the models submodule from tsplib95
import networkx as nx # Graph library, for TSP solving
import matplotlib.pyplot as plt # Plotting library, base for seaborn
import seaborn as sns # Statistical data visualization
import numpy as np # Numerical operations, arrays
from loguru import logger # Logging library for structured logging
# Global variables
BASE_URL = "http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/"
FILENAME = "berlin52.tsp.gz"
OUTPUT_FOLDER = "output" # Using a relative path for better portability
INPUT_FOLDER = "tsp_data"— Cell 1: Data Retrieval and Extraction (Task a. Question 1) —
def download_file(url: str, filename: str, input_folder: str, output_folder: str = OUTPUT_FOLDER) -> str | None:
"""Downloads a file and saves it to the specified folder."""
try:
response = requests.get(url, stream=True)
response.raise_for_status()
os.makedirs(os.path.join(output_folder, input_folder, "raw"), exist_ok=True)
full_path = os.path.join(output_folder, input_folder, "raw", filename)
with open(full_path, 'wb') as file:
for chunk in response.iter_content(chunk_size=8192):
file.write(chunk)
logger.info(f"Downloaded file: {filename}")
return full_path
except requests.exceptions.RequestException as e:
logger.error(f"Error downloading file: {e}")
return None
def extract_gz_file(file_path: str, extract_to: str) -> str | None:
"""Extracts a .gz file."""
try:
os.makedirs(extract_to, exist_ok=True)
output_file = os.path.join(extract_to, os.path.splitext(os.path.basename(file_path))[0])
with gzip.open(file_path, 'rb') as f_in:
with open(output_file, 'wb') as f_out:
f_out.write(f_in.read())
logger.info(f"Extracted {file_path} to {output_file}")
return output_file
except Exception as e:
logger.error(f"Error extracting gz file: {e}")
return None
# --- Download and Extract the TSP Data ---
file_url = BASE_URL + FILENAME
downloaded_file = download_file(file_url, FILENAME, INPUT_FOLDER)
if downloaded_file:
extracted_folder = os.path.join(OUTPUT_FOLDER, INPUT_FOLDER, "extracted")
extracted_file = extract_gz_file(downloaded_file, extracted_folder)
if extracted_file:
logger.info(f"Successfully extracted: {extracted_file}")
else:
logger.error("Failed to extract the file.")
else:
logger.error("Failed to download the file.")[32m2024-12-21 14:09:50.036[0m | [1mINFO [0m | [36m__main__[0m:[36mdownload_file[0m:[36m11[0m - [1mDownloaded file: berlin52.tsp.gz[0m
[32m2024-12-21 14:09:50.038[0m | [1mINFO [0m | [36m__main__[0m:[36mextract_gz_file[0m:[36m25[0m - [1mExtracted output/tsp_data/raw/berlin52.tsp.gz to output/tsp_data/extracted/berlin52.tsp[0m
[32m2024-12-21 14:09:50.038[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 35>[0m:[36m39[0m - [1mSuccessfully extracted: output/tsp_data/extracted/berlin52.tsp[0m— Cell 2: TSPLIB File Parsing (Task a. Question 1) —
def parse_tsplib_file(filename: str) -> Dict[str, Any] | None:
"""Parses a TSPLIB file and extracts relevant data."""
try:
with open(filename, 'r') as file:
lines = file.readlines()
data: Dict[str, Any] = {}
section = None
for line in lines:
line = line.strip()
if not line or line.startswith("COMMENT"):
continue
if ":" in line:
key, value = line.split(":", 1)
key = key.strip()
value = value.strip()
data[key] = value
if key in ("NODE_COORD_SECTION", "EDGE_WEIGHT_SECTION"):
section = key
data[section] = []
elif section:
if line == "EOF":
section = None
continue
data[section].append(line)
return data
except FileNotFoundError:
logger.error(f"File not found: {filename}")
return None
except Exception as e:
logger.error(f"Error parsing TSPLIB file: {e}")
return None
# Parse the extracted file
if extracted_file:
parsed_data = parse_tsplib_file(extracted_file)
if parsed_data:
logger.info(f"Successfully parsed TSPLIB file: {extracted_file}")
else:
logger.error(f"Failed to parse TSPLIB file: {extracted_file}")
else:
parsed_data = None
logger.error("Failed to extract the file, skipping parsing.")[32m2024-12-21 14:10:06.624[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 34>[0m:[36m37[0m - [1mSuccessfully parsed TSPLIB file: output/tsp_data/extracted/berlin52.tsp[0m— Cell 3: Data Output and Problem Loading (Task a. Question 2) —
# --- Cell 3: Data Output and Problem Loading (Task a. Question 2) ---
def output_parsed_data_to_console(data: Dict[str, Any] | models.Problem) -> None:
"""Outputs parsed data to the console."""
output_str = ""
if isinstance(data, models.Problem):
output_str += f"Problem Name: {data.name}\n"
output_str += f"Problem Type: {data.type}\n"
output_str += f"Dimension: {data.dimension}\n"
output_str += f"Edge Weight Type: {data.edge_weight_type}\n"
if hasattr(data, 'node_coords'):
output_str += "\nNode Coordinates:\n"
for node, coords in data.node_coords.items():
output_str += f"{node}: {coords}\n"
if hasattr(data, 'edge_weights'):
output_str += "\nEdge Weights:\n"
for i, row in enumerate(data.edge_weights):
output_str += f"{i+1}: {row}\n"
elif isinstance(data, dict):
output_str += f"Problem Name: {data.get('NAME', 'N/A')}\n"
output_str += f"Problem Type: {data.get('TYPE', 'N/A')}\n"
output_str += f"Dimension: {data.get('DIMENSION', 'N/A')}\n"
output_str += f"Edge Weight Type: {data.get('EDGE_WEIGHT_TYPE', 'N/A')}\n"
if "NODE_COORD_SECTION" in data:
output_str += "\nNode Coordinates:\n"
for coord_line in data["NODE_COORD_SECTION"]:
output_str += coord_line + "\n"
if "EDGE_WEIGHT_SECTION" in data:
output_str += "\nEdge Weights:\n"
for weight_line in data["EDGE_WEIGHT_SECTION"]:
output_str += weight_line + "\n"
else:
logger.warning("Invalid data format for output.")
return
logger.info(output_str)
def output_parsed_data_to_file(data: Dict[str, Any] | models.Problem, output_file: str) -> None:
"""Outputs parsed data to a JSON file."""
try:
os.makedirs(os.path.join(OUTPUT_FOLDER, "processed"), exist_ok=True)
full_output_path = os.path.join(OUTPUT_FOLDER, "processed", output_file)
if isinstance(data, dict):
with open(full_output_path, 'w') as file:
json.dump(data, file, indent=4)
logger.info(f"Data written to file: {full_output_path}")
elif isinstance(data, models.Problem):
problem_dict = {
"name": data.name,
"type": data.type,
"dimension": data.dimension,
"edge_weight_type": data.edge_weight_type,
"node_coords": data.node_coords if hasattr(data, 'node_coords') else None,
"edge_weights": data.edge_weights if hasattr(data, 'edge_weights') else None
}
with open(full_output_path, 'w') as file:
json.dump(problem_dict, file, indent=4)
logger.info(f"Data written to file: {full_output_path}")
else:
logger.warning("Invalid data format for file output.")
except Exception as e:
logger.error(f"Error writing to file: {e}")
# Load the problem using tsplib95
if extracted_file:
problem = tsplib95.load(extracted_file)
else:
problem = None
# Output parsed data to console and file
if parsed_data:
output_parsed_data_to_console(parsed_data)
output_parsed_data_to_file(parsed_data, "berlin52_parsed.json")
else:
logger.warning("No parsed data to output.")
if problem:
output_parsed_data_to_console(problem)
output_parsed_data_to_file(problem, "berlin52_problem.json")
else:
logger.warning("Could not load problem with tsplib95.")[32m2024-12-21 14:10:12.324[0m | [1mINFO [0m | [36m__main__[0m:[36moutput_parsed_data_to_console[0m:[36m36[0m - [1mProblem Name: berlin52
Problem Type: TSP
Dimension: 52
Edge Weight Type: EUC_2D
[0m
[32m2024-12-21 14:10:12.325[0m | [1mINFO [0m | [36m__main__[0m:[36moutput_parsed_data_to_file[0m:[36m46[0m - [1mData written to file: output/processed/berlin52_parsed.json[0m
[32m2024-12-21 14:10:12.326[0m | [1mINFO [0m | [36m__main__[0m:[36moutput_parsed_data_to_console[0m:[36m36[0m - [1mProblem Name: berlin52
Problem Type: TSP
Dimension: 52
Edge Weight Type: EUC_2D
Node Coordinates:
1: [565.0, 575.0]
2: [25.0, 185.0]
3: [345.0, 750.0]
4: [945.0, 685.0]
5: [845.0, 655.0]
6: [880.0, 660.0]
7: [25.0, 230.0]
8: [525.0, 1000.0]
9: [580.0, 1175.0]
10: [650.0, 1130.0]
11: [1605.0, 620.0]
12: [1220.0, 580.0]
13: [1465.0, 200.0]
14: [1530.0, 5.0]
15: [845.0, 680.0]
16: [725.0, 370.0]
17: [145.0, 665.0]
18: [415.0, 635.0]
19: [510.0, 875.0]
20: [560.0, 365.0]
21: [300.0, 465.0]
22: [520.0, 585.0]
23: [480.0, 415.0]
24: [835.0, 625.0]
25: [975.0, 580.0]
26: [1215.0, 245.0]
27: [1320.0, 315.0]
28: [1250.0, 400.0]
29: [660.0, 180.0]
30: [410.0, 250.0]
31: [420.0, 555.0]
32: [575.0, 665.0]
33: [1150.0, 1160.0]
34: [700.0, 580.0]
35: [685.0, 595.0]
36: [685.0, 610.0]
37: [770.0, 610.0]
38: [795.0, 645.0]
39: [720.0, 635.0]
40: [760.0, 650.0]
41: [475.0, 960.0]
42: [95.0, 260.0]
43: [875.0, 920.0]
44: [700.0, 500.0]
45: [555.0, 815.0]
46: [830.0, 485.0]
47: [1170.0, 65.0]
48: [830.0, 610.0]
49: [605.0, 625.0]
50: [595.0, 360.0]
51: [1340.0, 725.0]
52: [1740.0, 245.0]
Edge Weights:
[0m
[32m2024-12-21 14:10:12.328[0m | [1mINFO [0m | [36m__main__[0m:[36moutput_parsed_data_to_file[0m:[36m58[0m - [1mData written to file: output/processed/berlin52_problem.json[0m— Cell 4: TSP Algorithms (Nearest Neighbor and Simulated Annealing) (Task b. Question 3) —
def calculate_distance(coord1: Tuple[float, float], coord2: Tuple[float, float]) -> float:
"""Calculates the Euclidean distance between two points."""
return math.sqrt((coord1[0] - coord2[0])**2 + (coord1[1] - coord2[1])**2)
def validate_tsplib_data(problem: models.Problem) -> bool:
"""Validates that the TSPLIB problem data is valid for the algorithms."""
if not problem.node_coords:
logger.error("Problem data does not contain node coordinates.")
return False
if len(problem.node_coords) < 3:
logger.error("Problem data contains too few nodes.")
return False
return True
def calculate_tour_distance(problem: models.Problem, tour: List[int],
distance_cache: Dict[Tuple[int, int], float]) -> float:
"""Calculates total tour distance with caching."""
total_distance = 0
for i in range(len(tour) - 1):
city1, city2 = tour[i], tour[i + 1]
if (city1, city2) not in distance_cache:
distance_cache[(city1, city2)] = calculate_distance(problem.node_coords[city1],
problem.node_coords[city2])
total_distance += distance_cache[(city1, city2)]
# Add distance from the last city back to the starting city
city1, city2 = tour[-1], tour[0]
if (city1, city2) not in distance_cache:
distance_cache[(city1, city2)] = calculate_distance(problem.node_coords[city1],
problem.node_coords[city2])
total_distance += distance_cache[(city1, city2)]
return total_distance
def nearest_neighbor_tsp(problem: models.Problem) -> Tuple[List[int], float] | Tuple[None, None]:
"""Implements the Nearest Neighbor heuristic for the TSP."""
if not validate_tsplib_data(problem):
return None, None
distance_cache: Dict[Tuple[int, int], float] = {}
nodes = list(problem.node_coords.keys())
start_node = nodes[0]
unvisited_nodes = set(nodes)
unvisited_nodes.remove(start_node)
tour = [start_node]
total_distance = 0
current_node = start_node
while unvisited_nodes:
nearest_node = None
min_distance = float('inf')
for neighbor in unvisited_nodes:
distance = calculate_distance(problem.node_coords[current_node], problem.node_coords[neighbor])
if distance < min_distance:
min_distance = distance
nearest_node = neighbor
tour.append(nearest_node)
total_distance += min_distance
unvisited_nodes.remove(nearest_node)
current_node = nearest_node
total_distance += calculate_distance(problem.node_coords[current_node], problem.node_coords[start_node])
tour.append(start_node)
return tour, calculate_tour_distance(problem, tour, distance_cache)
def simulated_annealing_tsp(problem: models.Problem, initial_temperature: float = 500,
cooling_rate: float = 0.995, stopping_temperature: float = 0.01,
max_iterations: int = 75000) -> Tuple[List[int], float, List[float]] | Tuple[None, None, None]:
"""Implements the Simulated Annealing algorithm for the TSP.
Returns:
Tuple[List[int], float, List[float]] | Tuple[None, None, None]: The best tour, its total distance, and the list of distances at each iteration for convergence plotting.
"""
if not validate_tsplib_data(problem):
return None, None, None
distance_cache: Dict[Tuple[int, int], float] = {}
initial_tour, _ = nearest_neighbor_tsp(problem)
if not initial_tour:
return None, None, None
current_tour = initial_tour
best_tour = current_tour
current_distance = calculate_tour_distance(problem, current_tour, distance_cache)
best_distance = current_distance
temperature = initial_temperature
iterations = 0
convergence_data = []
while temperature > stopping_temperature and iterations < max_iterations:
new_tour = current_tour[:]
# Swap two random cities
i, j = random.sample(range(1, len(new_tour) - 1), 2)
new_tour[i], new_tour[j] = new_tour[j], new_tour[i]
new_distance = calculate_tour_distance(problem, new_tour, distance_cache)
delta_distance = new_distance - current_distance
# Acceptance probability
if delta_distance < 0 or random.random() < math.exp(-delta_distance / temperature):
current_tour = new_tour
current_distance = new_distance
if current_distance < best_distance:
best_tour = current_tour
best_distance = current_distance
temperature *= cooling_rate
iterations += 1
convergence_data.append(current_distance)
return best_tour, best_distance, convergence_data
def save_tsp_results(results: Dict[str, Any], filename: str) -> None:
"""Saves TSP results to a JSON file."""
try:
os.makedirs(os.path.join(OUTPUT_FOLDER, "results"), exist_ok=True)
full_output_path = os.path.join(OUTPUT_FOLDER, "results", filename)
with open(full_output_path, 'w') as file:
json.dump(results, file, indent=4)
logger.info(f"TSP results written to file: {full_output_path}")
except Exception as e:
logger.error(f"Error writing TSP results to file: {e}")
# Run the algorithms
if problem:
nn_tour, nn_distance = nearest_neighbor_tsp(problem)
if nn_tour:
logger.info(f"Nearest Neighbor Tour: {nn_tour}")
logger.info(f"Nearest Neighbor Distance: {nn_distance}")
save_tsp_results({"algorithm": "Nearest Neighbor", "tour": nn_tour, "distance": nn_distance}, "nearest_neighbor_results.json")
else:
logger.error("Nearest Neighbor algorithm failed.")
sa_tour, sa_distance, convergence_data = simulated_annealing_tsp(problem)
if sa_tour:
logger.info(f"Simulated Annealing Tour: {sa_tour}")
logger.info(f"Simulated Annealing Distance: {sa_distance}")
save_tsp_results({"algorithm": "Simulated Annealing", "tour": sa_tour, "distance": sa_distance}, "simulated_annealing_results.json")
else:
logger.error("Simulated Annealing algorithm failed.")
else:
logger.error("Problem not loaded, skipping algorithm execution.")[32m2024-12-21 14:10:19.240[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 122>[0m:[36m125[0m - [1mNearest Neighbor Tour: [1, 22, 49, 32, 36, 35, 34, 39, 40, 38, 37, 48, 24, 5, 15, 6, 4, 25, 46, 44, 16, 50, 20, 23, 31, 18, 3, 19, 45, 41, 8, 10, 9, 43, 33, 51, 12, 28, 27, 26, 47, 13, 14, 52, 11, 29, 30, 21, 17, 42, 7, 2, 1][0m
[32m2024-12-21 14:10:19.241[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 122>[0m:[36m126[0m - [1mNearest Neighbor Distance: 8980.918279329191[0m
[32m2024-12-21 14:10:19.242[0m | [1mINFO [0m | [36m__main__[0m:[36msave_tsp_results[0m:[36m117[0m - [1mTSP results written to file: output/results/nearest_neighbor_results.json[0m
[32m2024-12-21 14:10:19.283[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 122>[0m:[36m133[0m - [1mSimulated Annealing Tour: [1, 22, 49, 32, 36, 35, 34, 39, 40, 38, 37, 48, 24, 5, 15, 6, 4, 25, 46, 44, 16, 50, 20, 23, 31, 18, 3, 19, 45, 41, 8, 10, 9, 43, 33, 51, 12, 28, 27, 26, 47, 13, 14, 52, 11, 29, 30, 21, 17, 42, 7, 2, 1][0m
[32m2024-12-21 14:10:19.284[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 122>[0m:[36m134[0m - [1mSimulated Annealing Distance: 8980.918279329191[0m
[32m2024-12-21 14:10:19.286[0m | [1mINFO [0m | [36m__main__[0m:[36msave_tsp_results[0m:[36m117[0m - [1mTSP results written to file: output/results/simulated_annealing_results.json[0m— Cell 5: NetworkX TSP Integration (Task b. Question 4) —
def create_graph(problem: models.Problem) -> nx.Graph | None:
"""Creates a NetworkX graph from a TSPLIB problem."""
if not validate_tsplib_data(problem):
return None
G = nx.Graph()
if hasattr(problem, 'node_coords'):
for node, coords in problem.node_coords.items():
G.add_node(node, pos=coords)
for i in G.nodes():
for j in G.nodes():
if i != j:
G.add_edge(i, j, weight=calculate_distance(G.nodes[i]['pos'], G.nodes[j]['pos']))
return G
def solve_tsp_networkx(problem: models.Problem) -> Tuple[List[int], float, List[int], float] | Tuple[None, None, None, None]:
"""Solves the TSP using NetworkX's Nearest Neighbor and Simulated Annealing implementations."""
G = create_graph(problem)
if not G:
logger.error("Could not create graph.")
return None, None, None, None
# Solve with Nearest Neighbor
nn_tour = nx.approximation.traveling_salesman.greedy_tsp(G, source=list(G.nodes)[0])
nn_distance = sum(G[nn_tour[i]][nn_tour[i+1]]['weight'] for i in range(len(nn_tour)-1))
# Solve with Simulated Annealing (using default parameters)
sa_tour = nx.approximation.traveling_salesman.simulated_annealing_tsp(G, "greedy", source=list(G.nodes)[0])
sa_distance = sum(G[sa_tour[i]][sa_tour[i+1]]['weight'] for i in range(len(sa_tour)-1))
return nn_tour, nn_distance, sa_tour, sa_distance
# Solve using NetworkX
if problem:
nx_nn_tour, nx_nn_distance, nx_sa_tour, nx_sa_distance = solve_tsp_networkx(problem)
if nx_nn_tour:
logger.info(f"NetworkX Nearest Neighbor Tour: {nx_nn_tour}")
logger.info(f"NetworkX Nearest Neighbor Distance: {nx_nn_distance}")
save_tsp_results({"algorithm": "NetworkX Nearest Neighbor", "tour": nx_nn_tour, "distance": nx_nn_distance}, "networkx_nn_results.json")
else:
logger.error("NetworkX Nearest Neighbor algorithm failed.")
if nx_sa_tour:
logger.info(f"NetworkX Simulated Annealing Tour: {nx_sa_tour}")
logger.info(f"NetworkX Simulated Annealing Distance: {nx_sa_distance}")
save_tsp_results({"algorithm": "NetworkX Simulated Annealing", "tour": nx_sa_tour, "distance": nx_sa_distance}, "networkx_sa_results.json")
else:
logger.error("NetworkX Simulated Annealing algorithm failed.")
else:
logger.error("Problem not loaded, skipping NetworkX algorithm execution.")[32m2024-12-21 14:10:26.380[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 33>[0m:[36m36[0m - [1mNetworkX Nearest Neighbor Tour: [1, 22, 49, 32, 36, 35, 34, 39, 40, 38, 37, 48, 24, 5, 15, 6, 4, 25, 46, 44, 16, 50, 20, 23, 31, 18, 3, 19, 45, 41, 8, 10, 9, 43, 33, 51, 12, 28, 27, 26, 47, 13, 14, 52, 11, 29, 30, 21, 17, 42, 7, 2, 1][0m
[32m2024-12-21 14:10:26.381[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 33>[0m:[36m37[0m - [1mNetworkX Nearest Neighbor Distance: 8980.918279329191[0m
[32m2024-12-21 14:10:26.383[0m | [1mINFO [0m | [36m__main__[0m:[36msave_tsp_results[0m:[36m117[0m - [1mTSP results written to file: output/results/networkx_nn_results.json[0m
[32m2024-12-21 14:10:26.384[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 33>[0m:[36m43[0m - [1mNetworkX Simulated Annealing Tour: [1, 22, 49, 32, 36, 35, 34, 39, 40, 38, 37, 48, 24, 5, 15, 6, 4, 25, 46, 44, 16, 50, 20, 23, 31, 18, 3, 19, 45, 41, 8, 10, 9, 43, 33, 51, 12, 28, 27, 26, 47, 13, 14, 52, 11, 29, 30, 21, 17, 42, 7, 2, 1][0m
[32m2024-12-21 14:10:26.384[0m | [1mINFO [0m | [36m__main__[0m:[36m<cell line: 33>[0m:[36m44[0m - [1mNetworkX Simulated Annealing Distance: 8980.918279329191[0m
[32m2024-12-21 14:10:26.386[0m | [1mINFO [0m | [36m__main__[0m:[36msave_tsp_results[0m:[36m117[0m - [1mTSP results written to file: output/results/networkx_sa_results.json[0m— Cell 6: TSP Visualization (Task c. Question 5) —
def visualize_tour(problem: models.Problem, tour: List[int], title: str, filename: str, tour_color: str = 'skyblue', node_color: str = 'crimson') -> None:
"""Visualizes a TSP tour on a plot with enhanced aesthetics.
Args:
problem (models.Problem): The TSPLIB problem instance.
tour (List[int]): The list of nodes in the tour.
title (str): The title of the plot.
filename (str): The name of the file to save the plot to.
tour_color (str): The color of the tour path.
node_color (str): The color of the nodes.
"""
if not hasattr(problem, 'node_coords'):
logger.error("Cannot visualize tour: node coordinates are missing.")
return
plt.figure(figsize=(12, 8), dpi=100)
sns.set(style="whitegrid") # Use seaborn style for better aesthetics
# Extract coordinates
coords = np.array([problem.node_coords[node] for node in tour])
# Plot tour path with adjusted line width and style
plt.plot(coords[:, 0], coords[:, 1], color=tour_color, linestyle='-', linewidth=2.5, zorder=1)
# Scatter plot for nodes with adjusted size and color
plt.scatter(coords[:, 0], coords[:, 1], color=node_color, s=100, label='Nodes', zorder=2, edgecolor='black', linewidth=0.5)
# Annotate nodes with a loop to ensure proper order
for i in range(len(tour)):
plt.annotate(str(tour[i]), (coords[i, 0], coords[i, 1]), textcoords="offset points", xytext=(0, 10), ha='center', fontsize=9, color='black')
# Connect the last node to the first to complete the tour
plt.plot([coords[-1, 0], coords[0, 0]], [coords[-1, 1], coords[0, 1]], color=tour_color, linestyle='-', linewidth=2.5, zorder=1)
# Improve plot aesthetics
plt.title(title, fontsize=16, fontweight='bold', pad=20)
plt.xlabel("X Coordinate", fontsize=12, labelpad=10)
plt.ylabel("Y Coordinate", fontsize=12, labelpad=10)
plt.xticks(fontsize=10)
plt.yticks(fontsize=10)
sns.despine(left=True, bottom=True) # Remove spines for a cleaner look
plt.grid(False)
# Add a legend
plt.legend(loc='best', fontsize=10)
# Save the plot
os.makedirs(os.path.join(OUTPUT_FOLDER, "visualizations"), exist_ok=True)
full_output_path = os.path.join(OUTPUT_FOLDER, "visualizations", filename)
plt.savefig(full_output_path, bbox_inches='tight')
logger.info(f"Tour visualization saved to: {full_output_path}")
plt.show()
plt.close()
def visualize_tour_lengths(tour_lengths: Dict[str, float], title: str, filename: str) -> None:
"""Visualizes tour lengths using a bar chart with enhanced aesthetics.
Args:
tour_lengths (Dict[str, float]): A dictionary of tour lengths.
title (str): The title of the plot.
filename (str): The name of the file to save the plot to.
"""
if not tour_lengths:
logger.warning("No tour lengths to visualize.")
return
plt.figure(figsize=(10, 6), dpi=100)
sns.set(style="whitegrid")
# Use a more appealing color palette
palette = sns.color_palette("pastel")
# Create the bar plot
sns.barplot(x=list(tour_lengths.keys()), y=list(tour_lengths.values()), palette=palette, edgecolor="black")
# Improve plot aesthetics
plt.title(title, fontsize=16, fontweight='bold', pad=20)
plt.xlabel("Algorithm", fontsize=12, labelpad=10)
plt.ylabel("Total Distance", fontsize=12, labelpad=10)
plt.xticks(fontsize=10, rotation=45, ha='right')
plt.yticks(fontsize=10)
sns.despine(left=True, bottom=True)
plt.grid(axis='y', linestyle='--', alpha=0.7)
# Add value labels on top of each bar
ax = plt.gca()
for p in ax.patches:
ax.text(p.get_x() + p.get_width()/2., p.get_height(), '{:.2f}'.format(p.get_height()),
fontsize=10, color='black', ha='center', va='bottom')
# Save the plot
os.makedirs(os.path.join(OUTPUT_FOLDER, "visualizations"), exist_ok=True)
full_output_path = os.path.join(OUTPUT_FOLDER, "visualizations", filename)
plt.savefig(full_output_path, bbox_inches='tight')
logger.info(f"Tour lengths visualization saved to: {full_output_path}")
plt.show()
plt.close()
def visualize_convergence(distances: List[float], title: str, filename: str) -> None:
"""Visualizes the convergence of an algorithm with enhanced aesthetics.
Args:
distances (List[float]): A list of distances at each iteration.
title (str): The title of the plot.
filename (str): The name of the file to save the plot to.
"""
if not distances:
logger.warning("No convergence data to visualize.")
return
plt.figure(figsize=(10, 6), dpi=100)
sns.set(style="whitegrid")
# Use a more appealing color and line style
plt.plot(distances, marker='o', linestyle='-', color='dodgerblue', markersize=6, linewidth=2)
# Improve plot aesthetics
plt.title(title, fontsize=16, fontweight='bold', pad=20)
plt.xlabel("Iteration", fontsize=12, labelpad=10)
plt.ylabel("Total Distance", fontsize=12, labelpad=10)
plt.xticks(fontsize=10)
plt.yticks(fontsize=10)
sns.despine(left=True, bottom=True)
plt.grid(True, linestyle='--', alpha=0.7)
# Highlight the best (minimum) distance
min_distance = min(distances)
min_index = distances.index(min_distance)
plt.scatter(min_index, min_distance, color='red', s=100, zorder=3, label=f'Best: {min_distance:.2f}')
plt.legend(loc='best', fontsize=10)
# Save the plot
os.makedirs(os.path.join(OUTPUT_FOLDER, "visualizations"), exist_ok=True)
full_output_path = os.path.join(OUTPUT_FOLDER, "visualizations", filename)
plt.savefig(full_output_path, bbox_inches='tight')
logger.info(f"Convergence visualization saved to: {full_output_path}")
plt.show()
plt.close()
# Visualize results
if problem:
# Nearest Neighbor
if nn_tour:
visualize_tour(problem, nn_tour, "Nearest Neighbor Tour (berlin52)", "nearest_neighbor_tour.png")
# Simulated Annealing
if sa_tour:
visualize_tour(problem, sa_tour, "Simulated Annealing Tour (berlin52)", "simulated_annealing_tour.png")
# Convergence plot
if convergence_data:
visualize_convergence(convergence_data, "Simulated Annealing Convergence (berlin52)", "simulated_annealing_convergence.png")
else:
logger.warning("No convergence data available for Simulated Annealing.")
# NetworkX Nearest Neighbor
if nx_nn_tour:
visualize_tour(problem, nx_nn_tour, "NetworkX Nearest Neighbor Tour (berlin52)", "networkx_nearest_neighbor_tour.png")
# NetworkX Simulated Annealing
if nx_sa_tour:
visualize_tour(problem, nx_sa_tour, "NetworkX Simulated Annealing Tour (berlin52)", "networkx_simulated_annealing_tour.png")
# Tour Lengths Comparison
tour_lengths = {
"Nearest Neighbor": nn_distance,
"Simulated Annealing": sa_distance,
"NetworkX Nearest Neighbor": nx_nn_distance,
"NetworkX Simulated Annealing": nx_sa_distance
}
visualize_tour_lengths(tour_lengths, "Comparison of Tour Lengths (berlin52)", "tour_lengths_comparison.png")
else:
logger.error("Problem not loaded, skipping visualization.")[32m2024-12-21 14:10:32.829[0m | [1mINFO [0m | [36m__main__[0m:[36mvisualize_tour[0m:[36m51[0m - [1mTour visualization saved to: output/visualizations/nearest_neighbor_tour.png[0m
png
[32m2024-12-21 14:10:33.737[0m | [1mINFO [0m | [36m__main__[0m:[36mvisualize_tour[0m:[36m51[0m - [1mTour visualization saved to: output/visualizations/simulated_annealing_tour.png[0m
png
[32m2024-12-21 14:10:34.441[0m | [1mINFO [0m | [36m__main__[0m:[36mvisualize_convergence[0m:[36m136[0m - [1mConvergence visualization saved to: output/visualizations/simulated_annealing_convergence.png[0m
png
[32m2024-12-21 14:10:35.203[0m | [1mINFO [0m | [36m__main__[0m:[36mvisualize_tour[0m:[36m51[0m - [1mTour visualization saved to: output/visualizations/networkx_nearest_neighbor_tour.png[0m
png
[32m2024-12-21 14:10:36.113[0m | [1mINFO [0m | [36m__main__[0m:[36mvisualize_tour[0m:[36m51[0m - [1mTour visualization saved to: output/visualizations/networkx_simulated_annealing_tour.png[0m
png
/usr/local/lib/python3.10/dist-packages/seaborn/_oldcore.py:1765: FutureWarning: unique with argument that is not not a Series, Index, ExtensionArray, or np.ndarray is deprecated and will raise in a future version.
order = pd.unique(vector)
[32m2024-12-21 14:10:36.755[0m | [1mINFO [0m | [36m__main__[0m:[36mvisualize_tour_lengths[0m:[36m95[0m - [1mTour lengths visualization saved to: output/visualizations/tour_lengths_comparison.png[0m
png