|
|
الگوریتم ژنتیک با مرتبسازی نامغلوب برای ساخت درخت پوشای متوازن
|
|
|
|
|
نویسنده
|
حاجیزاده طحان مرضیه ,قاسم زاده محمد ,لطیف علی محمد
|
منبع
|
رايانش نرم و فناوري اطلاعات - 1399 - دوره : 9 - شماره : 3 - صفحه:67 -82
|
|
|
چکیده
|
این پژوهش نشان میدهد که در رابطه با یافتن درخت پوشای متوازن، چگونه میتوان با بهرهگیری از الگوریتم چند هدفه تکاملی بدون نیاز به تعیین پارامترهای مربوطه به نمونههای با شرایط مطلوب دست یافت. این مسئله متعلق به کلاس پیچیدگی اِنپیکامل است، لذا برای ورودیهای قدری بزرگ نمیتوان از یک الگوریتم دقیق که غالباً متکی بر جستجوی همهجانبه است، بهره برد. الگوریتمهای تقریبی موجود از یک سو همگی محدود به دریافت پارامتر مرتبط و لحاظ نمودن آنها بهطور مجزا میباشند؛ این امر موجب میشود که بهطورمعمول پاسخهایی باکیفیت پایینتر از مطلوب را بیابند. از سویی دیگر روشهای موجود، مسئله درخت پوشای متوازن را به صورت تک هدفه حل میکند؛ که این امر منجر به از دست رفتن اطلاعات فضای جستجوی مسئله و یافتن تنها یک راهحل میگردد، درحالیکه در مسائل واقعی، غالباً تصمیمگیرندگان برای تصمیمگیری بهتر، به چندین نمونهی راهحل نیاز دارند. رفع کاستیهای فوق میتواند منجر به یافتن درخت پوشای متوازن با ویژگیهای برتری گردد، که بهتبع آن منافع بیشتری در کاربردهای مربوطه مانند شبکههای ارتباطی و محاسبات با کارایی بالا، حاصل آید. در این پژوهش، برای غلبه بر چالشهای فوق، بهکارگیری بهینهسازی چندهدفه تکاملی از طریق الگوریتم ژنتیک با مرتبسازی نامغلوب توصیه میگردد. راهحل پیشنهادی از دو تابع هدف برای بهینهسازی همزمان وزن درخت پوشا و کوتاهترین مسیر بهره میبرد. تابع هدف اول، سعی در حداقلسازی فاصله هر راس تا ریشه درخت دارد، تابع هدف دوم بهگونهای انتخاب شده تا وزن درخت پوشای بهدستآمده کمینه باشد. روش پیشنهادی توسط توابع تخصصی و در محیط پایتون، بر روی یک میکروکامپیوتر هفت هستهای پیادهسازی و اجرا گردید. بهمنظور ارزیابی عملکرد الگوریتم پیشنهادی، مجموعهای از گرافهای تصادفی با رویکرد اردوس و رنی بکار گرفته شدند. الگوریتم پیشنهادی با روشهای مطرح در حوزه یافتن درخت پوشای متوازن مورد مقایسه قرار گرفت. نتایج آزمایشی نشان میدهند که الگوریتم پیشنهادی، در غالب موارد قادر به یافتن پاسخهای بهتری نسبت به سایر الگوریتمهای مورد مقایسه میباشد. ضمناً غالباً پاسخهای بهینه که بهطورمعمول تنها از طریق الگوریتمهای دقیق و بسیار پرهزینه قابل حصولاند، را با صرف توان محاسباتی ناچیزی مییابد.
|
کلیدواژه
|
درخت پوشای متوازن، درخت کوتاهترین مسیر، درخت پوشای کمینه، مسائل چندهدفه تکاملی
|
آدرس
|
دانشگاه یزد, دانشکده مهندسی کامپیوتر, گروه مهندسی کامپیوتر, ایران, دانشگاه یزد, دانشکده مهندسی کامپیوتر, گروه مهندسی کامپیوتر, ایران, دانشگاه یزد, دانشکده مهندسی کامپیوتر, گروه مهندسی کامپیوتر, ایران
|
پست الکترونیکی
|
alatif@yazd.ac.ir
|
|
|
|
|
|
|
|
|
A non-dominated genetic algorithm for constructing balanced spanning tree
|
|
|
Authors
|
Latif Ali Mohammad ,Hajizadeh Tahan Marzieh ,Ghasemzadeh Mohammad
|
Abstract
|
This research shows how we can find Balanced Spanning Trees, without the need to determine the relevant parameters, by using an evolutionary multiobjective algorithm. This problem belongs to the complexity class NPcomplete; 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 realworld problems, decisionmakers often need several solutions to make a better decision. Overcoming the abovementioned 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 highperformance computing projects. In this research, in order to overcome the above challenge, the use of evolutionary multiobjective optimization via Nondominated 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 sevencore 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
|
|
|
|
|
|
|
|
|
|
|
|