禁忌搜索算法有关介绍与举例

禁忌搜索算法首先先介绍一下局部搜索的概念，函数优化问题中，在距离空间中，通常的邻域定义是以一点为中心的一个球体。即例如X=[0,1,0,0,1,0,0]，令u=1，d=[0,0,1,0,0,0,0]，可以得到X的一个邻域移动X+ud=[0,1,1,0,1,0,0]TSP问题解的一种表示方法为D={x=(i1,i2,…,in)|i1,i2,…,in是1,2,…,n的排列}，定义它的邻域映射为2－opt，即x中的两个元素进行对换，N(x)中共包含x的Cn2=n(n-1)/2个邻居和x本身。另外TSP问题解的邻域映射可由2－opt，推广到k－opt。邻域的构造依赖于决策变量的表示，邻域的结构在现代优化算法中起重要的作用。下面介绍局部搜索算法的步骤：Step1：选定一个初始可行解x0，记录当前最优解xbest:=x0,T=N(xbest)Step2：当T\{xbest}=Φ时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从T中选一集合S，得到S中的最好解xnow；若f(xnow)f(xbest)，则xbest:=xnow，T=N(xbest)；否则T:=T\S；重复SETP2。局部搜索具有的特点简单易行，但无法保证全局最优性；局部搜索主要依赖起点的选取和邻域ud,xsxudSxssxudsXSx邻域的概念：的邻域移动为，为步长，为方向，则：邻域是邻域移动可达到的解的集合。的结构；为了得到好的解，可以比较不同的邻域结构和不同的初始点；如果初始点的选择足够多，总可以计算出全局最优解。禁忌搜索算法禁忌搜索（Tabusearch）是局部邻域搜索算法的推广，FredGlover在1986年提出这个概念，进而形成一套完整算法。其特点为使用禁忌表封锁刚搜索过的区域,禁止重复前面的工作。跳出局部最优点，也可避免陷入死循环。赦免禁忌区域中的一些优良状态，以保证搜索的多样性。编码方法属于灵活的选择编码方法，如背包的0-1编码。同一问题有多种编码方法，如分组问题：不相同的n件物品分为m组，n=9，m=3.编码1：1-3-4-0-2-6-7-5-0-8-9（1-4-3-0-6-2-5-7-0-9-8）0起到隔开作用1-3-4分为一组，2-6-7-5一组，8-9一组。编码2：1-2-1-1-2-2-2-3-3（2-1-2-2-1-1-1-3-3）表示1-3-4分为一组，2-6-7-5一组，8-9一组在适值函数的构造中，适值函数是用来对搜索状态进行评价的。对目标函数的任何变形都可作为目标函数，只要该变形保持严格单调。其外我们可以随机给出初始解，也可以是其它启发式算法给出的较好的初始解。禁忌搜索算法主要是基于邻域搜索的，所以初始解对算法搜索性能影响很大。对于较为复杂的约束问题，随机产生的初始解可能是不可行解，应该采用一些启发式方法找到一个可行解作为初始解。移动是产生新解的途径，从当前解可以进行的所有的移动构成邻域，因此移动规则的设计是算法的关键。移动规则类似于交叉算子，根据具体问题进行分析设计，如排序问题中采用两两交换方式的移动规则。有关禁忌表的概念：禁忌表记录前若干步走过的点、方向或目标值，禁止返回;是为了防止搜索过程出现循环而陷入局部最优的，是禁忌搜索算法的核心;表是动态更新的——把最新的解记入，最老的解从表中释放(解禁)。禁忌对象：放入禁忌表的元素，主要包括三种，（1）以状态本身或状态变化为禁忌对象，其禁忌范围适中；（2）以状态分量或状态分量的变化作为禁忌对象，其禁忌范围较小；（3）以目标值为禁忌对象，其禁忌范围较大。禁忌长度：禁忌表的大小。禁忌表越小，计算时间和存储空间越少，但禁忌表过小，会造成搜索过程进入循环。表长越大分散性越好。禁忌长度分为固定禁忌长度和随时间变化禁忌长度两类。根据所选的初始解，我们需要制定相应的选择策略。选择策略是从邻域中选择一个较好解作为下一次迭代初始解的方法。候选解集的确定是选择策略的关键，对算法性能影响很大。候选解集为整个邻域。选择策略是从整个邻域内选择一个最优解为下一次迭代的初始解，计算时间较长。候选解集为邻域的真子集。这种选择策略只扫描邻域的一部分构成候选解集，虽不能找到邻域内最优解，但减少了搜索时间。在有些特定的条件下，不管某个移动是否在禁忌表中，都接受这个移动并更新当前解和历史最优解。这个特定的条件即为渴望水平。渴望水平的设定有如下几种形式：（1）基于适配值的准则，如果某个候选解的适配值高于历史最优解，无论是否处于禁忌表中，都选择接受。（2）基于搜索方向的准则，某禁忌对象进入紧急表时改善了适配值，而这次这个被禁忌的候选解由改善了适配值，故破禁。（3）基于影响力的准则，有的禁忌对象对适配值的影响较大，解禁会对解有较大影响，解禁时要考虑。（4）其它准则.禁忌搜索的停止准则与GA相似，给定最大迭代次数得到满意解，设定某对象的最大禁忌频率。禁忌搜索算法实现步骤：Step1：选定一个初始解xnow;令禁忌表T=Φ;Step2：若满足终止准则,转第四步;否则,在xnow的邻域N(xnow)中选出满足禁忌要求的候选集C-N(xnow),转第三步;Step3：在C-N(xnow)中选一个评价值最好的解xbest,令xnow=xbest,更新禁忌表T,转第二步;Step4：输出计算结果,停止.禁忌搜索示例四城市非对称TSP问题初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市。第1步解的形式禁忌对象及长度候选解第2步解的形式禁忌对象及长度候选解如此重复到第六步，得到第6步解的形式禁忌对象及长度候选解其中解的形式分别为：f(x0)=4，f(x1)=4.5，f(x2)=3.5，f(x3)=7.5，f(x4)=4.5，f(x5)=8从禁忌长度为2的迭代与禁忌长度为3的迭代比较可得：禁忌长度短会造成循环，也就可能在一个局部最优解的附近循环（步6，产生ABCD循环到步1）（极限状况下，禁忌长度为1：造成一直在一个局部最优解处循环，退化为局部搜索算法）（此处由于城市个数只有4个，除去起点A，BCD排列一共才6种，所以看上去好像循环会产生的足够晚，会比禁忌长度更长的方案产生更多的候选局部最优解。但如果城市个数是20呢？禁忌长度为1，是否会在第5,6步就产生循环呢？相对而言禁忌长度为(19-1)*(19)/2的方案，会迭代(19-1)*(19)/2步，产生更多候选局部最优解）。禁忌长度长会造成，算法的记忆存储量增加，使得算法的计算时间增加（譬如，上述例子，20个城市的TSP，从头禁到尾，一定要跑(19-1)*(19)/2步，但是禁忌长度短，或许早就出现循环，解收敛了）。代码附录：#includetsp.husingnamespacestd;boolcmp(inta,intb){returnab;}boolcountMin(constvectorvectorint&v,vectorint&x,vectorvectorint&tabutable,constint&num){intxtemp;intytemp;intmin=INT_MAX;for(inti=1;inum-1;i++){for(intj=i+1;jnum;j++){swap(x[i],x[j]);inttemp=countDis(x,v);if(tempmin&&tabutable[x[i]][x[j]]==0&&tabutable[x[j]][x[i]]==0){min=temp;xtemp=i;ytemp=j;}swap(x[i],x[j]);}}if(min==INT_MAX){returnfalse;}else{swap(x[xtemp],x[ytemp]);tabutable[x[xtemp]][x[ytemp]]=1;tabutable[x[ytemp]][x[xtemp]]=1;returntrue;}}voidtabusearchN(constvectorvectorint&v,vectorint&x,int&costbest,intfirstcity){swap(x[0],x[firstcity]);intnum=x.size();//城市节点个数vectorvectorinttabutable;//禁忌表，tabutable[i][j]=z表示对换对(i,j)的禁忌长度为zvectorintf;//记录每一个局部最优解initX(tabutable,num);for(inti=0;inum;i++)//初始化禁忌长度为0{for(intj=i+1;jnum;j++){tabutable[x[i]][x[j]]=0;tabutable[x[j]][x[i]]=0;}}f.push_back(countDis(x,v));while(countMin(v,x,tabutable,num)){f.push_back(countDis(x,v));}sort(f.begin(),f.end(),cmp);costbest=f[0];}