A Genetic Algorithm to solve the Traveling Salesman Problem (TSP) + Colab Notebook Link

Task: Implement a Genetic Algorithm to Solve the Traveling Salesman Problem

Visualization of the evolving solution over generations:

Initial distance: 2460.48518188386 
Final distance: 918.168167905173        

Objective: Write a Python program that uses a genetic algorithm to find a near-optimal solution to the TSP. The program should allow for easy modification of parameters such as population size, mutation rate, and number of generations.

Background: The TSP asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”

Genetic Algorithm Concepts:

• Population: A set of possible solutions to the problem.
• Fitness Function: A function that ranks solutions based on how “good” they are.
• Selection: Choosing the best individuals in the current generation for reproduction.
• Crossover: Combining two individuals to produce a new individual.
• Mutation: Introducing small random changes to an individual’s route to create diversity.

Assignment Steps:

1. Initialize Population: Randomly generate a set of possible routes (solutions).
2. Evaluate Fitness: Calculate the total distance of each route and rank them.
3. Selection: Select the top routes to serve as parents for the next generation.
4. Crossover: Create children by combining parts of two parent routes.
5. Mutation: Randomly swap two cities in a route to create variation.
6. Repeat: Perform steps 2-5 for a set number of generations or until a satisfactory solution is found.

Requirements:

• The code must be well-commented and include explanations for each part of the algorithm.
• The implementation should be efficient and run without errors in Google Colab.
• Include a section that explains the genetic algorithm concepts in simple terms.

Deliverables:

• A Python script that implements the genetic algorithm for TSP.
• A report that includes an explanation of the algorithm and the results obtained.

Advanced Challenge (Optional):

• Implement a visualization of the evolving solution over generations using matplotlib.

# Genetic Algorithm to Solve the Traveling Salesman Problem (TSP)

import numpy as np
import random
import matplotlib.pyplot as plt

# Define the TSP using a list of city coordinates
cities = [(random.uniform(-100, 100), random.uniform(-100, 100)) for i in range(30)]

# Helper function to calculate the total distance of a route
def total_distance(route):
    distance = 0
    for i in range(len(route)):
        j = (i + 1) % len(route)
        city_from, city_to = route[i], route[j]
        distance += np.sqrt((city_to[0] - city_from[0])**2 + (city_to[1] - city_from[1])**2)
    return distance

# Create the initial population
def create_population(pop_size, cities):
    return [random.sample(cities, len(cities)) for _ in range(pop_size)]

# Rank the routes based on distance
def rank_routes(population):
    fitness_results = {}
    for i, route in enumerate(population):
        fitness_results[i] = 1 / float(total_distance(route))
    return sorted(fitness_results.items(), key=lambda x: x[1], reverse=True)

# Selection process for the genetic algorithm
def selection(ranked_routes, elite_size):
    selection_results = []
    df = pd.DataFrame(np.array(ranked_routes), columns=["Index", "Fitness"])
    df['cum_sum'] = df.Fitness.cumsum()
    df['cum_perc'] = 100 * df.cum_sum / df.Fitness.sum()
    
    for i in range(elite_size):
        selection_results.append(ranked_routes[i][0])
    for i in range(len(ranked_routes) - elite_size):
        pick = 100 * random.random()
        for i in range(len(ranked_routes)):
            if pick <= df.iat[i,3]:
                selection_results.append(ranked_routes[i][0])
                break
    return selection_results

# Create mating pool
def mating_pool(population, selection_results):
    pool = []
    for i in range(len(selection_results)):
        index = selection_results[i]
        pool.append(population[index])
    return pool

# Breed function for crossover
def breed(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

# Function to run crossover over full mating pool
def breed_population(matingpool, elite_size):
    children = []
    length = len(matingpool) - elite_size
    pool = random.sample(matingpool, len(matingpool))

    for i in range(elite_size):
        children.append(matingpool[i])
    
    for i in range(length):
        child = breed(pool[i], pool[len(matingpool)-i-1])
        children.append(child)
    return children

# Mutation function to add randomness
def mutate(individual, mutation_rate):
    for swapped in range(len(individual)):
        if(random.random() < mutation_rate):
            swapWith = int(random.random() * len(individual))
            
            city1 = individual[swapped]
            city2 = individual[swapWith]
            
            individual[swapped] = city2
            individual[swapWith] = city1
    return individual

# Function to run mutation over entire population
def mutate_population(population, mutation_rate):
    mutated_pop = []
    
    for ind in range(len(population)):
        mutated_ind = mutate(population[ind], mutation_rate)
        mutated_pop.append(mutated_ind)
    return mutated_pop

# Function to run one generation of the genetic algorithm
def next_generation(current_gen, elite_size, mutation_rate):
    ranked_routes = rank_routes(current_gen)
    selection_results = selection(ranked_routes, elite_size)
    matingpool = mating_pool(current_gen, selection_results)
    children = breed_population(matingpool, elite_size)
    next_generation = mutate_population(children, mutation_rate)
    return next_generation

# Function to plot the route
def plot_route(route):
    x = []; y = []
    for city in route:
        x.append(city[0])
        y.append(city[1])
    plt.plot(x, y, 'ro')
    plt.plot(x, y, 'g')
    plt.show()

# Main execution of the genetic algorithm
def genetic_algorithm(cities, pop_size, elite_size, mutation_rate, generations):
    pop = create_population(pop_size, cities)
    print("Initial distance: " + str(1 / rank_routes(pop)[0][1]))
    
    for i in range(generations):
        pop = next_generation(pop, elite_size, mutation_rate)
    
    print("Final distance: " + str(1 / rank_routes(pop)[0][1]))
    best_route_index = rank_routes(pop)[0][0]
    best_route = pop[best_route_index]
    plot_route(best_route)

# Parameters for the genetic algorithm
pop_size = 100
elite_size = 20
mutation_rate = 0.01
generations = 500

# Run the genetic algorithm
genetic_algorithm(cities, pop_size, elite_size, mutation_rate, generations)        

Google Colab Notebook Link: