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