1

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

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

4

1 回答 1

0

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 次反转。

于 2017-09-08T08:16:06.550 回答