بخشی از مقاله
چکیده
تحقیق حاضر در صدد حل مسأله کوله پشتی با استفاده از الگوریتم زنبور عسل می باشد. پژوهش حاضر کاربردی می باشد. در دهه های اخیر، روش های تکاملی و فراکاوشی به عنوان یک ابزار جستجو و بهینه سازی در حوزه های مختلفی مانند علوم، تجارت و مهندسی مورد استفاده قرار گرفته اند. وسعت دامنه کاربرد، سهولت استفاده و قابلیت دستیابی به جواب نزدیک به بهینه مطلق از جمله دلایل موفقیت این روش ها می باشد. الگوریتم زنبور عسل به عنوان یک روش بهینه سازی نشأت گرفته از رفتار زنبور عسل می باشد به طوری که در این الگوریتم با تعداد قبولی از پروازها نتایج مناسب و نزدیک به بهینه در مسأله کوله پشتی 0و1 را ارائه می دهد. در این تحقیق با استفاده از نرم افزار متلب سعی بر این است که با تعداد پروازهای رندوم بهترین جواب ها را در بهینه سازی مسأله کوله پشتی به دست بیاوریم.
واژگان کلیدی: الگوریتم زنبور عسل، مسأله کوله پشتی، بهینه سازی، نرم افزار متلب
مقدمه
مسائل غیر چند جمله ای - NP - 1 به مسائلی اطلاق می شود که با زیاد شدن ابعاد مسئله، فضای جستجوی آن ها به صورت نمایی افزایش می یابد. این مسائل از طریق معادلات ریاضی به سختی قابل حل هستند، و با افزایش ابعاد مسئله امکان استفاده از این روش ها غیر ممکن می گردد. مسائل NP به دو دسته NP-Hard و NP-Complete تقسیم می شوند. حالت NP-Complete مربوط به مسائل تصمیم گیری است و حالت NP-Hard بیشتر مربوط به مسائل بهینه سازی است. در روش های بهینه سازی بر مبنای مشتق گیری مانند روش کاهش گرادیان، تلاش در جهت رسیدن به پاسخ بهینه، با حرکت روی مسیر نمودار خطا صورت می گیرد. در نتیجه این روش ها برای حل مسائل NP نامناسب می باشند، زیرا مسائل NP دارای مینیمم های محلی زیادی هستند، و این روش هااصولاً منجر به دستیابی به یکی از نزدیک ترین مینیمم های محلی به راه حل تصادفی اولیه می گردند.
الگوریتم های تکاملی مانند الگوریتم ژنتیک - GA - 2، الگوریتم بهینه سازی ذرات - PSO - 3، الگوریتم بهینه سازی کلونی مورچه - ACO - 4 و الگوریتم کلونی زنبورهای مصنوعی5 - ABC - الگوریتم هایی مبتنی بر جمعیت هستند که به اطلاعات مشتق وابسته نیستند، و اشکال افتادن در مینیمم های محلی را ندارند و می توانند تمام فضای جستجو را به طور مؤثری بررسی نمایند. نمونه ای از این گونه مسائل را در مسائلی همچون فروشنده دوره گرد و کوله پشتی می توان مشاهده کرد که بهترین راه حل برای حل این گونه مسائل، استفاده از الگوریتم های تکاملی می باشد - ثابت، . - 1390در این مقاله در بخش اول توضیح مختصری در باره مسئله کوله پشتی و در بخش دوم تعریف الگوریتم زنبور عسل و گام های الگوریتم توضیح داده شده است. بخش سوم مربوط به شبیه سازی مسئله و بخش چهارم نتیجه گیری می باشد.
-1مسئله کوله پشتی
مسئله کوله پشتی بیش از یک قرن مورد مطالعه قرار گرفته و اولین بررسی در سال 1897 انجام گرفته است 2003 - . - Lucic,P., and Teodorovic,Dهر چند اولین داده های ثبت شده در این مورد، به کارهای ریاضی دانی به نام توبیاس دانتزیگ6 بر می گردد، چیزی با عنوان مسئله ی کوله پشتیقبلاً در میان عامه ی مردم وجود داشت . - Gen, M., and Cheng, R.W, 1997 - مسئله ی کوله پشتی انواع مختلف دارد که یکی از آن مسئله کوله پشتی درجه دوم است که اولین بار توسط گالو، هامرو سیمون در سال 1960مطرح شد . - Fogel, D.B, 2000 - از دید علوم کامپیوتر، مسئله کوله پشتی شایان توجه است زیرا:
• الگوریتمی با زمان اجرای شبه چند جمله ای با استفاده از برنامه نویسی پویا دارد.
·الگوریتمی تقریبی با زمان چند جمله ای دارد که الگوریتم های با زمان شبه چند جمله ای به عنوان یک زیر برنامه استفاده می کند.
-1-1 مسئله کوله پشتی انواع مختلفی دارد که ما به چند نمونه از آن اشاره می کنیم:
·مسئله کوله پشتی 0و:1 معروف ترین نوع از مسئله کوله پشتی، مسئله کوله پشتی 0و1 است. یعنی تعداد از هر شی، یا 0 است - آن شی را انتخاب نمی کنیم - یا 1 - آن شی انتخاب می شود - - ویکی پدیا - .
·مسئله کوله پشتی مجموعه - اجتماع: - SUKP - توسط Kellerer و همکارانش Gen, M., and, 1997 - . - Cheng, R.W هدف پیدا کردن زیرمجموعه ای از عضوها است که وزن کلی آن از حجم کولهپشتی بیشتر نشود و ارزش بیشینه را داشته باشد.
·مسئله کوله پشتی با چگالی بیشینه : w0 وزن اولیه است و ما تراکم اشیای انتخابی را تا زمانی که با محدودیتهای ظرفیت مغایرت نداشته باشد، زیاد می کنیم . - Gen , M., and Cheng, R.W , 1997 - یکی از مسائل مهم در زمینه مسائل تصمیم گیری و مهم تر از آن بهینه سازی، مسأله کوله پشتی استمخصوصاً. در مواردی که مسأله زمان و سرمایه گذاری در یک زمینه جزو فاکتورهای بحرانی است و از درجه اهمیت بالایی برخوردار می باشد، حل دقیق و بهینه مسأله کوله پشتی، راه گشا خواهد بود. از طرف دیگر در تخصیص منابع با محدودیت مالی، و مواردی از قبیل ترکیبات، نظریه پیچیدگی محاسباتی، رمز نگاری و ریاضیات کاربردی نیز با این مسأله روبرو هستیم. الگوریتم های مختلفی برای حل مسأله کوله پشتی ارائه شده است، اما مرتبه زمانی بیشتر آنها، نمایی است - قربان پور و اکبری نسب، . - 1392
مسئله کوله پشتی یکی از مسائل مهم بهینه سازی بوده و کاربرد زیادی در مسائل واقعی پیدا کرده است. کاربرد زیاد این مسئله و نیز ظاهر شدن آن در قسمتی از مسائل بهینه سازی پیچیده، باعث شده است که در طی سه دهه ی اخیر مسئله کوله پشتی مورد توجه فراوان قرار گرفته و انواع زیادی از آن مورد بررسی قرار گیرد - نوجوان، . - 1387در این تحقیق کوله پشتی دارای ظرفیت خاص و ثابتی از لحاظ حجم و وزن است که در شرایط مسئله تأثیرگذار می باشد. جمع آوری محتویاتی که بیشتر از لحاظ کیفیت برتر می باشند اولویت دارند که در مسئله طرح شده وزن خوانده می شود جای گشت حجم های انتخاب شده بر اساس کیفیت - وزن - می باشد.
