ترجمه حل مساله کوله پشتی0 و 1 (01 KP) با یکپارچه سازی الگوریتم ژنتیک همگن

توضیحات

 عنوان فارسی: حل مساله کوله پشتی0 و 1 (01 KP) با یکپارچه سازی الگوریتم ژنتیک همگن

عنوان انگلیسی مقاله ترجمه شده:

Taming the 0/1 knapsack problem with monogamous pairs genetic algorithm

چکیده

     این مقاله یک زیرگروه تا حدودی متفاوت از الگوریتم ژنتیک (GA) را تعریف می کند که یک الگوریتم ژنتیک همگن (MopGA) برای حل مساله کوله پشتی 0 و 1 است. MopGA شامل دو عملیات مهم است که از یکپارچه سازی اجتماعی اقتباس شده است: پیوند جفتی و خیانت در احتمال کم. بر خلاف GA های متداول، جفت های والدین (پدر و مادر همجنس) در هر نسل باقی می مانند تا زمانی که سهام آنها منقضی شود. با این وجود، این حکم یکپارچه ممکن است در صورت وجود خیانت، نقض شود. تکنیک ما بر بهره برداری کامل از منطقه جستجوی فعلی از طریق پیوند جفتی است، در حالیکه از طریق خیانت امکان اکتشاف کافی به مناطق ناشناخته دیگر را نیز فراهم می‌کند. بنابراین الگوریتم MopGA می تواند از گستردگی بیشتر جمعیت تحت بررسی پشتیبانی کند که این کار را با محافظت از فرزندانی که از یک والد تک جفتی ایجاد شده است، از فشار انتخاب جمعیت گسترده و استراتژی جفت گیری محدود انجام می دهد. به عنوان یک مزیت جانبی از استفاده اقتصادی از مکانیزم انتخاب، MopGA به صورت محاسباتی کارآمدتر است، به ویژه هنگامی که با مساله کوله پشتی 0 و 1 با مقیاس بزرگ تری به کار گرفته شود. نتایج تجربی کوله پشتی 0 و 1 همچنین عملکرد قابل توجهی را به نفع روش پیشنهادی از نظر کیفیت راه حل نشان می دهد.    

• مقدمه

     مساله کوله پشتی0 و 1 (0/1 KP) یکی از پیچیده ترین مشکلات ترکیبیNP – hard در چند دهه گذشته است. این مساله دارای کاربردهای گسترده ای است که برخی از آن ها شامل کنترل بودجه، ارتباطات تلفنی، تخصیص منابع، طراحی VLSI و انتخاب پروژه ها است.

     مساله کوله پشتی کلاسیک 0 و 1 را می توان بدین صورت تعریف کرد: مجموعه ای از M مورد با pj و wj در نظر گرفته می شود که نشان دهنده سود و وزن هر مورد j است؛ هدف نهایی این است که بزرگ ترین مجموعه از این M مورد انتخاب شود تا سود بیشینه شود و از ظرفیت C کوله پشتی فراتر نرود. مساله را می توان به صورت زیر بیان کرد:

در این رابطه  xj یک متغیر تصمیم گیری دودویی است که اگر مورد j در کوله پشتی گنجانده شود، xi = 1 خواهد بود. در غیر این صورت 0 است. بدون از دست دادن کلیت موضوع  مس توان فرض کرد که تمام وزن ها و سود مثبت باشند، همه وزن ها کوچکتر از C هستند و وزن کلی اقلام بیش از C است.

     در بررسی های اولیه کوله پشتی، الگوریتم های دقیق اغلب اتخاذ می شدند. به عنوان مثال، منسی، آلوس، والریو دی کاروالو، و هانفی (2012) یک الگوریتم دقیق برای حل مساله کوله پشتی دو سطحی 0 و1 پیشنهاد کردند. آنها از روش آرام سازی خطی برای محاسبه راه حل های قابل قبول استفاده کردند. علاوه بر این، آنها همچنین یک فرایند برنامه ریزی پویا را توصیف می کنند که راه حل بهینه ی عددی را پیدا می کند. روش پیشنهادی از سایر روشهای موجود پیشرفته تر و موفق تر بوده است. در عین حال، با استفاده از برنامه نویسی پویا و پارتیشن بندی می توان مساله کوله پشتی اصلی را به چند مشکل ساده تر بر اساس مفهوم اصلی KP اصلی تقسیم کرد که همچنین منجر به نتایج امیدوار کننده ای خواهد شد.

     اخیراً، الگوریتم های اکتشافی در میان محققان KP محبوبیت زیادی به دست آورده اند. مزیت اصلی رویکردهای اکتشافی این است که راه حل های تقریبی معمولاً در قالب زمان معقولی یافت می شود. الگوریتم ژنتیک (GA) یکی از کاندیداهای رایج در این زمینه بوده است. به عنوان مثال، Khuri و همکارانش در سال 1994 یک الگوریتم ژنتیک برای حل مساله کوله پشتی 0 و 1 با مشکلات نسبتاً بزرگ آزمون پیشنهاد کردند. Shen، Xu و Huang (2011) یک جمعیت دوگانه GA را با معرفی رویکرد حریصانه و رقابت زیرگروه برای مقابله با 0/1 KP بهبود بخشیدند. با این وجود، آزمایشات به اندازه کافی گسترده نیستند تا اثربخشی روش پیشنهادی را نتیجه بگیرند. در همین حال، KP 0/1  با استفاده از یک کوانتوم GA با عملیات جهش، توابع سینوسی و کوزینو برای رمزگذاری کروموزوم ها و تنظیم سازگار زاویه چرخش نیز حل شده است. روش پیشنهادی با توجه به توانایی آن در حفظ تنوع بیشتر جمعیت ، راه حل با کیفیت بهتر را تولید می کند.

     الگوریتم های تکاملی دیگر که برای حل KP ها اتخاذ می شوند شامل، بهینه سازی کلون مورچه (He & Huang، 2011)، الگوریتم جستجوی کوسه (Feng، Jia، & He، 2014)، الگوریتم ارگانیسم امی شکل Zhang et al. 2013)) ، الگوریتم ماهیگیری ماهی مصنوعی (AFSA) ((Azad et al و الگوریتم جست و جوی هماهنگی می شود.

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

     بر خلاف GAs های سنتی، والدین در MopGA یک همکاری پایدار را در طول یک نسل از پیش تعیین شده تشکیل می دهند. والدین Bonded و یا همجنس همچنان در نسل بعدی خواهند ماند تا زمانی که پیوند منقضی می شود. سپس انتخاب والدین جدید برای چرخه بعدی پیوند جفتی انجام می شود. در نتیجه، مکانیزم های انتخابی به اندازه کافی مورد استفاده قرار می گیرند. فرزندان تنها با خواهر و برادر خود برای انتقال به نسل بعدی رقابت می کنند. گاهی اوقات، خیانت به اجبار موارد ژنتیکی کل جمعیت را تغییر می دهد. به طور گسترده، دو عامل، یعنی پیوند جفت و خیانت، به ترتیب عمق بهره برداری و اکتشاف فضای جستجو را کنترل می کنند. بهبود عملکرد بدین ترتیب حاصل می شود:

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

     علاوه بر این، به عنوان یک مزیت جانبی از استفاده اقتصادی از مکانیزم انتخاب، MopGA به صورت محاسباتی کارآمدتر است، به ویژه هنگامی هنگامی که مقیاس مساله بزرگ تر می شود.

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

توجه:

• برای دانلود فایل word کامل ترجمه از گزینه افزودن به سبد خرید بالا استفاده فرمایید.
• لینک دانلود فایل بلافاصله پس از خرید بصورت اتوماتیک برای شما ایمیل می گردد.