Continuous ant colony system and tabu search algorithms hybridized for global minimization of continuous multi-minima functions

A new hybrid optimization method, combining Continuous Ant Colony System (CACS) and Tabu Search (TS) is proposed for minimization of continuous multi-minima functions. The new algorithm incorporates the concepts of promising list, tabu list and tabu balls from TS into the framework of CACS. This enables the resultant algorithm to avoid bad regions and to be guided toward the areas more likely to contain the global minimum. New strategies are proposed to dynamically tune the radius of the tabu balls during the execution and also to handle the variable correlations. The promising list is also used to update the pheromone distribution over the search space. The parameters of the new method are tuned based on the results obtained for a set of standard test functions. The results of the proposed scheme are also compared with those of some recent ant based and non-ant based meta-heuristics, showing improvements in terms of accuracy and efficiency.     

“MOSS” multiobjective scatter search applied to non-linear multiple criteria optimization

This paper introduces a multiple criteria scatter search to deal with bounded constrained non-linear continuous vector optimization problems of high dimension, applying a MultiStart Tabu Search (TS) as a diversification generation method, each TS works with its own starting point, recency memory, and aspiration threshold. Frequency memory is used to diversify the search and it is shared between the TS. A Pareto relation is applied in order to designate a subset of the best generated solutions to be reference solutions. A choice function called Kramer Choice function is used to divide the reference solutions in two subsets. The Euclidean distance is used as a measure of dissimilarity in order to find diverse solutions to be combined. Linear combinations of the reference solutions are used as a solution combination method. “Balls” in the decision space and the objective space are used to avoid duplications. Different tabu sets with different tabu tenures are employed in the scatter phase to enhance the diversity of the search. The performance of our approach is compared with Pareto-optimal frontiers and three other state-of-the-art MOEAs for a suite test problems taken from the literature.     

DC-GRASP: directing the search on continuous-GRASP

Several papers in the scientific literature use metaheuristics to solve continuous global optimization. To perform this task, some metaheuristics originally proposed for solving combinatorial optimization problems, such as Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search and Simulated Annealing, among others, have been adapted to solve continuous global optimization problems. Proposed by Hirsch et al., the Continuous-GRASP (C-GRASP) is one example of this group of metaheuristics. The C-GRASP is an adaptation of GRASP proposed to solve continuous global optimization problems under box constraints. It is simple to implement, derivative-free and widely applicable method. However, according to Hedar, due to its random construction, C-GRASP may fail to detect promising search directions especially in the vicinity of minima, which may result in a slow convergence. To minimize this problem, in this paper we propose a set of methods to direct the search on C-GRASP, called Directed Continuous-GRASP (DC-GRASP). The proposal is to combine the ability of C-GRASP to diversify the search over the space with some efficient local search strategies to accelerate its convergence. We compare the DC-GRASP with the C-GRASP and other metaheuristics from literature on a set of standard test problems whose global minima are known. Computational results show the effectiveness and efficiency of the proposed methods, as well as their ability to accelerate the convergence of the C-GRASP.     

Three new stochastic local search algorithms for continuous optimization problems

This paper introduces three new stochastic local search metaheuristics algorithms namely, the Best Performance Algorithm (BPA), the Iterative Best Performance Algorithm (IBPA) and the Largest Absolute Difference Algorithm (LADA). BPA and IBPA are based on the competitive nature of professional athletes, in them desiring to improve on their best recorded performances. LADA is modeled on calculating the absolute difference between two numbers. The performances of the algorithms have been tested on a large collection of benchmark unconstrained continuous optimization functions. They were benchmarked against two well-known local-search metaheuristics namely, Tabu Search (TS) and Simulated Annealing (SA). Results obtained show that each of the new algorithms delivers higher percentages of the best and mean function values found, compared to both TS and SA. The execution times of these new algorithms are also comparable. LADA gives the best performance in terms of execution time.     

Managing the tabu list length using a fuzzy inference system: an application to examination timetabling

In this paper, we present an application of Tabu Search (TS) to the examination timetabling problem. One of the drawbacks of this meta-heuristic is related to the need of tuning some parameter (like tabu tenure) whose value affects the performance of the algorithm. The importance of developing an automatic procedure is clear considering that most of the users of timetabling software, like academic staff, do not have the expertise to conduct such tuning. The goal of this paper is to present a method to automatically manage the memory in the TS using a Decision Expert System. More precisely a Fuzzy Inference Rule Based System (FIRBS) is implemented to handle the tabu tenure based on two concepts, “Frequency” and “Inactivity”. These concepts are related respectively with the number of times a move is introduced in the tabu list and the last time (in number of iterations) the move was attempted and prevented by the tabu status. Computational results show that the implemented FIRBS handles well the tuning of the tabu status duration improving, as well, the performance of Tabu Search.     

A novel metaheuristics approach for continuous global optimization

This paper proposes a novel metaheuristics approach to find the global optimum of continuous global optimization problems with box constraints. This approach combines the characteristics of modern metaheuristics such as scatter search (SS), genetic algorithms (GAs), and tabu search (TS) and named as hybrid scatter genetic tabu (HSGT) search. The development of the HSGT search, parameter settings, experimentation, and efficiency of the HSGT search are discussed. The HSGT has been tested against a simulated annealing algorithm, a GA under the name GENOCOP, and a modified version of a hybrid scatter genetic (HSG) search by using 19 well known test functions. Applications to Neural Network training are also examined. From the computational results, the HSGT search proved to be quite effective in identifying the global optimum solution which makes the HSGT search a promising approach to solve the general nonlinear optimization problem.     

Tabu Search for the planar three-index assignment problem

Tabu Search is a very effective method for approximately solving hard combinatorial problems. In the current work we implement Tabu Search for solving the Planar Three-Index Assignment Problem. The problem deals with finding the minimum cost assignment between elements of three distinct sets demanding that every pair of elements, each representing a different set, appears in the same solution exactly once. The solutions of the problems correspond to Latin squares. These structures form the basis of the move generation mechanism employed by the Tabu Search procedures. Standard Tabu Search ideas such as candidate move list, variable tabu list size, and frequency-based memory are tested. Computational results for a range of problems of varying dimensions are presented.     

Comparative analysis of three metaheuristics for short-term open pit block sequencing

This paper presents the application of simulated annealing (SA), Tabu search (TS) and hybrid TS–SA to solve a real-world mining optimisation problem called open pit block sequencing (OPBS). The OPBS seeks the optimum extraction sequences under a variety of geological and technical constraints over short-term horizons. As industry-scale OPBS instances are intractable for standard mixed integer programming (MIP) solvers, SA, TS and hybrid TS–SA are developed to solve the OPBS problem. MIP exact solution is also combined with the proposed metaheuristics to polish solutions in feasible neighbourhood moves. Extensive sensitivity analysis is conducted to analyse the characteristics and determine the optimum sets of values of the proposed metaheuristics algorithms’ parameters. Computational experiments show that the proposed algorithms are satisfactory for solving the OPBS problem. Additionally, this comparative study shows that the hybrid TS–SA is superior to SA or TS in solving the OPBS problem in several aspects.     

A hybrid method combining continuous tabu search and Nelder–Mead simplex algorithms for the global optimization of multiminima functions

Tabu search (TS) is a metaheuristic, which proved efficient to solve various combinatorial optimization problems. However, few works deal with its application to the global minimization of functions depending on continuous variables. To perform this task, we propose an hybrid method combining tabu search and simplex search (SS). TS allows to cover widely the solution space, to stimulate the search towards solutions far from the current solution, and to avoid the risk of trapping into a local minimum. SS is used to accelerate the convergence towards a minimum. The Nelder–Mead simplex algorithm is a classical very powerful local descent algorithm, making no use of the objective function derivatives. A “simplex” is a geometrical figure consisting, in n-dimensions, of (n+1) points. If any point of a simplex is taken as the origin, the n other points define vector directions that span the n-dimension vector space. Through a sequence of elementary geometric transformations (reflection, contraction and extension), the initial simplex moves, expands or contracts. To select the appropriate transformation, the method only uses the values of the function to be optimized at the vertices of the simplex considered. After each transformation, the current worst vertex is replaced by a better one. Our algorithm called continuous tabu simplex search (CTSS) implemented in two different forms (CTSS_single, CTSS_multiple) is made up of two steps: first, an adaptation of TS to continuous optimization problems, allowing to localize a “promising area”; then, intensification within this promising area, involving SS. The efficiency of CTSS is extensively tested by using analytical test functions of which global and local minima are known. A comparison is proposed with several variants of tabu search, genetic algorithms and simulated annealing. CTSS is applied to the design of a eddy current sensor aimed at non-destructive control.     

Tabu Machine: A New Neural Network Solution Approach for Combinatorial Optimization Problems

A new artificial neural network solution approach is proposed to solve combinatorial optimization problems. The artificial neural network is called the Tabu Machine because it has the same structure as the Boltzmann Machine does but uses tabu search to govern its state transition mechanism. Similar to the Boltzmann Machine, the Tabu Machine consists of a set of binary state nodes connected with bidirectional arcs. Ruled by the transition mechanism, the nodes adjust their states in order to search for a global minimum energy state. Two combinatorial optimization problems, the maximum cut problem and the independent set problem, are used as examples to conduct a computational experiment. Without using overly sophisticated tabu search techniques, the Tabu Machine outperforms the Boltzmann Machine in terms of both solution quality and computation time.     

Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics

Constraint Programming typically uses the technique of depth-first branch and bound as the method of solving optimization problems. Although this method can give the optimal solution, for large problems, the time needed to find the optimal can be prohibitive. This paper introduces a method for using local search techniques within a Constraint Programming framework, and applies this technique to vehicle routing problems. We introduce a Constraint Programming model for vehicle routing, and a system for integrating Constraint Programming and local search techniques. We then describe how the method can be accelerated by handling core constraints using fast local checks, while other more complex constraints are left to the constraint propagation system. We have coupled our local search method with a meta-heuristic to avoid the search being trapped in local minima. Several meta-heuristics are investigated ranging from a simple Tabu Search method to Guided Local Search. An empirical study over benchmark problems shows the relative merits of these techniques. Investigations indicate that the specific long-term memory technique used by Guided Local Search can be used as a diversification method for Tabu Search, resulting in significant benefit. Several new best solutions on the Solomon problems are found in relatively few iterations of our algorithm.     

GRASP-based heuristic algorithm for the multi-product multi-vehicle inventory routing problem

In this paper, we introduce an improved Greedy Randomized Adaptive Search Procedure (GRASP) based heuristic for the multi-product multi-vehicle inventory routing problem (MMIRP). The inventory routing problem, which combines the vehicle-routing problem and the inventory control decisions, is one of the most important problems in combinatorial optimization field. To deal with the MMIRP, we develop a GRASP-based heuristic (GBH). Each GBH iteration consists of two sequential phases; the first phase is a Greedy Randomized Procedure, in which, the best tradeoff between the inventory holding cost and routing cost is looked. Then, in the second phase, as local search for the GRASP, we use the Tabu search (TS) meta-heuristic to improve the solution found in the first phase. The GBH two phases are repeated until some stopped criterion is met. Our proposed method is evaluated on two benchmark data sets, and successfully compared with two state-of-the-art algorithms.     

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).     

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.     

Optimization of a high-speed placement machine using tabu search algorithms

Combinatorial optimization represents a wide range of real-life manufacturing optimization problems. Due to the high computational complexity, and the usually high number of variables, the solution of these problems imposes considerable challenges. This paper presents a tabu search approach to a combinatorial optimization problem, in which the objective is to maximize the production throughput of a high-speed automated placement machine. Tabu search is a modern heuristic technique widely employed to cope with large search spaces, for which classical search methods would not provide satisfactory solutions in a reasonable amount of time. The developed TS strategies are tailored to address the different issues caused by the modular structure of the machine. This revised version was published online in June 2006 with corrections to the Cover Date.     

Comparing local search metaheuristics for the maximum diversity problem

The Maximum Diversity Problem (MDP) requires to extract a subset M of given cardinality from a set N, maximising the sum of the pair-wise diversities between the extracted elements. The MDP has recently been the subject of much research, and several sophisticated heuristics have been proposed to solve it. The present work compares four local search metaheuristics for the MDP, all based on the same Tabu Search procedure, with the aim to identify what additional elements provide the strongest improvement. The four metaheuristics are an Exploring Tabu Search, a Scatter Search, a Variable Neighbourhood Search and a simple Random Restart algorithm. All of them prove competitive with the best algorithms proposed in the literature. Quite surprisingly, the best ones are the simple Random Restart algorithm and a Variable Neighbourhood Search algorithm with an unusual parameter setting, which makes it quite close to random restart. Although this is probably related to the elementary structure of the MDP, it also suggests that, more often than expected, simpler algorithms might be better.     

Massively parallel analog tabu search using neural networks applied to simple plant location problems

Neural networks and tabu search are two very significant techniques which have emerged recently for the solution of discrete optimization problems. Neural networks possess the desirable quality of implementability in massively parallel hardware while the tabu search metaheuristic shows great promise as a powerful global search method. Tabu Neural Network (TANN) integrates an analog version of the short term memory component of tabu search with neural networks to generate a massively parallel, analog global search strategy that is hardware implementable. In TANN, both the choice of the element to enter the tabu list as well as the maintenance of the decision elements in tabu status is accomplished via neuronal activities. In this paper we apply TANN to the simple plant location problem. Comparisons with the Hopfield-Tank network show an average improvement of about 85% in the quality of solutions obtained.     

Dynamic tabu search strategies for the traveling purchaser problem

Tabu search is a metastrategy for guiding known heuristics to overcome local optimality with a large number of successful applications reported in the literature. In this paper we investigate two dynamic strategies, the reverse elimination method and the cancellation sequence method. The incorporation of strategic oscillation as well as a combination of these methods are developed. The impact of the different methods is shown with respect to the traveling purchaser problem, a generalization of the classical traveling salesman problem. The traveling purchaser problem is the problem of determining a tour of a purchaser buying several items in different shops by minimizing the total amount of travel and purchase costs. A comparison of the tabu search strategies with a simulated annealing approach is presented, too.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

Metaheuristics for a Flexible Assembly System Design Problem

Flexibility has become an important priority in the formulation and implementation of manufacturing strategies. This in turn has opened up a new class of design problems for such systems. Flexible assembly systems (FAS), consisting of a variety of processors and operations, provide the opportunity for improving product manufacturing flexibility, hence gaining competitive advantages. This paper considers a particular design decision problem for FAS. A matrix-based, polynomial-time lower bound algorithm is presented. Simulated annealing and tabu search metaheuristics are formulated to address the problems. Computational experience with these metaheuristics is reported.