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

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

 

فرمت فایل : WORD (قابل ویرایش)

تعداد صفحات:91

پایان نامه برای دریافت درجه کارشناسی ارشد در رشته مهندسی صنایع
گرایش مهندسی سیستم های اقتصادی اجتماعی

فهرست مطالب:
فصل اول- مقدمه و کلیات تحقیق    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- الگوریتم HCKP    49
3-4-2- الگوریتم HCHV    50
3-4-3- الگوریتم HCGAP    50
3-4-4- الگوریتم HCORD    51
3-4-5- الگوریتم HCORD2    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- اکتشاف TP2kp که متناوبا توسط الگوریتم GA2kp فراخوانی می شود..............................58
شکل 3-6- بسته بندی جزیی با استفاده از الگوریتم TP2kp. ...............................................................59
شکل 3-7- طرح های غیر ممکن برای اکتشاف پایین چپ (BL) .......................................................60
شکل 3-8- الگوریتم GA2kp.. ........................................................ .................................................61

چکیده
مسئله کوله پشتی ، مسئله ای در بهینه سازی ترکیبیاتی است. ازمسئله کوله پشتی به نام هایی چون KnapsackیاRucksack نیز یاد می کنند. به بیان ساده مسئله کوله پشتی اینطور بیان می شود که فرض کنید مجموعه ای از اشیا، که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به طوری که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده، و ارزش آنها بیشینه شود.
در این مسئله ما یک مستطیل بزرگتر داریم که بایستی به تعبیری آنرا برش زده و به قطعات کوچکتر تقسیم کنیم. در واقع این به این معناست که ما در داخل این مستطیل بزرگ که مخزن  هم میتوان آنرا نامید ، قطعات مستطیلی کوچکتری قرار دهیم.
هدف از این نوع بسته بندی هم ماکزیمم کردن سطح مستطیل های قرار گرفته شده است. ما در این مقاله ابتدا الگوریتمی حریصانه جدیدی ارائه کرده و به دنبال آن یک رهیافت ژنتیک با استفاده از تئوری نخبه گرایی  ، نرخ مهاجرت ، اکتشاف آنلاین  و اپراتورهای تلفیق  مناسب معرفی می کنیم.
به عنوان مثال ارائه یک توالی مناسب برای جمع آوری بسته های موجود .
ابتدا و در فاز مقدماتی ما حدود بالایی  برای مسئله محاسبه می نماییم. در اینجا راه حل های آغازین نیز از طریق الگوریتم های حریصانه بدست می آیند. در ادامه فرآیند جستجوی ژنتیک که از عملگر های مختلف و همچنین تئوری نخبه گرایی استفاده می کند، اجرا می گردد. جستجوی ژنتیک با یک الگوریتم اکتشاف آنلاین ترکیب می شود.
از منظر روش تحقیق بکار رفته در این مسئله، از نظر هدف پژوهش می توان گفت که تحقیق از نوع کاربردی بوده و بر اساس ماهیت و روش گردآوری داده ها یک پژوهش توصیفی می باشد.
از دستاوردهای این تحقیق می توان به این نکته اشاره کردکه بر طبق نتایج محاسباتی و تعداد زیادی از معیارهای سنجش کارایی با مقیاس کم و زیاد (مسائل بزرگ و کوچک) ، مدلی که ما ارائه کرده ایم نتایج بهتری از مدل های قبلی موجود نشان می دهد و راه حل هایی با تابع هدف بزرگتر تولید می نماید.
روش فراابتکاری بکارگرفته شده در این پایان نامه مبتنی بر الگوریتم ژنتیک می باشد. .سپس الگوریتمی حریصانه جهت یافتن یک راه حل بهتر و مناسب تر بکار گرفته شده است. و در نهایت هم با استفاده از یک الگوریتم فرا ابتکاری راه گذر کردن از یک نقطه بهینه محلی به نقطه بهینه اصلی فراهم می گردد.
کلمات کلیدی : مسئله کوله پشتی دو بعدی، الگوریتم حریصانه،  الگوریتم ژنتیک

پایان نامه طراحی الگوریتم فراابتکاری برای زمانبندی ماشین های موازی نامرتبط با تابع هدف چندگانه در محیط تولید بهنگام

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

فرمت فایل : WORD (قابل ویرایش)

تعداد صفحات:114

پایان نامه مقطع کارشناسی ارشد
مهندسی صنایع- مهندسی سیستم های اقتصادی اجتماعی

فهرست مطالب:
فصل اول مقدمه و کلیات    1
1-1.    مقدمه    2
1-2. تعریف مسأله زمانبندی    5
1-3. ضرورت انجام تحقیق    7
1-4. اهداف تحقیق    8
1-5. مفروضات مسئله    9
1-6. جنبه های نوآوری تحقیق    10
1-7. محتوای تحقیق    10
فصل دوم ادبیات و پیشینه تحقیق    11
2-1. مقدمه    12
2-2. طبقه بندی محیط های زمانبندی    15
2-3. مسائل ماشینهای موازی    19
2-3-1.  زمان نصب و آماده سازی    20
2-3-2. دسترسی محدود به ماشینها    26
2-3-3. زمان دسترسی متفاوت به کارها    27
2-4. مسائل با تمرکز بر موعد تحویل برای کارها    27
2-4-1. زمان تکمیل کارها    29
2-4-2. زمانهای زودکرد و دیرکرد    29
2-5. مروری بر رویکرد و اصول سیستم تولیدی  بهنگام    31
2-6. توالی ماشینﻫای موازی با معیارهای زودکرد و دیرکرد    33
2-7. جمع بندی    34
فصل سوم مدل ریاضی و بهینه سازی چند هدفه    36
3-1. مقدمه    37
3-2. تعریف مسئله    37
3-2-1. مفروضات مسئله    39
3-3. مدل پیشنهادی    39
3-3-1.نمادها، تعاریف، پارامترها و متغیر های تصمیم    40
3-3-2.  پارامترهای ورودی    40
3-3-3.  توابع هدف    41
3-3-4.  محدودیتها    41
3-4. اعتبارسنجی مدل    43
3-5. پیچیدگی مسئله    45
3-6  بهینه سازی چند معیاره    47
3-6-1. ارتباط غالب    47
3-6-2. نقاط بهینه موضعی    48
3-6-3. نقاط بهینه سراسری    48
3-6-4. مرز بهینه    48
3-7. روشهای بهینه سازی    49
3-7-1. روشهای اسکالر    49
3-7-2. روش مجموع وزنی    51
3-7-2-1. طراحی روش مجموع وزنی برای حل مسأله مورد نظر    54
3-7-3. روش محدودیت-ε    55
3-7-3-1. طراحی روش محدودیت – ε برای حل مسأله    57
3-7-4. روشهای عکس العملی    57
3-7-5. روش های مبتنی بر منطق فازی    58
3-7-6. روش های فرا ابتکاری    59
3-7-7. الگوریتم NSGA-II    60
3-7-7-1. مرتب سازی سریع    61
3-7-7-2. عملگر گزینش تورنمنت تراکمی    63
3-7-7-3. فاصله تراکمی    63
3-7-8. طراحی روش فراابتکاری NSGA-II برای حل مسأله    65
3-7-9. طراحی روش فراابتکاری CENSGA برای حل مسأله    70
3-8. مقایسه روش های بهینه سازی چند هدفه    71
3-8-1.  شاخص متوسط فاصله از نقطه ایدهآل    73
3-8-2.  شاخص نرخ دستیابی به توابع هدف    74
3-8-3.  شاخص گستردگی جواب های غیر مغلوب (SNS)    74
3-8-4. شاخص یکنواختی فضا    74
3-9. جمعﺑندی    75
فصل چهارم محاسبات و نتایج  تحقیق    77
4‐1. مقدمه    78
4‐2. تنطیمات پارامترها و شرایط اجرای الگوریتم ها    79
4-3. الگوریتمهای  NSGA-II,CENSGA    80
4-4. روش مجموع وزنی    80
4-5. روش محدودیت-ε    81
4‐6. ساختار مسائل    82
4‐7. معیارهای ارزیابی الگوریتمها    83
4‐8. مسائل با ابعاد کوچک و متوسط    83
4-8-1. نتایج آزمایشات مسائل کوچک و متوسط    83
4‐9. مسائل با ابعاد بزرگ    90
4‐10. نتایج محاسباتی    90
4‐11. جمعﺑندی    96
فصل پنجم نتیجه گیری و پیشنهادات    97
5‐1. مقدمه    98
5‐2. نتیجهﮔیری    99
5‐3. پیشنهادهای آتی    100
فهرست منابع و مراجع    102
    
فهرست جداول
جدول 2-1. محیط¬های کارگاهی (نماد α)     13
جدول 2-2. توابع هدف رایج در ادبیات     15
جدول 3-1. زمان¬های پردازش،موعدهای تحویل و زمان دسترسی    44
جدول 3-2. زمان نصب ماشین یک و دو برای کارهای مختلف     44
جدول 4-1.  حدهای بالا برای مسائل مختلف     82
جدول 4-2.  جوابهای نامغلوب مربوط به مسأله 5j2m به تفکیک روش ها    84
جدول 4-3.  ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j2m     85
جدول 4-4.  جوابهای نامغلوب مربوط به مسأله 5j3m به تفکیک روش ها    85
جدول 4-5. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j3m     86
جدول 4-6. جوابهای نامغلوب مربوط به مسأله 8j2m به تفکیک روش ها    87
جدول 4-7.  ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j2m    88
جدول 4-8 . جوابهای نامغلوب مربوط به مسأله 8j3m به تفکیک روش ها     89
جدول 4-9.  ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j3m     90
جدول 4-10 نتایج شاخص¬های متریک برای الگوریتم CENSGAوNSGA-II     91
جدول 4- 11.  ارزیابی آماری الگوریتم¬های فراابتکاری بکار گرفته شده     94

فهرست شکل¬ها و نمودارها
شکل 2-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید     19
شکل 3-1. سلسله¬مراتب پیچیدگی محیط¬های کارگاهی در مسائل زمان¬بندی    46
شکل 3-2. سلسله¬مراتب پیچیدگی توابع هدف در مسائل زمان¬بندی    46
شکل 3-3. نقاط بهینه موضعی     48
شکل 3-4.  رابطه فضای جواب و ارتباط غالب     48
شکل 3-5.  نمایش روش مجموع وزنی با مرز بهینه پارتو محدب     52
شکل 3-6.  نمایش روش مجموع وزنی با مرز بهینه پارتو غیر محدب     54
شکل 3-7. روش محدودیت- ε     56
شکل 3-8.  نمایش الگوریتم NSGAII    61
شکل 3-9.  محاسبه فاصله تراکمی     64
شکل 3-10.  ساختار کروموزوم    66
شکل 3-11.  نحوه ایجاد جمعیت اولیه     67
شکل 3-12.  نحوه عملکرد عملگر تقاطع     69
شکل 3-13. عملگر تقاطع تک نقطه ای با نقطه برش 3    69
شکل 3-14. نحوه عملکرد عملگر جهش     70
شکل 3-15. استراتژی انتخاب در الگوریتم CENSGA  و NSGA-II     71
شکل 3-16.  دو هدف در بهینه سازی چند هدفه    72
شکل 3-17.  یک مجموعه ایده آل از جواب های نامغلوب    72
شکل 3-18.  همگرائی خوب، اما تنوع ضعیف (الگوریتم 1)    73
شکل 3-19.  همگرائی ضعیف، اما تنوع خوب (الگوریتم 2)    73
شکل 4-1.  نمایش جوابهای نامغلوب ε-محدودیت مسأله 5j2m     84
شکل 4-2.  نمایش جوابهای نامغلوب روش وزنی مسأله 5j2m     84
شکل 4-3. نمایش جوابهای نامغلوب روش وزنی مسأله 5j3m    86
شکل 4-4.  نمایش جوابهای نامغلوب  روش محدودیت-ε مسأله 5j3m    86
شکل 4-5 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j2m    88
شکل 4-6 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j2m     88
شکل 4-7 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j3m     89
شکل 4-8 .  نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j3m    89
شکل 4- 9  نمودار نتایج محاسباتی شاخص های متریک در مسائل مختل    92
شکل 4-10. نمودارجعبه ای (BoxPlot) نتایج ارزیابی الگوریتم¬های  CENSGA,NSGA-II     93
شکل 4-11. نمودار میانگین و فواصل اطمینان (سطح اطمینان 95%)نتایج ارزیابی الگوریتم ها     95

چکیده
    در طول دهه گذشته، گسترش الگوریتم¬های فراابتکاری بهینه سازی چند معیاره توجه بسیاری را به خود جلب کرد. مسائل برنامه ریزی تولید بهنگام به عنوان مهمترین مسئله برنامه¬ریزی بهینه سازی نیز مستثنی نبود. البته بسیاری از الگوریتم¬های بهینه سازی که برای مسائل گوناگون به کار برده می¬شدند رویکردی نامناسب داشتند. به زبان دیگر بسیاری از آنها هدف¬ ها را ترکیب می¬کردند و مسائل را با رویکرد تک هدفه حل می¬کردند. البته بعضی از محققان الگوریتم¬های پارتویی به کار می¬برند. در این تحقیق یک برنامه ریزی ماشین¬های موازی نامرتبط با زمان آماده سازی وابسته به توالی، زمان دسترسی پویا به کارها، زمان تحویل متفاوت کارها و محدودیت مجموعه پردازشی نشان داده شده است. توابع هدف مورد نظر، مجموع وزنی زمانهای زودکرد و دیرکرد کارها و همچنین مجموع زمان تکمیل کارها را کمینه می-کنند. برای حل مدل و اعتبار سنجی آن از الگوریتم¬ مجموع وزنی و الگوریتم محدودیت اپسیلون استفاده شده است. همچنین نشان داده شده است که الگوریتم¬هایی که از روش شاخه و کران برای حل استفاده می¬کنند قادر به حل مسائل بزرگ در زمان معقول نمی-باشند. بنابراین برای حل این مسئله برنامه ریزی چند معیاره که از نوع چند جمله¬ای سخت (NP-Hard) می¬باشد الگوربتم فراابتکاری (CENSGA)معرفی شده است. الگوریتم ارائه شده را  با استفاده از شاخص¬های آماری با الگوریتم فراابتکاری (NSGA-II) مورد مقایسه و تحلیل قرار داده شده است که نتایج نشان دهنده کارایی بهتر الگوریتم فراابتکاری (CENSGA)  می¬باشد.  
کلمات کلیدی: تولید بهنگام; زمان آماده¬سازی وابسته به توالی;  کنترل نخبه¬گرایی; بهینه سازی چند هدفه; الگوریتم مرتب سازی نامغلوب.