fork download
copy 
  1.  
  2. /**
  3.  *
  4.  * @author http://v...content-available-to-author-only...y.com
  5.  * Use this code at your own risk ;)
  6.  */
  7.  class TabuSearch {
  8.  
  9.     public static int[] getBestNeighbour(TabuList tabuList,
  10.             TSPEnvironment tspEnviromnet,
  11.             int[] initSolution) {
  12.  
  13.  
  14.         int[] bestSol = new int[initSolution.length]; //this is the best Solution So Far
  15.         System.arraycopy(initSolution, 0, bestSol, 0, bestSol.length);
  16.         int bestCost = tspEnviromnet.getObjectiveFunctionValue(initSolution);
  17.         int city1 = 0;
  18.         int city2 = 0;
  19.         boolean firstNeighbor = true;
  20.  
  21.         for (int i = 1; i < bestSol.length - 1; i++) {
  22.             for (int j = 2; j < bestSol.length - 1; j++) {
  23.                 if (i == j) {
  24.                     continue;
  25.                 }
  26.  
  27.                 int[] newBestSol = new int[bestSol.length]; //this is the best Solution So Far
  28.                 System.arraycopy(bestSol, 0, newBestSol, 0, newBestSol.length);
  29. 				 System.out.print("init ");
  30.                 newBestSol = swapOperator(i, j, initSolution); //Try swapping cities i and j
  31.                 System.out.print("new ");
  32.                 printSolution(newBestSol);
  33.                 // , maybe we get a bettersolution
  34.                 int newBestCost = tspEnviromnet.getObjectiveFunctionValue(newBestSol);
  35.  
  36.  
  37.  
  38.                 if ((newBestCost > bestCost || firstNeighbor) && tabuList.tabuList[i][j] == 0) { //if better move found, store it
  39.                     firstNeighbor = false;
  40.                     city1 = i;
  41.                     city2 = j;
  42.                     System.arraycopy(newBestSol, 0, bestSol, 0, newBestSol.length);
  43.                     bestCost = newBestCost;
  44.                 }
  45.  
  46.  
  47.             }
  48.         }
  49.  
  50.         if (city1 != 0) {
  51.             tabuList.decrementTabu();
  52.             tabuList.tabuMove(city1, city2);
  53.         }
  54.         return bestSol;
  55.  
  56.  
  57.     }
  58.  
  59.     //swaps two cities
  60.     public static int[] swapOperator(int city1, int city2, int[] solution) {
  61.         int temp = solution[city1];
  62.         solution[city1] = solution[city2];
  63.         solution[city2] = temp;
  64.         return solution;
  65.     }
  66.  
  67.     public static void main(String[] args) {
  68.  
  69.         TSPEnvironment tspEnvironment = new TSPEnvironment();
  70.  
  71.         tspEnvironment.distances = //Distance matrix, 5x5, used to represent distances
  72.                 new int[][]  {{0, 55, 75, 115, 170, 148, 145, 159, 98, 101, 95, 50, 58, 20},
  73.                             {55, 0, 43, 115, 165, 155, 170, 198, 142, 138, 115, 75, 105, 75},
  74.                             {75, 43, 0, 80, 125, 120, 142, 181, 135, 123, 91, 64, 106, 95},
  75.                             {115 , 115, 80, 0, 56, 41, 72, 124, 102, 80, 40, 66, 100, 124},
  76.                             {170, 165, 125, 56, 0, 41, 85, 145, 120, 88, 121, 151, 178 },
  77.                             {148, 155, 120, 41, 41, 0, 45, 105, 105, 80, 55, 96, 120, 153}, 
  78.                             {145, 170, 142, 72, 85, 45, 0, 60, 75, 53, 53, 98, 103, 145},
  79.                             {159, 198, 181, 124, 145, 105, 60, 0, 63, 60, 91, 123, 104, 150},
  80.                             {98, 142, 135, 102, 120, 105, 75, 63, 0, 25, 60,72, 40, 88}, 
  81.                             {101, 138, 123, 80, 120, 80, 53, 60, 25, 0, 40, 65, 50, 95},
  82.                             {95, 115, 91, 40, 88, 55, 53, 91, 60, 40, 0, 45, 64, 98},
  83.                             {50, 75, 64, 66, 121, 96, 98, 123, 72, 65, 45, 0, 46, 58},
  84.                             {58, 105, 106, 100, 151, 120, 103, 104, 40, 50, 64, 46, 0, 47},
  85.                             {20, 75, 95, 124, 178, 153, 145, 150, 88, 95, 98, 58, 47, 0},
  86.         //Between cities. 0,1 represents distance between cities 0 and 1, and so on.
  87.  
  88.         int[] currSolution = new int[]{0, 3,1, 4,2, 7,6,8,5,10,14,11,13,12,0};  //initial solution
  89.         //city numbers start from 0
  90.         // the first and last cities' positions do not change
  91.  
  92.         int numberOfIterations = 1;
  93.         int tabuLength = 10;
  94.         TabuList tabuList = new TabuList(tabuLength);
  95.  
  96.         int[] bestSol = new int[currSolution.length]; //this is the best Solution So Far
  97.         System.arraycopy(currSolution, 0, bestSol, 0, bestSol.length);
  98.         int bestCost = tspEnvironment.getObjectiveFunctionValue(bestSol);
  99.  
  100.         for (int i = 0; i < numberOfIterations; i++) { // perform iterations here
  101.  
  102.             currSolution = TabuSearch.getBestNeighbour(tabuList, tspEnvironment, currSolution);
  103.             //printSolution(currSolution);
  104.             int currCost = tspEnvironment.getObjectiveFunctionValue(currSolution);
  105.  
  106.             //System.out.println("Current best cost = " + tspEnvironment.getObjectiveFunctionValue(currSolution));
  107.  
  108.             if (currCost < bestCost) {
  109.                 System.arraycopy(currSolution, 0, bestSol, 0, bestSol.length);
  110.                 bestCost = currCost;
  111.             }
  112.         }
  113.  
  114.         System.out.println("Search done! \nBest Solution cost found = " + bestCost + "\nBest Solution :");
  115.  
  116.         printSolution(bestSol);
  117.  
  118.  
  119.  
  120.     }
  121.  
  122.     public static void printSolution(int[] solution) {
  123.         for (int i = 0; i < solution.length; i++) {
  124.             System.out.print(solution[i] + " ");
  125.         }
  126.         System.out.println();
  127.     }
  128. }
  129.  
  130. /**
  131.  *
  132.  * @author http://v...content-available-to-author-only...y.com
  133.  * Use this code at your own risk ;)
  134.  */
  135.  class TSPEnvironment { //Tabu Search Environment
  136.  
  137.     public int [][] distances;
  138.  
  139.     public TSPEnvironment(){
  140.  
  141.     }
  142.  
  143.     public int getObjectiveFunctionValue(int solution[]){ //returns the path cost
  144.         //the first and the last cities'
  145.         //  positions do not change.
  146.         // example solution : {0, 1, 3, 4, 2, 0}
  147.  
  148.         int cost = 0;
  149.  
  150.         for(int i = 0 ; i < solution.length-1; i++){
  151.             cost+= distances[solution[i]][solution[i+1]];
  152.         }
  153.  
  154.         return cost;
  155.  
  156.     }
  157.  
  158.  
  159.  
  160. }
  161.  
  162. class TabuList {
  163.  
  164.     int [][] tabuList ;
  165.     public TabuList(int numCities){
  166.         tabuList = new int[numCities][numCities]; //city 0 is not used here, but left for simplicity
  167.     }
  168.  
  169.     public void tabuMove(int city1, int city2){ //tabus the swap operation
  170.         tabuList[city1][city2]+= 5;
  171.         tabuList[city2][city1]+= 5;
  172.  
  173.     }
  174.  
  175.     public void decrementTabu(){
  176.         for(int i = 0; i<tabuList.length; i++){
  177.            for(int j = 0; j<tabuList.length; j++){
  178.             tabuList[i][j]-=tabuList[i][j]<=0?0:1;
  179.          } 
  180.         }
  181.     }
  182.  
  183. }
  184.  
  185.  
Compilation error #stdin compilation error #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:88: error: '.class' expected
        int[] currSolution = new int[]{0, 3,1, 4,2, 7,6,8,5,10,14,11,13,12,0};  //initial solution
              ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/R1Iirh
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!