×

A parallel water flow algorithm with local search for solving the quadratic assignment problem. (English) Zbl 1415.90106

Summary: In this paper, we adapt a nature-inspired optimization approach, the water flow algorithm, for solving the quadratic assignment problem. The algorithm imitates the hydrological cycle in meteorology and the erosion phenomenon in nature. In this algorithm, a systematic precipitation generating scheme is included to increase the spread of the raindrop positions on the ground to increase the solution exploration capability of the algorithm. Efficient local search methods are also used to enhance the solution exploitation capability of the algorithm. In addition, a parallel computing strategy is integrated into the algorithm to speed up the computation time. The performance of the algorithm is tested with the benchmark instances of the quadratic assignment problem taken from the QAPLIB. The computational results and comparisons show that our algorithm is able to obtain good quality or optimal solutions to the benchmark instances within reasonable computation time.

MSC:

90C27 Combinatorial optimization
90B80 Discrete location and assignment
68W10 Parallel algorithms in computer science

Software:

QAPLIB; WCA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Abbiw-Jackson; B. Golden; S. Raghavan; E. Wasil, A divide-and-conquer local search heuristic for data visualization, Computers & Operations Research, 33, 3070-3087 (2006) · Zbl 1113.90127 · doi:10.1016/j.cor.2005.01.020
[2] R. K. Ahuja; J. B. Orlin; A. Tiwari, A greedy genetic algorithm for the quadratic assignment problem, Computers & Operations Research, 27, 917-934 (2000) · Zbl 0970.90067 · doi:10.1016/S0305-0548(99)00067-2
[3] E. M. Arkin; R. Hassin; M. Sviridenko, Approximating the maximum quadratic assignment problem, Information Processing Letters, 77, 13-16 (2001) · Zbl 0996.90500 · doi:10.1016/S0020-0190(00)00151-4
[4] A. Blanchard; S. Elloumi; A. Faye; N. Wicker, A cutting algorithm for the quadratic assignment problem, INFOR, 41, 35-49 (2003) · Zbl 07682293
[5] S. H. Bokhari, Assignment Problems in Parallel and Distributed Computing, Kluwer Academic Publishers, Boston, MA, 1987.
[6] E. S. Buffa; G. C. Armour; T. E. Vollmann, Allocating facilities with CRAFT, Harvard Business Review, 42, 136-158 (1964)
[7] R. E. Burkard; S. E. Karisch; F. Rendl, QAPLIB -A quadratic assignment problem library, Journal of Global Optimization, 10, 391-403 (1997) · Zbl 0884.90116 · doi:10.1023/A:1008293323270
[8] R. E. Burkard, E. Cela, G. Rote and G. J. Woeginger, The quadratic assignment problem with a monotone Anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases, in: Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization, Vancouver, British Columbia, Canada, (1996), 204-218. · Zbl 0949.90077
[9] E. Cela, The Quadratic Assignment Problem: Theory and Algorithms, Combinatorial Optimization (eds. D. Z. Du and P. Pardalos), Kluwer Academic Publishers, London, 1998. · Zbl 0909.90226
[10] V. M. Demidenko; G. Finke; V. S. Gordon, Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices, Journal of Mathematical Modeling and Algorithms, 5, 167-187 (2006) · Zbl 1121.90107 · doi:10.1007/s10852-005-9013-2
[11] M. Dorigo, Optimization, Learning and Natural Algorithms, Ph. D thesis, Politecnico di Milano, Italie, 1992.
[12] E. Duman; I. Or, The quadratic assignment problem in the context of the printed circuit board assembly process, Computers & Operations Research, 34, 163-179 (2007) · Zbl 1113.90130 · doi:10.1016/j.cor.2005.05.004
[13] B. Eschermann and H. J. Wunderlich, Optimized synthesis of self-testable finite state machines, in: Proceedings of the 20th International Symposium Fault-Tolerant Computing (FTCS 20), Newcastle Upon Tyne, UK, (1990), 390-397.
[14] H. Eskandar; A. Sadollah; A. Bahreininejad; M. Hamdi, Water cycle algorithm-A novel metaheuristic optimization method for solving constrained engineering optimization problems, Computers & Structures, 110/111, 151-166 (2012)
[15] R. N. Gasimov; O. Ustun, Solving the quadratic assignment problem using F-MSG algorithm, Journal of Industrial and Management Optimization, 3, 173-191 (2007) · Zbl 1171.90445 · doi:10.3934/jimo.2007.3.173
[16] G. Gutin; A. Yeo, Polynomial approximation algorithms for TSP and QAP with a factorial domination number, Discrete Applied Mathematics, 119, 107-116 (2002) · Zbl 0996.90061 · doi:10.1016/S0166-218X(01)00267-0
[17] P. M. Hahn; W. L. Hightower; T. A. Johnson; M. Guignard-Spielberg; C. Roucairol, Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem, Yugoslavian Journal of Operational Research, 11, 41-60 (2001)
[18] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.
[19] L. J. Hubert, Assignment Methods in Combinatorial Data Analysis, Marcel Dekker Inc., New York, 1987. · Zbl 0628.62003
[20] J. Kennedy and R. C. Eberhart, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, (1995), 1942-1948.
[21] I. K. Kim; D. W. Jung; R. H. Park, Document image binarization based on topographic analysis using a water flow model, Pattern Recognition, 35, 265-277 (2002) · Zbl 0988.68801 · doi:10.1016/S0031-3203(01)00027-9
[22] Y. Li, P. M. Pardalos and M. G. C. Resende, A greedy randomized adaptive search procedure for the quadratic assignment problem, in Quadratic Assignment and Related Problems(eds. P. M. Pardalos and H. Wolkowicz), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 16 (1994), 237-261. · Zbl 0817.90057
[23] M. Lim; Y. Yuan; S. Omatu, Extensive testing of a hybrid genetic algorithm for solving quadratic assignment problems, Computational Optimization and Applications, 23, 47-64 (2002) · Zbl 1036.90057 · doi:10.1023/A:1019972523847
[24] V. Maniezzo; A. Colorni, The ant system applied to the quadratic assignment problem, IEEE Transactions on Knowledge and Data Engineering, 11, 769-778 (1999) · doi:10.1109/69.806935
[25] P. Merz; B. Freisleben, Fitness landscape analysis and memetic algorithms for the quadratic assignment problem, IEEE Transactions on Evolutionary Computation, 4, 337-352 (2000)
[26] S. Nakrani; C. Tovey, On honey bees and dynamic server allocation in internet hosting centers, Adaptive Behaviors, 12, 223-240 (2004) · doi:10.1177/105971230401200308
[27] H. H. Oh; K. T. Lim; S. I. Chien, An improved binarization algorithm based on a water flow model for document image with inhomogeneous backgrounds, Pattern Recognition, 38, 2612-2625 (2005) · doi:10.1016/j.patcog.2004.11.025
[28] A. S. Ramkumar; S. G. Ponnambalam; N. Jawahar, A population-based hybrid ant system for quadratic assignment formulations in facility layout design, International Journal of Advanced Manufacturing Technology, 44, 548-558 (2009) · doi:10.1007/s00170-008-1849-y
[29] A. S. Ramkumar; S. G. Ponnambalam; N. Jawahar, Iterated fast local search algorithm for solving quadratic assignment problems, Robotics and Computer-Integrated Manufacturing, 24, 392-401 (2008) · doi:10.1016/j.rcim.2007.01.004
[30] D. F. Rossin; M. C. Springer; B. D. Klein, New complexity measures for the facility layout problem: An empirical study using traditional and neural network analysis, Computers & Industrial Engineering, 36, 585-602 (1999) · doi:10.1016/S0360-8352(99)00153-9
[31] S. Sahni; T. Gonzalez, P-complete approximation problems, Journal of the ACM, 23, 555-565 (1976) · Zbl 0348.90152 · doi:10.1145/321958.321975
[32] H. Q. Saremi; B. Abedin; A. M. Kermani, Website structure improvement: Quadratic assignment problem approach and ant colony metaheuristic technique, Applied Mathematics and Computation, 195, 285-298 (2008) · Zbl 1128.68004 · doi:10.1016/j.amc.2007.04.095
[33] A. Shukla, A modified bat algorithm for the quadratic assignment problem, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC’ 15), Sendai, Japan, (2015), 486-490.
[34] H. Shah-Hosseini, Problem solving by intelligent water drops, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC’ 07), Singapore, (2007), 3226-3231.
[35] H. Shah-Hosseini, Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem, International Journal of Intelligent Computing and Cybernetics, 1, 193-212 (2008) · Zbl 1163.90719 · doi:10.1108/17563780810874717
[36] H. Shah-Hosseini, The intelligent water drops algorithm: A nature-inspired swarm-based optimization algorithm, International Journal of Bio-Inspired Computation, 1, 71-79 (2009)
[37] S. P. Singh; R. R. K. Sharma, Two-level modified simulated annealing based approach for solving facility layout problem, International Journal of Production Research, 46, 3563-3582 (2008) · Zbl 1141.90473
[38] E. Taillard, Comparison of iterative searches for the quadratic assignment problem, Location Science, 3, 87-105 (1995) · Zbl 0916.90235 · doi:10.1016/0966-8349(95)00008-6
[39] T. H. Tran; K. M. Ng, A water flow algorithm for flexible flow shop scheduling with intermediate buffers, Journal of Scheduling, 14, 483-500 (2011) · doi:10.1007/s10951-010-0205-x
[40] T. H. Tran; K. M. Ng, A hybrid water flow algorithm for multi-objective flexible flow shop scheduling problems, Engineering Optimization, 45, 483-502 (2013) · doi:10.1080/0305215X.2012.685072
[41] K. Y. Wong; P. C. See, A hybrid ant colony optimization algorithm for solving facility layout problems formulated as quadratic assignment problems, Engineering Computations: International Journal for Computer-Aided Engineering and Software, 27, 117-128 (2010) · Zbl 1284.74099
[42] T. H. Wu; S. H. Chung; C. C. Chang, A water flow-like algorithm for manufacturing cell formation problems, European Journal of Operational Research, 205, 346-360 (2010) · Zbl 1188.90281 · doi:10.1016/j.ejor.2010.01.020
[43] X. Yang; Q. Lu; C. Li; X. Liao, Biological computation of the solution to the quadratic assignment problem, Applied Mathematics and Computation, 200, 369-377 (2008) · Zbl 1316.90019 · doi:10.1016/j.amc.2007.11.016
[44] F. C. Yang; Y. P. Wang, Water flow-like algorithm for object grouping problems, Journal of the Chinese Institute of Industrial Engineers, 24, 475-488 (2007)
[45] Y. J. Zheng, Water wave optimization: A new nature-inspired metaheuristic, Computers & Operations Research, 55, 1-11 (2015) · Zbl 1348.90652 · doi:10.1016/j.cor.2014.10.008
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.