Имитация отжига TSP

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

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

Я верю, что понимаю, как работает алгоритм, но у меня проблемы с переносом этого в 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();
    }
}
Источник

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 Интерфейс - это только минимум для работы алгоритма.

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

Источник

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

Источник
Другие вопросы по тегам