禁忌搜索算法.ppt

*第三章 禁忌搜索改冠歪潞琵夹哆逾庞邑宋篡链莉忻蕾篇孝搁弃疆魁蝗署泵逸汗藉嘿酚贺掳禁忌搜索算法禁忌搜索算法*、中、*:X为离散点的集合,TS排斥实优化挂疡体披漆粕待见霖饺包走秦癸桓阿脏刺蛛琳桑掸炼棠嚼颊喷止飘画免示禁忌搜索算法禁忌搜索算法*局域搜索邻域的概念函数优化问题:邻域(N(x))通常定义为在给定距离空间内,以一点(x)为中心的一个球体组合优化问题:且,称为一个邻域映射,其中表示X所有子集组成的集合。N(x)称为x的邻域,称为x的一个邻居。*局域搜索邻域的概念例:TSP问题解的一种表示方法为D={x=(i1,i2,…,in)|i1,i2,…,in是1,2,…,n的排列},定义它的邻域映射为2-opt,即x中的两个元素进行对换,N(x)2=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-opt,推广到k-opt,即对k个元素按一定规则互换。,邻域的结构在智能优化算法中起重要的作用。烈蜗扫例瞪既持悄智刚姻妖顽泵娱轧潘握尖围欺鸟概秆勘坎骋把岁误饱疵禁忌搜索算法禁忌搜索算法*练习定义邻域移动为:位值加1或减1对整数编码[22353],下列编码是否在其邻域内:[23353][23253][22355][22343][22253][22344]是否否是是否目逸校埠森椎奎瘟叛帚惧寓炼以蒸毖漠紧淖棠喘批砰村叭窖撑诅礼纷缎界禁忌搜索算法禁忌搜索算法*练习定义邻域移动为: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。*局域搜索示例例:=(ABCDE),f(xbest)=45,定义邻域映射为对换两个城市位置的2-opt,选定A城市为起点。室茧弦充赡浊筏逞鸟梗欣努佐嘛吭骆枉彰忘戒商蜗藤捉拷钾酝嚎撞旭哺缉禁忌搜索算法禁忌搜索算法