下载文档原格式
车间排程优化问题的禁忌搜索算法研究车间排程优化是制造业中一个重要的问题，通过合理地安排生产任务，可以提高生产效率和资源利用率，减少生产成本和交货期延误。
而禁忌搜索算法作为一种经典的启发式优化算法，可以有效地解决这个问题。
一、问题描述车间排程优化问题是指在给定的工作车间、机器和作业序列的情况下，通过合理的调度工序和机器安排，最大程度地提高生产效率。
该问题涉及到多个因素的综合考虑，如工序之间的先后关系、机器之间的冲突、作业的紧急程度等。
二、禁忌搜索算法原理禁忌搜索算法是一种通过维护一个禁忌列表来避免搜索过程中陷入局部最优解的方法。
它基于贪婪策略，在每一步选择移动方案时，优先考虑能够带来最大改善的邻域解。
同时，它还引入了一个禁忌列表，记录了已经搜索过的解禁忌信息。
在搜索过程中，如果发现一个解与禁忌列表中的解相似度太高，则不会继续搜索该解，以避免重复的计算和陷入局部最优解。
三、禁忌搜索算法在车间排程优化中的应用禁忌搜索算法在车间排程优化中有着广泛的应用。
它可以针对车间排程问题的各种约束条件，自动调整工序的先后次序和机器的分配，以达到最优的排程效果。
1. 邻域解生成禁忌搜索算法中的邻域解一般通过交换相邻工序的位置来产生。
在车间排程中，邻域解的生成可以通过调整工序的先后次序和机器的分配来实现。
通过确定合适的邻域解生成规则，禁忌搜索算法能够快速生成多个可行解，为搜索过程提供了丰富的选择。
2. 目标函数定义在车间排程中，目标函数一般包括生产效率、资源利用率、成本和交货期延误等多个指标。
禁忌搜索算法可以通过合理定义目标函数，将多个指标进行综合考虑，并制定相应的优化策略。
3. 禁忌搜索策略禁忌搜索算法通过维护一个禁忌列表，避免搜索过程中陷入局部最优解。
禁忌列表中的每个元素记录了一个解的局部信息，如交换的工序、机器的分配等。
当在搜索过程中发现一个解与禁忌列表中的解相似度太高时，禁忌搜索算法将终止搜索该解并选择其他的邻域解，以保证搜索的多样性和全局最优解的寻找。
禁忌算法心得体会禁忌算法是一种常用的优化算法，它通过维护一个禁忌表来避免搜索过程中陷入局部最优解。
在实际应用中，禁忌算法常常能够取得很好的效果。
在我使用禁忌算法的过程中，我总结了一些心得体会，希望能够对大家有所帮助。
禁忌表的设计禁忌表是禁忌算法的核心，它记录了搜索过程中已经搜索过的解，以及这些解的一些属性。
禁忌表的设计对禁忌算法的性能有着很大的影响。
在我的实践中，我总结了以下几点：禁忌表的大小禁忌表的大小是禁忌算法性能的一个重要参数。
如果禁忌表太小，那么搜索过程中可能会出现重复搜索已经搜索过的解的情况，从而浪费时间。
如果禁忌表太大，那么搜索过程中可能会出现搜索空间过大的情况，从而导致搜索时间过长。
因此，禁忌表的大小需要根据具体问题进行调整。
禁忌表的属性禁忌表的属性是指禁忌表记录的解的一些属性，例如解的质量、解的结构等。
禁忌表的属性需要根据具体问题进行选择。
在我的实践中，我发现，如果禁忌表的属性能够反映出问题的特点，那么禁忌算法的性能会更好。
禁忌表的更新策略禁忌表的更新策略是指禁忌表中记录的解的禁忌期限如何更新。
禁忌表的更新策略需要根据具体问题进行选择。
在我的实践中，我发现，如果禁忌表的更新策略能够反映出问题的特点，那么禁忌算法的性能会更好。
禁忌算法的参数禁忌算法有很多参数，例如禁忌表的大小、禁忌期限、邻域结构等。
这些参数对禁忌算法的性能有着很大的影响。
在我的实践中，我总结了以下几点：禁忌期限禁忌期限是指禁忌表中记录的解的禁忌期限。
禁忌期限需要根据具体问题进行选择。
在我的实践中，我发现，如果禁忌期限能够反映出问题的特点，那么禁忌算法的性能会更好。
邻域结构邻域结构是指禁忌算法中用于生成邻域解的方法。
邻域结构需要根据具体问题进行选择。
在我的实践中，我发现，如果邻域结构能够反映出问题的特点，那么禁忌算法的性能会更好。
禁忌表的大小禁忌表的大小是禁忌算法性能的一个重要参数。
禁忌表的大小需要根据具体问题进行调整。
北航最优化大作业1.引言旅行商问题（Traveling Salesman Problem，TSP）是一种经典的组合优化问题，目标是找到一条路径，使得旅行商从起点出发，途经所有城市一次后返回起点，并且总路径长度最短。
TSP问题具有NP-hard的特性，寻找最优解是一个非常具有挑战性的任务。
本文将基于禁忌算法，探讨TSP问题的求解方法。
2.禁忌算法简介禁忌算法是一种基于局部的元启发式算法，通过在过程中禁止一定的动作来跳出局部最优解，以期望获得更好的全局最优解。
算法通过引入禁忌表和禁忌长度等机制，避免过程中陷入局部最优解。
3.TSP问题的数学建模假设有n个城市，城市之间的距离可以表示为一个n×n的距离矩阵D。
TSP问题的目标可以定义为：min ∑_(i=1)^n ∑_(j=1)^(n) D_ij*x_ijs.t. ∑_(i=1)^n x_ij=1,∑_(j=1)^n x_ij=1,∀i ≠ jx_ij∈{0,1}, 1≤i,j≤n其中x_ij表示城市i与城市j之间的路径是否存在，1表示存在，0表示不存在。
4.禁忌算法在TSP问题中的应用（1）初始化选取一个起始解x，计算其路径长度f(x)。
将x设为当前解x_best，将f(x)设为当前解的最优值f_best。
（2）选择邻域解选择当前解的一个邻域解x'，使得x'与x只有一个位置上的交换。
通过随机选择两个位置，进行交换操作。
（3）禁忌判断如果邻域解x'的路径长度f(x')小于当前解的最优值f_best，则更新f_best为f(x')，并将x'设为新的当前解。
否则，比较x'与当前解的禁忌情况。
（4）禁忌更新如果x'未在禁忌表中，或者禁忌表中对应的禁忌周期已过，则将x'设为新的当前解。
否则，选择一个路径长度较短的邻域解x''，即使其路径长度f(x'')大于f_best。
禁忌搜索算法
1. 背景介绍
禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。
在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。
使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用。
禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。
为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。
TS是人工智能的一种体现，是局部领域搜索的一种扩展。
禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等影响禁忌搜索算法性能的关键因素。
迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。
2. 国内外发展。
忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。
TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。
相对于模拟退火和遗传算法，TS是又一种搜索特点不同的meta-heuristic算法。
迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。
本章将主要介绍禁忌搜索的优化流程、原理、算法收敛理论与实现技术等内容。
1. 引言局部领域搜索是基于贪婪思想持续地在当前解的领域中进行搜索，虽然算法通用易实现，且容易理解，但其搜索性能完全依赖于领域结构和初解，尤其窥陷入局部极小而无法保证全局优化性。
针对局部领域搜索，为了实现全局优化，可尝试的途径有：以可控性概率接受劣解来逃逸局部极小，如模拟退火算法；扩大领域搜索结构，如TSP的2opt扩展到k-opt；多点并行搜索，如进化计算；变结构领域搜索（Mladenovic et al,1997）；另外，就是采用TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。
禁忌搜索是人工智能的一种体现，是局部领域搜索的一种扩展。
禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。
禁忌搜索涉及到领域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等概念，我们首先用一个示例来理解禁忌搜索及其各重要概念，而后给出算法的一般流程。
2.禁忌搜索示例组合优化是TS算法应用最多的领域。
置换问题，如TSP、调度问题等，是一大批组合优化问题的典型代表，在此用它来解释简单的禁忌搜索算法的思想和操作。
对于n元素的置换问题，其所有排列状态数为n!，当n较大时搜索空间的大小将是天文数字，而禁忌搜索则希望仅通过探索少数解来得到满意的优化解。
首先，我们对置换问题定义一种邻域搜索结构，如互换操作（SW AP），即随机交换两个点的位置，则每个状态的邻域解有Cn2=n（n一1）/2个。
称从一个状态转移到其邻域中的另一个状态为一次移动（move），显然每次移动将导致适配值（反比于目标函数值）的变化。
其次，我们采用一个存储结构来区分移动的属性，即是否为禁忌“对象”在以下示例中：考虑7元素的置换问题，并用每一状态的相应21个邻域解中最优的5次移动（对应最佳的5个适配值）作为候选解；为一定程度上防止迂回搜索，每个被采纳的移动在禁忌表中将滞留3步（即禁忌长度），即将移动在以下连续3步搜索中将被视为禁忌对象；需要指出的是，由于当前的禁忌对象对应状态的适配值可能很好，因此在算法中设置判断，若禁忌对象对应的适配值优于“best so far”状态，则无视其禁忌属性而仍采纳其为当前选择，也就是通常所说的藐视准则（或称特赦准则）。
可见，简单的禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中领域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。
需要指出的是：
（1）首先，由于TS是局部领域搜索的一种扩充，因此领域结构的设计很关键，它决定了当前解的领域解的产生形式和数目，以及各个解之间的关系。
（2）其次，出于改善算法的优化时间性能的考虑，若领域结构决定了大量的领域解（尤其对大规模问题，如TSP的SW AP操作将产生Cn2个领域解），则可以仅尝试部分互换的结果，而候选解也仅取其中的少量最佳状态。
（3）禁忌长度是一个很重要的关键参数，它决定禁忌对象的任期，其大小直接进而影响整个算法的搜索进程和行为。
同时，以上示例中，禁忌表中禁忌对象的替换是采用FIFO方式
（不考虑藐视准则的作用），当然也可以采用其他方式，甚至是动态自适应的方式。
（4）藐视准则的设置是算法避免遗失优良状态，激励对优良状态的局部搜索，进而实现全局优化的关键步骤。
（5）对于非禁忌候选状态，算法无视它与当前状态的适配值的优劣关系，仅考虑它们中间的最佳状态为下一步决策，如此可实现对局部极小的突跳（是一种确定性策略）。
（6）为了使算法具有优良的优化性能或时间性能，必须设置一个合理的终止准则来结束整个搜索过程。
此外，在许多场合禁忌对象的被禁次数（frequency）也被用于指导搜索，以取得更大的搜索空间。
禁忌次数越高，通常可认为出现循环搜索的概率越大。
3.禁忌搜索算法流程通过上述示例的介绍，基本上了解了禁忌搜索的机制和步骤。
简单TS 算法的基本思想是：给定一个当前解（初始解）和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“best so far”状态，则忽视其禁忌特性，用其替代当前解和“best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。
条理化些，则简单禁忌搜索的算法步骤可描述如下：
（1）给定算法参数，随机产生初始解x，置禁忌表为空。
（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。
（3）利用当前解工的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。
（4）对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤。
（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。
（6）转步骤（2）。
同时，上述算法可用如下流程框图更直观地描述，如图4．1．1。
我们可以明显地看到，邻域函数、禁忌对象、禁忌表和藐视准则，构成了禁忌搜索算法的关键。
其中，邻域函数沿用局部邻域搜索的思想，用于实现邻域搜索；禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；藐视准则，则是对优良状态的奖励，它是对禁忌策略的一种放松。
需要指出的是，上述算法仅是一种简单的禁忌搜索框架，对各关键环节复杂和多样化的设计则可构造出各种禁忌搜索算法。
同时，算法流程中的禁忌对象，可以是搜索状态，也可以是特定搜索操作，甚至是搜索目标值等。
同时，与传统的优化算法相比，TS算法的主要特点是：
（1）在搜索过程中可以接受劣解，因此具有较强的“爬山”能力；
（2）新解不是在当前解的邻域中随机产生，而或是优于“best so far”的解，或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。
由于TS算法具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，从而增强获得更好的全局最优解的概率，所以TS算法是一种局部搜索能力很强的全局迭代寻优算法。
