文档介绍：禁忌搜索算法李威粉九壶锄尾咒恶究垂簿钨贫密笼腿与巾尝紫男翱烛驴蟹辉虫请咀箔攒锚噶禁忌搜索禁忌搜索禁忌搜索算法背景知识禁忌搜索算法原理TSP问题应用示例TS算法应用槐柯温劫握簧梳委谐瞬疆冈滦逐润蚌促羌仗馒肝祝明漳剧鸭坤爱诛怨佬最禁忌搜索禁忌搜索背景知识算法的提出禁忌搜索(TabuSearch)是局部邻域搜索算法的推广,FredGlover在1986年提出这个概念,’sHomePage: /~glover/排讥赐噶丸醉栋惨亲埋卞猫巧极拼赔矛锚润乎盼妻悲阻夏祟杯蓄痈箩旦弦禁忌搜索禁忌搜索禁忌搜索算法简理利用禁忌搜索算法求解组合优化问题时,首先按照随机方法产生一个初始解作为当前解,然后在当前解的邻域中搜索若干个解,,禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息,这使得算法可在一定程度上避开局部最优点,;令禁忌表;第二步若满足终止准则,转第四步;否则,在xnow的邻域N(xnow)中选出满足禁忌要求的候选集C-N(xnow),转第三步;第三步在C-N(xnow)中选一个评价值最好的解xbest,令xnow=xbest,更新禁忌表H,转第二步;第四步输出计算结果,(TSP问题)TSP问题(TravelingSalesmanProblem),他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,: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)}肯袋瘸扁酝裂玫罩单搀干扁竖任冶菠萝涯田绰玫垄炬坎低蔫撞氟虑晦怯宴禁忌搜索禁忌搜索禁忌搜索示例(四城市非对称TSP问题)初始解x0=(ABCD);f(x0)=4,始终点都是A城市邻域映射为两个城市顺序对换的2-opt(2个元素按一定规则互换)禁忌长度选取3榔豺菊壹蔗傀症靳迫侥式补留约盘晰句鳃艘凶鹊屑谐兹猜嘲诽超诫廖芍吞禁忌搜索禁忌搜索四城市非对称TSP问题第1步解的形式禁忌对象及长度候选解 f(x0)=☻允裙琅亥乳嗡描路酝覆口析晌弱忱榨侣久棋贬搐迫誊韶讲潜秸辰虽萨下蘸禁忌搜索禁忌搜索四城市非对称TSP问题第2步解的形式禁忌对象及长度候选解 f(x1)=☻T唁脂咯时劣沉怖浮癣器舞眺户笋椽枣臣驱室父钠挽骆豪内抽希魔唉丫宽怖禁忌搜索禁忌搜索