Travelling Salesman problem using GA, mutation, and crossover

I created a short python program that can create a list of random unique nodes with a given length and a given number of strategies. The GA runs through a given number of generations, changing a random selection of strategies by using ordered crossover and an inverse mutation between two random indices. Each strategy has a given probability of a mutation and another probability of crossover. The end goal of the program is to find the shortest distance through all the nodes.

I'm new to this kind of programming and would like some guidance to improve efficiency while preserving the same concepts (ordered crossover and inverse mutation) and functionality. It runs slowly as it is pretty much just brute force.

```
import random
import math
import copy
from matplotlib import pyplot as plt
import numpy as np

#number of nodes
nodes = 25
strategies = 100
generations = 100
mutateP = .70
crossP = 1.0
count = 0
bestStrat = [[0 for i in range(nodes)], 0]
temp = [[0 for i in range(nodes)], 0]
graphX = [0 for i in range(nodes)]
graphY = [0 for i in range(nodes)]
tempTable = [0 for i in range(nodes)]
parent1 = [0 for i in range(nodes)]
parent2 = [0 for i in range(nodes)]

#create first generation
table = [ [ 0 for i in range(6) ] for j in range(strategies) ]
for d1 in range(strategies):
table[d1] = random.sample(range(1, nodes+1), nodes)
for i in range(strategies):
print table[i]

print "TOP MEN are looking through:"
print strategies, "strategies in", generations, "generations with", nodes, "nodes in each strategy..."

#create locations for nodes
def createNodeLocations():
print "Creating locations for nodes"
nodeTable = [ [ 0 for i in range(nodes) ] for j in range(2) ]
for i in range(2):
nodeTable[i] = random.sample(range(1, nodes+1), nodes)
print nodeTable[i]
return nodeTable

def generateIteration():

for i in range(strategies):
p = random.random()
p2 = random.random()
mini = 0
maxi = 0

#

Everything is scattered everywhere

Your code and your functions definitions are interleaved, it impairs both readability and understandability. You also make extensive use of global variables without a good reason. For instance graphX and graphY are globals but used only in drawGraph; you should use local variables instead. temp is also a bad thing to put at global scope (on top of being a bad variable name): globals should mainly be immutable constants.

A standard and readable code layout typically looks like:

import XXX
import YYY
for ZZZ import zzz

CST1 = ...
CST2 = ...

def ...:
    ...

def ...:
    ...

def ...:
    ...

if __name__ == '__main__':
    ...

It has 3 advantages:

• least astonishment: people used to python code are used to that kind of layout, it takes them less time to understand what is going on;

• separation of concerns: if you are looking for something specific, you usually know in which section you should search for it;

• improved testing and reusability: the if __name__ == '__main__' part will be executed when you run your script from the command line but not when you import your file into an interactive session, leaving a clean state to start with and test functions.

Use globals sparingly

Most of the global variables could be avoided by making good use of parameters and return values. To me, only nodes, strategies, generations, mutateP and crossP are valid as global variables. But they could be optional parameters with default values as well.

Remember that when passing a mutable object as parameter, you can modify it in place easily. Passing mutable objects as parameters also help better understand the control flow.

Python is a dynamic language

There is absolutely no need to pre-assign arrays filled with default values before assigning the real ones. You might thing that it helps reserve the right amount of memory but its plain wrong. In fact, Python will need to use twice as much memory before discarding (garbage collecting) half of it (the one half containing the default values).

createNodeLocations can thus be written (omitting to declare nodes as a parameter for now):

def createNodeLocations():
    print "Creating locations for nodes"
    elements = range(1, nodes+1)
    return [random.sample(elements, nodes), random.sample(elements, nodes)]

elements is used to avoid building a new range object each time. And for unknown number of items, such as in table creation:

elements = range(1, nodes+1)
table = [list(elements) for _ in range(strategies)]
for elem in table:
    random.shuffle(elem)

Note the use of _ when the iteration variable is not needed (we just want to repeat an operation a certain amount of time) and the preferred list-comprehension syntax to build the list. I could have used table = [random.sample(elements, nodes) for _ in range(strategies)] too, but I wanted to introduce random.shuffle, just in case.

As a side note, you could have a function taking both the number of nodes and the number of wanted rows (2 or strategies) that can be used to create these two tables.

Iterating over elements rather than indices

In Python, the for loop is built to iterate over elements of a collection. In various places, you rather use for i in range(strategies) instead and iterate over the indices (such as table[i]).

You could simplify a whole lot of your logic using direct element access as in for row in table. If you also want the index of the element being iterated to access its predecessor or successor, use enumerate. You can also use the second, optional, parameter of enumerate to easily access the next element, as you seem to do often:

for next_idx, element in enumerate(table, 1):
    try:
        next_element = table[next_idx]
    except IndexError: # in case `element` is the last one
        next_element = something_else()
    # use both element and next_element

A corollary of this is to ramdom.sample the tables directly rather than creating a couple of indices. Again, it will simplify the overall logic since you won't have to keep nodes and strategies everywhere.

Manipulating lists and couples of elements

Python have various builtin ways of copying, inverting, swapping elements of lists and tuples.

-
tuple unpacking can be used to swap elements in one line:

mini, maxi = random.sample(range(0, strategies), 2)
if maxi < mini:
    mini, maxi = maxi, mini

Better, though, would be to use the sorted builtin.

-
lists extended slice syntax (look for "sequences" under the standard type hierarchy) can be used to both reverse some parts and assign a whole chunk at once:

table[i][mini:maxi+1] = table[i][maxi:mini-1:-1]

-
copying a list is done by slicing it from its start to its end:

table[i][:] = table[mini][:]

It's a shallow copy, but since you are only manipulating integers in these lists, it does not matter.

-
Building a list of n i

StackExchange Code Review Q#115230, answer score: 6