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

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

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

Я считаю, что понимаю, как работает алгоритм, но у меня проблемы с его использованием в Java, у меня 2 класса; один называется City, который просто содержит методы для разработки деталей каждого города, таких как 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();
    }
}

java algorithm traveling-salesman brute-force simulated-annealing
person user2517280    schedule 24.06.2013    source источник

Ответы (2)


arrow_upward
6
arrow_downward

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

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

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

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

person mike    schedule 06.09.2013

arrow_upward
1
arrow_downward

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

person mmicheo    schedule 18.08.2013