Denna handledning innehåller en implementering av en genetisk sökalgoritm i Python, algoritmen används för att hitta en lösning på ett handelsresandeproblem. Genetisk sökning börjar med en population av individer som har genererats slumpmässigt. De bästa individerna i populationen skapar avkommor från deras gener (crossover) och barnens gener muteras, denna process upprepas under ett visst antal generationer.
En genetisk sökalgoritm är inte garanterad att ge en optimal lösning, den kan hitta en tillfredsställande lösning snabbt utan att behöva testa alla permutationer eller kombinationer. Genetisk sökning kan användas för att lösa problem i verkligheten där vägen till målet är irrelevant. Genetisk sökning är en lokal sökalgoritm som är lite mer komplicerad än bergsklättring och simulerad glödgning.
En initial population av en viss storlek kan skapas slumpmässigt, övergångsprocessen och mutationsprocessen kommer att förbättra populationen under ett visst antal generationer. Befolkningen sorteras för att få de bästa individerna överst, individer paras i enlighet med deras lämplighetspoäng och ett barn skapas genom att några gener tas från en förälder och resten av generna tas från den andra föräldern (crossover), barnens gener kan också muteras.
Handelsresandeproblemet
En genetisk algoritm används för att hitta en lösning på ett handelsresandeproblem med 13 städer (Traveling Salesman Problem). Det totala antalet permutationer är 479001600 ((13-1)!), målet är att hitta den kortaste vägen som besöker alla städer genom att starta och sluta i samma stad. Jag skapar en initial population av 100 individer, dessa individer genereras slumpmässigt. Jag sorterar populationen på avstånd i varje generation (100 totalt), väljer föräldrar som skapar avkommor, muterar barn genom att byta städer och jag behåller alltid 20 av de bästa individerna i populationen.
# 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()Resultat
Den bästa lösningen är 7293 miles och den genetiska algoritmen lyckades hitta denna lösning, det är inte säkert att man får samma resultat varje gång. En stor befolkning som reproducerar sig skapar en större befolkning med fler utvecklingsmöjligheter. Algoritmen är långsammare än bergsklättring och simulerad glödgning.
-- 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