ga_tsp.py

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

# Define the coordinates of cities
city_names = ["Gliwice", "Cairo", "Rome", "Krakow", "Paris", "Alexandria", "Berlin", "Tokyo", "Hong Kong", "Rio"]
x = [0, 3, 6, 7, 15, 10, 16, 5, 8, 1.5]
y = [1, 2, 1, 4.5, -1, 2.5, 11, 6, 9, 12]
city_coords = dict(zip(city_names, zip(x, y)))

# Distance Calculation
def dist_two_cities(city_1, city_2):
    coord1, coord2 = np.array(city_coords[city_1]), np.array(city_coords[city_2])
    return np.linalg.norm(coord1 - coord2)

# Total distance for a given tour
def total_dist(individual):
    return sum(dist_two_cities(individual[i], individual[i+1]) for i in range(len(individual)-1)) + dist_two_cities(individual[-1], individual[0])

# Generate initial population
def initial_population(cities, population_size):
    return [random.sample(cities, len(cities)) for _ in range(population_size)]

# Fitness function
def fitness_prob(population):
    distances = np.array([total_dist(ind) for ind in population])
    max_distance = max(distances)
    if max_distance == 0:  # Prevent division by zero
        max_distance = 1
    fitness_scores = max_distance - distances  # Higher fitness for shorter distances
    total_fitness = fitness_scores.sum()
    return fitness_scores / total_fitness if total_fitness > 0 else np.ones(len(population)) / len(population)  # Avoid NaN issue

# Selection using Roulette Wheel
def roulette_wheel_selection(population, fitness_probs):
    cumulative_probs = np.cumsum(fitness_probs)
    rand_val = np.random.rand()
    for i, cp in enumerate(cumulative_probs):
        if rand_val < cp:
            return population[i]
    return population[-1]  # Ensure a valid individual is always returned

# Crossover (Ordered Crossover)
def crossover(parent_1, parent_2):
    if parent_1 is None or parent_2 is None:
        raise ValueError("Crossover received a NoneType parent!")

    cut = random.randint(1, len(parent_1) - 1)
    child_1 = parent_1[:cut] + [city for city in parent_2 if city not in parent_1[:cut]]
    child_2 = parent_2[:cut] + [city for city in parent_1 if city not in parent_2[:cut]]
    return child_1, child_2

# Mutation (Swap Mutation)
def mutation(individual, mutation_rate=0.2):
    if random.random() < mutation_rate:
        idx1, idx2 = random.sample(range(len(individual)), 2)
        individual[idx1], individual[idx2] = individual[idx2], individual[idx1]
    return individual

# Genetic Algorithm Execution
def run_ga(cities, population_size=250, generations=50, crossover_rate=0.8, mutation_rate=0.2):
    population = initial_population(cities, population_size)

    best_fitness_history = []
    average_fitness_history = []

    for _ in range(generations):
        fitness_probs = fitness_prob(population)

        # Track best and average fitness
        fitness_values = np.array([total_dist(ind) for ind in population])
        best_fitness = min(fitness_values)
        avg_fitness = np.mean(fitness_values)
        best_fitness_history.append(best_fitness)
        average_fitness_history.append(avg_fitness)

        # Selection
        parents = [roulette_wheel_selection(population, fitness_probs) for _ in range(int(crossover_rate * population_size))]

        # Ensure valid parents
        parents = [p for p in parents if p is not None]

        # Crossover
        offspring = []
        for i in range(0, len(parents), 2):
            if i+1 < len(parents):
                child1, child2 = crossover(parents[i], parents[i+1])
                offspring.extend([child1, child2])

        # Mutation
        offspring = [mutation(child, mutation_rate) for child in offspring]

        # Replacement
        population = sorted(population + offspring, key=total_dist)[:population_size]

    return population, best_fitness_history, average_fitness_history

# Run the GA
best_population, best_fitness_history, average_fitness_history = run_ga(city_names, population_size=250, generations=50, crossover_rate=0.8, mutation_rate=0.2)

# Extract the best route
best_route = min(best_population, key=total_dist)
best_distance = total_dist(best_route)

print(f"Optimal Route: {' → '.join(best_route)}")
print(f"Minimum Distance: {best_distance:.3f}")

# Visualization of TSP Solution
def plot_tsp(route):
    x_shortest = [city_coords[city][0] for city in route] + [city_coords[route[0]][0]]
    y_shortest = [city_coords[city][1] for city in route] + [city_coords[route[0]][1]]

    plt.figure(figsize=(10, 6))
    plt.plot(x_shortest, y_shortest, '--go', linewidth=2.5, label="Best Route")
    plt.scatter(x, y, color='red', zorder=3)

    for i, txt in enumerate(route):
        plt.annotate(f"{i+1}- {txt}", (x_shortest[i], y_shortest[i]), fontsize=10)

    plt.legend()
    plt.title(f"TSP Best Route Using GA - Total Distance: {best_distance:.3f}")
    plt.show()

plot_tsp(best_route)

# Convergence Plot (Black Box Parameters Optimization)
def plot_optimization(best_fitness, avg_fitness, generations=50):
    gen_range = np.arange(generations)

    plt.figure(figsize=(8, 6))
    plt.plot(gen_range, best_fitness, color='black', label='best')
    plt.plot(gen_range, avg_fitness, color='red', label='average')

    # Labels and title
    plt.xlabel('generations', fontsize=14, color='blue')
    plt.ylabel('output', fontsize=14, color='blue')
    plt.title('Black Box Parameters Optimization', fontsize=18, color='blue')

    # Legend
    plt.legend()

    # Show plot
    plt.show()

plot_optimization(best_fitness_history, average_fitness_history, generations=50)

Optimal Route: Paris → Alexandria → Krakow → Rome → Cairo → Gliwice → Tokyo → Rio → Hong Kong → Berlin
Minimum Distance: 61.137