2 opt арифметика для оптимального решения TSP

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

public class SimulatedAnnealing {

// Calculate the acceptance probability
public static double acceptanceProbability(int energy, int newEnergy, double temperature) {
    // If the new solution is better, accept it
    if (newEnergy < energy) {
        return 1.0;
    }
    // If the new solution is worse, calculate an acceptance probability
    return Math.exp((energy - newEnergy) / temperature);
}

public static void main(String[] args) {
    // Create and add our cities
    City city = new City(60, 200);
    TourManager.addCity(city);
    City city2 = new City(180, 200);
    TourManager.addCity(city2);
    City city3 = new City(80, 180);
    TourManager.addCity(city3);
    City city4 = new City(140, 180);
    TourManager.addCity(city4);
    City city5 = new City(20, 160);


    // Set initial temp
    double temp = 10000;

    // Cooling rate
    double coolingRate = 0.003;

    // Initialize intial solution
    Tour currentSolution = new Tour();
    currentSolution.generateIndividual();

    System.out.println("Initial solution distance: " + currentSolution.getDistance());

    // Set as current best
    Tour best = new Tour(currentSolution.getTour());

    // Loop until system has cooled
    while (temp > 1) {
        // Create new neighbour tour
        Tour newSolution = new Tour(currentSolution.getTour());

        // Get a random positions in the tour
        int tourPos1 = (int) (newSolution.tourSize() * Math.random());
        int tourPos2 = (int) (newSolution.tourSize() * Math.random());

        // Get the cities at selected positions in the tour
        City citySwap1 = newSolution.getCity(tourPos1);
        City citySwap2 = newSolution.getCity(tourPos2);

        // Swap them
        newSolution.setCity(tourPos2, citySwap1);
        newSolution.setCity(tourPos1, citySwap2);

        // Get energy of solutions
        int currentEnergy = currentSolution.getDistance();
        int neighbourEnergy = newSolution.getDistance();

        // Decide if we should accept the neighbour
        if (acceptanceProbability(currentEnergy, neighbourEnergy, temp) > Math.random()) {
            currentSolution = new Tour(newSolution.getTour());
        }

        // Keep track of the best solution found
        if (currentSolution.getDistance() < best.getDistance()) {
            best = new Tour(currentSolution.getTour());
        }

        // Cool system
        temp *= 1-coolingRate;
    }

    System.out.println("Final solution distance: " + best.getDistance());
    System.out.println("Tour: " + best);
  }
}

когда я закончу задачу TSP, используя описанный выше способ, я обнаружу, что на картинке много крестов, я слышал, что арифметика 2-Opt может решить эту проблему. По сути, я хочу создать туры из двух вершин или набор уникальных ребер. Теперь для каждой уникальной пары ребер (x, y) и (u, v), если стоимость (x, y) + стоимость (u, v) ‹ стоимость (x, u) + стоимость (y, v), то Я буду использовать ребра (x,y) и (u,v) над (x,u) и (y,v). Я буду повторять этот процесс для каждой уникальной пары ребер, пока стоимость не уменьшится.

Но как я найду уникальную пару ребер, чтобы применить метод 2-opt? Я имею в виду, если я сгенерирую решение ранее (как в приведенном выше коде), как я найду поперечные ребра (ребра, которые мне нужно изучить для применения 2 opt) в решении?


java algorithm traveling-salesman simulated-annealing
person Community    schedule 20.04.2016    source источник
comment
Обычно вы проверяете каждую пару ребер и смотрите, улучшает ли решение описанный выше обмен. Если да, то сделайте обмен. Если нет, продолжайте.   -  person LarrySnyder610    schedule 21.04.2016
comment
Обычно я получаю набор вершин (например: (60 200), (80 180), (140 180), (20 160), (180 200)) в качестве выходных данных текущего решения. Но из этого вывода: как я выберу каждую пару ребер? не могли бы вы дать мне демо-код для этой части? @grendelsdad   -  person    schedule 21.04.2016

Ответы (1)


arrow_upward
0
arrow_downward

2-Opt может быть реализован как разворот субтура.

int[] tour= new int[]{1,2,3,6,5,4,7,8,9};
List<int[]> neighboors = new ArrayList<int[]>();
for (int i = 0; i<tour.length; ++i) {
  for (int j = i+1; j<tour.length; ++j) {
    neighboors.add(opt2(tour,i,j));
  }
}
function int[] opt2(tour, i,j) {
  int n = tour.length;
  int d = Math.abs(j-i);
  if (j<i) return null;//or fix it
  d = (d+1)/2;//d+1==element count... /2 === number of pairs to swap
  for (int k = 0; k <d; k++) {
    //swap tour[i+k] and tour[j-k]
  }
}

opt2(tour,3,5)={1,2,3,4,5,6,7,8,9} это меняет местами ребра (3,6) и (4,7) с (3,4) и (6,7). opt2(tour,2,6)={1,2,7,4,5,6,3,8,9} меняет местами края (2,3) и (7,8) с (2,7) и (3,8)

Обратите внимание, что вам не нужно рассматривать реверсирование вокруг начала или конца массива. {"reverse begining", "keep the same", "reverse ending"}, так как это то же самое, что и reverseTheWholeArray({"keep the same", "reverse the middle", "keep the same"}). То есть тур {1,2,3,4} такой же, как {4,3,2,1}.

Самое интересное заключается в том, что 3-Opt может быть реализован с "ротациями" и реверсами тура >:) или только с 3 реверсами.

person user8578151    schedule 08.09.2017