بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
حل مساله بسته بندی در ظرف دو بعدی با استفاده از ترکیب روش بهینه سازی مدل ازدحام ذرات و الگوریتم های فرا ابتکاری
خلاصه
مسئله بستهبندی ظروف یا Bin Packing کاربردهای بسیاری در علوم مهندسی، صنعت و اقتصاد دارد. در مسئله اشیاء با ظرفیتهای مختلف باید به یک تعداد متناهی از ظروف یا صندوقها، هر یک با حجم ثابت بستهبندی شود، بطوریکه تعداد ظروف مورد استفاده حداقل شود. تاکنون تلاشهای بسیاری برای حل مساله بستهبندی ظروف صورت پذیرفته و الگورتیمهای بسیاری برای دستیابی به جوابهای بهینه و نزدیک به آن توسعه داده شده است. در این مقاله تمرکز روی بررسی کارهای نسبتا اخیر فراابتکاری برای حل مساله بستهبندی ظروف دو بعدی و ارائه یک راهکار ترکیبی با استفاده از رویکرد فراابتکاری الگوریتمهای تکاملی برای حل این مسئله دارد. در الگوریتم تکاملی پیشنهادی از الگوریتمهای ازدحام جمعیت و ژنتیک با نرخ های تخریب متفاوت استفاده شده است، و در نهایت با شبیه سازیهای انجام شده این دو الگوریتم با هم مقایسه میشوند. نتایج حاصل در الگوریتم ازدحام جمعیت نشان از بهینگی در مقایسه با الگوریتم ژنتیک دارد.
کلمات کلیدی: ح بسته بندی ظروف دوبعدی، الگوریتم ازدحام جمعیت، الگوریتم ژنتیک، نرخ تخریب.
1. مقدمه
در دنیای علوم کامپیوتر مسائلی وجود دارند که دارای کاربردهای بسیاری در صنعت و اقتصاد است. یکی از این مسائل، مسئله بستهبندی ظروف1 است که کاربردهای همچون توزیع منابع، برنامه ریزی تولید، زمان بندی، برنامه ریزی پروژه و تدارکات، برنامه ریزی، پارتیشن بندی، طراحی مدار چاپی، تعادل بار، مسیریابی، برش شیشه، چوب یا فلز و بسته بندی در زمینه حمل و نقل و یا انبارداری و غیره دارد .[9, 10] از آنجا که شرکتهای تولیدی، زمان و هزینه زیادی را برای طراحی و یا طراحی مجدد تجهیزات خود میپردازند، مسئله چیدمان تجهیزات در محلهای مختلف به منظور کاهش هزینههای ناشی از جابجایی حجم بالای تجهیزات همواره مورد توجه پژوهشگران و محققان عرصه طرح ریزی و طراحی واحدهای صنعتی بوده است.
در مسئله بستهبندی ظروف، اشیاء با ظرفیتهای مختلف باید به یک تعداد متناهی از ظروف یا صندوقها، هر یک با حجم ثابت V بسته بندی شوند بطوریکه تعداد ظروف مورد استفاده، حداقل شود .[3] به عبارتی دیگر در مسئله تصمیم گیری بستهبندی ظروف این مسئله پیش میآید که آیا با توجه به مجموعه ای از اشیاء با اندازه های متمایز، و مجموعه ای از ظروف با ظرفیت خاص، توزیعی از اقلام به ظروف وجود دارد، به گونه ای که هیچ قلمی با
توجه به محدودیت اندازه ظروف بدون ظرف (بستهبندی نشده) باقی میماند یا خیر؟ و بهینه سازی انجام شده برای حداقل سازی تعداد از ظروف برای بسته همه اشیاء است.[3]
در بسیاری از کاربردهای صنعتی نیاز است یا یک مجموعه از اشیاء مستطیلی را در واحدهای موجودی انبار استاندارد شده مستطیلی اختصاص داده شود، به گونه ای که مقدار ضایعات به حداقل برسد. به عنوان مثال در صنایع چوب یا شیشه، اجزاء مستطیلی باید از ورقه های بزرگ مواد برش داده شوند. در زمینه انبارداری، کالاها باید در قفسه ها قرار داده شوند. در صفحه بندی روزنامهها، مقالات و تبلیغات باید در صفحات مرتب شوند. در این برنامههای کاربردی، واحدهای انبار مستطیلی هستند و یک تابع هدف مشترک نیز وجود دارد تا تمام اشیاء درخواست شده را در حداقل تعداد واحد ها بستهبندی کند: مسائل بهینه سازی نتایج در ادبیات به عنوان مسائل بستهبندی دو بعدی ظروف شناخته میشوند. در سایر زمینه ها از قبیل صنایع کاغذ و پارچه، یک واحد استاندارد شده یکتا (یک رول از مواد) موجود است و هدف بدست آوردن اشیاء با استفاده از حداقل طول رول میباشد. این مسائل به عنوان مسائل بستهبندی دو بعدی نوار شناخته میشوند. این دو مسئله تقریبا در همه روشهای الگوریتمیارتباط بسیار محکمیدارند .[15] انواع مختلف بستهبندی دو بعدی، بستهبندی خطی، بستهبندی با وزن، بسته بندی با هزینه و غیره از مسئلهبستهبندی ظروف میباشند. در مسائل بستهبندی دو بعدی واحدها مستطیلهای محدودی هستند و هدف بستهبندی تمام اقلام میباشند در حالی که در مسائل بسته بندی نوار دو بعدی یک واحد استاندارد شده با عرض مشخص در حداقل واحدها میباشد، همچنین هدف بستهبندی تمام اشیاء در حداقل ارتفاع میباشد.[15]
در این مقاله، ما مسائلی را در نظر میگیریم که نیاز دارند تا یک مجموعه از اشیاء مستطیلی را با به حداقل رسانیدن ضایعات، در واحدهای مستطیلی شکل بزرگتر جا سازی کنیم. در روش پیشنهادی از الگوریتم تکاملی استفاده شده که در آن از الگوریتم های جزیره و اپراتور جهش با نرخ های تخریب متفاوت بکار رفته است. نتایج روش پیشنهادی با بهترین روشهای موجود مقایسه شده است. این الگوریتم علاوه بر جواب خوبی که بدست می آورد می تواند پیچیدگی محاسباتی مساله را 6 برابر نسبت به الگوریتم های تکاملی کلاسیک کمتر نماید.
2. طراحی الگوریتم جمعیت ذرات برای مسئله بسته بندی دو بعدی:
این الگوریتم بر اساس رفتار گروهی پرندگان الگو گرفته است. این پرندگان تمایلی به سردسته خودشان دارند. یعنی این سردسته انحرافی داشته باشد بقیه متناسب با سردسته انحراف خواهند داشت. این سردسته در واقع بهترین پرنده موجود است. همانند سایر الگوریتمهای جمعیتی، این الگوریتم از مجموعهای از پاسخهای ممکن استفاده میکند که این پاسخها تا زمانی که یک پاسخ بهینه یابد و یا شرایط پایان الگوریتم مهیا شود به حرکت خود ادامه میدهند.
در این روش هر پاسخ x بصورت یک ذره نمایش داده میشود و یک گروه ذرات در حقیقت یک مجموعهای از ذرات میباشند. در این روش معادله سرعت ضامن حرکت ذرات بسمت ناحیه بهینه میباشد. این معادله معمولا براساس سه عنصر اصلی: (1 سرعت سکون (2 مولفه شناختی Pbest (بهترین وضعیت ذره یا جواب) (3 مولفه جمعی gbest (بهترین جواب یا ذرهای که تا حالا داشته است) ارائه میشود. رهیافت نهایی میتواند بعنوان الگوریتمی شناخته شود که جستجویی را به صورت چند بعدی اعمال میکند. در شبه سازی این الگوریتم، رفتار هر ذره میتواند تحت تاثیر بهترین ذره محلی Pbest (در داخل یک همسایگی مشخص) و یا بهترین ذره عمومی gbest باشد. در شکل زیر وضعیت جدید هر ذره را نشان میدهد.
شکل(:(1 وضعیت جدید هر ذره
وضعیت جدید هر ذره همان وضعیت فعلی به اضافه سرعت آینده حتما موقعیت آینده بدست میآید. همانطور که گفتیم بر اساس سه مولفه سرعت سکون، مولفه شناختی Pbest و مولفه جمعی gbest ارائه میشود. در واقع بر اساس رندمی از سرعت قبلی، رندمی از بهترین ذره از بین کل ذرهها و بر اساس بهترین وضعیتی که خود ذره داشته است سرعت جدید را آپدیت میکنیم.
بطور کلی اگر نشان دهنده موقعیت ذره Pi در فضای جستجو در لحظه t باشد، موقعیت Pi با افزودن سرعت به موقعیت فعلی بصورت زیر تغییر مینماید.
(1)
(2)
در معادله((2 بردار سرعت در گام 1-t م، C1 و C2 مقادیر ثابت مثبت و r1 و r2 اعداد تصادفی هستند که بصورت نرمال در بازه [0,1]
تولید میشوند، پارامترهای و به ترتیب نشان دهنده موقعیت بهترین تجربه شخصی و جمعی میباشد. به منظور ایجاد قابلیت بهتر جستجو، پارامتری بنام وزن اینرسی به شکل زیر و بصورت ضریبی در پارامتر سرعت به الگوریتم اضافه میگردد:
(3)
وزن اینرسی تاثیر سرعت ذرات در گام قبل را بر سرعت فعلی تعیین میکند. به این ترتیب که با مقادیر بزرگی از وزن اینرسی قابلیت جستجوی عمومی الگوریتم بهبود یافته و فضای بیشتری مورد بررسی قرار میگیرد، حال آنکه با مقادیر کوچک وزن اینرسی شروع به حرکت میکند که سبب جستجوی گسترده فضا در ابتدای اجرا شده و این وزن به مرور در طول زمان کاهش مییابد که سبب تمرکز جستجو در فضای کوچک در گامهای پایانی می-باشد.
تمامی این نوع الگوریتمها از دونوع مکانیزم تنوع و تمرکز استفاده میکنند. مکانیزم تنوع یعنی از فضای بیشتری برای جستجو استفاده کنیم و در پایان این تنوع را کم کنیم و تمرکز کنیم، در واقع به ناحیه بهینه تمرکز کنیم. در واقع در معادله (3)، W همان میزان تنوع ما است که مقدار آن را زیاد می-گذاریم که هر چه به پایان الگوریتم رسیدیم مقدار آن کم و کمتر میشود.
در ابتدا ذرات بصورت تصادفی در سرتاسر فضای جستجو مقدار دهی میشوند که این موقعیتهای اولیه بعنوان بهترین تجربه شخصی ذرات نیز شناخته میشوند .(Pbest) در گام بعد بهترین ذره از میان ذرات موجود انتخاب شده و بنام بهترین پاسخ شناخته میشود(.(gbest سپس گروه ذرات در فضای جستجو حرکت میکنند تا زمانی که شرایط پایان محقق گردد. این حرکت شامل اعمال معادله سرعت به گروه ذرات میباشد که موقعیت هر ذره بر اساس آن تغییر میکند. مقدار برازش جدید حاصل از ذره با مقدار Pbest ذره مقایسه میگردد. در حالتی که موقعیت جدید دارای برازش بهتری باشد این موقعیت جدید جایگزین موقعیت Pbest میشود. روال مشابهی نیز gbest نیز انجام میپذیرد. این الگوریتم دارای پارامترهای زیر میباشد:
(1 معیار خاتمه: این معیار ضوابط اتخاذ شده برای به پایان رساندن اجرای الگوریتم را در بر دارد ولی معمولا به تعداد دفعات تکراری گفته میشود که الگوریتم اجرا خواهد شد.
(2 تعداد ذرات: ابن معیار به تعداد کل ذراتی که در فضای جستجو حرکت میکنند اشاره دارد.
از آنجایی که در این پایان نامه بستهبندی دو بعدی واحد ها مستطیلهای محدودی هستند و هدف بستهبندی تمام اقلام میباشد در حالی که در مسائل بستهبندی نوار دو بعدی یک واحد استاندارد شده با عرض مشخص در حداقل واحدها میباشد، همچنین هدف بستهبندی تمام اشیاء در حداقل ارتفاع میباشد. به همین علت در برنامه نویسی برای آپدیت معادله سرعت، رندم مقدار ثابتی که در فاصله شیء تا بهترین تجربه شخصی ضرب میشود را طوری مینویسیم که بصورت خطی بدست نیاید.
par(i).vel=w*par(i).vel+...
نکته قابل توجه این است که چون مقادیر تصادفی در برنامه نویسی در نظر گرفتیم شکل موج زیر بدست میآید.
جمعیت طراحی الگوریتم تکاملی برای مسئله بسته بندی دو بعدی:
یک الگوریتم تکاملی باید دارای موارد زیر باشد تا بتواند کار کند سایز جمعیت نحوه نمایش کروموزوم فرمول تابع هدف اپراتور تولید فرزند اپراتور جهش
مکانیزم انتخاب والد مکانیزم انتخاب کسانی که به نسل بعد می روند
سایز جمعیت برای پیاده سازی این مسئله 500 در نظر گرفته شد یعنی 5 جزیره ی 100 تایی. نحوه نمایش کروموزومها نیز به اینصورت است که یک کروموزوم به طول تعداد حالت هایی که جعبه های هم شکل در محیط مسئله می توانند قرار بگیرند و حالتی از جایگشت1 را خواهیم داشت. یعنی اعداد 1 تا طول کروموزوم (تعداد حالات جعبه ها) بدون تکرار در کنار هم قرار گیرند. Si مجموعه حالات ممکن برای قطعه i ام است و طبق فرمول (4) کروموزوم را تعریف می نماییم:
x یکی از مولفه های می باشد که در صورت انتخاب از سایر مجموعه ها حذف می شود و خواهیم داشت:
از آنجایی که هر کروموزوم راه حلی برای مسئله می باشد، می بایست یک سری محدودیت به آن ها اضافه نمود. برای مثال نمی توان کروموزومی داشت که همزمان دو جعبه را طوری قرار دهد که نقطه مشترک داشته باشند، این دو حتما می بایست کنار هم قرار گیرند نه روی هم. تولید اولیه یک کروموزوم هم می بایست از بیت اول صورت گیرد که یک عدد از 1 تا انواع حالات به صورت تصادفی انتخاب می شود. بر حسب قرار گرفتن جعبه اول چند حالت دیگر امکان رخ دادن ندارد و حالات اضافی را از لیست انتخاب برای بیت دوم حذف می شود. از لیست باقی مانده عدد (حالت) بعدی به صورت تصادفی انتخاب می شود. در صورتی که در میان کروموزوم دیگر حالتی برای انتخاب وجود نداشته باشد بیت های باقیمانده مقدار -1 خواهند داشت.
