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

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