Abstract
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.
Similar content being viewed by others
References
A. Amin, Simulated jumping, Annals of Operations Research (1998) to appear.
R. Battiti and G. Tecchiolli, The reactive tabu search, ORSA Journal on Computing 6(2) (1994) 126–140.
C.M. Bishop and G. Hinton, Neural Networks for Pattern Recognition (Clarendon Press, New York, 1995).
R.E. Burkard, S.E. Karisch and F. Rendl, QAPLIB – a quadratic assignment problem library, Journal of Global Optimization 10 (1997) 391–403.
A. Davenport, Extensions and evaluation of GENET in constraint satisfaction, Ph.D. Thesis, Department of Computer Science, University of Essex, Colchester, UK (July 1997).
A. Davenport, E.P.K. Tsang, K. Zhu and C.J. Wang, GENET: a connectionist architecture for solving constraint satisfaction problems by iterative improvement, in: Proceedings of AAAI (1994) pp. 325–330.
C. Fleurent and J.A. Ferland, Genetic hybrids for the quadratic assignment problem, in: Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 16, eds. P. Pardalos and H. Wolkowicz (Amer. Math. Soc., Providence, RI, 1994) pp. 173–187.
F. Glover, Tabu search. Part I, ORSA Journal on Computing 1 (1989) 109–206.
F. Glover, Tabu search. Part II, ORSA Journal on Computing 2 (1990) 4–32.
P. Kilby, P. Prosser and P. Shaw, Guided local search for the vehicle routing problem, in: Proceedings of the 2nd International Conference on Metaheuristics (July 1997).
T.L. Lau, Guided genetic algorithm, Ph.D. Thesis, Department of Computer Science, University of Essex (1999).
T.L. Lau and E.P.K. Tsang, Applying a mutation-based genetic algorithm to processor configuration problems, in: Proceedings of 8th IEEE Conference on Tools with Artificial Intelligence (ICTAI '96), Toulouse, France (November 1996).
T.L. Lau and E.P.K. Tsang, Solving the processor configuration problem with a mutation-based genetic algorithm, International Journal on Artificial Intelligence Tools 6(4) (1997) 567–585.
T.L. Lau and E.P.K. Tsang, Solving the radio link frequency assignment problem with the guided genetic algorithm, in: Proceedings of NATO Symposium on Radio Length Frequency Assignment, Sharing and Conservation Systems (Aerospace), Aalborg, Denmark (October 1998), paper 14b.
T.L. Lau and E.P.K. Tsang, The guided genetic algorithm and its application to the general assignment problems, in: IEEE 10th International Conference on Tools with Artificial Intelligence (ICTAI '98), Taiwan (November 1998).
T.L. Lau and E.P.K. Tsang, Solving large processor configuration problems with the guided genetic algorithm, in: IEEE 10th International Conference on Tools with Artificial Intelligence (ICTAI '98), Taiwan (November 1998).
T.L. Lau and E.P.K. Tsang, Guided genetic algorithm and its application to radio link frequency assignment problems, to appear in Journal of Constraints.
P. Mills and E.P.K. Tsang, Guided local search for solving SAT and weighted MAX-SAT problems, Journal of Automatic Reasoning 24, Special Issue on Satisfiability Problems (2000) 205–223.
P.M. Pardalos, F. Rendl and H. Wolkowicz, The quadratic assignment Problem: a survey of recent developments, in: Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 16, eds. P. Pardalos and H. Wolkowicz (Amer. Math. Soc., Providence, RI, 1994) pp. 1–42.
B. Selman, H. Kautz and B. Cohen, Noise strategies for improving local search, in: Proceedings of AAAI-94 (1994).
B. Stroustrup, The C++ Programming Language, 3rd edn. (Addison-Wesley, Reading, MA, 1997).
T. Stutzle, MAX-MIN Ant system for quadratic assignment problems, Research Report AIDA–97–04, Department of Computer Science, Darmstadt University of Technology, Germany (1997).
E.D. Taillard, Robust tabu search for the quadratic assignment problem, Parallel Computing 17 (1991) 443–455.
E.D. Taillard, Comparison of Iterative Searches for the Quadratic Assignment Problem (Location Science, 1994).
E.D. Taillard and L.M. Gambardella, Adaptive memories for the quadratic assignment problem, Research Report, IDSIA, Lugano, Switzerland (1997).
U.W. Thonemann and A. Bolte, An improved simulated annealing algorithm for the quadratic assignment problem, Working paper, School of Business, Department of Production and Operations Research, University of Paderborn, Germany (1994).
E.P.K. Tsang and C. Voudouris, Fast local search and guided local search and their application to British Telecom's workforce scheduling problem, Operations Research Letters 20(3) (1997) 119–127.
E.P.K. Tsang and C.J.Wang, A generic neural network approach for constraint satisfaction problems, in: Neural Network Applications, ed. J.G. Taylor (Springer, Berlin, 1992) pp. 12–22.
C. Voudouris, Guided local search for combinatorial optimisation problems, Ph.D. Thesis, Department of Computer Science, University of Essex (1997).
C. Voudouris, Guided local search – an illustrative example in function optimisation, BT Technology Journal 16(3) (1998) 46–50.
C. Voudouris and E.P.K. Tsang, Solving the radio link frequency assignment problem using guided local search, in: Proceedings of NATO Symposium on Radio Length Frequency Assignment, Sharing and Conservation Systems (Aerospace), Aalborg, Denmark, October (1998) paper 14a.
C. Voudouris and E.P.K. Tsang, Guided local search and its application to the travelling salesman problem, European Journal of Operational Research 113(2) (1999) 469–499.
M.R. Wilhelm and T.L. Ward, Solving quadratic assignment problems by simulated annealing, IIE Transactions 19(1) (1987) 107–119.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mills, P., Tsang, E. & Ford, J. Applying an Extended Guided Local Search to the Quadratic Assignment Problem. Annals of Operations Research 118, 121–135 (2003). https://doi.org/10.1023/A:1021857607524
Issue Date:
DOI: https://doi.org/10.1023/A:1021857607524