@Test public final void testPerformOperator() { Map<Integer, Integer[]> correct = buildIsCorrect(); UnstringingT2 u2 = new UnstringingT2(); double[][] tour = getSimpleTour(); for (int i = 0; i < tour.length; i++) { Integer[] result = u2.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[] indexNeighbourhoodJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, indexes for neighborhood for i+1 {} vj are {}", unstringIndex, unstringNext, Arrays.toString(indexNeighbourhoodJ)); logger.trace("i is {}, indexes for neighborhood for i-1 {} vk are {}", unstringIndex, unstringPrevious, Arrays.toString(indexNeighbourhoodK)); List<Value> valuesToConsider = new ArrayList<>(); for (int indexJ : indexNeighbourhoodJ) { int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { logger.trace("j is {} determine possible values for k", indexJ); int[] tourForK = getPoissbleIndexesFor(tour.length, indexJ + 1, unstringIndex - 2); int[] possibleIndexsForK = Util.getIntersection(tourForK, indexNeighbourhoodK); if (possibleIndexsForK != null) { for (int indexK : possibleIndexsForK) { int[] indexNeighbourhoodL = Util.getNeighbourhoodIndexesFromIndexInTour(tour, indexK + 1, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, j is {}, k is {} indexes for neighborhood for k+1 {} vl are {}", unstringIndex, indexJ, indexK, indexK + 1, Arrays.toString(indexNeighbourhoodL)); int[] tourForL = getPoissbleIndexesFor(tour.length, indexJ, indexK - 1); int[] possibleIndexesForL = Util.getIntersection(indexNeighbourhoodL, tourForL); for (int indexL : possibleIndexesForL) { valuesToConsider.add(new Value(indexJ, indexK, indexL)); } } } } } Map<Integer, OpNode> bestTour = null; Value bestValue = null; double bestCost = Double.MAX_VALUE; for (Value toConsider : valuesToConsider) { int i = unstringIndex; int j = toConsider.j; int k = toConsider.k; int l = toConsider.l; logger.trace("Consider i = {}, j = {}, k = {}, l = {}", unstringIndex, j, k, l); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, j - 1); Util.revert(nodes, l + 1, k); Util.insert(nodes, i - 1, k); Util.insert(nodes, l + 1, j - 1); Util.insert(nodes, i + 1, j); Util.insert(nodes, l, k + 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 = toConsider; } } else { logger.debug("No cost calculated due to 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 {} from {}", unstringIndex, bestCost, bestValue, Arrays.toString(result)); } return new OpResult(result, bestCost); }
UnstringingT2 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[] indexNeighbourhoodJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, indexes for neighborhood for i+1 {} vj are {}", unstringIndex, unstringNext, Arrays.toString(indexNeighbourhoodJ)); logger.trace("i is {}, indexes for neighborhood for i-1 {} vk are {}", unstringIndex, unstringPrevious, Arrays.toString(indexNeighbourhoodK)); List<Value> valuesToConsider = new ArrayList<>(); for (int indexJ : indexNeighbourhoodJ) { int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { logger.trace("j is {} determine possible values for k", indexJ); int[] tourForK = getPoissbleIndexesFor(tour.length, indexJ + 1, unstringIndex - 2); int[] possibleIndexsForK = Util.getIntersection(tourForK, indexNeighbourhoodK); if (possibleIndexsForK != null) { for (int indexK : possibleIndexsForK) { int[] indexNeighbourhoodL = Util.getNeighbourhoodIndexesFromIndexInTour(tour, indexK + 1, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, j is {}, k is {} indexes for neighborhood for k+1 {} vl are {}", unstringIndex, indexJ, indexK, indexK + 1, Arrays.toString(indexNeighbourhoodL)); int[] tourForL = getPoissbleIndexesFor(tour.length, indexJ, indexK - 1); int[] possibleIndexesForL = Util.getIntersection(indexNeighbourhoodL, tourForL); for (int indexL : possibleIndexesForL) { valuesToConsider.add(new Value(indexJ, indexK, indexL)); } } } } } Map<Integer, OpNode> bestTour = null; Value bestValue = null; double bestCost = Double.MAX_VALUE; for (Value toConsider : valuesToConsider) { int i = unstringIndex; int j = toConsider.j; int k = toConsider.k; int l = toConsider.l; logger.trace("Consider i = {}, j = {}, k = {}, l = {}", unstringIndex, j, k, l); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, j - 1); Util.revert(nodes, l + 1, k); Util.insert(nodes, i - 1, k); Util.insert(nodes, l + 1, j - 1); Util.insert(nodes, i + 1, j); Util.insert(nodes, l, k + 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 = toConsider; } } else { logger.debug("No cost calculated due to 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 {} from {}", unstringIndex, bestCost, bestValue, Arrays.toString(result)); } return new OpResult(result, bestCost); } }
UnstringingT2 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[] indexNeighbourhoodJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, indexes for neighborhood for i+1 {} vj are {}", unstringIndex, unstringNext, Arrays.toString(indexNeighbourhoodJ)); logger.trace("i is {}, indexes for neighborhood for i-1 {} vk are {}", unstringIndex, unstringPrevious, Arrays.toString(indexNeighbourhoodK)); List<Value> valuesToConsider = new ArrayList<>(); for (int indexJ : indexNeighbourhoodJ) { int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { logger.trace("j is {} determine possible values for k", indexJ); int[] tourForK = getPoissbleIndexesFor(tour.length, indexJ + 1, unstringIndex - 2); int[] possibleIndexsForK = Util.getIntersection(tourForK, indexNeighbourhoodK); if (possibleIndexsForK != null) { for (int indexK : possibleIndexsForK) { int[] indexNeighbourhoodL = Util.getNeighbourhoodIndexesFromIndexInTour(tour, indexK + 1, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, j is {}, k is {} indexes for neighborhood for k+1 {} vl are {}", unstringIndex, indexJ, indexK, indexK + 1, Arrays.toString(indexNeighbourhoodL)); int[] tourForL = getPoissbleIndexesFor(tour.length, indexJ, indexK - 1); int[] possibleIndexesForL = Util.getIntersection(indexNeighbourhoodL, tourForL); for (int indexL : possibleIndexesForL) { valuesToConsider.add(new Value(indexJ, indexK, indexL)); } } } } } Map<Integer, OpNode> bestTour = null; Value bestValue = null; double bestCost = Double.MAX_VALUE; for (Value toConsider : valuesToConsider) { int i = unstringIndex; int j = toConsider.j; int k = toConsider.k; int l = toConsider.l; logger.trace("Consider i = {}, j = {}, k = {}, l = {}", unstringIndex, j, k, l); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, j - 1); Util.revert(nodes, l + 1, k); Util.insert(nodes, i - 1, k); Util.insert(nodes, l + 1, j - 1); Util.insert(nodes, i + 1, j); Util.insert(nodes, l, k + 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 = toConsider; } } else { logger.debug("No cost calculated due to 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 {} from {}", unstringIndex, bestCost, bestValue, Arrays.toString(result)); } return new OpResult(result, bestCost); }  }
UnstringingT2 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[] indexNeighbourhoodJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, indexes for neighborhood for i+1 {} vj are {}", unstringIndex, unstringNext, Arrays.toString(indexNeighbourhoodJ)); logger.trace("i is {}, indexes for neighborhood for i-1 {} vk are {}", unstringIndex, unstringPrevious, Arrays.toString(indexNeighbourhoodK)); List<Value> valuesToConsider = new ArrayList<>(); for (int indexJ : indexNeighbourhoodJ) { int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { logger.trace("j is {} determine possible values for k", indexJ); int[] tourForK = getPoissbleIndexesFor(tour.length, indexJ + 1, unstringIndex - 2); int[] possibleIndexsForK = Util.getIntersection(tourForK, indexNeighbourhoodK); if (possibleIndexsForK != null) { for (int indexK : possibleIndexsForK) { int[] indexNeighbourhoodL = Util.getNeighbourhoodIndexesFromIndexInTour(tour, indexK + 1, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, j is {}, k is {} indexes for neighborhood for k+1 {} vl are {}", unstringIndex, indexJ, indexK, indexK + 1, Arrays.toString(indexNeighbourhoodL)); int[] tourForL = getPoissbleIndexesFor(tour.length, indexJ, indexK - 1); int[] possibleIndexesForL = Util.getIntersection(indexNeighbourhoodL, tourForL); for (int indexL : possibleIndexesForL) { valuesToConsider.add(new Value(indexJ, indexK, indexL)); } } } } } Map<Integer, OpNode> bestTour = null; Value bestValue = null; double bestCost = Double.MAX_VALUE; for (Value toConsider : valuesToConsider) { int i = unstringIndex; int j = toConsider.j; int k = toConsider.k; int l = toConsider.l; logger.trace("Consider i = {}, j = {}, k = {}, l = {}", unstringIndex, j, k, l); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, j - 1); Util.revert(nodes, l + 1, k); Util.insert(nodes, i - 1, k); Util.insert(nodes, l + 1, j - 1); Util.insert(nodes, i + 1, j); Util.insert(nodes, l, k + 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 = toConsider; } } else { logger.debug("No cost calculated due to 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 {} from {}", unstringIndex, bestCost, bestValue, Arrays.toString(result)); } return new OpResult(result, bestCost); }  @Override OpResult performOperator(Integer[] tour, int unstringIndex, int neighbourhoodSize, IDistanceCalculator distanceCalculator); }
UnstringingT2 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[] indexNeighbourhoodJ = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringNext, neighbourhoodSize, distanceCalculator); int[] indexNeighbourhoodK = Util.getNeighbourhoodIndexesFromIndexInTour(tour, unstringPrevious, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, indexes for neighborhood for i+1 {} vj are {}", unstringIndex, unstringNext, Arrays.toString(indexNeighbourhoodJ)); logger.trace("i is {}, indexes for neighborhood for i-1 {} vk are {}", unstringIndex, unstringPrevious, Arrays.toString(indexNeighbourhoodK)); List<Value> valuesToConsider = new ArrayList<>(); for (int indexJ : indexNeighbourhoodJ) { int canNotBeJ = (unstringIndex - 1) % tour.length; canNotBeJ = (canNotBeJ < 0) ? canNotBeJ + tour.length : canNotBeJ; if (indexJ != unstringIndex && indexJ != canNotBeJ) { logger.trace("j is {} determine possible values for k", indexJ); int[] tourForK = getPoissbleIndexesFor(tour.length, indexJ + 1, unstringIndex - 2); int[] possibleIndexsForK = Util.getIntersection(tourForK, indexNeighbourhoodK); if (possibleIndexsForK != null) { for (int indexK : possibleIndexsForK) { int[] indexNeighbourhoodL = Util.getNeighbourhoodIndexesFromIndexInTour(tour, indexK + 1, neighbourhoodSize, distanceCalculator); logger.trace("i is {}, j is {}, k is {} indexes for neighborhood for k+1 {} vl are {}", unstringIndex, indexJ, indexK, indexK + 1, Arrays.toString(indexNeighbourhoodL)); int[] tourForL = getPoissbleIndexesFor(tour.length, indexJ, indexK - 1); int[] possibleIndexesForL = Util.getIntersection(indexNeighbourhoodL, tourForL); for (int indexL : possibleIndexesForL) { valuesToConsider.add(new Value(indexJ, indexK, indexL)); } } } } } Map<Integer, OpNode> bestTour = null; Value bestValue = null; double bestCost = Double.MAX_VALUE; for (Value toConsider : valuesToConsider) { int i = unstringIndex; int j = toConsider.j; int k = toConsider.k; int l = toConsider.l; logger.trace("Consider i = {}, j = {}, k = {}, l = {}", unstringIndex, j, k, l); Map<Integer, OpNode> nodes = Util.constrcutOpNodes(tour); Util.revert(nodes, i + 1, j - 1); Util.revert(nodes, l + 1, k); Util.insert(nodes, i - 1, k); Util.insert(nodes, l + 1, j - 1); Util.insert(nodes, i + 1, j); Util.insert(nodes, l, k + 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 = toConsider; } } else { logger.debug("No cost calculated due to 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 {} from {}", unstringIndex, bestCost, bestValue, Arrays.toString(result)); } return new OpResult(result, bestCost); }  @Override OpResult performOperator(Integer[] tour, int unstringIndex, int neighbourhoodSize, IDistanceCalculator distanceCalculator);  }