فایل ترکیب الگوریتم پرواز پرندگان و الگوریتم ابتکاری CUL برای حل مسأله برش دو بعدی غیرگیوتینی
دسته بندي :
کالاهای دیجیتال »
رشته کامپیوتر و IT (آموزش_و_پژوهش)
صداقت، اعتبار ماست
اين مقاله صرفا تبديل به Word و مرتب شده تا دانشجويان بتوانند به عنوان منابع از آن به راحتي استفاده كنند و PDF آن در سايت ها موجود مي باشد: كليك كنيد , كليك كنيد
فهرست
مقدمه
پیشینه تحقیق
روش‌شناسی
الگوریتم پرواز پرندگان
الگوریتم پرواز پرندگان گسسته
الگوریتم ابتکاری CUL
تجزیه و تحلیل داده‌ها
محدودیتها
بحث و نتیجهگیری
منابع
چکیده
در این مقاله، مسأله برش دو بعدی با تقاضا مورد بررسی قرار میگیرد. در این مسأله با برش ورقهای مستطیل شکل بزرگ، مستطیلهای کوچکتر مورد نیاز باید به نحوی تولید شوند که ضمن تأمین تقاضا برای آنها، ضایعات یا تعداد ورقهای مصرفی حداقل شود. مسأله برش، جزء مسائلNP-Hard است که روشهای دقیق قادر، به حل عملی آنها نیستند. لذا در این مقاله با استفاده از الگوریتم پرواز پرندگان، الگوریتمی فراابتکاری برای حل مسأله برش دو بعدی با تقاضا ارائه شده است. برای بهبود کارایی این الگوریتم و جلوگیری از همپوشانی در مسأله برش، الگوریتم ابتکاری CUL بهکار گرفته شد. همچنین برای بررسی نتایج الگوریتم پیشنهادی (ترکیب الگوریتم‌های PSO و CUL) نرم‌افزاری تهیه شد که با در نظر گرفتن طول و عرض صفحه اصلی و با توجه به اندازه‌های قطعات و تعداد مورد تقاضا، بهترین الگوی برش ممکن را ارائه می‌دهد.
کلید واژه‌ها: الگوریتم پرواز پرندگان، الگوریتم پرواز پرندگان گسسته، الگوریتم CUL، مسأله برش دو بعدی.
مقدمه
در فرایند تولید در بسیاری از صنایع، این نیاز وجود دارد که قطعات کوچکتری از راه برش اجسام بزرگتر حاصل شوند و یا قطعات کوچکتر در یک جسم بزرگتر جای داده شوند. در این فرایند معمولاً بخشهایی از جسم بزرگتر به قطعاتی تبدیل میشوند که قابل استفاده در هیچ یک از محصولات تولیدی نیستند و ضایعات و دورریز محسوب میشوند. کاهش چنین ضایعاتی، نقش مهمی در کاهش هزینهها دارد و به عنوان یکی از موضوعات علم تحقیق در عملیات ـ با نام مسألهی برش ـ توجه بسیاری از محققان را در نیم قرن گذشته جلب کرده است[1].
الگوریتم پرواز پرندگان
این الگوریتم را جیمز کندی (روانشناس اجتماعی) و راسلابرهارت (مهندس برق) [33] در 1995 برای حل مسائل بهینهسازی ـ که ماهیت پیوسته بر جوابهای آنها حاکم است ـ مطرح کردند. بسیاری از نویسندگان، کار آنها را توسعه داده‌اند [45، 42]. خلاصهای از توسعه، بهبود و کاربردهای این الگوریتم در [52] آمده است.
مزایای این الگوریتم عبارتست از:
- ریشه در زندگی مصنوعی و هوش محاسباتی دارد.
- مفاهیمی ساده دارد.
- پارامترهای اندکی دارد.
- در مقایسه با الگوریتم ژنتیک، عملگرهای تقاطع و جهش ندارد.
- برای حل مسائل گوناگون، مؤثر و قابل اجراست.
- اجرای آن ساده است.
معایب این الگوریتم، اندک است:
- کاربرد اصلی آن برای حل مسائل نامحدود است، اما با استفاده از روش جریمه میتوان آن را برای مسائل محدود نیز بهکار برد.
- توانایی کمی در جستجوی محلی دارد [43].
الگوریتم پرواز پرندگان گسسته
کندی و ابرهارت [33] اولین نسخه از الگوریتم پرواز پرندگان گسسته دوارزشی را توسعه دادند. جزئیات بیشتر در مورد ادبیات آن در [55، 56] آمده است.
از آنجا مسأله برش، ماهیتی گسسته دارد و الگوریتم پرواز پرندگان استاندارد قادر به حل چنین مسائلی نمیباشد، در این مقاله از الگوریتم پرواز پرندگان گسسته ـ که برای بهینهسازی در چنین فضاهایی مناسب میباشد ـ استفاده شده است. این الگوریتم به شرح زیر میباشد [46]:
هر پرنده، یک جواب ممکن و نشانگر نقطهای در فضای جستجوی چندبعدی است. در ابتدا الگوریتم با مجموعه جوابهای تصادفی شروع میشود و به هر پرنده، به صورت تصادفی، سرعتی نسبت داده میشود.
الگوریتم ابتکاری CUL
در این مقاله، برای هر قطعه i، تعداد مشخصی تقاضا وجود دارد. برای مثال، 4 واحد تقاضا برای قطعاتی با ابعاد 52 وجود دارد که باید در ورق اصلی قرار گیرند و فرایند به همین ترتیب برای سایر قطعات ادامه می‌یابد.
تجزیه و تحلیل داده‌ها
در این مقاله برای حل مسأله برش دوبعدی غیرگیوتینی، پارامترهای پیشنهادی الگوریتم پرواز پرندگان به صورت زیر تعریف میشوند:
1- جمعیت اولیه: S با جمعیتی تصادفی شروع میشود. اندازه S، بسته به مسأله، متفاوت است و هیچ معیار مشخصی برای تعیین اندازه آن وجود ندارد. S در نرم‌افزار مورد استفاده در این مقاله به گونه‌ای در نظر گرفته شده است که قابل تنظیم است. طول هر پرنده در S برابر با تعداد قطعاتی است که باید بستهبندی شوند. هر پرنده، یک ترکیب است که شامل اعداد صحیح و توالی قرارگیری قطعات در ورق اصلی میباشد. S=[Sij] نشانگر جمعیت اولیه میباشد: تعداد پرندگان (i=1,2,…,) و تعداد قطعات (j=1,2,…,).
2- موقعیت: موقعیت X شامل طول و عرض قطعات مطابق با توالی قرارگیری آنهاست. این موقعیت، شامل چند ماتریس فرعی (ابعاد ماتریسهای فرعی، دو برابر تعداد قطعات است) ـ که دربرگیرنده موقعیت هر پرنده هستند ـ است. لذا تعداد سطرهای ماتریس X، دو برابر تعداد سطرهای S میباشد.