下载文档原格式
禁忌搜索算法评述(一)摘要:工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。
禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。
本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。
关键词:禁忌搜索算法;优化;禁忌表;启发式;智能算法1引言工程领域内存在大量的优化问题,对于优化算法的研究一直是计算机领域内的一个热点问题。
优化算法主要分为启发式算法和智能随机算法。
启发式算法依赖对问题性质的认识,属于局部优化算法。
智能随机算法不依赖问题的性质,按一定规则搜索解空间,直到搜索到近似优解或最优解,属于全局优化算法,其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。
禁忌搜索算法(TabuSearch,TS)最早是由Glover在1986年提出,它的实质是对局部邻域搜索的一种拓展。
TS算法通过模拟人类智能的记忆机制,采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。
同时引入特赦(破禁)准则来释放一些被禁忌的优良状态,以保证搜索过程的有效性和多样性。
TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法,可以克服搜索过程易于早熟收敛的缺陷而达到全局优化1]。
迄今为止,TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域,并显示出极好的研究前景2~9,11~15]。
目前关于TS 的研究主要分为对TS算法过程和关键步骤的改进,用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。
禁忌搜索提出了一种基于智能记忆的框架,在实际实现过程中可以根据问题的性质做有针对性的设计,本文在给出禁忌搜索基本流程的基础上,对如何设计算法中的关键步骤进行了有益的总结和分析。
2禁忌搜索算法的基本流程TS算法一般流程描述1]:(1)设定算法参数,产生初始解x,置空禁忌表。
禁忌搜索算法的研究及其在TSP的应用禁忌搜索在一系列应用范围内取得了很大的成功,这篇论文致力于揭示其最主要的思想,解释其最基本的原理,并用它来求解组合优化难题中的典型代表旅行商问题(TSP),经过试验和分析,证明它是一种较好的全局启发式搜索算法。
标签：禁忌搜索组合优化旅行商问题启发式搜索算法0 引言禁忌搜索(Tabu Search或Taboo Search,简称TS)最早由Glover(1986)提出,它是对局部邻域搜索的一种扩展,并且是一种全局逐步寻优算法。
禁忌搜索算法通过引入一个灵活的存储结构,并且配备一个相应的禁忌准则来避免搜索的重复,并通过设置一个相应的藐视准则来赦免一些被禁忌的但是还有可能是优于当前解的状态,从而保证多样化的探索并且最终实现全局优化。
相对于模拟退火和遗传算法,禁忌搜索算法是又一种搜索特点不同的meta-heuristic算法[1]。
迄今为止,禁忌搜索算法在机器学习和组合优化,甚至包括生产调度、和神经网络等领域取得了非常大的成功,并且引起越来越多的学者的关注,得到了进一步的发展。
1 TSP问题的描述旅行商问题(TSP问题)是一个比较经典的数学问题,就是一个销售商从多个城市中的某一城市出发,不重复地走完其它的城市并且回到原点,在所有可行的路径中找出路径长度最短的一条。
将TSP用数学语言可以表述为:假设V1,V2,V3…Vn是给定的n个城市,从某个城市Vi(1≤i≤n)出发,走遍每个城市一次且只一次,然后返回到出发点,求出一条使得总路径最短的路径。
aij表示城市Vi到城市Vj的两地路径的长度[2]。
2 禁忌搜索算法禁忌搜索算法的基本思想是:给定一个初始解(随机的),并且给定这个初始解的一个邻域,然后在此初始解的邻域中确定某些解作为算法的候选解;给定一个状态,“best so far”(既当前最优解);若最佳候选解所对应的目标值优于“best so far”状态,则忽视它的禁忌特性,并且用这个最佳候选解替代当前解和“best so far”状态,并将相应的解加入到禁忌表中,同时修改禁忌表中各个解的任期;若找不到上述候选解,则在候选解里面选择非禁忌的最佳状态做为新的当前解,并且不管它与当前解的优劣,并且将相应的解加入到禁忌表中,同时修改禁忌表中各对象的任期;最后,重复上述搜索过程,直至我们得到的解满足停止准则。
禁忌搜索算法
1. 背景介绍
禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。
在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。
使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用。
禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。
为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。
TS是人工智能的一种体现，是局部领域搜索的一种扩展。
禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等影响禁忌搜索算法性能的关键因素。
迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。
2. 国内外发展。
Vol 18,No 1管 理 工 程 学 报Journal of Industrial Engineering Engineering Management2004年第1期车辆路径问题的禁忌搜索算法研究郎茂祥,胡思继(北京交通大学交通运输学院,北京100044)摘要:论文在对车辆路径问题进行简单描述的基础上,通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法,并进行了实验计算。
计算结果表明,用本文设计的禁忌搜索算法求解车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定。
关键词:车辆路径问题;禁忌搜索算法;优化中图分类号:F502 文献标识码:A 文章编号:1004-6062(2004)01-0081-04收稿日期:2002-06-18 修回日期:2002-12-30作者简介:郎茂祥(1969 ),男(汉),山东高唐人,北京交通大学交通运输学院副教授,博士,主要研究方向为交通运输规划与管理。
0 引言车辆路径问题(VRP,Vehicle Rou ting Problem)是由Dantzig 和Ramser 于1959年提出的[1]。
该问题一直是运筹学与组合优化领域的前沿与热点问题。
在现实生产和生活中,邮政投递问题、飞机、铁路列车、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题。
研究车辆路径问题具有重要的理论和现实意义。
车辆路径问题作为一个NP 难题,随着客户数量的增加,可选的车辆路径方案数量将以指数速度急剧增长。
因此,用启发式算法求解该问题就成为人们研究的一个重要方向。
求解车辆路径问题的方法很多,常用的有旅行商法、动态规划法、节约法、扫描法[2]、分区配送算法[3]、方案评价法等。
禁忌搜索算法的出现,为求解车辆路径问题提供了新的工具。
Gendreau 、Jiefeng 、Barbarosoglu 、蔡延光等都曾利用禁忌搜索算法求解车辆路径问题[4-8],并取得了一些研究成果。
一、实验背景禁忌搜索算法（Tabu Search，TS）是一种基于局部搜索的优化算法，最早由Glover和Holland于1989年提出。
该算法通过引入禁忌机制，避免陷入局部最优解，从而提高全局搜索能力。
近年来，禁忌搜索算法在蛋白质结构预测、调度问题、神经网络训练等领域得到了广泛应用。
本次实验旨在验证禁忌搜索算法在求解组合优化问题中的性能，通过改进禁忌搜索算法，提高求解效率，并与其他优化算法进行对比。
二、实验目的1. 研究禁忌搜索算法的基本原理及其在组合优化问题中的应用；2. 改进禁忌搜索算法，提高求解效率；3. 将改进后的禁忌搜索算法与其他优化算法进行对比，验证其性能。
三、实验方法1. 算法实现本次实验采用Python编程语言实现禁忌搜索算法。
首先，初始化禁忌表，存储当前最优解；然后，生成新的候选解，判断是否满足禁忌条件；若满足，则更新禁忌表；否则，保留当前解；最后，重复上述步骤，直到满足终止条件。
2. 实验数据本次实验采用TSP（旅行商问题）和VRP（车辆路径问题）两个组合优化问题作为实验数据。
TSP问题要求在给定的城市集合中找到一条最短的路径，使得每个城市恰好访问一次，并返回起点。
VRP问题要求在满足一定条件下，设计合理的配送路径，以最小化配送成本。
3. 对比算法本次实验将改进后的禁忌搜索算法与遗传算法、蚁群算法进行对比。
四、实验结果与分析1. TSP问题实验结果（1）改进禁忌搜索算法（ITS）实验结果表明，改进后的禁忌搜索算法在TSP问题上取得了较好的效果。
在实验中，设置禁忌长度为20，迭代次数为1000。
改进禁忌搜索算法的求解结果如下：- 最短路径长度：335- 迭代次数：1000- 算法运行时间：0.0015秒（2）遗传算法（GA）实验结果表明，遗传算法在TSP问题上的求解效果一般。
在实验中，设置种群规模为100，交叉概率为0.8，变异概率为0.1。
遗传算法的求解结果如下：- 最短路径长度：345- 迭代次数：1000- 算法运行时间：0.003秒（3）蚁群算法（ACO）实验结果表明，蚁群算法在TSP问题上的求解效果较好。
禁忌搜索算法作者：季敏惠来源：《电脑知识与技术》2009年第27期摘要:随着网络应用不断广泛,网络数据也呈几何级增长。
基于内容的图像搜索算法成为一个很好的解决方案。
该文为图像提取方法提供了一个新的高效的框架,该算法框架相对于以前所使用的基于流形的方法具有明显的优势:本方法框架可以直接对图像数据评定相关性并返回相关性最高的图像数据,而以往的基于流形的方法必须要从特征空间到一个不清晰的语义流形空间做一个映射,并对这个映射进行学习。
关键词:图像;CUDA;熵;流形中图分类号:TP391.41文献标识码:A 文章编号:1009-3044(2009)27-7748-03Active Tabu SearchJI Min-hui(College of Software Engineering, Southeast University, Nanjing 210096, China)Abstract:With the extensive of network applications, network-level data is growing geometrically. Content-based image search algorithm is a good solution. A novel framework is proposed for image retrieval in this paper. Our framework has an clear advantage over pervious manifold based methods: our method can directly rank and return relevant images and does not need to learn a mapping from the feature space to the unclear semantic manifold space, further avoiding the unnecessary exploration on the dimensionality of the semantic space.Key words: image; CUDA; manifold随着信息技术的日益发展,有一样东西以无可遏制的速度增长着,这就是数据。
禁忌搜索算法详解转载现代优化算法之禁忌搜索算法（含题⽬）禁忌搜索算法的实现_Python禁忌搜索算法详解链接：禁忌搜索是由局部搜索算法发展⽽来，爬⼭法是从通⽤局部搜索算法改进⽽来。
在介绍禁忌搜索之前先来熟悉下爬⼭法和局部搜索算法。
局部搜索算法算法的基本思想在搜索过程中，始终选择当前点的邻居中与离⽬标最近者的⽅向搜索。
算法过程（1）随机选择⼀个初始的可能解x0 ∈D，xb=x0,P=N(xb);//D是问题的定义域， xb⽤于记录到⽬标位置的最优解，P为xb的邻域。
（2）如果不满⾜结束条件，则：//结束条件为循环次数或P为空等（3）Begin；（4）选择P的⼀个⼦集P'，xn为P’的最优解；//P’可根据问题特点，选择适当⼤⼩的⼦集。
可按概率选择（5）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转(2)；//重新计算P，f(x)为指标函数（6）否则P=P-P'，转(2)；（7）End；（8）输出计算结果；（9）结束；爬⼭法算法的基本思想将搜索过程⽐作爬⼭过程，在没有任何有关⼭顶的其他信息的情况下，沿着⾼度增加的⽅向爬。
如果相邻状态没有⽐当前值更⾼，则算法停⽌，认为当前值即为顶峰。
算法过程（1）设置初始状态n=s0为当前状态;（2）如果当前状态已达标，算法结束，搜索成功;（3）获取当前状态n的若⼲个临近状态m,计算这些h(m), nextn=min{h(m)}；（4） IF h(n) < h(nextn)THEN n:=nextn;ELSE 取当前状态为最佳状态并退出;（5） GOTO (2)步;该算法在单峰的条件下，必能达到⼭顶。
显⽽易见爬⼭法对于复杂情况的求解会遇到以下问题：（1）局部极值（2）⼭脊：造成⼀系列的局部极值（3）⾼原：平坦的局部极值区域——解决办法：继续侧向移动⽬前有些改进的爬⼭法，⽐如随机爬⼭法、⾸选爬⼭法等等不再细说。
禁忌搜索算法算法思想标记已经解得的局部最优解或求解过程，并在进⼀步的迭代中避开这些局部最优解或求解过程。
基于禁忌搜索算法的车辆路径选择摘要：本文从VRP的提出背景与求解方法出发，阐释了禁忌搜索算法的原理与影响算法性能的关键因素，进而将禁忌搜索算法的思想运用于解决车辆路径问题，在VRP问题初始解的基础上，用禁忌搜索算法优化车辆配送路线，设计出直观且策略易于理解的客户直接排列的解的表示方法，最后将该算法用C语言实现并用于求解VRP问题，测试结果表明该算法可行且解的质量较高。
关键词：车辆路径问题；禁忌搜索；邻域；禁忌表1.引言物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径，使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车辆路径问题正是基于这一需求而产生的。
求解车辆路径问题（Vehicle Routing Problem简记VRP）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间复杂度呈指数增长，且VRP问题属于NP-hard问题，求解比较困难，因此启发式算法成为求解VRP问题的主要方法。
禁忌搜索算法是启发式算法的一种，为求解VRP提供了新的工具。
本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌搜索算法。
因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。
2.车辆路径问题的禁忌搜索算法2.1 车辆路径问题的描述车辆路径问题的研究目标是对一系列送货点或取货点，确定适当的配送车辆行驶路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。
参见下图2.1所示：其中0表示配送中心，1～８表示客户编号。
图2.1 车辆路径问题在本文中为使得问题易于理解，将该问题描述为：有一定数量的客户，各自有不同数量的货物需求，且每个客户的位置和需求量一定，一个物流中心提供这些货物，并有一个车队负责分送货物，每台配送车辆的载重量一定，这里假设车辆的型号一致，即最大载重量和最远行驶里程数相同，要求合理安排车辆配送路线，使配送总路程最短，同时得满足一定的约束条件，即每条路线总需求量之和不得超过配送车辆的载重量、每条路线行驶的里程数不得超过配送车辆的最远里程数、每一客户需求必须满足且仅由一台车辆配送。
禁忌搜索算法描述禁忌搜索算法思想最早由Glover在1986年提出的，是一种全局逐步寻优算法。
其求解的过程是先求得一初始解，然后在邻域中搜索较佳解或是移动到较差的区域搜索该区域最佳解，并且记录曾经搜寻的路径，作为下次搜索的依据，以避免陷入局部最优解中。
它引入了一个禁忌表记录下已经搜索过的局部最优点，在下一次搜索中利用禁忌表中的信息不再或者有选择地搜索这些点，以此来跳出局部最优点,从而实现全局优化。
将禁忌搜索的思想条理化，可描述如下图2.2所示：图2.2 禁忌搜索算法框架3车辆路径问题的禁忌搜索算法实现3.1算法思路本文先用插入式启发算法得到车辆路径问题的初始可行解，再利用禁忌搜索算法对初始解进行改造。
具体步骤如下：（1）构造初始解时，先用客户直接排列的解的表示方法，随机生成某一不重复的客户排列序列，然后按照车辆路径问题的约束条件，依次将解的元素（客户）划入各条配送路径中，由此产生车辆路径问题的初始解，计算出当前解的目标函数值，这里的目标函数值为各车辆配送路径的里程数总和。
（2）通过随机交换两客户位置来生成当前解的邻域解，则有C2n=n*(n-1)/2个客户直接排列序列，然后按照车辆路径问题的约束条件,依次将解的元素（客户）划入各条配送路径中，由此计算出各邻域解的目标函数值。
（3）根据藐视准则来评价当前解的邻域解，更新当前解与禁忌表。
若候选解的目标值优于当前的最优目标值，不管其禁忌属性如何，更新为当前最优解并更新禁忌表，否则判别该方案的两个客户交换是否被禁忌：若被禁忌，选取次优解后继续该步骤；若未被禁忌，更新该解为当前解并更新禁忌表。
（4）若所有的候选对象均被禁忌，则根据队列FIFO原则，对禁忌表中队头元素取消其禁忌属性；禁忌表的更新为将其中所有的禁忌对象的禁忌长度减1，禁忌长度为0的对象取消其禁忌属性。
（5）重复迭代指定步长的（2）～（4），输出车辆配送方案的最终结果。
3.2 程序设计简介算法中，无论是初始解的构造还是邻域内寻优，都涉及到对大量配送点进行的操作，如构造初始解时，针对车辆路径问题的约束条件将客户划分到不同的路径中；更新禁忌表时的将禁忌对象放入表中以及满足藐视准则时的禁忌对象的解禁。
程序中针对该问题，采用了队列的形式，通过改进的队列基本操作来实现路径的分配与禁忌表的更新问题。
下面给出定义的几个结构体：（1）客户位置的无重复随机生成以及客户需求量的随机生成实际配送系统中的客户的地理位置相对独立，且彼此之间服从独立均匀分布，为简易起见，程序中对客户的地理位置分布与客户的需求量只简单地使用C语言中的rand()函数进行随机分配，其中物流中心的地理位置默认为（0，0），为了保证生成的客户位置没有重复，用c_location[j].x==c_location[i].x && c_location[j].y==c_location[i].y语句来判定，其中c_location数组采用CPoint结构体，用于存储客户的位置，demand数组用于存储客户需求量，这两个数组均被定义为全局变量。
（2）客户随机序列的生成算法中采用客户直接排列的解的表示方式，随机生成初始解，即无重复的客户随机排列序列数组A。
（3）初始解的车辆路径分配将客户随机序列数组A中的各个值赋值到i_now数组中，i_now数组用于记录当前的最优解，定义车辆的最大负载量vehicle_Max，这里假设物流中心车辆的型号一致并且不考虑车辆的最大行驶距离。
（4）当前解的邻域结构通过依次交换两客户位置来生成当前解的邻域解，则有C2n=n*(n-1)/2个客户直接排列序列。
i_now的邻域解，用数组exchange_solution记录。
用与初始分配方案相似的算法，可以求出exchange_solution数组中每一个车辆分配路线的车辆数以及车辆所行驶的总里程数，分别记录到数组N_num和s中。
（5）寻找当前解邻域结构的评价值最优方案先从数组s中寻找到车辆行驶里程数最短的方案，记其下标为ibest，判断该方案是由当前解的哪两个客户交换得到的，记作i_x和i_y。
根据禁忌准则对该局部最优解进行处理，可以替换为当前最优解的条件有二：(1)这两个元素的交换是可行的、未被禁忌的；(2)其解优于当前解，不管其是否禁忌均替换当前最优解，更新禁忌表，将禁忌表中各禁忌对象的禁忌步长减1，当禁忌步长为0时，取消禁忌对象的禁忌属性，而当替换方案中的所有对象均被禁忌后，根据FIFO原则，取消队头元素的禁忌属性。
4. 算例分析这里用Microsoft Visual C++对车辆路径问题的禁忌搜索算法进行编程，通过对相对独立的随机分布在（0，100]平方公里范围内的指定客户数、且客户的需求为的（0，指定的客户数]范围内的随机数的VRP实例进行求解，进行了实验计算。
设在某物流中心有10台配送车辆，车辆的最大载重量均为10单位，在不考虑车辆一次配送的最大行驶距离的情况下，需要向10个客户运送货物，作者利用计算机随机产生了范围在0～100内的10个客户的位置坐标（坐标无重复情况）以及客户的货物需求量，其中物流中心的坐标默认为（0，0），各个客户的坐标位置与需求量如下图2.3所示，要求合理安排配送车辆的行车路径，使配送的总里程数最短。
为简便起见，本文设各客户相互之间及物流中心与客户之间的距离均采用直线距离，该距离可根据客户和物流中心的坐标计算得到，如下图2.4所示。
图2.3 禁忌搜索算法相关信息图2.4 客户地理位置分布情况及车辆路径分配由算法的运行结果可知：初始解方案中所调派的车辆数为7、车辆所行驶的总里程数为731.46，车辆的配送方案为0-4-0、0-7-0、0-8-0、0-6-0、0-9-10-0、0-3-2-5-0、0-1-0，而用禁忌搜索算法对初始解进行改进后所得到的最终方案为：车辆数为6、车辆所行驶的总里程数为353.96，车辆的分配方案为0-1-7-0、0-4-0、0-6-0、0-8-0、0-10-3-2-0、0-5-9-0，车辆所行驶的总里程数得到很大程度的改善，且得到全局较优解所花费的时间仅为0.05s。
5总结本文基于车辆路径问题的简单描述，采用客户直接排列的解的表示方法，相比较现有研究成果将车辆路径问题描述为网络图问题的有向边排列方法，表示更加直观、算法策略更加简单并易于理解，而且算法在迭代过程中产生的解均为可行解，算法的收敛速度得到明显改善。
实验的计算结果表明，用禁忌搜索算法求解车辆路径问题能够跳出局部最优解，实现全局最优化，所得到的最终解决方案相比较初始方案质量更优，寻优性能良好。
参考文献：[1]李军，郭耀辉．车辆优化调度理论与方法[M]．北京：中国物资出版社，2001年．[2]郎茂祥，胡思继．车辆路径问题的禁忌搜索算法研究[J]．管理工程学报，2004，18（1）：81-84．[3]李松，李瑞彩，刘兴．基于改进禁忌搜索算法的车辆路径优化[J]．铁道运输与经济，2008，30（5）：91-94．[4]张强，荆刚，陈建岭．车辆路线问题研究现状及发展方向[J]．交通科技，2004，23（1）：60-62．[5]刘云忠，宣慧玉．车辆路径问题的模型及算法研究综述[J]．管理工程学报，2005，19（1）：124-130．。
