صداقت، اعتبار ماست

اين مقاله صرفا تبديل به Word و مرتب شده تا دانشجويان بتوانند به عنوان منابع از آن به راحتي استفاده كنند و PDF آن در سايت ها موجود مي باشد: كليك كنيد , كليك كنيد

فهرست

مقدمه

پیشینه تحقیق

روش‌شناسی

الگوریتم پرواز پرندگان

الگوریتم پرواز پرندگان گسسته

الگوریتم ابتکاری CUL

تجزیه و تحلیل داده‌ها

محدودیت­ها

بحث و نتیجه­گیری

منابع

چکیده

در این مقاله، مسأله برش دو بعدی با تقاضا مورد بررسی قرار می­گیرد. در این مسأله با برش ورق­های مستطیل شکل بزرگ، مستطیل­های کوچک­تر مورد نیاز باید به نحوی تولید شوند که ضمن تأمین تقاضا برای آنها، ضایعات یا تعداد ورق­های مصرفی حداقل شود. مسأله برش، جزء مسائلNP-Hard  است که روش­های دقیق قادر، به حل عملی آنها نیستند. لذا در این مقاله با استفاده از الگوریتم پرواز پرندگان، الگوریتمی فراابتکاری برای حل مسأله برش دو بعدی با تقاضا ارائه شده است. برای بهبود کارایی این الگوریتم و جلوگیری از هم­پوشانی در مسأله برش، الگوریتم ابتکاری CUL به­کار گرفته شد. همچنین برای بررسی نتایج الگوریتم پیشنهادی (ترکیب الگوریتم‌های PSO و CUL) نرم‌افزاری تهیه شد که با در نظر گرفتن طول و عرض صفحه‌ اصلی و با توجه به اندازه‌های قطعات و تعداد مورد تقاضا، بهترین الگوی برش ممکن را ارائه می‌دهد.

کلید واژه‌ها: الگوریتم پرواز پرندگان، الگوریتم پرواز پرندگان گسسته، الگوریتم CUL، مسأله برش دو بعدی.

مقدمه

     در فرایند تولید در بسیاری از صنایع، این نیاز وجود دارد که قطعات کوچک­تری از راه برش اجسام بزرگ­تر حاصل شوند و یا قطعات کوچک­تر در یک جسم بزرگ­تر جای داده شوند. در این فرایند معمولاً بخش­هایی از جسم بزرگ­تر به قطعاتی تبدیل می­شوند که قابل استفاده در هیچ یک از محصولات تولیدی نیستند و ضایعات و دورریز محسوب می­شوند. کاهش چنین ضایعاتی، نقش مهمی در کاهش هزینه­ها دارد و به عنوان یکی از موضوعات علم تحقیق در عملیات ـ با نام مسأله­ی برش ـ توجه بسیاری از محققان را در نیم قرن گذشته جلب کرده است[1].

الگوریتم پرواز پرندگان

     این الگوریتم را جیمز کندی (روانشناس اجتماعی) و راسل­ابرهارت (مهندس برق) [33] در 1995 برای حل مسائل بهینه­سازی ـ که ماهیت پیوسته بر جواب­های آن­ها حاکم است ـ مطرح کردند. بسیاری از نویسندگان، کار آنها را توسعه داده‌اند [45، 42]. خلاصه­ای از توسعه، بهبود و کاربردهای این الگوریتم در [52] آمده است.

مزایای این الگوریتم عبارتست از:

1. ریشه در زندگی مصنوعی و هوش محاسباتی دارد.
2. مفاهیمی ساده دارد.
3. پارامترهای اندکی دارد.
4. در مقایسه با الگوریتم ژنتیک، عملگرهای تقاطع و جهش ندارد.
5. برای حل مسائل گوناگون، مؤثر و قابل اجراست.
6. اجرای آن ساده است.

معایب این الگوریتم، اندک است:

1. کاربرد اصلی آن برای حل مسائل نامحدود است، اما با استفاده از روش جریمه می­توان آن را برای مسائل محدود نیز به­کار برد.
2. توانایی کمی در جستجوی محلی دارد [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 می­باشد.