Using Swarm Intelligence for solving NP-Hard Problems
DOI:
https://doi.org/10.25007/ajnu.v6n3a78Keywords:
Swarm Intelligence, NP-Hard problem, Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC), Bat algorithm (BA), Ant Colony Algorithm (ACO)Abstract
Swarm Intelligence algorithms are computational intelligence algorithms inspired from the collective behavior of real swarms such as ant colony, fish school, bee colony, bat swarm, and other swarms in the nature. Swarm Intelligence algorithms are used to obtain the optimal solution for NP-Hard problems that are strongly believed that their optimal solution cannot be found in an optimal bounded time. Travels Salesman Problem (TSP) is an NP-Hard problem in which a salesman wants to visit all cities and return to the start city in an optimal time. This article applies most efficient heuristic based Swarm Intelligence algorithms which are Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC), Bat algorithm (BA), and Ant Colony Optimization (ACO) algorithm to find a best solution for TSP which is one of the most well-known NP-Hard problems in computational optimization. Results are given for different TSP problems comparing the best tours founds by BA, ABC, PSO and ACO.
Downloads
References
Altringham J. D., Bats, (1996), Biology and Behaviour, Oxford University Press.
Andrej Kazakov, (2009), Travelling Salesman Problem: Local Search and Divide and Conquer working together.
Basic J. (2012), A New Hybrid Algorithm for Optimization Using PSO and GDA Appl. Sci. Res., 2(3)2336-2341.
Blum, C. (2005), Ant colony optimization Introduction and recent trends, Physics of Life Reviews, 2(4), 353-373.
Bonabeau E, Dorigo M, Theraulaz G. (1999), Swarm Intelligence: From Natural to Artificial Systems. Journal of Artificial Societies and Social Simulation; 4: 320.
Dorigo M., Maniezzo V., A. (1996), Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Trans. Syst. Man Cybern. B 26 29–41.
Eberhart RC, Kennedy J, (1995), A new optimizer using particles swarm theory[A], Proc Sixth Int Symposium on Micro Machine and Human Science[C], pp. 39-43.
Hochbaum, S. (1997), Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston.
Karaboga D, Basturk B. (2007), A Powerful and Efficient Algorithm for Numeric Function Optimization: Artificial Bee Colony (ABC) Algorithm. Journal of Global Optimization: 459–471.
Karaboga D. (2007), An idea based on honey bee swarm for numerical optimization. Technical Report TR06.Erciyes University.
Karaboga D. (2010), Artificial bee colony algorithm. Scholarpedia.: 6915.
Kennedy J., Eberhart R. (1995), Particle swarm optimization, in: IEEE International Conference on Neural Networks Proceedings, vols. 1–6, pp.1942–1948.
Li, Y.: (2010), Solving TSP by an ACO-and-BOA-based Hybrid Algorithm. In: 2010 International Conference on Computer Application and System Modeling, pp. 189–192. IEEE Press, New York.
Marco Dorigo, Thomas Stu, (2004), Ant Colony Optimization.
Rao RS, Narasimham SVL, (2008), Ramalingaraju M. Optimization of distribution network configuration for loss reduction using artificial bee colony algorithm. International Journal of Electrical Power and Energy Systems Engineering.: 116–122.
Reinelt, (1991), TSPLIB—A traveling salesman problem library, ORSA Journal on Computing 3 (4) 376–384.
Sahni, S. & Gonzalez, (1976), T. P-Complete Approximation Problems. JACM, 23(3), pp.555-565.
Shi YH, Eberhart RC, (1998), A modified particle swarm optimizer[A], IEEE Int Conf on Evolutionary Computation [C], pp. 63-73.
Yang, X.-S. (2010), A new metaheuristic bat-inspired algorithm. In Natureinspired cooperative strategies for optimization (pp. 65(74). Springer.
Downloads
Published
How to Cite
Issue
Section
License
Authors retain copyright
The use of a Creative Commons License enables authors/editors to retain copyright to their work. Publications can be reused and redistributed as long as the original author is correctly attributed.
- Copyright
- The researcher(s), whether a single or joint research paper, must sell and transfer to the publisher (the Academic Journal of Nawroz University) through all the duration of the publication which starts from the date of entering this Agreement into force, the exclusive rights of the research paper/article. These rights include the translation, reuse of papers/articles, transmit or distribute, or use the material or parts(s) contained therein to be published in scientific, academic, technical, professional journals or any other periodicals including any other works derived from them, all over the world, in English and Arabic, whether in print or in electronic edition of such journals and periodicals in all types of media or formats now or that may exist in the future. Rights also include giving license (or granting permission) to a third party to use the materials and any other works derived from them and publish them in such journals and periodicals all over the world. Transfer right under this Agreement includes the right to modify such materials to be used with computer systems and software, or to reproduce or publish it in e-formats and also to incorporate them into retrieval systems.
- Reproduction, reference, transmission, distribution or any other use of the content, or any parts of the subjects included in that content in any manner permitted by this Agreement, must be accompanied by mentioning the source which is (the Academic Journal of Nawroz University) and the publisher in addition to the title of the article, the name of the author (or co-authors), journal’s name, volume or issue, publisher's copyright, and publication year.
- The Academic Journal of Nawroz University reserves all rights to publish research papers/articles issued under a “Creative Commons License (CC BY-NC-ND 4.0) which permits unrestricted use, distribution, and reproduction of the paper/article by any means, provided that the original work is correctly cited.
- Reservation of Rights
The researcher(s) preserves all intellectual property rights (except for the one transferred to the publisher under this Agreement).
- Researcher’s guarantee
The researcher(s) hereby guarantees that the content of the paper/article is original. It has been submitted only to the Academic Journal of Nawroz University and has not been previously published by any other party.
In the event that the paper/article is written jointly with other researchers, the researcher guarantees that he/she has informed the other co-authors about the terms of this agreement, as well as obtaining their signature or written permission to sign on their behalf.
The author further guarantees:
- The research paper/article does not contain any defamatory statements or illegal comments.
- The research paper/article does not violate other's rights (including but not limited to copyright, patent, and trademark rights).
This research paper/article does not contain any facts or instructions that could cause damages or harm to others, and publishing it does not lead to disclosure of any confidential information.