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

دانشگاه علوم و فنون مازندران

دانشکده مهندسی صنایع

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

گرایش مهندسی سیستم های اقتصادی اجتماعی

عنوان:

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

استاد راهنما:

جناب آقای دکتر نیکبخش جوادیان

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی گردد

(در فایل دانلودی نام نویسنده موجود می باشد)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل می باشد)

فهرست مطالب:

فصل اول- مقدمه و کلیات پژوهش……………………………………… 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………………………………………………….

3-4-2- الگوریتم HCHV…………………………………………………

3-4-3- الگوریتم HCGAP………………………………………………..

3-4-4- الگوریتم HCORD……………………………………………….

3-4-5- الگوریتم HCORD2……………………………………………..

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

چکیده:

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

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

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

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

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

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

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

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

فصل اول: مقدمه و کلیات پژوهش

1-1- مقدمه

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

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

نسخه ی مسئله تصمیم برای مسئله ی کوله پشتی، این سوال می باشد: “آیا ارزش V با انتخاب اشیایی با مجموع وزن کمتر یا مساوی W، قابل دستیابی می باشد؟”

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

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

 در این ارتباط بایستی روشی برای حل این مسئله پیدا نمود . یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می کند ، عبارت از برنامه نویسی برای کامپیوتر به مقصود امتحان کردن تمامی بردارهای دودویی ممکن x می باشد، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند. متاسفانه تعداد چنین بردارهایی مشکل اصلی ماست .بطوریکه یک کامپیوتر فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛برای n = 60 بیش از 30 سال وقت لازم دارد و بیش از 60 سال برای n = 61 و دهها قرن برای n = 65 والی اخر. با این تفاصیل با بهره گیری از الگوریتمهایی خاص می توان در بسیاری موردها مسئله ای با n = 100 000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل نمود .

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

صورت مسئله: دزدی قصد سرقت از مغازه ای رو دارد و حداکثر وزن w از اجناس را که می تواند بدزد در این مغازه n نوع جنس هست. اگر وزن جنس iام wi و قیمت آن vi باشد ماکسیمم سودی که بدست می آورد چقدر می باشد؟

این مسئله به دو صورت تعریف میشود : 1- صفر و یک 2- حالت کسری

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

ایده حل این مسئله در حالت پویا به این شکل هست که دزد یا جنس iام رو برمیدارد و یا برنمیدارد و براساس این دو حالت سود زیرمسئله ایجاد شده محاسبه میشود و از مسیری که جواب ماکسیمم رو داده پیش خواهد رفت.

حالت دوم حالت کسری می باشد که دزد می تواند کسری از یک قطعه را بردارد.

[1] container

[2] Elitist theory

[3] Immigration rate

[4] Heuristics on-line

[5] crossover

[6] upper bounds

تعداد صفحه : 92

قیمت : 14700تومان

این مطلب رو هم توصیه می کنم بخونین:   پایان نامه مهندسی صنایع گرایش صنایع: مدل زنجیره تأمین استوار چند هدفه برای شرکت ملی پخش فراورده های نفتی ایران وحل آن به وسیله الگوریتم فرا ابتکاری NS-GAII

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

و در ضمن فایل خریداری شده به ایمیل شما ارسال می گردد.

پشتیبانی سایت :               serderehi@gmail.com

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

***  *** ***