代码
package com.dam.heuristic.ts.test; import java.util.Arrays; import java.util.HashSet; import java.util.Random; /** * 禁忌搜索 */ public class TsApi { //当前已占用的禁忌表长度 private int curUsedTabooLen; //禁忌表长度 private int tabooTableLength; //序列长度 private int sequenceLen; //最大的迭代次数 private int maxGen; //每次搜索领域的个数 private int neighbourNum; //距离矩阵 private double[][] distanceMatrix; /** * 构造函数，用于创建对象 * * @param tabooTableLength * @param maxGen * @param neighbourNum * @param distanceMatrix */ public TsApi(int tabooTableLength, int maxGen, int neighbourNum, double[][] distanceMatrix) { this.curUsedTabooLen = 0; this.tabooTableLength = tabooTableLength; this.sequenceLen = distanceMatrix[0].length; this.maxGen = maxGen; this.neighbourNum = neighbourNum; this.distanceMatrix = distanceMatrix; } /** * 禁忌搜素算法接口 */ public void solve() { 定义变量 long startTime = System.currentTimeMillis(); //禁忌表 int[][] tabooTable = new int[this.tabooTableLength][this.sequenceLen];//禁忌表 //代数 int t = 0; ///最优解 //最优代数 int bestT = 0; //序列 int[] localSequence = new int[this.sequenceLen]; //最优序列 int[] bestSequence; //存储暂时序列 int[] tempSequenceInNeighbour; //存储邻居中最好的序列对 int[] bestSequenceInNeighbour = null; //存储求得最优解的时间 long bestTime = 0; //最优序列对应的目标函数值 double bestObjectValue = 0; 生成初始序列 this.generateInitialSequence(localSequence); //初始化bestSequence，刚开始的最优序列为初始序列 bestSequence = localSequence.clone(); bestObjectValue = this.getObjectValue(bestSequence); System.out.println("初始序列：" + Arrays.toString(bestSequence)); System.out.println("初始目标函数值：" + bestObjectValue); 对序列进行迭代优化 while (t++ < this.maxGen) { //如果目标是最小化函数值，则初始化为Double.MAX_VALUE；反之，初始化为-Double.MAX_VALUE double bestObjectValueInNeighbour = Double.MAX_VALUE; //neighbourNum ：搜索领域个数 int i = 0; while (i < this.neighbourNum) { //产生一条新序列 tempSequenceInNeighbour = this.generateNewSequence(localSequence); //判断是否在禁忌表中 if (isSequenceAtTabooTable(tabooTable, tempSequenceInNeighbour) == false) { //搜索到的邻居序列不在禁忌表中，i才加一 i++; //不在禁忌表中时，执行下面的计算，获取tempSequence所对应的目标函数值 double tempObjectValue = this.getObjectValue(tempSequenceInNeighbour); //更新最优解 if (tempObjectValue < bestObjectValueInNeighbour) { bestObjectValueInNeighbour = tempObjectValue; bestSequenceInNeighbour = tempSequenceInNeighbour.clone(); } } } //解禁忌表，LocalGh加入禁忌表 this.addSequenceToTabooTable(tabooTable, bestSequenceInNeighbour); //接受邻居序列中的最优序列，让算法可以跳出局部最优 localSequence = bestSequenceInNeighbour.clone(); // System.out.println("当前最优邻居目标函数值：" + bestObjectValueInNeighbour); // System.out.println("当前最优邻居解：" + Arrays.toString(bestSequenceInNeighbour)); // System.out.println("当前最优解为：" + bestObjectValue + "，求得最优解的时间：" + bestTime + "ms"); //更新全局最优解 if (bestObjectValueInNeighbour < bestObjectValue) { //更新最优代数 bestT = t; //更新最优目标函数值 bestObjectValue = bestObjectValueInNeighbour; //更新最优序列 bestSequence = localSequence.clone(); System.out.println("----------------------------------------------------------------------------------------------------------------"); System.out.println("当前代数：" + t); System.out.println("当前最优解为：" + bestObjectValue); bestTime = (System.currentTimeMillis() - startTime); System.out.println("当前计算时间为：" + bestTime + "ms"); System.out.println("----------------------------------------------------------------------------------------------------------------"); } // System.out.println("当前计算时间为：" + (System.currentTimeMillis() - startTime) + "ms"); // System.out.println("----------------------------------------------------------------------------------------------------------------"); } System.out.println("最佳迭代次数:" + bestT); System.out.println("最优目标函数值:" + bestObjectValue); System.out.println("最优解对应序列：" + Arrays.toString(bestSequence)); System.out.println("计算时间为：" + (System.currentTimeMillis() - startTime) + "ms"); } /** * 生成初始序列 */ public 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 */ public 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; } /** * 生产新序列 * * @param sequence * @return */ public int[] generateNewSequence(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; } /** * 将序列加入禁忌表，如果禁忌表已满，根据先进先出的原则移除最早进入禁忌表的序列 * * @param tabooTable * @param sequence */ public void addSequenceToTabooTable(int[][] tabooTable, int[] sequence) { if (this.curUsedTabooLen < this.tabooTableLength) { //如果当前禁忌表还有空位，则直接加入即可 for (int i = 0; i < sequence.length; i++) { tabooTable[this.curUsedTabooLen][i] = sequence[i]; } this.curUsedTabooLen++; } else { //如果禁忌表已经满了，则移除第一个进表的路径，添加新的路径到禁忌表末尾 //后面的禁忌编码全部向前移动一位，覆盖掉当前第一个禁忌编码 for (int i = 0; i < tabooTable.length - 1; i++) { tabooTable[i] = tabooTable[i + 1].clone(); } //将sequence加入到禁忌队列的最后 for (int i = 0; i < sequence.length; i++) { tabooTable[tabooTable.length - 1][i] = sequence[i]; } } } /** * 判断序列对是否存在于禁忌表中 * * @param tabooTable * @param sequence * @return */ public boolean isSequenceAtTabooTable(int[][] tabooTable, int[] sequence) { for (int i = 0; i < tabooTable.length; i++) { boolean flag = true; for (int j = 0; j < sequence.length; j++) { if (sequence[j] != tabooTable[i][j]) { flag = false; break; } } if (flag == true) { return true; } } return false; } }
测试
package com.dam.heuristic.ts.test; import java.io.File; import java.io.FileInputStream; public class TsMainRun { public static void main(String[] args) throws Exception { 声明变量 //距离矩阵，可以直接获取任意两个编号城市的距离 double[][] distanceMatrix; 读取数据 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]; for (int i = 0; i < cityDataArr.length; i++) { String[] city1Arr = cityDataArr[i].split(" "); 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]; } } } /* System.out.println("输出距离矩阵-------------------------------------------------------------------"); for (double[] matrix : distanceMatrix) { System.out.println(Arrays.toString(matrix)); }*/ TsApi TSApi = new TsApi(20, 100000, 100, distanceMatrix); TSApi.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) { } } } }
最佳迭代次数:37144 最优目标函数值:10666.643562660376 最优解对应序列：[34, 44, 9, 23, 41, 4, 47, 38, 31, 20, 12, 24, 13, 22, 10, 46, 19, 11, 14, 32, 45, 35, 29, 42, 16, 26, 18, 36, 5, 27, 6, 17, 43, 30, 37, 8, 7, 0, 39, 2, 21, 15, 40, 33, 28, 1, 3, 25] 计算时间为：2375ms
