الگوریتم ژنتیک با مرتب‌سازی نامغلوب برای ساخت درخت پوشای متوازن

نوع مقاله : مقاله پژوهشی فارسی

نویسندگان

دانشکده مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران.

چکیده

این پژوهش نشان می‌دهد که در رابطه با یافتن درخت پوشای متوازن، چگونه می‌توان با بهره‌گیری از الگوریتم چند هدفه تکاملی بدون نیاز به تعیین پارامترهای مربوطه به نمونه‌های با شرایط مطلوب دست یافت. این مسئله متعلق به کلاس پیچیدگی اِن-پی-کامل است، لذا برای ورودی‌های قدری بزرگ نمی‌توان از یک الگوریتم دقیق که غالباً متکی بر جستجوی همه‌جانبه است، بهره برد. الگوریتم‌های تقریبی موجود از یک سو همگی محدود به دریافت پارامتر مرتبط و لحاظ نمودن آن‌ها به‌طور مجزا می‌باشند؛ این امر موجب می‌شود که به‌طورمعمول پاسخ‌هایی باکیفیت پایین‌تر از مطلوب را بیابند. از سویی دیگر روش‌های موجود، مسئله درخت پوشای متوازن را به صورت تک هدفه حل می‌کند؛ که این امر منجر به از دست رفتن اطلاعات فضای جستجوی مسئله و یافتن تنها یک راه‌حل می‌گردد، درحالی‌که در مسائل واقعی، غالباً تصمیم‌گیرندگان برای تصمیم‌گیری بهتر، به چندین نمونه‌ی راه‌حل نیاز دارند. رفع کاستی‌های فوق می‌تواند منجر به یافتن درخت پوشای متوازن با ویژگی‌های برتری گردد، که به‌تبع آن منافع بیشتری در کاربردهای مربوطه مانند شبکه‌های ارتباطی و محاسبات با کارایی بالا، حاصل آید. در این پژوهش، برای غلبه بر چالش‌های فوق، به‌کارگیری بهینه‌سازی چندهدفه تکاملی از طریق الگوریتم ژنتیک با مرتب‌سازی نامغلوب توصیه می‌گردد. راه‌حل پیشنهادی از دو تابع هدف برای بهینه‌‌سازی هم‌زمان وزن درخت پوشا و کوتاه‌ترین مسیر بهره می‌برد. تابع هدف اول، سعی در حداقل‌سازی فاصله هر رأس تا ریشه درخت دارد، تابع هدف دوم به‌گونه‌ای انتخاب شده تا وزن درخت پوشای به‌دست‌آمده کمینه باشد. روش پیشنهادی توسط توابع تخصصی و در محیط پایتون، بر روی یک میکروکامپیوتر هفت هسته‌ای پیاده‌سازی و اجرا گردید. به‌منظور ارزیابی عملکرد الگوریتم پیشنهادی، مجموعه‌ای از گراف‌های تصادفی با رویکرد اردوس و رنی بکار گرفته شدند. الگوریتم پیشنهادی با روش‌های مطرح در حوزه یافتن درخت پوشای متوازن مورد مقایسه قرار گرفت. نتایج آزمایشی نشان می‌دهند که الگوریتم پیشنهادی، در غالب موارد قادر به یافتن پاسخ‌های بهتری نسبت به سایر الگوریتم‌های مورد مقایسه می‌باشد. ضمناً غالباً پاسخ‌های بهینه که به‌طورمعمول تنها از طریق الگوریتم‌های دقیق و بسیار پرهزینه قابل حصول‌اند، را با صرف توان محاسباتی ناچیزی می‌یابد.

کلیدواژه‌ها


[1]       S. M. Ejabati, "Adaptive Increasing/Decreasing PSO for Solving Dynamic Optimization Problems," Journal of Soft Computing and Information Technology, vol. 7, no. 2, pp. 58-70, 2018.
[2]       A. Mohammadi, S.-H. Zahiri, and S.-M. Razavi, "Performance of Intelligent Optimization Methods in IIR System Identification Problems," Journal of Soft Computing and Information Technology, vol. 6, no. 2, pp. 25-39, 2017.
[3]       R. Campos and M. Ricardo, "A fast algorithm for computing minimum routing cost spanning trees," Computer Networks, vol. 52, no. 17, pp. 3229-3247, 2008.
[4]       C. Li, H. Zhang, B. Hao, and J. Li, "A survey on routing protocols for large-scale wireless sensor networks," Sensors, vol. 11, no. 4, pp. 3498-3526, 2011.
[5]       R. Moharam and E. Morsy, "Geneticalgorithms to balanced tree structures in graphs," Swarm and Evolutionary Computation, vol. 32, pp. 132-139, 2017.
[6]       C. A. C. Coello, G. B. Lamont, and D. A. Van Veldhuizen, Evolutionary algorithms for solving multi-objective problems. Springer, 2007.
[7]       P. Ngatchou, A. Zarei, and A. El-Sharkawi, "Pareto multi objective optimization," in Proceedings of the 13th International Conference on, Intelligent Systems Application to Power Systems, 2005, pp. 84-91: IEEE.
[8]       W. Gao, M. Pourhassan, V. Roostapour, and F. Neumann, "Runtime Analysis of Evolutionary Multi-objective Algorithms Optimising the Degree and Diameter of Spanning Trees," in International Conference on Evolutionary Multi-Criterion Optimization, 2019, pp. 504-515: Springer.
[9]       S. Ronoud and S. Asadi, "An evolutionary deep belief network extreme learning-based for breast cancer diagnosis," Soft Computing, vol. 23, no. 24, pp. 13139-13159, 2019.
[10]     K. Deb, "A robust evolutionary framework for multi-objective optimization," in Proceedings of the 10th annual conference on Genetic and evolutionary computation, 2008, pp. 633-640.
[11]     P. ERDdS and A. wi, "On random graphs I," Publ. Math. Debrecen, vol. 6, pp. 290-297, 1959.
[12]     S. Khuller, B. Raghavachari, and N. Young, "Balancing minimum spanning trees and shortest-path trees," Algorithmica, vol. 14, no. 4, pp. 305-321, 1995.
[13]     M. Souier, M. Dahane, and F. Maliki, "An NSGA-II-based multiobjective approach for real-time routing selection in a flexible manufacturing system under uncertainty and reliability constraints," The International Journal of Advanced Manufacturing Technology, vol. 100, no. 9-12, pp. 2813-2829, 2019.
[14]     K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEEtransactions on evolutionary computation, vol. 6, no. 2, pp. 182-197, 2002.
[15]     K. Singh and S. Sundar, "Artifical bee colony algorithm using problem-specific neighborhood strategies for the tree t-spanner problem," Applied Soft Computing, vol. 62, pp. 110-118, 2018.
[16]     S. Sundar, "A Steady-State Genetic Algorithm for the Tree t-Spanner Problem," in Soft Computing: Theories and Applications: Springer, 2019, pp. 387-398.
[17]     Y. Ran, Z. Chen, S. Tang, and Z. Zhang, "Primal dual based algorithm for degree-balanced spanning tree problem," Applied Mathematics and Computation, vol. 316, pp. 167-173, 2018.
[18]     M. H. Tahan and S. Asadi, "MEMOD: a novel multivariate evolutionary multi-objective discretization," Soft Computing, vol. 22, no. 1, pp. 301-323, 2018.
[19]     M. H. Tahan and S. Asadi, "EMDID: Evolutionary multi-objective discretization for imbalanced datasets," Information Sciences, vol. 432, pp. 442-461, 2018.
[20]     K. Bharath-Kumar and J. Jaffe, "Routing to multiple destinations in computer networks," IEEE Transactions on communications, vol. 31, no. 3, pp. 343-351, 1983.
[21]     J. Cong, A. Kahng, G. Robins, M. Sarrafzadeh, and C. Wong, "Performance-driven global routing for cell based ics," in [1991 Proceedings] IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1991, pp. 170-173: IEEE.
[22]     J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C.-K. Wong, "Provably good performance-driven global routing," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 11, no. 6, pp. 739-752, 1992.
[23]     B. Awerbuch, A. Baratz, and D. Peleg, "Cost-sensitive analysis of communication protocols," Massachusetts Inst of Tech Cambridg Lab for Computer Science,1991.
[24]     A. Avokh and G. Mirjalily, "Dynamicbalanced spanning tree (DBST) for data aggregation in wireless sensor networks," in 2010 5th international symposium on telecommunications, 2010, pp. 391-396: IEEE.
[25]     R. Moharam, E. Morsy, and I. A. Ismail, "Genetic algorithms for balanced spanning tree problem," in 2015 Federated Conference on Computer Science and Information Systems (FedCSIS), 2015, pp. 537-545: IEEE.
[26]     C. J. Alpert et al., "Prim-Dijkstra Revisited: Achieving Superior Timing-driven Routing Trees," in Proceedings of the 2018 International Symposium on Physical Design, 2018, pp. 10-17: ACM.
[27]     L. Davis, D. Orvosh, A. Cox, and Y. Qiu, "A genetic algorithm for survivable network design," in Proceedings of the 5th International Conference on Genetic Algorithms, 1993, pp. 408-415: Morgan Kaufmann Publishers Inc.
[28]     P. Piggott and F. Suraweera, "Encoding graphs for genetic algorithms: An investigation using the minimum spanning tree problem," in Progress in Evolutionary Computation: Springer, 1993, pp. 305-314.
[29]     R. Mathur, I. Khan, and V. Choudhary, "Genetic algorithm for dynamic capacitated minimum spanning tree," International Journal of Computer Technology and Applications, vol. 4, no. 3, p. 404, 2013.
[30]     Q. P. Tan, "A genetic approach for solving minimum routing cost spanning tree problem," International Journal of Machine Learning and Computing, vol. 2, no. 4, p. 410, 2012.
[31]     S. Balaji, V. Swaminathan, and K. Kannan, "Approximating maximum weighted independent set using vertex Support," International Journal of Computational and Mathemtical Sciences1, vol. 3, no. 8, pp. 406-411, 2009.
[32]     A. Cayley, "A theorem on trees," The Quarterly Journal of Mathematics, vol. 23, pp. 376-378, 1889.
[33]     D. B. Johnson, "Finding all the elementary circuits of a directed graph," SIAMJournal on Computing, vol. 4, no. 1, pp. 77-84, 1975.