ارائه یک الگوریتم فراابتکاری برای حل مسئله کوله پشتی دو بعدی با قطعات مستطیلی شکل : پايان‌نامه ارشد مهندسی صنایع گرايش سیستم های اقتصادی- اجتماعی

رشته صنایع یکی از مهمترین زیر شاخه های فنی و مهندسی شامل گرایش های متعددی در مقطع کارشناسی ارشد میباشد . در ادامه به معرفی نمونه پایان نامه ارشد مهندسی صنایع گرایش مهندسی سیستم های اقتصادی و اجتماعی با عنوان : ارائه یک الگوریتم فراابتکاری برای حل مسئله کوله پشتی دو بعدی با قطعات مستطیلی شکل که در 95 صفحه در فرمت قابل ویرایش Word به نگارش در آمده میپردازیم .

چکیده تحقیق ارائه یک الگوریتم فراابتکاری برای حل مسئله کوله پشتی دو بعدی با قطعات مستطیلی شکل :

مسئله کوله پشتی ، مسئله ای در بهینه سازی ترکیبیاتی است. ازمسئله کوله پشتی به نام هایی چون KnapsackیاRucksack نیز یاد می کنند. به بیان ساده مسئله کوله پشتی اینطور بیان می شود که فرض کنید مجموعه ای از اشیا، که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به طوری که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده، و ارزش آنها بیشینه شود.

در این مسئله ما یک مستطیل بزرگتر داریم که بایستی به تعبیری آنرا برش زده و به قطعات کوچکتر تقسیم کنیم. در واقع این به این معناست که ما در داخل این مستطیل بزرگ که مخزن هم میتوان آنرا نامید ، قطعات مستطیلی کوچکتری قرار دهیم.

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

به عنوان مثال ارائه یک توالی مناسب برای جمع آوری بسته های موجود .

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

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

از دستاوردهای این تحقیق می توان به این نکته اشاره کردکه بر طبق نتایج محاسباتی و تعداد زیادی از معیارهای سنجش کارایی با مقیاس کم و زیاد (مسائل بزرگ و کوچک) ، مدلی که ما ارائه کرده ایم نتایج بهتری از مدل های قبلی موجود نشان می دهد و راه حل هایی با تابع هدف بزرگتر تولید می نماید.

روش فراابتکاری بکارگرفته شده در این پایان نامه مبتنی بر الگوریتم ژنتیک می باشد. .سپس الگوریتمی حریصانه جهت یافتن یک راه حل بهتر و مناسب تر بکار گرفته شده است. و در نهایت هم با استفاده از یک الگوریتم فرا ابتکاری راه گذر کردن از یک نقطه بهینه محلی به نقطه بهینه اصلی فراهم می گردد.

کلمات کلیدی فارسی

مسئله کوله پشتی دو بعدی ، الگوریتم حریصانه ،  الگوریتم ژنتیک

بیان مسئله

مسئله برش وبسته بندی کاربردهای مستقیم فراوانی در چندین زمینه دارد.برای مثال در زمینه های حمل ونقل ولجستیکی اشیاء در اندازه های متفاوت در کانتینرهای بزرگتر از اندازه استاندارد بسته بندی می شوند وفضای موجود درهر کانتینر نیاز است تا حد ممکن به طور بیشینه استفاده شود.

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

این مسئله جایگاه مهمی در صنایع مختلف دارد. مثلا در صنعت فولاد و برش ورق های بزرگ فولادی، صنعت شیشه سازی، چوب بری، کاغذ و صنعت چاپ و توزیع روزنامه نمونه هایی از کاربرد این مسئله می باشند. از مسائل مرتبط با این مسئله می توان به مسئله مینیمم سازی مواد خام تلف شده بوسیله برش اشاره کرد که در واقع می توان به گونه ای این دو مسئله را به هم تبدیل نمود.

و …

فهرست مطالب تحقیق ارائه یک الگوریتم فراابتکاری برای حل مسئله کوله پشتی دو بعدی

فصل اول- مقدمه و کلیات تحقیق.. 1

1-1- مقدمه. 2

1-2- تعریف مسئله. 2

1-3-یک مثال از مسئله کوله پشتی… 3

1-5 – مسئله ی کوله پشتی بیکران    3

1-6- مسئله ی کوله پشتی 0 و 1… 3

1-6- بیان مسئله. 4

1-7- اهداف تحقیق    7

فصل دوم- ادبیات و پیشینه تحقیق.. 8

2-1- مقدمه. 9

2-2- تاریخچه. 9

2-3- روش حريصانه براي حل کوله پشتی… 13

2-4- راه حل برنامه نویسی پویا 19

2-5- مسئله ی کوله پشتی 0 و 1. 20

2-6- الگوریتم تقریبی حریصانه. 21

2-7- کاربرد ها 22

2-8- مقدمه ای بر کوله پشتی چند بعدی… 23

2-9- الگوریتم ژنتیک…. 24

2-10- روند كلي الگوريتم‏هاي ژنتيكي… 29

2-11- روند کلي بهينه سازي و حل مسائل در الگوريتم ژنتيک : 31

2-12- شرط پايان الگوريتم.. 32

2-13- برخي از كاربرد الگوريتم‏هاي ژنتيكي… 33

2-14- الگوریتم های تقریبی… 34

2-15- ارزيابي كارايي الگوريتمها 35

2-16- قضيه ي ماكسيمم ها 37

2-16-1- كروموزوم. 38

2-16-2- جمعيت… 38

2-16-3- تابع برازندگي.. 38

2-17-  عملگرهاي الگوریتم  ژنتيك…. 39

2-17-1- عملگر انتخاب… 39

2-17-2- روش های انتخاب… 39

2-17-3- نمونه‏برداري به روش چرخ رولت… 39

2-17-4- انتخاب تورنومنت : 40

2-17-5- عملگر آميزش : 40

2-17-6- تلفیق تک نقطه ای.. 41

2-17-7- روش ادغام دو نقطه ای.. 42

2-18- تلفیق نقطه ای… 42

2-19- تلفیق جامع 42

2-20- عملگر جهش…. 42

2-21- جمع بندی… 43

فصل سوم- ارائه مدل و الگوریتم. 44

3-1- مقدمه. 45

3-2- فرض های مسئله. 45

3-3- حد های بالا و پایین.. 47

3-3-1- نمونه ساده شده کوله پشتی یک بعدی.. 47

3-4-  الگوریتم های حریصانه. 48

3-4-1- الگوریتم HC_KP 49

3-4-2- الگوریتم HC_HV. 50

3-4-3- الگوریتم HC_GAP 50

3-4-4- الگوریتم HC_ORD. 51

3-4-5- الگوریتم HC_ORD2 51

3-5- الگوریتم ژنتیک…. 52

3-5-1- نمایش و برازندگی.. 52

3-5-2- فرآیند تکامل.. 53

3-5-3- عملگر های تلفیق.. 55

3-6- اکتشاف آنلاین.. 57

3-7- خلاصه الگوریتم.. 60

فصل چهارم- محاسبات و یافته های تحقیق.. 62

4-1- نمونه های سنجش با اندازه کوچکتر. 63

4-2- مسائل سنجش با اندازه بزرگ…. 67

4-3- مقایسه با دیگر الگوریتم ها 69

4-4- بسته بندی مربعی… 73

فصل پنجم- نتیجه گیری و ارائه پیشنهادات… 75

5-1- نتیجه گیری… 76

5-2-  پیشنهاداتی برای آینده. 77

منابع و مآخذ.. 78

فهرست جداول

جدول 4-1 – نتایج محاسباتی از نمونه معیار های سنجش با اندازه کوچک………………………………….66

جدول 4-2- نتایج محاسباتی حاصل از نمونه معیارهای سنجش با اندازه بزرگتر……………………………68

جدول 4-3- مقایسه بین الگوریتم های مختلف در نمونه مسایل کوچک…………………………………….71

جدول 4-4- مقایسه با الگوریتم B03 در نمونه های بزرگ………………………………………………………72

جدول 4-5- نمونه مسایل مربعی…………………………………………………………………………………………74

جدول 4-6- خلاصه ای از روش های حل مسئله کوله پشتی دو بعدی با قطعات مستطیلی……………..74

فهرست اشکال و نمودارها

شکل 2-1- بهینه محلی و بهینه کلی ………………………………………………………………………………………28

شکل 2-2- روند کلی الگوریتم های ژنتیکی.. ………………………………………………………………………..30

شکل 2-3-کد برنامه مجازی الگوریتم ژنتیک ساده و فلوچارت آن… …………………………………………30

شکل 2-4- نحوه ارزیابی تابع شایستگی…. …………………………………………………………………………….31

شکل 2-5- نحوه ارزیابی شایستگی در چرخ رولت.. ……………………………………………………………….40

شکل 2-6- یک نمونه از تلفیق…. ……………………………………………….. ………………………………………41

شکل 2-7- روش ادغام دو نقطه ای.. ……………………………………………….. …………………………………42

شکل 3-1- قطعه های قرار گرفته در لایه مستطیل شکل (مرحله ابتدایی).. ……………………………………46

شکل 3-2- قطعه های قرار گرفته در لایه مستطیل شکل (مرحله اول). …………………………………………47

شکل 3-3- قطعه های قرار گرفته در لایه مستطیل شکل (مرحله دوم).. ………………………………………..47

شکل 3-4- عملگر تلفیق OX3.. ……………………………………………….. ……………………………………….56

شکل 3-5- اکتشاف TP_2kp که متناوبا توسط الگوریتم GA_2kp فراخوانی می شود…………………………58

شکل 3-6- بسته بندی جزیی با استفاده از الگوریتم TP_2kp. ………………………………………………………59

شکل 3-7- طرح های غیر ممکن برای اکتشاف پایین چپ (BL) ……………………………………………….60

شکل 3-8- الگوریتم GA_2kp.. ……………………………………………….. ………………………………………….61

راهنمای خرید و دانلود فایل

برای پرداخت، میتوانید از کلیه کارتهای عضو شتاب  استفاده نمائید.

بعد از پرداخت آنلاین لینک دانلود فعال و نمایش داده میشود ، همچنین یک نسخه از فایل همان لحظه به ایمیل شما ارسال میگردد.

در صورت بروز  هر مشکلی،میتوانید از طریق تماس با ما  پیغام بگذارید و یا در تلگرام با ما در تماس باشید، تا شکایت شما مورد بررسی قرار گیرد.

برای دانلود فابل روی دکمه خرید و دانلود  کلیک نمایید.