A comparison of nature inspired algorithms for the quadratic assignment problem

• Autorzy: Chmiel W. , Kadłuczka P. , Kwiecień J. , Filipowicz B.

Identyfikatory

DOI

10.1515/bpasts-2017-0056

• Języki publikacji: EN

Abstrakty

EN

This paper presents an application of the ant algorithm and bees algorithm in optimization of QAP problem as an example of NP-hard optimization problem. The experiments with two types of algorithms: the bees algorithm and the ant algorithm were performed for the test instances of the quadratic assignment problem from QAPLIB, designed by Burkard, Karisch and Rendl. On the basis of the experiments results, an influence of particular elements of algorithms, including neighbourhood size and neighbourhood search method, will be determined.

Słowa kluczowe

EN

permutation problem; quadratic assignment problem; ant algorithm; bees algorithm

PL

problem permutacji; problem przydziału kwadratowego; algorytm Ant Colony; algorytm pszczół

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2017
• Tom: Vol. 65, nr 4
• Strony: 513--522
• Opis fizyczny: Bibliogr. 53 poz., rys., wykr., tab.

Twórcy

autor

Chmiel W.

• AGH University of Science and Technology, 30 Mickiewicza Ave., 30-059 Krakow, Poland

autor

Kadłuczka P.

• AGH University of Science and Technology, 30 Mickiewicza Ave., 30-059 Krakow, Poland

autor

Kwiecień J.

• AGH University of Science and Technology, 30 Mickiewicza Ave., 30-059 Krakow, Poland

autor

Filipowicz B.

• AGH University of Science and Technology, 30 Mickiewicza Ave., 30-059 Krakow, Poland

Bibliografia

• [1] R. Burkard, S. Karisch and F. Rendl, “QAPLib: a quadratic assignment problem library”, 1997.
• [2] W. Chmiel and P. Szwed, “Bees algorithm for the quadratic assignment problem on CUDA platform”, 4th International Conference on Man-Machine Interactions, 615‒625, Springer Int. Publishing (2015).
• [3] W. Chmiel, P. Kadłuczka, and G. Packanik, “Performance of swarm algorithms for permutation problems”, Automatyka 15(2), 117–126 (2009) (in Polish).
• [4] S. Sahni and T. Gonzalez, “P-complete approximation problems”, J.ACM, 23(3), 555‒565 (1976).
• [5] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, 1979.
• [6] D.S. Johnson, C.H. Papadimitriou, and M. Yannakakis, “How easy is local search?”, J. Comput. Syst. Sci. 37(1), 79–100 (1988).
• [7] K.A. Murthy, Y. Li, and P.M.Pardalos, “A local search algorithm for the quadratic assignment problem”, Informatica, Vilnius, 3(4), 524–538 (1992).
• [8] B.W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs”, The Bell System Technical Journal 49(1), 291–307 (1970).
• [9] A.A. Schaffer and M. Yannakakis, “Simple local search problems that are hard to solve”, SIAM J. Comput., 20(1), 56‒87 (1991).
• [10] E.L. Lawler, “The quadratic assignment problem: A brief review”, Combinatorial Programming: Methods and Applications, 19, 351‒360, Springer Netherlands 1975.
• [11] T.C. Koopmans and M.J. Beckmann, “Assignment problems and the location of economic activities”, Econometrica 25, 53–76 (1957).
• [12] R. Bermudez and M.H. Cole, “A genetic algorithm approach to door assignments in breakbulk terminals”, Technical Report MBTC-1102, Mack-Blackwell Transportation Center, University of Arkansas, 2001.
• [13] A. Mason and M.Rönnqvist, “Solution methods for the balancing of jet turbines”, Computers & OR 24(2), 153–167 (1997).
• [14] I. Ugi, J. Bauer, J. Brandt, J. Friedrich, J. Gasteiger, C. Jochum, and W.Schubert, “Neue Anwendungsgebiete für Computer in der Chemie”, Angewandte Chemie 91(2), (1979) [in German].
• [15] A.T. Phillips and J.B. Rosen, “A quadratic assignment formulation of the molecular conformation problem”, Journal of Global Optimization 4, 229–241 (1994).
• [16] M. Grötschel, “Discrete mathematics in manufacturing”, in R.E.O. Malley (Ed.), ICIAM 1991: Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, 119–145 (1991).
• [17] R.E. Burkard and E. Çela, “Heuristics for biquadratic assignment problems and their computational comparison”, European Journal of Operational Research 83(2), 283 – 300 (1995).
• [18] Z. Drezner, “The quadratic assignment problem”, Location Science (eds.: Laport G.et al.), 345‒363, Springer International Publishing (2015).
• [19] E.M. Loiola, N.M.M. de Abreu, P.O. Boaventura-Netto, P. Hahn, and T. Querido, “A survey for the quadratic assignment problem”, European Journal of Operational Research 176 (2), 657‒690 (2007).
• [20] C. Roucairol, “A reduction method for quadratic assignment problem”, Operations Research Verfahren, Methods of Operations Research 32, 185–187 (1979).
• [21] C. Roucairol, “An efficient branching scheme in branch and bound procedures”, Tims XXVI, Masi, Universite Paris 6, 42, 1984.
• [22] C. Roucairol, “A parallel branch and bound algorithm for the quadratic assignment problem”, Discrete Applied Mathematics 18(2), 211 – 225 (1987).
• [23] G. Erdoḡan and B. Tansel, “A branch-and-cut algorithm for quadratic assignment problems based on linearizations”, Computers& Operations Research 34(4), 1085- 1106 (2007).
• [24] M. Bashiri and H. Karimi, “Effective heuristics and meta-heuristics for the quadratic assignment problem with tuned parameters and analytical comparisons”, Journal of Industrial Engineering International 8(6), 1‒9 (2012).
• [25] L. Congying, Z. Huanping, and Y. Xinfeng, “Particle swarm optimization algorithm for quadratic assignment problem”, International Conference on Computer Science and Network Technology, 3, 1728‒1731 (2011).
• [26] A. Mamaghani and M. Meybodi, “Solving the quadratic assignment problem with the modified hybrid PSO algorithm”, International Conference on Application of Information and Communication Technologies, 1‒6 (2012).
• [27] E. Duman, M. Uysal and A.F. Alkaya, “Migrating birds optimization: A new metaheuristic approach and its performance on quadratic assignment problem”, Information Sciences, 217, 65‒77 (2012).
• [28] M. Dorigo, “Optimization, learning and natural algorithms”, PhD Thesis, Politecnico di Milano, Italy (1992).
• [29] E. Bonabeau, M. Dorigo, and G. Theraulaz, From Natural to Artificial Swarm Intelligence, Oxford University Press, 1999.
• [30] T. Stützle and H. Hoos, “Max-min ant system”, Future Generation Computer Systems 16(8), 889–914 (2000).
• [31] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies”, European Conference on Artificial Life, 134–142 (1991).
• [32] E.D. Taillard, “Fant: Fast ant system”, Technical Report, (1998).
• [33] D.T. Pham and M. Castellani, “Benchmarking and comparison of nature-inspired population-based continuous optimisation algorithms”, Soft Computing 18(5), 871‒903 (2014).
• [34] C.S. Chong, A.I. Sivakumar, M.Y.H. Low, and K.L. Gay, “A bee colony optimization algorithm to job shop scheduling”, Proceedings of the 38th Conference on Winter Simulation, Monterey, (2006).
• [35] B. Filipowicz and J. Kwiecień, “Swarm algorithms in optimization of quadratic assignment problem (QAP)”, Automatyka 15(2), 159–166 (2011) (in Polish).
• [36] V. Saravanov and N. Doroshko, “The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of factorial cardinality in cubic time”. Software: Algorithms and Programs 31, 11‒13 (1981).
• [37] F. Aurenhammer, “On-line sorting of twisted sequences in linear time”, BIT 28, 194‒204 (1988).
• [38] N. Christofides and E. Benavent, “An exact algorithm for the quadratic assignment problem on a tree”, Operations Research 37(5), 760–768 (1989).
• [39] T. Mautor, “Contribution a la resolution des problemes dimplanation: algorithmes sequentiels et paralleles pour laffectation quadratique”, PhD thesis (1992).
• [40] J. Skorin-Kapov, “Tabu search applied to the quadratic assignment problem”, ORSA Journal on Computing 2(1), 33–45 (1990).
• [41] E.D. Taillard, “Comparison of iterative searches for the quadratic assignment problem”, Location Science 3(2), 87‒105 (1995).
• [42] A. Nyberg and T. Westerlund, “New exact discrete linear reformulation of the quadratic assignment problem”, Technical Report, Abo Akademi University (2011).
• [43] M. Fischetti, M. Monaci, and D. Salvagnin, “Three ideas for the quadratic assignment problem”. CPAIOR 2011, ZIB report 11‒20, 9/13 (2011).
• [44] A. Brüngger, A. Marzetta, J. Clausen, and M. Perregaard, “Joining forces in solving large-scale quadratic assignment problems in parallel”, Proceedings of the 11th International 9Symposium on Parallel Processing, 418–426 (1997).
• [45] K. Anstreicher, N. Brixius, J.-P. Goux, and J. Linderoth, “Solving large quadratic assignment problems on computational grids”, Mathematical Programming 91(3), 563‒588 (2002).
• [46] Y. Li and P.M. Pardalos, “Generating quadratic assignment test problems with known optimal permutations”, Computational Optimization and Applications 1(2), 163‒184 (1992).
• [47] P. Ji, Y. Wu, and H. Liu, “A solution method for the quadratic assignment problem (QAP)”, The 6th International Symposium on Operations Research and Its Applications, Xinjiang, China, 106‒117, (2006).
• [48] A. Misevicius, “An implementation of the iterated tabu search algorithm for the quadratic assignment problem”, OR Spectrum, 34(3), 665‒690 (2012).
• [49] E.D. Taillard and L.M. Gambardella, “Adaptive memories for the quadratic assignment problem”, 1997.
• [50] T. Stützle, “MAX-MIN ant system for quadratic assignment problems”, Research Report AIDA‒97‒04, Department of Computer Science, Darmstadt University of Technology, Germany (1997).
• [51] A. Bölte and U.W. Thonemann, “Optimizing simulated annealing schedules with genetic programming”, European Journal of Operational Research 92(2), 402 – 416 (1996).
• [52] C. Fleurent, Jacques, and J.A. Ferland, “Genetic hybrids for the quadratic assignment problem”, DIMACS Series in Mathematics and Theoretical Computer Science, American Mathematical Society, 173–187 (1993).
• [53] J. Derrac, S. Garcia, D. Molina, and F. Herrera, “A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms”, Swarm Evol. Comput. 1, 3‒18 (2011).

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).