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- تعریف مسئله