禁忌搜索算法浅析 摘要:本文介绍了禁忌搜索算法的基本思想、算法流程及其实现的伪代码。禁忌搜索算法（Tabu Search或Taboo Search，简称TS算法）是一种全局性邻域搜索算法，可以有效地解决组合优化问题，引导算法跳出局部最优解，转向全局最优解的功能。 关键词:禁忌搜索算法；组合优化；近似算法；邻域搜索 1禁忌搜索算法概述 禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用。 禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。 TS是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等影响禁忌搜索算法性能的关键因素。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 2禁忌搜索算法的基本思想 禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索，TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。 禁忌搜索是对局部邻域搜索的一种扩展，是一种全局逐步寻求最优算法。局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索，虽然算法通用易实现，且容易理解，但搜索性能完全依赖于邻域结构和初解，尤其会陷入局部极小而无法保证全局优化型。 禁忌搜索算法中充分体现了集中和扩散两个策略，它的集中策略体现在局部搜索，即从一点出发，在这点的邻域内寻求更好的解，以达到局部最优解而结束，为了跳出局部最优解，扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息，算法通过对禁
一、二维背包问题 一维背包问题讨论的背包问题只有一种限制，即旅行者所能承受的背包的重量（亦即重量不能超过a （kg ）.但是实际上背包除受重量的限制外，还有体积的限制，这就是不但要求旅行者的背包的重量M 不能超过a （kg ），还要求旅行者背包的体积V 不能超过b （m3）,我们把这样的问题称为“二维背包问题”。 它的状态变量有两个因素:一个是重量，一个是体积。 二维背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i 件物品所需的两种代价分别为i a 和i b 。两种代价可付出的最大值（两种背包容量）分别为a 和b 。物品的价值为i c 。 模型： 11 1 max . ,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑
例题 码头有一艘载重量为30t ，最大容为12×10m 3的船，由于运输需要,这艘船可用于装载四种货物到珠江口，它们的单位体积,重量及价值量见下表: 现求如何装载这四种货物使价值量最大。 1 1 1 max .,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑ 可用动态规划来解决 1.设x i （i=1,2,3,4）分别表示装载这四种货物的重量， 2.阶段k ：将可装入的货物按1,2,3,…n 排序，每个阶段装一种货物，（共可分为四个阶段） 3.状态变量： 1k S +和1k R +，表示在第k 阶段开始时，允许装入的前k 种货物的重量与体积。 状态转移方程： 11k k k k k k k k S S a x R R b x ++=-=- ()(){}111,max ,j k k j k k j j f S R f S R c x -++=+，表示在不超过重量和体积的前提下，装 入前j 中货品的价值。（j=1,2,3,4）
基于WSA算法的作业车间低碳调度方法研究 1.1 引言 本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型 本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。 考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。
禁忌搜索算法评述(一) 摘要:工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 关键词:禁忌搜索算法;优化;禁忌表;启发式;智能算法 1引言 工程领域内存在大量的优化问题,对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识,属于局部优化算法。智能随机算法不依赖问题的性质,按一定规则搜索解空间,直到搜索到近似优解或最优解,属于全局优化算法,其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法(TabuSearch,TS)最早是由Glover在1986年提出,它的实质是对局部邻域搜索的一种拓展。TS算法通过模拟人类智能的记忆机制,采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦(破禁)准则来释放一些被禁忌的优良状态,以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法,可以克服搜索过程易于早熟收敛的缺陷而达到全局优化1]。 迄今为止,TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域,并显示出极好的研究前景2~9,11~15]。目前关于TS 的研究主要分为对TS算法过程和关键步骤的改进,用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。 禁忌搜索提出了一种基于智能记忆的框架,在实际实现过程中可以根据问题的性质做有针对性的设计,本文在给出禁忌搜索基本流程的基础上,对如何设计算法中的关键步骤进行了有益的总结和分析。 2禁忌搜索算法的基本流程 TS算法一般流程描述1]: (1)设定算法参数,产生初始解x,置空禁忌表。 (2)判断是否满足终止条件?若是,则结束,并输出结果;否则,继续以下步骤。 (3)利用当前解x的邻域结构产生邻域解,并从中确定若干候选解。 (4)对候选解判断是否满足藐视准则?若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“bestsofar”状态,然后转步骤(6);否则,继续以下步骤。 (5)判断候选解对应的各对象的禁忌情况,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。 (6)转步骤(2)。 算法可用图1所示的流程图更为直观的描述。 3禁忌搜索算法中的关键设计 3.1编码及初始解的构造 禁忌搜索算法首先要对待求解的问题进行抽象,分析问题解的形式以形成编码。禁忌搜索的过程就是在解的编码空间里找出代表最优解或近似优解的编码串。编码串的设计方式有多种策略,主要根据待解问题的特征而定。二进制编码将问题的解用一个二进制串来表示2],十进制编码将问题的解用一个十进制串来表示3],实数编码将问题的解用一个实数来表示4],在某些组合优化问题中,还经常使用混合编码5]、0-1矩阵编码等。 禁忌搜索对初始解的依赖较大,好的初始解往往会提高最终的优化效果。初始解的构造可以
第15卷第7期计算机集成制造系统 Vol.15No.72009年7月 Computer Integrated Manufacturing Systems July 2009 文章编号:1006-5911(2009)07-1383-06 收稿日期:2008 06 18;修订日期:2008 10 13。Received 18June 2008;accepted 13Oct.2008. 基金项目:国家自然科学基金资助项目(70771008,70371057)。Fo undation item:Project supp orted by the National Natural Science Fundation, Ch ina(N o.70771008,70371057). 作者简介:崔健双(1971-),男,河北衡水人,北京科技大学经济管理学院副教授,博士,主要从事生产调度算法理论及应用、安全电子商务的研 究。E mail:cuijs@manag https://www.doczj.com/doc/354089028.html, 。 求解作业车间调度问题的全局邻域搜索方法 崔健双,李铁克 (北京科技大学经济管理学院,北京 100083) 摘 要:采用传统的关键邻域搜索方法求解作业车间调度问题时,往往容易陷入局部极值而且难以跳出。为此,提出了一种具有动态调整能力的全局邻域交换策略,该策略有可能产生大量的不可行调度,需要一种筛选方法加以过滤。证明了一个新的邻域交换性质,利用该性质可以对所得调度方案作可行性约束判定,从而有效地过滤掉不可行调度。在此基础上,提出了一种求解作业车间调度问题的算法。最后,取不同规模的Benchmar k 问题算例对该算法进行测试,结果表明,无论从解的质量还是计算时间都取得了较好的效果。 关键词:邻域结构;关键路径;作业车间调度;邻域交换;调度算法中图分类号:T P18 文献标识码:A Global neighborhood algorithm for Job Shop scheduling problem CUI J ian shuang,LI T ie ke (Scho ol of Economic M anag ement,U niversit y of Science &T echno lo gy Beijing,Beijing 100083,China)Abstract:T r aditional cr itical neighbor ho od alg or ithms fo r Jo b Shop scheduling problem w ere easily t rapped into local optimal and hardly to escape.T o deal w ith t his pro blem,a g lo bal neig hbo rhoo d swapping st rateg y wit h dynamic adapatability w as pr oposed.H ow ever,this new strateg y mig ht possibly induce infeasible so lutio ns.T hus,a new pr oposition concerning the neig hbor hood sw apping str ategy w as presented and pr ov ed,w hich could be used to v erify whether a neighbor ho od swapping w as accept able or not.Based on this g lo bal neig hbo rhoo d st rateg y,a new alg o r ithm w as develo ped and tested by a gr oup of benchmark instances.T he r esults indicated that the new algo rithm ob tained satisfactor y results both on solut ions quality and computat ion time. Key words:neig hbo rhoo d structur e;crit ical path;Job Sho p scheduling ;neighborho od sw apping;scheduling alg o rithms 0 引言 自从20世纪50年代以来,调度问题相关理论及其应用技术的研究已经发展成为一门重要的学科,从经典的单机调度、并行机调度、车间调度发展到后来的多目标调度、随机调度和模糊调度等内容。调度问题成为从事运筹学、人工智能学和应用数学等学科领域的学者们关注的焦点,相应的应用领域在不断地扩大。随着问题研究的深化,人们对解决 调度问题的难度有了进一步的认识,发展了关于调度算法的有效性和计算复杂性理论,并且证明出许多调度问题包括多数作业车间调度问题(Jo b Shop Scheduling Problem,JSP)都是NP 完备问题[1]。JSP 是利用一组有限资源对一批有限任务在满足给定约束条件下求解最优目标函数的一个复杂的组合优化问题,也是迄今为止人们研究最多、研究成果最丰富、但仍未得到根本解决的问题之一。事实表明,有些NP 完备问题存在有限时间内的可行解,
基于禁忌搜索算法的车辆路径选择 摘要：本文从VRP的提出背景与求解方法出发，阐释了禁忌搜索算法的原理与影响算法性能的关键因素，进而将禁忌搜索算法的思想运用于解决车辆路径问题，在VRP问题初始解的基础上，用禁忌搜索算法优化车辆配送路线，设计出直观且策略易于理解的客户直接排列的解的表示方法，最后将该算法用C语言实现并用于求解VRP问题，测试结果表明该算法可行且解的质量较高。 关键词：车辆路径问题；禁忌搜索；邻域；禁忌表 1.引言 物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径，使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车辆路径问题正是基于这一需求而产生的。求解车辆路径问题（Vehicle Routing Problem简记VRP）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间复杂度呈指数增长，且VRP问题属于NP-hard问题，求解比较困难，因此启发式算法成为求解VRP问题的主要方法。禁忌搜索算法是启发式算法的一种，为求解VRP提供了新的工具。本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌搜索算法。 因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。 2.车辆路径问题的禁忌搜索算法 2.1 车辆路径问题的描述 车辆路径问题的研究目标是对一系列送货点或取货点，确定适当的配送车辆行驶路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。参见下图2.1所示：其中0表示配送中心，1～８表示客户编号。 图2.1 车辆路径问题 在本文中为使得问题易于理解，将该问题描述为：有一定数量的客户，各自有不同数量的货物需求，且每个客户的位置和需求量一定，一个物流中心提供这些货物，并有一个车队负责分送货物，每台配送车辆的载重量一定，这里假设车辆的型号一致，即最大载重量和最
目录 一、摘要 (2) 二、禁忌搜索简介 (2) 三、禁忌搜索的应用 (2) 1、现实情况 (2) 2、车辆路径问题的描述 (3) 3、算法思路 (3) 4、具体步骤 (3) 5、程序设计简介 (3) 6、算例分析 (4) 四、禁忌搜索算法的评述和展望 (4) 五、参考文献 (5)
禁忌搜索及应用 一、摘要 工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 二、禁忌搜索简介 禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的meta-heuristic算法。 迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 禁忌搜索是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu length）、候选解（candidate）、藐视准则（aspiration criterion）等概念。 三、禁忌搜索的应用 禁忌搜索应用的领域多种多样，下面我们简单的介绍下基于禁忌搜索算法的车辆路径选择。 1、现实情况 物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径，使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车辆路径问题正是基于这一需求而产生的。求解车辆路径问题（vehicle routing problem简记vrp）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间复杂度呈指数增长，且vrp问题属于np-hard问题，求解比较困难，因此启发式算法成为求解vrp问题的主要方法。禁忌搜索算法是启发式算法的一种，为求解vrp提供了新的工具。本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌搜索算法。 因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最
禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法1，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。 为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索 中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个没有兔子留守的地方优越性太突出，超过 了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。 伪码表达 procedure tabu search; begin initialize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va>best_to_far then {va is a string in the tabu list} begin
6.2基于均衡原理的LRP 算法设计 6.2.1基于均衡原理的LRP 算法整体流程 基于均衡原理的LRP 算法整体流程如下： step1：初始化，设置整体收敛性判断参数δ； step2：随机生成一组LRP 选址问题的解D ，求出相应的目标值F ； step3：根据上层解D ，利用Frank-Wolfe 算法（见6.2.3节）求出各客户的 货物总量Q j 及客户在各配送中心的货物均衡分配量x j i ,； step4：根据D 及x j i ,运用禁忌算法求解VRP 问题(见6.2.4节)，得出各配送 中对各客户的单位货物配送费用C j i ,； step5：根据 x j i ,及公式（6-8）求出下层 x j i ,与 d i 的关系y d x j i i j i W ,,+ =； step6：将LRP 模型上层目标函数中用代替，并代入下层求得的Q j 和C j i ,，运用禁忌算法 求得新的LRP 选址规划的解'Z 及目标函数'F （见6.2.2节）； step7：如果δ<-F F ' ，转step8，算法结束，D 、F 为LRP 的最终解和解值；否则 '':,:F F D D ==，转step3； step8：算法结束。 6.2.2 LRP 选址规划的禁忌算法 模型上层是基于0-1整数规划的选址问题。由于选址问题是NP-hard ，如果 用精确算法求解，对节点数目的限制将有严格的要求。本章根据模型的特点， 采用禁忌算法优化产业选址问题。 1．解的构造和初始解的生成 采用二进制编码，编码长度为潜在的配送中心地点数量N T ，对于编码中位置i ，1表示选中i 点作为厂址，0表示没有选中。对于解中任意点i ，产生随机数δ，如果N T N /≥δ，则置i 点为0，否则置1。重复以上步骤m 次，得到初始解。 2．邻域的搜索 根据本章选址问题的特点，设计了三种邻域操作，分别为自身取反、2-swap 交换和2-opt 交换。 1）．自身取反。为单点操作，即选择解中i 点，对该点的值取反； 2）．2-swap 交换。为双点操作，选择解中两点进行交换，其它位置的值不变。例如解001101中的2、6点被选中，则2-swap 交换后变为：011100； 3）．2-opt 交换。为多点操作，选择解中两点进行交换，同时两点之间的值逆序改变。例如解001101中的2、6点被选中，则2-swap 交换后变为：010110；
禁忌搜索算法 又名“tabu搜索算法” 为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best to far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。 伪码表达： procedure tabu search; begin initialize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va>best_to_far then {va is a string in the tabu list} begin cur:=va; let va take place of the oldest string in the tabu list; best_to_far:=va; end else begin cur:=vn; let vn take place of the oldest string in the tabu list; end; until (termination-condition); end; 以上程序中有关键的几点：
无时限单向配送车辆优化调度问题的禁忌搜索算法无时限单向配送车辆优化调度问题，是指在制定配送路线时不考虑客户对货物送到（或取走）时间要求的纯送货（或纯取货）车辆调度问题。 无时限单向配送车辆优化调度问题可以描述为：从某配送中心用多台配送车辆向多个客户送货，每个客户的位置和需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足一下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量； （2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离； （3）每个客户的需求必须满足，且只能由一台配送车辆送货。 一、禁忌搜索算法的原理 禁忌搜索算法是解决组合优化问题的一种优化方法。该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来挑出局部最优点。 在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的领域中搜索若干个解，取其中的最优解作为新的当前解。为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。 二、算法要素的设计 1.禁忌对象的确定 禁忌对象是指禁忌表中被禁的那些变化元素。由于解状态的变化可以分为解的简单变化、解向量分量的变化和目标值变化三种情况，则在确定禁忌对象时也有相对应的三种禁忌情况。 一般来说，对解的简单变化进行禁忌比另两种的受禁范围要小，因此可能早能造成计算时间的增加，但其优点是提供了较大的搜索范围。 根据配送车辆优化调度问题的特点，可采用对解的简单变化进行禁忌的方法。举例进行说明：当解从x变化到y时，y可能是局部最优解，为了避开局部最优解，禁忌y这一解再度出现，可采用如下禁忌规则：当y的领域中有比它更优的解时，选择更优的解；当y为其领域的局部最优解时，不再选y，而选比y稍差的解。 2.禁忌长度的确定 禁忌长度是指被禁对象不允许被选取的迭代步数，一般是给被禁忌对象x一个数l（称为禁忌长度），要求x在l步迭代内被禁，在禁忌表中采用Tabu(x)=l记忆，每迭代一步，该指标做运算Tabu(x)=l-1，直到Tabu(x)=0时解禁。关于禁忌长度l的选取，可归纳为以下几种情况。 （1）l为常数，可取l=10、（n为领域中邻居的总个数）。这种规则容易在算法中实现。 （2）。此时，l是可以变化的数，其变化的依据是被禁对象的目标函数值和领域的结构。、是确定的数，确定的常用方法是根据问题的规模N，限定变化区间；也可以用领域中邻居的个数n确定变化区间。 禁忌长度的选取同实际问题和算法设计者的经验有紧密联系，同时它也会影响计算的复杂性，过短会造成循环的出现，过长又会造成计算时间的增加。 3.候选集合的确定 候选集合由领域中的邻居组成，常规的方法是从领域中选择若干个目标函数值或评价值最佳的邻居。
禁忌搜索算法 2009210042 李同玲运筹学与控制论 搜索是人工智能的一个基本问题，一个问题的求解过程就是搜索。人工智能在各应用领域中，被广泛的使用。现在，搜索技术渗透在各种人工智能系统中，可以说没有哪一种人工智能的应用不用搜索方法。 禁忌搜索算法(Tabu Search或Taboo Search,简称TS)的思想最早由Glover (美国工程院院士，科罗拉多大学教授)在1977年提出，它是对局部邻域搜索的一种扩展，是一种全局邻域搜索算法，是人工智能的一种体现，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 1.1引言 1.1.1局部邻域搜索 局部邻域搜索是基于贪婪思想持续地在当前的邻域中进行搜索，虽然算法通用易实现，且容易理解，但其搜索性能完全依赖于邻域结构和初始解，尤其容易陷入局部极小而无法保证全局优化性。 局部搜索的算法可以描述为：
1、 选定一个初始可行解：0x ； 记录当前最优解0best x x =，()best T N x =； 2、 当\best T x =?时，或满足其他停止运算准则时，输出计算结果， 停止运算；否则，从T 中选一集合S ，得到S 中的最好解now x ；若()()now best f x f x <，则b e s t n o w x x =，()best T N x =；否则，\T T S =；重复2，继续搜索 这种邻域搜索方法容易实现理解，容易实现，而且具有很好的通用性，但是搜索结果完全依赖于初始解和邻域的结构，而且只能搜索到局部最优解。为了实现全局搜索，禁忌搜索采用允许接受劣解来逃离局部最优解。针对局部领域搜索，为了实现全局优化，可尝试的途径有：以可控性概率接受劣解来逃逸局部极小，如模拟退火算法；扩大领域搜索结构，如TSP 的2-opt 扩展到k-opt ；多点并行搜索，如进化计算；变结构领域搜索（ Mladenovic et al,1997）；另外，就是采用TS 的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。 1.1.2禁忌搜索算法的基本思想 禁忌搜索算法的基本思想就是在搜索过程中将近期的历史上的搜索过程存放在禁忌表（Tabu List ）中，阻止算法重复进入，这样就有效地防止了搜索过程的循环。禁忌表模仿了人类的记忆功能，禁忌搜索因此得名，所以称它是一种智能优化算法。 具体的思路如下：禁忌搜索算法采用了邻域选优的搜索方法，为了能逃离局部最优解，算法必须能够接受劣解，也就是每一次迭代得到的解不必一定优于原来的解。但是。一旦接受了劣解，迭代就可能