一. 禁忌搜索算法
禁忌搜索算法是一种全局性邻域搜索算法，模拟人类具有记忆功能的寻优特征。它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索，并通过破禁水平来释放一些被禁忌的优良状态，进而保证多样化的有效搜索，以实现全局优化。
二. 禁忌搜索计算流程以及Matlab实现
1. 算法流程图
2. 代码实现
主程序
%% 禁忌搜索算法求解TSP问题程序clearclcdata = initData(); % 存放城市之间距离的矩阵cityQty = size(data,1); % 城市总数otherCities = 2:cityQty; tabuTimes = 3;% 禁忌次数% 随机产生初始解randCities = otherCities(randperm(cityQty - 1));xnew = [1 randCities]; % 产生xnewfitxnew = routeDistance(data,xnew);% 计算xnew解的路线长度xbest = xnew; % 让xbest = xnewfitxbest = fitxnew; % 让fitxbest = fitxnew% 定义禁忌表，1，2为置换的两点符号，3为禁忌剩余代数tabuTable = zeros(0,3);% 循环计算isStop = 0;while isStop < 4 % 设置迭代次数% 使用2-opt方式产生xnew的全部邻域解[neighbors,changePos] = neighborBy2opt(xnew); % 产生xnew的邻域解% 计算neighbors中每个解的值，并获取最小值neighborRows = size(neighbors,1);fitnesses = zeros(neighborRows, 2);for i = 1 : neighborRowsfitnesses(i,1) = routeDistance(data, neighbors(i,:));minC = min(changePos(i,:));maxC = max(changePos(i,:));for j = 1 : size(tabuTable,1)if tabuTable(j,1) == minC && tabuTable(j,2) == maxCfitnesses(i,2) = 1;% 特赦准则if fitnesses(i, 1) < fitxbest fitnesses(i,2) = 0;endendendend[~, idx] = sortrows(fitnesses, [2,1]);xnow = neighbors(idx(1),:);fitnow = fitnesses(idx(1),1);tabuObj = changePos(idx(1), :); % 禁忌对象tabuTable = updataTabuTable(tabuTable, tabuObj, tabuTimes); % 更新禁忌表% 进行解的更新和终止循环判断if fitnow < fitxbestxbest = xnow;fitxbest = fitnow;isStop = 0;elseisStop = isStop + 1;endxnew = xnow;end% 输出结果disp('----------------------最短路径------------------------');disp(xbest);disp('---------------------最短路径长度---------------------');disp(fitxbest);
initData()函数
初始化数据
%% 初始化数据: 各个城市之间的距离矩阵function distData = initData()distData = [0 15 19 30 6 11 18 14 2415 0 34 44 14 23 29 4 3819 34 0 16 22 15 19 32 930 44 16 0 35 30 18 44 76 14 22 35 0 9 24 11 2811 23 15 30 9 0 24 20 2318 29 19 18 24 24 0 30 1514 4 32 44 11 20 30 0 3724 38 9 7 28 23 15 37 0];end
routeDistance()函数
计算解的路线长度
function routeDist = routeDistance(cityDist, route)% 根据城市间的距离计算总路径qty = max(size(route));sumDist = 0;for i = 1 : qty-1sumDist = sumDist + cityDist(route(i),route(i+1));endsumDist = sumDist + cityDist(route(qty),route(1));routeDist = sumDist;end
neighborBy2opt（）函数
两点邻域法产生xnow的邻域解集
function [routes, changePos] = neighborBy2opt( route )% 根据一条路径route，采用2opt方式产生其全部邻域解集cityQty = max(size(route));if cityQty <= 3disp('cityQty is too small in neighborBy2opt.....');endpos = 2 : cityQty;changePos = nchoosek(pos, 2);rows = size(changePos, 1);routes = zeros(rows, cityQty);% 依次对两个点进行位置互换，形成新的解for i = 1 : rowscity1 = route(changePos(i,1));city2 = route(changePos(i,2));midRoute = route;midRoute(changePos(i,1)) = city2;midRoute(changePos(i,2)) = city1;routes(i,:) = midRoute;endend
updataTabuTable（）函数
更新禁忌表里的对象和禁忌次数
function newTabuTable = updataTabuTable( tabuTable, tabuObj, tabuTimes )% 更新禁忌表oldRows = size(tabuTable,1);% 先排序if tabuObj(1) > tabuObj(2)midV = tabuObj(1);tabuObj(1) = tabuObj(2);tabuObj(2) = midV;endif oldRows == 0tabuTable = [tabuObj tabuTimes];else% 将以前禁忌表中的禁忌次数-1for i = 1 : oldRowstabuTable(i, 3) = tabuTable(i,3) - 1;end% 查看当前禁忌对象是否存在于原有禁忌表中isExist = 0;for i = 1 : oldRowsif tabuTable(i, 1) == tabuObj(1) && tabuTable(i, 2) == tabuObj(2)isExist = i;break;endendif isExist == 0midTabu = [tabuObj tabuTimes];tabuTable = [tabuTable; midTabu];elsetabuTable(isExist, 3) = tabuTimes;enda = tabuTable(:, 3) == 0;tabuTable(a, :) = [];% 删除禁忌次数为0的替换对endnewTabuTable = tabuTable;end
3. 实现结果
如果觉得《禁忌搜索算法求解TSP旅行商问题Matlab实现》对你有帮助，请点赞、收藏，并留下你的观点哦！
