第2章 禁忌搜索算法

《第2章 禁忌搜索算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章禁忌搜索算法TabuSearch禁忌搜索算法òGlover在1986年提出ò是局部邻域搜索算法的推广ò所谓禁忌就是禁止重复前面的工作ò用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点ò是一种人工智能的算法2.1局部搜索假设算法解决如下组合最优化问题：minf(x)s.t.g(x)≥0，x∈D.其中f(x)为目标函数，g（x）为约束方程，D为定义域，是一个离散的点集合局部搜索算法•STEP1选定一个初始可行解：x0；记录当前最优解：xbest：=x0，令T=N(xbest).•STEP2当T{

2、xbest}=∅时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从T中选一集合S，得到S中的最好解xnow；若f(xnow)

3、止准则取决于人们对算法的计算时间、计算结果的要求局部搜索算法ò优点是简单易行，容易理解ò缺点是无法保证全局最优性ò计算结果主要依赖起点的选取和邻域的结构.为了得到好的解，可以比较不同的邻域结构和不同的初始点ò非常直观的结论是：如果初始点的选择足够多，总可以计算出全局最优解例2.1.15个城市的对称TSP距离矩阵例2.1.1•初始解为xbest=（ABCDE),f（xbest）=45•定义邻域映射为对换两个城市位置的2-opt•选A为起点•两种搜索：全领域搜索、一步随机搜索•解为（ACBDE)例2.1.2四城市非对称TSP•该算法终止时的解是局部最优解（ABCD)•全局最优

4、解是（ACDB）2.2禁忌搜索•是局部搜索算法的扩展•它的一个重要思想是标记已得到的局部最优解或求解的过程，并在进一步的迭代中避开这些局部最优解或过程．例2.2.1四城市非对称TSP距离矩阵例2.2.1•假设初始解x0=（ABCD),目标值为f(x0)=4•邻域映射为两个城市顺序对换的2-opt•始、终点都为A城市，所以候选集中最多有两两城市对换对3个•分别对换城市顺序并按目标值由小到大排列，三个评价值都劣于原值4．此时已达到局部最优解．例2.2.1第1步：解的形式禁忌对象及长度ABCDBCDA对换关系f(x0)=4B候选集N(x0)C对换评价值CD4.5*用★标记入选的

5、对换BC7.5目标值上升，但可BD8能跳出局部最优例2.2.1第2步：解的形式禁忌对象及长度ABDCBCDAf(x1)=4.5B候选集N(x1)C3对换评价值CD成为禁忌对象并限BC3.5*定在以下3次迭代中不BD4.5允许CD或DC对换，以CD4.5T避免计算中的循环例2.2.1第3步：解的形式禁忌对象及长度ACDBBCDAf(x2)=3.5B3上次候选集N(x2)C2再上次对换评价值BC4.5TBD7.5*CD8T例2.2.1第4步：解的形式禁忌对象及长度ACBDBCDAf(x3)=7.5B23上次候选集N(x3)C1对换评价值BD3.5TBC4.5T所有候选对换被禁

6、CD4.5T问题(1)选择什么为禁忌的对象？例2.2．1禁忌的是城市顺序对换，是否会造成求全局最优解的困难？(2)禁忌的长度如何选取？•禁忌长度短会造成循环，也就可能在一个局部最优解附近循环•禁忌长度长会造成算法的记忆存储量增加，使得算法计算时间增加，同时可能造成算法无法继续计算下去•因此，必须权衡这对矛盾，确定禁忌长度例2.2.2上例禁忌长度从3改为2第4步：解的形式禁忌对象及长度ACBDBCDAf(x3)=7.5B12上次候选集N(x3)C0对换评价值BD3.5T解禁BC4.5TCD4.5*例2.2.2第5步：解的形式禁忌对象及长度ADBCBCDAf(x4)=4.5B

7、01候选集N(x4)C2上次对换评价值解禁BD4.5T再迭代一步，又回CD7.5T到状态(ABCD)，BC8*此时出现循环问题(3)是否解禁一些状态以便跳出局部最优？解禁的功能就是为了获得更大的搜索范围，以免陷入局部最优(4)候选集合如何选取？为了节省每一步的计算时间，有可能只在邻域中随机选一些对换(5)是否有评价值的其他替代形式？问题(6)如何利用更多的信息？•通过记录其他一些信息，如当前最好解，一个被禁对象（交换）被禁的次数，评价值的大小等，来提高算法的效率•BC或CB出现的高频率反映出这对顺序交换对目标值影响较大，在现有