Using Swarm Intelligence for solving NP-Hard Problems
DOI:
https://doi.org/10.25007/ajnu.v6n3a78الكلمات المفتاحية:
Swarm Intelligence، NP-Hard problem، Particle Swarm Optimization (PSO)، Artificial Bee Colony (ABC)، Bat algorithm (BA)، Ant Colony Algorithm (ACO)الملخص
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.
التنزيلات
المراجع
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.
التنزيلات
منشور
كيفية الاقتباس
إصدار
القسم
الرخصة
بيان الحقوق الفكرية
حقوق التأليف
يوافق المؤلفون الذين ينشرون في هذه المجلة على المصطلحات التالية:
١. يحتفظ المؤلفون بحقوق الطبع والنشر ومنح حق المجلة في النشر الأول مع العمل المرخص له في نفس الوقت بموجب ترخيص المشاع الإبداعي [سيسي بي-نك-ند 4.0] الذي يسمح للآخرين بمشاركة العمل مع الإقرار بحقوق التأليف والنشر الأولي في هذه المجلة.
٢. يمكن للمؤلفين الدخول في ترتيبات تعاقدية إضافية منفصلة للتوزيع غير الحصري للنسخة المنشورة من المجلة من العمل (على سبيل المثال، نشرها في مستودع مؤسسي أو نشرها في كتاب) مع الإقرار بنسخة أولية نشر في هذه المجلة.
٣. يسمح للمؤلفين وتشجيعهم على نشر عملهم عبر الإنترنت (على سبيل المثال، في المستودعات المؤسسية أو على موقعهم على الويب) قبل وأثناء عملية التقديم، حيث يمكن أن يؤدي إلى التبادلات الإنتاجية، فضلا عن الاستشهاد المبكر والأكبر للعمل المنشورة ( انظر تأثير النفاذ المفتوح).
نقل حقوق الطبع والنشر
بيان الخصوصية
المجلة الأكاديمية لجامعة نوروز ملتزمة بحماية خصوصية مستخدمي موقع المجلة هذا. سيتم استخدام الأسماء والتفاصيل الشخصية وعناوين البريد الإلكتروني التي تم إدخالها في هذا الموقع الإلكتروني فقط للأغراض المعلنة لهذه المجلة ولن يتم إتاحتها لأطراف ثالثة بدون إذن المستخدم أو الإجراءات القانونية الواجبة. موافقة المستخدمين مطلوبة لتلقي الاتصالات من المجلة الأكاديمية لجامعة نوروز للأغراض المعلنة للمجلة. ويمكن توجيه الاستفسارات المتعلقة بالخصوص إلى [email protected]