@@ -0,0 +1,210 @@
# Python 3
# Genetic algorithm approximation for Traveling Salesman Problem
def tsp_solve (network ):
"""
Solves the TSP using a genetic algorithm.
:param network: list of nodes in the network
:return: path, length of path
"""
# Initialize population with random paths
population = []
for i in range (POPULATION_SIZE ):
population .append (random_path (network ))
# Calculate fitness of each path
for i in range (POPULATION_SIZE ):
population [i ][1 ] = fitness (population [i ][0 ], network )
# Sort paths by fitness
population = sorted (population , key = lambda x : x [1 ])
# Evolve the population
for i in range (GENERATIONS ):
# Select parents for mating
parents = []
for j in range (PARENTS_COUNT ):
parents .append (population [random .randint (0 , POPULATION_SIZE - 1 )])
# Crossover
children = crossover (parents )
# Mutation
for j in range (len (children )):
children [j ] = mutation (children [j ])
# Calculate fitness of each path
for j in range (len (children )):
children [j ][1 ] = fitness (children [j ][0 ], network )
# Sort paths by fitness
children = sorted (children , key = lambda x : x [1 ])
# Replace least fit population with new children
for j in range (POPULATION_SIZE ):
population [j ] = children [j ]
# Return most fit path
return population [0 ]
def random_path (network ):
"""
Generates a random path through the network.
:param network: list of nodes in the network
:return: list of nodes in the path, length of path
"""
# Initialize variables
path = []
length = 0
# Add first node to path
path .append (network [0 ])
# Add remaining nodes to path
for i in range (len (network ) - 1 ):
node = network [random .randint (0 , len (network ) - 1 )]
# Make sure node is not already in path
while node in path :
node = network [random .randint (0 , len (network ) - 1 )]
path .append (node )
length += distance (path [i ], path [i + 1 ])
# Add distance from last node to first node
length += distance (path [len (path ) - 1 ], path [0 ])
# Return path and length
return [path , length ]
def fitness (path , network ):
"""
Calculates the fitness of a path.
:param path: list of nodes in the path
:param network: list of nodes in the network
:return: length of path
"""
# Initialize variables
length = 0
# Add distances between consecutive nodes in path
for i in range (len (path ) - 1 ):
length += distance (path [i ], path [i + 1 ])
# Add distance from last node to first node
length += distance (path [len (path ) - 1 ], path [0 ])
# Return length
return length
def crossover (parents ):
"""
Generates children from a set of parents.
:param parents: list of parent paths
:return: list of children paths
"""
# Initialize variables
children = []
# Generate children
for i in range (len (parents ) // 2 ):
# Select parents
parent1 = parents [random .randint (0 , len (parents ) - 1 )]
parent2 = parents [random .randint (0 , len (parents ) - 1 )]
# Select crossover point
cross_point = random .randint (1 , len (parent1 [0 ]) - 1 )
# Generate children
child1 = parent1 [0 ][:cross_point ] + parent2 [0 ][cross_point :]
child2 = parent2 [0 ][:cross_point ] + parent1 [0 ][cross_point :]
# Add children to list of children
children .append ([child1 , 0 ])
children .append ([child2 , 0 ])
# Return list of children
return children
def mutation (path ):
"""
Mutates a path.
:param path: list of nodes in the path
:return: mutated path
"""
# Initialize variables
new_path = []
# Select two points on the path to swap
point1 = random .randint (0 , len (path ) - 1 )
point2 = random .randint (0 , len (path ) - 1 )
# Make sure points are not the same
while point1 == point2 :
point2 = random .randint (0 , len (path ) - 1 )
# Swap nodes at the two points
new_path = path [:point1 ] + path [point2 :point2 + 1 ] + path [point1 + 1 :point2 ] + path [point1 :point1 + 1 ] + path [point2 + 1 :]
# Return mutated path
return [new_path , 0 ]
def distance (node1 , node2 ):
"""
Calculates the distance between two nodes.
:param node1: first node
:param node2: second node
:return: distance between the nodes
"""
# Return distance between nodes
return math .sqrt ((node1 [0 ] - node2 [0 ]) ** 2 + (node1 [1 ] - node2 [1 ]) ** 2 )
def main ():
"""
Main function.
:return: None
"""
# Initialize variables
network = []
path = []
length = 0
# Generate some random test data
for i in range (100 ):
network .append ([random .randint (0 , 100 ), random .randint (0 , 100 )])
# Solve TSP using a genetic algorithm
path , length = tsp_solve (network )
# Print results
print ("Path:" , path )
print ("Length:" , length )
# Plot the path and points with matplotlib.
import matplotlib .pyplot as plt
x = [p [0 ] for p in path ]
y = [p [1 ] for p in path ]
x .append (path [0 ][0 ])
y .append (path [0 ][1 ])
plt .plot (x , y )
plt .scatter (x , y )
plt .show ()
if __name__ == "__main__" :
main ()
stong revised this gist