代码
package com.dam.heuristic.algorithm.vns.dam.v2; import java.util.*; public class VnsApiV2 { //迭代次数 private int GEN_NUM; //变领域下降搜索时，每种领域搜索方式的搜索次数 private int SEARCH_NUM; //城市数量 private int CITY_NUM; //多少次没有找到更优解退出迭代 private int NUM_OF_NOT_FIND_BETTER_SOLUTION; //距离矩阵 private double[][] distanceMatrix; public VnsApiV2(int genNum, int searchNum, int numOfNotFindBetterSolution, double[][] distanceMatrix) { this.GEN_NUM = genNum; this.SEARCH_NUM = searchNum; this.NUM_OF_NOT_FIND_BETTER_SOLUTION = numOfNotFindBetterSolution; this.distanceMatrix = distanceMatrix; this.CITY_NUM = distanceMatrix[0].length; } /** * 求解 */ public int[] solve() { 声明变量 //开始求解时间 long startTime = System.currentTimeMillis(); ///最优解 //序列 int[] localSequence = new int[this.distanceMatrix[0].length]; //最优序列 int[] bestSequence; //最优序列对应的目标函数值 double bestObjectValue; 生成初始序列 this.generateInitialSequence(localSequence); //初始化bestSequence，刚开始的最优序列为初始序列 bestSequence = localSequence.clone(); bestObjectValue = this.getObjectValue(bestSequence); 迭代优化 int numOfNotFindBetterSolution = 0; for (int iterations = 0; iterations < this.GEN_NUM; iterations++) { if (numOfNotFindBetterSolution>this.NUM_OF_NOT_FIND_BETTER_SOLUTION){ //很长时间都找不到更优解了，说明解已经相对稳定了，牺牲解质量换取更短的求解时间 break; } int k = 1; boolean isFindBetterSolution = false; while (true) { ///扰动序列(SHAKING PROCEDURE) //扰动最优解产生新解 if (k == 1) { //随机翻转最优解的一段序列来生成新解 localSequence = this.generateNewSequenceByReverseTwoElement(bestSequence); } else if (k == 2) { //扰动最优解产生新解 localSequence = this.perturbation(bestSequence); } else { break; } ///变邻域下降搜索(VARIABLE NEIGHBORHOOD DESCENT) localSequence = this.variableNeighborhoodDescent(localSequence); double localObjectValue = this.getObjectValue(localSequence); ///更新最优解(tsp问题：优化目标为总距离越短越好) if (localObjectValue < bestObjectValue) { bestObjectValue = localObjectValue; bestSequence = localSequence.clone(); k = 0; isFindBetterSolution = true; System.out.println("最优目标函数值:" + bestObjectValue); System.out.println("计算时间为：" + (System.currentTimeMillis() - startTime) * 1.0 / 1000 + "s"); } k++; } if (isFindBetterSolution == true) { numOfNotFindBetterSolution = 0; } else { numOfNotFindBetterSolution++; } } System.out.println("最优目标函数值:" + bestObjectValue); System.out.println("最优解对应序列：" + Arrays.toString(bestSequence)); System.out.println("计算时间为：" + (System.currentTimeMillis() - startTime) * 1.0 / 1000 + "s"); return bestSequence; } /** * 变邻域下降搜索 * * @param localSequence * @return */ private int[] variableNeighborhoodDescent(int[] localSequence) { //定义初始解 double localObjectValue = this.getObjectValue(localSequence); //使用领域动作类型 int l = 1; while (true) { if (l == 1) { //第一种邻域搜索方式：随机交换两个元素的位置 for (int i = 0; i < SEARCH_NUM; i++) { //找localSequence对应的比较好的邻居序列 int[] tempSequence = this.generateNewSequenceBySwapTwoElement(localSequence); double tempObjectValue = this.getObjectValue(tempSequence); //更新localSequence及其对应的解 if (tempObjectValue < localObjectValue) { localSequence = tempSequence.clone(); localObjectValue = tempObjectValue; //当在本邻域搜索找不出一个比当前解更优的解的时候，我们就跳到下一个邻域继续进行搜索; //当在本邻域搜索找到了一个比当前解更优的解的时候，我们就跳回第一个邻域重新开始搜索 l = 0; } } } else if (l == 2) { //第二种邻域搜索方式：将一个元素取出来，插入到另一个位置 for (int i = 0; i < SEARCH_NUM; i++) { //找localSequence对应的比较好的邻居序列 int[] tempSequence = this.insertElementToAnotherPosition(localSequence); double tempObjectValue = this.getObjectValue(tempSequence); //更新localSequence及其对应的解 if (tempObjectValue < localObjectValue) { localSequence = tempSequence.clone(); localObjectValue = tempObjectValue; //当在本邻域搜索找不出一个比当前解更优的解的时候，我们就跳到下一个邻域继续进行搜索; //当在本邻域搜索找到了一个比当前解更优的解的时候，我们就跳回第一个邻域重新开始搜索 l = 0; } } } else { break; } l++; } return localSequence; } /** * 通过反转indexI和indexJ之间的元素，产生新的序列 * * @param sequence */ private int[] generateNewSequenceByReverseTwoElement(int[] sequence) { //克隆出新序列 int[] newSequence = sequence.clone(); int temp; Random random = new Random(); int indexI = random.nextInt(sequence.length); int indexJ = random.nextInt(sequence.length); while (indexI == indexJ) { indexJ = random.nextInt(sequence.length); } //当indexJ更小时，将indexI和indexJ的数值进行交换 if (indexJ < indexI) { temp = indexI; indexI = indexJ; indexJ = temp; } //不但交换indexI和indexJ对应的元素 while (indexI < indexJ) { temp = newSequence[indexI]; newSequence[indexI] = newSequence[indexJ]; newSequence[indexJ] = temp; indexI++; indexJ--; } return newSequence; } /** * 随机交换两个元素的位置 * * @param sequence * @return */ private int[] generateNewSequenceBySwapTwoElement(int[] sequence) { int[] sequenceClone = sequence.clone(); //对序列中的元素进行打乱，即可产生新的序列 Random random = new Random(); int i = random.nextInt(sequence.length); int j = random.nextInt(sequence.length); while (i == j) { j = random.nextInt(sequence.length); } int temp = sequenceClone[i]; sequenceClone[i] = sequenceClone[j]; sequenceClone[j] = temp; return sequenceClone; } /** * 将index1的元素插入到index2的位置 * * @param sequence 序列 * @param sequence */ private int[] insertElementToAnotherPosition(int[] sequence) { 变量声明 //随机生成两个索引 Random random = new Random(); int index1 = random.nextInt(sequence.length); int index2 = random.nextInt(sequence.length); //判断是前面插到后面还是后面插到前面 type 0:前面插到后面 1：后面插到前面 int type = index1 < index2 ? 0 : 1; //克隆一份序列出来 int[] sequenceClone = sequence.clone(); 执行插入 if (type == 0) { //--if--将前面的元素插到后面 //取出要迁移的元素 int moveElement = sequenceClone[index1]; //从index1+1开始，将后面的元素分别向前挪动1位 for (int i = index1 + 1; i <= index2; i++) { sequenceClone[i - 1] = sequenceClone[i]; } //将moveElement插入到index2 sequenceClone[index2] = moveElement; } else { //--if--将后面的元素插到前面 //取出要迁移的元素 int moveElement = sequenceClone[index1]; //从index1开始，将元素分别向后挪动1位 for (int i = index1; i > index2; i--) { sequenceClone[i] = sequenceClone[i - 1]; } //将moveElement插入到index2 sequenceClone[index2] = moveElement; } return sequenceClone; } /** * 扰动序列 * 通过将bestSequence的元素分为四组，然后改变四个组的组序，获得新序列 * * @param bestSequence */ private int[] perturbation(int[] bestSequence) { Random random = new Random(); int[] newSequence = new int[bestSequence.length]; 获取五个index，这五个index将bestSequence划分为四组(并非均分) //this.cityNum - 2的原因是：indexArr[0]和indexArr[4]都已经确定 int elementNumInOneGroup = (this.CITY_NUM - 2) / 3; int[] indexArr = new int[5]; indexArr[0] = 0; indexArr[1] = random.nextInt(elementNumInOneGroup) + 1; indexArr[2] = random.nextInt(elementNumInOneGroup) + elementNumInOneGroup + 1; indexArr[3] = random.nextInt(elementNumInOneGroup) + elementNumInOneGroup * 2 + 1; indexArr[4] = this.CITY_NUM; 将组别[0,1,2,3]对应的元素赋值给newSequence ///将组序打乱 List<Integer> groupCodeList = new ArrayList<>(); //将[0,1,2,3]赋值给集合 Collections.addAll(groupCodeList, 0, 1, 2, 3); //随机打乱 Collections.shuffle(groupCodeList); ///赋值 int index = 0; for (int i = 0; i < groupCodeList.size(); i++) { for (int j = indexArr[groupCodeList.get(i)]; j < indexArr[groupCodeList.get(i) + 1]; j++) { newSequence[index] = bestSequence[j]; index++; } } return newSequence; } /** * 生成初始序列 */ private void generateInitialSequence(int[] sequence) { HashSet<Integer> sequenceSet = new HashSet<>(); for (int i = 1; i < sequence.length; i++) { sequenceSet.add(i); } //贪婪算法获取初始序列，从城市0开始旅行，即城市0为起点城市 sequence[0] = 0; //每次获取离当前城市最近的城市，并加入到sequence for (int i = 1; i < sequence.length; i++) { //寻找离i-1城市最近的城市，即确定第i个城市是哪个 double smallDistance = Double.MAX_VALUE; int curCity = 0; for (Integer j : sequenceSet) { if (this.distanceMatrix[sequence[i - 1]][j] < smallDistance && j != sequence[i - 1]) { smallDistance = this.distanceMatrix[sequence[i - 1]][j]; curCity = j; } } sequence[i] = curCity; sequenceSet.remove(curCity); } /* for (int i = 0; i < sequence.length; i++) { sequence[i] = i; }*/ } /** * 根据当前序列获取目标函数值 * * @param sequence * @return */ private double getObjectValue(int[] sequence) { double objectValue = 0; //计算从第0个城市到最后一个城市的路程 for (int i = 0; i < sequence.length - 1; i++) { objectValue += this.distanceMatrix[sequence[i]][sequence[i + 1]]; } //计算最后一个城市到第0个城市的路程 objectValue += this.distanceMatrix[sequence[0]][sequence[sequence.length - 1]]; return objectValue; } }
测试
package com.dam.heuristic.algorithm.vns.dam; import com.dam.heuristic.algorithm.vns.dam.v1.VnsApiV1; import com.dam.heuristic.algorithm.vns.dam.v2.VnsApiV2; import java.io.File; import java.io.FileInputStream; public class VnsMainRun { public static void main(String[] args) throws Exception { 声明变量 //距离矩阵，可以直接获取任意两个编号城市的距离 double[][] distanceMatrix; //存储每个城市对应的x,y坐标 double[][] cityPositionArr; 读取数据 String data = read(new File("src/main/java/com/data/tsp/att48.txt"), "GBK"); String[] cityDataArr = data.split("\n"); //初始化数组 distanceMatrix = new double[cityDataArr.length][cityDataArr.length]; cityPositionArr = new double[cityDataArr.length][2]; for (int i = 0; i < cityDataArr.length; i++) { String[] city1Arr = cityDataArr[i].split(" "); cityPositionArr[i][0] = Double.valueOf(city1Arr[1]); cityPositionArr[i][1] = Double.valueOf(city1Arr[2]); int cityOne = Integer.valueOf(city1Arr[0]); for (int j = 0; j < i; j++) { String[] city2Arr = cityDataArr[j].split(" "); int cityTwo = Integer.valueOf(city2Arr[0]); if (cityOne == cityTwo) { distanceMatrix[cityOne - 1][cityTwo - 1] = 0; } else { distanceMatrix[cityOne - 1][cityTwo - 1] = getDistance(Double.valueOf(city1Arr[1]), Double.valueOf(city1Arr[2]), Double.valueOf(city2Arr[1]), Double.valueOf(city2Arr[2])); //对称赋值 distanceMatrix[cityTwo - 1][cityOne - 1] = distanceMatrix[cityOne - 1][cityTwo - 1]; } } } /* VnsApiV1 vnsApiV1 = new VnsApiV1(1000, 40, 500, 50, distanceMatrix); vnsApiV1.solve();*/ VnsApiV2 vnsApiV2 = new VnsApiV2(3000, 100, 100000, distanceMatrix); vnsApiV2.solve(); } /** * 给定两个城市坐标，获取两个城市的直线距离 * * @param x1 * @param y1 * @param x2 * @param y2 * @return */ private static double getDistance(double x1, double y1, double x2, double y2) { return Math.sqrt((Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2)) / 10); } private static String read(File f, String charset) throws Exception { FileInputStream fstream = new FileInputStream(f); try { int fileSize = (int) f.length(); if (fileSize > 1024 * 512) { throw new Exception("File too large to read! size=" + fileSize); } byte[] buffer = new byte[fileSize]; fstream.read(buffer); return new String(buffer, charset); } finally { try { fstream.close(); } catch (Exception e) { } } } }
结果
att48
最优目标函数值:10745.961500968939 最优解对应序列：[19, 11, 14, 32, 45, 35, 29, 42, 16, 26, 18, 36, 5, 27, 6, 17, 43, 30, 37, 7, 0, 8, 39, 2, 21, 15, 40, 33, 47, 4, 28, 1, 41, 25, 3, 34, 44, 9, 23, 31, 38, 20, 12, 24, 13, 22, 10, 46] 计算时间为：0.688s
随机生成500城市
