بخشی از مقاله
چکیده
مسئله بسته بندی اقلام در ظروف یکی از مسائل گروه بندی است که در صنایع مختلف کاربرد دارد و تاکنون الگوریتمهای بسیاری که در بیشتر موارد مبتنی بر الگوریتم ژنتیک بوده اند ، برای حل آن پیشنهاد شده است. معرفی استراتژی تکاملی گروه بندی - - GES1 در سال 2009 توسط حسین زاده کاشان،حرکتی در راستای ارائه الگوریتمی متفاوت از الگوریتم ژنتیک گروه بندی - - GGA2 بود که در مقایسه با GGA عملکرد مناسبی نیز نشان داد.
همچنین الگوریتمهای کاهشی نیز برای کاهش فضای جستجو در روشهایی که برای یافتن بهترین جواب به جستجو در یک فضای حل می پردازند، ارائه شده است و الگوریتم MTRP3 مارتلو و تات که در 1991 معرفی شد ، یکی از کاربردی ترین روشهای کاهشی است. در این مقاله ما الگوریتم - 1+ - -GES که توسط حسین زاده به کار برده شد ، با الگوریتم کاهشی مارتلو و تات ترکیب کردیم و عملکرد آن را روی 10 نمونه مسئله سخت، با GES و GGA مقایسه نمودیم. همچنین روش ترکیبی پیشنهادی را روی 720 نمونه مسئله موجود در ادبیات پیاده کردیم که در همه مسائل جواب بهینه به دست آمد.
-1 مقدمه
-1-1 معرفی
مسئله بسته بندی اقلام در ظروف - BPP - از نظر تئوری و عملی دارای اهمیت می باشد چرا که این مسئله کاربرد فراوانی در صنایع مختلف دارد و دستیابی به یک جواب بهینه برای این مسئله کاهش هزینه های بسیاری را در پی خواهد داشت. مسئله بسته بندی اقلام در ظروف شامل تخصیص اشیا به ظروف است طوری که مجموع وزن اشیا در یک ظرف از ظرفیت ظرف تجاوز نکند و در عین حال تعداد ظرفهای استفاده شده حداقل گردد. مسئله BPP یک مسئله Np-Hard است - Garey & . - Johnson, 1979 این موضوع دلالت بر این دارد که هر الگوریتم دقیق شناخته شده ای در زمان نمایی متناسب با اندازه مسئله اجرا خواهد شد. بنابراین چنین الگوریتمی در بیشتر موارد برای مسائل با اندازه واقعی کاربردی نیست.
نتایج نسبتا دلگرم کننده الگوریتمهای تکاملی روی مسائل Np-hard ، این الگوریتم را به کاندیدی برای حل مسائل گروه بندی تبدیل کرده است. کاربرد الگوی کدینگ مستقیم همراه با اپراتورهای ژنتیک استاندارد توسط - - Holland, 1975 اولین حرکت در مسیر نوشته های GA مربوط به مسائل گروه بندی مثل - Jones & Beltramo , 1991 - و - Ding, El-Keib, & Smith, 1992 - بوده است . - Garey & Johnson, 1979 - روشهای ابتکاری ساده ای برای مسئله بسته بندی اقلام در ظروف بیان کردند که می توان نشان داد جوابهای چندان بدتری نسبت به تعداد ظروف بهینه تولید نمی کنند.در این روشها با شروع از یک ظرف خالی، اشیا را یک به یک برداشته و برای هر یک ابتدا ظرفهایی را که دارای فضای کافی جهت دربر گرفتن آن شئ را داشته باشند جستجو می کند.
اگر چنین ظرفی پیدا شد شئ را در آن قرار می دهد و در غیر این صورت به دنبال ظرف جدیدی می گردد . قرار دادن شئ در اولین ظرف ممکن روش ابتکاری اولین انطباق4 را بوجود می آورد و جستجو برای ظرف با بیشترین ظرفیت خالی الگوریتم بهترین انطابق5 که الگوریتم بهتری است را ایجاد می کند. - Khuri, Schütz, & Heitkötter, 1995 - یک الگوریتم EA برای حل مسئله بسته بندی اقلام در ظروف بکار بردند و آن را با روش اولین انطباق نزولی6 مقایسه کردند. آنها از دانش ویژه مسئله یا اپراتورهای مخصوص مسئله استفاده نکردند ، تنها از یک تابع تناسب با جریمه درجه بندی شده استفاده کردند. نتایج ناامید کننده بود : حتی الگوریتم ساده FFD بهتر از EA بود.
- Falkenauer, 1996 - ، - - Falkenauer, 1994b ، - - Falkenauer, 1994a مفاهیم الگوریتم ژنتیک را برای مسائل گروه بندی پیاده کردند و الگوریتم ژنتیک گروه بندی هیبرید - HGGA - 7 را ارائه دادند . آنها یک طرح نمایش مخصوص به شکل شئ:گروه را مورد استفاده قرار دادند. از دیگر مطالعات انجام گرفته در زمینه مسائل بسته بندی اقلام و الگوریتمهای تکاملی میتوان به مقاله - Reeves, 1996 - اشاره کرد که در آن یک استراتژی تکاملی - EA - 8 برای مسئله بسته بندی اقلام در ظروف ارائه کرد.
در این تحقیق افراد جمعیت با استفاده از روشهای ابتکاری اولین انطباق ، بهترین انطباق و انطباق بعدی9 کد شده اند که موفق ترین روش، روش بهترین انطباق بوده است. Reeves در مقاله اش از یک تکنیک برای کاهش سایز مسئله استفاده می کند: ظرفهایی که به خوبی پر شده اند از مسئله حذف می شوند ، تا به مسئله کوچکتری برسیم. با اینکه ریسک گیر کردن در یک جواب بهینه محلی وجود دارد، در کل عملکرد به میزان قابل توجهی افزایش می یابد و EA پیشنهادی برتر از روشهای ابتکاری مانند اولین انطباق عمل می کند.
- Schwerin & Wäscher, 1999 - یک حد پایین جدید برای مسئله BPP پیشنهاد دادند که بر مسئله برش موجودی استوار است و آن را با الگوریتم MTP 10 مارتلو و توت - S. Martello & P. Toth, 1990 - یکپارچه کردند ، تا از الگوریتم جدید خود - MTPCS - نتایج با کیفیت بالایی به دست آورند . - Sami Khuri, 2000 - الگوریتم ابتکاری حداقل اتلاف ظروف - MBS - را معرفی کردند . - Krzysztof Fleszar & Hindi, 2002 - الگوریتم جدید MBS را معرفی کردند که قبل از شمارش ، بزرگترین اشیاء باقیمانده را در یک ظرف ثابت نگه می داشت - Levine & Ducatelle, 2004 - . یک روش هیبریدی که الگوریتم بهینه سازی مورچگان را به کار می برد، ارائه کرد.
این روش شامل یک استراتژی برای جستجوی محلی بود که بر معیار تسلط مارتلو و توت - Silvano Martello & Paolo Toth, 1990 - استوار بود . الگوریتم ابتکاری هیبریدی HI_BP ارائه کردند که در آن استراتژی دوگان استفاده شده توسط - Scholl, Klein, & - Jürgens, 1997 مجددا معرفی شد و به علاوه تکنیکهای کاهش فضای جستجوی مارتلو و توت - Silvano Martello & Paolo - Toth , 1990 و استراتژی های حد پایین مورد استفاده قرار گرفت.
