Используя поиск по табу, как выбираются соседи для коммивояжера? - PullRequest
Новая
       23

Используя поиск по табу, как выбираются соседи для коммивояжера?

0 голосов
/ 27 марта 2019

Когда я пытаюсь понять, как поиск табу может быть применен к коммивояжеру, я с трудом понимаю, как создается окрестность. Если мы посмотрим на этот псевдокод из википедии: 

sNeighborhood ← getNeighbors(bestCandidate)
for (sCandidate in sNeighborhood)
    if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
        bestCandidate ← sCandidate
    end
end

Мой лучший кандидат начинается с пути, сгенерированного из алгоритма ближайших соседей, каковы соседи по этому пути?

Скажите, что мой путь A, B, D, C, A является ли соседство каждой возможностью для каждого индекса? например [B, D, C], [A, C, D] и т. Д.?

А затем мы исключаем соседей, которые есть в списке табу для каждого индекса?

Если нет, то каково мое соседство?

Также в псевдокоде в список табу добавляются только новые лучшие кандидаты, так как же нам выбрать другой район в следующий раз? 

if (fitness(bestCandidate) > fitness(sBest))
    sBest ← bestCandidate
end
tabuList.push(bestCandidate)

Исходный код Википедии:

https://en.wikipedia.org/wiki/Tabu_search

1 Ответ

1 голос
/ 27 марта 2019

Вопрос 1

is the neighborhood every possibility for each index?

Не каждый, в этом случае это может быть сделано, так как суммарные индексы равны 4, но это будет слишком сложно, когда число индексов увеличится.

В целом окрестности можно найти с помощью некоторой эвристики (например, прямого расстояния между индексами). Например, если путь [A, B, C, F, G, E, D, A] и для каждого индекса выбраны 2 ближайших индекса, например, [B, C], [A, F ], [A, D] и т. Д. Теперь окрестности могут быть сгенерированы с использованием этих индексов, принимая только действительные (помните, что каждый город посещают только один раз, а не в списке Табу).

Вопрос 2

so then how do we pick a different neighborhood next time?

Да, лучший кандидат выдвинут в списке, но не его соседи, поэтому он найдет новых соседей и не будет зацикливаться на бесконечном цикле.

Например, путь X даст соседям Y и Z, из которых (давайте предположим) Z является лучшим, поэтому Z будет помещен в список Табу (а X уже был в списке), поэтому теперь Z выиграл не пойду искать X и, следовательно, буду искать новых и лучших соседей.

...