Comparative Study between FA, ACO, and PSO Algorithms for Optimizing Quadratic Assignment Problem
Keywords:
Quadratic Assignment Problem, Facility Location Problems, Firefly Algorithm, Ant Colony Optimization Algorithm, Particle Swarm OptimizationAbstract
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 .
References
Guha, S., & Khuller, S, “Greedy Strikes Back: Improved Facility Location Algorithms” Journal of Algorithms, 31(1), 228–248. (1999)
Wolsey, Laurence A,.et. al. “The Uncapacitated Facility Location Problem”, CM university, Pittsburgh, management science research rep., (1983).
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)
Vygen, Jens, “Approximation algorithms facility location problems” Forschungsinstitut für Diskrete Mathematik, Rheinische Friedrich-Wilhelms-Universität, 1–59, 2005
Verter, Vedat. "Uncapacitated and capacitated facility location problems" Foundations of Location Analysis. Springer US, (2011), 25-37.
Choi, Darwin., "Quadratic Assignment Problems (QAP) and its Size Reduction Method" Math Journal 4(1), (2003).
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
Eliane Maria,.et..al., “A survey for the quadratic assignment problem,” European Journal of Operational Research, vol. 176, (2007), pp. 657–690
R.E. Burkard, “Quadratic Assignment Problems”, EJOR 15, (1984), 283-289.
Taillard, Éric. "Robust taboo search for the quadratic assignment problem", Parallel computing 17(4), (1991), pp.443-455.
Azarbonyad, Hosein, and Reza Babazadeh. "A Genetic Algorithm for solving Quadratic Assignment Problem (QAP)” ,arXiv preprint arXiv:1405.5050, (2014).
Heragu S., “Facilities Design”, Boston, PWS Publishing company, (1997).
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.
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.
Burkard, Rainer E., Stefan E. Karisch, and Franz Rendl. "QAPLIB–a quadratic assignment problem library." ,Journal of Global optimization 10.4 (1997): 391-403.
Yang, Xin-She, and Xingshi He., "Firefly algorithm: recent advances and applications", International Journal of Swarm Intelligence 1(1), (2013): 36-50.
Yang, Xin-She. "Firefly algorithm, Levy flights and global optimization”, Research and development in intelligent systems XXVI. Springer London, (2010), 209-218.
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).
Venter, Gerhard, and Jaroslaw Sobieszczanski-Sobieski. "Particle swarm optimization" American Institute of Aeronautics and Astronautics Journal ,41(8), (2003): 1583-1589.
Bharat Bhushan and Sarath S. Pillai, "Particle Swarm Optimization and Firefly Algorithm: Performance Analysis", IEEE International Advance Computing Conference, (2013).
X.-S. Yang, “Analysis of Algorithms,” in Nature-Inspired Optimization Algorithms, 1sted. London, Elsevier, (2014), pp.15-16
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
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.
Pedersen, Magnus Erik Hvass, and Andrew J. Chipperfield. "Simplifying particle swarm optimization" Applied Soft Computing 10(2), (2010): 618-628.
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.
Jens Clausen, Michael Perregaard, “Solving Large Quadratic Assignment Problems in Parallel”, Computational Optimization and Applications, September 1997, 8(2), pp 111-127.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
