Genetic Algorithm (GA) for the Traveling Salesman Problem (TSP)¶

In [1]:

from metazoo.bio.evolutionary import GeneticAlgorithm
from metazoo.bio.evolutionary.operators import selection, mutation, crossover
from metazoo.gym.combinatorial import TSP
from metazoo.bio.utils import encoding

from metazoo.bio.evolutionary import GeneticAlgorithm from metazoo.bio.evolutionary.operators import selection, mutation, crossover from metazoo.gym.combinatorial import TSP from metazoo.bio.utils import encoding

In [2]:

TSP.available_problems()

TSP.available_problems()

Out[2]:

['Berlin52', 'Eil76']

In [3]:

tsp = TSP.Berlin52()
tsp.plot(show_optimal=True)

tsp = TSP.Berlin52() tsp.plot(show_optimal=True)

In [4]:

fitness_function = tsp
encoder = encoding.Permutation(permutation_size=fitness_function.dimension)

ga = GeneticAlgorithm(
    fitness_function=fitness_function,
    crossover_function=crossover.PMX,
    mutation_function=mutation.swap,
    selection_function=selection.tournament,
    population_size=500,
    mutation_rate=0.05,
    crossover_rate=0.7,
    encoder=encoder,
    elitism=0.1,
    minimize=True,
)

ga.run(generations=1000)

fitness_function = tsp encoder = encoding.Permutation(permutation_size=fitness_function.dimension) ga = GeneticAlgorithm( fitness_function=fitness_function, crossover_function=crossover.PMX, mutation_function=mutation.swap, selection_function=selection.tournament, population_size=500, mutation_rate=0.05, crossover_rate=0.7, encoder=encoder, elitism=0.1, minimize=True, ) ga.run(generations=1000)

Output()

In [5]:

print(f'Best Individual: {ga.best_individual}')
print(f'Best Fitness: {ga.best_fitness}')
print(f'Optimal Value: {tsp.optimal_value}')
print(f'Difference from Optimal: {ga.best_fitness - tsp.optimal_value}')

print(f'Best Individual: {ga.best_individual}') print(f'Best Fitness: {ga.best_fitness}') print(f'Optimal Value: {tsp.optimal_value}') print(f'Difference from Optimal: {ga.best_fitness - tsp.optimal_value}')

Best Individual: [ 0  2 16 20 41  6  1 29 19 43 33 34 35 48 31 44 18 40  7  8 32  9 42 14
  4 47 23  5 24 27 11  3 37 36 39 38 21 17 30 22 49 15 28 46 25 26 12 13
 51 10 50 45]
Best Fitness: 9812.489666984764
Optimal Value: 7542.0
Difference from Optimal: 2270.489666984764

In [6]:

ga.fitness_plot()

ga.fitness_plot()

In [7]:

tsp.plot(solution=ga.best_individual, show_optimal=True)

tsp.plot(solution=ga.best_individual, show_optimal=True)