@Test public final void testPerformOperator() { Map<Integer, Integer[]> correct = buildIsCorrect(); UnstringingT1 unstringT1 = new UnstringingT1(); double[][] tour = getSimpleTour(); for (int i = 0; i < tour.length; i++) { Integer[] result = unstringT1.performOperator(transform(tour), i, 4, getDistancecalculator(tour)).getTour(); logger.debug("Result tour for index {} is {}", i, Arrays.toString(result)); if (!isOrderCorrect(i, result, correct)) { fail("False result for index " + i + "."); } } }
@Override public OpResult performOperator(Integer[] tour, int unstringIndex, int neighbourhoodSize, IDistanceCalculator distanceCalculator) { int unstringNext = (unstringIndex + 1) % tour.length; unstringNext = (unstringNext < 0) ? unstringNext + tour.length : unstringNext; int unstringPrevious = (unstringIndex - 1) % tour.length; unstringPrevious = (unstringPrevious < 0) ? unstringPrevious + tour.length : unstringPrevious; int[] indexNeighbourhoodVJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodVK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("Indexes for neighbourhood for i+1 {} vj are {}", unstringNext, Arrays.toString(indexNeighbourhoodVJ)); logger.trace("Indexes for neighbourhood for i-1 {} vk are {}", unstringPrevious, Arrays.toString(indexNeighbourhoodVK)); List<Point> indexesToConsider = new ArrayList<>(); for (int n = 0; n < indexNeighbourhoodVJ.length; n++) { int indexJ = indexNeighbourhoodVJ[n]; int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { int[] possibleIndexesK = getPoissbleIndexesFor(tour.length, unstringNext, indexJ - 1); int[] intersectionForK = Util.getIntersection(possibleIndexesK, indexNeighbourhoodVK); if (intersectionForK != null) { logger.trace("j={}, k can be {}", indexJ, Arrays.toString(intersectionForK)); for (int m = 0; m < intersectionForK.length; m++) { int indexK = intersectionForK[m]; int canNotBeK = (unstringIndex - 1) % tour.length; canNotBeK = (canNotBeK < 0) ? canNotBeK + tour.length : canNotBeK; if(indexK != indexJ) { indexesToConsider.add(new Point(indexJ, indexK)); } } } } } Map<Integer, OpNode> bestTour = null; Point bestValue = null; double bestCost = Double.MAX_VALUE; for (Point p : indexesToConsider) { int i = unstringIndex; int j = p.x; int k = p.y; logger.trace("Consider i = {}, j = {} and k = {}", unstringIndex, j, k); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, k); Util.revert(nodes, k + 1, j); Util.insert(nodes, i - 1, k); Util.insert(nodes, i + 1, j); Util.insert(nodes, k + 1, j + 1); nodes.remove(i); if (!Util.isNull(nodes)) { double c = Util.getDistance(nodes, distanceCalculator); logger.trace("Costs c of the solution is {}", c); if (c < bestCost) { bestCost = c; bestTour = nodes; bestValue = p; } } else { logger.debug("No cost calculated due invalid tour."); } } Integer[] result = null; if(bestTour == null) { Integer[] first = Arrays.copyOfRange(tour, 0, unstringIndex); Integer[] second = Arrays.copyOfRange(tour, unstringIndex+1, tour.length); result = ArrayUtils.addAll(first, second); bestCost = Util.getDistance(result, distanceCalculator); } else { result = Util.getTour(bestTour); logger.trace("Best cost for i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Util.toString(bestTour)); logger.trace("Best cost fir i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Arrays.toString(result)); } return new OpResult(result, bestCost); }
UnstringingT1 implements IUnstringingOperator { @Override public OpResult performOperator(Integer[] tour, int unstringIndex, int neighbourhoodSize, IDistanceCalculator distanceCalculator) { int unstringNext = (unstringIndex + 1) % tour.length; unstringNext = (unstringNext < 0) ? unstringNext + tour.length : unstringNext; int unstringPrevious = (unstringIndex - 1) % tour.length; unstringPrevious = (unstringPrevious < 0) ? unstringPrevious + tour.length : unstringPrevious; int[] indexNeighbourhoodVJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodVK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("Indexes for neighbourhood for i+1 {} vj are {}", unstringNext, Arrays.toString(indexNeighbourhoodVJ)); logger.trace("Indexes for neighbourhood for i-1 {} vk are {}", unstringPrevious, Arrays.toString(indexNeighbourhoodVK)); List<Point> indexesToConsider = new ArrayList<>(); for (int n = 0; n < indexNeighbourhoodVJ.length; n++) { int indexJ = indexNeighbourhoodVJ[n]; int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { int[] possibleIndexesK = getPoissbleIndexesFor(tour.length, unstringNext, indexJ - 1); int[] intersectionForK = Util.getIntersection(possibleIndexesK, indexNeighbourhoodVK); if (intersectionForK != null) { logger.trace("j={}, k can be {}", indexJ, Arrays.toString(intersectionForK)); for (int m = 0; m < intersectionForK.length; m++) { int indexK = intersectionForK[m]; int canNotBeK = (unstringIndex - 1) % tour.length; canNotBeK = (canNotBeK < 0) ? canNotBeK + tour.length : canNotBeK; if(indexK != indexJ) { indexesToConsider.add(new Point(indexJ, indexK)); } } } } } Map<Integer, OpNode> bestTour = null; Point bestValue = null; double bestCost = Double.MAX_VALUE; for (Point p : indexesToConsider) { int i = unstringIndex; int j = p.x; int k = p.y; logger.trace("Consider i = {}, j = {} and k = {}", unstringIndex, j, k); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, k); Util.revert(nodes, k + 1, j); Util.insert(nodes, i - 1, k); Util.insert(nodes, i + 1, j); Util.insert(nodes, k + 1, j + 1); nodes.remove(i); if (!Util.isNull(nodes)) { double c = Util.getDistance(nodes, distanceCalculator); logger.trace("Costs c of the solution is {}", c); if (c < bestCost) { bestCost = c; bestTour = nodes; bestValue = p; } } else { logger.debug("No cost calculated due invalid tour."); } } Integer[] result = null; if(bestTour == null) { Integer[] first = Arrays.copyOfRange(tour, 0, unstringIndex); Integer[] second = Arrays.copyOfRange(tour, unstringIndex+1, tour.length); result = ArrayUtils.addAll(first, second); bestCost = Util.getDistance(result, distanceCalculator); } else { result = Util.getTour(bestTour); logger.trace("Best cost for i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Util.toString(bestTour)); logger.trace("Best cost fir i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Arrays.toString(result)); } return new OpResult(result, bestCost); } }
UnstringingT1 implements IUnstringingOperator { @Override public OpResult performOperator(Integer[] tour, int unstringIndex, int neighbourhoodSize, IDistanceCalculator distanceCalculator) { int unstringNext = (unstringIndex + 1) % tour.length; unstringNext = (unstringNext < 0) ? unstringNext + tour.length : unstringNext; int unstringPrevious = (unstringIndex - 1) % tour.length; unstringPrevious = (unstringPrevious < 0) ? unstringPrevious + tour.length : unstringPrevious; int[] indexNeighbourhoodVJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodVK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("Indexes for neighbourhood for i+1 {} vj are {}", unstringNext, Arrays.toString(indexNeighbourhoodVJ)); logger.trace("Indexes for neighbourhood for i-1 {} vk are {}", unstringPrevious, Arrays.toString(indexNeighbourhoodVK)); List<Point> indexesToConsider = new ArrayList<>(); for (int n = 0; n < indexNeighbourhoodVJ.length; n++) { int indexJ = indexNeighbourhoodVJ[n]; int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { int[] possibleIndexesK = getPoissbleIndexesFor(tour.length, unstringNext, indexJ - 1); int[] intersectionForK = Util.getIntersection(possibleIndexesK, indexNeighbourhoodVK); if (intersectionForK != null) { logger.trace("j={}, k can be {}", indexJ, Arrays.toString(intersectionForK)); for (int m = 0; m < intersectionForK.length; m++) { int indexK = intersectionForK[m]; int canNotBeK = (unstringIndex - 1) % tour.length; canNotBeK = (canNotBeK < 0) ? canNotBeK + tour.length : canNotBeK; if(indexK != indexJ) { indexesToConsider.add(new Point(indexJ, indexK)); } } } } } Map<Integer, OpNode> bestTour = null; Point bestValue = null; double bestCost = Double.MAX_VALUE; for (Point p : indexesToConsider) { int i = unstringIndex; int j = p.x; int k = p.y; logger.trace("Consider i = {}, j = {} and k = {}", unstringIndex, j, k); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, k); Util.revert(nodes, k + 1, j); Util.insert(nodes, i - 1, k); Util.insert(nodes, i + 1, j); Util.insert(nodes, k + 1, j + 1); nodes.remove(i); if (!Util.isNull(nodes)) { double c = Util.getDistance(nodes, distanceCalculator); logger.trace("Costs c of the solution is {}", c); if (c < bestCost) { bestCost = c; bestTour = nodes; bestValue = p; } } else { logger.debug("No cost calculated due invalid tour."); } } Integer[] result = null; if(bestTour == null) { Integer[] first = Arrays.copyOfRange(tour, 0, unstringIndex); Integer[] second = Arrays.copyOfRange(tour, unstringIndex+1, tour.length); result = ArrayUtils.addAll(first, second); bestCost = Util.getDistance(result, distanceCalculator); } else { result = Util.getTour(bestTour); logger.trace("Best cost for i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Util.toString(bestTour)); logger.trace("Best cost fir i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Arrays.toString(result)); } return new OpResult(result, bestCost); }  }
UnstringingT1 implements IUnstringingOperator { @Override public OpResult performOperator(Integer[] tour, int unstringIndex, int neighbourhoodSize, IDistanceCalculator distanceCalculator) { int unstringNext = (unstringIndex + 1) % tour.length; unstringNext = (unstringNext < 0) ? unstringNext + tour.length : unstringNext; int unstringPrevious = (unstringIndex - 1) % tour.length; unstringPrevious = (unstringPrevious < 0) ? unstringPrevious + tour.length : unstringPrevious; int[] indexNeighbourhoodVJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodVK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("Indexes for neighbourhood for i+1 {} vj are {}", unstringNext, Arrays.toString(indexNeighbourhoodVJ)); logger.trace("Indexes for neighbourhood for i-1 {} vk are {}", unstringPrevious, Arrays.toString(indexNeighbourhoodVK)); List<Point> indexesToConsider = new ArrayList<>(); for (int n = 0; n < indexNeighbourhoodVJ.length; n++) { int indexJ = indexNeighbourhoodVJ[n]; int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { int[] possibleIndexesK = getPoissbleIndexesFor(tour.length, unstringNext, indexJ - 1); int[] intersectionForK = Util.getIntersection(possibleIndexesK, indexNeighbourhoodVK); if (intersectionForK != null) { logger.trace("j={}, k can be {}", indexJ, Arrays.toString(intersectionForK)); for (int m = 0; m < intersectionForK.length; m++) { int indexK = intersectionForK[m]; int canNotBeK = (unstringIndex - 1) % tour.length; canNotBeK = (canNotBeK < 0) ? canNotBeK + tour.length : canNotBeK; if(indexK != indexJ) { indexesToConsider.add(new Point(indexJ, indexK)); } } } } } Map<Integer, OpNode> bestTour = null; Point bestValue = null; double bestCost = Double.MAX_VALUE; for (Point p : indexesToConsider) { int i = unstringIndex; int j = p.x; int k = p.y; logger.trace("Consider i = {}, j = {} and k = {}", unstringIndex, j, k); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, k); Util.revert(nodes, k + 1, j); Util.insert(nodes, i - 1, k); Util.insert(nodes, i + 1, j); Util.insert(nodes, k + 1, j + 1); nodes.remove(i); if (!Util.isNull(nodes)) { double c = Util.getDistance(nodes, distanceCalculator); logger.trace("Costs c of the solution is {}", c); if (c < bestCost) { bestCost = c; bestTour = nodes; bestValue = p; } } else { logger.debug("No cost calculated due invalid tour."); } } Integer[] result = null; if(bestTour == null) { Integer[] first = Arrays.copyOfRange(tour, 0, unstringIndex); Integer[] second = Arrays.copyOfRange(tour, unstringIndex+1, tour.length); result = ArrayUtils.addAll(first, second); bestCost = Util.getDistance(result, distanceCalculator); } else { result = Util.getTour(bestTour); logger.trace("Best cost for i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Util.toString(bestTour)); logger.trace("Best cost fir i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Arrays.toString(result)); } return new OpResult(result, bestCost); }  @Override OpResult performOperator(Integer[] tour, int unstringIndex, int neighbourhoodSize, IDistanceCalculator distanceCalculator); }
UnstringingT1 implements IUnstringingOperator { @Override public OpResult performOperator(Integer[] tour, int unstringIndex, int neighbourhoodSize, IDistanceCalculator distanceCalculator) { int unstringNext = (unstringIndex + 1) % tour.length; unstringNext = (unstringNext < 0) ? unstringNext + tour.length : unstringNext; int unstringPrevious = (unstringIndex - 1) % tour.length; unstringPrevious = (unstringPrevious < 0) ? unstringPrevious + tour.length : unstringPrevious; int[] indexNeighbourhoodVJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodVK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("Indexes for neighbourhood for i+1 {} vj are {}", unstringNext, Arrays.toString(indexNeighbourhoodVJ)); logger.trace("Indexes for neighbourhood for i-1 {} vk are {}", unstringPrevious, Arrays.toString(indexNeighbourhoodVK)); List<Point> indexesToConsider = new ArrayList<>(); for (int n = 0; n < indexNeighbourhoodVJ.length; n++) { int indexJ = indexNeighbourhoodVJ[n]; int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { int[] possibleIndexesK = getPoissbleIndexesFor(tour.length, unstringNext, indexJ - 1); int[] intersectionForK = Util.getIntersection(possibleIndexesK, indexNeighbourhoodVK); if (intersectionForK != null) { logger.trace("j={}, k can be {}", indexJ, Arrays.toString(intersectionForK)); for (int m = 0; m < intersectionForK.length; m++) { int indexK = intersectionForK[m]; int canNotBeK = (unstringIndex - 1) % tour.length; canNotBeK = (canNotBeK < 0) ? canNotBeK + tour.length : canNotBeK; if(indexK != indexJ) { indexesToConsider.add(new Point(indexJ, indexK)); } } } } } Map<Integer, OpNode> bestTour = null; Point bestValue = null; double bestCost = Double.MAX_VALUE; for (Point p : indexesToConsider) { int i = unstringIndex; int j = p.x; int k = p.y; logger.trace("Consider i = {}, j = {} and k = {}", unstringIndex, j, k); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, k); Util.revert(nodes, k + 1, j); Util.insert(nodes, i - 1, k); Util.insert(nodes, i + 1, j); Util.insert(nodes, k + 1, j + 1); nodes.remove(i); if (!Util.isNull(nodes)) { double c = Util.getDistance(nodes, distanceCalculator); logger.trace("Costs c of the solution is {}", c); if (c < bestCost) { bestCost = c; bestTour = nodes; bestValue = p; } } else { logger.debug("No cost calculated due invalid tour."); } } Integer[] result = null; if(bestTour == null) { Integer[] first = Arrays.copyOfRange(tour, 0, unstringIndex); Integer[] second = Arrays.copyOfRange(tour, unstringIndex+1, tour.length); result = ArrayUtils.addAll(first, second); bestCost = Util.getDistance(result, distanceCalculator); } else { result = Util.getTour(bestTour); logger.trace("Best cost for i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Util.toString(bestTour)); logger.trace("Best cost fir i = {} is {} with j={}, k={} from {}", unstringIndex, bestCost, bestValue.x, bestValue.y, Arrays.toString(result)); } return new OpResult(result, bestCost); }  @Override OpResult performOperator(Integer[] tour, int unstringIndex, int neighbourhoodSize, IDistanceCalculator distanceCalculator);  }