Genetic Algorithm for Travelling Salesman Problem

Introduction

In my previous blog post “Travelling Salesman Problem”, I have presented the non-approximate brute force and integer linear programming solvers for solving TSP problems. However, since TSP problems are NP-hard, the brute force and integer linear programming solvers are just too slow to solve large TSP problems.

In this blog post, I would like to present a genetic algorithm solver for solving TSP problems approximately. Usually the genetic algorithm will produce solutions that are not too worse than the global optimum.

Genetic Algorithm

General Genetic Algorithm

The general genetic algorithm for solving an optimization problem usually follows the following protocol.

1. Initialize the population randomly.
2. Determine the fitness of the individuals.
3. Until done, repeat:
   • Select parents.
   • Breed children by performing crossover and mutation.
   • Determine the fitness of the children.
   • Select the new population from the parents and the children.

Genetic Algorithm for Travelling Salesman Problem

The solution of the TSP problem could be represented as an ordered list of size $n$ consisting of $1,2,\cdots,n$. Here we will fix the first value of the ordered list to be always $1$. The population could be initialized with random permutations of the ordered list $[1,2,\cdots,n]$. The fitness metric could just be the TSP travelling distance of the solution. The parents would be the individuals which have the highest fitness.

Because the TSP solution does not allow duplicated elements, the crossover operation and the mutation operation are a little bit special. We will perform crossover for ordered list and swap mutation for the TSP solution representations. For example, order 1 crossover was performed specifically in our implementation.

Genetic Algorithm Solver for Travelling Salesman Problem Python Implementation

genetic_algorithm.py

from typing import List, Tuple, Union, Callable, Any
from itertools import permutations
import random
import heapq
from operator import itemgetter
import math
import numpy as np


class GeneticAlgorithmSolver:
    def __init__(self, population_size: int) -> None:

        self.population_size = population_size

    def initialize_population(self):
        # Initialize the population.

        raise NotImplementedError

    def evolve_population(self):
        # Evolve the population.

        raise NotImplementedError

    def get_top_k_individuals(self, k: int) -> List[Any]:
        # Get the top K individuals from the population.

        raise NotImplementedError


class TSPGeneticAlgorithmSolver(GeneticAlgorithmSolver):
    def __init__(self,
                 population_size: int,
                 parent_pool_size: int,
                 child_pool_size: int,
                 distance_matrix: np.ndarray,
                 mutation_rate: float = 1e-2,
                 minimum_cross_over_size: int = 1,
                 maximum_cross_over_size: int = 10) -> None:

        super(TSPGeneticAlgorithmSolver,
              self).__init__(population_size=population_size)

        assert distance_matrix.ndim == 2
        assert distance_matrix.shape[0] == distance_matrix.shape[1]
        assert minimum_cross_over_size <= distance_matrix.shape[0]
        self.parent_pool_size = parent_pool_size
        self.child_pool_size = child_pool_size
        self.distance_matrix = distance_matrix
        self.mutation_rate = mutation_rate
        self.minimum_cross_over_size = minimum_cross_over_size
        self.n = self.distance_matrix.shape[0]
        self.maximum_cross_over_size = min(maximum_cross_over_size, self.n - 1)
        assert self.maximum_cross_over_size >= self.minimum_cross_over_size
        self.population = self.initialize_population()

    def initialize_population(self):

        population = []

        for _ in range(self.population_size):
            perm = list(range(2, self.n + 1))
            random.shuffle(perm)
            perm = [1] + list(perm)
            population.append(perm)

        return population

    def compute_travelling_distance(self, individual: List[int]):

        assert len(individual) == self.n

        travelling_distance = 0
        for i in range(self.n):
            j = (i + 1) % self.n
            travelling_distance += self.distance_matrix[individual[i] -
                                                        1][individual[j] - 1]

        return travelling_distance

    def get_top_k_individual_indices(self, candidates: List[List[int]],
                                     k: int) -> List[Any]:
        # Get the index of top_k individuals.

        travelling_distances = [
            self.compute_travelling_distance(individual=individual)
            for individual in candidates
        ]

        # O(Nlogk)
        # List[Tuple[int, float]]
        top_k_individuals: List[Tuple[int, float]] = heapq.nsmallest(
            n=k, iterable=enumerate(travelling_distances), key=itemgetter(1))

        indices = [individual[0] for individual in top_k_individuals]

        return indices

    def get_top_k_individuals(self, k: int) -> List[Any]:

        indices = self.get_top_k_individual_indices(candidates=self.population,
                                                    k=k)
        individuals = [self.population[index] for index in indices]

        return individuals

    def cross_over(self, parent_1: List[int],
                   parent_2: List[int]) -> List[int]:
        # There are many ordered cross over methods suitable for TSP problems.
        # https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)#Crossover_for_ordered_lists
        # We will be implementing OX1 without considering about the performance (Python is already slow XD).
        # https://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperator.aspx

        # The first value is immutable.
        # The rest of the values are mutable.

        idx_start = random.randint(a=1,
                                   b=self.n - self.maximum_cross_over_size)
        cross_over_size = random.randint(a=self.minimum_cross_over_size,
                                         b=self.maximum_cross_over_size)

        idx_end = idx_start + cross_over_size

        fragment_1 = []
        fragment_1_length = idx_start
        fragment_2 = parent_1[idx_start:idx_end]
        fragment_3 = []
        fragment_3_length = self.n - idx_end

        recombinant_set = set(parent_1[idx_start:idx_end])

        for val in parent_2:
            if val not in recombinant_set:
                if len(fragment_1) < fragment_1_length:
                    fragment_1.append(val)
                else:
                    fragment_3.append(val)

        child = fragment_1 + fragment_2 + fragment_3

        return child

    def mutate(self, individual: List[int]) -> List[int]:
        # Swap mutation.

        for idx_source in range(1, self.n):
            if (random.random() < self.mutation_rate):
                # The first value is immutable.
                # The rest of the values are mutable.
                idx_target = random.randint(a=1, b=self.n - 1)
                val_temp = individual[idx_source]
                individual[idx_source] = individual[idx_target]
                individual[idx_target] = val_temp

        return individual

    def breed(self, parent_1: List[int], parent_2: List[int]) -> List[int]:

        child = self.cross_over(parent_1=parent_1, parent_2=parent_2)
        child = self.mutate(individual=child)

        return child

    def evolve_population(self):

        # Select elite parents.
        top_k_individual_indices = self.get_top_k_individual_indices(
            candidates=self.population, k=self.parent_pool_size)
        random.shuffle(top_k_individual_indices)
        parent_pool = [
            self.population[index] for index in top_k_individual_indices
        ]
        # Breed.
        # Randomly pick parents for breeding.
        # We used uniform sampling for the moment.
        # Prevent parent_1 and parent_2 are the same individual.
        children = []
        for _ in range(self.child_pool_size):
            parents = random.sample(parent_pool, 2)
            child = self.breed(parent_1=parents[0], parent_2=parents[1])
            children.append(child)

        candidates = self.population + children
        # Best individuals survive.
        new_population_indices = self.get_top_k_individual_indices(
            candidates=candidates, k=self.population_size)
        self.population = [
            candidates[index] for index in new_population_indices
        ]

        # print(self.population)


def create_random_symmetric_distance_matrix(n: int) -> np.ndarray:
    def euclidean_distance(node_1: Tuple[float, float],
                           node_2: Tuple[float, float]) -> float:

        return math.sqrt((node_1[0] - node_2[0])**2 +
                         (node_1[1] - node_2[1])**2)

    nodes = [(random.uniform(0, 1), random.uniform(0, 1)) for _ in range(n)]

    distance_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            distance = euclidean_distance(nodes[i], nodes[j])
            distance_matrix[i][j] = distance
            distance_matrix[j][i] = distance

    return distance_matrix

We will inherit the most of the code for TSP baseline solutions from my previous blog post “Travelling Salesman Problem”.

tsp.py

from itertools import permutations
import random
import math
from timeit import default_timer as timer
from datetime import timedelta
from typing import List, Tuple, Union, Callable
import numpy as np
from pulp import LpMaximize, LpMinimize, LpProblem, LpStatus, lpSum, LpVariable, LpBinary, LpInteger, lpDot
from pulp import GLPK

from genetic_algorithm import TSPGeneticAlgorithmSolver


def idx_2d_to_1d(i: int, j: int, width: int) -> int:

    # i, j are in 1-indexed
    # The returned index are 0 indexed.

    return (i - 1) * width + (j - 1)


def assemble_tsp_solution(non_zero_idx: List[Tuple[int, int]]) -> List[int]:

    # The TSP problem ensures that each city is visited exactly once.

    # For example,
    # [(2, 4), (3, 1), (4, 3), (1, 2)] -> [1, 2, 4, 3]
    # Set the starting node to be 1 arbitrarily.

    n = len(non_zero_idx)
    tsp_solution = [1]

    src_tgt_map = {}
    for idx in non_zero_idx:
        src_tgt_map[idx[0]] = idx[1]

    src = 1
    while len(tsp_solution) < n:
        tgt = src_tgt_map[src]
        tsp_solution.append(tgt)
        src = tgt
        if len(tsp_solution) == n:
            assert src_tgt_map[src] == 1

    return tsp_solution


def verify_symmetric_tsp_solution_equality(tsp_solution_1: List[int],
                                           tsp_solution_2: List[int]) -> bool:

    return (tsp_solution_1[:1] + tsp_solution_1[:0:-1]
            ) == tsp_solution_2 or tsp_solution_1 == tsp_solution_2


def tsp_brute_force_solver(
        distance_matrix: np.ndarray) -> Tuple[List[int], float]:

    assert distance_matrix.ndim == 2
    assert distance_matrix.shape[0] == distance_matrix.shape[1]

    n = distance_matrix.shape[0]

    perms = permutations(range(2, n + 1))

    tsp_solution = None
    optimal_cost = float("inf")

    for perm in perms:
        perm = [1] + list(perm)
        cost = 0
        for i in range(n):
            j = (i + 1) % n
            cost += distance_matrix[perm[i] - 1][perm[j] - 1]
        if cost < optimal_cost:
            optimal_cost = cost
            tsp_solution = perm

    return tsp_solution, optimal_cost


def tsp_mtz_integer_linear_programming_solver(
        distance_matrix: np.ndarray) -> Tuple[List[int], float]:

    # TSP MTZ formulation
    # https://en.wikipedia.org/wiki/Travelling_salesman_problem#Miller%E2%80%93Tucker%E2%80%93Zemlin_formulation

    assert distance_matrix.ndim == 2
    assert distance_matrix.shape[0] == distance_matrix.shape[1]

    n = distance_matrix.shape[0]

    distance_list = distance_matrix.flatten().tolist()

    model = LpProblem(name="TSP-Problem", sense=LpMinimize)

    x_variables = []
    for i in range(n):
        for j in range(n):
            x_variables.append(LpVariable(name=f"x_{i+1}_{j+1}", cat=LpBinary))
    # The first value in the u_variables is a dummy value and is never used.
    # Depending on the literature, the lower bound might be 2, and the upper bound might be n. It is actually equivalent.
    u_variables = [1] + [
        LpVariable(name=f"u_{i+2}", lowBound=1, upBound=n - 1, cat=LpInteger)
        for i in range(n - 1)
    ]

    # Add objectives.
    model += lpDot(x_variables, distance_list)

    # Add constraints.
    # sum_{i=1, i \neq j}^{n} x_{ij} = 1 for all j
    for j in range(1, n + 1):
        sum_exp = 0
        for i in range(1, n + 1):
            if i != j:
                idx_id = idx_2d_to_1d(i=i, j=j, width=n)
                sum_exp += x_variables[idx_id]
        model += sum_exp == 1

    # sum_{j=1, j \neq i}^{n} x_{ji} = 1 for all i
    for i in range(1, n + 1):
        sum_exp = 0
        for j in range(1, n + 1):
            if j != i:
                idx_id = idx_2d_to_1d(i=i, j=j, width=n)
                sum_exp += x_variables[idx_id]
        model += sum_exp == 1

    # u_i - u_j + n x_{ij} \neq n - 1 for all 2 <= i, j <= n and i \neq j
    for i in range(2, n + 1):
        for j in range(2, n + 1):
            if i != j:
                idx_id = idx_2d_to_1d(i=j, j=i, width=n)
                model += u_variables[i - 1] - u_variables[
                    j - 1] + n * x_variables[idx_id] <= n - 1

    # print(model)
    status = model.solve(solver=GLPK(msg=False))

    assert status == True, "Linear programming solver did not solve the problem successfully."

    # Collect TSP solution
    non_zero_idx = []
    for variable in model.variables():
        if variable.name.startswith("x_") and variable.value() == 1:
            _, i, j = variable.name.split("_")
            i = int(i)
            j = int(j)
            non_zero_idx.append((i, j))
    assert len(non_zero_idx) == n

    tsp_solution = assemble_tsp_solution(non_zero_idx=non_zero_idx)

    optimal_cost = model.objective.value()

    return tsp_solution, optimal_cost


def tsp_genetic_algorithm_approximate_solver(
        distance_matrix: np.ndarray) -> Tuple[List[int], float]:
    def is_convergent(cost_history: List[float], minimum_history_size: int):

        if len(cost_history) < minimum_history_size:

            return False

        else:
            val = cost_history[0]
            for i in range(1, len(cost_history)):
                if cost_history[i] != val:
                    return False

            return True

    population_size = 500
    parent_pool_size = 100
    child_pool_size = 2000
    mutation_rate = 2.5e-1
    minimum_cross_over_size = 3
    maximum_cross_over_size = 8
    minimum_convergence_iterations = 200

    tsp_ga_solver = TSPGeneticAlgorithmSolver(
        population_size=population_size,
        parent_pool_size=parent_pool_size,
        child_pool_size=child_pool_size,
        distance_matrix=distance_matrix,
        mutation_rate=mutation_rate,
        minimum_cross_over_size=minimum_cross_over_size,
        maximum_cross_over_size=maximum_cross_over_size)

    best_tsp_solution = None
    cost_history = []

    while not is_convergent(
            cost_history=cost_history,
            minimum_history_size=minimum_convergence_iterations):
        tsp_ga_solver.evolve_population()
        best_tsp_solution = tsp_ga_solver.get_top_k_individuals(k=1)[0]
        best_cost = tsp_ga_solver.compute_travelling_distance(
            individual=best_tsp_solution)
        cost_history.append(best_cost)
        cost_history = cost_history[-minimum_convergence_iterations:]
        # print(tsp_ga_solver.population[0:3])
        # print(best_cost)

    tsp_solution = best_tsp_solution
    optimal_cost = best_cost

    return tsp_solution, optimal_cost


def create_random_symmetric_distance_matrix(n: int) -> np.ndarray:
    def euclidean_distance(node_1: Tuple[float, float],
                           node_2: Tuple[float, float]) -> float:

        return math.sqrt((node_1[0] - node_2[0])**2 +
                         (node_1[1] - node_2[1])**2)

    nodes = [(random.uniform(0, 1), random.uniform(0, 1)) for _ in range(n)]

    distance_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            distance = euclidean_distance(nodes[i], nodes[j])
            distance_matrix[i][j] = distance
            distance_matrix[j][i] = distance

    return distance_matrix


def main():

    random_seed = 1
    n = 25

    random.seed(random_seed)

    distance_matrix = create_random_symmetric_distance_matrix(n=n)
    print("-" * 75)
    print("Distance Matrix (Symmetric):")
    print(distance_matrix)

    start = timer()
    tsp_mtz_integer_linear_programming_solution, tsp_mtz_integer_linear_programming_optimal_cost = tsp_mtz_integer_linear_programming_solver(
        distance_matrix=distance_matrix)
    end = timer()
    print("-" * 75)
    print(
        f"Integer Linear Programming Solver Time Elapsed: {timedelta(seconds=end-start)}"
    )
    print("Integer Linear Programming Solver Solution:")
    print(tsp_mtz_integer_linear_programming_solution,
          tsp_mtz_integer_linear_programming_optimal_cost)

    start = timer()
    tsp_genetic_algorithm_approximate_solution, tsp_genetic_algorithm_approximate_optimal_cost = tsp_genetic_algorithm_approximate_solver(
        distance_matrix=distance_matrix)
    end = timer()
    print("-" * 75)
    print(
        f"Genetic Algorithm Approximate Solver Time Elapsed: {timedelta(seconds=end-start)}"
    )
    print("Genetic Algorithm Approximate Solver Solution:")
    print(tsp_genetic_algorithm_approximate_solution,
          tsp_genetic_algorithm_approximate_optimal_cost)


if __name__ == "__main__":

    main()

TSP Problem Solver Execution

Running the following program will print out the solution for the TSP problem in the terminal.

$ python tsp.py 
---------------------------------------------------------------------------
Distance Matrix (Symmetric):
[[0.         0.86432249 0.53733651 0.52055016 0.82008715 0.81480772
  1.05302288 0.33553614 0.13595238 1.12054437 0.32482646 0.93007995
  0.43319431 0.63454406 0.46450414 0.62442036 0.39691122 0.84043923
  0.76103783 0.83403333 0.85827039 0.51491488 0.60272047 0.90787075
  0.71786709]
 [0.86432249 0.         0.33136993 0.54531794 0.70724028 0.19172695
  0.25296739 0.56477053 0.87327923 0.26332327 0.7919103  0.21602389
  0.57210629 0.73549157 0.4051662  0.53124177 0.58211025 0.52842092
  0.31029024 0.13978891 0.64669309 0.64755425 0.45807905 0.24023992
  0.42049009]
 [0.53733651 0.33136993 0.         0.37344856 0.58191477 0.34074068
  0.52092188 0.27661423 0.56294925 0.58335917 0.47889395 0.44893794
  0.2801762  0.51905318 0.07387398 0.34150335 0.2768388  0.47484578
  0.358473   0.30173597 0.64466299 0.39233319 0.34581144 0.44185488
  0.40089476]
 [0.52055016 0.54531794 0.37344856 0.         0.94299417 0.40077955
  0.79436667 0.21687421 0.45088016 0.79823773 0.6732183  0.49875885
  0.56887603 0.84207847 0.36258366 0.69739057 0.54373346 0.84826583
  0.29755558 0.6028888  0.34831013 0.6997195  0.10438371 0.46426901
  0.21416016]
 [0.82008715 0.70724028 0.58191477 0.94299417 0.         0.84497278
  0.6689354  0.77723071 0.92679389 0.80757098 0.51760615 0.91598164
  0.41245505 0.20392021 0.58041242 0.2457591  0.44898452 0.19604201
  0.91214795 0.5706185  1.22441398 0.30554569 0.92746388 0.93004801
  0.97676274]
 [0.81480772 0.19172695 0.34074068 0.40077955 0.84497278 0.
  0.43688552 0.48557671 0.79442587 0.40750209 0.81757024 0.11552917
  0.6192573  0.83388066 0.40284142 0.63560034 0.61756743 0.68355471
  0.12370054 0.31364181 0.45504036 0.72184545 0.30096577 0.10123828
  0.23760758]
 [1.05302288 0.25296739 0.52092188 0.79436667 0.6689354  0.43688552
  0.         0.7861338  1.08360549 0.14203284 0.9131134  0.41832775
  0.68860457 0.76541342 0.59074215 0.57652353 0.71041896 0.4728959
  0.5594388  0.21949736 0.88820689 0.72157499 0.71025829 0.45467865
  0.67162595]
 [0.33553614 0.56477053 0.27661423 0.21687421 0.77723071 0.48557671
  0.7861338  0.         0.31141899 0.82787964 0.45694273 0.59969103
  0.37682657 0.65053264 0.22585234 0.53463345 0.34635403 0.71713566
  0.42551957 0.57068027 0.56439019 0.50645708 0.27629107 0.57514657
  0.38804567]
 [0.13595238 0.87327923 0.56294925 0.45088016 0.92679389 0.79442587
  1.08360549 0.31141899 0.         1.13539391 0.45214932 0.90709458
  0.52329549 0.75063657 0.49572807 0.71441723 0.48576978 0.92579408
  0.72238134 0.86466362 0.76853232 0.62200095 0.54549803 0.88006188
  0.66116232]
 [1.12054437 0.26332327 0.58335917 0.79823773 0.80757098 0.40750209
  0.14203284 0.82787964 1.13539391 0.         1.01404308 0.35263761
  0.78884887 0.89307242 0.65673507 0.69770558 0.80626218 0.61171354
  0.5297264  0.3021144  0.83434669 0.83696257 0.70398742 0.3930795
  0.64368689]
 [0.32482646 0.7919103  0.47889395 0.6732183  0.51760615 0.81757024
  0.9131134  0.45694273 0.45214932 1.01404308 0.         0.92764239
  0.22532462 0.31974102 0.41495489 0.37356734 0.20993143 0.58326073
  0.8122714  0.71195979 1.0182051  0.22950486 0.71644586 0.91877374
  0.81484859]
 [0.93007995 0.21602389 0.44893794 0.49875885 0.91598164 0.11552917
  0.41832775 0.59969103 0.90709458 0.35263761 0.92764239 0.
  0.72370711 0.92398134 0.51419661 0.72189251 0.72462175 0.74234275
  0.2025569  0.35533656 0.48171063 0.81969583 0.39530965 0.04099234
  0.309007  ]
 [0.43319431 0.57210629 0.2801762  0.56887603 0.41245505 0.6192573
  0.68860457 0.37682657 0.52329549 0.78884887 0.22532462 0.72370711
  0.         0.27449659 0.23323704 0.19195919 0.03755032 0.40725609
  0.63534323 0.48683828 0.89094567 0.13098275 0.58178462 0.71984119
  0.66174154]
 [0.63454406 0.73549157 0.51905318 0.84207847 0.20392021 0.83388066
  0.76541342 0.65053264 0.75063657 0.89307242 0.31974102 0.92398134
  0.27449659 0.         0.49223754 0.20424983 0.30430805 0.32873485
  0.87509909 0.61429679 1.15572773 0.14407655 0.84799087 0.92926891
  0.91806714]
 [0.46450414 0.4051662  0.07387398 0.36258366 0.58041242 0.40284142
  0.59074215 0.22585234 0.49572807 0.65673507 0.41495489 0.51419661
  0.23323704 0.49223754 0.         0.33487393 0.22207827 0.49690769
  0.4042646  0.37124633 0.66350347 0.3565034  0.35611163 0.50397177
  0.42921795]
 [0.62442036 0.53124177 0.34150335 0.69739057 0.2457591  0.63560034
  0.57652353 0.53463345 0.71441723 0.69770558 0.37356734 0.72189251
  0.19195919 0.20424983 0.33487393 0.         0.2291837  0.21691756
  0.68660019 0.41167242 0.98616406 0.15151461 0.68501594 0.72889146
  0.74125397]
 [0.39691122 0.58211025 0.2768388  0.54373346 0.44898452 0.61756743
  0.71041896 0.34635403 0.48576978 0.80626218 0.20993143 0.72462175
  0.03755032 0.30430805 0.22207827 0.2291837  0.         0.44382964
  0.62633038 0.50425558 0.87119618 0.16027593 0.56214531 0.71863844
  0.64655056]
 [0.84043923 0.52842092 0.47484578 0.84826583 0.19604201 0.68355471
  0.4728959  0.71713566 0.92579408 0.61171354 0.58326073 0.74234275
  0.40725609 0.32873485 0.49690769 0.21691756 0.44382964 0.
  0.76568139 0.38897049 1.09402193 0.35408084 0.81366838 0.76069839
  0.84429645]
 [0.76103783 0.31029024 0.358473   0.29755558 0.91214795 0.12370054
  0.5594388  0.42551957 0.72238134 0.5297264  0.8122714  0.2025569
  0.63534323 0.87509909 0.4042646  0.68660019 0.62633038 0.76568139
  0.         0.41885744 0.3407665  0.75080614 0.1934461  0.16680234
  0.1141008 ]
 [0.83403333 0.13978891 0.30173597 0.6028888  0.5706185  0.31364181
  0.21949736 0.57068027 0.86466362 0.3021144  0.71195979 0.35533656
  0.48683828 0.61429679 0.37124633 0.41167242 0.50425558 0.38897049
  0.41885744 0.         0.75960824 0.54167291 0.53122116 0.37724367
  0.51950889]
 [0.85827039 0.64669309 0.64466299 0.34831013 1.22441398 0.45504036
  0.88820689 0.56439019 0.76853232 0.83434669 1.0182051  0.48171063
  0.89094567 1.15572773 0.66350347 0.98616406 0.87119618 1.09402193
  0.3407665  0.75960824 0.         1.01871179 0.30919405 0.44141928
  0.24974478]
 [0.51491488 0.64755425 0.39233319 0.6997195  0.30554569 0.72184545
  0.72157499 0.50645708 0.62200095 0.83696257 0.22950486 0.81969583
  0.13098275 0.14407655 0.3565034  0.15151461 0.16027593 0.35408084
  0.75080614 0.54167291 1.01871179 0.         0.70991081 0.82043726
  0.78540973]
 [0.60272047 0.45807905 0.34581144 0.10438371 0.92746388 0.30096577
  0.71025829 0.27629107 0.54549803 0.70398742 0.71644586 0.39530965
  0.58178462 0.84799087 0.35611163 0.68501594 0.56214531 0.81366838
  0.1934461  0.53122116 0.30919405 0.70991081 0.         0.36024459
  0.11599596]
 [0.90787075 0.24023992 0.44185488 0.46426901 0.93004801 0.10123828
  0.45467865 0.57514657 0.88006188 0.3930795  0.91877374 0.04099234
  0.71984119 0.92926891 0.50397177 0.72889146 0.71863844 0.76069839
  0.16680234 0.37724367 0.44141928 0.82043726 0.36024459 0.
  0.27004542]
 [0.71786709 0.42049009 0.40089476 0.21416016 0.97676274 0.23760758
  0.67162595 0.38804567 0.66116232 0.64368689 0.81484859 0.309007
  0.66174154 0.91806714 0.42921795 0.74125397 0.64655056 0.84429645
  0.1141008  0.51950889 0.24974478 0.78540973 0.11599596 0.27004542
  0.        ]]
---------------------------------------------------------------------------
Integer Linear Programming Solver Time Elapsed: 0:05:05.087696
Integer Linear Programming Solver Solution:
[1, 9, 8, 4, 23, 21, 25, 19, 6, 24, 12, 2, 10, 7, 20, 3, 15, 17, 13, 16, 18, 5, 14, 22, 11] 4.69096282119964
---------------------------------------------------------------------------
Genetic Algorithm Approximate Solver Time Elapsed: 0:00:56.850967
Genetic Algorithm Approximate Solver Solution:
[1, 9, 8, 4, 23, 21, 25, 19, 6, 24, 12, 2, 10, 7, 20, 3, 15, 17, 13, 16, 18, 5, 14, 22, 11] 4.690962821199639

We happen to get the global optimum solution for the TSP problem. However, in most of the cases, we can’t get the global optimum.

Genetic Algorithm Caveats

There are a lot of parameters used in the genetic algorithm, which will affect the convergence and the best fitness could possibly be achieved in certain iterations. When the algorithm almost converges, all the individuals would be very similar in the population, preventing the further exploration for the global optimum solution. There are some tricks to improve this situation, such as decreasing the parent pool size from generation to generation and increasing crossover size and mutation rate, which we did not investigate in our implementation of the genetic algorithm for TSP problems.

Reference

• Travelling Salesman Problem