An Ant Colony Optimization for the Travel Salesman problem.

aco.py

import numpy as np

import utils as u


class ACO:
    """An Ant-Colony Optimization implementation.

    """

    def __init__(self, distance, n_ants=1, n_elitists=1, n_iterations=10, alpha=1, beta=5, decay=0.5):
        """Initialization method.

        Args:
            D (np.array): Distances' matrix.
            n_ants (int): Number of colony ants.
            n_elitists (int): Number of elitist ants.
            n_iterations (int): Number of iterations.
            alpha (float): Pheromone's exponent, where higher values gives it more weight.
            beta (float): Distance's exponent, where higher values gives it more weight.
            decay (float): Rate at which the pheromone decays.

        """

        # Distances' matrix.
        self.D = distance

        # Number of ants
        self.n_ants = n_ants

        # Number of elitist ants
        self.n_elitists = n_elitists

        # Number of iterations
        self.n_iterations = n_iterations

        # Pheromone's exponent
        self.alpha = alpha

        # Distance's exponent
        self.beta = beta

        # Pheromone decay
        self.decay = decay

        # Calculates the pheromones
        self.pheromones = np.ones(self.D.shape) / len(self.D)

    def generate_path_distance(self, paths):
        """Generates the total distance based on current path.

        Args:
            paths (list): A list of paths.

        Returns:
            The total distance in the path.

        """

        # Initialize total distance as 0
        total = 0

        # For each path in current paths
        for path in paths:
            # Adds its distance to total
            total += self.D[path]

        return total

    def generate_path(self, start):
        """Generates a path from the beginning.

        Args:
            start (int): An integer representing the beginning node.

        Returns:
            A list that holds the path.

        """

        # Create an empty list to hold the path
        path = []

        # Create a set of visited paths
        visited = set()

        # Adds the starting path
        visited.add(start)

        # Also gathers the previous path
        previous = start

        # For every possible distance
        for _ in range(len(self.D) - 1):
            # Calculate the current movement
            current = self.choose_path(
                self.pheromones[previous], self.D[previous], visited)

            # Appends new path founded
            path.append((previous, current))

            # Replace previous with current
            previous = current

            # Adds current node to visited set
            visited.add(current)

        # Appends the path back to starting position
        path.append((previous, start))

        return path

    def generate_all_paths(self):
        """Generates all paths.

        Returns:
            A list of paths.

        """

        # Initialize an empty paths list
        paths = []

        # For every ant
        for _ in range(self.n_ants):
            # Generate a new path from the beginning
            path = self.generate_path(0)

            # Appends to the list the path and its distance
            paths.append((path, self.generate_path_distance(path)))

        return paths

    def choose_path(self, pheromone, distance, visited):
        """Choose a new path to visit.

        Args:
            pheromone (np.array): An array of pheromones.
            distance (float): A distance value.
            visited (set): A set of already visited nodes.

        Returns:
            The index of the next movement.

        """

        # Makes a copy of current pheromones
        p = np.copy(pheromone)

        # Apply zero pheromone to visited cities
        p[list(visited)] = 0

        # Calculate track of pheromones
        track = p ** self.alpha * ((1 / distance) ** self.beta)

        # Gathers the track's norm
        track_norm = track / track.sum()

        # Calculate the index based on probability of movement
        index = np.random.choice(range(len(self.D)), 1, p=track_norm)[0]

        return index

    def spread_pheromone(self, paths):
        """Spreads the pheromone across the path.

        Args:
            paths (list): A list of paths to be spreaded.

        """

        # Sorts all paths
        sort_paths = sorted(paths, key=lambda x: x[1])

        # For every path and for every elitist ant
        for path, _ in sort_paths[:self.n_elitists]:
            # For every node in the path
            for p in path:
                # Spreads the pheromones
                self.pheromones[p] += 1 / self.D[p]

    def run(self):
        """Runs the optimization process.

        """

        # Initializes the shortest path as None
        short_path = None

        # Initializes the best path as infinite
        best_path = ('', np.inf)

        # For every iteration
        for i in range(self.n_iterations):
            print(f'Running iteration {i+1}/{self.n_iterations} ...')

            # Generates all possible paths
            paths = self.generate_all_paths()

            # Spreads the pheromone accross the paths
            self.spread_pheromone(paths)

            # Calculates the shortest path
            short_path = min(paths, key=lambda x: x[1])

            # If current cost is better than best cost
            if short_path[1] < best_path[1]:
                # Replace the best cost as current
                best_path = short_path

            print(f'Best path: {best_path[0]} | Cost: {best_path[1]}\n')
            
            # Decay the pheromone
            self.pheromones *= self.decay

        return best_path


if __name__ == "__main__":
    # Declaring an input file
    input_file = 'berlin52.tsp'

    # Actually reading the file
    nodes = u.read_tsp(input_file)

    # Creating distance matrix
    D = u.create_distances(nodes)

    # Instanciating an ACO
    a = ACO(D, n_ants=52, n_elitists=10, n_iterations=2000, alpha=1, beta=2, decay=1)

    # Running the optimization
    path = a.run()

berlin52.tsp

NAME: berlin52
TYPE: TSP
COMMENT: 52 locations in Berlin (Groetschel)
DIMENSION: 52
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 565.0 575.0
2 25.0 185.0
3 345.0 750.0
4 945.0 685.0
5 845.0 655.0
6 880.0 660.0
7 25.0 230.0
8 525.0 1000.0
9 580.0 1175.0
10 650.0 1130.0
11 1605.0 620.0 
12 1220.0 580.0
13 1465.0 200.0
14 1530.0 5.0
15 845.0 680.0
16 725.0 370.0
17 145.0 665.0
18 415.0 635.0
19 510.0 875.0  
20 560.0 365.0
21 300.0 465.0
22 520.0 585.0
23 480.0 415.0
24 835.0 625.0
25 975.0 580.0
26 1215.0 245.0
27 1320.0 315.0
28 1250.0 400.0
29 660.0 180.0
30 410.0 250.0
31 420.0 555.0
32 575.0 665.0
33 1150.0 1160.0
34 700.0 580.0
35 685.0 595.0
36 685.0 610.0
37 770.0 610.0
38 795.0 645.0
39 720.0 635.0
40 760.0 650.0
41 475.0 960.0
42 95.0 260.0
43 875.0 920.0
44 700.0 500.0
45 555.0 815.0
46 830.0 485.0
47 1170.0 65.0
48 830.0 610.0
49 605.0 625.0
50 595.0 360.0
51 1340.0 725.0
52 1740.0 245.0
EOF

utils.py

import numpy as np


def read_tsp(input_file):
    """Reads an input .tsp file.

    Args:
        input_file (str): A string holding the input file's path.

    Returns:
        A set of nodes from the loaded file.

    """

    # Opening input file
    f = open(input_file, 'r')

    # While not finding data
    while f.readline().find('NODE_COORD_SECTION') == -1:
        # Keeps reading
        pass

    # Creating an empty list
    nodes = []

    # While finding data is possible
    while True:
        # Reading every line
        data = f.readline()

        # If reaching end of file
        if data.find('EOF') != -1:
            # Break the process
            break

        # Splits the line
        (_, x, y) = data.split()

        # Convert (x, y) pairs into float
        x = float(x)
        y = float(y)

        # Appends to list
        nodes.append(np.array([x, y]))

    return nodes


def create_distances(nodes):
    """Calculates the euclidean distance between the nodes.

    Args:
        nodes (list): A list of (x, y) nodes' pairs.

    Returns:
        A distance matrix from input nodes.

    """

    # Gathering the amount of nodes
    size = len(nodes)

    # Creating an empty distance matrix
    distances = np.zeros((size, size))

    # For every pair
    for i in range(size):
        # For every pair
        for j in range(size):
            # If pairs are different, calculate the distance
            distances[i][j] = np.linalg.norm(nodes[i] - nodes[j])

            # If pairs are equal
            if i == j:
                # Apply an infinite distance
                distances[i][j] = np.inf

    return distances