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

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

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