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

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

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

 فهرست مطالب

فصل اول- مقدمه و کلیات تحقیق.. 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_KP49

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

3-4-3- الگوریتم HC_GAP50

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

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

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

فصل اول

مقدمه و کلیات تحقیق

 1-1- مقدمه

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

معروف ترین نوع از این مسئله، مسئله ی کوله پشتی 0 و 1 است. یعنی تعداد از هر شی، یا 0 است (آن شی را انتخاب نمی کنیم) یا 1 ( آن شی انتخاب می شود).

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

یکی از کاربرد های اولیه ی مسئله ی کوله پشتی، طراحی و بارم بندی آزمون است به نحوی که آزمون دهنده در پاسخگویی به سوالات حق انتخاب داشته باشد. چنانچه بارم بندی سوالات همگن باشد، مسئله بسیار ساده خواهد شد.برای مثال، اگر آزمون دارای 12 سوال، هر سوال به ارزش 10 نمره باشد، آزمون دهنده باید فقط 10 سوال را پاسخ دهد تا به بیشینه نمره ممکنِ 100 برسد. اما برای آزمون هایی با بارم بندی نایکسان، مسئله کمی سخت تر می شود.

فرض کنید که دانش آموزان با آزمونی با بارم بندی ناهمگن، با جمع بارم 125 روبرو هستند. از دانش آموزان خواسته می شود با توجه به توانایی های خود به سوالات پاسخ دهند. در اینجا با مسئله ی کوله پشتی روبرو هستیم. چه زیر مجموعه هایی، جمع نمره ای برابر با 100 خواهند داشت؟ برای هر دانش آموز، پاسخ گویی به کدام زیر مجموعه از سوالات، نمره ی بیشتری را به ارمغان می آورد؟

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

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

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

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

مسئله بسته بندی کوله پشتی دو بعدی را می توان بصورت مسئله برش هم در نظر گفت. در این مقاله ما دو واژه برش^[1] و بسته بندی^[2] را ممکن است به جای هم بکار ببریم.

دریافت فایل

---

جهت کپی مطلب از ctrl+A استفاده نمایید نماید