@article { author = {Hajizadeh Tahan, Marzieh and Ghasemzadeh, Mohammad and Latif, Ali Mohammad}, title = {A non-dominated genetic algorithm for constructing balanced spanning tree}, journal = {Journal of Soft Computing and Information Technology}, volume = {9}, number = {3}, pages = {67-82}, year = {2020}, publisher = {Babol Noshirvani University of Technology}, issn = {2383-1006}, eissn = {2588-4913}, doi = {}, abstract = {This research shows how we can find Balanced Spanning Trees, without the need to determine the relevant parameters, by using an evolutionary multi-objective algorithm. This problem belongs to the complexity class NP-complete; therefore, for big graphs, we cannot use exact algorithms, which often rely on exhaustive search. The existing approximate algorithms are all limited to obtaining the related parameter(s) and considering them separately during their computations; this usually leads to finding solution with lower quality than desired. On the other hand, the existing methods solve the problem of the balanced spanning tree as a single objective; which loss search space information and finding only one solution, while in real-world problems, decision-makers often need several solutions to make a better decision. Overcoming the above-mentioned shortcomings leads to finding a balanced spanning tree with better characteristics; which in turn, yields more benefits in relevant applications, such as communication networks and high-performance computing projects. In this research, in order to overcome the above challenge, the use of evolutionary multi-objective optimization via Non-dominated Sorting Genetic Algorithm - NSGA is recommended. The proposed solution uses two objective functions to simultaneously optimize the weight of the spanning tree and the shortest path. The first objective function attempts to minimize the distance between each vertex and the root of the tree. The second objective function is selected to minimize the weight of the obtained spanning tree. The proposed method was implemented and run in a Python environment by specialized functions, on a seven-core microcomputer. In order to evaluate the performance of the proposed algorithm, a set of random graphs by Erdos and Renyi approaches were used. The proposed algorithm was compared with the state of the art methods in the problem of finding the balanced spanning tree. Experimental results show that the proposed algorithm is often able to find better responses than the other algorithms compared. The experimental results show that the proposed algorithm was always able to find highly ranked Balanced Spanning Trees. Meanwhile, often the optimal solutions, which can only be obtained through exact and very costly algorithms, were found, with teeny computations.}, keywords = {Balanced Spanning Tree,Shortest Path Tree,Minimum Spanning Tree,Evolutionary Multi-Objective Problems}, title_fa = {الگوریتم ژنتیک با مرتب‌سازی نامغلوب برای ساخت درخت پوشای متوازن}, abstract_fa = {این پژوهش نشان می‌دهد که در رابطه با یافتن درخت پوشای متوازن، چگونه می‌توان با بهره‌گیری از الگوریتم چند هدفه تکاملی بدون نیاز به تعیین پارامترهای مربوطه به نمونه‌های با شرایط مطلوب دست یافت. این مسئله متعلق به کلاس پیچیدگی اِن-پی-کامل است، لذا برای ورودی‌های قدری بزرگ نمی‌توان از یک الگوریتم دقیق که غالباً متکی بر جستجوی همه‌جانبه است، بهره برد. الگوریتم‌های تقریبی موجود از یک سو همگی محدود به دریافت پارامتر مرتبط و لحاظ نمودن آن‌ها به‌طور مجزا می‌باشند؛ این امر موجب می‌شود که به‌طورمعمول پاسخ‌هایی باکیفیت پایین‌تر از مطلوب را بیابند. از سویی دیگر روش‌های موجود، مسئله درخت پوشای متوازن را به صورت تک هدفه حل می‌کند؛ که این امر منجر به از دست رفتن اطلاعات فضای جستجوی مسئله و یافتن تنها یک راه‌حل می‌گردد، درحالی‌که در مسائل واقعی، غالباً تصمیم‌گیرندگان برای تصمیم‌گیری بهتر، به چندین نمونه‌ی راه‌حل نیاز دارند. رفع کاستی‌های فوق می‌تواند منجر به یافتن درخت پوشای متوازن با ویژگی‌های برتری گردد، که به‌تبع آن منافع بیشتری در کاربردهای مربوطه مانند شبکه‌های ارتباطی و محاسبات با کارایی بالا، حاصل آید. در این پژوهش، برای غلبه بر چالش‌های فوق، به‌کارگیری بهینه‌سازی چندهدفه تکاملی از طریق الگوریتم ژنتیک با مرتب‌سازی نامغلوب توصیه می‌گردد. راه‌حل پیشنهادی از دو تابع هدف برای بهینه‌‌سازی هم‌زمان وزن درخت پوشا و کوتاه‌ترین مسیر بهره می‌برد. تابع هدف اول، سعی در حداقل‌سازی فاصله هر رأس تا ریشه درخت دارد، تابع هدف دوم به‌گونه‌ای انتخاب شده تا وزن درخت پوشای به‌دست‌آمده کمینه باشد. روش پیشنهادی توسط توابع تخصصی و در محیط پایتون، بر روی یک میکروکامپیوتر هفت هسته‌ای پیاده‌سازی و اجرا گردید. به‌منظور ارزیابی عملکرد الگوریتم پیشنهادی، مجموعه‌ای از گراف‌های تصادفی با رویکرد اردوس و رنی بکار گرفته شدند. الگوریتم پیشنهادی با روش‌های مطرح در حوزه یافتن درخت پوشای متوازن مورد مقایسه قرار گرفت. نتایج آزمایشی نشان می‌دهند که الگوریتم پیشنهادی، در غالب موارد قادر به یافتن پاسخ‌های بهتری نسبت به سایر الگوریتم‌های مورد مقایسه می‌باشد. ضمناً غالباً پاسخ‌های بهینه که به‌طورمعمول تنها از طریق الگوریتم‌های دقیق و بسیار پرهزینه قابل حصول‌اند، را با صرف توان محاسباتی ناچیزی می‌یابد.}, keywords_fa = {درخت پوشای متوازن,درخت کوتاه‌ترین مسیر,درخت پوشای کمینه,مسائل چندهدفه تکاملی}, url = {https://jscit.nit.ac.ir/article_104836.html}, eprint = {https://jscit.nit.ac.ir/article_104836_208f642ae1d907c810f355ff14d1ea7a.pdf} }