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.

My source is at Github.

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)

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.