Effective Heuristics for the GPS Survey Network of Malta: Simulated Annealing and Tabu Search Techniques

A GPS network can be defined as a set of stations, co-ordinated by a series of sessions formed by placing receivers on the stations. This paper shows how to search for the best order in which to observe these sessions giving the cheapest schedule. The complexity of observing GPS networks increases with their size and become highly difficult to solve effectively. To obtain good methods to solve this problem a new area of research is implemented. This area is based on developed heuristic techniques that provide an optimal or near optimal solution for large networks. Comparing their outcome in terms of solution quality and computational effort proves the performance of the developed techniques.     

An Application of Tabu Search Heuristic for the Maximum Edge-Weighted Subgraph Problem

The purpose of this article is to describe an efficient search heuristic for the Maximum Edge-weighted Subgraph (MEwS) problem. This problem requires to find a subgraph such that the sum of the weights associated with the edges of the subgraph is maximized subject to a cardinality constraint. In this study a tabu search heuristic for the MEwS problem is proposed. Different algorithms to obtain an initial solution are presented. One neighborhood search strategy is also proposed. Preliminary computational results are reported for randomly generated test problems of MEwS problem with different densities and sizes. For most of test problems, the tabu search heuristic found good solutions. In addition, for large size test problems, the tabu search outperformed the local search heuristic appearing in the literature.     

Solution of the Cumulative Assignment Problem With a Well-Structured Tabu Search Method

The Cumulative Assignment Problem is an NP-complete problem obtained by substituting the linear objective function of the classic Linear Assignment Problem, with a non-linear cumulative function. In this paper we present a first attempt to solve the Cumulative Assignment Problem with metaheuristic techniques. In particular we consider two standard techniques, namely the Simulated Annealing and the Multi-Start methods, and we describe the eXploring Tabu Search: a new structured Tabu Search algorithm which uses an iterative multi-level approach to improve the search. The new method is analyzed through extensive computational experiments and proves to be more effective than the standard methods.     

Tabu Search with Simple Ejection Chains for Coloring Graphs

We present a Tabu Search (TS) method that employs a simple version of ejection chains for coloring graphs. The procedure is tested on a set of benchmark problems. Empirical results indicate that the proposed TS implementation outperforms other metaheuristic methods, including Simulated Annealing, a previous version of Tabu Search and a recent implementation of a Greedy Randomized Adaptive Search Procedure (GRASP).     

A Tabu Search Based Approach for Solving a Class of Bilevel Programming Problems in Chemical Engineering

In this paper an approach based on the tabu search paradigm to tackle the bilevel programming problems is presented. The algorithm has been tested for a number of benchmark problems and the results obtained show superiority of the approach over the conventional methods in solving such problems.     

Tabu Search Based Procedure for Solving the 0-1 MultiObjective Knapsack Problem: The Two Objectives Case

We consider in this paper the solving of 0-1 knapsack problems with multiple linear objectives. We present a tabu search approach to generate a good approximation of the efficient set. The heuristic scheme is included in a redu tion decision space framework. The case of two objectives is developed in this paper. TS principles viewed into the multiobjective context are discussed. According to a prospective way, several variations of the algorithm are investigate. Numerical experiments are reported and compared with available exact efficient solutions. Intuitive justifications for the observed empirical behavior of the procedure and open questions are discussed.     

An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem

This paper proposes a new tabu search algorithm for multi-objective combinatorial problems with the goal of obtaining a good approximation of the Pareto-optimal or efficient solutions. The algorithm works with several paths of solutions in parallel, each with its own tabu list, and the Pareto dominance concept is used to select solutions from the neighborhoods. In this way we obtain at each step a set of local nondominated points. The dispersion of points is achieved by a clustering procedure that groups together close points of this set and then selects the centroids of the clusters as search directions. A nice feature of this multi-objective algorithm is that it introduces only one additional parameter, namely, the number of paths. The algorithm is applied to the permutation flowshop scheduling problem in order to minimize the criteria of makespan and maximum tardiness. For instances involving two machines, the performance of the algorithm is tested against a Branch-and-Bound algorithm proposed in the literature, and for more than two machines it is compared with that of a tabu search algorithm and a genetic local search algorithm, both from the literature. Computational results show that the heuristic yields a better approximation than these algorithms.     

Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems

In this paper, a computational algorithm, named RST2ANU algorithm, has been developed for solving integer and mixed integer global optimization problems. This algorithm, which primarily is based on the original controlled random search approach of Price [22i], incorporates a simulated annealing type acceptance criterion in its working so that not only downhill moves but also occasional uphill moves can be accepted. In its working it employs a special truncation procedure which not only ensures that the integer restrictions imposed on the decision variables are satisfied, but also creates greater possibilities for the search leading to a global optimal solution. The reliability and efficiency of the proposed RST2ANU algorithm has been demonstrated on thirty integer and mixed integer optimization problems taken from the literature. The performance of the algorithm has been compared with the performance of the corresponding purely controlled random search based algorithm as well as the standard simulated annealing algorithm. The performance of the method on mathematical models of three realistic problems has also been demonstrated.     

Derivative-Free Filter Simulated Annealing Method for Constrained Continuous Global Optimization

In this paper, a simulated-annealing-based method called Filter Simulated Annealing (FSA) method is proposed to deal with the constrained global optimization problem. The considered problem is reformulated so as to take the form of optimizing two functions, the objective function and the constraint violation function. Then, the FSA method is applied to solve the reformulated problem. The FSA method invokes a multi-start diversification scheme in order to achieve an efficient exploration process. To deal with the considered problem, a filter-set-based procedure is built in the FSA structure. Finally, an intensification scheme is applied as a final stage of the proposed method in order to overcome the slow convergence of SA-based methods. The computational results obtained by the FSA method are promising and show a superior performance of the proposed method, which is a point-to-point method, against population-based methods.     

A Tabu Search Algorithm for Quadratic 0—1 Programming Problem

1.IntroductionThemathematicalmodelofaquaduatico-1programmingproblemisasfollows:MinimizesubjecttwhereI,AsfaraspaperL1'2Jcanseemedel(I)(fordu=O)isveryimPOrtantinthemarshallingofsinglegrouptrainbetweenmarshallingstationsinrailwaynetworkandthemarshallingoftraininnetw0rkwiththetw0types0fvehiclefl0w,butproblem(I)isNP-C.C0nsiderarelax-ationproblemasf0llows:MinimizeIngeneral,solvingrelaxati0nproblemiseasierthansolvingcombinatiorial0ptimalpr0b-lem,thesameaslinearpr0grammingproblemissolvableinPOly…     

一种改进的禁忌搜索算法及其在连续全局优化中的应用

禁忌搜索算法是一种元启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题,提出了一种改进的禁忌搜索算法,并进行了理论分析和数值实验。数值实验表明,对于连续函数全局优化问题的求解该算法是可行有效的,并且结构简单,迭代次数较少,是一种较好的全局启发式优化算法。     

On Using Tabu Search for Design Automation of VLSI Systems

Tabu search is a meta-heuristic problem solving technique that, when applied carefully, provides near optimal solutions in a very short time. In this paper, we have described the use of tabu search for solving problems related to very large scale integrated (VLSI) circuit design automation. Specifically, we have demonstrated the use for VLSI circuit partitioning and placement. We present a tabu search based circuit bi-partitioning technique that partitions circuits with the goal of minimizing the size of the cutset between the partitions. Then, we use tabu search techniques along with force directed placement techniques to accomplish the physical placement of VLSI circuits on regular two-dimensional arrays with the goal of minimizing the placement time. We use empirical data from partitioning and placement of benchmark circuits to test our techniques. Our methods show improvement when compared to partitioning techniques from the literature and commercially available placement tools. Relative to the literature, our tabu search bi-partitioning technique improves on the best known minimum cuts for several benchmark circuits. Relative to commercially available computer aided design tools, our tabu search based placement approach shows dramatic (20×) speedup in execution time without negative impact on the quality of the solution.     

一种改进的禁忌搜索算法及其在选址问题中的应用

本文研究了选址问题中无容量限制的p-中值问题,在Rolland等人提出的有效禁忌搜索算法基础上,提出了一种以目标函数变化量作为评价函数的改进禁忌搜索算法,并进行了理论分析,然后将其与有效禁忌搜索算法作了性能比较.通过比较三个公共测试数据集的计算结果,验证了本文提出的禁忌搜索算法的可行性和有效性.     

Improved Bounds for Ternary Linear Codes of Dimension 8 Using Tabu Search

In this paper, new codes of dimension 8 are presented which give improved bounds on the maximum possible minimum distance of ternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Twenty three codes are given which improve or establish the bounds for ternary codes. In addition, a table of upper and lower bounds for d ₃(n, 8) is presented for n 200.     

Statistical search methods for lotsizing problems

This paper reports on our experiments with statistical search methods for solving lotsizing problems in production planning. In lotsizing problems the main objective is to generate a minimum cost production and inventory schedule, such that (i) customer demand is satisfied, and (ii) capacity restrictions imposed on production resources are not violated. We discuss our experiences in solving these, in general NP-hard, lotsizing problems with popular statistical search techniques like simulated annealing and tabu search. The paper concludes with some critical remarks on the use of statistical search methods for solving lotsizing problems.     

Design and Evaluation of Tabu Search Algorithms for Multiprocessor Scheduling

Using a simple multiprocessor scheduling problem as a vehicle, we explore the behavior of tabu search algorithms using different tabu, local search and list management strategies. We found that random blocking of the tail of the tabu list always improved performance; but that the use of frequency-based penalties to discourage frequently selected moves did not. Hash coding without conflict resolution was an effective way to represent solutions on the tabu list. We also found that the most effective length of the tabu list depended on features of the algorithm being used, but not on the size and complexity of the problem being solved. The best combination of features included random blocking of the tabu list, tasks as tabus and a greedy local search. An algorithm using these features was found to outperform a recently published algorithm solving a similar problem.     

多目标交互可行方向法

对于多目标非线性规划问题，本文借助修正Zoutendijk法的可行方向思想，利用ε－约束问题的K－T乘子和决策者提供的权衡比产生变形标量化问题的可行下降方向，逐步求得决策者满意的有效解．     

A Distributed Evolutionary Simulated Annealing Algorithm for Combinatorial Optimisation Problems

In this paper, the Evolutionary Simulated Annealing (ESA) algorithm, its distributed implementation (dESA) and its application to two combinatorial problems are presented. ESA consists of a population, a simulated annealing operator, instead of the more usual reproduction operators used in evolutionary algorithms, and a selection operator. The implementation is based on a multi island (agent) system running on the Distributed Resource Machine (DRM), which is a novel, scalable, distributed virtual machine based on Java technology. As WAN/LAN systems are the most common multi-machine systems, dESA implementation is based on them rather than any other parallel machine. The problems tackled are well-known combinatorial optimisation problems, namely, the classical job-shop scheduling problem and the uncapacitated facility location problem. They are difficult benchmarks, widely used to measure the efficiency of metaheuristics with respect to both the quality of the solutions and the central processing unit (CPU) time spent. Both applications show that dESA solves problems finding either the optimum or a very near optimum solution within a reasonable time outperforming the recent reported approaches for each one allowing the faster solution of existing problems and the solution of larger problems.