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

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