欢迎来到天天文库
浏览记录
ID:42134914
大小:736.00 KB
页数:52页
时间:2019-09-08
《现代优化算法 禁忌算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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
此文档下载收益归作者所有