2 opt Arithmetik für die optimale Lösung TSP

Question

Ich versuche eine Lösung von Traveling Verkäufer Problem in Java zu finden. Ich habe simuliertes Glühen angewendet, um dies auf die folgende Weise zu lösen. Hier ist ein Code-Segment, wo ich simulierte Glühen umgesetzt haben:

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); 
    } 
} 

, wenn ich das TSP Problem mit der oben beschriebenen Weise zu beenden, finde ich es gibt viele Kreuze im Bild, hörte ich die 2-Opt Arithmetik diese lösen kann Problem. Grundsätzlich möchte ich Touren von zwei Vertices erstellen, oder im Grunde ein Set der einzigartigen Edges. Nun für jedes eindeutige Paar von Kanten (x, y) und (u, v), wenn die Kosten (x, y) + Kosten (u, v) < Kosten (x, u) + Kosten (y, v), dann Ich werde Kanten (x, y) und (u, v) über (x, u) und (y, v) verwenden. Ich wiederhole diesen Vorgang für jedes eindeutige Kantenpaar, bis die Kosten nicht sinken.

Aber wie finde ich das einzigartige Paar Kanten, um die 2-opt-Technik anzuwenden? Ich meine, wenn ich vorher eine Lösung (wie im obigen Code) erzeuge, wie finde ich die Kreuzkanten (die Kanten, die ich untersuchen muss, um 2 Opt anzuwenden) in der Lösung?

Answer 1

2-Opt kann als Sub-Tour-Umkehrung implementiert werden.

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} diese tauscht Kanten (3,6) und (4,7) mit (3,4) und (6,7). opt2(tour,2,6)={1,2,7,4,5,6,3,8,9} Kehrt die Kanten (2,3) und (7,8) mit (2,7) und (3,8)

Beachten Sie, dass Sie nicht brauchen, um den Anfang oder das Ende des Arrays Umkehr zu berücksichtigen. {"reverse begining", "keep the same", "reverse ending"} wie es ist reverseTheWholeArray({"keep the same", "reverse the middle", "keep the same"}). Das ist eine Tour von {1,2,3,4} ist das gleiche wie {4,3,2,1}.

Jetzt ist der Spaß Teil in der Erkenntnis, dass 3-Opt mit Tour "Rotationen" und Umkehrungen> implementiert werden könnte :) oder nur bis zu 3 Umkehrungen.