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

سال انتشار: 1392
محل انتشار: همایش ملی کاربرد سیستم های هوشمند (محاسبات نرم) در علوم و صنایع
کد COI اختصاصی: AISST01_138
زبان مقاله: فارسی
تعداد مشاهده: 4730

نویسندگان

کارشناس ارشد مهندسی کامپیوتر- دانشگاه علوم و تحقیقات خراسان رضوی

چکیده

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

کلیدواژه ها

الگوریتم ژنتیک، بهینه سازی، کوله پشتی، fitness

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.