第!"卷第#期西南师范大学学报（自然科学版）!$$!年%月
&’()!"*’)#+’,-./(’01’,234562738./*’-9/(:.8;5-682
文章编号：>$$$?@">（!$$!）$#$#@>$?
禁忌搜索算法求解旅行商问题研究
贺
!
一>，，刘光远>
!
>A西南师范大学电子与信息工程系，重庆@$$">?；!A重庆师范学院现代信息管理系，重庆@$$$@"
摘要：设计了一种基于B/2(/C实现的禁忌搜索算法，用以求解组合优化难题中的典型代表旅行商问题（D1E）)分别对F’G085(H原始>$城市和中国旅行商问题进行了测试，所得结果都能达到或优于公布的最优解，与传统的F’G085(H神经网络求解D1E相比，禁忌搜索算法具有强健、快速和高效的特点)关
键
词：禁忌搜索算法；旅行商问题；F’G085(H神经网络
文献标识码：%
中图分类号：!"#$
旅行商问题（D1E）是一类有代表性的已被证明具有*E7计算复杂性的组合难题，它的提法是：给定*
个城市，有一旅行商从某一城市出发，访问各城市一次且仅有一次后回到原出发城市，要求找出一条最短的巡回路径)该问题等价于!个点的圆排列，其路径数为（*I>）！J!)若按穷举法求解，即使用每秒运
［>］
算一亿次的巨型机对只有!$个城市的D1E求解，也需搜索#?$年之久)由于D1E代表一类组合优化问题，在实际工程中有许多应用，如电子地图、交通诱导、&K1L单元布局、MDB分组交换网等)因此，利用各种先进算法（如1M和NM）对D1E类似的问题进行求解就成为一个值得关注的问题)事实上，只要能找到能用于实际问题的“亚优解”（1,COPG289/(1’(,28’.）即可)禁忌搜索算法在这一领域中已显示出强大的优越性，正日益受到重视，它所得到的亚优解往往优于传统算法得到的局部极值解，加之搜索效率高，已受到广泛欢迎)本文针对D1E问题的特点，设计了禁忌搜索算法的一种有效实现形式，实验表明，这一方法具有良好的收敛性和较高的搜索效率)
#禁忌搜索算法简介
［!］
禁忌搜索（D/C,15/-=3，简称D1）技术是一种亚启发式搜索技术，由N(’;5-在>QR%年首次提出，进而
［#，@］
形成一套完整算法)所谓禁忌就是禁止重复前面的工作)为了回避局部邻域搜索陷入局部最优的主要
不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次的搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点)就好比人的短时记忆，走过的路不再重复或有选择地重复；同时“遗忘”又使得这些禁止是弱禁止，即在一定的时间之后这些禁止将失效，最终达到全局优化之目的)
［?］
该算法可简单地表示为：
选定一个初始解TO.’4及给以禁忌表"U!；
（F，中选出满足禁忌要求的1DSE!若满足终止规则，则终止计算；否则，在TO.’4的邻域*TO.’4）
候选集7/.O*（TO.’4）；在7/.O*（TO.’4）中选一个评价值最佳的解TO.5V2，TO.’4WUTO.5V2；更新历史记录
1DSE>
收稿日期：!$$>>>$%
作者简介：贺一（>Q"$I），男，四川达县人，讲师，硕士研究生，主要从事神经网络研究)
基金项目：重庆市应用基础研究项目（>QQ"I?""?）；教育部《高等学校骨干教师资助计划》项目（NNI?!$I>$%#?I!R$"）)
!
/0&西南师范大学学报（自然科学版）第&:卷
!，重复"#$%&’
禁忌对象、禁忌长度、邻域结构、评价函数和候选集的确定是禁忌搜索算法设计的核心，此外还包括
［(］
特赦规则和终止规则的确定’
!禁忌搜索算法用于求解"#$
本文提出的禁忌搜索算法如下：
（)）解的领域映射为&*+,-，即固定起点城市，后面的每两个城市进行对换，邻域中的元素个数为!&".)；
（&）目标函数定义为巡回路径的城市间距离之和，目标函数亦作为评价函数；（/）禁忌对象定义为目标函数所求得的目标值；（0）禁忌长度（-123*4567-8）随具体问题而定；
（9）从邻域中选最佳的-123*4567-8.)个元素作为候选集；
（(）为提高解的质量，防止出现循环，应用了特赦规则’本文的特赦规则定义为：当当前最优解未下
降的次数超过给定值时，则特赦禁忌表中的最优解，将其作为下一次迭代的初始解；
（:）终止规则为：程序运行超过给定最大迭代步数，或特赦次数超过给定最大特赦次数；
（;）为增强搜索空间的多样性，本文应用了多初始点策略，即分别以每一个城市作为初始点进行搜索’实验表明，能以较大概率达到最优解或亚优解’
%计算机模拟结果
例)
!+,?#16@)A城市各城市的坐标值来自文献［:］，具体如下：
B)C（AD0AAA，AD00/E）B/C（AD):A:，AD&&E/）B9C（AD9):)，ADE0)0）B:C（AD(;:;，AD9&)E）BEC（AD((;/，AD&9/(）
B&C（AD&0/E，AD)0(/）B0C（AD&&E/，AD:()A）B(C（AD;:/&，AD(9/(）B;C（AD;0;;，AD/(AE）B)AC（AD()9E，AD&(&/）
基于传统!+,?#16@方法的神经网络求得的最好解是&D;E’文献［:］中提出的改进的神经网络新方法求得的“最优解”是&D:&’本文的禁忌搜索算法求得的最优解为&D(EA&（表)），好于已知的最优解’获优概率为;AF’
表ӝ)
初始点)&/09(:;E)A
&D::E0&D:(EA&D(EA&&D(EA&&D(EA&&D(EA&&D(EA&&D(EA&&D(EA&&D(EA&巡回距离
)&/09(:;E)A
&))9(:;E)A&
禁忌搜索算法求得的结果
城/00(:;E)A&/
099:;E)A&/)市9((;E)A&/)0
序(::E)A&/)09
:;;)A&/)09(列;EE&/)09(:
E)A)A/)09(:;
)A/&)09(:;E
#85G5H34-H2I#123"51JK8L47+J=-8M
典型的寻优过程见图)，最优巡回路径见图&’
例&
中国旅行商问题（B*#"%）（城市间距离见文献［;］）’
自从文献［;］提出B*#"%组合优化问题，即我国/)个省、市、自治区首府间的距离表和归一化距离表后，国内外学者对该问题进行了大量的研究工作’由于该问题属于中大规模的组合优化问题，因此，都
期贺一，等：禁忌搜索算法求解旅行商问题研究
地以出，中索显质市
9::西南师范大学学报（自然科学版）表!!"#$%&
中国旅行商问题计算结果’()*+,",-(."$/%0+$,01(2’3!45
城
6:&6;=66>6=6=&&=&=&99
8&9:8:8966==>:866:6=6=&&8&7&79696&8&8&:&9&:&:76;:78
6;6>;;6&7=66&&[1**********]86:6:6>67686=&&>969696969&9&:&9&96;788:87:6
9=9=>;;&6&6666&>;[1**********]:6:6>6>6=6=&&>9696&7&7&89&9&:76;::8:66=6==>
>;>;6&666768&6969676&66686:6:6>6>6=6=&&>9696&7&7&8&8&:&:&9&>6;6;:8:8776=>>;>;;9
&676&66&[1**********]86:&696>6=6=&&>9696&7&7&8&8&:&:&9&96;6;::8876=6==>;996
[1**********]86&6>6:6>6>6=6768&&>9696&7&7&8&8&9&:&9&96;6;::887766=>;>;;96
市666&686:6:6>6:6=6=&&&&=&=9&>9696&7&7&8&8&:&9&:&:76;::887766==>>;96
序
列
6=&&6&&96&7&7&8&8&:&:&9&96;6;::8:66=6==>>;;996
&6&&&&&=&=9&>9696&=9>;>;;9966>6=6>6=6=6:
&=9&>9696&7&7&8&>96&:&9&96;6;::887766==>;9966:6>6>6=6=&6;
&>9696&7&7&8&8&:&:&9&76;::887766==>>;;966=&
&7&7&8&8&:&:&9&96;6;6>;;9966&6967&[1**********]86:6:6>6>6=6=&&8&>&8&8&7
6>6:6>6=6=&&>9696&7&7&8&8&:&:&9&96;788:87766==>>;;996
第卷
起点最短路径6&9:87;>=66=&&=9
67689677>768;:=68;:=68;9&68:::68:;>679>7677679>>
&8&:&:&9&96;6;&96;;99666&66&686:6768686:6:6>6>6=6=&&7&7&7&>&=
76;6966=&96&896&>9
参考文献：
［6］靳
蕃?神经计算智能基础原理・方法［@］?成都：西南交通大学出版社，&
［&］A$(B%2C?C+,+2%*",D01(2-.,%E%2*2(E2"))-.E".F$-.G0,("2,-1-H-"$-.,%$$-E%.H%［I］?!"#$%&’()*+,#&’)%-"*(.&(&)’/0，6=>7，69：
899J8:=?
［9］A$(B%2C?!"#+4%"2HD：*"2,K［I］?,.123"$’*)4"*!"5#$%-*6，6=>=，6：6=］靳［=］杨
潮，宣国荣?人工神经网络求解!45问题新方法［I］（:）：8=J78??计算机应用与软件，&蕃，范俊波，谭永东?神经网络与神经计算机原理・应用［@］?成都：西南交通大学出版社，6==6?忠，鲍
明，赵淳生?人机结合求解中国旅行商问题［I］（:）：9;&J9;7??模式识别与人工智能，6==8，6>
［6
［66］潘立登，黄晓峰?用改进的遗传算法求解中国旅行商问题［I］（6）：7&J77??北京化工大学学报，6==;，&:［6&］孙惠文?遗传算法求解旅行商问题［I］（8）：88
第R期贺一，等：禁忌搜索算法求解旅行商问题研究R14
!"#"$%&’()*(+,-)./*0-)/$12*"$%&’3+.(%-4’5
!"
&
，’()*+,-./0+,-%#$%，
%!"#$%!&’()#*%+&,-*.,/0,’&+1.%-&,(,2-,##+-,2，3&4%56#7%85-,.，9&+1.):,-;#+7-%.,.2#1#,%，85&,2=-,29&+1.):,-;#+7-%
31#4%$&4：5,6789-:,;?2，,;,=+67,@AB,
（HIJ）；!9EF$7
责任编辑
潘春燕
禁忌搜索算法求解旅行商问题研究
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
贺一， 刘光远
贺一(西南师范大学电子与信息工程系,重庆,400715;重庆师范学院现代信息管理系,重庆,400047)， 刘光远(西南师范大学电子与信息工程系,重庆,400715)西南师范大学学报(自然科学版)
JOURNAL OF SOUTHWEST CHINA NORMAL UNIVERSITY2002，27(3)15次
参考文献(13条)
1.靳蕃 神经网络计算基础-原理和方法 2000
2.GLOVER F Future paths for integer programming and links to artificial intelligence 19863.GLOVER F Tabu Search: part I 19894.GLOVER F Tabu Search: part II 19905.刑文训.谢金鑫 现代优化计算方法 19996.GLOVER F.Laguna M Tabu Search 1997
7.王潮.宣国荣 人工神经网络求解TSP问题新方法[期刊论文]-计算机应用与软件 2001(04)8.靳蕃.范俊波.谭永东 神经网络与神经计算机--原理、应用 19919.杨忠.鲍明.赵淳生 人机结合求解中国旅行商问题 1995(04)
10.周培德 求解货郎担问题的几何算法[期刊论文]-北京理工大学学报 1995(01)11.潘立登.黄晓峰 用改进的遗传算法求解中国旅行商问题 1997(01)12.孙惠文 遗传算法求解旅行商问题 1996(05)
13.罗映红 遗传算法求解组合优化问题研究[期刊论文]-甘肃科学学报 1997(02)
相似文献(10条)
1.学位论文 李大卫 GA与TS混合策略的理论与应用研究 1998
该文通过对遗传算法和禁忌搜索算法的分析与比较,提出了一种遗传算法与禁忌搜索算法的混合策略,在重组过程中引入禁忌搜索算法的记忆功能,并把禁忌搜索作为变异算子.应用马尔科夫链理论对混合策略进行了数学描述,证明了混合策略是全局收敛的,并有针对性的选择出八个典型的测试函数对混合策略进行性能测试,并与标准遗传算法进行比较.对自然数编码的遗传算法的最优群体规划的最优变异率两个基本参数进行研究,得到了最优群体规模存在性定理,获得了最优群体规模的一个下限值,给出了最优变异率的存在性定理,这些结果可用于指导应用遗传算法求解实际问题.该文对热轧钢管的生产批量问题进行了系统的分析和研究,首次从切割的角度研究热轧钢管的生产批量计划问题,在分析钢管生产工艺基础上,建立了钢管生产批量计划问题的数学模型,并应用遗传算法进行求解.提出了两阶段可重复自然数编码方法和两阶段独立交叉和变异的遗传算子.
2.期刊论文 张芬莉.姜秀山.孙艳丰 混合遗传算法在旅行商问题中的应用 -西安工业学院学报2004,24(2)
为了更优地解决旅行商问题,改进单纯用遗传算法求解旅行商问题的结果,本文通过遗传算法和禁忌搜索算法自身的特点,分别对二者的优势和不足进行分析,提出一种将二者混合使用的求解旅行商问题的算法.该算法以遗传算法为基础,用遗传算法作全局搜索,用禁忌搜索算法作局部搜索.同时,通过计算实例分析,将这种混合遗传算法用于旅行商问题的求解中.试验表明,混合遗传算法比较单纯的遗传算法的计算结果有一定的改进.
3.学位论文 江新姿 蚁群算法与其他算法的混合 2008
自从上世纪50年代中期创立仿生学以来，人们不断地从生物进化的机理中得到启发，提出了许多用于解决复杂优化问题的新方法，比如神经网络、遗传算法、模拟退火算法、进化规划等，并成功应用于解决实际问题。由意大利学者M.Dorigo，Vmaniezzo，A.Colorni于1992年首先提出的蚁群系统(Ant ColonySystem，ACS)，是一种新颖的仿生进化算法，适用于求解复杂组合优化问题。目前，蚁群系统己成功应用于求解旅行商问题(TSP)、二次分配问题和job-shop调度问题等，取得了很好的实验效果。受其影响，蚁群系统的研究已经逐渐引起了更多学者和专家的关注。虽然，该研究方法处于研究的初级阶段，但是一些研究成果已经显示出蚁群系统在求解复杂优化问题方面的优越性。作为一种全局搜索的方法，蚁群算法具有正反馈性、并行性、分布性、自组织性等特点。但是，蚁群算法也存在一些不足之处:例如，算法需要较长的搜索时间、容易出现早熟停滞现象等。
针对上述不足，我们在深入研究蚁群算法的同时，又对免疫算法和禁忌搜索等算法进行了一定的分析和研究，提出了几种新的用于求解旅行商问题(TSP)的蚁群改进算法。旨在借鉴其他仿生算法的长处，利用其优点弥补蚁群算法的不足，从而提高蚁群算法的求解性能。
本文的主要内容包括：首先，针对蚁群算法中的个体蚂蚁缺乏识别问题特征信息的能力，将免疫算法中疫苗的思想引入到蚁群算法中，新算法从TSP问题本身出发，提取出该 问题的一种本质特征，将此特征信息作为疫苗注射给精英蚂蚁，使其具有“免疫”的能力，能识别该固有特征，以提高精英蚂蚁的搜索质量，从而使得整体的求解能力得以提高。其次，因为蚁群算法容易出现早熟停滞，而禁忌搜索算法可以接受劣解，搜索时能跳出局部最优解，转向解空间的其他解，从而获得更好的全局最优解。故将两种算法混合，用蚁群算法作全局搜索，禁忌搜索算法作局部搜索。从而加速收敛速度，使算法的搜索性能得以提高。最后，根据蚁群算法与遗传算法、模拟退火算法的特性，提出了采用遗传算法生成信息素分布，利用蚁群算法求精确解的遗传蚁群混合算法，以及采用模拟退火算法生成信息素分布，在蚁群算法寻优中采用模拟退火的在领域内找另外一个解的策略的模拟退火蚁群算法。并用新算法解决旅行商问题，得到更有效的解。将上述几种改进算法应用于旅行商问题，进行仿真试验，检验改进算法的相关性能。 实验结果均表明，这几种改进的蚁群算法较之基本蚁群算法，在寻优能力上均有了较大的提高。
4.学位论文 李黎 基于ILOG组件的线路优化平台的设计和实现 2006
线路优化问题应用广泛，涉及到很多行业，譬如在国防领域中，军事物流共同配送线路的优化，在某种意义上可提高军事物资的配送效率；民用方
面的邮电、旅游业，大多都牵涉线路制定问题。虽然目前关于不同约束条件下的基本线路优化模型理论研究已经有很多年的历史，但是理论和实际应用技术问题之间仍然存在着鸿沟。本文通过探讨线路规划技术，并力求将其应用于解决实际问题。
本文对线路优化问题考虑因素分类，总结出六类通用的应用问题模型，即最短路优化问题、旅行商问题、VRP(VehicleRoutingProblem)模型、VRPTW(VehicleRoutingProblemWithTimeWindow)、DVRP(DynamicVehicleRoutingProblem)模型、多发车点模型。对问题本身进行了理论研究，并建立问题的约束规划模型，对该模型的解、约束的性质进行了深入讨论，设计并实现了解决问题的蚁群算法和禁忌搜索算法的流程；并改进蚁群算法、确定了参数选取的原则，使得蚁群算法收敛速度快，提高运行效率。
基于模型的理论分析，利用ILOG优化和视图组件建立了优化算法模块引擎和视图显示系统的线路优化平台，本文大概简要介绍ILOG优化组件类库解决线路优化的技术思路，对部分使用的类进行说明，同时扩展改进蚁群算法到ILOG算法库。并以旅行商问题模型验证算法的效果，实验结果表明算法是十分有效的。
线路优化平台采用了组件技术，相对简化了平台的设计，并保证了平台的易于扩展的功能。
本课题结合两个应用实例——军事配送线路和旅游线路优化，根据线路的特点，总结了类线路优化模型，并使用线路优化平台得出了军事配送线路的示范效果图。
最后，本文进行总结和展望，指出进一步完善的工作。
5.期刊论文 刘于江.喻泽峰.LIU Yu-jiang.YU Ze-feng 一种求解旅行商问题的禁忌搜索算法 -江西理工大学学报2006,27(4)
提出了一种求解旅行商问题的禁忌搜索算法,并对几个实例进行了计算机模拟.实验结果表明,在求解中小规模的旅行商问题上,该算法具有良好的性能.
6.学位论文 杨博 禁忌搜索算法在冷藏供应链配送网络中的应用研究 2005
历史长河中，人类努力的基本目标大多是获得生存的食物。至二十一世纪，随着科技进步，人们的食物在得到了稳定的供应的保证后，开始把美味和营养速冻起来。跨入二十一世纪，发展食品冷藏供应链，保护食品资源，将是我国食品产业可持续发展战略。
冷藏供应链是一种特殊的供应链，它需要特殊的温度控制来保证产品质量。配送环节是产品品质保证最困难的环节，温度、湿度的控制均处于相当不利的状况，从供应链角度看，绝大部分货损常常出现在这一环节。
本文从优化冷藏供应链配送网络的角度来解决上面提到的问题。由于冷藏供应链与传统供应链的不同，作者选用了一种不依赖于具体问题的直接搜索法-禁忌搜索(TS)。
TS是由F.Glover提出来的。其基本思想是从某一初始状态(初始解)出发，对其邻域进行搜索，在禁忌表的控制下，确定移动的方向，直至得到满意解为止。它具有计算速度快、能够跳出局部最优、可解大型问题的能力。因此，TS算法自产生以来，以其自身特有的优势立足于许多研究领域。目前它已被成功应用于调度问题、旅行商问题、工作流程排序问题、通讯线路分配问题、神经网络识别问题、图形着色问题、二次指派问题等。
本文应用TS来解决冷链网络优化问题，充分考虑到冷链的特殊性，建立了质量和成本模型。并将禁忌搜索算法得到的结果与其他算法得到的优化结果进行了比较。实例表明用TS算法求解搜索到了其它算法未能得到的最优解。
7.期刊论文 张洪艳 一种改进的多初始解禁忌搜索算法 -科技信息（学术版）2008,""(34)
本文根据禁忌搜索算法的特点,提出了一种基于多初始解的禁忌搜索算法(STS).该算法为禁忌搜索算法构造多个较优初始解,进而进行多初始解禁忌搜索以找到全局最优解.以旅行商问题(TSP)为例,验证了该算法的有效性.
8.学位论文 荚恒松 蚁群算法及其应用研究——基于旅行商问题和图像分类 2008
蚁群算法是MarcoDorigo等学者在真实蚂蚁觅食行为的启发下提出的一种具有高度创新性的元启发式搜索算法。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后提出的又一种应用于解决组合优化问题的启发式搜索算法。试验表明，蚁群算法具有较好的求解能力，但是蚁群算法存在收敛速度慢，容易陷入局部最优解等不足。本文主要研究如何改进算法模型并应用于相关领域，主要工作包括以下两部分。
首先，对蚁群算法进行基础理论研究，改进并提出分类蚁群算法(CBACO)，将其应用于TSP问题。旨在对蚁群算法近年来的研究进展进行总结，归纳算法的成功和存在的不足，对不足之处进行理论分析并改进，目的在于提高蚁群算法的总体性能。改进后的模型在智能蚁群的基础上引入随机蚁群以便扩大搜索空间，不同蚁群实行各自不同的搜索前进策略和信息更新机制，从而避免算法陷入早熟，以获取更大的解空间。并可通过调节随机蚁群与智能蚁群的比例来控制收敛速度，从而提高算法的运行效率。试验表明，将其应用于TSP问题可以获取更好的求解性能。
其次，针对基本蚁群算法分类图像速度慢的缺点，根据蚁群算法的聚类和离散性特点，改进蚁群算法并应用于图像分类。随机蚂蚁在图像中识别类、构建类别表，并确定聚类中心、生成相应类的智能蚂蚁，指导智能蚂蚁分类的过程；智能蚂蚁按相应的搜索前进策略向聚类中心聚集，识别目标。同时所有的蚂蚁在搜索前进过程中对图像进行边缘提取，以便提高算法对图像边缘分类的准确度。试验表明，相比基本蚁群算法求解图像分类问题，由于该改进引入初始聚类中心和识别边缘，算法的分类效率和对边缘信息点分类的准确度得到提高，并实现了图像的自动分类。
9.期刊论文 江新姿.高尚.JIANG Xin-zi.GAO Shang 改进的蚁群禁忌搜索混合算法 -科学技术与工程2010,10(14)
蚁群算法作为一种全局搜索的方法,具有正反馈性、并行性、分布性、自组织性等特点,在求解复杂组合优化问题上具有强大的优势.但是,蚁群算法也存在一些不足之处:例如,算法需要较长的搜索时间、容易出现早熟停滞现象.为了更优地解决旅行商问题,改进单纯用蚁群算法求解旅行商问题的结果,通过蚁群算法、免疫算法和禁忌搜索算法自身的特点,分别对三者的优势和不足进行分析,提出一种将三者混合使用的求解旅行商问题的算法.
10.学位论文 郭娜 基于节约算法和移动方向的禁忌搜索算法 2009
随着优化算法和启发式算法的提出，国内外掀起了研究智能优化算法的热潮。禁忌搜索是一种新的智能优化算法，是由美国科学家Glovr教授于1986年正式提出。禁忌搜索(TS)在智能算法中独树一帜，成为一个研究热点，受到了国内外学者的广泛关注，并应用到组合优化和函数优化问题中。本文基于原禁忌搜索的思想提出一种改进的禁忌搜索算法，并把这种改进算法应用到实际问题中。
在前期工作的基础上，本文主要的工作包括针对禁忌搜索算法对初始解依赖性强的缺点，利用c-w节约算法得到初始解。禁忌搜索算法设计的框架中初始解尤为关键，初始解的好坏制约着搜索的收敛速度。通过c-w节约算法得到高质量解，构造算法新的搜索起点，加强了集中性搜索力度。在仿真实验中验证了其有效性。
同时针对禁忌搜索算法中集中性与多样性搜索并重的情况下，多样性不足的缺点，从下面两个方面改进算法，拓宽搜索领域，加强多样性搜索，增加灵活性。通过改进禁忌表存储结构，定义优质解和劣质解的出现次数这两个概念，不只利用禁忌表禁忌最近的搜索，还记录这些移动是否有所改进，记录下改进的信息，表明新解的改变程度，在搜索决策中并入这些信息，使得搜索往利于改进的方向进行。T S中确定性的搜索过程制约了它的灵活性，所以在禁忌搜索原则确定的基础上，根据搜索中的移动信息，增加概率性因素，在评价函数中增加一个概率函数，把确定性选择过程变为概率性的，从而改进搜索方向，拓宽搜索领域，使得更好的解有更大的被选中的机会。
旅行商问题(TSP)是典型的组合优化难题，但由于TSP有着广泛的实际应用工程背景，有效地解决TSP问题一直受到人们的重视，已有多种方法成功求解TSP问题。根据本文改进的禁忌搜索算法提出一种解决TSP问题有效形式。
引证文献(14条)
1.李雪梅.张素琴 基于仿生理论的几种优化算法综述[期刊论文]-计算机应用研究 2009(6)2.任晔.顾彬.李玉凯 物流系统优化问题研究方法概述[期刊论文]-物流科技 2009(5)
3.陈榕.陈振林.李洪周 基于禁忌BP神经网络的动态测量误差预测研究[期刊论文]-国外电子测量技术 2009(2)
4.郭燕.史丽萍.陈红.王正达 求解TSP的插队算法中初始回路的选择[期刊论文]-计算机时代 2008(11)
5.岳培培.刘建.SHEIKH Anjum.陈杰 NoC映射问题中的列举路径分配算法[期刊论文]-电子科技大学学报 2008(1)6.任春玉 基于混合遗传算法的TSP问题优化研究[期刊论文]-哈尔滨商业大学学报（自然科学版） 2007(5)7.金雁.赵耀 嵌入混和混沌搜索的蚁群算法[期刊论文]-计算机工程与应用 2007(28)
8.陈乔礼.吴怀宇.赵新 一种求解旅行商问题的贪婪边重组交叉算子[期刊论文]-计算机工程与应用 2006(31)9.陈文兰.戴树贵 旅行商问题算法研究综述[期刊论文]-滁州学院学报 2006(3)
10.温万惠.刘光远 一种基于可变禁忌长度的多用户检测方法[期刊论文]-信号处理 2005(4)
11.雷开友.王芳.贺一.邱玉辉.刘光远 Tabu Search集中性和多样性自动平衡下的增强搜索策略[期刊论文]-计算机科学 2005(11)
12.刘显德.唐国维.向明尚.富宇.郝建华 求解旅行商问题的蚁群搜索算法[期刊论文]-大庆石油学院学报 2005(2)13.孙洪茹 城市物流配送体系及其路线优化的研究[学位论文]硕士 2005
14.方永慧.刘光远.贺一.邱玉辉 一种基于插入法的禁忌搜索算法[期刊论文]-西南师范大学学报(自然科学版)2003(6)
本文链接：http://d.wanfangdata.com.cn/Periodical_xnsfdxxb200203013.aspx
授权使用：西安建筑科技大学(xajzdx)，授权号：92bab526-55a7-4776-bd99-9e4e00cfe92f
下载时间：2010年12月16日
第!"卷第#期西南师范大学学报（自然科学版）!$$!年%月
&’()!"*’)#+’,-./(’01’,234562738./*’-9/(:.8;5-682
文章编号：>$$$?@">（!$$!）$#$#@>$?
禁忌搜索算法求解旅行商问题研究
贺
!
一>，，刘光远>
!
>A西南师范大学电子与信息工程系，重庆@$$">?；!A重庆师范学院现代信息管理系，重庆@$$$@"
摘要：设计了一种基于B/2(/C实现的禁忌搜索算法，用以求解组合优化难题中的典型代表旅行商问题（D1E）)分别对F’G085(H原始>$城市和中国旅行商问题进行了测试，所得结果都能达到或优于公布的最优解，与传统的F’G085(H神经网络求解D1E相比，禁忌搜索算法具有强健、快速和高效的特点)关
键
词：禁忌搜索算法；旅行商问题；F’G085(H神经网络
文献标识码：%
中图分类号：!"#$
旅行商问题（D1E）是一类有代表性的已被证明具有*E7计算复杂性的组合难题，它的提法是：给定*
个城市，有一旅行商从某一城市出发，访问各城市一次且仅有一次后回到原出发城市，要求找出一条最短的巡回路径)该问题等价于!个点的圆排列，其路径数为（*I>）！J!)若按穷举法求解，即使用每秒运
［>］
算一亿次的巨型机对只有!$个城市的D1E求解，也需搜索#?$年之久)由于D1E代表一类组合优化问题，在实际工程中有许多应用，如电子地图、交通诱导、&K1L单元布局、MDB分组交换网等)因此，利用各种先进算法（如1M和NM）对D1E类似的问题进行求解就成为一个值得关注的问题)事实上，只要能找到能用于实际问题的“亚优解”（1,COPG289/(1’(,28’.）即可)禁忌搜索算法在这一领域中已显示出强大的优越性，正日益受到重视，它所得到的亚优解往往优于传统算法得到的局部极值解，加之搜索效率高，已受到广泛欢迎)本文针对D1E问题的特点，设计了禁忌搜索算法的一种有效实现形式，实验表明，这一方法具有良好的收敛性和较高的搜索效率)
#禁忌搜索算法简介
［!］
禁忌搜索（D/C,15/-=3，简称D1）技术是一种亚启发式搜索技术，由N(’;5-在>QR%年首次提出，进而
［#，@］
形成一套完整算法)所谓禁忌就是禁止重复前面的工作)为了回避局部邻域搜索陷入局部最优的主要
不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次的搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点)就好比人的短时记忆，走过的路不再重复或有选择地重复；同时“遗忘”又使得这些禁止是弱禁止，即在一定的时间之后这些禁止将失效，最终达到全局优化之目的)
［?］
该算法可简单地表示为：
选定一个初始解TO.’4及给以禁忌表"U!；
（F，中选出满足禁忌要求的1DSE!若满足终止规则，则终止计算；否则，在TO.’4的邻域*TO.’4）
候选集7/.O*（TO.’4）；在7/.O*（TO.’4）中选一个评价值最佳的解TO.5V2，TO.’4WUTO.5V2；更新历史记录
1DSE>
收稿日期：!$$>>>$%
作者简介：贺一（>Q"$I），男，四川达县人，讲师，硕士研究生，主要从事神经网络研究)
基金项目：重庆市应用基础研究项目（>QQ"I?""?）；教育部《高等学校骨干教师资助计划》项目（NNI?!$I>$%#?I!R$"）)
!
/0&西南师范大学学报（自然科学版）第&:卷
!，重复"#$%&’
禁忌对象、禁忌长度、邻域结构、评价函数和候选集的确定是禁忌搜索算法设计的核心，此外还包括
［(］
特赦规则和终止规则的确定’
!禁忌搜索算法用于求解"#$
本文提出的禁忌搜索算法如下：
（)）解的领域映射为&*+,-，即固定起点城市，后面的每两个城市进行对换，邻域中的元素个数为!&".)；
（&）目标函数定义为巡回路径的城市间距离之和，目标函数亦作为评价函数；（/）禁忌对象定义为目标函数所求得的目标值；（0）禁忌长度（-123*4567-8）随具体问题而定；
（9）从邻域中选最佳的-123*4567-8.)个元素作为候选集；
（(）为提高解的质量，防止出现循环，应用了特赦规则’本文的特赦规则定义为：当当前最优解未下
降的次数超过给定值时，则特赦禁忌表中的最优解，将其作为下一次迭代的初始解；
（:）终止规则为：程序运行超过给定最大迭代步数，或特赦次数超过给定最大特赦次数；
（;）为增强搜索空间的多样性，本文应用了多初始点策略，即分别以每一个城市作为初始点进行搜索’实验表明，能以较大概率达到最优解或亚优解’
%计算机模拟结果
例)
!+,?#16@)A城市各城市的坐标值来自文献［:］，具体如下：
B)C（AD0AAA，AD00/E）B/C（AD):A:，AD&&E/）B9C（AD9):)，ADE0)0）B:C（AD(;:;，AD9&)E）BEC（AD((;/，AD&9/(）
B&C（AD&0/E，AD)0(/）B0C（AD&&E/，AD:()A）B(C（AD;:/&，AD(9/(）B;C（AD;0;;，AD/(AE）B)AC（AD()9E，AD&(&/）
基于传统!+,?#16@方法的神经网络求得的最好解是&D;E’文献［:］中提出的改进的神经网络新方法求得的“最优解”是&D:&’本文的禁忌搜索算法求得的最优解为&D(EA&（表)），好于已知的最优解’获优概率为;AF’
表ӝ)
初始点)&/09(:;E)A
&D::E0&D:(EA&D(EA&&D(EA&&D(EA&&D(EA&&D(EA&&D(EA&&D(EA&&D(EA&巡回距离
)&/09(:;E)A
&))9(:;E)A&
禁忌搜索算法求得的结果
城/00(:;E)A&/
099:;E)A&/)市9((;E)A&/)0
序(::E)A&/)09
:;;)A&/)09(列;EE&/)09(:
E)A)A/)09(:;
)A/&)09(:;E
#85G5H34-H2I#123"51JK8L47+J=-8M
典型的寻优过程见图)，最优巡回路径见图&’
例&
中国旅行商问题（B*#"%）（城市间距离见文献［;］）’
自从文献［;］提出B*#"%组合优化问题，即我国/)个省、市、自治区首府间的距离表和归一化距离表后，国内外学者对该问题进行了大量的研究工作’由于该问题属于中大规模的组合优化问题，因此，都
期贺一，等：禁忌搜索算法求解旅行商问题研究
地以出，中索显质市
9::西南师范大学学报（自然科学版）表!!"#$%&
中国旅行商问题计算结果’()*+,",-(."$/%0+$,01(2’3!45
城
6:&6;=66>6=6=&&=&=&99
8&9:8:8966==>:866:6=6=&&8&7&79696&8&8&:&9&:&:76;:78
6;6>;;6&7=66&&[1**********]86:6:6>67686=&&>969696969&9&:&9&96;788:87:6
9=9=>;;&6&6666&>;[1**********]:6:6>6>6=6=&&>9696&7&7&89&9&:76;::8:66=6==>
>;>;6&666768&6969676&66686:6:6>6>6=6=&&>9696&7&7&8&8&:&:&9&>6;6;:8:8776=>>;>;;9
&676&66&[1**********]86:&696>6=6=&&>9696&7&7&8&8&:&:&9&96;6;::8876=6==>;996
[1**********]86&6>6:6>6>6=6768&&>9696&7&7&8&8&9&:&9&96;6;::887766=>;>;;96
市666&686:6:6>6:6=6=&&&&=&=9&>9696&7&7&8&8&:&9&:&:76;::887766==>>;96
序
列
6=&&6&&96&7&7&8&8&:&:&9&96;6;::8:66=6==>>;;996
&6&&&&&=&=9&>9696&=9>;>;;9966>6=6>6=6=6:
&=9&>9696&7&7&8&>96&:&9&96;6;::887766==>;9966:6>6>6=6=&6;
&>9696&7&7&8&8&:&:&9&76;::887766==>>;;966=&
&7&7&8&8&:&:&9&96;6;6>;;9966&6967&[1**********]86:6:6>6>6=6=&&8&>&8&8&7
6>6:6>6=6=&&>9696&7&7&8&8&:&:&9&96;788:87766==>>;;996
第卷
起点最短路径6&9:87;>=66=&&=9
67689677>768;:=68;:=68;9&68:::68:;>679>7677679>>
&8&:&:&9&96;6;&96;;99666&66&686:6768686:6:6>6>6=6=&&7&7&7&>&=
76;6966=&96&896&>9
参考文献：
［6］靳
蕃?神经计算智能基础原理・方法［@］?成都：西南交通大学出版社，&
［&］A$(B%2C?C+,+2%*",D01(2-.,%E%2*2(E2"))-.E".F$-.G0,("2,-1-H-"$-.,%$$-E%.H%［I］?!"#$%&’()*+,#&’)%-"*(.&(&)’/0，6=>7，69：
899J8:=?
［9］A$(B%2C?!"#+4%"2HD：*"2,K［I］?,.123"$’*)4"*!"5#$%-*6，6=>=，6：6=］靳［=］杨
潮，宣国荣?人工神经网络求解!45问题新方法［I］（:）：8=J78??计算机应用与软件，&蕃，范俊波，谭永东?神经网络与神经计算机原理・应用［@］?成都：西南交通大学出版社，6==6?忠，鲍
明，赵淳生?人机结合求解中国旅行商问题［I］（:）：9;&J9;7??模式识别与人工智能，6==8，6>
［6
［66］潘立登，黄晓峰?用改进的遗传算法求解中国旅行商问题［I］（6）：7&J77??北京化工大学学报，6==;，&:［6&］孙惠文?遗传算法求解旅行商问题［I］（8）：88
第R期贺一，等：禁忌搜索算法求解旅行商问题研究R14
!"#"$%&’()*(+,-)./*0-)/$12*"$%&’3+.(%-4’5
!"
&
，’()*+,-./0+,-%#$%，
%!"#$%!&’()#*%+&,-*.,/0,’&+1.%-&,(,2-,##+-,2，3&4%56#7%85-,.，9&+1.):,-;#+7-%.,.2#1#,%，85&,2=-,29&+1.):,-;#+7-%
31#4%$&4：5,6789-:,;?2，,;,=+67,@AB,
（HIJ）；!9EF$7
责任编辑
潘春燕
禁忌搜索算法求解旅行商问题研究
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
贺一， 刘光远
贺一(西南师范大学电子与信息工程系,重庆,400715;重庆师范学院现代信息管理系,重庆,400047)， 刘光远(西南师范大学电子与信息工程系,重庆,400715)西南师范大学学报(自然科学版)
JOURNAL OF SOUTHWEST CHINA NORMAL UNIVERSITY2002，27(3)15次
参考文献(13条)
1.靳蕃 神经网络计算基础-原理和方法 2000
2.GLOVER F Future paths for integer programming and links to artificial intelligence 19863.GLOVER F Tabu Search: part I 19894.GLOVER F Tabu Search: part II 19905.刑文训.谢金鑫 现代优化计算方法 19996.GLOVER F.Laguna M Tabu Search 1997
7.王潮.宣国荣 人工神经网络求解TSP问题新方法[期刊论文]-计算机应用与软件 2001(04)8.靳蕃.范俊波.谭永东 神经网络与神经计算机--原理、应用 19919.杨忠.鲍明.赵淳生 人机结合求解中国旅行商问题 1995(04)
10.周培德 求解货郎担问题的几何算法[期刊论文]-北京理工大学学报 1995(01)11.潘立登.黄晓峰 用改进的遗传算法求解中国旅行商问题 1997(01)12.孙惠文 遗传算法求解旅行商问题 1996(05)
13.罗映红 遗传算法求解组合优化问题研究[期刊论文]-甘肃科学学报 1997(02)
相似文献(10条)
1.学位论文 李大卫 GA与TS混合策略的理论与应用研究 1998
该文通过对遗传算法和禁忌搜索算法的分析与比较,提出了一种遗传算法与禁忌搜索算法的混合策略,在重组过程中引入禁忌搜索算法的记忆功能,并把禁忌搜索作为变异算子.应用马尔科夫链理论对混合策略进行了数学描述,证明了混合策略是全局收敛的,并有针对性的选择出八个典型的测试函数对混合策略进行性能测试,并与标准遗传算法进行比较.对自然数编码的遗传算法的最优群体规划的最优变异率两个基本参数进行研究,得到了最优群体规模存在性定理,获得了最优群体规模的一个下限值,给出了最优变异率的存在性定理,这些结果可用于指导应用遗传算法求解实际问题.该文对热轧钢管的生产批量问题进行了系统的分析和研究,首次从切割的角度研究热轧钢管的生产批量计划问题,在分析钢管生产工艺基础上,建立了钢管生产批量计划问题的数学模型,并应用遗传算法进行求解.提出了两阶段可重复自然数编码方法和两阶段独立交叉和变异的遗传算子.
2.期刊论文 张芬莉.姜秀山.孙艳丰 混合遗传算法在旅行商问题中的应用 -西安工业学院学报2004,24(2)
为了更优地解决旅行商问题,改进单纯用遗传算法求解旅行商问题的结果,本文通过遗传算法和禁忌搜索算法自身的特点,分别对二者的优势和不足进行分析,提出一种将二者混合使用的求解旅行商问题的算法.该算法以遗传算法为基础,用遗传算法作全局搜索,用禁忌搜索算法作局部搜索.同时,通过计算实例分析,将这种混合遗传算法用于旅行商问题的求解中.试验表明,混合遗传算法比较单纯的遗传算法的计算结果有一定的改进.
3.学位论文 江新姿 蚁群算法与其他算法的混合 2008
自从上世纪50年代中期创立仿生学以来，人们不断地从生物进化的机理中得到启发，提出了许多用于解决复杂优化问题的新方法，比如神经网络、遗传算法、模拟退火算法、进化规划等，并成功应用于解决实际问题。由意大利学者M.Dorigo，Vmaniezzo，A.Colorni于1992年首先提出的蚁群系统(Ant ColonySystem，ACS)，是一种新颖的仿生进化算法，适用于求解复杂组合优化问题。目前，蚁群系统己成功应用于求解旅行商问题(TSP)、二次分配问题和job-shop调度问题等，取得了很好的实验效果。受其影响，蚁群系统的研究已经逐渐引起了更多学者和专家的关注。虽然，该研究方法处于研究的初级阶段，但是一些研究成果已经显示出蚁群系统在求解复杂优化问题方面的优越性。作为一种全局搜索的方法，蚁群算法具有正反馈性、并行性、分布性、自组织性等特点。但是，蚁群算法也存在一些不足之处:例如，算法需要较长的搜索时间、容易出现早熟停滞现象等。
针对上述不足，我们在深入研究蚁群算法的同时，又对免疫算法和禁忌搜索等算法进行了一定的分析和研究，提出了几种新的用于求解旅行商问题(TSP)的蚁群改进算法。旨在借鉴其他仿生算法的长处，利用其优点弥补蚁群算法的不足，从而提高蚁群算法的求解性能。
本文的主要内容包括：首先，针对蚁群算法中的个体蚂蚁缺乏识别问题特征信息的能力，将免疫算法中疫苗的思想引入到蚁群算法中，新算法从TSP问题本身出发，提取出该 问题的一种本质特征，将此特征信息作为疫苗注射给精英蚂蚁，使其具有“免疫”的能力，能识别该固有特征，以提高精英蚂蚁的搜索质量，从而使得整体的求解能力得以提高。其次，因为蚁群算法容易出现早熟停滞，而禁忌搜索算法可以接受劣解，搜索时能跳出局部最优解，转向解空间的其他解，从而获得更好的全局最优解。故将两种算法混合，用蚁群算法作全局搜索，禁忌搜索算法作局部搜索。从而加速收敛速度，使算法的搜索性能得以提高。最后，根据蚁群算法与遗传算法、模拟退火算法的特性，提出了采用遗传算法生成信息素分布，利用蚁群算法求精确解的遗传蚁群混合算法，以及采用模拟退火算法生成信息素分布，在蚁群算法寻优中采用模拟退火的在领域内找另外一个解的策略的模拟退火蚁群算法。并用新算法解决旅行商问题，得到更有效的解。将上述几种改进算法应用于旅行商问题，进行仿真试验，检验改进算法的相关性能。 实验结果均表明，这几种改进的蚁群算法较之基本蚁群算法，在寻优能力上均有了较大的提高。
4.学位论文 李黎 基于ILOG组件的线路优化平台的设计和实现 2006
线路优化问题应用广泛，涉及到很多行业，譬如在国防领域中，军事物流共同配送线路的优化，在某种意义上可提高军事物资的配送效率；民用方
面的邮电、旅游业，大多都牵涉线路制定问题。虽然目前关于不同约束条件下的基本线路优化模型理论研究已经有很多年的历史，但是理论和实际应用技术问题之间仍然存在着鸿沟。本文通过探讨线路规划技术，并力求将其应用于解决实际问题。
本文对线路优化问题考虑因素分类，总结出六类通用的应用问题模型，即最短路优化问题、旅行商问题、VRP(VehicleRoutingProblem)模型、VRPTW(VehicleRoutingProblemWithTimeWindow)、DVRP(DynamicVehicleRoutingProblem)模型、多发车点模型。对问题本身进行了理论研究，并建立问题的约束规划模型，对该模型的解、约束的性质进行了深入讨论，设计并实现了解决问题的蚁群算法和禁忌搜索算法的流程；并改进蚁群算法、确定了参数选取的原则，使得蚁群算法收敛速度快，提高运行效率。
基于模型的理论分析，利用ILOG优化和视图组件建立了优化算法模块引擎和视图显示系统的线路优化平台，本文大概简要介绍ILOG优化组件类库解决线路优化的技术思路，对部分使用的类进行说明，同时扩展改进蚁群算法到ILOG算法库。并以旅行商问题模型验证算法的效果，实验结果表明算法是十分有效的。
线路优化平台采用了组件技术，相对简化了平台的设计，并保证了平台的易于扩展的功能。
本课题结合两个应用实例——军事配送线路和旅游线路优化，根据线路的特点，总结了类线路优化模型，并使用线路优化平台得出了军事配送线路的示范效果图。
最后，本文进行总结和展望，指出进一步完善的工作。
5.期刊论文 刘于江.喻泽峰.LIU Yu-jiang.YU Ze-feng 一种求解旅行商问题的禁忌搜索算法 -江西理工大学学报2006,27(4)
提出了一种求解旅行商问题的禁忌搜索算法,并对几个实例进行了计算机模拟.实验结果表明,在求解中小规模的旅行商问题上,该算法具有良好的性能.
6.学位论文 杨博 禁忌搜索算法在冷藏供应链配送网络中的应用研究 2005
历史长河中，人类努力的基本目标大多是获得生存的食物。至二十一世纪，随着科技进步，人们的食物在得到了稳定的供应的保证后，开始把美味和营养速冻起来。跨入二十一世纪，发展食品冷藏供应链，保护食品资源，将是我国食品产业可持续发展战略。
冷藏供应链是一种特殊的供应链，它需要特殊的温度控制来保证产品质量。配送环节是产品品质保证最困难的环节，温度、湿度的控制均处于相当不利的状况，从供应链角度看，绝大部分货损常常出现在这一环节。
本文从优化冷藏供应链配送网络的角度来解决上面提到的问题。由于冷藏供应链与传统供应链的不同，作者选用了一种不依赖于具体问题的直接搜索法-禁忌搜索(TS)。
TS是由F.Glover提出来的。其基本思想是从某一初始状态(初始解)出发，对其邻域进行搜索，在禁忌表的控制下，确定移动的方向，直至得到满意解为止。它具有计算速度快、能够跳出局部最优、可解大型问题的能力。因此，TS算法自产生以来，以其自身特有的优势立足于许多研究领域。目前它已被成功应用于调度问题、旅行商问题、工作流程排序问题、通讯线路分配问题、神经网络识别问题、图形着色问题、二次指派问题等。
本文应用TS来解决冷链网络优化问题，充分考虑到冷链的特殊性，建立了质量和成本模型。并将禁忌搜索算法得到的结果与其他算法得到的优化结果进行了比较。实例表明用TS算法求解搜索到了其它算法未能得到的最优解。
7.期刊论文 张洪艳 一种改进的多初始解禁忌搜索算法 -科技信息（学术版）2008,""(34)
本文根据禁忌搜索算法的特点,提出了一种基于多初始解的禁忌搜索算法(STS).该算法为禁忌搜索算法构造多个较优初始解,进而进行多初始解禁忌搜索以找到全局最优解.以旅行商问题(TSP)为例,验证了该算法的有效性.
8.学位论文 荚恒松 蚁群算法及其应用研究——基于旅行商问题和图像分类 2008
蚁群算法是MarcoDorigo等学者在真实蚂蚁觅食行为的启发下提出的一种具有高度创新性的元启发式搜索算法。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后提出的又一种应用于解决组合优化问题的启发式搜索算法。试验表明，蚁群算法具有较好的求解能力，但是蚁群算法存在收敛速度慢，容易陷入局部最优解等不足。本文主要研究如何改进算法模型并应用于相关领域，主要工作包括以下两部分。
首先，对蚁群算法进行基础理论研究，改进并提出分类蚁群算法(CBACO)，将其应用于TSP问题。旨在对蚁群算法近年来的研究进展进行总结，归纳算法的成功和存在的不足，对不足之处进行理论分析并改进，目的在于提高蚁群算法的总体性能。改进后的模型在智能蚁群的基础上引入随机蚁群以便扩大搜索空间，不同蚁群实行各自不同的搜索前进策略和信息更新机制，从而避免算法陷入早熟，以获取更大的解空间。并可通过调节随机蚁群与智能蚁群的比例来控制收敛速度，从而提高算法的运行效率。试验表明，将其应用于TSP问题可以获取更好的求解性能。
其次，针对基本蚁群算法分类图像速度慢的缺点，根据蚁群算法的聚类和离散性特点，改进蚁群算法并应用于图像分类。随机蚂蚁在图像中识别类、构建类别表，并确定聚类中心、生成相应类的智能蚂蚁，指导智能蚂蚁分类的过程；智能蚂蚁按相应的搜索前进策略向聚类中心聚集，识别目标。同时所有的蚂蚁在搜索前进过程中对图像进行边缘提取，以便提高算法对图像边缘分类的准确度。试验表明，相比基本蚁群算法求解图像分类问题，由于该改进引入初始聚类中心和识别边缘，算法的分类效率和对边缘信息点分类的准确度得到提高，并实现了图像的自动分类。
9.期刊论文 江新姿.高尚.JIANG Xin-zi.GAO Shang 改进的蚁群禁忌搜索混合算法 -科学技术与工程2010,10(14)
蚁群算法作为一种全局搜索的方法,具有正反馈性、并行性、分布性、自组织性等特点,在求解复杂组合优化问题上具有强大的优势.但是,蚁群算法也存在一些不足之处:例如,算法需要较长的搜索时间、容易出现早熟停滞现象.为了更优地解决旅行商问题,改进单纯用蚁群算法求解旅行商问题的结果,通过蚁群算法、免疫算法和禁忌搜索算法自身的特点,分别对三者的优势和不足进行分析,提出一种将三者混合使用的求解旅行商问题的算法.
10.学位论文 郭娜 基于节约算法和移动方向的禁忌搜索算法 2009
随着优化算法和启发式算法的提出，国内外掀起了研究智能优化算法的热潮。禁忌搜索是一种新的智能优化算法，是由美国科学家Glovr教授于1986年正式提出。禁忌搜索(TS)在智能算法中独树一帜，成为一个研究热点，受到了国内外学者的广泛关注，并应用到组合优化和函数优化问题中。本文基于原禁忌搜索的思想提出一种改进的禁忌搜索算法，并把这种改进算法应用到实际问题中。
在前期工作的基础上，本文主要的工作包括针对禁忌搜索算法对初始解依赖性强的缺点，利用c-w节约算法得到初始解。禁忌搜索算法设计的框架中初始解尤为关键，初始解的好坏制约着搜索的收敛速度。通过c-w节约算法得到高质量解，构造算法新的搜索起点，加强了集中性搜索力度。在仿真实验中验证了其有效性。
同时针对禁忌搜索算法中集中性与多样性搜索并重的情况下，多样性不足的缺点，从下面两个方面改进算法，拓宽搜索领域，加强多样性搜索，增加灵活性。通过改进禁忌表存储结构，定义优质解和劣质解的出现次数这两个概念，不只利用禁忌表禁忌最近的搜索，还记录这些移动是否有所改进，记录下改进的信息，表明新解的改变程度，在搜索决策中并入这些信息，使得搜索往利于改进的方向进行。T S中确定性的搜索过程制约了它的灵活性，所以在禁忌搜索原则确定的基础上，根据搜索中的移动信息，增加概率性因素，在评价函数中增加一个概率函数，把确定性选择过程变为概率性的，从而改进搜索方向，拓宽搜索领域，使得更好的解有更大的被选中的机会。
旅行商问题(TSP)是典型的组合优化难题，但由于TSP有着广泛的实际应用工程背景，有效地解决TSP问题一直受到人们的重视，已有多种方法成功求解TSP问题。根据本文改进的禁忌搜索算法提出一种解决TSP问题有效形式。
引证文献(14条)
1.李雪梅.张素琴 基于仿生理论的几种优化算法综述[期刊论文]-计算机应用研究 2009(6)2.任晔.顾彬.李玉凯 物流系统优化问题研究方法概述[期刊论文]-物流科技 2009(5)
3.陈榕.陈振林.李洪周 基于禁忌BP神经网络的动态测量误差预测研究[期刊论文]-国外电子测量技术 2009(2)
4.郭燕.史丽萍.陈红.王正达 求解TSP的插队算法中初始回路的选择[期刊论文]-计算机时代 2008(11)
5.岳培培.刘建.SHEIKH Anjum.陈杰 NoC映射问题中的列举路径分配算法[期刊论文]-电子科技大学学报 2008(1)6.任春玉 基于混合遗传算法的TSP问题优化研究[期刊论文]-哈尔滨商业大学学报（自然科学版） 2007(5)7.金雁.赵耀 嵌入混和混沌搜索的蚁群算法[期刊论文]-计算机工程与应用 2007(28)
8.陈乔礼.吴怀宇.赵新 一种求解旅行商问题的贪婪边重组交叉算子[期刊论文]-计算机工程与应用 2006(31)9.陈文兰.戴树贵 旅行商问题算法研究综述[期刊论文]-滁州学院学报 2006(3)
10.温万惠.刘光远 一种基于可变禁忌长度的多用户检测方法[期刊论文]-信号处理 2005(4)
11.雷开友.王芳.贺一.邱玉辉.刘光远 Tabu Search集中性和多样性自动平衡下的增强搜索策略[期刊论文]-计算机科学 2005(11)
12.刘显德.唐国维.向明尚.富宇.郝建华 求解旅行商问题的蚁群搜索算法[期刊论文]-大庆石油学院学报 2005(2)13.孙洪茹 城市物流配送体系及其路线优化的研究[学位论文]硕士 2005
14.方永慧.刘光远.贺一.邱玉辉 一种基于插入法的禁忌搜索算法[期刊论文]-西南师范大学学报(自然科学版)2003(6)
本文链接：http://d.wanfangdata.com.cn/Periodical_xnsfdxxb200203013.aspx
授权使用：西安建筑科技大学(xajzdx)，授权号：92bab526-55a7-4776-bd99-9e4e00cfe92f
下载时间：2010年12月16日