禁忌搜索求解TSP问题

本文采用改进的禁忌搜索算法求解TSP问题,该算法是通过禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,最终实现全局优化。实验结果证明该算法的可行性。     

基于组合禁忌搜索的并行测试任务调度研究

任务调度是研究并行测试技术的核心问题。建立了该问题的数学模型,提出了一种基于组合禁忌搜索的并行测试任务调度方法,通过任务分组的规则构造较好的初始调度序列,利用禁忌搜索迭代寻找最好的调度序列,快速完成基于测试时间最短的任务调度规划。对实例进行了仿真实验,与基本禁忌搜索算法进行比较,仿真结果验证了该组合禁忌搜索算法的高效性和有效性。     

一类货运车辆调度问题的混合禁忌搜索算法

研究了一类货运车辆调度问题 :带时间窗口车辆装卸货问题 .首先给出了该问题的数学描述 ,通过引入快速局部搜索算法来加快禁忌搜索速度 ,提出了一种求解该问题的混合禁忌搜索算法 ,可以大大减少算法的运行时间而不影响解的质量 ,最后利用两个具有现实规模和复杂度的实例来测试 .结果表明 :本文提出的混合禁忌搜索算法是求解该类货运车辆调度问题的有效、快速算法 .     

一种改进的禁忌搜索算法求解背包问题

提出一种改进的禁忌搜索算法来求解背包问题.该算法基于禁忌搜索技术,并采用I&D策略,同时设计了两种针对局部最优解的变异算子.改进后的算法能有效地弥补标准禁忌算法对初始解依赖的缺陷,同时也避免了搜索停滞的现象.通过对具体实例和随机问题的测试,表明改进后的禁忌搜索算法有更好的性能.     

最小赋权支配集的迭代禁忌搜索算法

最小赋权支配集是一个NP困难的组合优化问题,有着广泛的应用背景。提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法。该算法采用随机贪心构造算法构造初始解,并利用快速的局部禁忌搜索算法寻找局部最优解,通过随机扰动和修复策略来搜索新的区域,以期跳出当前的局部最优解。用顶点数为800到1 000的大规模标准测试例子测试提出的算法。数值实验结果和与现存的启发式算法比较结果表明了算法是有效的。     

禁忌搜索算法解决零空闲流水线调度问题

针对流水线调度这一类NP-Hard难题,深入分析了零空闲流水线调度问题,提出了一种解决零空闲流水线调度问题的基于NEH方法的禁忌搜索算法,建立了以工件的最大完工时间为目标的算法模型.新算法利用NEH启发式算法产生问题的初始解,改善了新算法的搜索性能.利用动态方式更新禁忌表长,提高了新算法的鲁棒性.为了提高算法的运行时效,利用快速搜索算法对提出的禁忌搜索算法进行改进,即采用快速搜索算法作为禁忌搜索的邻域函数,得到另一种改进的禁忌搜索算法.仿真试验结果表明了该算法的有效性及优越性,新算法在流水线生产调度及自动化工程等领域具有较高的实用价值.     

多维背包问题的禁忌搜索求解

借鉴认知心理学有关记忆系统的表述，在禁忌搜索算法中引入长时记忆，构造了基于双禁忌表的禁忌搜索算法。多维0-1背包问题的仿真实验表明，该算法是可行的、有效的。     

解决图着色问题的一种新禁忌搜索算法

为了解决典型的组合优化问题——图顶点着色问题,结合增强SEQ算法和禁忌搜索算法的优点与缺点,提出一种基于增强SEQ的新禁忌搜索算法(SEQTS)。该算法利用增强SEQ算法较强的构造较优解的能力来为禁忌搜索算法构造多个较优初始解,然后进行多初始解禁忌搜索以找到全局最优解。计算机实验的结果表明该算法(SEQTS)有较好的寻优能力,增强了该算法的有效性。     

求解无等待流水调度的基于禁忌搜索的混合算法

本文提出了解决最小完工时间的无等待流水调度问题的基于禁忌搜索的混合算法。算法结合了调度规则和禁忌搜索算法的优点,首先利用调度规则构造较好的初始解,既可以加快禁忌搜索算法的收敛速度,也可以降低整个算法的运算量,使算法有更好的工程实用性;然后使用变邻域结构的禁忌搜索算法改进当前解。在保持可达性的基础上,该算法缩小了邻域规模和减少了计算时间。数值仿真实验表明,该算法是有效的。     

覆盖表生成的禁忌搜索算法

组合测试可以有效检测待测系统中由参数间交互作用而引发的故障.在其30多年的发展过程中,覆盖表生成一直是关键问题之一,相关研究文献已达200多篇.作为一种有效的覆盖表生成算法,已有的禁忌搜索算法在所生成的覆盖表规模上具备一定的优势,但其解的质量和运算速度仍有提升空间;同时,这些算法实际应用能力较差,既不支持约束处理,也无法生成可变力度覆盖表.针对以上问题,提出了一种禁忌搜索算法.该算法从3个方面对已有的算法进行了改进：1）算法参数配置调优分pair-wise和爬山两阶段进行,确保使用较少配置条数最大程度击中最优配置,进一步提高算法生成覆盖表的规模;2）进行算法并行化,加速算法生成覆盖表的速度;3）增加约束处理和变力度处理,使算法可适应多种测试场景.实验结果表明,该算法在固定力度、变力度、带约束等多种类型覆盖表的规模上都具有一定优势,同时,并行化使算法平均加速2.6倍左右.     

A parallel adaptive tabu search approach

This paper presents a new approach for parallel tabu search based on adaptive parallelism. Adaptive parallelism was used to dynamically adjust the parallelism degree of the application with respect to the system load. Adaptive parallelism demonstrates that high-performance computing using a hundred of heterogeneous workstations combined with massively parallel machines is feasible to solve large optimization problems. The parallel tabu search algorithm includes different tabu list sizes and new intensification/diversification mechanisms. Encouraging results have been obtained in solving the quadratic assignment problem. We have improved the best known solutions for some large real-world problems.     

求解可重入并行机调度的混合禁忌搜索算法

为解决带有一台远程服务设备的可重入并行机调度问题,设计了一种混合禁忌搜索算法。针对传统禁忌搜索算法只从单起始点搜索、容易陷入局部最优等缺点,混合禁忌搜索算法设计了一种Restart策略。当传统禁忌搜索算法陷入局部最优时,用Restart策略重新产生初始解以进行禁忌搜索,将传统的禁忌搜索算法从单起始点搜索改进成多起始点搜索。数值实验中将混合禁忌搜索算法与启发式算法CS相比,结果表明该算法具有较高的求解质量,且其计算时间是可接受的。     

Parallel tabu search algorithm for the hybrid flow shop problem

The paper deals with the parallel variant of the scheduling algorithm dedicated to the hybrid flow shop problem. The problem derives from practice of automated manufacturing lines, e.g. for printed packages. The overall goal is to design a new algorithm which merges the performance of the best known sequential approach with the efficient exploitation of parallel calculation environments. In order to fulfill the above aim, there are two methods proposed in this paper: the original fast method of parallel calculation of the criterion function and the local neighborhood parallel search method embedded in the tabu search approach. The theoretical analysis, as well as the original implementation, with the use of vector processing instructions SSE2 supported by suitable data organization, are presented below. Numerical properties of the proposed algorithm are empirically verified on the multi-core processor.     

车辆路径问题的禁忌搜索算法研究

简要回顾了车辆路径问题的禁忌搜索算法的发展现状,提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点：拓展了搜索空间,提高了最优解的效果;是一种将问题进行空间分解的并行算法,可采用多台计算机同时运算以减少整体运行时间。     

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

Feature selection using tabu search method

Selecting an optimal subset from original large feature set in the design of pattern classifier is an important and difficult problem. In this paper, we use tabu search to solve this feature selection problem and compare it with classic algorithms, such as sequential methods, branch and bound method, etc., and most other suboptimal methods proposed recently, such as genetic algorithm and sequential forward (backward) floating search methods. Based on the results of experiments, tabu search is shown to be a promising tool for feature selection in respect of the quality of obtained feature subset and computation efficiency. The effects of parameters in tabu search are also analyzed by experiments.     

物流动态车辆调度问题的混合禁忌搜索算法

在分析动态车辆调度问题的基础上,建立了基于时间轴的动态模型;接着针对该问题在实际中的应用,设计了基于并行节约法和禁忌搜索的混合算法以对动态车辆调度问题进行求解;最后给出算法实现和算例模拟,验证了该算法的有效性。     

基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题

带平衡约束的圆形装填(Packing)问题是一类简化的卫星舱布局优化问题.现提出一个基于禁忌搜索的启发式(TSH)算法对该问题进行求解.算法从任一初始格局出发,应用基于自适应步长的梯度法进行能量极小化.为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索,算法采用了禁忌搜索的策略.在禁忌搜索的过程中,我们对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进.对两组共11个有代表性的算例进行了实算.计算结果表明,TSH算法刷新了其中7个算例的当今国际上的最好纪录,对于其余4个算例,该算法均达到问题的最优解.     

A tabu search algorithm for order acceptance and scheduling

We consider a make-to-order production system, where limited production capacity and order delivery requirements necessitate selective acceptance of the orders. Since tardiness penalties cause loss of revenue, scheduling and order acceptance decisions must be taken jointly to maximize total revenue. We present a tabu search algorithm that solves the order acceptance and scheduling problem on a single machine with release dates and sequence dependent setup times. We analyze the performance of the tabu search algorithm on an extensive set of test instances with up to 100 orders and compare it with two heuristics from the literature. In the comparison, we report optimality gaps which are calculated with respect to bounds generated from a mixed integer programming formulation. The results show that the tabu search algorithm gives near optimal solutions that are significantly better compared to the solutions given by the two heuristics. Furthermore, the run time of the tabu search algorithm is very small, even for 100 orders. The success of the proposed heuristic largely depends on its capability to incorporate in its search acceptance and scheduling decisions simultaneously.