第二章禁忌搜索算法

第二章禁忌搜索算法智能优化计算华东理工大学自动化系2007年2.1局部搜索2.1.1邻域的概念2.1.2局部搜索算法2.1.3局部搜索示例2.2禁忌搜索2.2.1算法的主要思路2.2.2禁忌搜索示例2.3禁忌搜索的关键参数和操作2.3.1变化因素2.3.2禁忌表2.3.3其他2.4禁忌搜索的实现与应用2.4.130城市TSP问题（d*=423.741byDBFogel）2.4.2基于禁忌搜索算法的系统辨识智能优化计算华东理工大学自动化系2007年2.1局部搜索智能优化计算华东理工大学自动化系2007年函数优化问题中在距离空间中，通常的邻域定义是以一点为中心的一个球体；组合优化问题中2.1.1邻域的概念的一个邻居。称为的邻域，称为。的所有子集组成的集合表示其中，称为一个邻域映射，且xxNyxxNDxNxxNDxNDD)()(2)(,2)(:2.1局部搜索智能优化计算华东理工大学自动化系2007年例TSP问题解的一种表示方法为D={x=(i1,i2,…,in)|i1,i2,…,in是1,2,…,n的排列}，定义它的邻域映射为2－opt，即x中的两个元素进行对换，N(x)中共包含x的Cn2=n(n-1)/2个邻居和x本身。例如：x=(1,2,3,4)，则C42=6，N(x)={(1,2,3,4),(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)}2.1.1邻域的概念2.1局部搜索智能优化计算华东理工大学自动化系2007年例TSP问题解的邻域映射可由2－opt，推广到k－opt。邻域概念的重要性邻域的构造依赖于决策变量的表示，邻域的结构在现代优化算法中起重要的作用。2.1.1邻域的概念2.1局部搜索智能优化计算华东理工大学自动化系2007年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。2.1.2局部搜索算法2.1局部搜索智能优化计算华东理工大学自动化系2007年五个城市的对称TSP问题初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射为对换两个城市位置的2-opt，选定A城市为起点。2.1.3局部搜索示例2.1局部搜索智能优化计算华东理工大学自动化系2007年五个城市的对称TSP问题方法1：全邻域搜索第1步N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)}，对应目标函数为f(x)={45,43,45,60,60,59,44}xbest:=xnow=(ACBDE)2.1.3局部搜索示例ABCDE2.1局部搜索智能优化计算华东理工大学自动化系2007年五个城市的对称TSP问题方法1：全邻域搜索第2步N(xbest)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，对应目标函数为f(x)={43,45,44,59,59,58,43}xbest:=xnow=(ACBDE)2.1.3局部搜索示例2.1局部搜索智能优化计算华东理工大学自动化系2007年五个城市的对称TSP问题方法2：一步随机搜索第1步从N(xbest)中随机选一点，如xnow=(ACBDE)，对应目标函数为f(xnow)=4345xbest:=xnow=(ACBDE)2.1.3局部搜索示例2.1局部搜索智能优化计算华东理工大学自动化系2007年五个城市的对称TSP问题方法2：一步随机搜索第2步从N(xbest)中又随机选一点，如xnow=(ADBCE)，对应目标函数为f(xnow)=4443xbest:=xnow=(ACBDE)2.1.3局部搜索示例2.1局部搜索智能优化计算华东理工大学自动化系2007年五个城市的对称TSP问题简单易行，但无法保证全局最优性；局部搜索主要依赖起点的选取和邻域的结构；为了得到好的解，可以比较不同的邻域结构和不同的初始点；如果初始点的选择足够多，总可以计算出全局最优解。2.1.3局部搜索示例2.2禁忌搜索智能优化计算华东理工大学自动化系2007年算法的提出禁忌搜索（Tabusearch）是局部邻域搜索算法的推广，FredGlover在1986年提出这个概念，进而形成一套完整算法。算法的特点禁忌——禁止重复前面的工作。跳出局部最优点。2.2.1算法的主要思路~glover/2.2禁忌搜索智能优化计算华东理工大学自动化系2007年四城市非对称TSP问题初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市。2.2.2禁忌搜索示例2.2禁忌搜索智能优化计算华东理工大学自动化系2007年四城市非对称TSP问题第1步解的形式禁忌对象及长度候选解f(x0)=42.2.2禁忌搜索示例ABCDBCDABC对换评价值CD4.5BC7.5BD8☻2.2禁忌搜索智能优化计算华东理工大学自动化系2007年四城市非对称TSP问题第2步解的形式禁忌对象及长度候选解f(x1)=4.52.2.2禁忌搜索示例ABDCBCDABC3对换评价值CD4.5BC3.5BD4.5☻T2.2禁忌搜索智能优化计算华东理工大学自动化系2007年四城市非对称TSP问题第3步解的形式禁忌对象及长度候选解f(x2)=3.52.2.2禁忌搜索示例ACDBBCDAB3C2对换评价值CD8BC4.5BD7.5☻TT2.2禁忌搜索智能优化计算华东理工大学自动化系2007年四城市非对称TSP问题第4步解的形式禁忌对象及长度候选解f(x3)=7.5禁忌长度的选取2.2.2禁忌搜索示例ACBDBCDAB23C1对换评价值CD4.5BC4.5BD3.5TTT2.2禁忌搜索智能优化计算华东理工大学自动化系2007年四城市非对称TSP问题第4步（如果减小禁忌长度）解的形式禁忌对象及长度候选解f(x3)=7.52.2.2禁忌搜索示例ACBDBCDAB12C0对换评价值CD4.5BC4.5BD3.5☻TT2.2禁忌搜索智能优化计算华东理工大学自动化系2007年四城市非对称TSP问题第5步解的形式禁忌对象及长度候选解f(x4)=4.52.2.2禁忌搜索示例ADBCBCDAB01C2对换评价值CD7.5BC8BD4.5☻TT2.2禁忌搜索智能优化计算华东理工大学自动化系2007年四城市非对称TSP问题第6步解的形式禁忌对象及长度候选解f(x5)=82.2.2禁忌搜索示例ADCBBCDAB20C1对换评价值CD3.5BC4.5BD4☻TT2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌表的主要指标（两项指标）禁忌对象：禁忌表中被禁的那些变化元素禁忌长度：禁忌的步数状态变化（三种变化）解的简单变化解向量分量的变化目标值变化2.3.1变化因素2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年解的简单变化2.3.1变化因素个解。是从一个解变化到另一则简单解变化为优化问题的定义域，，其中，邻域映射为假设)(,xNyxDNDyx2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年向量分量的变化设原有的解向量为(x1,…,xi-1,xi,xi+1,…,xn)，向量分量的最基本变化为(x1,…,xi-1,xi,xi+1,…,xn)→(x1,…,xi-1,yi,xi+1,…,xn)即只有第i个分量发生变化。也包含多个分量变化的情形。2.3.1变化因素2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年目标值的变化目标值的变化隐含着解集合的变化。2.3.1变化因素2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌对象的选取情况1：禁忌对象为简单的解变化禁忌长度为4，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45，H={(ABCDE;45)}。2.3.2禁忌表2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌对象的选取情况1：禁忌对象为简单的解变化第1步——xnow=(ABCDE)，f(xnow)=45，H={(ABCDE;45)}Can_N(xnow)={(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表xnext=(ACBDE)2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌对象的选取情况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)}。2.3.2禁忌表xnext=(ACBED)2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌对象的选取情况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)}。2.3.2禁忌表xnext=(ABCED)2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌对象的选取情况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)}。2.3.2禁忌表xnext=(AECBD)2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌对象的选取情况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)}。2.3.2禁忌表xnext=(AEDBC)2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌对象的选取情况2：禁忌对象为分量变化禁忌长度为3，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。2.3.2禁忌表2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌对象的选取情况2：禁忌对象为分量变化第1步——xnow=(ABCDE)，f(xnow)=45，H=ΦCan_N(xnow)={(ACBDE;43)，(ADCBE;45)，(AECDB;60)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表xnext=(ACBDE)2.3禁忌搜索的关键参数和操作智能优化计算华东理工大学自动化系2007年禁忌对象的选取情况2：禁忌对象为分量变化第2步——xnow=(ACBDE)，f(xnow)=43，H={(B,C)}Can_N