بهبود الگوریتم ژنتیک برای حل مسئله ی کوله پشتی صفر و یک با استفاده از پالایش اعضای جمعیت

Publish Year: 1397
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 793

This Paper With 6 Page And PDF Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

این Paper در بخشهای موضوعی زیر دسته بندی شده است:

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

DCBDP04_016

تاریخ نمایه سازی: 24 شهریور 1397

Abstract:

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

Keywords:

Authors

زهرا شیخی دارانی

کارشناسی ارشد مهندسی فناوری اطلاعات، دانشکده مهندسی کامپیوتر، دانشگاه اصفهان،

مرجان کائدی

استادیار، دانشکده مهندسی کامپیوتر، دانشگاه اصفهان،