functions.py

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


def tsp(N, N_POP, CROSSOVER_PROB, MUTATION_PROB, CITIES,
              ITERATIONS_WO_IMPROVEMENT_LIMIT):
    """
    Solves the Traveling Salesman Problem using a genetic algorithm.

    Parameters:
        N (int): Number of cities.
        N_POP (int): Population size.
        CROSSOVER_PROB (float): Initial probability of crossover during genetic algorithm.
        MUTATION_PROB (float): Initial probability of mutation during genetic algorithm.
        CITIES (numpy.ndarray): 2D array containing coordinates of cities.
        ITERATIONS_WO_IMPROVEMENT_LIMIT (int): Maximum iterations without improvement before termination.

    Returns:
        tuple: A tuple containing:
            - list: Best fitness value found in each generation.
            - list: Median fitness value found in each generation.
            - list: Worst fitness value found in each generation.
            - int: Total number of generations.
            - list: Best solution found.
    """


    def fitness_function(v):
        """
        Calculates the fitness function for a given route.

        Parameters:
            v (list): A list representing the route as a permutation of cities.

        Returns:
            float: The total distance traveled along the route.
        """
        distance = 0
        for i in range(len(v)):
            distance += np.linalg.norm(CITIES[v[i - 1]] - CITIES[v[i]])
        return distance


    def selection(population):
        """
        Performs selection on the population using ranking method.

        Parameters:
            population (list): A list of candidate solutions (routes).

        Returns:
            list: The selected candidates for the next generation.
        """
        return population[:N_POP // 3]


    def crossover(parent_1, parent_2):
        """
        Performs crossover between two parent routes to create a child route.

        Parameters:
            parent_1 (list): The first parent route.
            parent_2 (list): The second parent route.

        Returns:
            list: The child route generated by crossover.
        """
        # Select random positions for crossover
        begin_pos = np.random.randint(N)
        end_pos = np.random.randint(N)
        if begin_pos > end_pos:
            begin_pos, end_pos = end_pos, begin_pos

        # Extract the crossover segment from parent_1
        cells = parent_1[begin_pos:end_pos + 1]

        # Initialize child route
        child = [0] * N

        # Place the crossover segment into the child route
        child[begin_pos:end_pos + 1] = cells[:]

        j = 0
        for i in range(N):
            # Check if the child route is fully filled
            if j == N:
                break
            # Skip the segment already filled with the crossover from parent_1
            if j == begin_pos:
                j += len(cells)

            # If the current city from parent_2 is not in the crossover segment,
            # place it into the child route
            if parent_2[i] not in cells:
                child[j] = parent_2[i]
                j += 1

        return child


    def generation(population, n, cross_prob):
        """
        Generates a new individual for the next generation using crossover.

        Parameters:
            population (list): The current population of individuals.
            n (int): The size of the population.
            cross_prob (float): The probability of crossover.

        Returns:
            list: The new individual generated for the next generation.
        """
        # Select a parent 1 randomly
        p1_index = np.random.randint(n)
        p1 = population[p1_index][0]

        # Select a parent 2 randomly, ensuring it's not the same as parent 1
        while True:
            p2_index = np.random.randint(n)
            if p2_index != p1_index:
                break
        p2 = population[p2_index][0]

        # Perform crossover based on crossover probability
        if cross_prob > np.random.rand():
            return crossover(p1, p2)
        else:
            # If crossover is not performed, repeat the process
            return generation(population, n, cross_prob)


    def mutation(v):
        """
        Performs mutation on an individual.

        Parameters:
            v (list): The individual (route) to be mutated.

        Returns:
            list: The mutated individual.
        """
        # Mutation type 1: Swap mutation
        if np.random.rand() < 0.5:
            # Select two distinct indices randomly for swapping
            i1 = np.random.randint(N)
            while True:
                i2 = np.random.randint(N)
                if i2 != i1:
                    break
            # Swap the cities at the selected indices
            v[i1], v[i2] = v[i2], v[i1]
        else:
            # Mutation type 2: Shift mutation
            # Select parameters for shift mutation
            group_size = np.random.randint(2, N // 2)
            start_index = np.random.randint(0, N - group_size)
            direction = np.random.choice([-1, 1])
            shift_amount = np.random.randint(1, group_size)

            if direction == -1:
                # Shift the group of cities to the left
                temp = v[start_index:start_index + shift_amount]
                v[start_index:start_index + group_size - shift_amount] = v[
                                                                         start_index + shift_amount:start_index + group_size]
                v[start_index + group_size - shift_amount:start_index + group_size] = temp
            else:
                # Shift the group of cities to the right
                temp = v[start_index + group_size - shift_amount:start_index + group_size]
                v[start_index + shift_amount:start_index + group_size] = v[
                                                                         start_index:start_index + group_size - shift_amount]
                v[start_index:start_index + shift_amount] = temp


    def mutation_probability(initial_prob, generation):
        """
        Calculates the mutation probability for a given generation.

        Parameters:
            initial_prob (float): The initial mutation probability.
            generation (int): The current generation.

        Returns:
            float: The mutation probability for the given generation.
        """
        decay_rate = 1e-4
        return max(0, initial_prob - decay_rate * generation)


    def crossover_probability(initial_prob, generation):
        """
        Calculates the crossover probability for a given generation.

        Parameters:
            initial_prob (float): The initial crossover probability.
            generation (int): The current generation.

        Returns:
            float: The crossover probability for the given generation.
        """
        decay_rate = 3e-4
        return max(0, initial_prob - decay_rate * generation)


    # Starting population
    sequence = [i for i in range(N)]
    first_pop = []

    # Generating initial population with random shuffling of cities
    for i in range(N_POP):
        random.shuffle(sequence)
        first_pop.append([sequence[:], fitness_function(sequence)])

    # Sorting the initial population based on fitness
    first_pop = sorted(first_pop, key=lambda x: x[1])
    best = first_pop[0][1]
    best_results = [best]

    # Calculating median fitness of the initial population
    median_results = [(first_pop[N_POP // 2][1] + first_pop[N_POP // 2 - 1][1]) / 2]

    # Storing the fitness of the worst individual in the initial population
    worst_results = [first_pop[-1][1]]
    n_generations = 1

    new_gen = first_pop.copy()
    i_no_imp = 0

    # Iterating until reaching the limit of iterations without improvement
    while i_no_imp < ITERATIONS_WO_IMPROVEMENT_LIMIT:
        new_gen = selection(new_gen)
        curr_cross_prob = crossover_probability(CROSSOVER_PROB, n_generations)
        curr_mut_prob = mutation_probability(MUTATION_PROB, n_generations)

        # Generating new individuals for the next generation using crossover and mutation
        for i in range(N_POP - len(new_gen)):
            b = generation(new_gen, len(new_gen), curr_cross_prob)
            new_gen.append([b, fitness_function(b)])

        # Applying mutation to a subset of the population
        for i in new_gen:
            if random.random() < curr_mut_prob:
                mutation(i[0])

        # Sorting the new generation based on fitness
        new_gen = sorted(new_gen, key=lambda x: x[1])

        # Checking for improvement in the best fitness
        if new_gen[0][1] < best:
            best = new_gen[0][1]
            i_no_imp = 0
        else:
            i_no_imp += 1

        # Updating lists for tracking the evolution of solutions
        best_results.append(best)
        median_results.append((new_gen[N_POP // 2][1] + new_gen[N_POP // 2 - 1][1]) / 2)
        worst_results.append(new_gen[-1][1])
        n_generations += 1

    # Storing the final results
    results = (best_results, median_results, worst_results, n_generations, new_gen[0][0])
    return results


def randomize_cities_on_circle(num_cities, radius):
    """
    Randomly distributes cities on a circle.

    Parameters:
        num_cities (int): Number of cities to distribute.
        radius (float): Radius of the circle.

    Returns:
        numpy.ndarray: 2D array containing coordinates of cities placed on the circle.
    """
    # Generate angles evenly spaced around the circle
    angles = np.linspace(0, 2 * np.pi, num_cities, endpoint=False)
    # Calculate x and y coordinates of cities using trigonometric functions
    x_coordinates = radius * np.cos(angles)
    y_coordinates = radius * np.sin(angles)
    # Stack x and y coordinates to form city locations
    cities = np.column_stack((x_coordinates, y_coordinates))
    return cities


def plot_points_and_road(points, solution, ax):
    """
    Plots points representing cities and the route connecting them.

    Parameters:
        points (numpy.ndarray): 2D array containing coordinates of cities.
        solution (list): List containing the order of cities in the route.
        ax (matplotlib.axes.Axes): Axes object for plotting.

    Returns:
        None
    """
    # Plot cities as blue circles
    ax.plot(points[:, 0], points[:, 1], 'bo')
    ax.set_aspect('equal')
    ax.set_xlabel("X")
    ax.set_ylabel("Y")
    ax.grid()
    # Plot the route connecting cities
    for i in range(-1, len(solution) - 1):
        ax.plot([points[solution[i], 0], points[solution[i + 1], 0]],
                [points[solution[i], 1], points[solution[i + 1], 1]], 'k-')