الگوریتم ژنتیک با مرتب سازی نامغلوب برای ساخت درخت پوشای متوازن
Publish Year: 1399
Type: Journal paper
Language: Persian
View: 60
This Paper With 17 Page And PDF Format Ready To Download
- Certificate
- I'm the author of the paper
این Paper در بخشهای موضوعی زیر دسته بندی شده است:
Export:
Document National Code:
JR_JSCIT-9-3_006
Index date: 16 October 2024
الگوریتم ژنتیک با مرتب سازی نامغلوب برای ساخت درخت پوشای متوازن abstract
این پژوهش نشان می دهد که در رابطه با یافتن درخت پوشای متوازن، چگونه می توان با بهره گیری از الگوریتم چند هدفه تکاملی بدون نیاز به تعیین پارامترهای مربوطه به نمونه های با شرایط مطلوب دست یافت. این مسئله متعلق به کلاس پیچیدگی ان-پی-کامل است، لذا برای ورودی های قدری بزرگ نمی توان از یک الگوریتم دقیق که غالبا متکی بر جستجوی همه جانبه است، بهره برد. الگوریتم های تقریبی موجود از یک سو همگی محدود به دریافت پارامتر مرتبط و لحاظ نمودن آن ها به طور مجزا می باشند؛ این امر موجب می شود که به طورمعمول پاسخ هایی باکیفیت پایین تر از مطلوب را بیابند. از سویی دیگر روش های موجود، مسئله درخت پوشای متوازن را به صورت تک هدفه حل می کند؛ که این امر منجر به از دست رفتن اطلاعات فضای جستجوی مسئله و یافتن تنها یک راه حل می گردد، درحالی که در مسائل واقعی، غالبا تصمیم گیرندگان برای تصمیم گیری بهتر، به چندین نمونه ی راه حل نیاز دارند. رفع کاستی های فوق می تواند منجر به یافتن درخت پوشای متوازن با ویژگی های برتری گردد، که به تبع آن منافع بیشتری در کاربردهای مربوطه مانند شبکه های ارتباطی و محاسبات با کارایی بالا، حاصل آید. در این پژوهش، برای غلبه بر چالش های فوق، به کارگیری بهینه سازی چندهدفه تکاملی از طریق الگوریتم ژنتیک با مرتب سازی نامغلوب توصیه می گردد. راه حل پیشنهادی از دو تابع هدف برای بهینه سازی هم زمان وزن درخت پوشا و کوتاه ترین مسیر بهره می برد. تابع هدف اول، سعی در حداقل سازی فاصله هر راس تا ریشه درخت دارد، تابع هدف دوم به گونه ای انتخاب شده تا وزن درخت پوشای به دست آمده کمینه باشد. روش پیشنهادی توسط توابع تخصصی و در محیط پایتون، بر روی یک میکروکامپیوتر هفت هسته ای پیاده سازی و اجرا گردید. به منظور ارزیابی عملکرد الگوریتم پیشنهادی، مجموعه ای از گراف های تصادفی با رویکرد اردوس و رنی بکار گرفته شدند. الگوریتم پیشنهادی با روش های مطرح در حوزه یافتن درخت پوشای متوازن مورد مقایسه قرار گرفت. نتایج آزمایشی نشان می دهند که الگوریتم پیشنهادی، در غالب موارد قادر به یافتن پاسخ های بهتری نسبت به سایر الگوریتم های مورد مقایسه می باشد. ضمنا غالبا پاسخ های بهینه که به طورمعمول تنها از طریق الگوریتم های دقیق و بسیار پرهزینه قابل حصول اند، را با صرف توان محاسباتی ناچیزی می یابد.
الگوریتم ژنتیک با مرتب سازی نامغلوب برای ساخت درخت پوشای متوازن Keywords:
الگوریتم ژنتیک با مرتب سازی نامغلوب برای ساخت درخت پوشای متوازن authors
Marzieh Hajizadeh Tahan
دانشکده مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران.
Mohammad Ghasemzadeh
دانشکده مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران.
Ali Mohammad Latif
دانشکده مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران.
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :