Travelling Salesman problem using GA, mutation, and crossover

Question

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

        # mutation!
        if p > mutateP:
            indices = random.sample(range(0,nodes), 2)
            mini = min(indices)
            maxi = max(indices)
            iterator = 0
            for j in range(maxi,mini-1,-1):
                tempTable[iterator] = table[i][j]
                iterator += 1

            iterator = 0
            for j in range(mini, maxi+1):
                table[i][j] = tempTable[iterator]
                iterator += 1



        # ordered crossover!
        if p2 > crossP:
            if i < strategies-1:
                iterator = 0
                if (nodes % 2) == 0:
                    mini = random.randint(0, nodes/2)
                    maxi = mini + nodes/2 -1 

                else:
                    mini = random.randint(0, (nodes-1)/2)
                    maxi = mini + (nodes-1)/(2)

                parent1 = copy.deepcopy(table[i])
                parent2 = copy.deepcopy(table[i+1])

                tempTable2 = [0 for i in range(nodes)]
                for j in range(mini, maxi+1):
                    tempTable2[j] = copy.deepcopy(parent1[j])
                for j in range(0, nodes):
                    if tempTable2[j] == 0:
                        for k in range(len(parent2)):
                            if parent2[k] not in tempTable2:
                                # print parent2[k]
                                tempTable2[j] = copy.deepcopy(parent2[k])
                                break
                table[i] = copy.deepcopy(tempTable2)

        if (count == generations - 1):
            print table[i]

        for i in range(strategies):
            indices = random.sample(range(0,strategies), 2)
            mini = min(indices)
            maxi = max(indices)
            distance1 = sumDistance(table[mini])
            distance2 = sumDistance(table[maxi])
            winner = min(distance1, distance2)
            if(winner == distance1):
                table[i] = copy.deepcopy(table[mini])
            else:
                table[i] = copy.deepcopy(table[maxi])    

    return table

def tournament(mini, maxi):
    selections = random.sample(range(1,strategies), 2)

    return findDistance(table[selections[0]], table[selections[1]])


def chooseTwo():

    selections = random.sample(range(1,strategies), 2)

    return findDistance(table[selections[0]], table[selections[1]])


def sumDistance(s1):

    distSum = 0
    for i in range(nodes):
        if (i < nodes-1):
            node1 = s1[i]
            node2 = s1[i+1]
            distSum += math.hypot(nodeTable[0][node2-1] - nodeTable[0][node1-1], nodeTable[1][node2-1] - nodeTable[1][node1-1])
        else:
            node1 = s1[i]
            node2 = s1[0]
            distSum += math.hypot(nodeTable[0][node2-1] - nodeTable[0][node1-1], nodeTable[1][node2-1] - nodeTable[1][node1-1])
    return distSum

def findDistance(s1, s2):
    # print "Summing distance"
    distance1 = sumDistance(s1)
    distance2 = sumDistance(s2)
    winner = min(distance1, distance2)
    if(winner == distance1):
        stratWinner = s1
        temp[1] = distance1
    else:
        stratWinner = s2
        temp[1] = distance2
    temp[0] = stratWinner

    return temp

def drawGraph():

    for i in range(0,nodes):
        graphX[i] = nodeTable[0][bestStrat[0][i]-1]
        graphY[i] = nodeTable[1][bestStrat[0][i]-1]

    plt.scatter(graphX, graphY)
    plt.plot(graphX, graphY)
    plt.show()    

nodeTable = createNodeLocations()

while (count < generations):
    table = generateIteration() 
    temp = chooseTwo()

    if(temp[1] < bestStrat[1] or bestStrat[1] == 0):
        bestStrat = copy.deepcopy(temp)

    if (count == generations - 1):
        print "========================================================="
        print "Best we could find: ", bestStrat


    if(count % 10 == 0):
        print "Foraged", count, "berries"
        print "Best we got so far:", bestStrat
    count+=1

drawGraph()

Answer 1

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<something> 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 identical elements can be done using [elem] * n. It is also a shallow copy of elem, but again, elem should only be immutable in your case.

Printing stuff

Having some visual feedback of computation going on is good, but printing whole bunch of arrays without notice is just debugging. You shouldn't need to debug anymore at this point: remove useless print statements.

Long print statements can be splitted in several parts without introducing any newline by leaving a trailing coma.

Also, you might be interested in the pprint module instead of manually looping through each rows of your table.

More global style note

PEP8 is the de-facto coding style standard and is strongly followed within the community:

• use snake_case for variables and functions names, not camelCase;
• global constants uses UPPERCASE_SNAKE_CASE;
• use 4 spaces for indentation and stay consistent, not like in your "create first generation" block;
• use docstrings to document your functions, not comment above their definition;
• keep your lines length under 80 characters;
• remove unused stuff: numpy and tournament are not used anywhere;
• naming can be improved to be a bit more meaningful.

Possible bugs

• You basically use if random.random() > some_probability to chose if you mutate or crossover at this iteration in generateIteration. Meaning that in your default configuration you never crossover. Shouldn't it be < instead of >?
• You happen to have for i in range(strategies) within for i in range(strategies). Are you double sure that you want to improve every strategies each time you iterate over one strategy to mutate/cross it?

Putting it all together

Your code is thus equivalent to:

import random
import math
from matplotlib import pyplot as plt


def create_nodes(num_nodes, num_rows):
    elements = range(1, num_nodes + 1)
    return [random.sample(elements, num_nodes) for _ in range(num_rows)]


def mutate_once(table, node_table, mutate_probability, cross_probability):
    for next_id, row in enumerate(table, 1):
        nodes = len(row)

        # mutation!
        if random.random() > mutate_probability:
            mini, maxi = sorted(random.sample(range(nodes), 2))
            row[mini:maxi+1] = row[maxi:mini-1:-1]

        # ordered crossover!
        if random.random() > cross_probability:
            try:
                next_row = table[next_id]
            except IndexError:
                pass
            else:
                half_length = nodes//2
                mini = random.randint(0, half_length)
                maxi = mini + half_length - 1 + (nodes % 2)

                crossed = [None] * nodes
                crossed[mini:maxi+1] = row[mini:maxi+1]
                iterator = 0
                for element in next_row:
                    if element in crossed:
                        continue
                    while mini <= iterator <= maxi:
                        iterator += 1
                    crossed[iterator] = element
                    iterator += 1
                row[:] = crossed

        for strategy in table:
            s1, s2 = ramdom.sample(table, 2)
            distance1 = sum_distances(s1, node_table)
            distance2 = sum_distances(s2, node_table)

            if distance1 < distance2:
                strategy[:] = s1
            else:
                strategy[:] = s2


def sample_best(table, node_table):
    t1, t2 = ramdom.sample(table[1:], 2)
    return distance(t1, t2, node_table)


def sum_distances(strategy, node_table):
    dist = 0
    first_row, second_row = node_table

    for idx_next_node, node1 in enumerate(strategy, 1):
        try:
            node2 = strategy[idx_next_node]
        except IndexError:
            node2 = strategy[0]
        dist += math.hypot(
            first_row[node2-1] - first_row[node1-1],
            second_row[node2-1] - second_row[node1-1])

    return dist


def distance(s1, s2, node_table):
    distance1 = sum_distances(s1, node_table)
    distance2 = sum_distances(s2, node_table)

    if distance1 < distance2:
        return s1, distance1
    else:
        return s2, distance2


def draw_graph(node_table, strategy):
    graphX = [node_table[0][index - 1] for index in strategy]
    graphY = [node_table[1][index - 1] for index in strategy]

    plt.scatter(graphX, graphY)
    plt.plot(graphX, graphY)
    plt.show()

def main(nodes=25, strategies=100, generations=100, mutateP=.7, crossP=1.):
    node_table = create_nodes(nodes, 2)

    #create first generation
    table = create_nodes(nodes, strategies)

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

    best_score = None
    for count in range(generations):
        mutate_once(table, node_table, mutateP, crossP)
        strategy, score = sample_best(table, node_table)

        if best_score is None or score < best_score:
            best_strategy = strategy
            best_score = score

        if count % 10 == 0:
            print "Foraged", count, "berries"
            print "Best we got so far:", best_score

    print "========================================================="
    print "Best we could find: ", best_score, "for strategy", best_strategy

    draw_graph(node_table, best_strategy)


if __name__ == '__main__':
    main()