欢迎来到海神之光博客之家✅博主简介热爱科研的Matlab仿真开发者修心和技术同步精进个人主页海神之光代码获取方式海神之光Matlab王者学习之路—代码获取方式⛳️座右铭行百里者半于九十。更多Matlab路径规划仿真内容点击①Matlab路径规划进阶版②付费专栏Matlab路径规划初级版⛳️关注CSDN海神之光更多资源等你来⛄一、TSP简介旅行商问题即TSP问题Traveling Salesman Problem又译为旅行推销员问题、货郎担问题是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市他必须选择所要走的路径路径的限制是每个城市只能拜访一次而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP的数学模型⛄二、禁忌搜索算法简介1 引言一个问题的求解过程就是搜索它是人工智能的一个基本问题而人工智能在各应用领域中被广泛地使用。现在搜索技术渗透在各种人工智能系统中可以说没有哪一种人工智能的应用不用搜索方法。禁忌搜索算法(Tabu Search or Taboo Search TS) 的思想最早由美国工程院院士Glover教授于1986年提出[] 并在1989年和1990年对该方法做出了进一步的定义和发展[2-4]。在自然计算的研究领域中禁忌搜索算法以其灵活的存储结构和相应的禁忌准则来避免迂回搜索在智能算法中独树一帜成为一个研究热点受到了国内外学者的广泛关注。迄今为止禁忌搜索算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功近年来又在函数全局优化方面得到较多的研究并有迅速发展的趋势[5-8].所谓禁忌就是禁止重复前面的操作。为了改进局部邻域搜索容易陷入局部最优点的不足禁忌搜索算法引入一个禁忌表记录下已经搜索过的局部最优点在下一次搜索中对禁忌表中的信息不再搜索或有选择地搜索以此来跳出局部最优点从而最终实现全局优化。禁忌搜索算法是对局部邻域搜索的一种扩展是一种全局邻域搜索、逐步寻优的算法。禁忌搜索算法是一种迭代搜索算法它区别于其他现代启发式算法的显著特点是利用记忆来引导算法的搜索过程它是对人类智力过程的一种模拟是人工智能的一种体现。禁忌搜索算法涉及邻域、禁忌表、禁忌长度、候选解、藐视准则等概念在邻域搜索的基础上通过禁忌准则来避免重复搜索并通过藐视准则来赦免一些被禁忌的优良状态进而保证多样化的有效搜索来最终实现全局优化。2禁忌搜索算法理论2.1局部邻域搜索局部邻域搜索是基于贪婪准则持续地在当前的邻域中进行搜索虽然其算法通用易于实现且容易理解但其搜索性能完全依赖于邻域结构和初始解尤其容易陷入局部极小值而无法保证全局优化。局部搜索的算法可以描述为这种邻域搜索方法易于理解易于实现而且具有很好的通用性但是搜索结果的好坏完全依赖于初始解和邻域的结构。若邻域结构设置不当或初始解选择不合适则搜索结果会很差可能只会搜索到局部最优解即算法在搜索过程中容易陷入局部极小值。因此若不在搜索策略上进行改进要实现全局优化局部邻域搜索算法采用的邻域函数就必须是“完全”的即邻域函数将导致解的完全枚举。而这在大多数情况下是无法实现的而且穷举的方法对于大规模问题在搜索时间上也是不允许的。为了实现全局搜索禁忌搜索采用允许接受劣质解的策略来避免局部最优解。2.2禁忌搜索禁忌搜索算法是模拟人的思维的一种智能搜索算法即人们对已搜索的地方不会再立即去搜索而是去对其他地方进行搜索若没有找到可再搜索已去过的地方。禁忌搜索算法从一个初始可行解出发选择一系列的特定搜索方向(或称为“移动”)作为试探选择使目标函数值减小最多的移动。为了避免陷入局部最优解禁忌搜索中采用了一种灵活的“记忆”技术即对已经进行的优化过程进行记录指导下一步的搜索方向这就是禁忌表的建立。禁忌表中保存了最近若干次迭代过程中所实现的移动凡是处于禁忌表中的移动在当前迭代过程中是禁忌进行的这样可以避免算法重新访问在最近若干次迭代过程中已经访问过的解从而防止了循环帮助算法摆脱局部最优解。另外为了尽可能不错过产生最优解的“移动”禁忌搜索还采用“特赦准则”的策略。对一个初始解在一种邻域范围内对其进行一系列变化从而得到许多候选解。从这些候选解中选出最优候选解将候选解对应的目标值与“best so far”状态进行比较。若其目标值优于“best sofar”状态 就将该候选解解禁 用来替代当前最优解及其“best sofar”状态 然后将其加入禁忌表 再将禁忌表中相应对象的禁忌长度改变如果所有的候选解中所对应的目标值都不存在优于“best sofar”状态 就从这些候选解中选出不属于禁忌对象的最佳状态 并将其作为新的当前解不用与当前最优解进行比较直接将其所对应的对象作为禁忌对象并将禁忌表中相应对象的禁忌长度进行修改。2.3禁忌搜索算法的特点禁忌搜索算法是在邻域搜索的基础上通过设置禁忌表来禁忌一些已经进行过的操作并利用藐视准则来奖励一些优良状态其中邻域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。邻域函数沿用局部邻域搜索的思想用于实现邻域搜索禁忌表和禁忌对象的设置体现了算法避免迂回搜索的特点藐视准则则是对优良状态的奖励它是对禁忌策略的一种放松。与传统的优化算法相比禁忌搜索算法的主要特点是(1)禁忌搜索算法的新解不是在当前解的邻域中随机产生它要么是优于“best so far”的解 要么是非禁忌的最佳解 因此选取优良解的概率远远大于其他劣质解的概率。(2)由于禁忌搜索算法具有灵活的记忆功能和藐视准则并且在搜索过程中可以接受劣质解所以具有较强的“爬山”能力搜索时能够跳出局部最优解转向解空间的其他区域从而增大获得更好的全局最优解的概率。因此禁忌搜索算法是一种局部搜索能力很强的全局迭代寻优算法。2.4禁忌搜索算法的改进方向禁忌搜索是著名的启发式搜索算法但是禁忌搜索也有明显的不足即在以下方面需要改进(1)对初始解有较强的依赖性好的初始解可使禁忌搜索算法在解空间中搜索到好的解而较差的初始解则会降低禁忌搜索的收敛速度。因此可以与遗传算法、模拟退火算法等优化算法结合先产生较好的初始解再用禁忌搜索算法进行搜索优化。(2)迭代搜索过程是串行的仅是单一状态的移动而非并行搜索。为了进一步改善禁忌搜索的性能一方面可以对禁忌搜索算法本身的操作和参数选取进行改进对算法的初始化、参数设置等方面实施并行策略得到各种不同类型的并行禁忌搜索算法[9]另一方面则可以与遗传算法、神经网络算法以及基于问题信息的局部搜索相结合。(3)在集中性与多样性搜索并重的情况下多样性不足。集中性搜索策略用于加强对当前搜索的优良解的邻域做进一步更为充分的搜索以期找到全局最优解。多样性搜索策略则用于拓宽搜索区域尤其是未知区域当搜索陷入局部最优时多样性搜索可改变搜索方向跳出局部最优从而实现全局最优。增加多样性策略的简单处理手段是对算法的重新随机初始化或者根据频率信息对一些已知对象进行惩罚。3 禁忌搜索算法流程简单禁忌搜索算法的基本思想是给定一个当前解(初始解)和一种邻域然后在当前解的邻域中确定若干候选解若最佳候选解对应的目标值优于“best so far”状态 则忽视其禁忌特性 用它替代当前解和“best so far”状态 并将相应的对象加入禁忌表 同时修改禁忌表中各对象的任期若不存在上述候选解则在候选解中选择非禁忌的最佳状态为新的当前解而无视它与当前解的优劣同时将相应的对象加入禁忌表并修改禁忌表中各对象的任期。如此重复上述迭代搜索过程直至满足停止准则。其算法步骤可描述如下(1)给定禁忌搜索算法参数随机产生初始解x置禁忌表为空。(2)判断算法终止条件是否满足若是则结束算法并输出优化结果否则继续以下步骤。(3)利用当前解的邻域函数产生其所有(或若干)邻域解并从中确定若干候选解。(4)对候选解判断藐视准则是否满足若满足则用满足藐视准则的最佳状态y替代x成为新的当前解即xy并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象 同时用y替换“best so far”状态然后转步骤(6)否则继续以下步骤。(5)判断候选解对应的各对象的禁忌属性选择候选解集中非禁忌对象对应的最佳状态为新的当前解同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。(6)判断算法终止条件是否满足若是则结束算法并输出优化结果否则转步骤(3)。禁忌搜索算法的运算流程如图8.1所示。4 关键参数说明一般而言要设计一个禁忌搜索算法需要确定算法的以下环节初始解、适配值函数、邻域结构、禁忌对象、候选解选择、禁忌表、禁忌长度、藐视准则、搜索策略、终止准则[1011]。面对如此众多的参数针对不同邻域的具体问题很难有一套比较完善的或非常严格的步骤来确定这些参数。初始解禁忌搜索算法可以随机给出初始解也可以事先使用其他启发式算法等给出一个较好的初始解。由于禁忌搜索算法主要是基于邻域搜索的初始解的好坏对搜索的性能影响很大。尤其是一些带有很复杂约束的优化问题如果随机给出的初始解很差甚至通过多步搜索也很难找到一个可行解这时应该针对特定的复杂约束采用启发式方法或其他方法找出一个可行解作为初始解再用禁忌搜索算法求解以提高搜索的质量和效率。也可以采用一定的策略来降低禁忌搜索对初始解的敏感性。适配值函数禁忌搜索的适配值函数用于对搜索进行评价进而结合禁忌准则和特赦准则来选取新的当前状态。目标函数值和它的任何变形都可以作为适配值函数。若目标函数的计算比较困难或耗时较长此时可采用反映问题目标的某些特征值来作为适配值进而改善算法的时间性能。选取何种特征值要视具体问题而定但必须保证特征值的最佳性与目标函数的最优性一致。适配值函数的选择主要考虑提高算法的效率、便于搜索的进行等因素。邻域结构所谓邻域结构是指从一个解(当前解)通过“移动”产生另一个解(新解)的途径它是保证搜索产生优良解和影响算法搜索速度的重要因素之一。邻域结构的设计通常与问题相关。邻域结构的设计方法很多对不同的问题应采用不同的设计方法常用设计方法包括互换、插值、逆序等。不同的“移动”方式将导致邻域解个数及其变化情况的不同对搜索质量和效率有一定影响。通过移动目标函数值将产生变化移动前后的目标函数值之差称之为移动值。如果移动值是非负的则称此移动为改进移动否则称之为非改进移动。最好的移动不一定是改进移动也可能是非改进移动这一点能保证在搜索陷入局部最优时禁忌搜索算法能自动把它跳出局部最优。禁忌对象所谓禁忌对象就是被置入禁忌表中的那些变化元素。禁忌的目的则是为了尽量避免迂回搜索而多搜索一些解空间中的其他地方。归纳而言禁忌对象通常可选取状态本身或状态分量等。候选解选择候选解通常在当前状态的邻域中择优选取若选取过多将造成较大的计算量而选取较少则容易“早熟”收敛但要做到整个邻域的择优往往需要大量的计算因此可以确定性地或随机性地在部分邻域中选取候选解具体数据大小则可视问题特征和对算法的要求而定。禁忌表不允许恢复(即被禁止) 的性质称作禁忌(Tabu) 。禁忌表的主要目的是阻止搜索过程中出现循环和避免陷入局部最优它通常记录前若干次的移动禁止这些移动在近期内返回。在迭代固定次数后禁忌表释放这些移动重新参加运算因此它是一个循环表每迭代一次就将最近的一次移动放在禁忌表的末端而它的最早的一个移动就从禁忌表中释放出来。从数据结构上讲禁忌表是具有一定长度的先进先出的队列。禁忌搜索算法使用禁忌表禁止搜索曾经访问过的解从而禁止搜索中的局部循环。禁忌表可以使用两种记忆方式明晰记忆和属性记忆。明晰记忆是指禁忌表中的元素是一个完整的解消耗较多的内存和时间属性记忆是指禁忌表中的元素记录当前解移动的信息如当前解移动的方向等。禁忌长度所谓禁忌长度是指禁忌对象在不考虑特赦准则的情况下不允许被选取的最大次数。通俗地讲禁忌长度可视为禁忌对象在禁忌表中的任期。禁忌对象只有当其任期为0时才能被解禁。在算法的设计和构造过程中一般要求计算量和存储量尽量小这就要求禁忌长度尽量小。但是禁忌长度过小将造成搜索的循环。禁忌长度的选取与问题特征相关它在很大程度上决定了算法的计算复杂性。一方面禁忌长度可以是一个固定常数(如tcc为一常数)或者固定为与问题规模相关的一个量(如t√nn为问题维数或规模)如此实现起来方便、简单也很有效另一方面禁忌长度也可以是动态变化的如根据搜索性能和问题特征设定禁忌长度的变化区间而禁忌长度则可按某种规则或公式在这个区间内变化。藐视准则在禁忌搜索算法中可能会出现候选解全部被禁忌或者存在一个优于“best so far”状态的禁忌候选解 此时特赦准则将某些状态解禁以实现更高效的优化性能。特赦准则的常用方式有(1) 基于适配值的原则某个禁忌候选解的适配值优于“bestso far”状态 则解禁此候选解为当前状态和新的“best so far”状态。(2)基于搜索方向的准则若禁忌对象上次被禁忌时使得适配值有所改善并且目前该禁忌对象对应的候选解的适配值优于当前解则对该禁忌对象解禁。搜索策略搜索策略分为集中性搜索策略和多样性搜索策略。集中性搜索策略用于加强对优良解的邻域的进一步搜索。其简单的处理手段可以是在一定步数的迭代后基于最佳状态重新进行初始化并对其邻域进行再次搜索。在大多数情况下重新初始化后的邻域空间与上一次的邻域空间是不一样的当然也就有一部分邻域空间可能是重叠的。多样性搜索策略则用于拓宽搜索区域尤其是未知区域。其简单的处理手段可以是对算法的重新随机初始化或者根据频率信息对一些已知对象进行惩罚。终止准则禁忌搜索算法需要一个终止准则来结束算法的搜索进程而严格理论意义上的收敛条件即在禁忌长度充分大的条件下实现状态空间的遍历这显然是不可能实现的。因此在实际设计算法时通常采用近似的收敛准则。常用的方法有(1)给定最大迭代步数。当禁忌搜索算法运行到指定的迭代步数之后则终止搜索。(2)设定某个对象的最大禁忌频率。若某个状态、适配值或对换等对象的禁忌频率超过某一阈值或最佳适配值连续若干步保持不变则终止算法。(3)设定适配值的偏离阈值。首先估计问题的下界一旦算法中最佳适配值与下界的偏离值小于某规定阈值则终止搜索。⛄三、案例及部分源代码1 案例旅行商问题(TSP问题)。假设有一个旅行商人要拜访全国31个省会城市,他需要选择所要走的路径,路径的限制是每个城市只能拜访一次而且最后要回到原来出发的城市。路径的选择要求是所选路径的路程为所有路径之中的最小值。2 部分源代码%%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%clear all;%清除所有变量 close all;%清图 clc;%清屏 C[13042312;36391315;41772244;37121399;34881535;33261556;...32381229;41961044;4312790;4386570;30071970;25621756;...27881491;23811676;1332695;37151678;39182179;40612370;...37802212;36762578;40292838;42632931;34291908;35072376;...33942643;34393201;29353240;31403550;25452357;27782826;...23702975];%31个省会城市坐标 Nsize(C,1);%TSP问题的规模,即城市数目 Dzeros(N);%任意两个城市距离间隔矩阵%%%%%%%%%%%%%%%%%%%%%求任意两个城市距离间隔矩阵%%%%%%%%%%%%%%%%%%%%%fori1:Nforj1:ND(i,j)((C(i,1)-C(j,1))^2...(C(i,2)-C(j,2))^2)^0.5;end end Tabuzeros(N);%禁忌表 TabuLround((N*(N-1)/2)^0.5);%禁忌长度 Ca200;%候选集的个数(全部领域解个数)CaNumzeros(Ca,N);%候选解集合 S0randperm(N);%随机产生初始解 bestsofarS0;%当前最佳解 BestLInf;%当前最佳解距离figure(1);p1;Gmax1000;%最大迭代次数%%%%%%%%%%%%%%%%%%%%%%%%%%%禁忌搜索循环%%%%%%%%%%%%%%%%%%%%%%%%%%whilepGmaxALong(p)func1(D,S0);%当前解适配值%%%%%%%%%%%%%%%%%%%%%%%%%%%交换城市%%%%%%%%%%%%%%%%%%%%%%%%%%i1;Azeros(Ca,2);%解中交换的城市矩阵%%%%%%%%%%%%%%%%%求领域解中交换的城市矩阵%%%%%%%%%%%%%%%%%%%%%whileiCa MN*rand(1,2);Mceil(M);ifM(1)~M(2)A(i,1)max(M(1),M(2));A(i,2)min(M(1),M(2));ifi1isa0;elseforj1:i-1ifA(i,1)A(j,1)A(i,2)A(j,2)isa1;break;elseisa0;end end endif~isa ii1;elseendelseend end%%%%%%%%%%%%%%%%%%%%%%%%%产生领域解%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%保留前BestCaNum个最好候选解%%%%%%%%%%%%%%%%%%%BestCaNumCa/2;BestCaInf*ones(BestCaNum,4);Fzeros(1,Ca);fori1:CaCaNum(i,:)S0;CaNum(i,[A(i,2),A(i,1)])S0([A(i,1),A(i,2)]);F(i)func1(D,CaNum(i,:));ifiBestCaNumBestCa(i,2)F(i);BestCa(i,1)i;BestCa(i,3)S0(A(i,1));BestCa(i,4)S0(A(i,2));elseforj1:BestCaNumifF(i)BestCa(j,2)BestCa(j,2)F(i);BestCa(j,1)i;BestCa(j,3)S0(A(i,1));BestCa(j,4)S0(A(i,2));break;end end end end⛄四、运行结果⛄五、matlab版本及参考文献1 matlab版本2014a2 参考文献[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例第2版[M].电子工业出版社2016.[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社2017. 仿真咨询1 各类智能优化算法改进及应用生产调度、经济调度、装配线调度、充电优化、车间调度、发车优化、水库调度、三维装箱、物流选址、货位优化、公交排班优化、充电桩布局优化、车间布局优化、集装箱船配载优化、水泵组合优化、解医疗资源分配优化、设施布局优化、可视域基站和无人机选址优化2 机器学习和深度学习方面卷积神经网络CNN、LSTM、支持向量机SVM、最小二乘支持向量机LSSVM、极限学习机ELM、核极限学习机KELM、BP、RBF、宽度学习、DBN、RF、RBF、DELM、XGBOOST、TCN实现风电预测、光伏预测、电池寿命预测、辐射源识别、交通流预测、负荷预测、股价预测、PM2.5浓度预测、电池健康状态预测、水体光学参数反演、NLOS信号识别、地铁停车精准预测、变压器故障诊断3 图像处理方面图像识别、图像分割、图像检测、图像隐藏、图像配准、图像拼接、图像融合、图像增强、图像压缩感知4 路径规划方面旅行商问题TSP、车辆路径问题VRP、MVRP、CVRP、VRPTW等、无人机三维路径规划、无人机协同、无人机编队、机器人路径规划、栅格地图路径规划、多式联运运输问题、车辆协同无人机路径规划、天线线性阵列分布优化、车间布局优化5 无人机应用方面无人机路径规划、无人机控制、无人机编队、无人机协同、无人机任务分配6 无线传感器定位及布局方面传感器部署优化、通信协议优化、路由优化、目标定位优化、Dv-Hop定位优化、Leach协议优化、WSN覆盖优化、组播优化、RSSI定位优化7 信号处理方面信号识别、信号加密、信号去噪、信号增强、雷达信号处理、信号水印嵌入提取、肌电信号、脑电信号、信号配时优化8 电力系统方面微电网优化、无功优化、配电网重构、储能配置9 元胞自动机方面交通流 人群疏散 病毒扩散 晶体生长10 雷达方面卡尔曼滤波跟踪、航迹关联、航迹融合