# Solving the travelling salesman problem using a genetic algorithm

I've got a simple program written in Golang that takes a map as input and tries to solve the travelling salesman problem by using a genetic algorithm. My Crossover method is a real performance killer due to intense use of make() (allocate memory / will provoke the GC).

What I'd like to do - and yet failed to do is outsource the creation of newGenes. pCrossover and therefore the size of newGenes will be the same over all calls of the function, so I'd like to avoid creating that slice again and again.

I am also interested in any suggestions for improvements of my coding style in Golang and other performance improvements I can take a look at.

Here is an excerpt of the function I am trying to improve:

func (ts *TravellingSalesman) Crossover() {
// Crossover
var nCrossover = int(ts.pCrossover * float64(ts.nGenes))
var newGenes = make([]ga.Gene, nCrossover)
for i:=0; i < nCrossover; i++ {
newGenes[i].Data = make([]int, ts.geneLength)
n := rand.Intn(ts.nGenes)
m := rand.Intn(ts.nGenes)

currentCity := ts.genes[n].Data[0];
newGenes[i].Data[0] = currentCity
for k:=1; k < ts.geneLength; k++ {
nextN := findNextCity(&(ts.genes[n].Data), currentCity)
nextM := findNextCity(&(ts.genes[m].Data), currentCity)

existN := isInArray(&(newGenes[i].Data), nextN)
existM := isInArray(&(newGenes[i].Data), nextM)

// n exists, m doesnt -> take m
if existN && !existM {
newGenes[i].Data[k] = nextM
currentCity = nextM
} else if !existN && existM {
newGenes[i].Data[k] = nextN
currentCity = nextN
} else if existN && existM {
nextRandom := findNextRandomCity(newGenes[i].Data[0:k], &(ts.genes[n].Data))
newGenes[i].Data[k] = nextRandom
currentCity = nextRandom
} else {
// If both didn't exist, take the shorter one
distN := ts.distMatrix.GetDistance(currentCity-1, nextN-1)
distM := ts.distMatrix.GetDistance(currentCity-1, nextM-1)

// Take the shorter route
if distN < distM {
newGenes[i].Data[k] = nextN
currentCity = nextN
} else {
newGenes[i].Data[k] = nextM
currentCity = nextM
}
}
}
}

copy(ts.genes, newGenes)
}


How about using a slice for Gene.Data?

You just allocate

var allData := make([]int, nCrossover * ts.geneLength)


before entering the for loop and assign

newGenes[i].Data = allData[i * ts.geneLength: (i + 1) * ts.geneLength]


You'd cut down on the amount of allocations (and system calls) without changing much else (except findNextCity and isInArray - but they should be written to accept slices instead of array pointers anyway).

And you'd follow the advice given by the languages creators in Effective Go.