# Emilio Espada
# CS-463-02 Algorithms
# Genetic Algorithm implementation of the Travelling Salesperson Problem
import numpy as np
import random
# Cost matrix
cost_matrix = {
'A': {'A': 0, 'B': 16, 'C': 11, 'D': 6},
'B': {'A': 8, 'B': 0, 'C': 13, 'D': 16},
'C': {'A': 4, 'B': 7, 'C': 0, 'D': 9},
'D': {'A': 5, 'B': 12, 'C': 2, 'D': 0}
}
# Helper function to get cost from the matrix
def cost(city1, city2):
return cost_matrix[city1][city2]
# Create a class to handle the TSP
class TravelingSalesperson:
def __init__(self, cities):
self.cities = cities
self.population_size = 100
self.genome_length = len(cities)
self.population = self._initial_population()
self.mutation_rate = 0.01
self.generations = 500
# Initialize population with random routes
def _initial_population(self):
return [random.sample(self.cities, k=self.genome_length) for _ in range(self.population_size)]
# Calculate the total distance of the route
def _route_distance(self, route):
return sum([cost(route[i], route[i+1]) for i in range(len(route) - 1)])
# Selection process for breeding
def _selection(self):
ranked_population = sorted(self.population, key=lambda x: self._route_distance(x))
return ranked_population[:20]
# Create a crossover between two parents
def _crossover(self, parent1, parent2):
child = []
childP1 = []
childP2 = []
geneA = int(random.random() * len(parent1))
geneB = int(random.random() * len(parent1))
startGene = min(geneA, geneB)
endGene = max(geneA, geneB)
for i in range(startGene, endGene):
childP1.append(parent1[i])
childP2 = [item for item in parent2 if item not in childP1]
child = childP1 + childP2
return child
# Mutate the route based on a mutation rate
def _mutate(self, individual):
for swapped in range(len(individual)):
if random.random() < self.mutation_rate:
swapWith = int(random.random() * len(individual))
city1 = individual[swapped]
city2 = individual[swapWith]
individual[swapped] = city2
individual[swapWith] = city1
return individual
# Create a new generation
def _next_generation(self):
selection_results = self._selection()
children = [self._crossover(selection_results[i], selection_results[len(selection_results)-i-1]) for i in range(len(selection_results))]
next_generation = [self._mutate(child) for child in children]
return next_generation
# Run the genetic algorithm
def run(self):
for i in range(self.generations):
self.population = self._next_generation()
return sorted(self.population, key=lambda x: self._route_distance(x))[0]
# Example usage:
cities = ['A', 'B', 'C', 'D'] # Use city labels instead of coordinates
tsp = TravelingSalesperson(cities)
best_route = tsp.run()
print("Best route found:", best_route)
