网站制作公司咨询网站制作公司,山西长治做网站公司有哪些,什么是工具型网站,wordpress 函数教程视频01 什么是禁忌搜索算法#xff1f; 1.1 先从爬山算法说起 爬山算法从当前的节点开始#xff0c;和周围的邻居节点的值进行比较。 如果当前节点是最大的#xff0c;那么返回当前节点#xff0c;作为最大值 (既山峰最高点)#xff1b;反之就用最高的邻居节点来#xff0c;替… 01 什么是禁忌搜索算法 1.1 先从爬山算法说起 爬山算法从当前的节点开始和周围的邻居节点的值进行比较。 如果当前节点是最大的那么返回当前节点作为最大值 (既山峰最高点)反之就用最高的邻居节点来替换当前节点从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。因为不是全面搜索所以结果可能不是最佳。 1.2 再到局部搜索算法 局部搜索算法是从爬山法改进而来的。局部搜索算法的基本思想在搜索过程中始终选择当前点的邻居中与离目标最近者的方向搜索。同样局部搜索得到的解不一定是最优解。 1.3 然后到禁忌搜索算法 为了找到“全局最优解”就不应该执着于某一个特定的区域。于是人们对局部搜索进行了改进得出了禁忌搜索算法。 禁忌Tabu Search算法是一种亚启发式(meta-heuristic)随机搜索算法它从一个初始可行解出发选择一系列的特定搜索方向移动作为试探选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解TS搜索中采用了一种灵活的“记忆”技术对已经进行的优化过程进行记录和选择指导下一步的搜索方向这就是Tabu表的建立。 1.4 最后打个比方 为了找出地球上最高的山一群有志气的兔子们开始想办法。 1) 爬山算法兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山法它不能保证局部最优值就是全局最优值。 2) 禁忌搜索算法兔子们知道一个兔的力量是渺小的。他们互相转告着哪里的山已经找过并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。 02 思想和过程 2.1 基本思想 标记已经解得的局部最优解或求解过程并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于太过于对某一局部区域以及其邻域的搜索导致一叶障目。为了找到全局最优解禁忌搜索就是对于找到的一部分局部最优解有意识地避开它从而或得更多的搜索区域。 比喻兔子们找到了泰山它们之中的一只就会留守在这里其他的再去别的地方寻找。就这样一大圈后把找到的几个山峰一比较珠穆朗玛峰脱颖而出。 2.2 算法过程 step1给以禁忌表H空集并选定一个初始解xnow step2满足停止规则时停止计算输出结果否则在xnow的邻域N(xnow)中选择不受禁忌的候选集Can_N(xnow)在Can_N(xnow)中选一个评价值最佳的解xnextxnowxnext更新历史记录H保存f(xnow)重复step2 step3在保存的众多f中挑选最小大值作为解 03 相关概念解释 又到了科普时间了。其实关于邻域的概念前面的好多博文都介绍过了。今天还是给大家介绍一下。这些概念对理解整个算法的意义很大希望大家好好理解。 1) 邻域官方一点所谓邻域简单的说即是给定点附近其他点的集合。在距离空间中邻域一般被定义为以给定点为圆心的一个圆而在组合优化问题中邻域一般定义为由给定转化规则对给定的问题域上每结点进行转化所得到的问题域上结点的集合。通俗一点邻域就是指对当前解进行一个操作(这个操作可以称之为邻域动作)可以得到的所有解的集合。那么邻域的本质区别就在于邻域动作的不同了。 2) 邻域动作邻域动作是一个函数通过这个函数对当前解s产生其相应的邻居解集合。例如对于一个bool型问题其当前解为s 1001当将邻域动作定义为翻转其中一个bit时得到的邻居解的集合N(s){0001,1101,1011,1000}其中N(s) ∈ S。同理当将邻域动作定义为互换相邻bit时得到的邻居解的集合N(s){0101,1001,1010}。 3) 禁忌表包括禁忌对象和禁忌长度。当兔子们再寻找的时候一般地会有意识地避开泰山因为他们知道这里已经找过并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表tabu list”的含义。 4) 侯选集合侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价值最佳的邻居入选。 5) 禁忌对象禁忌算法中由于我们要避免一些操作的重复进行就要将一些元素放到禁忌表中以禁止对这些元素进行操作这些元素就是我们指的禁忌对象。当兔子们再寻找的时候一般地会有意识地避开泰山因为这里找过了。并且还有一只兔子在这留守。 6) 禁忌长度禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象x一个数禁忌长度 t 要求对象x 在t 步迭代内被禁在禁忌表中采用tabu(x)t记忆每迭代一步该项指标做运算tabu(x)t−1直到tabu(x)0时解禁。于是我们可将所有元素分成两类被禁元素和自由元素。禁忌长度t 的选取可以有多种方法例如t常数或t[√n]其中n为邻域中邻居的个数这种规则容易在算法中实现。那只留在泰山的兔子一般不会就安家在那里了它会在一定时间后重新回到找最高峰的大军因为这个时候已经有了许多新的消息泰山毕竟也有一个不错的高度需要重新考虑这个归队时间在禁忌搜索里面叫做“禁忌长度tabu length”。 7) 评价函数评价函数是侯选集合元素选取的一个评价公式侯选集合的元素通过评价函数值来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标但有时为了方便或易于计算会采用其他函数来取代目标函数。 8) 特赦规则在禁忌搜索算法的迭代过程中会出现侯选集中的全部对象都被禁忌或有一对象被禁但若解禁则其目标值将有非常大的下降情况。在这样的情况下为了达到全局最优我们会让一些禁忌对象重新可选。这种方法称为特赦相应的规则称为特赦规则。如果在搜索的过程中留守泰山的兔子还没有归队但是找到的地方全是华北平原等比较低的地方兔子们就不得不再次考虑选中泰山也就是说当一个有兔子留守的地方优越性太突出超过了“best so far”的状态就可以不顾及有没有兔子留守都把这个地方考虑进来这就叫“特赦准则aspiration criterion”。 04 代码实例(代码来源网络) 这次还是用一个求解TSP的代码实例来给大家讲解吧。 数据文件下载戳这里 http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/ 下载下来跟代码放一个路径里直接就可以跑记得把下面那个存路径的string改成你自己的。输入是0~9代表10个不同的tsp文件。 1#include iostream 2#include fstream 3#include string 4#include algorithm 5#include cstdlib 6#include climits 7#include ctime 8#include list 9using namespace std; 10 11#define TABU_SIZE 10 //禁忌代数 12#define SWAPSIZE 5 //对于每个点都只选与它距离较小的前SWAPSIZE个与它交换 13#define ITERATIONS 100 14#define INF INT_MAX 15int rowIndex; 16double adj[60][60]; 17int ordered[60][60]; 18int city1[60], city2[60], path[60]; 19string filename[10] {gr17.tsp, gr21.tsp, gr24.tsp, fri26.tsp, bayg29.tsp, bays29.tsp, swiss42.tsp, gr48.tsp, hk48.tsp, brazil58.tsp}; 20int bestans[10] {2085, 2707, 1272, 937, 1610, 2020, 1273, 5046, 11461, 25395}; 21int bestIteration; 22int tabuList[2000][4]; 23 24 25bool cmp(int a, int b); 26double TabuSearch(const int N); 27double GetPathLen(int* city, const int N); 28 29int main(){ 30 string absolute(C:\\); 31 int CASE; 32 srand(time(0)); 33 while (cin CASE CASE 10 CASE -1){ 34 memset(adj, 0, sizeof(adj)); 35 memset(city1, 0, sizeof(city1)); 36 memset(city2, 0, sizeof(city2)); 37 memset(tabuList, 0, sizeof(tabuList)); 38 memset(path, 0, sizeof(path)); 39 40 string relative filename[CASE]; 41 string filepath absoluterelative; 42 ifstream infile(filepath.c_str()); 43 if (infile.fail()){ 44 cout Open failed!\n; 45 } 46 int n; 47 infile n; 48 for (int j 0; j n; j){ 49 for (int k 0; k n; k){ 50 infile adj[j][k]; 51 } 52 } 53 54 clock_t start, end; 55 start clock(); 56 int distance TabuSearch(n); 57 end clock(); 58 double costTime (end - start)*1.0/CLOCKS_PER_SEC; 59 cout TSP file: filename[CASE] endl; 60 cout Optimal Soluton: bestans[CASE] endl; 61 cout Minimal distance: distance endl; 62 cout Error: (distance - bestans[CASE]) * 100 / bestans[CASE] % endl; 63 cout Best iterations: bestIteration endl; 64 cout Cost time: costTime endl; 65 cout Path:\n; 66 for (int i 0; i n; i){ 67 cout path[i] 1 ; 68 } 69 cout endl endl;; 70 infile.close(); 71 } 72 return 0; 73} 74 75 76//生成随机的城市序列 77void CreateRandOrder(int* city, const int N){ 78 for (int i 0; i N; i){ 79 city[i] rand() % N; 80 for (int j 0; j i; j){ 81 if (city[i] city[j]){ 82 i--; 83 break; 84 } 85 } 86 } 87} 88 89 90double GetPathLen(int* city, const int N){ 91 double res adj[city[N-1]][city[0]]; 92 int i; 93 for (i 1; i N; i){ 94 res adj[city[i]][city[i-1]]; 95 } 96 return res; 97} 98 99100void UpdateTabuList(int len){101 for (int i 0; i len; i){102 if (tabuList[i][3] 0)103 tabuList[i][3]--;104 }105}106107108double TabuSearch(const int N){109 int countI, countN, NEIGHBOUR_SIZE N * (N - 1) / 2;110 double bestDis, curDis, tmpDis, finalDis INF;111 bestIteration 0; 112 string bestCode, curCode, tmpCode;113114 //预生成所有可能的邻域0、1两列是要交换的点第2列是这种交换下的路径长度第3列是禁忌长度 115 int i 0;116 for (int j 0; j N - 1; j){117 for (int k j 1; k N; k){118 tabuList[i][0] j;119 tabuList[i][1] k;120 tabuList[i][2] INF;121 i;122 }123 }124125126 //生成初始解25次用于跳出局部最优 127 for (int t 0; t 25; t){128 CreateRandOrder(city1, N);129 bestDis GetPathLen(city1, N);130131 //开始求解 132 //迭代次数为ITERATIONS 133 countI ITERATIONS;134 int a, b;135 int pardon[2], curBest[2];136 while (countI--){137 countN NEIGHBOUR_SIZE;138 pardon[0] pardon[1] curBest[0] curBest[1] INF;139 memcpy(city2, city1, sizeof(city2));140 //每次迭代搜索的邻域范围为NEIGHBOUR_SIZE 141 while (countN--){142 //交换邻域 143 a tabuList[countN][0];144 b tabuList[countN][1];145 swap(city2[a], city2[b]);146 tmpDis GetPathLen(city2, N);147 //如果新的解在禁忌表中就只存特赦相关信息 148 if (tabuList[countN][3] 0){ 149 tabuList[countN][2] INF; 150 if (tmpDis pardon[1]){151 pardon[0] countN;152 pardon[1] tmpDis;153 }154 }155 //否则把距离存起来 156 else {157 tabuList[countN][2] tmpDis;158 }159 swap(city2[a], city2[b]);//再换回去回复原状方便后面使用 160 }161 //遍历邻域求得此代最佳 162 for (int i 0; i NEIGHBOUR_SIZE; i){163 if (tabuList[i][3] 0 tabuList[i][2] curBest[1]){164 curBest[0] i;165 curBest[1] tabuList[i][2];166 }167 }168 //特赦的 169 if (curBest[0] INF || pardon[1] bestDis) {170 curBest[0] pardon[0];171 curBest[1] pardon[1];172 }173174 //更新此代最优175 if (curBest[1] bestDis){176 bestDis curBest[1];177 tabuList[curBest[0]][3] TABU_SIZE;178 bestIteration ITERATIONS - countI;179 a tabuList[curBest[0]][0];180 b tabuList[curBest[0]][1];181 swap(city1[a], city1[b]);182 }183 UpdateTabuList(NEIGHBOUR_SIZE);184 }185 //更新全局最优186 if (bestDis finalDis){187 finalDis bestDis;188 memcpy(path, city1, sizeof(path));189 }190 }191 return finalDis;192} 欲获取代码请关注我们的微信公众号【程序猿声】在后台回复TS代码。即可获取。 微信公众号转载于:https://www.cnblogs.com/dengfaheng/p/9737556.html
