Simulated Annealing TSP

Question

Я ищу для реализации алгоритма имитированного отжига в Java, чтобы найти оптимальный маршрут для Travelling Salesman Problem, до сих пор я реализовал грубую силу и хочу изменить этот код, чтобы использовать имитируемый отжиг. Очевидно, что грубая сила и имитированный отжиг очень разные и используют очень разные функции.

Я понимаю, что имитационный отжиг использует переменную, известную как температура, которая затем охлаждается по мере запуска алгоритма; с высокой температурой, и она постепенно охлаждается. В то время как температура высокая, алгоритм с большей вероятностью будет выбирать решения, которые хуже, чем ток, устраняя локальные максимумы, как вы находите в аналогичном алгоритме альпинизма. Поскольку он остывает, алгоритм вряд ли примет худшие решения, и поэтому он может сосредоточиться на определенной области и найти оптимальный маршрут.

Я считаю, что я понимаю, как работает алгоритм, но у меня проблемы с его внедрением в Java, у меня есть 2 класса; один называется город, который содержит только методы отработать детали каждого города, такие как getIndex, getDistance и т.д. Класс алгоритм считывает из входного файла и сохраняет его в массиве (int [][])

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

public static void doBF() 
{ 
    int random1 = generateRand(); 

    if (towns2.size() > random1) 
    { 
     Town town = towns2.get(random1); 
     visitedTowns[i] = town; 
     towns2.remove(town); 
     i++; 
     if (lastTown != 1000) 
     { 
      journey += town.getDistance(lastTown); 
     } 
     lastTown = town.getIndex(); 
    } 
    else 
    { 
     doBF(); 
    } 
} 

Answer 1

Посмотрите на http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6. Он представляет собой хорошо документированный пример использования имитационного отжига для решения проблемы TSP.

Answer 2

Я не хочу показывать слишком много кода, так как это часть приложения, принадлежащего моему текущему тесту бакалавриата. Но здесь вы идете. Алгоритм должен быть очень общим. Взглянуть.

ОСНОВНАЯ ЧАСТЬ АЛГОРИТМА

// one could check for minimum q factor to be satisfied here 
while (temperature > 1) 
{ 
    state.step(); 
    int next = state.energy(); 

    if (acceptEnergyLevel(next)) 
    { 
    energy = next; 

    if (energy < minEnergy) 
    { 
     minState = state.copy(); 
     minEnergy = energy; 
    } 
    } 
    else 
    state.undo(); 
    temperature *= DECAY_RATE; 
} 

СОСТОЯНИЕ ИНТЕРФЕЙС

public interface State<T extends State<T>> 
{ 
    public void step(); 
    public void undo(); 
    public int energy(); 
    public T copy(); 
} 

При этом в качестве основы для алгоритма можно решить любую проблему. Не только TSP. Вам просто нужно реализовать интерфейс State, например. TspProblemInstance implements State<TspProblemInstance>. Алгоритм является общим и вернет оптимальный (или результат, очень близкий к оптимальному) объект класса TspProblemInstance. Поэтому важно, чтобы вы добросовестно применяли метод copy. Общий параметр T связан классом реализации, т.е. е. копия всегда будет иметь тип T (подтип также может быть возможен).

Вы должны добавить некоторые методы к вашей конкретной реализации интерфейса, которые показывают вам последовательность городов и т. Д. Методы в интерфейсе State являются минимальными для алгоритма работы.

Я рекомендую wiki article для дальнейшего ознакомления. И вот две другие реализации, first немного сложна, а second довольно прост, но хакерский (и не сохранен вообще). Но они должны дать вам больше понимания имитационного отжига.