共查询到20条相似文献,搜索用时 434 毫秒
1.
Variable neighborhood search for the linear ordering problem 总被引:2,自引:0,他引:2
Carlos G. Garcia Dionisio Prez-Brito Vicente Campos Rafael Martí 《Computers & Operations Research》2006,33(12):3549
Given a matrix of weights, the linear ordering problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This NP-complete problem can also be formulated in terms of graphs, as finding an acyclic tournament with a maximal sum of arc weights in a complete weighted graph. In this paper, we first review the previous methods for the LOP and then propose a heuristic algorithm based on the variable neighborhood search (VNS) methodology. The method combines different neighborhoods for an efficient exploration of the search space. We explore different search strategies and propose a hybrid method in which the VNS is coupled with a short-term tabu search for improved outcomes. Our extensive experimentation with both real and random instances shows that the proposed procedure competes with the best-known algorithms in terms of solution quality, and has reasonable computing-time requirements.Variable neighborhood search (VNS) is a metaheuristic method that has recently been shown to yield promising outcomes for solving combinatorial optimization problems. Based on a systematic change of neighborhood in a local search procedure, VNS uses both deterministic and random strategies in search for the global optimum.In this paper, we present a VNS implementation designed to find high quality solutions for the NP-hard LOP, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input–output tables in economics. Our implementation incorporates innovative mechanisms to include memory structures within the VNS methodology. Moreover we study the hybridization with other methodologies such as tabu search. 相似文献
2.
Miguel ángel González Inés González-Rodríguez Camino R. Vela Ramiro Varela 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2012,16(12):2097-2113
We confront the job shop scheduling problem with sequence-dependent setup times and weighted tardiness minimization. To solve this problem, we propose a hybrid metaheuristic that combines the intensification capability of tabu search with the diversification capability of a genetic algorithm which plays the role of long term memory for tabu search in the combined approach. We define and analyze a new neighborhood structure for this problem which is embedded in the tabu search algorithm. The efficiency of the proposed algorithm relies on some elements such as neighbors filtering and a proper balance between intensification and diversification of the search. We report results from an experimental study across conventional benchmarks, where we analyze our approach and demonstrate that it compares favorably to the state-of-the-art methods. 相似文献
3.
A heuristic algorithm for solving large scale fixed charge network flow problems (FCNFP) based on the dynamic slope scaling
procedure (DSSP) and tabu search strategies is presented. The proposed heuristic integrates the DSSP with short-term memory
intensification and long-term memory diversification mechanisms in the tabu scheme to improve the performance of the pure
DSSP. With the feature of dynamically evolving memory, the enhanced DSSP evaluates the solutions in the search history and
iteratively adjusts the linear factors in the linear approximation of the FCNFP to produce promising search neighborhoods
for good quality solutions. The comprehensive numerical experiments on various test problems ranging from sparse to dense
network structures are reported. The overall comparison of the pure DSSP, the enhanced DSSP, and branch and bound (B&B by
cutting-edge MIP optimizer in CPLEX) is shown in terms of solution quality and CPU time. The results show that the enhanced
DSSP approach has a higher solution quality than the pure DSSP for larger scale problems.
Research has been partially supported by NSF and CRDF grants. 相似文献
4.
In this article, a machine loading problem of a flexible manufacturing system (FMS) is discussed having the bicriterion objectives of minimizing system unbalance and maximizing throughput in the presence of technological constraints such as available machining time and tool slots. A generic 0–1 integer programming formulation with the objective functions and constraints described above has been proposed. A hybrid algorithm based on tabu search and simulated annealing (SA) is employed to solve the problem. The main advantage of this approach is that a short-term memory provided by the tabu list can be used to avoid revisiting the solution while preserving the stochastic nature of the SA method. The proposed methodology has been tested on ten standard problems and the results obtained are compared with those from some of the existing heuristics. 相似文献
5.
This paper deals with the problem of integrating production and distribution planning over periods of a finite horizon. We consider a capacity-constrained plant that produces a number of items distributed by a fleet of homogenous vehicles to customers with known demand for each item in each period. The production planning defines the amount of each item produced in every period, while the distribution planning defines when customers should be visited, the amount of each item that should be delivered to customers, and the vehicle routes. The objective is to minimize production and inventory costs at the plant, inventory costs at the customers and distribution costs. We propose two tabu search variants for this problem, one that involves construction and a short-term memory, and one that incorporates a longer term memory used to integrate a path relinking procedure to the first variant. The proposed tabu search variants are tested on generated instances with up to ten items and on instances from the literature involving a single item. 相似文献
6.
This paper presents a hybrid meta-heuristic search procedure to solve the well-known single machine scheduling problem to minimize the maximum lateness over all jobs, where precedence relations may exist between some of the jobs. The hybridization consists of a well-designed balance between the principles borrowed from an Electromagnetism-like Mechanism algorithm and the characteristics used in a tabu search procedure. The Electromagnetism-like Mechanism (EM) algorithm follows a search pattern based on the theory of physics to simulate attraction and repulsion of solutions in order to move towards more promising solutions. The well-known tabu search enhances the performance of a local search method by using memory structures by prohibiting visited solutions during a certain time of the search process. The hybridization of both algorithms results in an important trade-off between intensification and diversification strategies. These strategies will be discussed in detail. To that purpose, a new set of data instances is used to compare different elements of the hybrid search procedure and to validate the performance of the algorithm. 相似文献
7.
Unconstrained binary quadratic programming problem (UBQP) consists in maximizing a quadratic 0–1 function. It is a well known NP-hard problem and is considered as a unified model for a variety of combinatorial optimization problems. This paper combines a tabu Hopfield neural network (HNN) (THNN) with estimation of distribution algorithm (EDA), and thus a THNN–EDA is proposed for the UBQP. In the THNN, the tabu rule, instead of the original updating rule of the HNN, is used to govern the state transition or updating of neurons to search for the global minimum of the energy function. A probability vector in EDA model is built to characterize the distribution of promising solutions in the search space, and then the THNN is guided by the global search information in EDA model to search better solution in the promising region. Thus, the short term memory of the tabu mechanism in the THNN cooperates with the long term memory mechanism in the EDA to help the network escape from local minima. The THNN–EDA is tested on 21 UBQP benchmark problems with the size ranging from 3000 to 7000, and 48 maximum cut benchmark problems, a special case of the UBQP, with the size ranging from 512 to 3375. Simulation results show that the THNN–EDA is better than the other HNN based algorithms, and is better than or competitive with metaheuristic algorithms and state-of-the-art algorithms. 相似文献
8.
ASLR是防御漏洞攻击的重要保护机制,而容错攻击是绕过ASLR的主要方法之一,即利用容错机制重复尝试搜索内存中的敏感信息。针对目前容错攻击的搜索算法耗时长导致实用性不强的问题,提出了一种结合容错攻击和内存区域统计的ASLR绕过方法。通过软件逆向深入分析容错攻击的原理,包括操作系统和浏览器等软件的容错机制内部实现和容错攻击实现方法;分析进程内存空间分布,统计不同区域的系统DLL分布的平均比例,选定最大概率内存区域搜索DLL并定位关键基址,从而绕过ASLR保护,实验结果证明该方法相对现有方法极大缩短了平均耗时和最大耗时,提高了容错攻击的实用性;探讨了容错攻击更多的应用前景。 相似文献
9.
Using tabu search with ranking candidate list to solve production planning problems with setups 总被引:1,自引:0,他引:1
Yi-Feng Hung Ching-Ping Chen Chia-Chung Shih Ming-Hsiau Hung 《Computers & Industrial Engineering》2003,45(4):615-634
This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy. 相似文献
10.
Tabu搜索在特征选择中的应用 总被引:25,自引:0,他引:25
研究利用Tabu搜索从大特征集中选择一组有效特征的问题.分析了Tabu搜索中
表长、邻域大小和候选解数量等参数对Tabu搜索的影响.对两种特征选择的问题,与经典及
最近新提出的一些特征选择方法如SFS,SBS,GSFS,GSBS,PTA,BB,GA和SFFS,SFBS等
算法的实验比较表明,Tabu搜索在求解时间和解的质量上都取得了满意的结果. 相似文献
11.
Hardware/software partitioning is an essential step in hardware/software co-design. For large size problems, it is difficult to consider both solution quality and time. This paper presents an efficient GPU-based parallel tabu search algorithm (GPTS) for HW/SW partitioning. A single GPU kernel of compacting neighborhood is proposed to reduce the amount of GPU global memory accesses theoretically. A kernel fusion strategy is further proposed to reduce the amount of GPU global memory accesses of GPTS. To further minimize the transfer overhead of GPTS between CPU and GPU, an optimized transfer strategy for GPU-based tabu evaluation is proposed, which considers that all the candidates do not satisfy the given constraint. Experiments show that GPTS outperforms state-of-the-art work of tabu search and is competitive with other methods for HW/SW partitioning. The proposed parallelization is significant when considering the ordinary GPU platform. 相似文献
12.
Tabu search for attribute reduction in rough set theory 总被引:2,自引:0,他引:2
Abdel-Rahman Hedar Jue Wang Masao Fukushima 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(9):909-918
In this paper, we consider a memory-based heuristic of tabu search to solve the attribute reduction problem in rough set theory.
The proposed method, called tabu search attribute reduction (TSAR), is a high-level TS with long-term memory. Therefore, TSAR
invokes diversification and intensification search schemes besides the TS neighborhood search methodology. TSAR shows promising
and competitive performance compared with some other CI tools in terms of solution qualities. Moreover, TSAR shows a superior
performance in saving the computational costs. 相似文献
13.
14.
《Computers & Operations Research》2001,28(9):835-852
This paper evaluates artificial intelligence search methods for multi-machine two-stage scheduling problems with due date penalty, inventory, and machining costs. We compare four search methods: tabu search, simulated annealing, genetic algorithm, and neighborhood search. Computational results show that the tabu search performs best in terms of solution quality. The tabu search also requires much less computational time than the genetic algorithm and simulated annealing. As expected, the neighborhood search needs the smallest computational time, but gives the worst solution quality. To further improve the solution quality and computational time, this paper proposes a two-phase tabu search. The two-phase tabu search sequentially addresses two aspects of sequencing for the same problem, order- and component-based sequencing. The order-based tabu search identifies a sequence for customers’ orders. Starting from the sequence identified for customers’ orders, the component-based tabu search fine-tunes the sequence for components produced at the fabrication stage. The results show that the two-phase tabu search is better in solution quality and computational time than the one-phase tabu search. The difference in solution quality is more pronounced at the early stage of the search.Scope and purposeMost manufacturing firms have some form of separate fabrication and assembly stages. Raw materials are transformed into components at the fabrication stage and the components are then assembled into finished products at the assembly stage. The components and assembly items are typically routed in batch quantities through several machines/work centers in a predetermined order before the finished products are delivered to customers.In this study, we model fabrication and assembly work centers as multi-machine two-stage manufacturing systems where a given machine is used to assemble/produce at least one component/product. The scheduling problem considered in this study involves a scheduling decision that achieves three objectives concurrently: (1) meeting customers’ due dates, (2) minimizing inventory cost, and (3) minimizing machining cost. Each order is an indivisible scheduling element that needs to be delivered to customers on the due date. Each order triggers successive production events from upstream to downstream according to the bill-of-material structure between components and end products.The objective of this paper are three-fold: (1) to present a solution representation for the multi-machine two-stage scheduling problem, (2) to identify the best artificial intelligence search method for this problem based on extensive computational experiments, and (3) to propose a modified tabu search method to further improve the solution quality and computational time. 相似文献
15.
16.
针对具有一定生产期和存储期的快速消费品,从供应链集成的角度研究了确定性需求情形下多工厂、多产品、多客户供应网络的生产—库存—配送协同计划问题,并建立了多周期环境下生产—库存—配送协同计划问题的混合整数规划模型,以协同优化各工厂的生产计划、库存计划与配送计划.提出了求解该模型的禁忌搜索算法方案,且通过设计启发式顺序分配方法生成初始解,采用了从改进的2-opt和λ-interchange的邻域解中产生候选解的策略,给出了提出算法的具体实现过程.最后,通过测试算例的仿真结果,证明了禁忌搜索算法在求解该类问题时具有比混合遗传算法更强的鲁棒性,并且能够得到更好的解. 相似文献
17.
在分析动态车辆调度问题的基础上,建立了基于时间轴的动态模型;接着针对该问题在实际中的应用,设计了基于并行节约法和禁忌搜索的混合算法以对动态车辆调度问题进行求解;最后给出算法实现和算例模拟,验证了该算法的有效性。 相似文献
18.
机车车辆行业作为典型的面向订单的机械制造企业,优化的生产调度方法能提高订单的准时交货,缩短产品的生产周期,提高企业的市场竞争力。订单生产调度问题是典型的NP-hard问题。遗传算法(Genetic Algorithms)为求具有多个约束的复杂问题提供了有效的方法。但是遗传算法的局部搜索能力比较差,在解决订单生产调度问题中存在着明显的不足。本文引入了局部搜索能力很强的禁忌搜索算法,用遗传算法和禁忌搜索算法相结合的混合遗传算法来解决机车车辆行业中面向订单生产调度问题。 相似文献
19.
《Computers & Operations Research》2002,29(1):67-86
An investigation to explicitly define two key elements in tabu search methods is attempted. In this study a functional representation of the tabu list size is presented and a softer aspiration criterion is put forward. Experiments are conducted on a set of p-median problems.Scope and purposeTabu search is a metaheuristic that proved successful in finding good solutions to difficult combinatorial problems that were hard to find otherwise. In this study, we attempt to help the user in the choice of some of the parameters used in this type of heuristics. We based our analysis on the tabu list size and on an implementation on how to define the aspiration criterion. This added information can be valuable to those users who apply these methods in a near systematic manner without relying heavily on experimentations. As an example we used a simple location problem to test the usefulness of these ideas. 相似文献
20.
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. 相似文献