یافتن کوتاهترین مسیرهای ناهمپوشان با استفاده از الگوریتم NSGA-II
محل انتشار: نخستین کنفرانس بین المللی فناوری اطلاعات
سال انتشار: 1394
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 538
فایل این مقاله در 20 صفحه با فرمت PDF و WORD قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
FBFI01_066
تاریخ نمایه سازی: 9 مرداد 1395
چکیده مقاله:
مسئله کوتاهترین مسیر یکی از مسائل کلاسیک در تئوری گرافهاست که کاربرد وسیعی در زمینه های مختلف مثل حمل و نقل، ارتباطات، الکترونیک و ... دارد. این مسئله انواع گوناگونی دارد و الگوریتم های مختلفی برای حل آنها پیشنهاد شده است. در این تحقیق نوعی مسئله چند هدفه به نام کوتاهترین مسیرهای ناهمپوشان مطرح می شود که در آن، هدف یافتن n مسیر مجزا از مجموعه ای از مبدأها به مجموعه ای از مقصدها (بصورت جفت های مبدأ- مقصد)، با رعایت سه شرط است: 1) کلیه مسیرها باید مسیرهایی ساده باشند، 2) مسیرها نباید هیچ گونه اشتراک و همپوشانی با یکدیگر داشته باشند، 3) کوتاهترین مسیر ممکن بین هر جفت مبدأ - مقصد پیدا شود. الگوریتم ژنتیک مرتب سازی نامغلوب 2 (NSGA-II) از الگوریتم های چند هدفه ای است که در بسیاری از مسائل بهینه سازی چند هدفه استفاده شده است. در این تحقیق یک الگوریتم NSGA-II پیشنهادی برای مسئله کوتاهترین مسیرهای ناهمپوشان مطرح شده و عملکرد آن با یک الگوریتم دیگر به نام الگوریتم ژنتیک حاصل جمع توابع هزینه ی وزن دهی شده (SWCF) مقایسه می گردد. نتایج بدست آمده حاکی از این است که الگوریتم NSGA-II پیشنهادی، چه از لحاظ کیفی و چه کمی، عملکرد بهتری نسبت به الگوریتم ژنتیک SWCF دارد.
کلیدواژه ها:
نویسندگان
امین نجارپور
گروه کامپیوتر، واحد علوم و تحقیقات خوزستان، دانشگاه آزاد اسلامی، اهواز، ایران
مهدی صادق زاده
گروه کامپیوتر، واحد علوم و تحقیقات خوزستان، دانشگاه آزاد اسلامی، اهواز، ایران
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :