一、TSP问题
TSP问题(Travelling Salesman Problem )是一个旅行者问题，也被翻译为旅游推销员问题、货郎担问题，是数学领域有名的问题之一。 假设一个旅行商人要访问n个城市，他必须选择去的路径。 路径限制是每个城市只能访问一次，最后返回原来出发的城市。 路径的选择目标是所要求的路径的路程在所有路径中是最小的。
TSP问题是一个组合优化问题。 这个问题可以证明有NPC计算的复杂性。 TSP问题可分为对称TSP问题(Symmetric TSP )和不对称问题(Asymmetric TSP )两类。 的所有TSP问题都可以用一个图表(Graph )来描述。
V={c1, c2, …, ci, …, cn}，i = 1,2, …, n，是所有城市的集合.ci表示第i个城市， n为城市的数目；
E={(r, s): r,s V}是所有城市之间连接的集合；
C = {crs: r,s V}是所有城市之间连接的成本度量（一般为城市之间的距离）；
如果crs = csr, 那么该TSP问题为对称的，否则为非对称的。
一个TSP问题可以表达为：
求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。
二、禁忌搜索算法
禁忌搜索(Tabu Search或Taboo Search，简称TS ) )思想最初由Glover(1986 )提出，它是局部区域搜索的扩展，是全局渐进算法，是人类智力过程的模拟其特点是采用禁忌技术，用一个禁忌表记录已经达到的局部最优点，下一步搜索不再或有选择地利用禁忌表信息搜索这些优点，以摆脱局部最优点。 该算法可以克服爬山算法全局搜索能力不强的弱点。
禁忌搜索算法中，首先用随机方法生成一个初始解作为当前解，然后在当前解附近搜索一些解，其中的最优解作为新的当前解。 为了避免陷入局部最优解，该优化方法允许一定的下山操作。 另外，为了避免检索到的局部最优解的重复，禁忌检索算法通过记录利用禁忌表检索到的局部最优解的历史信息，检索过程可以在一定程度上避免局部极值点，可以开辟新的检索区域。
禁忌搜索最重要的思想是标记与搜索到的局部最优解相对应的几个对象，并且在迭代搜索中尽量避免这些对象，以保证搜索不同的有效搜索路径。 禁忌搜索涉及临域(neighborhood )、禁忌表(tabu list )、禁忌长度(tabu length )、候选解(candidate )、轻蔑标准(aspiration criterion )等概念
禁忌搜索算法实施步骤：
三、禁忌搜索算法求解TSP问题
在此JAVA实现中，我们选择使用TSPlib上的数据att48。 这是一个对称的tsp问题，城市规模为48，最佳值为10628。 该距离的计算方法如下图所示。
具体代码如下。
打包新闻； import java.io.BufferedReader； import java.io.FileInputStream； import java.io.IOException； import Java.io.input streamreader； import java.util.Random； 公共类tabu { private intmax _ gen； //重复次数private int N； //每次搜索邻居数时，都使用私有Int LL； //禁忌长度private int cityNum； //城市数，代码长度private int[][] distance； //距离矩阵private int bestT； //代数private int[] Ghh； //初始密码private int[] bestGh； //最佳密码隐私最佳评估； private int[] LocalGhh； //现代最好编码private int local evaluation [ ] temp ghh； //存储临时代码私有时间评估； private int[][] jinji； //禁忌表private int t； //当前代数私有随机随机； public Tabu () { }/* * * constructor of ga * * @ param n *城市数* @param g *执行代数* @param c *每次都在旁边搜索
居个数 * @param m * 禁忌长度 * **/public Tabu(int n, int g, int c, int m) {cityNum = n;MAX_GEN = g;N = c;ll = m;}// 给编译器一条指令，告诉它对被批注的代码元素内部的某些警告保持静默@SuppressWarnings("resource")/** * 初始化Tabu算法类 * @param filename 数据文件名，该文件存储所有城市节点坐标数据 * @throws IOException */private void init(String filename) throws IOException {// 读取数据int[] x;int[] y;String strbuff;BufferedReader data = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));distance = new int[cityNum][cityNum];x = new int[cityNum];y = new int[cityNum];for (int i = 0; i < cityNum; i++) {// 读取一行数据，数据格式1 6734 1453strbuff = data.readLine();// 字符分割String[] strcol = strbuff.split(" ");x[i] = Integer.valueOf(strcol[1]);// x坐标y[i] = Integer.valueOf(strcol[2]);// y坐标}// 计算距离矩阵// ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪醉熏的小懒猪距离，最优值为10628for (int i = 0; i < cityNum - 1; i++) {distance[i][i] = 0; // 对角线为0for (int j = i + 1; j < cityNum; j++) {double rij = Math.sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])* (y[i] - y[j])) / 10.0);// 四舍五入，取整int tij = (int) Math.round(rij);if (tij < rij) {distance[i][j] = tij + 1;distance[j][i] = distance[i][j];} else {distance[i][j] = tij;distance[j][i] = distance[i][j];}}}distance[cityNum - 1][cityNum - 1] = 0;Ghh = new int[cityNum];bestGh = new int[cityNum];bestEvaluation = Integer.MAX_VALUE;LocalGhh = new int[cityNum];localEvaluation = Integer.MAX_VALUE;tempGhh = new int[cityNum];tempEvaluation = Integer.MAX_VALUE;jinji = new int[ll][cityNum];bestT = 0;t = 0;random = new Random(System.currentTimeMillis());/* * for(int i=0;i<cityNum;i++) { for(int j=0;j<cityNum;j++) { * System.out.print(distance[i][j]+","); } System.out.println(); } */}// 初始化编码Ghhvoid initGroup() {int i, j;Ghh[0] = random.nextInt(65535) % cityNum;for (i = 1; i < cityNum;)// 编码长度{Ghh[i] = random.nextInt(65535) % cityNum;for (j = 0; j < i; j++) {if (Ghh[i] == Ghh[j]) {break;}}if (j == i) {i++;}}}// 复制编码体，复制编码Gha到Ghbpublic void copyGh(int[] Gha, int[] Ghb) {for (int i = 0; i < cityNum; i++) {Ghb[i] = Gha[i];}}public int evaluate(int[] chr) {// 0123int len = 0;// 编码，起始城市,城市1,城市2...城市nfor (int i = 1; i < cityNum; i++) {len += distance[chr[i - 1]][chr[i]];}// 城市n,起始城市len += distance[chr[cityNum - 1]][chr[0]];return len;}// 邻域交换，得到邻居public void Linju(int[] Gh, int[] tempGh) {int i, temp;int ran1, ran2;for (i = 0; i < cityNum; i++) {tempGh[i] = Gh[i];}ran1 = random.nextInt(65535) % cityNum;ran2 = random.nextInt(65535) % cityNum;while (ran1 == ran2) {ran2 = random.nextInt(65535) % cityNum;}temp = tempGh[ran1];tempGh[ran1] = tempGh[ran2];tempGh[ran2] = temp;}// 判断编码是否在禁忌表中public int panduan(int[] tempGh) {int i, j;int flag = 0;for (i = 0; i < ll; i++) {flag = 0;for (j = 0; j < cityNum; j++) {if (tempGh[j] != jinji[i][j]) {flag = 1;// 不相同break;}}if (flag == 0)// 相同，返回存在相同{// return 1;break;}}if (i == ll)// 不等{return 0;// 不存在} else {return 1;// 存在}}// 解禁忌与加入禁忌public void jiejinji(int[] tempGh) {int i, j, k;// 删除禁忌表第一个编码，后面编码往前挪动for (i = 0; i < ll - 1; i++) {for (j = 0; j < cityNum; j++) {jinji[i][j] = jinji[i + 1][j];}}// 新的编码加入禁忌表for (k = 0; k < cityNum; k++) {jinji[ll - 1][k] = tempGh[k];}}public void solve() {int nn;// 初始化编码GhhinitGroup();copyGh(Ghh, bestGh);// 复制当前编码Ghh到最好编码bestGhbestEvaluation = evaluate(Ghh);while (t < MAX_GEN) {nn = 0;localEvaluation = Integer.MAX_VALUE;while (nn < N) {Linju(Ghh, tempGhh);// 得到当前编码Ghh的邻域编码tempGhhif (panduan(tempGhh) == 0)// 判断编码是否在禁忌表中{// 不在tempEvaluation = evaluate(tempGhh);if (tempEvaluation < localEvaluation) {copyGh(tempGhh, LocalGhh);localEvaluation = tempEvaluation;}nn++;}}if (localEvaluation < bestEvaluation) {bestT = t;copyGh(LocalGhh, bestGh);bestEvaluation = localEvaluation;}copyGh(LocalGhh, Ghh);// 解禁忌表，LocalGhh加入禁忌表jiejinji(LocalGhh);t++;}System.out.println("最佳长度出现代数：");System.out.println(bestT);System.out.println("最佳长度");System.out.println(bestEvaluation);System.out.println("最佳路径：");for (int i = 0; i < cityNum; i++) {System.out.print(bestGh[i] + ",");}}/** * @param args * @throws IOException */public static void main(String[] args) throws IOException {System.out.println("Start....");Tabu tabu = new Tabu(48, 1000, 200, 20);tabu.init("c://data.txt");tabu.solve();}}
运行结果截图：
四、总结
禁忌算法其主要特点是在搜索开始阶段，解的质量提高很快，随着搜索过程的继续，解的质量的提高速度逐渐放缓，甚至在很长的搜索阶段内解的质量没有太大提高，适合中小规模的NP问题求解，整体效率比较均衡。
（接上一篇爬山算法，个人计划TSP问题系列大概会有四五种算法来求解，敬请各位期待！）
注：本文部分内容来源于网络，但程序以及分析结果属于本人成果，转载请注明！