现代优化算法 禁忌算法

《现代优化算法 禁忌算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、现代优化算法ChapterⅡ禁忌搜索算法南昌航空大学WSN小组张海利1主要内容局部搜索禁忌搜索技术问题应用案例——图节点着色22.1局部搜索此章，出特别强调，我们假设算法解决如下组合最优化问题：minf（x）s.tg（x）≥0，x∈D，其中f（x）为目标函数，g（x）为约束方程，D为定义域，是一个离散的点集合。3STEP1:选定一个初始可行解：x0；记录当前最优解：xbest：=x0，T=N(xbest).STEP2:当T｛xbest｝=ø时，或满足其它停止运算准则时，输出计算结果，停止运算；否则，从T中选一集合S，得到S中的最好解Xnow；若f（Xnow）＜f（xbest），则x

2、best：=Xnow，T=N（xbest）；否则，T：=TS；重复STEP2。局部搜索算法4例2.1.1五个城市的对称TSP数据及其对应矩阵如图5初始解为xbest=（ABCDE）f(xbest)=45.本例定义邻域映射为对换两个城市位置的2-opt。选定A城市为起点，我们用两种情况解释局部搜索算法。6即S:=N(xbest).第一循环：N(xbest)={(ABCDE)(ACBDE)(ADCBE)(AECDB)(ABDCE)(ABEDC)(ABCED)}对应的目标函数值为f（x）=｛45，43，45，60，60，59，44｝xbest:=xnow=(ACBDE).情况1：全邻域搜

3、索7第二循环：N(xbest)=｛(ACBDE),(ABCDE)(ADBCE)(AEBDC)(ACDBE)(ACBED)｝，对应的目标函数值为f(x)={43，45，44，59，59，58，43}xbest:=xnow=(ACBDE)此时，N(xbest)S为空集，于是所得解为(ACBDE)，目标值为43.8这个方法的主要实质是910情况2：一步随机搜索xbest=(ABCDE),f(xbest)=45第一循环：由于采用N(xbest)中的一部随机搜索，可以不再计算N(xbest)中每一点的值。若从中随机选一点，如xnow=(ACBDE).因f(xnow)=43＜45，所以xbes

4、t:=(ACBDE).11第二循环：若从N(xbest)中又随机选一点xnow=(ADBCE),f(xnow)=44＞43.N(xbest)=N(xbest)｛xnow｝.最后得到的解为(ACBDE).12这种随机一部搜索的方法其实就是随机选举一个对象，计算目标函数值然后跟初始函数值比较，如果优于初始解，则改变最优值，进一步随机选举对象将其目标函数值与之比较。如果未优化，则上一部得出的就是最优解。13例2.1.2四城市非对称TSP及其距离矩阵如图若初始解为xbest=(ABCD),并且假设城市A为起始点，f(xbest)=4.四城市TSP14邻域N(xbest)={(ABCD),(

5、ACBD),(ADCB),(ABDC)}中，局部最优解是(ABCD).而全局最优解xbest=(ACDB),f(xbest)=3.5.15Summary局部搜索算法的计算结果主要依赖起点的选取和邻域的结构。（同一个起点，不同的邻域结构会得到不同的计算结果。同样，同一个邻域结构，不同的初始点会的到不同的计算结果）因此，在使用局部搜索算法时，为了得到好的解，可以比较不同的邻域结构和不同的初始点。一个非常直观的结论是：如果初始点的选择足够多，总可以计算出全局最优解。162.2禁忌搜索禁忌搜索是一种人工智能算法，是局部搜索算法的扩展．它的一个重要思想是标记已得到的局部最优解，并在进一步的迭代

6、中避开这些局部最优解．如何避开和记忆这些点是本章主要讨论的问题．首先，用一个示例来理解禁忌搜索算法．17例2.2.1（2.1.2续）假设初始解x0=(ABCD)，邻域映射为两个城市顺序对换的2-opt，始、终点都是A城市。目标值为f（x0）=4.城市间的距离为依据局部搜索的思想，在给定一个解后，下一步从其邻域中获得一个新的解，解的变化是由城市顺序的调换造成的，因此，关注这个变化过程。18第1步解的形式禁忌对象及长度候选集19第2部解的形式禁忌对象及长度候选集20第3步解的形式禁忌对象及长度候选集21第4步解的形式禁忌对象及长度候选集22例2.2.2若例2.2.1中禁忌长度从3更改为2

7、，在当前3步与例2.2.1相同的情况下，有下列情形第4步解的形式禁忌对象及长度候选集23第5步解的形式禁忌对象及长度候选集如果再迭代一步，那么又回到了状态(ABCD)24禁忌搜索算法STEP1给出禁忌表（tabulist）H=ø并选定一个初始解xnow；STEP2满足停止规则时，停止计算，输出结果；否则，在xnow的邻域N(xnow)中选出满足不受禁忌的候选集Can_N(xnow)；在Can_N(xnow)中选一个评价值最佳的解xnext，xnow：=xn