Traveling Salesman Problem genetic algorithm

This is my take on this problem. I don't pre determine the distances, it's not suitable for the application I'll use it for. I'll use it in shool to determine some a mean total distance and how to setup a the poles of a power grid.

from random import sample
from random import random
from random import uniform
from random import shuffle
from math import sqrt
from time import time
from itertools import permutations
import matplotlib.pyplot as plt
import cProfile
import pstats
import io

class NodesLeastDistanceGA:
""" Traveling salesman problem genetic algorithm """

def __init__(self, parent, side, verbose=False):
""" Constructor """
self._parent = parent
self._side = side

self._mutate_rate = 0.07
self._population_size = 60 if len(parent) > 10 else 10
self._new_generation_size = self._population_size*2
self._rounds = 200
self._genlen = len(parent)
self._verbose = verbose
self._cached_distances = {}
self._cached_fitness = {}

def algorithm(self):
"""
Initialize population of lists and sets fittest.

Yields a new population and mutate a small amount of the individuals to avoid getting stuck.

Thorough elitism the most fitest individual is carried through the rounds.
"""

population = self.generate_population()
fitest = min(population, key=self.fitness)

total_time = time()
for r in range(self._rounds):
new_pop = []
while len(new_pop) < self._new_generation_size:
father = self.select(population)
mother = self.select(population)
child = self.crossover(father, mother)
if child not in new_pop:
new_pop += [child]
continue
for i in range(len(new_pop)):
if random() < self._mutate_rate:
new_pop[i] = self.mutate(new_pop[i])

new_fittest = min(population, key=self.fitness)
if self.fitness(fitest) > self.fitness(new_fittest):
fitest = new_fittest
if r % 50 == 0:
print(r, self.fitness(min(population, key=self.fitness)))

population = self.selection(new_pop)
if fitest not in population:
population += [fitest]

self.result(population, fitest, total_time)

def result(self, population, fitest, total_time):
if self._verbose:
for ind in sorted(population, key=self.fitness):
print("Path: {}, Fitness: {:.3f}".format(ind, self.fitness(ind)))

print("Cached-> Fitness:{}, Distances: {}".format(len(self._cached_fitness), len(self._cached_distances)))
print("Execution Time: {:.3f}s".format(time() - total_time))
print("Best path found: {}, fitness: {:.3f}".format(fitest, self.fitness(fitest)))
if self._verbose:
self.plot(fitest)

def selection(self, new_pop):
""" Determines which individuals that survives. Shuffle to destroy symmetry selection over rounds. """

shuffle(new_pop)
pop = []
for _ in range(self._population_size):
survivor = self.select(new_pop)
new_pop.remove(survivor)
pop += [survivor]
return pop

def select(self, pop):
""" Selects a individual that might have a low fitness. """

pop_total_fit = sum(1.0 / self.fitness(p) for p in pop)
limit = uniform(0.0, pop_total_fit)
c = 0
for p in pop:
c += 1 / self._cached_fitness[hash(tuple(p))]
if c > limit:
return p

def fitness(self, child):
"""
Returns the fitness of a individual if it has been calculated.
Else it calculates the distance between each node and sum it up, cache it,
this is the fitness of current individual. In this case a low
fitness is a good fitness.
"""

h = hash(tuple(child))
if h in self._cached_fitness.keys():
return self._cached_fitness[h]

distance = 0
for i in range(len(child)-1):
distance += self.point_distance(child[i], child[i+1])
self._cached_fitness[h] = distance
return distance

@staticmethod
def crossover(father, mother):
"""
Cross two individual thorough a gen by gen approach.
For readability and optimization this function is kept ugly.
"""
child = [None]*len(father)
rate = 0.5
for gen in father:
parent, other_parent = (father, mother) if random() > rate \
else (mother, father)

key = None
for key, value in enumerate(parent):
if value == gen:
break
if not child[key]:
child[key] = gen
continue
for key, value in enumerate(other_parent):
if value == gen:
break
if not child[key]:
child[key] = gen
continue

for key, value in enumerate(child):
if not value:
child[key] = gen
break
return child

@staticmethod
def mutate(child):
""" Swaps place of two gens. """

i1, i2 = sample(range(1, len(child)-1), 2)
child[i1], child[i2] = child[i2], child[i1]
return child

def point_distance(self, p1, p2):
""" Calculates the distance between two points and cache it. """

nodes = hash((p1, p2))
if nodes in self._cached_distances.keys():
return self._cached_distances[nodes]
d = sqrt((p2-p1)**2 + (p2-p1)**2)
self._cached_distances[nodes] = d
return d

def generate_population(self):
""" Creates the initial populations. """

pop = [self._parent[:1]+sample(
self._parent[1:-1], len(self._parent)-2)+self._parent[-1:]
for _ in range(self._population_size)]
for p in pop:
h = hash(tuple(p))
self._cached_fitness[h] = self.fitness(p)
return pop

def plot(self, path):
plt.axis([-1, self._side+1, -1, self._side+1])
for i in range(0, len(path)-1):
plt.plot([path[i], path[i+1]], [path[i], path[i+1]], color="brown", marker="o")
plt.show()

def correct_ans(self, nodes):
""" Very bad bruteforce approach. """

if len(nodes) > 11:
print("Not a good idea.")
raise Exception
start = time()
best = nodes
for path in permutations(nodes[1:-1]):
path = nodes[:1]+list(path)+nodes[-1:]
if self.fitness(best) > self.fitness(path):
best = path
print("Correct ans should be: {}: fitness: {:.3f}, solutions: {}".format(
str(best), self.fitness(best), len(list(permutations(nodes)))))
print("Bruteforce approch: {:.3f}".format(time()-start))
self.plot(best)

def profile(self):
pr = cProfile.Profile()
pr.enable()
self.algorithm()
pr.disable()
s = io.StringIO()
sortby = 'cumulative'
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
ps.print_stats()
stats = s.getvalue().split("\n")
stats = "\n".join([x for x in stats if "GridGA.py" in x])
print(stats)

def main():
nodes = [(13, 2), (1, 12), (12, 5), (19, 6), (2, 10), (15, 15), (5, 11), (17, 9),
(10, 18), (17, 5), #(13, 12), #(1, 17), (2, 6), (7, 16), (19, 2), (3, 7),
#(10, 9), (5, 19), (1, 2), (9, 2)
]
nodes += nodes[:1]
ga = NodesLeastDistanceGA(nodes, 20)
ga.profile()

if __name__ == '__main__':
main()

What optimization and refactoring should I do?

Your code to cache the distances between points unnecessarily uses hash on all its inputs. This is actually how python dicts operate under the hood already. The call hash on the keys and store them thus. This is also where the limitation comes from that dictionary keys have to be hashable.

So you could replace all your self._cached_distances[hash((p1, p2))] = value etc with self._cached_distances[(p1, p2)] = value, because tuples are hashable (while lists are not, because they are mutable).

However, it would be even better to use a memoization decorator like this:

import functools

def memoize(func):
cache = func.cache = {}
@functools.wraps(func)
def wrapper(self, *args):
if args not in cache:
cache[args] = func(self, *args)
return cache[args]
return wrapper

class NodesLeastDistanceGA:
...
@memoize
def point_distance(self, p1, p2):
""" Calculates the distance between two points."""
return sqrt(sum((p2_i-p1_i)**2 for p1_i, p2_i in zip(p1, p2)))

@memoize
def fitness(self, child):
"""
Returns the fitness of a individual by calculating the distance
between each node and summing it up.
In this case a low fitness is a good fitness.
"""
return sum(self.point_distance(gen1, gen2)
for gen1, gen2 in zip(child, child[1:]))

This creates a separate cache for every function you decorate it with. It is slightly modified to allow decorating a class method. The functools.wraps makes sure that the name of the function and its docstring are copied to the wrapper function.

I also changed the function to calculate the distance slightly. This is the general form which can be used to calculate the distance between n-dimensional points.

Theoretically, point_distance could now be a staticmethod, since it does not depend on the class any more (it could even be an independent method). But this would mean having to define two decorators, one with and one without the self argument. Or you make your class hashable itself, then args == (hash(self), p1, p2) and everything will work without the explicit self in the decorator.

For the fitness function I also used the python idiom to iterate over pairs of an element of a list and its successor.

Caching the fitness function in this way means you have to make your child a tuple in the first place. There are two places where you would have to change your logic for this, as far as I can see, mutate and crossover. The first is easy to fix:

@staticmethod
def mutate(child):
""" Swaps place of two gens. """

i1, i2 = sample(range(1, len(child)-1), 2)
_child = list(child)
_child[i1], _child[i2] = _child[i2], _child[i1]
return tuple(_child)

The latter is also easy, just return tuple(child).

• Actually at a certain point I'll run out of ram for very small numbers of nodes, the possible distances increase with n!. So I think I'm better of keeping different caches for this particular implementation, if I can figure out a better method, I certainly use your memorization method. It rocks. Oct 11 '16 at 1:32
• @Simon While I agree that at some point you will run out of memory, I don't I understand the other part if the answer. This keeps two caches, one for each decorated function, just like your code? Btw if memory is a problem, have a look at functools.lru_cache, which will only store a specified number if elements Oct 11 '16 at 6:48
• Combinatorics, it's asking, in how many ways can we arrange n diffrent things, answer being n!. It's like for 0 nodes, there is 1 solution(None), 1 node 1 solutions, 1*2 nodes 2 solutions, 1*2*3 nodes 6 solutions, 1*2*3*4 nodes 24 solutions, 1*2*3*4*5 nodes 120 solutions, ... for 1*2*3*...18*19*20 nodes its 2432902008176640000 solutions. Not important. Very good suggestion. Oct 11 '16 at 8:11
• Yes I'm aware of that. Unfortunately I don't know an answer to that problem. Actually nobody does, as you seem to be aware of. But if I did I would be rich and not posting it as a review on Code review:-) Oct 11 '16 at 8:15
• Haha! Yes, seem weird that you didn't, seen your answers (y). Oct 11 '16 at 8:40

This is a very superficial review, but you have your generic algorithm code mixed in with the problem you're applying it to. In a general sense, this should be avoided whenever possible. Having only loosely related code immediately beside each other is just asking for something bad to happen during a future change.

Whenever I start on a learn a new language, I usually create a GA implementation for practice, and in case I ever actually need it.

It's a fairly easy concept to abstract out:

• The class contains information about the set of possible genes (if a closed set), the max population size, maybe percentage chances of gene crossovers and other chance events (provided you want this to be constant across generations).

• I keep mine simple and only expose a handful of methods. The main method is just a function that automates the processing of an entire generation. It takes the population, runs each genetic sequence through a fitness function (that the caller provides), then chops and repopulates.

By separating the GA code from the use code, you can safely make changes to either without risking breaking some almost unrelated, but coupled code. You also then have the benefit of using your independent GA implementation in any other projects you may need it for without needing to copy and paste select bits from your TSP code.