本文采用改进的禁忌搜索算法求解TSP问题,该算法是通过禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,最终实现全局优化。实验结果证明该算法的可行性。
10 1
福
建
电
脑
2 1年第 9期 01
禁忌搜索求解 T P问题 S 肖驰 (韩山师范学院数学与信息技术系广东潮州 5 14 2 0 1)
【摘要】本文采用改进的禁忌搜索算法求解 T P问题,算法是通过禁忌准则来避免迂回搜索,: S该并通过藐视准则来赦免一些被禁忌的优良状态,最终实现全局优化。实验结果证明该算法的可行性。
【关键词】:禁忌搜索 0引言、
T P局部搜索 S
禁忌搜索的适应函数是对搜索的评价 .结合禁忌禁忌搜索是一种新的优化方法 .其框架灵活,用准则和藐视准则来选取新的当前状态。禁忌的目的则通性强,应用领域较广。T P是一类典型的组合优化问是为了尽量避免迂回搜索。禁忌长度就是即禁忌对象 S题。在交通运输、它电路板线路以及物流配送等领域都不允许被选取的最大次数。禁忌对象只有当其任期为它有广泛的应用。本文采用改进的禁忌搜索算法求解 0时才能被解禁禁忌长度与问题相关。可以是固定 T P问题。 S
值也可以是某种规律变化的在藐视准则的设置时 .法应避免遗失优良状态,算 激励对优良状态的局部邻域搜索 .实现全局优化的关
1禁忌搜索算法、
11法思想 .算禁忌搜索是对局部邻域搜索的一种扩展 .是一种键步骤。
全局逐步寻优算法,忌就是禁止重复前面的工作,禁有在禁忌搜索算法中 .视准则是将某些状态解禁。藐 效克服局部邻域搜索易陷入局部最优的不足。该算法以实现更高效的优化性能。禁忌对象上次被禁忌时使是通过引入一个灵活的存储结构和相应的禁忌准则来得适应函数有所改善 .并且当前该禁忌对象对应的候保证对不同的有效搜索途径的搜索 .并通过藐视准则选解的适应函数优于当前解,则对该禁忌对象解禁。该 来赦免一些被禁忌的优良状态,最终实现全局优化。 1 .域和候选解 2邻
准则保证有效的搜索禁忌搜索是动态搜索邻域的算法 .程图如下:流 给定初始解和算法参数
定义1:令 ( r为一个组合优化问题,其中D为决 D )
策变量的可行域,目标函数,决策变量为,一伪设则 个
邻域函数可定义为D上的一个映射。:即 M 2。其 中2表示 D的所有子集组成的集合。即对每个戈∈ D,
坼 J 2。称为∈Ⅳ )的邻域,∈ ) 坼称为的一个邻居。 定义2若V∈ , xⅣ均满足 J J则称, 。在 DI的局部极小解; V D, - _若∈均满足’删, 则称 为为 D上的全局最小解。
产生的邻域解,确定候选解
邻域结构的设计通常与问题有关。它影响了当前解的邻域解的产生形式和数目.以及各个解之间的关
将非禁忌最佳解作为当前解 新禁鼹斋
图 1禁忌算法系。搜索质量和效率有较大的影响。对 候选解通常在当前状态的邻域中择优选取,但选 2禁忌算法求解 T P、 S取过多将造成较大的计算量 .而选取较小则容易早熟, P是一个易于描述问题却难以大规模处理的 N I ' S P收敛。了节省时间 .法要有选择性取少量的优良解问题 T P问题定义如下:为算 S
来改善算法的时间效率。 1 .始解、应函数、忌准则和藐视准则 3初适禁
T P=CC o c}个城市的集合, S设c f, '是 l o
禁忌搜索对初始解有较强的依赖性 .好的初始解厂—————1——————— 可以使禁忌搜索在解空间中搜索到好的解,而较差的 d=,…,是z J, 2的距离, 、 ( ) (_ )。即d=/ + 初始解则会降低禁忌搜索的收敛速度。在求解某个具体问题时 .如何选择高质量的初始解来提高算法搜索的质量和效率是很重要的
L{ Ic c是集合C= c j 1 i∈,中城市两两相连的集合, P一条对 C{p c}个城市访问且只访问是= CC…,中儿 一
次的最短封闭曲线。 P 是一个组合最优化问题,即

如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入阅读会员!获取下载券 一种求解TSP问题的改进禁忌搜索算法 禁忌...
禁忌搜索解决TSP_数学_自然科学_专业资料。禁忌搜索解决 TSP 的 Matlab 程序 ... 第4章_禁忌搜索 41页 1下载券 一种适用于求解TSP问题的... 3页 免费...
改进禁忌搜索算法在 TSP 问题中的应用 摘要:提出了一种基于改进最近邻点法的禁忌搜索算法(TSBIN)。 该算法利用改进最近邻点法为禁忌搜索算法构造较优初始解 ,能...
ComputerEngineeringandApplications 计算机工程与应用 2008,44(1) 57 一种适用于求解 TSP 问题的改进的禁忌算法武 妍, 周欣 WUYan,ZHOUXin同济大学 计算机科学与...
禁忌搜索算法求TSP问题_理学_高等教育_教育专区。用禁忌搜索算法(TS)求解旅行商问题(TSP问题)例 从北京(Pe)乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(...
改进禁忌搜索算法在TSP问题中的应用_数学_自然科学_专业资料。Q Q:墼 SCIENCE... 禁忌搜索求解TSP问题 166人阅读 2页 1.00 一种改进的禁忌搜索算法... ...
总第1 5卷16 5期 201 3年 5月 大众科技 Popular Science&Technology VOl_15 N0.5 May 2013 禁忌搜索算法及其在 TS P问题 中的应用研 究 程林辉 ( 中南...
禁忌搜索算法的研究及其在TSP的应用_工学_高等教育_教育专区。禁忌搜索算法解决TSP问题禁忌搜索算法的研究及其在TSP的应用徐丽1 陈丽1 宋遥2(1.河北政法职业学院...
求解大规模TSP问题的混合算法_IT/计算机_专业资料。遗传算法求解大规模TSP时呈现出求解时间长、后期效率明显降低等缺陷。通过结合分块方法、局部搜索算法以及禁忌算法...
解:禁忌搜索算法解 TSP 问题的程序如下: function main() %禁忌搜索算法解TSP问题 %A为禁忌表,此题中设置为一个禁忌队列,长度为t %t:禁忌表的长度 %x:一...
热门文档