Comparative Study between FA, ACO, and PSO Algorithms for Optimizing Quadratic Assignment Problem

Vanita Jain¹ , Aarushi Jain² , Achin Jain³ , Arun Kumar Dubey⁴

1. Bharati Vidyapeeth’s College of Engineering, New Delhi, India.
2. FPM(Information Systems), IIM, Indore, India.
3. Bharati Vidyapeeth’s College of Engineering, New Delhi, India.
4. Bharati Vidyapeeth’s College of Engineering, New Delhi, India.

Section:Research Paper, Product Type: Isroset-Journal
Vol.6 , Issue.2 , pp.76-81, Apr-2018

CrossRef-DOI:   https://doi.org/10.26438/ijsrcse/v6i2.7681

Online published on Apr 30, 2018

Copyright © Vanita Jain, Aarushi Jain, Achin Jain, Arun Kumar Dubey . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

689 Views    263 Downloads    217 Downloads

Abstract :
Many advancements have been made in the development of optimization algorithms which are based on the evolutionary concept of behavior of biotic creatures like fish, ants, birds etc. This paper compares three such nature inspired algorithms; firefly, particle swarm optimization and ant colony optimization algorithm for optimizing Quadratic Assignment Problem. These algorithms are compared on the grounds of their time of computation of result, the no. of iterations required to solve the problem, and the accuracy .

Key-Words / Index Term :
Quadratic Assignment Problem; Facility Location Problems; Firefly Algorithm; Ant Colony Optimization Algorithm; Particle Swarm Optimization

References :
[1] Guha, S., & Khuller, S, “Greedy Strikes Back: Improved Facility Location Algorithms” Journal of Algorithms, 31(1), 228–248. (1999)
[2] Wolsey, Laurence A,.et. al. “The Uncapacitated Facility Location Problem”, CM university, Pittsburgh, management science research rep., (1983).
[3] Arya, V., Arya, V., Garg, N., Garg, N., Khandekar, R., Khandekar, R., Pandit, V., “Local search heuristic for k-median and facility location problems”, Proceedings of the Thirty-Third Annual {ACM} Symposium on Theory of Computing, 33(3), 21–29, (2001)
[4] Vygen, Jens, “Approximation algorithms facility location problems” Forschungsinstitut für Diskrete Mathematik, Rheinische Friedrich-Wilhelms-Universität, 1–59, 2005
[5] Verter, Vedat. "Uncapacitated and capacitated facility location problems" Foundations of Location Analysis. Springer US, (2011), 25-37.
[6] Choi, Darwin., "Quadratic Assignment Problems (QAP) and its Size Reduction Method" Math Journal 4(1), (2003).
[7] P. Pardalos, F. Rendl, and H. Wolkowicz, “The quadratic assignment problem: A survey and recent developments” DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, (1994), 1–42
[8] Eliane Maria,.et..al., “A survey for the quadratic assignment problem,” European Journal of Operational Research, vol. 176, (2007), pp. 657–690
[9] R.E. Burkard, “Quadratic Assignment Problems”, EJOR 15, (1984), 283-289.
[10] Taillard, Éric. "Robust taboo search for the quadratic assignment problem", Parallel computing 17(4), (1991), pp.443-455.
[11] Azarbonyad, Hosein, and Reza Babazadeh. "A Genetic Algorithm for solving Quadratic Assignment Problem (QAP)” ,arXiv preprint arXiv:1405.5050, (2014).
[12] Heragu S., “Facilities Design”, Boston, PWS Publishing company, (1997).
[13] Maniezzo, Vittorio, and Alberto Colorni. "The ant system applied to the quadratic assignment problem" Knowledge and Data Engineering, IEEE Transactions on 11(5), (1999): 769-778.
[14] Gambardella, L. M., ÉD Taillard, and M. Dorigo. “Ant Colonies for the Quadratic Assignment Problem”, The Journal of the Operational Research Society 50(2), (1999): 167–176.
[15] Burkard, Rainer E., Stefan E. Karisch, and Franz Rendl. "QAPLIB–a quadratic assignment problem library." ,Journal of Global optimization 10.4 (1997): 391-403.
[16] Yang, Xin-She, and Xingshi He., "Firefly algorithm: recent advances and applications", International Journal of Swarm Intelligence 1(1), (2013): 36-50.
[17] Yang, Xin-She. "Firefly algorithm, Levy flights and global optimization”, Research and development in intelligent systems XXVI. Springer London, (2010), 209-218.
[18] Dorigo, M., & Stu¨tzle, T., “The ant colony optimization metaheuristic: Algorithms, applications and advances”, In F. Glover & G. Kochenberger (Eds.), Handbook of Metaheuristics, vol. 57 (2002).
[19] Venter, Gerhard, and Jaroslaw Sobieszczanski-Sobieski. "Particle swarm optimization" American Institute of Aeronautics and Astronautics Journal ,41(8), (2003): 1583-1589.
[20] Bharat Bhushan and Sarath S. Pillai, "Particle Swarm Optimization and Firefly Algorithm: Performance Analysis", IEEE International Advance Computing Conference, (2013).
[21] X.-S. Yang, “Analysis of Algorithms,” in Nature-Inspired Optimization Algorithms, 1sted. London, Elsevier, (2014), pp.15-16
[22] S. Agarwal, “Edge Detection in blurred images using Ant Colony Optimization Techniques”, International Journal of Scientific Research in Computer Science and Engineering, Vol.1, Issue.2, pp.21-24, 2013
[23] J. E. Bell and P. R. McMullen, “Ant colony optimization techniques for the vehicle routing problem,” Adv. Eng. Informatics, 18(1), (2004), pp. 41–48.
[24] Pedersen, Magnus Erik Hvass, and Andrew J. Chipperfield. "Simplifying particle swarm optimization" Applied Soft Computing 10(2), (2010): 618-628.
[25] Russell C. Eberhart and Yuhui Shi, “Particle swarm optimization: Developments, applications and resources,” in Proc. IEEE Int. Conf. Evolutionary Computation, 01, (2001) pp. 81-86.
[26] Jens Clausen, Michael Perregaard, “Solving Large Quadratic Assignment Problems in Parallel”, Computational Optimization and Applications, September 1997, 8(2), pp 111-127