2-21- جمع بندي43
فصل سوم- ارائه مدل و الگوريتم44
3-1- مقدمه45
3-2- فرض هاي مسئله45
3-3- حد هاي بالا و پايين47
3-3-1- نمونه ساده شده کوله پشتي يک بعدي47
3-4- الگوريتم هاي حريصانه48
3-4-1- الگوريتم HCKP49
3-4-2- الگوريتم HCHV50
3-4-3- الگوريتم HCGAP50
3-4-4- الگوريتم HCORD51
3-4-5- الگوريتم HCORD251
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
فصل اول
مقدمه و کليات تحقيق
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- بيان مسئله
مسئله برش وبسته بندي کاربردهاي مستقيم فراواني در چندين زمينه دارد.براي مثال در زمينه هاي حمل ونقل ولجستيکي اشياء در اندازه هاي متفاوت در کانتينرهاي بزرگتر از اندازه استاندارد بسته بندي مي شوند وفضاي موجود درهر کانتينر نياز است تا حد ممکن به طور بيشينه استفاده شود.
اين مقاله به بررسي مسئله اي پردازد که در حوزه بسته بندي بسيار پرکابرد است . فرض کنيد که ما يک مخزن بزرگ داريم و مي خواهيم بسته هاي مستطيلي کوچکي را در درون آن جا دهيم. مسئله را مي توان به اين صورت هم در نظر گرفت که ما بخواهيم اين مخزن بزرگ را برش دهيم. هر يک از اين قطعات کوچکتر داراي طول و عرض و ارزش هستند که ما بايستي مجموع اين ارزش ها را ماکزيمم کنيم. در واقع تابع هدف ما اين است : بيشينه سازي ارزش قطعات بسته بندي شده. به جاي ارزش قطعات مي توان از مساحت آن قطعه که حاصلضرب طول و عرض آن مي باشند هم استفاده نمود.
اين مسئله جايگاه مهمي در صنايع مختلف دارد. مثلا در صنعت فولاد و برش ورق هاي بزرگ فولادي، صنعت شيشه سازي، چوب بري، کاغذ و صنعت چاپ و توزيع روزنامه نمونه هايي از کاربرد اين مسئله مي باشند. از مسائل مرتبط با اين مسئله مي توان به مسئله مينيمم سازي مواد خام تلف شده بوسيله برش اشاره کرد که در واقع مي توان به گونه اي اين دو مسئله را به هم تبديل نمود.
مسئله بسته بندي کوله پشتي دو بعدي را مي توان بصورت مسئله برش هم در نظر گفت. در اين مقاله ما دو واژه برش7 و بسته بندي8 را ممکن است به جاي هم بکار ببريم.
ما در اين مسئله فرض را بر اين مي گيريم که برش ها موازي لبه ها بوده و همچنين جهت قطعات ثابت باشد و چرخشي نداشته باشيم هرچند در عموميت مسئله خلل وارد نمي شود(يعني مي توان چرخش را به اين صورت وارد کرد که جاي طول و عرض قطعه را با هم عوض نماييم). در واقع محدوديت برشي در اينجا مطرح مي شود که نام آنرا برش گيوتين9 مي نامند. برش گيوتين برشي است که از يکي از لبه هاي مستطيل شروع مي شود و به لبه مخالف ديگري ختم مي گردد به شرطي که موازي دو لبه باقيمانده باشد.
در اين مقاله ما براي حل مسئله کوله پشتي دو بعدي الگوريتم ساده و در عين حال کارامدي را ارائه خواهيم کرد. ابتدا و در فاز مقدماتي ما حدود بالايي10 براي مسئله محاسبه مي نماييم. در اينجا راه حل هاي آغازين نيز از طريق الگوريتم هاي حريصانه بدست مي آيند. در ادامه فرآيند جستجوي ژنتيک که از عملگر هاي مختلف و همچنين تئوري نخبه گرايي استفاده مي کند، اجرا مي گردد. جستجوي ژنتيک با يک الگوريتم اکتشاف آنلاين ترکيب مي شود. نتايج محاسباتي نشان مي دهد که اين الگوريتم بهترين راه حل را يافته و نسبت به الگوريتم هاي مشابه زمان معقولتري ارائه مي کند.
هر مسئله يک سري محدوديت و فرض به همراه خودش دارد . در اين مسئله هم ما بايد به نکات و فرض هايي توجه نماييم :
هر مستطيل بسته بندي شده يک جهت گيري ثابت دارد(به عبارت ديگر نمي تواند بچرخد)ولبه هاي ان بايد با لبه هاي صفحات ذخيره شده مطابق باشد(به عبارت ديگر بسته بندي متعامد).
هر مستطيل يک ميزان مرتبط مساوي با نواحيش دارد بنابراين هدف مسئله بيشينه نمودن نواحي کلي از مستطيل هاي بسته بندي است،به عبارتي نواحي بدون استفاده يا اتلاف شده از صفحات ذخيره به حداقل مي رسد(کاهش نظم).مسئله بسته بندي کوله پشتي به مسئله بسته بندي کوله پشتي دوبعدي مستطيل شکل تعلق داردکه براساس طبقه بندي پيشنهاد شده ان پي سخت11 است و کاربردهاي بسياري درصنعت دارد.
برخي الگوريتم ها در گذشته توسعه يافته اند تا اين مسئله ومتغيرهايش را حل کنند .چون که الگوريتم هاي دقيق نيازمند زمان بيشتري براي يافتن يک راه حل هستند الگوريتم هاي ابتکاري عموميت بيشتري دارند .
اخيرا برخي الگوريتم هاي عالي براي کسب کردن راه حل مطلوب توسعه يافته اند .اين الگوريتم هابراي بررسي مسئله بسته بندي سريعتر ونيرومند تر هستند.براي حل نمودن مسئله بسته بندي کوله پشتي مستطيلي از انجايي که ميزان هر مستطيل برابر با نواحيش نيست برخي الگوريتم هاگسترش يافته اند .
اگرچه اين الگوريتم ها نسبتا پيچيده ترهستند و زمان محاسباتي بيشتري را براي يافتن راه حل مطلوب صرف مي کنند.
در ابتدا اين پايان نامه، يک استراتژي مناسب را ارائه مي دهد و سپس يک الگوريتم ابتکاري ساختاري را گسترش مي دهد. يک استراتژي حريصانه از الگوريتم ابتکاري ساختاري استفاده مي کند تا براي تحقيق درمورد راه حل بهتراز آن استفاده کند.در آخر الگوريتم ژنتيک معرفي مي شود تا از دام هاي بهينه محلي از استراتژي حريصانه رهايي يابد تا به عبارتي يک راه حل ديگر را به کار گيرد.
1-7- اهداف تحقيق
اهداف اين تحقيق عبارتند از:
مروري بر روش هاي حل مسئله کوله پشتي با تکيه بر الگوريتم هاي حريصانه و …
مروري بر حل مسائل کوله پشتي دو بعدي
توسعه الگوريتم هاي فراابتکاري براي حل مسئله موجود(کوله پشتي دو بعدي)
مقايسه کارايي الگوريتم هاي بکار رفته و مدل پيشنهادي در اين تحقيق
فصل دوم
ادبيات و پيشينه تحقيق
2-1- مقدمه
در اين فصل بيشتر در مورد تحقيقات و مقالاتي که در زمينه مسئله کوله پشتي انجام گرفته است مي پردازيم . درادامه مسائل بسته بندي که مرتبط با هدف اين تحقيق مي باشند را مورد تجزيه و تحليل قرار مي دهيم. ودر پايان هم به ادبيات مهمتري که در اين پايان نامه بکار گرفته شده است اشاره اي داريم.
2-2- تاريخچه
مسئله ي کوله پشتي بيش از يک قرن مورد مطالعه قرار گرفته و اولين بررسي در سال 1897 انجام گرفته است ]38[ هر چند اولين داده هاي ثبت شده در اين مورد، به کارهاي رياضيداني به نام توبياس دانتزيگ12 برمي گردد، چيزي با عنوان مسئله ي کوله پشتي قبلا در ميان عامه ي مردم وجود داشته است.] 16[
مسئله ي کوله پشتي درجه دوم، اولين بار توسط هامر13،گالو14 و سيمون15 ، و در سال 1960 مطرح شد]39[
در سال 1988، تحقيقي از دانشگاه استوني بروک بر روي مجموعه اي از الگوريتم ها، نشان داد که از ميان 75 مسئله ي الگوريتمي، مسئله ي کوله پشتي، 18 امين مسئله ي معروف و 4 امين مسئله ي پرکاربرد بعد از درخت کي دي، درخت پيشوندي و مسئله بسته بندي جمعي16 است.
در حوزه مسائل بسته بندي و برش چند بعدي مقالات بسياري وجود دارد. از آن جمله اين افراد مي توان به ديکوف17 ]13[ ، هسلر و سواني18]18[ ، سواني و پاترنوستر19]34[ ، دوزلند20]12[ و لودي و همکاران21 ]26[ اشاره کرد.
بعد از کارهاي ابتدايي که گيلمور و گوموري22 ]17[ به انجام رسانيدند، هر يک از محققين بر روي مسئله بسته بندي دو بعدي با فرمت خاص خودشان کار کرده اند. البته روي مسئله بدون محدوديت برش گيوتين تعداد محدودي تمرکز کرده اند از آن جمله مي توان به آرنالز و مورابيتو23 ]2[ اشاره کرد که يک گراف AND/OR و يک جستجوي شاخه و برگ ارائه کرده بودند. همچنين هيلي و همکاران24 ]19[ الگوريتمي بر پايه تشخيص فضا هاي خالي که مي توانند محل قرارگيري قطعات باشند ارائه کردند.
از ديگر محققين در اين زمينه مي توان به بزلي25 ]4[ ، شيتاور و ترنو26]32[ ، حاجي کنستانتينو و کريستوفيدز27 ]9[ ، فکته و شپرز28]14[ ، آمارال و لچفورد29 ]1[ ، بوشتي و همکاران30 ]6[ و کاپارا و موناکي31]8[ اشاره کرد.
بزلي ]4[ الگوريتم شاخه برگي با حد بالا معرفي کرد که از يک فرمولاسيون برنامه ريزي خطي عدد صحيح بهره مي برد. با استفاده از يک تابع بهينه سازي مقدار حد بالايي را کاهش مي دهد.
شيتاور و ترنو]32[ الگوريتم برنامه ريزي عدد صحيحي ارائه کردند براي اينکه برش در ناحيه راست، چپ ، بالا يا پايين انجام شود. البته نتايج محاسباتي در آن مقاله ارائه نشده بود. جالب اينجاست که در مقاله آقايان آمارال و لچفورد]1[ ثابت شد که اين برنامه ريزي عدد صحيح بسيار ضعيف و ابتدايي بوده است. در اين مقاله، نويسندگان يک حد بالايي معرفي نمودند و همچنين راه حلي براي مسئله برنامه ريزي خطي بزرگي که با الگوريتم خاصي حل مي شود.
حاجي کنستانتينو و کريستوفيد]9[ به توسعه يک الگوريتم شاخه و برگ پرداخته که بر پايه توابع لاگرانژي قرار دارد. و در زمينه بهينه سازي بهتر عمل مي کند. نتايجي که از اعمال تست هاي مختلف بدست مي آيد اين مسئله را تاييد مي کند.

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

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

مقاله ديگري که در اين مورد وجود دارد توسط کاپارا و موناکي]8[ ارائه شده است. مولفين در اين مقاله به مقايسه 4 مورد از الگوريتم هاي جديد براي مسئله کوله پشتي دو بعدي پرداخته اند. در اين الگوريتم ها کوله پشتي مورد نظر ظرفيتي معادل با مساحت مستطيل اصلي (مخزن) دارد. همچنين ارزش هر يک از قطعات برابر مقدار مساحتشان است. نتايج محاسباتي نشان مي دهد که با آزمايش اين الگوريتم روي مجموعه هاي بزرگ نتايج بدست آمده قابل رقابت با الگوريتم هاي قبلي مي باشد.
لي و چان ]35[ دو الگوريتم اکتشاف مبتني بر تبريد شبيه سازي شده ارائه کرده اند. اين الگوريتم تبريد شبيه سازي شده مشتمل بر سه گام مي باشد.ابتدا الگوريتم سطح مستطيل اصلي را به زير فضاهايي تقسيم مي کند. اين زير فضاها مکانهايي براي بسته بندي قطعات هستند. سپس شروع به قرار دادن قطعات در نزديکترين فضاي ممکن مي کند(الگوريتم اکتشافي). در نهايت هم توابعي کلاسيک شروع به جابجايي قطعات مي نمايند.
استراتژي تکامل بکار رفته شامل توابع تپه نوردي32 و جهش مي باشد. هر دو الگوريتم اکتشاف مورد نظر روي نمونه هاي توليد شده تصادفي تست شده اند و با تابع هدف مينيمم کردن مواد اوليه اتلافي نتايج خوبي بدست آمده است.
لي يانگ و همکاران]24[ نيز يک الگوريتم اکتشافي تبريد شبيه سازي شده و ژنتيک ارائه کرده اند. مولف با ترکيب اين جستجوي ژنتيک با يک اکتشاف آنلاين ساده به نام پايين-چپ33 ، قطعات را در پايين و چپ ترين نقطه ممکن قرار مي دهد. همجنين در ادامه به بررسي اپراتورهاي تلفيق متفاوتي پرداخته ولي نتايج بدست آمده را شرح نداده است.

اکتشاف آنلاين بکار رفته در مقاله بالا قادر به توليد همه طرح هاي برش ممکن نيست. براي غلبه بر اين مشکل ليو و تنگ ]25[ از اکتشاف آنلاين متفاوتي به نام BL-algorithm استفاده کرده اند. بر طبق اين اکتشاف، بعد از قرار دادن اولين قطعه در نقطه پايين و چپترين، بقيه قطعات با شروع از نقطه گوشه بالا و راست شروع به جايگيري مي نمايند. سپس شروع به شيفت دادن به سمت پايين و چپ مي کنيم.تا جايي که ديگر جايي براي شيفت دادن باقي نمانده باشد. متاسفانه در اين مقاله نتايجي ارائه نشده که بتوانيم آنرا با بقيه نتايج مقايسه نماييم.

تا جايي که ما مي دانيم مقاله اي که توسط بزلي ]4[ ارائه شده است نقش بسزايي در حل اينگونه از مسائل دارد. بر پايه اين الگوريتم متغير هاي صفر يک را در نظر بگيريد که براي نشان دادن اين مطلب که آيا قطعه در درون مستطيل اصلي قرار گرفته است يا نه بکار مي رود. همچنين دو مقدار ديگر که مختصات مرکز قطعه قرار گرفته شده را نشان مي دهد. مدل بکار رفته در اين مقاله منجر به ايجاد رشته کد سه بعدي از يک راه حل مي شود که اين رشته کد براي توليد ژن هاي34 جمعيت الگوريتم ژنتيک بکار مي رود. تکامل جمعيت سپس از طريق عملگر هاي تلفيق و جهش بوقوع مي پيوندد. راه حل هايي ناممکن با ايجاد يک ترم منفي جريمه مي شوند که همين مطلب باعث حرکت به سمت شدني بودن جواب مي گردد.
با انتخاب نمونه هاي استاندارد موجود براي آزمايش اين مدل روي آنها، نمونه هاي بزرگ و کوچکي مورد تست قرار گرفت نتايج حاصله از بزرگترين نمونه ها در مقايسه با نمونه هاي کوچکتر که مدل هاي ديگري روي آنها تست شده اند نشان مي دهد که مدل بزلي از آنها بهتر عمل کرده است.
تکنيک هاي فراابتکاري براي ديگر مسائل مرتبط بسته بندي دو بعدي توسعه داده شده اند. درباره مسئله بسته بندي دو بعدي نوار35، ژاکوب36 ]36[ ، گومز و دلا فونته37]37[ راهکارهاي مبتني بر الگوريتم ژنتيک ارائه کرده اند. هوپر و تورتن]20[ تحقيقي تجربي در مورد روش هاي فرا ابتکاري و اکتشاف انجام داده اند. لوري و همکاران نيز الگوريتمي مبتني بر روش جستجوي ممنوعه براي مسئله بسته بندي دو بعدي ارائه کردند و سپس از راهکار ژنتيک با استفاده از عملگر هاي تلفيق و اکتشاف آنلاين استفاده کرده اند.
در نهايت بورکه و همکاران38 ]7[ يک اکتشاف جايگزيني جديد ارائه کرده اند که با تعبيه کردن آن در يک الگوريتم ژنتيک و يک تبريد شبيه سازي شده به مدل خوبي رسيدند که نتايج قابل قبولي ارائه کرده است.
2-3- روش حريصانه براي حل کوله پشتي
روش ، صفر و يك: يعني يك شيء يا به طور كامل در كوله‌پشتي قرار مي‌گيرد يا اصلا قرار نمي‌گيرد.
روش كسري: كه مي‌توان بخشي از يك شيء را در كيسه قرار داد. مثلا مي‌توان دوسوم يك شيء را در كوله‌پشتي قرار داد.
هر دو حالت را توضيح خواهيم داد. بسيار خوب فرض كنيد مجموعه S اشياي موجود را نشان مي‌دهد و دزد مي‌تواند آنها را انتخاب بكند و مقدار Pitem ارزش يك شيء و Witem وزن آن شيء است و W وزني است كه كوله‌پشتي مي‌تواند تحمل بكند.

روش صفر و يك: اولين استراتژي اين است كه بياييم تمام زير مجموعه‌هاي موجود از S را به دست بياوريم و سپس از بين آنها زير مجموعه‌اي را انتخاب كنيم كه داراي بيشترين ارزش باشد و وزن اشياي آن بيشتر از وزن كوله‌پشتي نباشد. آيا اين روش درست است؟
جواب قطعا خير است. مي‌دانيم‌تعدادزيرمجموعه‌هاي يك مجموعه n عضوي برابر 2 به توان n است، همان‌طور كه مشخص است اين راه براي مجموعه‌هاي بزرگ جوابگو نيست. اما راه‌حل چيست؟
يك راه که در مقالات پيشين به آن پرداخته شده اين بوده است كه اشيا را به ترتيب وزن مرتب كنيم و سپس بيشترين‌ها را در كوله‌پشتي قرار دهيم. اين روش نيز رد شده است چرا که فرض كنيد يك وسيله داراي ارزش بيشتري است ولي وزن آن كمتر از بقيه است يا بعكس. نتيجه حاصل الزاما نتيجه بهينه مساله نيست.

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

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

راه‌حل ديگري كه مطرح شده بود مثل همين راه بالاست، يعني به جاي اين‌كه بر اساس وزن مرتب كنيم بر حسب ارزش مرتب كنيم، اما نتيجه حاصل از اين روش نيز مانند روش بالا بهينه نبوده است. به‌خاطر اين‌كه ممكن است اشياي داراي ارزش بيشتر، وزن بيشتري داشته باشند و اگر در كوله‌پشتي قرار بگيرند الزاما نتيجه بهينه به دست نمي‌آيد. چون ممكن است ارزش چند شيء سبك‌تر روي هم بيشتر از ارزش يك شيء بزرگ باشد. پس هميشه جواب بهينه را نمي‌دهد.

راه‌حل ديگري وجود دارد؟ روش بالا احتمالا شما را به اين راه‌حل نزديك كرده است. اين راه‌حل قصد دارد نارسايي روش‌هاي بالا را حل كند، اين روش مي‌گويد بهتر است اشيا بر اساس يك نسبت مشخص كه حاصل از نسبت ارزش به وزن آنهاست، در كوله‌پشتي قرار بگيرند با اين روش مشكلاتي كه در بالا گفته شد، به وجود نمي‌آيد به دليل اين كه شما يك نسبت داريد و اشيا بر حسب نسبت ارزش به وزن در كوله‌پشتي قرار مي‌گيرند پس اگر يك شيء ارزش بيشتري داشت و وزن كمتر، شانس بيشتري براي قرار گرفتن در كوله‌پشتي دارد.
براي اينکار، در اولين مرحله نسبت ارزش به وزن را براي همه اشيا به دست مي‌آوريم سپس آنها را مرتب مي‌كنيم و اشيايي كه داراي نسبت بيشتر هستند ابتدا در كوله‌پشتي قرار مي‌گيرند تا زماني كه وزن اشياي موجود در كوله‌پشتي از W بيشتر نشود.
يك مثال مطرح مي‌كنيم كه در فهم بهتر اين موضوع به ما كمك مي‌كند، فرض كنيد داريم:
P1=5,W1=50
P2=10,W2=60
P3=20,W2=140
W=30
سپس نسبت ارزش به وزن را حساب مي‌كنيم:
Q=10
Q=6
Q=7
اگر اشيا را بر حسب اين نسبت در كوله‌پشتي قرار دهيم، ارزش كل اشياي موجود در كوله‌پشتي برابر 190مي‌شود، اما اگر آنها را بر اساس وزن قرار دهيم، ارزش كوله‌پشتي برابر 200 مي‌شود!
شايد شما هم تعجب كنيد كه چرا روش آخر نتيجه بهينه را به دست نمي‌آورد؟
اين خاصيت تمامي ‌الگوريتم‌هاي حريصانه است كه هميشه اين نتيجه را به دست نمي‌آورند و براي بعضي مسائل نتيجه مي‌دهند پس هميشه نمي‌توان به آنها اطمينان كرد كه جواب بهينه بدهد.

روش كسري: در اين روش شما مي‌توانيد بخشي از اشيا را درون كوله‌پشتي خود قرار دهيد، مثلا دوسوم يك شيء را در كوله‌پشتي بگذاريد.
اين هم مثل همان روش نسبت ارزش به وزن است، اما در آخر اگر مجموع ارزش اشياي موجود در كوله‌پشتي از وزن كوله‌پشتي كمتر بود و اين وزن كمتر از وزن يك شيء بود، مي‌توان بخشي از شيء را در كوله‌پشتي قرار داد. بگذاريد با مثال توضيح دهيم:
در مثال بالا اشيا را بر حسب نسبت ارزش به وزن در كوله‌پشتي قرار داديم، پس ابتدا P1 سپس P3 مجموع ارزش آنها برابر 190 است و هنوز مي‌توان يك شيء با وزن 5 در كوله قرار داد، اما شيء P2 وزنش برابر 10 است! اين روش مي‌گويد كه مي‌توان نصف شيء P2 را در كوله‌پشتي قرار داد كه ارزش آن برابر 30 است. در نتيجه ارزش اشياي موجود در كوله‌پشتي برابر 220 مي‌شود و اشيايي كه در كوله‌پشتي‌اند به صورت زير هستند:
P1+P3+1/2P2
همان طور كه ديديد اين روش نتيجه بهينه‌تري نسبت به روش‌هاي قبلي داد.آيا اين روش نيز مثال نقضي دارد كه ثابت شود هميشه نتيجه بهينه نيست؟
فرض کنيد جسم داريم که از تا شماره گذاري شده اند. جسم ام ارزشي معادل و وزني برابر با دارد. معمولا فرض مي شود که وزن ها و ارزش ها نامنفي اند. براي ساده تر شدن نمايش، بدون کم شدن از کليت مسئله مي توان فرض کرد اشيا به ترتيب صعودي بر حسب وزنشان مرتب شده اند. بيشترين وزني که مي توان در کوله پشتي حمل کرد، است.
معروف ترين نوع از اين مسئله، مسئله ي کوله پشتي 0 و 1 است. يعني تعداد از هر شي، يا 0 است (آن شي را انتخاب نمي کنيم) يا 1 ( آن شي انتخاب مي شود). مسئله ي کوله پشتي 0 و 1 را مي توان به اين صورت، به زبان رياضي بيان کرد:
مقدار را بيشينه کنيد.
به طوري که
مسئله ي کوله پشتي کران دار، نسخه ي ديگري از اين سوال است که در آن تعداد اشيا () عددي صحيح و نامنفي و حد اکثر برابر با است. به بيان رياضي[4]:
مقدار را بيشينه کنيد.
به طوري که
مسئله ي کوله پشتي بيکران ، هيچ محدوديتي روي تعداد اشيا قائل نمي شود. يعني از هر شي، به هر تعداد دلخواهي مي توان انتخاب کرد. نسخه اي ازين سوال که بيش از همه مورد توجه قرار ميگيرد، داراي ويژگي هاي زير است:
* يک مسئله تصميم است.
* مسئله 0 و 1 است.
* براي هر شي، وزن و ارزش آن برابرند. يعني .
دقت کنيد که در اين مورد خاص، اين مسئله هم ارز است با: ” مجموعه اي از اعداد صحيح نا منفي داده شده است. آيا زير مجموعه اي از آن وجود دارد که جمع اعضايش دقيقا شود؟” و چنانچه وزن هاي منفي هم قابل قبول باشند، و برابر با در نظر گرفته شود، مسئله عبارت است از: ” مجموعه اي از اعداد صحيح داده شده است. آيا زير مجموعه اي غير تهي از آن هست که جمع اعضايش شود؟” اين مسئله خاص، مسئله جمع زيرمجموعه ها ناميده مي شود. در رمزنگاري، هر گاه از مسئله کوله پشتي نام برده مي شود، منظور مسئله جمع زيرمجموعه ها است]2[
چنانچه چند کوله پشتي داشته باشيم، مسئله تبديل به سوال bin packing مي شود.
از ديد علوم کامپيوتر، مسئله ي کوله پشتي شايان توجه است زيرا:
* الگوريتمي با زمان اجراي شبه چند جمله اي با استفاده از برنامه نويسي پويا دارد.
* الگوريتمي تقريبي با زمان چند جمله اي دارد که از الگوريتم هاي با زمان شبه چند جمله اي به عنوان يک زير-برنامه استفاده مي کند.
* حل دقيق اين سوال، مسئله اي از نوع ان پي کامل است. بنابراين پيش بيني شده که راه حلي که هم درست و هم سريع باشد( با زمان اجراي چند جمله اي) براي هر ورودي دلخواه، ندارد.
تلاش هايي براي استفاده از مسئله ي جمع زير مجموعه ها به عنوان اصل در سيستم هاي رمزنگاري کليد عمومي، مانند سيستم رمزنگاري کوله پشتي مرکل-هلمن39 انجام شد]2[. در اين روش ها، معمولا از گروههايي به جز اعداد صحيح استفاده مي شد. الگوريتم هاي مشابه ديگر بعدا با شکست روبرو شدند، زيرا مسائل خاصي که توليد مي کردند در زمان چند جمله اي قابل حل بودند.]1[
در خيلي از تحقيقات سعي مي شود به اين سوال پاسخ داده شود که نمونه هاي سخت مسئله ي کوله پشتي چه هستند؟]1[ يا از ديد ديگر، چه ويژگي هايي از مثال هاي مسئله ي کوله پشتي، باعث مي شود در زماني معقولتر نسبت به آن چه در صورت کلي ان پي کامل سوال مطرح است، حل شوند. الگوريتم هاي زيادي بر پايه برنامه نويسي پويا روش تقسيم و حد، يا ترکيبي از هر دو روش براي اين مسئله وجود دارند.]3[
2-4- راه حل برنامه نويسي پويا
اگر تمام وزن ها ( ) اعداد صحيح نامنفي باشند، مسئله ي کوله پشتي در زماني شبه چند جمله اي با استفاده از برنامه نويسي پويا قابل حل است. ]3[
براي سادگي فرض کنيد تمام وزن ها اکيدا مثبت اند ( ). مي خواهيم جمع ارزش کالاهاي انتخاب شده را بيشينه کنيم با اين فرض که مجموع وزن آنها حداکثر شود.
حال براي هر ، مقدار را بيشترين ارزش قابل دستيابي تعريف کنيد به طوري که جمع وزن اشيا انتخاب شده حد اکثر شود. بديهي است که پاسخ مورد نظر است.
دقت کنيد که ويژگي هاي زير را دارد:
جمع اعضاي مجموعه ي تهي 0 است يعني:
*
*
بيشترين ارزش قابل دستيابي از مجموعه ي تهي، 0 است. براي محاسبه ي هر کدام از ها، بايد شي را بررسي کرد. همچنين آرايه ي ، عنصر دارد. بنابر اين زمان اجراي اين الگوريتم است. بديهي است با تقسيم کردن بر بزرگترين مقسوم عليه مشترک شان، مي توان زمان اجراي الگوريتم را بهينه کرد[3].
پيچيدگي زماني تناقضي با NP-complete بودن مسئله ي کوله پشتي ندارد. زيرا برخلاف ، برحسب ورودي چند جمله اي نيست. طول ِ ورودي، متناسب با تعداد بيت هاي لازم براي نمايش ، يعني است، نه خود .
2-5- مسئله ي کوله پشتي 0 و 1
روش مشابهي با استفاده از برنامه سازي پويا براي حل مسئله کوله پشتي 0 و 1 با پيچيدگي زماني شبه چندجمله اي وجود دارد. مانند بالا، فرض کنيد ها اعداد صحيح اکيدا مثبتي هستند. را بيشترين ارزش قابل دستيابي، با استفاده از اشياي 1 تا با حد اکثر وزن تعريف مي شود]4[
را مي توان به طور بازگشتي، مطابق زير تعريف کرد:
*
*
* اگر
* اگر .
پاسخ با محاسبه ي بدست مي آيد. براي کارآمد شدن راه حل، مي توان از جدولي براي نگهداري نتايج محاسبات قبلي استفاده کرد. بنابراين پيچيدگي زماني آن و حافظه خواهد شد. همچنين مي توان حجم حافظه را به کاهش داد. به اين ترتيب که آرايه ي يک بعدي، ارزش بهينه تا کنون را نشان مي دهد. از شروع کرده، آرايه را پر مي کنيم. سپس با حرکت بر روي ، مقدار را با افزدون يک شي جديد به انتخاب ها، به روز آوري مي کنيم.

الگوريتم ديگري براي مسئله کوله پشتي 0 و 1، در سال 1974 ارائه شد]4[ که گاهي “رويارويي در ميانه” نيز ناميده مي شود. اين الگوريتم نسبت به تعداد اشيا نمايي است. (اين اسم، از الگوريتمي مشابه در رمزنگاري نشات گرفته است). هنگامي که نسبت به بسيار بزرگتر باشد ( يعني از هم بزرگتر باشد)، اين الگوريتم نسبت به روش پويا از نظر زماني بهينه تر است.


پاسخ دهید