本文主要是介绍禁忌搜索算法详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
引言
对于优化问题相关算法有如下分类：
禁忌搜索是由局部搜索算法发展而来，爬山法是从通用局部搜索算法改进而来。在介绍禁忌搜索之前先来熟悉下爬山法和局部搜索算法。
局部搜索算法
算法的基本思想
在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。
算法过程
（1）随机选择一个初始的可能解x0 ∈D，xb=x0,P=N(xb);//D是问题的定义域， xb用于记录到目标位置的最优解，P为xb的邻域。
（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
（3）Begin；
（4）选择P的一个子集P'，xn为P’的最优解 ； //P’可根据问题特点，选择适当大小的子集。可按概率选择
（5）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转(2)； //重新计算P，f(x)为指标函数
（6）否则P=P-P'，转(2)；
（7）End；
（8）输出计算结果；
（9）结束 ；爬山法
算法的基本思想
将搜索过程比作爬山过程，在没有任何有关山顶的其他信息的情况下，沿着高度增加的方向爬。如果相邻状态没有比当前值更高，则算法停止，认为当前值即为顶峰。
算法过程
（1） 设置初始状态n=s0为当前状态;
（2） 如果当前状态已达标，算法结束，搜索成功;
（3）获取当前状态n的若干个临近状态m,计算这些h(m), nextn=min{h(m)}；
（4） IF h(n) < h(nextn) THEN n:=nextn;ELSE 取当前状态为最佳状态并退出;
（5） GOTO (2)步;该算法在单峰的条件下，必能达到山顶。
显而易见爬山法对于复杂情况的求解会遇到以下问题：
（1）局部极值
（2）山脊：造成一系列的局部极值
（3）高原：平坦的局部极值区域——解决办法：继续侧向移动
目前有些改进的爬山法，比如随机爬山法、首选爬山法等等不再细说。
禁忌搜索算法
算法思想
标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某一局部区域以及其邻域的搜索，导致一叶障目。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而或得更多的搜索区域
算法过程
（1）给定一个禁忌表（Tabu List）H=null,并选定一个初始解X_now.
（2）如果满足停止规则，则停止计算，输出结果；否则，在X_now的领域中选出满足不受禁忌的候选集N(X_now).在N(X_now)中选择一个评价值最贱的解X_next，X_next：=X_now；更新历史记录H, 重复步骤（2）.对搜索性能有影响的因素
禁忌长度
控制其他变量，单就禁忌长度的选择而言，禁忌长度越短，机器内存占用越少，解禁范围更大（搜索范围上限越大），但很容易造成搜索循环（实际去搜索的范围却很小），过早陷入局部最优。禁忌长度过长又会导致计算时间过长。
特赦规则
通俗定义：对于在禁忌的对象，如果出现以下情况，不论现在对象的禁忌长度如何，均设为0
（1）基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；
（2）基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；
（3）基于影响力的规则，可以特赦对目标值影响大的对象。
候选集
候选集的大小，过大增加计算内存和计算时间，过小过早陷入局部最优。候选集的选择一般由邻域中的邻居组成，可以选择所有邻居，也可以选择表现较好的邻居，还可以随机选择几个邻居。
评价函数
评价函数分为直接评价函数和间接评价函数。
直接评价函数：上述例子，均直接使用目标值作为评价函数。
间接评价函数：反映目标函数特性的函数（会比目标函数的计算更为简便，用以减少计算时间等）。
终止规则
禁忌算法是一个启发式算法，我们不可能让搜索过程无穷进行，所以一些直观的终止规则就出现了
（1）确定步数终止，无法保证解的效果，应记录当前最优解；
（2）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；
（3）目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。
代码
public class TabuSearchAlgorithm {/** 迭代次数 */private int MAX_GEN;/** 每次搜索邻居个数 */private int neighbourhoodNum;/** 禁忌长度 */private int tabuTableLength;/** 节点数量，编码长度 */private int nodeNum;/** 节点间距离矩阵 */private int[][] nodeDistance;/** 当前路线 */private int[] route;/** 最好的路径 */private int[] bestRoute;/** 最佳路径总长度 */private int bestEvaluation;/** 禁忌表 */private int[][] tabuTable;/**禁忌表中的评估值*/private int[] tabuTableEvaluate;private DynamicDataWindow ddWindow;private long tp;public TabuSearchAlgorithm() {}/*** constructor of GA* * @param n* 城市数量* @param g* 运行代数* @param c* 每次搜索邻居个数* @param m* 禁忌长度* **/public TabuSearchAlgorithm(int n, int g, int c, int m) {nodeNum = n;MAX_GEN = g;neighbourhoodNum = c;tabuTableLength = m;}/*** 初始化Tabu算法类* * @param filename* 数据文件名，该文件存储所有城市节点坐标数据* @throws IOException*/private void init(String filename) throws IOException {// 读取数据int[] x;int[] y;String strbuff;FileReader fileReader = new FileReader(filename);BufferedReader data = new BufferedReader(fileReader);nodeDistance = new int[nodeNum][nodeNum];x = new int[nodeNum];y = new int[nodeNum];String[] strcol;for (int i = 0; i < nodeNum; i++) {// 读取一行数据，数据格式1 6734 1453strbuff = data.readLine();// 字符分割strcol = strbuff.split(" ");x[i] = Integer.valueOf(strcol[1]);// x坐标y[i] = Integer.valueOf(strcol[2]);// y坐标}data.close();// 计算距离矩阵// ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628for (int i = 0; i < nodeNum - 1; i++) {nodeDistance[i][i] = 0; // 对角线为0for (int j = i + 1; j < nodeNum; 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) {nodeDistance[i][j] = tij + 1;nodeDistance[j][i] = nodeDistance[i][j];} else {nodeDistance[i][j] = tij;nodeDistance[j][i] = nodeDistance[i][j];}}}nodeDistance[nodeNum - 1][nodeNum - 1] = 0;route = new int[nodeNum];bestRoute = new int[nodeNum];bestEvaluation = Integer.MAX_VALUE;tabuTable = new int[tabuTableLength][nodeNum];tabuTableEvaluate=new int[tabuTableLength];for (int i = 0; i < tabuTableEvaluate.length; i++) {tabuTableEvaluate[i]=Integer.MAX_VALUE;}}/** 生成初始群体 */void generateInitGroup() {System.out.println("1.生成初始群体");boolean iscontinue = false;for (int i = 0; i < route.length; i++) {do {iscontinue = false;route[i] = (int) (Math.random() * nodeNum);for (int j = i - 1; j >= 0; j--) {if (route[i] == route[j]) {iscontinue = true;break;}}} while (iscontinue);// System.out.println("i="+i+", route[i]="+route[i]);}}/** 复制编码体，复制Gha到Ghb */public void copyGh(int[] Gha, int[] Ghb) {for (int i = 0; i < nodeNum; i++) {Ghb[i] = Gha[i];}}/** 计算路线的总距离 */public int evaluate(int[] chr) {// 0123int len = 0;// 编码，起始城市,城市1,城市2...城市nfor (int i = 1; i < nodeNum; i++) {len += nodeDistance[chr[i - 1]][chr[i]];}// 城市n,起始城市len += nodeDistance[chr[nodeNum - 1]][chr[0]];return len;}/*** 随机获取邻域路径* @param route 当前路径* */public int[] getNeighbourhood(int[] route) {int temp;int ran1, ran2;int[] tempRoute=new int[route.length];copyGh(route, tempRoute);ran1 = (int) (Math.random() * nodeNum);do {ran2 = (int) (Math.random() * nodeNum);} while (ran1 == ran2);temp = tempRoute[ran1];tempRoute[ran1] = tempRoute[ran2];tempRoute[ran2] = temp;return tempRoute;}/*** 随机获取一定数量的领域路径* */public int[][] getNeighbourhood(int[] route, int tempNeighbourhoodNum) {int[][] NeighbourhoodRoutes=new int[tempNeighbourhoodNum][nodeNum];List<int[]> tempExchangeNodeList=new ArrayList<>();int temp;int ran0, ran1;int[] tempRoute=null;boolean iscontinue;for(int i=0; i<tempNeighbourhoodNum; i++) {tempRoute=new int[route.length];copyGh(route, tempRoute);do{iscontinue=false;//随机生成一个邻域;ran0 = (int) (Math.random() * nodeNum);do {ran1 = (int) (Math.random() * nodeNum);} while (ran0 == ran1);//判断是否重复for (int j = 0; j <tempExchangeNodeList.size(); j++) {if (tempExchangeNodeList.get(j)[0]<tempExchangeNodeList.get(j)[1]) {if ((ran0 < ran1 && (tempExchangeNodeList.get(j)[0]==ran0 && tempExchangeNodeList.get(j)[1]==ran1))||(ran0 > ran1 && (tempExchangeNodeList.get(j)[0]==ran1 && tempExchangeNodeList.get(j)[1]==ran0))) {iscontinue=true;} }else {if ((ran0 < ran1 && (tempExchangeNodeList.get(j)[0]==ran1 && tempExchangeNodeList.get(j)[1]==ran0))||(ran0 > ran1 && (tempExchangeNodeList.get(j)[0]==ran0 && tempExchangeNodeList.get(j)[1]==ran1))) {iscontinue=true;}}}if (iscontinue==false) {temp = tempRoute[ran0];tempRoute[ran0] = tempRoute[ran1];tempRoute[ran1] = temp;tempExchangeNodeList.add(new int[]{ran0,ran1});//将交换点添加到列表中用于查重；//判断是否与route相同for (int j = 0; j < tempRoute.length; j++) {if (tempRoute[j]!=route[j]) {iscontinue=false;}}if (iscontinue==false && !isInTabuTable(tempRoute)) {NeighbourhoodRoutes[i]=tempRoute;}else {iscontinue=true;}}}while(iscontinue);}return NeighbourhoodRoutes;}/** 判断路径是否在禁忌表中 */public boolean isInTabuTable(int[] tempRoute) {int i, j;int flag = 0;for (i = 0; i < tabuTableLength; i++) {flag = 0;for (j = 0; j < nodeNum; j++) {if (tempRoute[j] != tabuTable[i][j]){flag = 1;// 不相同break;}}if (flag == 0){// 相同，返回存在相同break;}}if (i == tabuTableLength){// 不等return false;// 不存在} else {return true;// 存在}}/** 解禁忌与加入禁忌，注意禁忌策略的选择 */public void flushTabuTable(int[] tempGh) {int tempValue=evaluate(tempGh);// 找到禁忌表中路径的最大值；int tempMax=tabuTableEvaluate[0];int maxValueIndex=0;for (int i = 0; i < tabuTableLength; i++) {if(tabuTableEvaluate[i]>tempMax){tempMax=tabuTableEvaluate[i];maxValueIndex=i;}}// 新的路径加入禁忌表if (tempValue<tabuTableEvaluate[maxValueIndex]) {if (tabuTableEvaluate[maxValueIndex]<Integer.MAX_VALUE) {copyGh(tabuTable[maxValueIndex], route);}System.out.println("测试点：更新禁忌表，maxValueIndex= "+maxValueIndex);for (int k = 0; k < nodeNum; k++) {tabuTable[maxValueIndex][k] = tempGh[k];}tabuTableEvaluate[maxValueIndex]=tempValue;}}/**启动禁忌搜索*/public void startSearch() {int nn;int neighbourhoodEvaluation;int currentBestRouteEvaluation;/** 存放邻域路径 */int[] neighbourhoodOfRoute = new int[nodeNum];/** 当代最好路径 */int[] currentBestRoute = new int[nodeNum];/** 当前代数 */int currentIterateNum = 0;/** 最佳出现代数 */int bestIterateNum = 0;int[][] neighbourhoodOfRoutes=null;//用于控制迭代次数int[]priviousRoute=new int[nodeNum];// 初始化编码GhhgenerateInitGroup();// 将当前路径作为最好路径copyGh(route, bestRoute);currentBestRouteEvaluation=evaluate(route);bestEvaluation = currentBestRouteEvaluation;System.out.println("2.迭代搜索....");while (currentIterateNum < MAX_GEN) {for (int i = 0; i < route.length; i++) {priviousRoute[i]=route[i];}neighbourhoodOfRoutes=getNeighbourhood(route, neighbourhoodNum);System.out.println("测试点：currentIterateNum= "+currentIterateNum);for(nn = 0; nn < neighbourhoodNum; nn++) {// 得到当前路径route的一个邻域路径neighbourhoodOfRoute
// neighbourhoodOfRoute=getNeighbourhood(route);neighbourhoodOfRoute=neighbourhoodOfRoutes[nn];neighbourhoodEvaluation = evaluate(neighbourhoodOfRoute);
// System.out.println("测试：neighbourhoodOfRoute="+neighbourhoodEvaluation);if (neighbourhoodEvaluation < currentBestRouteEvaluation) {copyGh(neighbourhoodOfRoute, currentBestRoute);currentBestRouteEvaluation = neighbourhoodEvaluation;
// System.out.println("测试：neighbourhoodOfRoute="+neighbourhoodEvaluation);}}if (currentBestRouteEvaluation < bestEvaluation) {bestIterateNum = currentIterateNum;copyGh(currentBestRoute, bestRoute);bestEvaluation = currentBestRouteEvaluation;System.out.println("测试：currentBestRouteEvaluation="+currentBestRouteEvaluation);}copyGh(currentBestRoute, route);// 解禁忌表，currentBestRoute加入禁忌表
// System.out.println("测试点：currentBestRoute= "+currentBestRoute);flushTabuTable(currentBestRoute);currentIterateNum++;for (int i = 0; i < priviousRoute.length; i++) {if (priviousRoute[i] != route[i]) {currentIterateNum=0;break;}}printRunStatus();}//结果显示：System.out.println("最佳长度出现代数：");System.out.println(bestIterateNum);System.out.println("最佳长度:");System.out.println(bestEvaluation);System.out.println("最佳路径：");for (int i = 0; i < nodeNum; i++) {System.out.print(bestRoute[i] + ",");}}/** * @Description: 输出结运行状态*/ private void printRunStatus() { long millis=System.currentTimeMillis();if (millis-tp>20) {tp=millis;ddWindow.addData(millis, bestEvaluation);}try {Thread.sleep(100L);} catch (InterruptedException e) {// TODO Auto-generated catch blocke.printStackTrace();}}/*** @param args* @throws IOException*/public static void main(String[] args) throws IOException {System.out.println("Start....");TabuSearchAlgorithm tabu = new TabuSearchAlgorithm(48, 120, 500, 100);tabu.ddWindow=new DynamicDataWindow("禁忌搜索算法优化求解过程");tabu.ddWindow.setVisible(true);tabu.init("C:\\Users\\att48.txt");tabu.startSearch();}}总结
启发式搜索算法蕴含着许多人生哲学，它虽不是数学方法，其思想更类似于人类解决问题的思想和一些人生中总结的道理，值得好好体会。最后用网上一段描述各种搜索算法的例子来作为总结：
为了找出地球上最高的山，一群有志气的兔子们开始想办法。
（1）兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山法，它不能保证局部最优值就是全局最优值。
（2）兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝他踏过的最高方向跳去。这就是模拟退火。
（3）兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。
（4）兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。
参考资料
1.爬山法 。
2.局部搜索案例与求解方法。
3.《群体智能优化算法及其应用》雷秀娟 著。
这篇关于禁忌搜索算法详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
