Optimizing the Traveling Salesman Problem with a Genetic Algorithm

Hello, dear reader! Today, we'll delve into the fascinating world of genetic algorithms (GAs) and see how they can be harnessed to solve the Traveling Salesman Problem (TSP), a notorious computational problem. We will achieve this using Python and the geneticalgorithm library.

Introduction:

The Traveling Salesman Problem (TSP) is a classic optimization problem. The objective is simple: given a list of cities and the distances between each pair, what is the shortest possible route that visits each city exactly once and returns to the original city?

Genetic algorithms are search heuristics that mimic the process of natural evolution. They are particularly suited for optimization and search problems, like TSP.

Let's get started!

1. Setting up our Environment:

First, you need to install the geneticalgorithm package:

pip install geneticalgorithm

And you must also have numpy:

pip install numpy

2. Defining the Problem:

We'll begin by specifying the cities and their respective coordinates:

lookUpLocations = {
    0: [4, 7],
    1: [2, 6],
    2: [0, 5],
    3: [1, 3],
    4: [3, 0],
    5: [5, 1],
    6: [7, 2],
    7: [6, 4]
}

3. Computing the Distance:

For our TSP, we need to calculate the distance between two cities. We'll use the Euclidean distance for this:

def get_distance(A, B):
    return np.sqrt((A[0] - B[0])**2 + (A[1] - B[1])**2)

4. Objective Function:

The objective function is crucial in a GA. It defines how well (or poorly) a solution solves the problem at hand:

def f(X):
    total_distance = 0
    for i in range(len(X)-1):
        total_distance += get_distance(
            lookUpLocations[int(X[i])], lookUpLocations[int(X[i+1])])
    # Complete the loop
    total_distance += get_distance(
        lookUpLocations[int(X[-1])], lookUpLocations[int(X[0])])
    return total_distance

Our objective function f(X) computes the total distance for a given tour sequence X.

5. Genetic Algorithm Setup:

Here, we configure the genetic algorithm model for our TSP. The geneticalgorithm library makes this relatively straightforward:

varbound = np.array([[0, len(lookUpLocations) - 1]
                    for _ in range(len(lookUpLocations))])
model = ga(function=f, dimension=len(lookUpLocations),
           variable_type='int', variable_boundaries=varbound)

6. Let's Run our GA:

Now, we initiate the genetic algorithm using:

model.run()

This can take some time, as the algorithm is searching for the optimal or near-optimal solution.

7. Extracting and Displaying the Best Solution:

Lastly, we want to see what the GA has found as the best route:

print(model.output_dict)
best_sequence_indices = model.output_dict['variable']
best_sequence = [int(i) for i in best_sequence_indices]
print("Best sequence of cities (indices):", best_sequence)

Voila! The program will now provide you with the sequence of cities that represents the shortest possible route.

Conclusion:

GAs offer a flexible approach to solving complex optimization problems like the TSP. While they might not always guarantee an absolute optimal solution, they often come very close. This Python tutorial showcased the power of the geneticalgorithm library in addressing real-world problems. Happy coding!

Using Genetic Algorithm to Solve the Traveling Salesman Problem with Python

Table of contents