Genetic Algorithm Travelling Salesman Problem Python Code

In operations research and computer science, the Traveling Salesman Problem (TSP) is a well-known optimization issue. It is one way to put it: To discover the shortest route that visits every city precisely once and returns to the starting city, one must first determine the distances between each pair of cities on the list. Stated differently, the TSP looks for the best tour to help a salesman cover the least amount of travel distance.

The TSP is known to be NP-hard, and it becomes computationally impossible to solve it optimally for a large number of cities. Utilizing Genetic Algorithms (GAs) is one well-liked heuristic method for solving the TSP. A technique for optimization that draws inspiration from nature and resembles natural selection and evolution is known as a genetic algorithm.

Genetic Algorithm for TSP in Python:

Here is an example of Python code that solves the travelling salesman problem using a genetic algorithm:

Code:

import random

cities = {

    'A': (0, 0),

    'B': (1, 3),

    'C': (2, 2),

    'D': (3, 1),

    'E': (4, 4)

}

population_size = 50

generations = 1000

mutation_rate = 0.01

def distance(city1, city2):

    x1, y1 = city1

    x2, y2 = city2

    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def create_individual(cities):

    cities_list = list(cities.keys())

    random.shuffle(cities_list)

    return cities_list

def tour_distance(tour, cities):

    dist = 0

    for i in range(len(tour) - 1):

        dist += distance(cities[tour[i]], cities[tour[i + 1]])

    dist += distance(cities[tour[-1]], cities[tour[0]])

    return dist

population = [create_individual(cities) for _ in range(population_size)]

for generation in range(generations):

    fitness = [1 / tour_distance(tour, cities) for tour in population]

    parents = random.choices(population, weights=fitness, k=population_size)

    new_population = []

    for _ in range(population_size):

        parent1, parent2 = random.sample(parents, 2)

        child = parent1[:]

        for city in parent2:

            if city not in child:

                if random.random() < mutation_rate:

                    swap_idx = random.randint(0, len(child) - 1)

                    child[swap_idx] = city

                else:

                    child.append(city)

        new_population.append(child)

    population = new_population

best_tour = min(population, key=lambda tour: tour_distance(tour, cities))

best_distance = tour_distance(best_tour, cities)

print(f"Best tour: {best_tour}")

print(f"Best distance: {best_distance}")

Output:

Best tour: ['C', 'B', 'A', 'D', 'E']

Best distance: 13.729473667624424

In order to discover a rough solution to the TSP for a limited number of cities, this code defines a genetic algorithm. Depending on your particular issue, you can change the number of cities, population size, number of generations, and mutation rate.

Detailed information on each section of the Python code used to solve the Genetic Algorithm version of the Traveling Salesman Problem (TSP):

1. City Definitions

The cities dictionary is defined in the code, and each city is represented by a distinct key (such as "A," "B," or "C") and the matching (x, y) coordinates. Replace this dictionary with the information about your city.

2. Genetic Algorithm Parameters

• population_size: The number of trips (or persons) in each generation of the population is determined by this parameter.
• Generations: The number of generations that the algorithm will run in total.
• mutation_rate: The likelihood that a mutation may manifest itself when designing a new tour. It regulates the population's degree of genetic diversity.

3. Distance Calculation

By utilizing their coordinates, the distance(city1, city2) function determines the Euclidean distance between two cities. To calculate the distance between cities on a tour, use this function.

4. Initialization of Population

To produce a fresh tour that represents a person in the population, the create_individual(cities) method shuffles the list of cities at random.

5. Tour Distance Calculation

A tour's overall distance is determined by adding the distances between its subsequent cities using the tour_distance(tour, cities) function. It guarantees that the journey ends in the city where it began.

6. Initial Population

The code initializes the population by generating a list of random tours (individuals).

7. Genetic Algorithm Main Loop

The main loop of the genetic algorithm, which executes for a predetermined number of generations, is its central component.

• Fitness Evaluation: Based on its overall length, each tour is assessed for fitness. In this code, the relationship between fitness and tour distance is inverse. Tours that cover less ground have higher fitness ratings.
• Selection: Parents are selected for reproduction by a roulette wheel selection process; fitter parents have a higher probability of getting selected.
• Crossover and Mutation: In order to accomplish crossover, two parents are chosen, a subset of one parent's tour is taken, and the other parent's tour is used to fill in the missing cities. By randomly switching out cities on the tour, mutation makes minor adjustments to the itinerary.
• New Generation: Through crossover and mutation, the old population is replaced by the new one.

8. Final Output

In the final population, the best tour is determined after the predetermined number of generations. The best tour represents the estimated solution to the TSP, and its distance is printed as a result.

Conclusion

In conclusion, applying a genetic algorithm to solve the Traveling Salesman Problem (TSP) is a strong and adaptable strategy. It finds approximations for solutions to a difficult combinatorial optimization problem by combining the concepts of natural selection and evolution. You can modify and adjust a genetic algorithm to meet your unique TSP instance by being aware of its essential elements, which include selection, crossover, mutation, and fitness evaluation. To further enhance the quality of the solution, more sophisticated techniques can be investigated, such as hybridization with other optimization procedures, crossover operators, mutation strategies, and various selection methods. Resolving extra limitations and dynamic elements may be necessary while solving real-world TSP situations. The Genetic Algorithm provides a versatile and efficient framework for addressing the TSP and associated optimization problems.