Решения задачи коммивояжера с помощью генетического алгоритма


У меня есть простая программа, написанная на Golang, который принимает карту в качестве входных данных и пытается решить задачу коммивояжера с помощью генетического алгоритма. Мой метод кроссовера-это настоящий спектакль убийца из-за интенсивного использования сделать() (выделить память / спровоцирует ГК).

Что я хочу сделать - и все-таки не удалось сделать-аутсорсинг создание newGenes. pCrossover и, следовательно, размер newGenes будет неизменным на все вызовы функции, поэтому я бы хотел, чтобы избежать того, что кусочек снова и снова.

Также Меня интересуют любые предложения по улучшению моего стиля кодирования в Golang и другие улучшения производительности можно посмотреть на.

Мой источник на GitHub.

Вот выдержка из функции я пытаюсь улучшить:

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)
}


985
6
задан 1 декабря 2011 в 11:12 Источник Поделиться
Комментарии
1 ответ

Как насчет того, используя кусочек для Гена.Данные?

Вы просто выделять

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

перед входом в цикл и присвоить

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

Вы бы сократить сумму отчислений (и системных вызовов), не меняя многого другого (кроме findNextCity и isInArray - но они должны быть написаны, чтобы принять кусочки вместо массива указателей в любом случае).

И вы бы следовать советам дано языках создатели эффективного идти.

2
ответ дан 17 августа 2012 в 02:08 Источник Поделиться