This tutorial includes an implementation of a genetic search algorithm in Python, the algorithm is used to find a solution to a traveling salesman problem. Genetic search starts with a population of individuals that has been generated randomly. The fittest individuals in the population creates offsprings from their genes (crossover) and genes of children is mutated, this process repeats during a specified number of generations.
A genetic search algorithm is not guaranteed to give an optimal solution, it can find a satisfactory fast without a need to consider all permutations or combinations. Genetic search can be used to solve real-world problems in which the path to the goal is irrelevant. Genetic search is a local search algorithm that is a little more complicated than hill-climbing and simulated annealing.
An initial population of a certain size can be created at random, the crossover process and the mutation process will improve the population during a specified number of generations. The population is sorted to get the fittest individuals at the top, individuals is paired according to their fittness score and a child is created by taking some genes from one parent and the rest from the other parent (crossover), genes of children can also mutated.
Traveling Salesman Problem (TSP)
A genetic algorithm is used to find a solution to a traveling salesman problem with 13 cities (Traveling Salesman Problem). The total number of permutations is 479001600 ((13-1)!), and the goal is to find the shortest route that visits all cities by starting and ending in the same city. I create an initial population of 100 individuals at random. I sort the population by distance in each generation (100 in total), select parents that create offsprings with crossover, mutate children by swapping cities and I always keep 20 of the best individuals in the population.
# Import libraries
import random
import copy
# This class represent a state
class State:
# Create a new state
def __init__(self, route:[], distance:int=0):
self.route = route
self.distance = distance
# Compare states
def __eq__(self, other):
for i in range(len(self.route)):
if(self.route[i] != other.route[i]):
return False
return True
# Sort states
def __lt__(self, other):
return self.distance < other.distance
# Print a state
def __repr__(self):
return ('({0},{1})\n'.format(self.route, self.distance))
# Create a shallow copy
def copy(self):
return State(self.route, self.distance)
# Create a deep copy
def deepcopy(self):
return State(copy.deepcopy(self.route), copy.deepcopy(self.distance))
# Update distance
def update_distance(self, matrix, home):
# Reset distance
self.distance = 0
# Keep track of departing city
from_index = home
# Loop all cities in the current route
for i in range(len(self.route)):
self.distance += matrix[from_index][self.route[i]]
from_index = self.route[i]
# Add the distance back to home
self.distance += matrix[from_index][home]
# This class represent a city (used when we need to delete cities)
class City:
# Create a new city
def __init__(self, index:int, distance:int):
self.index = index
self.distance = distance
# Sort cities
def __lt__(self, other):
return self.distance < other.distance
# Get best solution by distance
def get_best_solution_by_distance(matrix:[], home:int):
# Variables
route = []
from_index = home
length = len(matrix) - 1
# Loop until route is complete
while len(route) < length:
# Get a matrix row
row = matrix[from_index]
# Create a list with cities
cities = {}
for i in range(len(row)):
cities[i] = City(i, row[i])
# Remove cities that already is assigned to the route
del cities[home]
for i in route:
del cities[i]
# Sort cities
sorted = list(cities.values())
sorted.sort()
# Add the city with the shortest distance
from_index = sorted[0].index
route.append(from_index)
# Create a new state and update the distance
state = State(route)
state.update_distance(matrix, home)
# Return a state
return state
# Create a population
def create_population(matrix:[], home:int, city_indexes:[], size:int):
# Create a gene pool
gene_pool = city_indexes.copy()
# Remove the home city
gene_pool.pop(home)
# Create a population
population = []
for i in range(size):
# Shuffle the gene pool at random
random.shuffle(gene_pool)
# Create a new state and update the distance
state = State(gene_pool[:])
state.update_distance(matrix, home)
# Add an individual to the population
population.append(state)
# Return a population
return population
# Ordered crossover (TSP)
def crossover(matrix:[], home:int, parents:[]):
# Copy parents
parent_1 = parents[0].deepcopy()
parent_2 = parents[1].deepcopy()
# Child gene parts
part_1 = []
part_2 = []
# Select the genes to copy from parents
a = int(random.random() * len(parent_1.route))
b = int(random.random() * len(parent_2.route))
start_gene = min(a, b)
end_gene = max(a, b)
# Get genes from parent 1
for i in range(start_gene, end_gene):
part_1.append(parent_1.route[i])
# Get genes from parent 2
part_2 = [int(x) for x in parent_2.route if x not in part_1]
# Create a child
state = State(part_1 + part_2)
state.update_distance(matrix, home)
# Return a child
return state
# Mutate a solution
def mutate(matrix:[], home:int, state:State, mutation_rate:float=0.01):
# Create a copy of the state
mutated_state = state.deepcopy()
# Loop all the states in a route
for i in range(len(mutated_state.route)):
# Check if we should do a mutation
if(random.random() < mutation_rate):
# Swap two cities
j = int(random.random() * len(state.route))
city_1 = mutated_state.route[i]
city_2 = mutated_state.route[j]
mutated_state.route[i] = city_2
mutated_state.route[j] = city_1
# Update the distance
mutated_state.update_distance(matrix, home)
# Return a mutated state
return mutated_state
# A genetic algorithm
def genetic_algorithm(matrix:[], home:int, population:[], keep:int, mutation_rate:float, generations:int):
# Loop to create new generations
for i in range(generations):
# Sort the population to get the fittest individuals at the beginning
population.sort()
# Generate parents
parents = []
for j in range(1, len(population)):
parents.append((population[j-1], population[j]))
# Generate childrens (breed) with crossover
children = []
for partners in parents:
children.append(crossover(matrix, home, partners))
# Mutate children
for j in range(len(children)):
children[j] = mutate(matrix, home, children[j], mutation_rate)
# Keep the fittest n from the population
population = population[:keep]
# Add children to the population
population.extend(children)
# Sort the population
population.sort()
# Return the best state
return population[0]
# The main entry point for this module
def main():
# Cities to travel
cities = ['New York', 'Los Angeles', 'Chicago', 'Minneapolis', 'Denver', 'Dallas', 'Seattle', 'Boston', 'San Francisco', 'St. Louis', 'Houston', 'Phoenix', 'Salt Lake City']
city_indexes = [0,1,2,3,4,5,6,7,8,9,10,11,12]
# Index of start location
home = 2 # Chicago
# Distances in miles between cities, same indexes (i, j) as in the cities array
matrix = [[0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
[2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
[713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
[1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
[1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
[1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
[2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
[213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
[2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
[875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
[1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
[2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
[1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]]
# Get the best route by distance
state = get_best_solution_by_distance(matrix, home)
print('-- Best solution by distance --')
print(cities[home], end='')
for i in range(0, len(state.route)):
print(' -> ' + cities[state.route[i]], end='')
print(' -> ' + cities[home], end='')
print('\n\nTotal distance: {0} miles'.format(state.distance))
print()
# Run genetic search to find a better solution
population = create_population(matrix, home, city_indexes, 100)
state = genetic_algorithm(matrix, home, population, 20, 0.01, 100)
print('-- Genetic algorithm solution --')
print(cities[home], end='')
for i in range(0, len(state.route)):
print(' -> ' + cities[state.route[i]], end='')
print(' -> ' + cities[home], end='')
print('\n\nTotal distance: {0} miles'.format(state.distance))
print()
# Tell python to run main method
if __name__ == "__main__": main()Output
The best solution is 7293 miles and the genetic algorithm was able to find this solution, it is not guaranteed to give the same result each time. A large population that reproduces creates a larger population with more possibilities for evolution. The algorithm is slower than hill-climbing and simulated annealing.
-- Best solution by distance --
Chicago -> St. Louis -> Minneapolis -> Denver -> Salt Lake City -> Phoenix -> Los Angeles -> San Francisco -> Seattle -> Dallas -> Houston -> New York -> Boston -> Chicago
Total distance: 8131 miles
-- Genetic algorithm solution --
Chicago -> Boston -> New York -> St. Louis -> Dallas -> Houston -> Phoenix -> Los Angeles -> San Francisco -> Seattle -> Salt Lake City -> Denver -> Minneapolis -> Chicago
Total distance: 7293 miles