Creating TSP Qubots
This example shows how to create qubots for the Traveling Salesman Problem (TSP) - finding the shortest route visiting all cities exactly once. You’ll learn to build both problem and optimizer qubots, connect them, run locally, and upload to Rastion.
Problem Overview
The TSP asks: given cities and distances, find the shortest tour visiting each city once and returning to start.
Applications: Vehicle routing, manufacturing optimization, DNA sequencing, circuit design.
Creating the TSP Problem Qubot
Step 1: Problem Implementation
Create qubot.py for the TSP problem:
# qubot.py
import numpy as np
from qubots import BaseProblem, ProblemMetadata, ProblemType, ObjectiveType
class TSPProblem(BaseProblem):
def __init__(self, n_cities=10, seed=42):
# Generate random city coordinates
np.random.seed(seed)
self.n_cities = n_cities
self.coordinates = np.random.rand(n_cities, 2) * 100
# Calculate distance matrix
self.distances = self._calculate_distances()
# Set metadata
metadata = ProblemMetadata(
name="TSP Problem",
description=f"Find shortest tour visiting {n_cities} cities",
problem_type=ProblemType.COMBINATORIAL,
objective_type=ObjectiveType.MINIMIZE,
dimension=n_cities,
variable_bounds=[(0, n_cities-1)] * n_cities
)
super().__init__(metadata)
def _calculate_distances(self):
"""Calculate Euclidean distance matrix between cities."""
distances = np.zeros((self.n_cities, self.n_cities))
for i in range(self.n_cities):
for j in range(self.n_cities):
if i != j:
dx = self.coordinates[i][0] - self.coordinates[j][0]
dy = self.coordinates[i][1] - self.coordinates[j][1]
distances[i][j] = np.sqrt(dx*dx + dy*dy)
return distances
def evaluate_solution(self, solution):
"""Calculate total tour distance."""
if not self.is_valid_solution(solution):
return float('inf')
total_distance = 0
for i in range(len(solution)):
from_city = solution[i]
to_city = solution[(i + 1) % len(solution)]
total_distance += self.distances[from_city][to_city]
return total_distance
def is_valid_solution(self, solution):
"""Check if solution is a valid tour."""
if len(solution) != self.n_cities:
return False
if set(solution) != set(range(self.n_cities)):
return False
return True
def get_random_solution(self):
"""Generate random valid tour."""
tour = list(range(self.n_cities))
np.random.shuffle(tour)
return tour
Step 2: Problem Configuration
Create config.json for the TSP problem:
{
"type": "problem",
"class_name": "TSPProblem",
"default_params": {
"n_cities": 10,
"seed": 42
},
"parameters": {
"n_cities": {
"type": "integer",
"default": 10,
"min": 3,
"max": 1000,
"description": "Number of cities to visit"
},
"seed": {
"type": "integer",
"default": 42,
"description": "Random seed for city generation"
}
},
"metadata": {
"name": "TSP Problem",
"description": "Traveling Salesman Problem with random cities",
"domain": "routing",
"tags": ["tsp", "routing", "combinatorial"]
}
}
Creating the TSP Optimizer Qubot
Step 3: Optimizer Implementation
Create qubot.py for a genetic algorithm optimizer:
# qubot.py
import numpy as np
import random
from qubots import BaseOptimizer, OptimizationResult, OptimizerMetadata, OptimizerType
class GeneticTSPOptimizer(BaseOptimizer):
def __init__(self, population_size=50, generations=100, mutation_rate=0.1):
self.population_size = population_size
self.generations = generations
self.mutation_rate = mutation_rate
# Set metadata
metadata = OptimizerMetadata(
name="Genetic TSP Optimizer",
description="Genetic algorithm for TSP with order crossover",
optimizer_type=OptimizerType.METAHEURISTIC,
required_parameters=["population_size", "generations"],
optional_parameters=["mutation_rate"],
parameter_ranges={
"population_size": (10, 500),
"generations": (10, 2000),
"mutation_rate": (0.001, 1.0)
}
)
super().__init__(metadata)
def optimize(self, problem, progress_callback=None, log_callback=None):
"""Solve TSP using genetic algorithm."""
n_cities = problem.n_cities
# Initialize population
population = [problem.get_random_solution() for _ in range(self.population_size)]
best_solution = None
best_value = float('inf')
for generation in range(self.generations):
# Evaluate population
fitness_scores = []
for individual in population:
fitness = problem.evaluate_solution(individual)
fitness_scores.append(fitness)
if fitness < best_value:
best_value = fitness
best_solution = individual.copy()
# Log progress
if log_callback:
log_callback('info', f'Generation {generation}: Best = {best_value:.2f}', 'optimizer')
# Selection and reproduction
new_population = []
for _ in range(self.population_size):
# Tournament selection
parent1 = self._tournament_selection(population, fitness_scores)
parent2 = self._tournament_selection(population, fitness_scores)
# Order crossover
child = self._order_crossover(parent1, parent2)
# Mutation
if random.random() < self.mutation_rate:
child = self._mutate(child)
new_population.append(child)
population = new_population
return OptimizationResult(
best_solution=best_solution,
best_value=best_value,
is_feasible=True,
iterations=self.generations,
termination_reason="max_generations_reached"
)
def _tournament_selection(self, population, fitness_scores, tournament_size=3):
"""Select individual using tournament selection."""
tournament_indices = random.sample(range(len(population)), tournament_size)
best_idx = min(tournament_indices, key=lambda i: fitness_scores[i])
return population[best_idx].copy()
def _order_crossover(self, parent1, parent2):
"""Order crossover for TSP."""
size = len(parent1)
start, end = sorted(random.sample(range(size), 2))
child = [-1] * size
child[start:end] = parent1[start:end]
pointer = end
for city in parent2[end:] + parent2[:end]:
if city not in child:
child[pointer % size] = city
pointer += 1
return child
def _mutate(self, individual):
"""Swap mutation for TSP."""
mutated = individual.copy()
i, j = random.sample(range(len(individual)), 2)
mutated[i], mutated[j] = mutated[j], mutated[i]
return mutated
Step 4: Optimizer Configuration
Create config.json for the genetic algorithm:
{
"type": "optimizer",
"class_name": "GeneticTSPOptimizer",
"default_params": {
"population_size": 50,
"generations": 100,
"mutation_rate": 0.1
},
"parameters": {
"population_size": {
"type": "integer",
"default": 50,
"min": 10,
"max": 500,
"description": "Number of individuals in population"
},
"generations": {
"type": "integer",
"default": 100,
"min": 10,
"max": 2000,
"description": "Number of generations to evolve"
},
"mutation_rate": {
"type": "number",
"default": 0.1,
"min": 0.001,
"max": 1.0,
"description": "Probability of mutation"
}
},
"metadata": {
"name": "Genetic TSP Optimizer",
"description": "Genetic algorithm with order crossover for TSP",
"optimizer_type": "metaheuristic",
"tags": ["genetic", "evolutionary", "tsp"]
}
}
Connecting Problem and Optimizer
Step 5: Local Testing
Test your qubots locally before uploading:
# test_local.py
from qubot import TSPProblem, GeneticTSPOptimizer
# Create problem instance
problem = TSPProblem(n_cities=15, seed=42)
print(f"Created TSP with {problem.n_cities} cities")
# Create optimizer instance
optimizer = GeneticTSPOptimizer(
population_size=30,
generations=50,
mutation_rate=0.15
)
print(f"Created genetic optimizer")
# Solve the problem
print("Solving TSP...")
result = optimizer.optimize(problem)
print(f"Best tour distance: {result.best_value:.2f}")
print(f"Best tour: {result.best_solution}")
print(f"Valid solution: {problem.is_valid_solution(result.best_solution)}")
print(f"Generations: {result.iterations}")
Uploading to Rastion
Step 6: Upload Problem Qubot
Upload your TSP problem to Rastion:
# upload_problem.py
import qubots.rastion as rastion
# Authenticate with Rastion
rastion.authenticate("your_api_token")
# Upload the TSP problem
problem_result = rastion.upload_qubots_model(
model_path="./tsp_problem", # Directory containing qubot.py and config.json
model_name="tsp_problem",
description="TSP problem with configurable city count",
tags=["tsp", "routing", "combinatorial"],
public=True
)
print(f"Problem uploaded: {problem_result['repository_url']}")
Step 7: Upload Optimizer Qubot
Upload your genetic algorithm optimizer:
# upload_optimizer.py
import qubots.rastion as rastion
# Upload the genetic optimizer
optimizer_result = rastion.upload_qubots_model(
model_path="./genetic_tsp_optimizer", # Directory with qubot.py and config.json
model_name="genetic_tsp_optimizer",
description="Genetic algorithm for TSP with order crossover",
tags=["genetic", "evolutionary", "tsp", "metaheuristic"],
public=True
)
print(f"Optimizer uploaded: {optimizer_result['repository_url']}")
Using AutoLoading Functions
Step 8: Load and Use Your Qubots
Once uploaded, use AutoProblem and AutoOptimizer to load your qubots:
from qubots import AutoProblem, AutoOptimizer
# Load your uploaded problem
problem = AutoProblem.from_repo("your_username/tsp_problem", override_params={
"n_cities": 20,
"seed": 123
})
# Load your uploaded optimizer
optimizer = AutoOptimizer.from_repo("your_username/genetic_tsp_optimizer", override_params={
"population_size": 100,
"generations": 200,
"mutation_rate": 0.08
})
# Solve the problem
result = optimizer.optimize(problem)
print(f"Solution found!")
print(f"Tour distance: {result.best_value:.2f}")
print(f"Runtime: {result.runtime_seconds:.3f}s")
print(f"Valid tour: {problem.is_valid_solution(result.best_solution)}")
Step 9: Load Others’ Qubots
Use qubots created by the community:
# Load community TSP problems
berlin52 = AutoProblem.from_repo("benchmarks/tsp_berlin52")
att48 = AutoProblem.from_repo("benchmarks/tsp_att48")
# Load community optimizers
ortools_solver = AutoOptimizer.from_repo("algorithms/ortools_tsp")
sa_optimizer = AutoOptimizer.from_repo("algorithms/simulated_annealing_tsp")
# Compare your optimizer against others
problems = [berlin52, att48]
optimizers = [optimizer, ortools_solver, sa_optimizer]
for prob in problems:
print(f"\nSolving {prob.metadata.name}:")
for opt in optimizers:
result = opt.optimize(prob)
print(f" {opt.metadata.name}: {result.best_value:.2f}")
Summary
You’ve learned how to create TSP qubots from scratch:
- Problem Qubot: Implemented
TSPProblem class with distance calculation and solution evaluation
- Optimizer Qubot: Created
GeneticTSPOptimizer with order crossover and mutation
- Configuration: Set up
config.json files for both qubots
- Local Testing: Connected problem and optimizer to verify functionality
- Upload to Rastion: Made qubots available to the community
- AutoLoading: Used
AutoProblem and AutoOptimizer to load and run qubots
Your qubots are now ready for benchmarking, cloud execution, and sharing with the community!
Next Steps
