A tabu search approach for the minimum sum-of-squares clustering problem

In this paper, a tabu search based clustering approach called TS-Clustering is proposed to deal with the minimum sum-of-squares clustering problem. In the TS-Clustering algorithm, five improvement operations and three neighborhood modes are given. The improvement operation is used to enhance the clustering solution obtained in the process of iterations, and the neighborhood mode is used to create the neighborhood of tabu search. The superiority of the proposed method over some known clustering techniques is demonstrated for artificial and real life data sets.     

A new hybrid multi-start tabu search for finding hidden purchase decision strategies in WWW based on eye-movements

It is known that the decision strategy performed by a subject is implicit in his/her external behaviors. Eye movement is one of the observable external behaviors when humans are performing decision activities. Due to the dramatic increase of e-commerce volume on WWW, it is beneficial for the companies to know where the customers focus their attention on the webpage in deciding to make a purchase. This study proposes a new hybrid multi-start tabu search (HMTS) algorithm for finding the hidden decision strategies by clustering the eye-movement data obtained during the decision activities. The HMTS uses adaptive memory and employs both multi-start and local search strategies. An empirical dataset containing 294 eye-fixation sequences and a synthetic dataset consisting of 360 sequences were experimented with. We conduct the Sign test and the result shows that the proposed HMTS method significantly outperforms its variants which implement just one strategy, and the HMTS algorithm shows an improvement over genetic algorithm, particle swarm optimization, and K-means, with a level of significance α = 0.01. The scalability and robustness of the HMTS is validated through a series of statistical tests.     

Solving the uncapacitated facility location problem using tabu search

A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. Tabu search is used to guide the solution process when evolving from one solution to another. A move is defined to be the opening or closing of a facility. The net cost change resulting from a candidate move is used to measure the attractiveness of the move. After a move is made, the net cost change of a candidate move is updated from its old value. Updating, rather than re-computing, the net cost changes substantially reduces computation time needed to solve a problem when the problem is not excessively large. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal or near optimal solutions for benchmark test problems from the literature. For randomly generated test problems, this tabu search procedure not only obtained solutions completely dominating those obtained with other heuristic methods recently published in the literature but also used substantially less computation time. Therefore, this tabu search procedure has advantage over other heuristic methods in both solution quality and computation speed.     

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.     

Rough set approach for clustering categorical data using information-theoretic dependency measure

A variety of clustering algorithms exists to group objects having similar characteristics. But the implementations of many of those algorithms are challenging in the process of dealing with categorical data. While some of the algorithms cannot handle categorical data, others are unable to handle uncertainty within categorical data in nature. This is prerequisite for clustering categorical data which also deal with uncertainty. An algorithm, termed minimum-minimum roughness (MMR) was proposed, which uses the rough set theory in order to deal with the above problems in clustering categorical data. Later many algorithms has developed to improve the handling of hybrid data. This research proposes information-theoretic dependency roughness (ITDR), another technique for categorical data clustering taking into account information-theoretic attributes dependencies degree of categorical-valued information systems. In addition, it is second to none of all its predecessors; MMR, MMeR, SDR and standard-deviation of standard-deviation roughness (SSDR). Experimental results on two benchmark UCI datasets show that ITDR technique is better with the baseline categorical data clustering technique with respect to computational complexity and the purity of clusters.     

Categorical data fuzzy clustering: An analysis of local search heuristics

The fuzzy c partition of a set of qualitative data is the problem of selecting the optimal c   centroids that are the most representative of the whole population. Moreover, a set of weights _wij$w_{\mathit{ij}}$ must be determined, describing the fuzzy membership function of pattern i to the cluster represented by centroid j. Both problems are formulated by a single mathematical programming problem, that is an extension of the classic p-median models often used for clustering. The new objective function is neither concave nor convex and the application requires the clustering of many thousands of data, therefore heuristic methods are to be developed to find the best fuzzy partition.     

Eigenvalue assignments in multimachine power systems using tabu search algorithm

Applying tabu search (TS) optimization technique to multimachine power system stabilizer (PSS) design is presented in this paper. The proposed approach employs TS to search for optimal or near optimal settings of PSS parameters that shift the system eigenvalues associated with the electromechanical modes to the left of a vertical line in the s-plane. Incorporation of TS algorithm in PSS design significantly reduces the computational burden. One of the main advantages of the proposed approach is its robustness to the initial guess. The performance of the proposed PSS under different disturbances and loading conditions is investigated for multimachine power systems. The eigenvalue analysis and the nonlinear simulation results show the effectiveness of the proposed PSSs to damp out the local as well as the interarea modes of oscillations and work effectively over a wide range of loading conditions and system configurations.     

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.     

Problem difficulty for tabu search in job-shop scheduling

Tabu search algorithms are among the most effective approaches for solving the job-shop scheduling problem (JSP). Yet, we have little understanding of why these algorithms work so well, and under what conditions. We develop a model of problem difficulty for tabu search in the JSP, borrowing from similar models developed for SAT and other NP-complete problems. We show that the mean distance between random local optima and the nearest optimal solution is highly correlated with the cost of locating optimal solutions to typical, random JSPs. Additionally, this model accounts for the cost of locating sub-optimal solutions, and provides an explanation for differences in the relative difficulty of square versus rectangular JSPs. We also identify two important limitations of our model. First, model accuracy is inversely correlated with problem difficulty, and is exceptionally poor for rare, very high-cost problem instances. Second, the model is significantly less accurate for structured, non-random JSPs. Our results are also likely to be useful in future research on difficulty models of local search in SAT, as local search cost in both SAT and the JSP is largely dictated by the same search space features. Similarly, our research represents the first attempt to quantitatively model the cost of tabu search for any NP-complete problem, and may possibly be leveraged in an effort to understand tabu search in problems other than job-shop scheduling.     

一种基于禁忌搜索的RFID读写器部署算法*

为解决射频识别（RFID）读写器部署问题,提出了一种基于禁忌搜索算法的读写器部署方法。在增加了读写器容量约束的读写器部署模型基础上,采用禁忌搜索算法来寻找最优部署方案。通过仿真可以得出该算法性能稳定。与遗传算法的数据对比,提出的基于禁忌搜索的读写器部署方法在覆盖率大于遗传算法的同时,迭代次数小于遗传算法。     

一种适用于求解TSP问题的改进的禁忌算法

利用传统的禁忌算法的基本思想,针对TSP问题,提出了一种改进的禁忌算法（MTS）。该算法在初始解的生成,邻域结构及禁忌策略方面进行了大的改进,充分地利用了问题本身的启发式信息与禁忌算法的优点。算法首先通过对城市分区,然后对区域连接,生成初始解;同时生成每个城市的k邻居列表,利用k邻居列表和改进的禁忌策略来突破局部最优。通过对CHN144问题及若干TSPLIB中问题的求解,结果表明所提算法能够以较快速度求得较好的满意解。     

A tabu search approach for scheduling hazmat shipments

Vehicle routing and scheduling are two main issues in the hazardous material (hazmat) transportation problem. In this paper, we study the problem of managing a set of hazmat transportation requests in terms of hazmat shipment route selection and actual departure time definition. For each hazmat shipment, a set of minimum and equitable risk alternative routes from origin to destination points and a preferred departure time are given. The aim is to assign a route to each hazmat shipment and schedule these shipments on the assigned routes in order to minimize the total shipment delay, while equitably spreading the risk spatially and preventing the risk induced by vehicles traveling too close to each other. We model this hazmat shipment scheduling problem as a job-shop scheduling problem with alternative routes. No-wait constraints arise in the scheduling model as well, since, supposing that no safe area is available, when a hazmat vehicle starts traveling from the given origin it cannot stop until it arrives at the given destination. A tabu search algorithm is proposed for the problem, which is experimentally evaluated on a set of realistic test problems over a regional area, evaluating the provided solutions also with respect to the total route risk and length.     

An adaptive tabu search algorithm for the capacitated clustering problem

In the Capacitated Clustering Problem, a given set of customers with distinct demands must be partitioned into p clusters with limited capacities. The objective is to find p customers, called medians, from which the sum of the distances to all other customers in the cluster is minimized. In this article, a new adaptive tabu search approach is applied to solve the problem. Initial solutions are obtained by four constructive heuristics that use weights and distances as optimization criteria. Two neighborhood generation mechanisms are used by the local search heuristic: pairwise interchange and insertion . Computational results from 20 instances found in the literature indicate that the proposed method outperforms alternative metaheuristics developed for solving this problem.     

A deterministic tabu search algorithm for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult optimisation problem in vehicle routing with applications where a service must be provided by a set of vehicles on specified roads. A heuristic algorithm based on tabu search is proposed and tested on various sets of benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.     

A tabu search approach to an urban transport problem in northern Spain

In this work we analyze an urban transport problem that the City Council of Burgos, a city in northern Spain, has posed to the authors. Given a fleet of buses and drivers, the problem consists in designing routes and assigning buses to the routes such that the service level is optimized. The optimality of the service level is measured in terms of the waiting time at the bus stops and the duration of the trip. Thus, the problem comprises two decision levels (route design and bus assignment) and differs from other urban transport models found in the literature. In order to solve the problem, we propose two algorithms: one with a local search strategy and another with a tabu search strategy. In both cases, the solutions of the two decision levels are modified in alternating steps. The proposed algorithms obtained significantly better results than the tools currently applied by the transport authorities. In addition, the solutions obtained are very robust with respect to variations on demand, as shown by the experiments.     

A tabu search based approach for graph layout

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of metrics which are used in a weighted fitness function to measure the aesthetic quality of the graph layout. The main goal of this work is to speed up the graph layout process without sacrificing layout quality. To achieve this, we use a tabu search based method that goes through a predefined number of iterations to minimize the value of the fitness function. Tabu search always chooses the best solution in the neighbourhood. This may lead to cycling, so a tabu list is used to store moves that are not permitted, meaning that the algorithm does not choose previous solutions for a set period of time. We evaluate the method according to the time spent to draw a graph and the quality of the drawn graphs. We give experimental results applied on random graphs and we provide statistical evidence that our method outperforms a fast search-based drawing method (hill climbing) in execution time while it produces comparably good graph layouts. We also demonstrate the method on real world graph datasets to show that we can reproduce similar results in a real world setting.     

Regularization of boosted decision stumps using tabu search

This study proposes a novel method to improve the well-known AdaBoost algorithm by combining it with a procedure inspired by tabu search. After each iteration of AdaBoost, the attribute used by the weak learner is placed on the tabu list, which prevents it from being utilized by the subsequent weak learners. The length of the tabu list becomes a new meta-parameter of the learning process and can be tuned based on the cross-validation procedure. This study shows that the proposed approach can improve the original AdaBoost procedure, preventing it from over-fitting to training data. This study also demonstrates that the novel method can act as a regularization procedure. Finally, the paper presents results for the proposed algorithm for 20 classification problems from the UCI repository and for face verification and gender recognition problems.     

A tabu search algorithm for structural software testing

This paper presents a tabu search metaheuristic algorithm for the automatic generation of structural software tests. It is a novel work since tabu search is applied to the automation of the test generation task, whereas previous works have used other techniques such as genetic algorithms. The developed test generator has a cost function for intensifying the search and another for diversifying the search that is used when the intensification is not successful. It also combines the use of memory with a backtracking process to avoid getting stuck in local minima. Evaluation of the generator was performed using complex programs under test and large ranges for input variables. Results show that the developed generator is both effective and efficient.     

A novel hybrid tabu search approach to container loading

The container loading problem, which is significant for a number of industrial sectors, aims to obtain a high space utilisation in the container while satisfying practical constraints. This paper presents a novel hybrid tabu search approach to the container loading problem. A loading heuristic is devised to incorporate heuristic strategies with a handling method for remaining spaces to generate optimal loading arrangements of boxes with stability considered. The tabu search technique, which covers the encoding, evaluation criteria and configuration of neighbourhood and candidate solutions, is used to improve the performance of the loading heuristic. Experimental results with benchmark data show that the hybrid approach provides a better space utilisation than the published approaches under the condition of all loaded boxes with one hundred percent support from below. Moreover, it is shown that the hybrid tabu search can solve problems with the constraints of weight limit and weight distribution with real world data.