Performance Analysis of Cyclical Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Measures for assessing the finite-time performance of GHC algorithms have been developed using this framework, including the expected number of iterations to visit a predetermined objective function value level. This paper analyzes how the expected number of iterations to visit a predetermined objective function value level can be estimated for cyclical simulated annealing. Cyclical simulated annealing uses a cooling schedule that cycles through a set of temperature values. Computational results with traveling salesman problem instances taken from TSPLIB show how the expected number of iterations to visit solutions with predetermined objective function levels can be estimated for cyclical simulated annealing.AMS 2000 Subject Classification 90-08 Computational Methods: Local Search, 90C59 Heuristics: Simulated Annealing     

Finite-Time Performance Analysis of Static Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Current theoretical results are based on the assumption that the goal when addressing such problems is to find a globally optimal solution. However, from a practical point of view, solutions that are close enough to a globally optimal solution (where close enough is measured in terms of the objective function value) for a discrete optimization problem may be acceptable. This paper introduces -acceptable solutions, where is a value greater than or equal to the globally optimal objective function value. Moreover, measures for assessing the finite-time performance of GHC algorithms, in terms of identifying -acceptable solutions, are defined. A variation of simulated annealing (SA), termed static simulated annealing (S²A), is analyzed using these measures. S²A uses a fixed cooling schedule during the algorithm's execution. Though S²A is provably nonconvergent, its finite-time performance can be assessed using the finite-time performance measures defined in terms of identifying -acceptable solutions. Computational results with a randomly generated instance of the traveling salesman problem are reported to illustrate the results presented. These results show that upper and lower estimates for the number of iterations to reach a -acceptable solution within a specified number of iterations can be obtained, and that these estimates are most accurate for moderate and high fixed temperature values for the S²A algorithm.     

Analysis of Static Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms to address intractable discrete optimization problems. This paper introduces a measure for determining the expected number of iterations to visit a predetermined objective function level, given that an inferior objective function level has been reached in a finite number of iterations. A variation of simulated annealing (SA), termed static simulated annealing (S²A), is analyzed using this measure. S²A uses a fixed cooling schedule during the algorithm execution. Though S²A is probably nonconvergent, its finite-time performance can be assessed using the finite-time performance measure defined in this paper.     

Analyzing the performance of simultaneous generalized hill climbing algorithms

Simultaneous generalized hill climbing (SGHC) algorithms provide a framework for using heuristics to simultaneously address sets of intractable discrete optimization problems where information is shared between the problems during the algorithm execution. Many well-known heuristics can be embedded within the SGHC algorithm framework. This paper shows that the solutions generated by an SGHC algorithm are a stochastic process that satisfies the Markov property. This allows problem probability mass functions to be formulated for particular sets of problems based on the long-term behavior of the algorithm. Such results can be used to determine the proportion of iterations that an SGHC algorithm will spend optimizing over each discrete optimization problem. Sufficient conditions that guarantee that the algorithm spends an equal number of iterations in each discrete optimization problem are provided. SGHC algorithms can also be formulated such that the overall performance of the algorithm is independent of the initial discrete optimization problem chosen. Sufficient conditions are obtained guaranteeing that an SGHC algorithm will visit the globally optimal solution for each discrete optimization problem. Lastly, rates of convergence for SGHC algorithms are reported that show that given a rate of convergence for the embedded GHC algorithm, the SGHC algorithm can be designed to preserve this rate.     

Global Optimization Performance Measures for Generalized Hill Climbing Algorithms

Generalized hill climbing algorithms provide a framework for modeling several local search algorithms for hard discrete optimization problems. This paper introduces and analyzes generalized hill climbing algorithm performance measures that reflect how effectively an algorithm has performed to date in visiting a global optimum and how effectively an algorithm may pes]rform in the future in visiting such a solution. These measures are also used to obtain a necessary asymptotic convergence (in probability) condition to a global optimum, which is then used to show that a common formulation of threshold accepting does not converge. These measures assume particularly simple forms when applied to specific search strategies such as Monte Carlo search and threshold accepting.     

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.     

Analyzing the Performance of Generalized Hill Climbing Algorithms

Generalized hill climbing algorithms provide a framework to describe and analyze metaheuristics for addressing intractable discrete optimization problems. The performance of such algorithms can be assessed asymptotically, either through convergence results or by comparison to other algorithms. This paper presents necessary and sufficient convergence conditions for generalized hill climbing algorithms. These conditions are shown to be equivalent to necessary and sufficient convergence conditions for simulated annealing when the generalized hill climbing algorithm is restricted to simulated annealing. Performance measures are also introduced that permit generalized hill climbing algorithms to be compared using random restart local search. These results identify a solution landscape parameter based on the basins of attraction for local optima that determines whether simulated annealing or random restart local search is more effective in visiting a global optimum. The implications and limitations of these results are discussed.     

Optimal search strategies using simultaneous generalized hill climbing algorithms

Optimal search strategies for conducting reconnaissance, surveillance or search and rescue operations with limited assets are of significant interest to military decision makers. Multiple search platforms with varying capabilities can be deployed individually or simultaneously for these operations (e.g., helicopters, fixed wing or satellite). Due to the timeliness required in these operations, efficient use of available search platforms is critical to the success of such missions. Designing optimal search strategies over multiple search platforms can be modeled and solved as a multiple traveling salesman problem (MTSP). This paper demonstrates how simultaneous generalized hill climbing algorithms (SGHC) can be used to determine optimal search strategies over multiple search platforms for the MTSP. Computational results with SGHC algorithms applied to the MTSP are reported. These results demonstrate that when limited computing budgets are available, optimal/near-optimal search strategies over multiple search platforms can be obtained more efficiently using SGHC algorithms compared to other generalized hill climbing algorithms. Applications and extensions of this research to other military applications are also discussed.     

A Tabu Search Heuristic for a Full-Load, Multi-Terminal, Vehicle Scheduling Problem with Backhauling and Time Windows

The problem considered is the full-load pickup and delivery problem with time windows (PDPTW), and heterogeneous products and vehicles, where the assignment of pickup points to requests is not predetermined. Elements associated with tabu search, such as diversification by reversion to junctions and the use of soft aspiration criteria, are embedded into our tabu search implementation. This metaheuristic is evaluated using random instances and selected data from a construction company in the U.K. The obtained results are compared against lower bounds from LP relaxation and also solutions from an existing multi-level heuristic.     

An Efficient Algorithm for the Knapsack Sharing Problem

The Knapsack Sharing Problem (KSP) is an NP-Hard combinatorial optimization problem, admitted in numerous real world applications. In the KSP, we have a knapsack of capacity c and a set of n objects, namely N, where each object j, j = 1,...,n, is associated with a profit p _j and a weight w _j. The set of objects N is composed of m different classes of objects J _i, i = 1,...,m, and N = ^m _i=1 J _i. The aim is to determine a subset of objects to be included in the knapsack that realizes a max-min value over all classes.In this article, we solve the KSP using an approximate solution method based upon tabu search. First, we describe a simple local search in which a depthparameter and a tabu list are used. Next, we enhance the algorithm by introducing some intensifying and diversifying strategies. The two versions of the algorithm yield satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach.     

Minimizing total completion time in a no-wait flowshop with sequence-dependent additive changeover times

This paper addresses the problem of minimizing total completion time in a two-machine no-wait flowshop where setup times of the jobs are sequence-dependent. Optimal solutions are obtained for two special flowshops and a dominance relation is developed for the general problem. Several heuristic algorithms with the computational complexity of O(n²) and O(n³) are constructed. The heuristics consist of two phases: in the first phase a starting list is developed and in the second a repeated insertion technique is applied. Computational experience demonstrates that the concept of repeated insertion application is quite useful for any starting list and that solutions for all starting lists converge to about the same value of less than 1% after a few iterations.     

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.     

Using solution properties within an enumerative search to solve a sports league scheduling problem

This paper presents an enumerative approach for a particular sports league scheduling problem known as “Prob026” in CSPLib. Despite its exponential-time complexity, this simple method can solve all instances involving a number T of teams up to 50 in a reasonable amount of time while the best known tabu search and constraint programming algorithms are limited to T?40 and the direct construction methods available only solve instances where or T/2 is odd. Furthermore, solutions were also found for some T values up to 70. The proposed approach relies on discovering, by observation, interesting properties from solutions of small problem instances and then using these properties in the final algorithm to constraint the search process.     

Metaheuristics: A bibliography

Metaheuristics are the most exciting development in approximate optimization techniques of the last two decades. They have had widespread successes in attacking a variety of difficult combinatorial optimization problems that arise in many practical areas. This bibliography provides a classification of a comprehensive list of 1380 references on the theory and application of metaheuristics. Metaheuristics include but are not limited to constraint logic programming; greedy random adaptive search procedures; natural evolutionary computation; neural networks; non-monotonic search strategies; space-search methods; simulated annealing; tabu search; threshold algorithms and their hybrids. References are presented in alphabetical order under a number of subheadings.     

Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem

The vehicle routing problem (VRP) under capacity and distance restrictions involves the design of a set of minimum cost delivery routes, originating and terminating at a central depot, which services a set of customers. Each customer must be supplied exactly once by one vehicle route. The total demand of any vehicle must not exceed the vehicle capacity. The total length of any route must not exceed a pre-specified bound. Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated. A special data structure for the tabu search algorithm is implemented which has reduced notably the computational time by more than 50%. An estimate for the tabu list size is statistically derived. Computational results are reported on a sample of seventeen bench-mark test problems from the literature and nine randomly generated problems. The new methods improve significantly both the number of vehicles used and the total distances travelled on all results reported in the literature.     

基于资源随机中断的反应性多模式项目调度优化

资源中断是项目实施过程中一种常见现象,它会导致项目进度计划的变更并引起额外的成本。本文研究资源随机中断下的项目调度问题,目标是对基准进度计划进行合理的调整,以最小化由此所造成的额外成本。作者首先对研究问题进行界定,随后构建问题的优化模型。针对模型的NP-hard属性,设计禁忌搜索启发式算法。最后以基准列表算法和随机生成算法为参照,在随机生成的标准算例集合上对算法进行测试,得到如下结论:在可接受的计算时间范围内,禁忌搜索获得的满意解质量明显高于其他两种启发式算法;算法的平均计算时间随着项目活动数的增加而增加,随着网络复杂度、资源强度或资源中断次数的增加而减小;满意解的平均目标函数值,随着项目活动数或网络复杂度的增加而增加,随着资源中断次数的增加而减小,与资源强度无明显关系。     

Heuristics for a coupled-operation scheduling problem

In this paper, we study a strongly NP-hard single machine scheduling problem in which each job consists of two operations that are separated by a time delay which lies within a specified range. The objective is to minimize the makespan. Determining the feasibility and, if applicable, makespan of any proposed permutation of the operations is non-trivial, requiring a longest path algorithm with O(n²) complexity for each permutation. Several heuristic algorithms are proposed: a deterministic and randomized construction algorithm, three descent algorithms and two reactive tabu search algorithms. The local search algorithms use a first improvement neighbourhood and mainly visit only feasible solutions within the search space. Results of extensive computational tests are reported, showing that the heavy computational burden of testing potential solutions renders the local search algorithms uncompetitive in comparison to the construction algorithms. The iterated descent algorithm performs least well.     

A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem

Neighbourhood search algorithms are often the most effective known approaches for solving partitioning problems. In this paper, we consider the capacitated examination timetabling problem as a partitioning problem and present an examination timetabling methodology that is based upon the large neighbourhood search algorithm that was originally developed by Ahuja and Orlin. It is based on searching a very large neighbourhood of solutions using graph theoretical algorithms implemented on a so-called improvement graph. In this paper, we present a tabu-based large neighbourhood search, in which the improvement moves are kept in a tabu list for a certain number of iterations. We have drawn upon Ahuja–Orlin's methodology incorporated with tabu lists and have developed an effective examination timetabling solution scheme which we evaluated on capacitated problem benchmark data sets from the literature. The capacitated problem includes the consideration of room capacities and, as such, represents an issue that is of particular importance in real-world situations. We compare our approach against other methodologies that have appeared in the literature over recent years. Our computational experiments indicate that the approach we describe produces the best known results on a number of these benchmark problems.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

Hashing vectors for tabu search

Tabu search as proposed by Glover [3,4] has proven to be a very effective metaheuristic for hard problems. In this paper we propose that hash functions be used to record the solutions encountered during recent iterations of the search in a long list. Hash values of potential solutions can be compared to the values on the list for the purpose of avoiding cycling. This frees the algorithm designer of the need to consider cycling when creating tabu restrictions based on move attributes. We suggest specific functions that result in very good performance.