×

Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem. (English) Zbl 0912.90240

Summary: This work compares the effectiveness of eight evolutionary heuristic algorithms applied to the quadratic assignment problem (QAP), reputedly one of the most difficult combinatorial optimization problems. QAP is merely used as a carrier for the comparison: we do not attempt to compare any heuristics with solving algorithms specific for it. Results are given, both with respect to the best result achieved by each algorithm in a limited time span and to its speed of convergence to that result.

MSC:

90C27 Combinatorial optimization
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C20 Quadratic programming
90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E. H.L.; Korst, J. H.M., Simulated Annealing and Boltzmann Machines (1988), Wiley: Wiley New York
[2] Bäck, T.; Hoffmeister, F.; Schwefel, H. P., A survey of evolution strategies, (Proc. of the Fourth Int. Conf. on Genetic Algorithms (1991), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA)
[3] Bersini, H.; Varela, F. J., The immune recruitment mechanism: A selective evolutionary strategy, (Proc. of the Fourth Int. Conf. on Genetic Algorithms (1991), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA)
[4] Bertoni, A.; Dorigo, M., Implicit parallelism in genetic algorithms, Artificial Intelligence, 61, 2, 307-314 (1993) · Zbl 0781.68093
[5] Boender, C. G.E.; Rinnooy Kan, A. H.G.; Timmer, G. T.; Stougie, L., A stochastic method for global optimization, Mathematical Programming, 22 (1982) · Zbl 0525.90076
[6] Brown, D. E.; Huntley, C. L.; Spillane, A. R., A parallel genetic heuristic for the Quadratic Assignment Problem, (Proc. of the Third Int. Conf. on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA)
[7] Burkard, R. E., Quadratic Assignment Problems, European Journal of Operational Research, 15 (1984) · Zbl 0541.90070
[8] Burkard, R. E.; Rendl, F., A thermodynamically motivated simulation procedure for combinatorial optimization problems, European Journal of Operational Research, 17 (1984) · Zbl 0541.90070
[9] Camerini, P. M.; Colorni, A.; Maffioli, F., Some experience in applying a stochastic method to location problems, Mathematical Programming Study, 26 (1986) · Zbl 0588.90024
[10] Carraresi, P.; Malucelli, F., Quadratic Assignment Problems: A review, Ricerca Operativa, 47 (1988)
[11] Chakrapani, J.; Skorin-Kapov, J., Connectionist approaches to the Quadratic Assignment Problem, (Report HAR-90-08 (1990), W.A. Harriman School for Management and Policy, SUNY at Stony Brook) · Zbl 0757.90060
[12] Colorni, A.; Dorigo, M.; Maniezzo, V., Distributed optimization by ant colonies, (Proc. of the First European Conference on Artificial Life. Proc. of the First European Conference on Artificial Life, Paris (1991), MIT Press: MIT Press Cambridge, CA)
[13] Colorni, A.; Dorigo, M.; Maniezzo, V., An investigation of some properties of an ant algorithm, (Männer, R.; Manderick, B., Parallel Problem Solving from Nature — 2 (1992), North-Holland: North-Holland Amsterdam)
[14] Connolly, D. T., An improved annealing scheme for the QAP, European Journal of Operational Research, 46 (1990) · Zbl 0715.90079
[15] Edwards, C. S., The derivation of a greedy approximator for the Koopmans-Beckmann Quadratic Assignment Problem, Mathematical Programming Study, 13 (1977)
[16] Elshafei, A. E., Hospital layout as a Quadratic Assignment Problem, OR Quarterly, 28 (1977) · Zbl 0353.90096
[17] Finke, G.; Burkard, R. E.; Rendl, F., Quadratic Assignment Problems, Annals of Discrete Mathematics, 31 (1987) · Zbl 0607.90026
[18] Finke, G.; Burkard, R. E.; Rendl, F., Quadratic Assignment Problems, Annals of Discrete Mathematics, 31 (1987) · Zbl 0607.90026
[19] Finke, G.; Medova Dempster, E., Combinatorial optimization problems in trace forms, Ricerca Operativa, 52 (1989)
[20] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[21] Glover, F., Tabu Search — Part I, ORSA Journal on Computing, 1 (1989) · Zbl 0753.90054
[22] Glover, F., Tabu Search — Part II, ORSA Journal on Computing, 2 (1990) · Zbl 0771.90084
[23] Goldberg, D.; Lingle, J. R., Alleles, loci and the Traveling Salesman Problem, (Proc. of an Int. Conf. on Genetic Algorithms and their Applications. Proc. of an Int. Conf. on Genetic Algorithms and their Applications, Pittsburgh (1985), Lawrence Erlbaum: Lawrence Erlbaum London) · Zbl 0674.90095
[24] Grefenstette, J. J.; Baker, J. E., How genetic algorithms work: A critical look at implicit parallelism, (Schaffer, Proc. of the Third Int. Conf. on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA)
[25] Hinton, G. E.; Sejnowski, T. J., Learning and relearning in Boltzmann machines, (Rumelhart, D. E.; McLelland, J. L., Parallel Distributed Processing: Explorations in the Microstructure of Cognition (1986), MIT Press: MIT Press Cambridge, MA)
[26] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press MI
[27] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by Simulated Annealing, Science, 220 (1983) · Zbl 1225.90162
[28] Koopmans, T. C.; Beckmann, M. J., Assignment problems and the location of economic activities, Econometrica, 25 (1957) · Zbl 0098.12203
[29] Krarup, J.; Pruzan, P. M., Computer-aided layout design, Mathematical Programming Study, 9 (1978) · Zbl 0413.90058
[30] Maniezzo, V., The rudes and the shrewds, (Technical Report 91-042 (1991), Dipartimento di Elettronica, Politecnico di Milano: Dipartimento di Elettronica, Politecnico di Milano Milan, Italy)
[31] Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21 (1953) · Zbl 1431.65006
[32] Mühlenbein, H., Parallel genetic algorithms, population genetics and combinatorial optimization, (Schaffer, Proc. of the Third Int. Conf. on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA) · Zbl 0722.92010
[33] Nugent, C. E.; Vollmann, T. E.; Ruml, J., An experimental comparison of techniques for the assignment of facilities of locations, Operations Research, 16 (1968)
[34] Peterson, C., Parallel distributed approaches to combinatorial optimization: Benchmark studies on Travelling Salesman Problem, Neural Computation, 2 (1990)
[35] Rechenberg, I., Evolutionsstrategie (1973), Fromman-Holzbog
[36] Rhee, W. T., A note on asymptotic properties of the Quadratic Assignment Problem, Operations Research Letters, 7 (1988) · Zbl 0657.90079
[37] Rudolph, G., Optimization of combinatorial problems by means of parallel evolutionary algorithms, (ESPRIT PCA Meeting. ESPRIT PCA Meeting, Ispra (1990))
[38] Sahni, S.; Gonzalez, T., P-complete approximation problems, Journal of the ACM, 23 (1976) · Zbl 0348.90152
[39] Schwefel, H.-P., Numerical Optimization of Computer Models (1981), Technische Universität Berlin: Technische Universität Berlin New York, Also available as
[40] Skorin-Kapov, J., Tabu Search applied to the Quadratic Assignment Problem, ORSA Journal on Computing, 2 (1990) · Zbl 0752.90054
[41] Taillard, E., Robust Taboo Search for the Quadratic Assignment Problem, (Report ORPW 90/10, DMA (1990), Swiss Federal Institute of Technology of Lausanne)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.