我正在尝试在 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 的边缘)?