Hybrid Population-Based Algorithms for the Bi-Objective Quadratic Assignment Problem

We present variants of an ant colony optimization (MO-ACO) algorithm and of an evolutionary algorithm (SPEA2) for tackling multi-objective combinatorial optimization problems, hybridized with an iterative improvement algorithm and the robust tabu search algorithm. The performance of the resulting hybrid stochastic local search (SLS) algorithms is experimentally investigated for the bi-objective quadratic assignment problem (bQAP) and compared against repeated applications of the underlying local search algorithms for several scalarizations. The experiments consider structured and unstructured bQAP instances with various degrees of correlation between the flow matrices. We do a systematic experimental analysis of the algorithms using outperformance relations and the attainment functions methodology to asses differences in the performance of the algorithms. The experimental results show the usefulness of the hybrid algorithms if the available computation time is not too limited and identify SPEA2 hybridized with very short tabu search runs as the most promising variant. This research was mainly done while Luís Paquete and Thomas Stützle were with the Intellectics Group at the Computer Science Department of Darmstadt University of Technology, Germany     

Efficient Genetic Algorithms Using Simple Genes Exchange Local Search Policy for the Quadratic Assignment Problem

In this paper, we describe an approach for solving the quadratic assignment problem (QAP) that is based on genetic algorithms (GA). It will be shown that a standard canonical GA (SGA), which involves genetic operators of selection, reproduction, crossover, and mutation, tends to fall short of the desired performance expected of a search algorithm. The performance deteriorates significantly as the size of the problem increases. To address this syndrome, it is common for GA-based techniques to be embedded with deterministic local search procedures. It is proposed that the local search should involve simple procedure of genome reordering that should not be too complex. More importantly, from a computational point of view, the local search should not carry with it the full cost of evaluating a chromosome after each move in the localized landscape. Results of simulation on several difficult QAP benchmarks showed the effectiveness of our approaches.     

Extensive Testing of a Hybrid Genetic Algorithm for Solving Quadratic Assignment Problems

A robust search algorithm should ideally exhibit reasonable performance on a diverse and varied set of problems. In an earlier paper Lim et al. (Computational Optimization and Applications, vol. 15, no. 3, 2000), we outlined a class of hybrid genetic algorithms based on the k-gene exchange local search for solving the quadratic assignment problem (QAP). We follow up on our development of the algorithms by reporting in this paper the results of comprehensive testing of the hybrid genetic algorithms (GA) in solving QAP. Over a hundred instances of QAP benchmarks were tested using a standard set of parameters setting and the results are presented along with the results obtained using simple GA for comparisons. Results of our testing on all the benchmarks show that the hybrid GA can obtain good quality solutions of within 2.5% above the best-known solution for 98% of the instances of QAP benchmarks tested. The computation time is also reasonable. For all the instances tested, all except for one require computation time not exceeding one hour. The results will serve as a useful baseline for performance comparison against other algorithms using the QAP benchmarks as a basis for testing.     

A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

基于免疫原理的蚁群系统及其应用

针对蚁群算法在寻优过程中容易出现停滞现象,同意在该算法中引入免疫机制,将待求解问题看成抗原,而问题的解看成抗体,通过基于浓度的选择机制和多样性保持策略来提高蚁群算法的全局搜索能力和避免停滞现象.对TSP问题的仿真实验结果表明,该算法极大地提高了搜索能力和避免了停滞现象.     

一种求解物流设施二次分配问题的混合分布估计算法

为了求解物流设施二次分配问题,提出了一种混合分布估计算法(HEDA)。首先,根据QAP的距离和物流量矩阵信息,提出了一种基于假设物流中心启发式规则的种群初始化方法,用于提高初始种群的质量和算法的搜索效率;其次,针对HEDA的概率模型,提出了一种概率矩阵初始构型生成机制和扰动操作,用于提高算法的全局探索能力;最后,在分析QAP的结构性质的基础上,设计了一种基于快速评价的局部搜索策略,用于提高算法的局部开发能力。仿真计算实验和算法比较验证了HEDA的优化性能。     

Ant colonies for the quadratic assignment problem

This paper presents HAS–QAP, a hybrid ant colony system coupled with a local search, applied to the quadratic assignment problem. HAS–QAP uses pheromone trail information to perform modifications on QAP solutions, unlike more traditional ant systems that use pheromone trail information to construct complete solutions. HAS–QAP is analysed and compared with some of the best heuristics available for the QAP: two versions of tabu search, namely, robust and reactive tabu search, hybrid genetic algorithm, and a simulated annealing method. Experimental results show that HAS–QAP and the hybrid genetic algorithm perform best on real world, irregular and structured problems due to their ability to find the structure of good solutions, while HAS–QAP performance is less competitive on random, regular and unstructured problems.     

Applying an Extended Guided Local Search to the Quadratic Assignment Problem

In this paper, we show how an extended Guided Local Search (GLS) can be applied to the Quadratic Assignment Problem (QAP). GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms, to help guide them out of local minima. We present empirical results of applying several extended versions of GLS to the QAP, and show that these extensions can improve the range of parameter settings within which Guided Local Search performs well. Finally, we compare the results of running our extended GLS with some state of the art algorithms for the QAP.     

Test driving three 1995 genetic algorithms: New test functions and geometric matching

Genetic algorithms have attracted a good deal of interest in the heuristic search community. Yet there are several different types of genetic algorithms with varying performance and search characteristics. In this article we look at three genetic algorithms: an elitist simple genetic algorithm, the CHC algorithm and Genitor. One problem in comparing algorithms is that most test problems in the genetic algorithm literature can be solved using simple local search methods. In this article, the three algorithms are compared using new test problems that are not readily solved using simple local search methods. We then compare a local search method to genetic algorithms for geometric matching and examine a hybrid algorithm that combines local and genetic search. The geometric matching problem matches a model (e.g., a line drawing) to a subset of lines contained in a field of line fragments. Local search is currently the best known method for solving general geometric matching problems.     

A cooperative parallel tabu search algorithm for the quadratic assignment problem

In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this.     

Iterative improvement methods for a multiperiod network design problem

We address an important problem in telecommunications planning: the multiperiod network expansion problem. Our aim is to show that it can be efficiently solved using a new local search approach. To achieve our goal, we first show how to adapt the problem's formulation to meet our local search program's requirements. We then describe GLIT (Generic Local Improvement Template), a new, generic auto-calibrating local search algorithm; the different neighbouring strategies that we designed specifically for this problem; as well as a Genetic algorithm for this problem. We compare and discuss the performance of these algorithms using extensive computational tests on a large range of instances with up to 7500 arcs. These experiments show that GLIT clearly outperforms competitive approaches, especially when it is coupled with Genetic algorithms. We also show that the hybrid algorithms Genetic/Tabu, Genetic/Simulated Annealing, and finally Genetic/GLIT all outperform both pure Genetic and pure local search algorithms.     

Iterated local search for workforce scheduling and routing problems

The integration of scheduling workers to perform tasks with the traditional vehicle routing problem gives rise to the workforce scheduling and routing problems (WSRP). In the WSRP, a number of service technicians with different skills, and tasks at different locations with pre-defined time windows and skill requirements are given. It is required to find an assignment and ordering of technicians to tasks, where each task is performed within its time window by a technician with the required skill, for which the total cost of the routing is minimized. This paper describes an iterated local search (ILS) algorithm for the WSRP. The performance of the proposed algorithm is evaluated on benchmark instances against an off-the-shelf optimizer and an existing adaptive large neighbourhood search algorithm. The proposed ILS algorithm is also applied to solve the skill vehicle routing problem, which can be viewed as a special case of the WSRP. The computational results indicate that the proposed algorithm can produce high-quality solutions in short computation times.     

Generating Hard Test Instances with Known Optimal Solution for the Rectilinear Quadratic Assignment Problem

In this paper we consider the rectilinear version of the quadratic assignment problem (QAP). We define a class of edge-weighted graphs with nonnegatively valued bisections. For one important type of such graphs we provide a characterization of point sets on the plane for which the optimal value of the related QAP is zero. These graphs are used in the algorithms for generating rectilinear QAP instances with known provably optimal solutions. The basic algorithm of such type uses only triangles. Making a reduction from 3-dimensional matching, it is shown that the set of instances which can be generated by this algorithm is hard. The basic algorithm is extended to process graphs larger than triangles. We give implementation details of this extension and of four other variations of the basic algorithm. We compare these five and also two existing generators experimentally employing multi-start descent heuristic for the QAP as an examiner. The graphs with nonnegatively valued bisections can also be used in the construction of lower bounds on the optimal value for the rectilinear QAP.     

An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

This paper considers a variant of the travelling salesman problem named the capacitated prize-collecting travelling salesman problem (CPCTSP), which is derived from the colour-coating production scheduling in a cold rolling mill. The objective of the CPCTSP is to minimize the travel cost and the penalties paid for unvisited customers in such a way that a sufficiently large prize is collected and the demand of the visited customers does not exceed the salesman's capacity. For this problem, we propose an iterated local search (ILS) heuristic adopting guided kick and enhanced dynasearch. The experimental results on randomly generated instances show that the proposed heuristic outperforms the improved tabu search algorithm using frequency-based memory, and the further experimental results on instances collected from real colour-coating production also show that the proposed ILS algorithm is more effective and efficient than the currently adopted manual scheduling method.     

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.     

Contributions to the quadratic assignment problem

Tree search procedures for solving the Koopmans Beckmann quadratic assignment problem (QAP) are unable to solve any reasonable size QAP's mainly because good quality lower bounds for this problem cannot be computed.The purpose of this paper is to propose a bounding technique based on the extraction from the QAP formulation, of a large linear assignment problem (which can then be solved optimally), leaving as a residual problem as ‘small’ a QAP as possible. The solution of this residual QAP can then be bounded by a separate procedure. This 2-step method produces improved bounds as compared with those produced by the direct application of the bounding algorithms to the original QAP. In addition, a procedure is described for the a priori fixing of variables in the QAP formulation, thus reducing the number of variables in the problem.     

A hybrid iterated local search heuristic for the maximum weight independent set problem

This paper presents a hybrid iterated local search (ILS) algorithm for the maximum weight independent set (MWIS) problem, a generalization of the classical maximum independent set problem. Two efficient neighborhood structures are proposed and they are explored using the variable neighborhood descent procedure. Moreover, we devise a perturbation mechanism that dynamically adjusts the balance between intensification and diversification during the search. The proposed algorithm was tested on two well-known benchmarks (DIMACS-W and BHOSLIB-W) and the results obtained were compared with those found by state-of-the-art heuristics and exact methods. Our heuristic outperforms the best-known heuristic for the MWIS as well as the best heuristics for the maximum weight clique problem. The results also show that the hybrid ILS was capable of finding all known optimal solutions in milliseconds.     

Approximate solutions to the turbine balancing problem

The turbine balancing problem (TBP) is an NP-Hard combinatorial optimization problem arising in the manufacturing and maintenance of turbine engines. Exact solution methods for solving the TBP are not appropriate since the problem has to be solved in real time and the input data is itself inaccurate. In this paper the TBP is formulated as a quadratic assignment problem (QAP) and we propose a heuristic algorithm for solving the resulting problem. Computational results on a set of instances provided by Pratt & Whitney (P&W) and from the literature, indicate that the proposed algorithm outperforms the current methods used for solving the TBP, and has the best overall performance with respect to other heuristic algorithms in the literature.     

Boosting local search with Lagrangian relaxation

Local search algorithms play an essential role in solving large-scale combinatorial optimization problems. Traditionally, the local search procedure is guided mainly by the objective function of the problem. Hence, the greedy improvement paradigm poses the potential threat of prematurely getting trapped in low quality attraction basins. In this study, we intend to utilize the information extracted from the relaxed problem, to enhance the performance of the local search process. Considering the Lin-Kernighan-based local search (LK-search) for the p-median problem as a case study, we propose the Lagrangian relaxation Assisted Neighborhood Search (LANS). In the proposed algorithm, two new mechanisms, namely the neighborhood reduction and the redundancy detection, are developed. The two mechanisms exploit the information gathered from the relaxed problem, to avoid the search from prematurely targeting low quality directions, and to cut off the non-promising searching procedure, respectively. Extensive numerical results over the benchmark instances demonstrate that LANS performs favorably to LK-search, which is among the state-of-the-art local search algorithms for the p-median problem. Furthermore, by embedding LANS into other heuristics, the best known upper bounds over several benchmark instances could be updated. Besides, run-time distribution analysis is also employed to investigate the reason why LANS works. The findings of this study confirm that the idea of improving local search by leveraging the information induced from relaxed problem is feasible and practical, and might be generalized to a broad class of combinatorial optimization problems.     

Ant colony optimization for solving an industrial layout problem

This paper presents ACO_GLS, a hybrid ant colony optimization approach coupled with a guided local search, applied to a layout problem. ACO_GLS is applied to an industrial case, in a train maintenance facility of the French railway system (SNCF). Results show that an improvement of near 20% is achieved with respect to the actual layout. Since the problem is modeled as a quadratic assignment problem (QAP), we compared our approach with some of the best heuristics available for this problem. Experimental results show that ACO_GLS performs better for small instances, while its performance is still satisfactory for large instances.