java - 2 最优求解TSP的opt算法

Question

我正在尝试在 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 Arithmetic可以解决这个问题。基本上，我想创建两个顶点的 Tours，或者基本上是一组独特的边。现在对于每对唯一的边 (x,y) 和 (u,v)，如果成本 (x,y) + 成本 (u,v) < 成本 (x,u) + 成本 (y,v)，则我将在 (x,u) 和 (y,v) 上使用边 (x,y) 和 (u,v)。我将对每对独特的边重复这个过程，直到成本不降低。

但是我如何找到唯一的一对边来应用 2-opt 技术呢？我的意思是，如果我之前生成一个解决方案(如上面的代码)，我将如何在解决方案中找到交叉边缘(我需要检查应用 2 opt 的边缘)？

Answer 1

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 beginning", "keep the same", "reverse ending"} 因为它和 reverseTheWholeArray({"keep the same", "reverse the middle", "keep相同的"})。即{1,2,3,4}的游览与{4,3,2,1}相同。

现在有趣的部分是意识到 3-Opt 可以通过游览“轮换”和反转来实现 >:) 或最多 3 次反转。