7禁忌搜索算法

智能优化计算概览局部搜索禁忌搜索禁忌搜索关键参数和操作禁忌搜索实现和应用局部搜索邻域--定义--tsp示例--重要性局部搜索--操作步骤搜索示例--五城市对称tsp问题邻域①函数优化问题：邻域(N(x))通常定义为在给定距离空间内，以一点(x)为中心的一个球体②组合优化问题：且，称为一个邻域映射，其中表示X所有子集组成的集合。N(x)称为x的邻域，称为x的一个邻居。:()2XNxXNx()xNx2X()yNx邻域举两个简单的例子：定义邻域移动为：位值加1或减1对整数编码[22353]，判断一下下列编码是否在其邻域内：[23353][23253][22355][22343][22253][22344]邻域定义邻域移动为：2-Opt对顺序编码[42351]，判断一下下列编码是否在其邻域内：[43251][43512][43351][52341][12354][34251]邻域定义邻域移动为：2-Opt对顺序编码[42351]，判断一下下列编码是否在其邻域内：[43251][43512][43351][52341][12354][34251]邻域重要性：邻域的构造依赖于决策变量的表示，邻域的结构在现代优化算法中起重要的作用。局部搜索操作步骤：•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；重复STEP2。局部搜索示例五个城市的对称TSP问题初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射为对换两个城市位置的2-opt，选定A城市为起点。局部搜索示例方案一：全邻域搜索第1步N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)}，对应目标函数为f(x)={45,43,45,60,60,59,44}初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射为对换两个城市位置的2-opt，选定A城市为起点。第2步N(xbest)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，对应目标函数为f(x)={43,45,44,59,59,58,43}xbest:=xnow=(ACBDE)局部搜索示例方案二：一步随机搜索第1步从N(xbest)中随机选一点，如xnow=(ACBDE)，对应目标函数为f(xnow)=4345xbest:=xnow=(ACBDE)第2步从N(xbest)中又随机选一点，如xnow=(ADBCE)，对应目标函数为f(xnow)=4443xbest:=xnow=(ACBDE)对局部搜索的思考简单易行，但无法保证全局最优性；局部搜索主要依赖起点的选取和邻域的结构；为了得到好的解，可以比较不同的邻域结构和不同的初始点；如果初始点的选择足够多，总可以计算出全局最优解。禁忌搜索1.TS的提出人类在选择过程中局优记忆功能，比如走迷宫时，当发现有可能又回到某个地点的时候总会有意识地避开先前选择的方向而选择其他的可能性，这样就可以确定性的避开迂回搜索。借鉴人类的智能思考特性，采用禁忌策略尽量避免迂回搜索就构成了TS算法。Glover在1977年提出TS。相对于LS，TS的优点是能够通过接受劣解来逃离局优，在90年代初开始受到广泛的关注。禁忌搜索举例•四城市非对称TSP问题初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市。禁忌搜索举例•四城市非对称TSP问题第1步解的形式禁忌对象及长度候选解f(x0)=4ABCDBCDABC对换评价值CD4.5BC7.5BD8第2步解的形式禁忌对象及长度候选解f(x1)=4.5ABDCBCDABC3对换评价值CD4.5BC3.5BD4.5☻T第3步解的形式禁忌对象及长度候选解f(x2)=3.5ACDBBCDAB3C2对换评价值CD8BC4.5BD7.5☻TT四城市非对称TSP问题第4步解的形式禁忌对象及长度候选解f(x3)=7.5禁忌长度的选取ACBDBCDAB23C1对换评价值CD4.5BC4.5BD3.5TTT四城市非对称TSP问题第5步解的形式禁忌对象及长度候选解f(x4)=4.5ADBCBCDAB01C2对换评价值CD7.5BC8BD4.5☻TT四城市非对称TSP问题第6步解的形式禁忌对象及长度候选解f(x5)=8ADCBBCDAB20C1对换评价值CD3.5BC4.5BD4☻TT禁忌表的主要指标（两项指标）禁忌对象：禁忌表中被禁的那些变化元素禁忌长度：禁忌的步数状态变化（三种变化）解的简单变化解向量分量的变化目标值变化变化因素禁忌搜索的关键参数和操作解的简单变化变化因素,()xyDNDxyNxÎ假设，邻域映射为，其中为优化问题的定义域，.则简单解变化是从一个解变化到另一个解。向量分量的变化设原有的解向量为(x1,…,xi-1,xi,xi+1,…,xn)，向量分量的最基本变化为(x1,…,xi-1,xi,xi+1,…,xn)→(x1,…,xi-1,yi,xi+1,…,xn)即只有第i个分量发生变化。也包含多个分量变化的情形。变化因素目标值的变化目标值的变化隐含着解集合的变化。变化因素禁忌对象的选取情况1：禁忌对象为简单的解变化禁忌长度为4，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45，H={(ABCDE;45)}。禁忌表禁忌对象的选取情况1：禁忌对象为简单的解变化第1步——xnow=(ABCDE)，f(xnow)=45，H={(ABCDE;45)}Can_N(xnow)={(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。禁忌表xnext=(ACBDE)禁忌对象的选取情况1：禁忌对象为简单的解变化第2步——xnow=(ACBDE)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。禁忌表xnext=(ACBED)禁忌对象的选取情况1：禁忌对象为简单的解变化第3步——xnow=(ACBED)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)}Can_N(xnow)={(ACBED;43)，(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)}。禁忌表xnext=(ABCED)禁忌对象的选取情况1：禁忌对象为简单的解变化第4步——xnow=(ABCED)，f(xnow)=44，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)，(ABCED;44)}Can_N(xnow)={(ACBED;43)，(AECBD;44)，(ABCDE;45)，(ABCED;44)，(ABDEC;58)}。禁忌表xnext=(AECBD)禁忌对象的选取情况1：禁忌对象为简单的解变化第5步——xnow=(AECBD)，f(xnow)=44，H={(ACBDE;43)，(ACBED;43)，(ABCED;44)，(AECBD;44)}Can_N(xnow)={(AEDBC;43)，(ABCED;44)，(AECBD;44)，(AECDB;44)，(AEBCD;45)}。禁忌表xnext=(AEDBC)禁忌对象的选取情况2：禁忌对象为分量变化禁忌长度为3，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。禁忌表禁忌对象的选取情况2：禁忌对象为分量变化第1步——xnow=(ABCDE)，f(xnow)=45，H=ΦCan_N(xnow)={(ACBDE;43)，(ADCBE;45)，(AECDB;60)，(ABEDC;59)，(ABCED;44)}。禁忌表xnext=(ACBDE)禁忌对象的选取情况2：禁忌对象为分量变化第2步——xnow=(ACBDE)，f(xnow)=43，H={(B,C)}Can_N(xnow)={(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59)}。禁忌表xnext=(ACBED)禁忌对象的选取情况2：禁忌对象为分量变化第3步——xnow=(ACBED)，f(xnow)=43，H={(B,C)，(D,E)}Can_N(xnow)={(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)，(ACEBD;58)}。禁忌表xnext=(AEBCD)禁忌对象的选取情况3：禁忌对象为目标值变化禁忌长度为3，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。禁忌表禁忌对象的选取情况3：禁忌对象为目标值变化第1步——xnow=(ABCDE)，f(xnow)=45，H={45}Can_N(xnow)={(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。禁忌表xnext=(ACBDE)禁忌对象的选取情况3：禁忌对象为目标值变化第2步——xnow=(ACBDE)，f(xnow)=43，H={45，43}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。禁忌表xnext=(ADBCE)禁忌对象的选取解的简单变化比解的分量变化和目标值变化的受禁范围要小，可能造成计算时间的增加，但也给予了较大的搜索范围；解分量的变化和目标值变化的禁忌范围大，减少了计算时间，可能导致陷在局部最优点。禁忌表禁忌长度的选取（1）t可以为常数，易于实现；（2），t是可以变化的数，tmin和tmax是确定的。tmin和tmax根据问题的规模确定，t的大小主要依据实际问题、实验和设计者的经验。（3）tmin和tmax的动态选择。禁忌表],[maxminttt禁忌长度的选取禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。（例）禁忌表特赦（藐视）原则（1）基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；（2）基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；（3）基于影响力的规则，可以特赦对目标值影响大的对象。禁忌表候选集合的确定（1）从邻域中选择若干目标值最佳的邻居入选；（2）在邻域中的一部分邻居中选择若干目标值最佳的状态入选；（3）随机选取。其他评价函数（1）直接评价函数，通过目标函数的运算得到评价函数；（2）间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。其他记忆频率信息根据记忆的频率信息（禁忌次数等）来控制禁忌参数（禁忌长度等）。例如：如果一个元素或序列重复出现或目标值变化很小，可增加禁忌长度以避开循环；如果一个最佳目标值出现频率很高，则可以终止计算认为已达到最优值。其他记忆频率信息可记录的信息：（1）静态频率信息：解、对换或目标值在计算中出现的频率；（2）动态频率信息：从一个解、对换或目标值到另一个解、对换或目标值的变化趋势。其他终止规则（1）确定步数终止，无法保证解的效果，应记录当前最优解；（2）频率控制原则，当某一个解、目标值或元素序