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

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