منابع پایان نامه ارشد درباره منابع محدود

تخاب مي‌شود. در اين انتخاب‌ها ترتيب اهميتي ندارد. پس تعداد حالت‌هاي انتخاب n خانه براي چيدن n وزير ترکيب n ازn2 يا C(n,n2) است که حتي براي n‌هاي نه چندان بزرگ (نظير 8) عدد بزرگي به دست مي‌آيد. اين خود گوياي اين واقعيت است که مسأله n-وزير در حين سادگي در توصيف، حل آن به اندازه کافي سخت هست که تبديل به يک مسأله کلاسيک و متعاقبا يک محک در فيلدهاي مختلف علوم کامپيوتر شود.
3-2-2- مسأله رنگآميزي گراف88
مسأله رنگ آميزي رئوس گراف، يک مسأله جاافتاده کلاسيک در تئوري گراف است که در آن به هر يک از رئوس گراف يک رنگ انتساب داده ميشود ؛ بگونـهاي کـه بـه هـر دو گره مجـاور دلخواه از گراف، رنگ هاي متفاوت? اختصـاص داده شـود. شکل زير مثالي از اين مسأله را نشان ميدهد.

شکل 3-3 مثالي از رنگ آميزي گراف(يک رنگ آميزي از گراف معروف پترسن به کمک 3 رنگ،کمترين تعداد رنگهاي ممکن)
يکي از پايگاههاي موجود براي دانلود مجموعه دادهاي مختلف مسأله رنگ آميزي گراف آدرس معرفي شده در مرجع [64] ميباشد که در اکثر مقالات مورد استفاده قرار گرفته است.
نمونه هاي موجود در اين لينک در دو فرمت استاندارد DIMACS (نمونه هايي که با پسوند .col مشخص شده اند) و Compressed (نمونه هايي که با پسوند .col.b مشخص شده اند) آورده شده اند. هر نمونه شامل اطلاعات تعداد گرهها، تعداد يالها، تعداد رنگهاي بهينه براي رنگ آميزي اين گراف است و هر مجموعه دادهاي ساختار ارتباطي گراف را تعريف ميکند.
3-2-3- مسأله زمانبندي89
مسأله جداول زماني، به فرايند تخصيص منابع محدود مکاني- زماني، به تعدادي رويداد، با شرط ارضاء تعداد زيادي محدوديت، اشاره مينمايد. مسأله ايجاد جداول زمانبندي از دسته مسائل بحث برانگيز ي است كه در حوزه هاي كاربردي مختلف راه حل هاي متنوعي براي آن ارائه شده است .اين مسأله از دسته مسائل NP-Complete بوده و راه حل ها و مطالعات زيادي پيرامون اين مسأله ارائه شده است تا به آنجا که اين مسأله به عنوان يک محک در ارزيابي روشهاي مختلف حل مسائل DCSP مورد استفاده قرار گرفته است.
به عنوان مثالهايي از اين حوزه ميتوان به زمانبندي دروس دانشگاهي يا زمانبندي کار اشاره کرد که در ادامه آنها را به اختصار شرح ميدهيم. توصيف اين مثالها نشان ميدهد چگونه يک مسأله زمانبندي ميتواند به عنوان يک مسأله ارضاء محدوديت تلقي گردد و به عنوان يک محک در روشهاي مختلف پيشنهادي اين فيلد مورد استفاده قرار گيرد.
زمانبندي دروس دانشگاهي : يکي از مسائل مهم اموزشي در دانشگاه‌ها‌، تنظيم برنامه‌ هفتگي است. اين موضوع نمونه‌اي ازمسأله عمومي زمانبندي مي‌باشد که به شکل‌هاي گوناگون و مطابق با محيط‌هاي مختلف تعريف مي‌شود. تنظيم برنامه هفتگي يک واحد اموزشي عبارتست از زمانبندي دروس يا جلسات مختلف، کلاس، استاد در جدول زماني ترم تحصيلي با توجه به اينکه گروه‌هاي مختلف دانشجويان از استادان و کلاس‌ها و امکانات مشترک استفاده مي‌کنند. عموما مسأله جداول زماني به طراحي برنامه کلاسي يا امتحانات، در محيط هاي آموزشي اشاره مينمايد. با توجه به افزايش تعداد دانشجويان، ايجاد رشته هاي جديد و کمبود فضاهاي اموزشي، با محدوديتهاي بسيار براي ساخت يک برنامه کلاسي مناسب مواجه هستيم. اين محدوديتها به دو دسته محدوديت قوي (سخت) و ضعيف (نرم) تقسيم بندي ميشوند. محدوديتهاي قوي شرايطي هستندکه رعايتشان شرط لازم براي داشتن جداول صحيح وکاربردي است. محدوديتهاي ضعيف شرايط اضافي هستندکه رعايت انها به افزايش کارايي جداول زمانبندي ومطلوبيت انها کمک ميکند. در مسأله جدول زمانبندي دروس از مفاهيم زير استفاده ميشود.
روز و بازه زماني90 : در اين مسأله حداکثر تعداد روز تدريس در هفته را مشخص ميکنيم (که معمولا 5 يا 6 روز است). هرروز به بازه هاي زماني ثابتي تقسيم ميشود که معمولا بازه هاي 2 ساعتي است که به اين ترتيب معمولا هر روز به به 5 يا 6 بازه زماني تقسيم بندي ميشود.
درس و تدريس: در هر بازه زماني يک يا چند درس (در چندين کلاس) تدريس ميشود. تدريس هر درس به يک يا دو بازه زماني است (هر درس شامل 2 يا 4 ساعت تدريس است).
استاد: هر درس توسط استادي تدريس ميشود. هر استاد در يک بازه زماني فقط ميتواند در مکان تدريس کند.
کلاس: هر کلاس داراي ظرفيت و نوع خاصي است و اتاقهايي مجزا براي تدريسهاي عملي و آزمايشگاهي و تئوري و غيره پيش بيني شده است.
ترم و رشته تحصيلي: هر رشته تحصيلي در هر ترم داراي دروس مشخصي است که بايد تمامي آن دروس در جدول زمانبندي گنجانده شود به طوري که در يک بازه زماني در کلاس هاي مختلف دروس يک ترم تدريس نشود.
همانطورکه گفتيم ايجادجداول زمانبندي دروس عبارتست از: تخصيص منابع، اساتيد، دانشجويان وکلاس ها، به دروسي که دربازه هاي زماني ثابتي زمانبندي شدهاند، با رعايت محدوديتهاي قوي و حداکثر ممکن محدوديتهاي ضعيف.
برخي ازمحدوديتهاي قوي درزمانبندي دروس عبارتنداز:
1. هر استاد در هر دوره زماني فقط ميتواند يک تدريس داشته باشد.
2. کليه تدريس هاي در نظر گرفته شده بايد در جدول زمانبندي گنجانده شود.
3. اتاق هاي در نظر گرفته شده از نظر موضوع با تدريس منطبق باشد.
4 دروسي که استاد مشترک دارند نميتوانند همزمان ارائه شوند.
5 دروس همنياز که توسط گروه مشترکي از دانشجويان بايد اخذ شوند نبايد همزمان ارائه شوند.
6. دروسي که در يک ترم ارائه ميشود با توجه به چارت دروس دانشگاهي نبايد همزمان ارائه شوند.
موارد زير را به عنوان محدوديتهاي ضع
ي
ف ميتوان شمرد :
1. استادي ميتواند ساعت يا روزهاي خاصي را براي تدريس ترجيح بدهد (اجباري نيست).
2. بهتر است کليه کلاس ها در ساعات صبح يا عصر يا … تشکيل شود.
3. تعداد کلاس هاي استفاده شده حداقل باشد.
4. گنجايش کلاس در نظر گرفته شود.
5. تا حد امکان کلاس در نظر گرفته شده براي يک استاد، تغيير نکند.
و مباحثي از اين دست…
اين توصيف از يک مثال مسأله زمانبندي به وضوح نشان ميدهد که اين دسته از مسائل ميتوانند به عنوان يک مسأله ارضاء محدوديت فرموله شوند و متعاقبا به عنوان يک محک در اين حوزه مورد استفاده قرار گيرند.
زمانبندي کار91 : از آنجا که محيطهاي توليدي مدرن بسيار پيچيده است، ايجاد يک زمانبندي مناسب براي افراد امري دشوار و زمانبر است. از اينرو داشتن يک فرآيند زمانبندي که توسط يک سيستم کامپيوتر انجام شود بسيار مقرون به صرفه است. تلاشهاي تحقيقاتي زيادي تاکنون در اين زمينه صورت گرفته و متدهاي بسياري براي حل اين مسأله پيشنهاد شدهاند و از آنجايي که اين مسأله قابليت تبديل شدن به فرم يک مسأله CSP را داگرهت در بسياري از تحقيقات مربوط به اين حوزه به عنوان يک محک مهم مورد استفاده قرار گرفته است. به طور کلي اين مسأله شامل زمانبندي يک مجموعه از کارها بر روي يک مجموعه ماشين است. يک مسأله زمانبندي کار با سايز m×n شامل n کار92 و m ماشين است. براي هر کار Ji ، دنباله اي از m عمليات93 Oi=(oi,1 ,oi,2 , . . . ,oi,m ) ترتيب فرآيند عمليات Ji داده شده را توصيف ميکنند. هر فرآيند oi,j بر روي يک ماشين خاص پردازش ميشود و يک زمان پردازش i,j ? دارد. هر ماشين تنها يک فرآيند را در يک زمان ميتواند پردازش کند، هر کار نيز تنها يک فرآيند در حال پردازش در يک زمان دارد و ترتيب اجراي فرآيندها نيز مشخص است. به عبارتي بين هر دو فرآيند از يک کار يک رابطه پيش نيازي وجود دارد ولي بين هر دو فرآيند از کارهاي مختلف هيچگونه رابطه پيش نيازي وجود ندارد. به هر کاري براي پردازش بر روي يک ماشين، يک زمان پردازش و يک زمان آماده سازي که به کار قبلي پردازش شده بر روي آن ماشين وابسته است اختصاص مييابد. هر يک از کارها براي پردازش بر روي ماشينها داراي يک مسير پردازش مختص خود است که به وسيله توالي ماشينها مشخص ميشود و در واقع روابط پيش نيازي مابين فعاليتهاي آن را نشان ميدهد. يک راه حل براي يک JSP يک زمانبندي خاص است زماني که براي پردازش هريک ازفرآيندها، هيچ محدوديتي نقض نشود.
3-2-4- مسائل ارضاء محدوديت باينري94
اگر كليه محدوديتها باينري باشند (يعني متغيرها تنها بتوانند دو مقدار بگيرند)، CSPميتواند توسط گرافي نمايش داده شود كه در هر گره يك متغير را نشان مي دهد و اتصال بين دو گره محدوديت بين متغيرهاي متناظر را نشان ميدهد. شکل() يک مثال از مساله CSP را نشان ميدهد که داراي سه متغير x1, x2, x3 و محدوديتهاي x1x3 و x2x3 است.

شکل 3-4 مثالي از مساله CSP [4]
طراحي و پياده سازي برخي روشهاي پيشنهادي
استفاده از ترکيب الگوريتمهاي تکاملي95 و سيستمهاي چندعامله براي حل مسائل ارضاء محدوديت
يکي از تلاشهاي موفق براي حل مسائل ارضاء محدوديت استفاده از يک روش ترکيبي توسط ويکايي ژانگ و همکارانش است. اين الگوريتم اختصارا “MAEA-CSPs96 ” نام گرفت. براي پياده سازي اين روش ابتدا مسائل ارضاء محدوديت به دو گروه مسائل ارضاء محدوديت جايگشتي97 و مسائل ارضاء محدوديت غير جايگشتي98 تقيسم بندي شده اند. پس از آن چندين رفتار براي عاملها با استفاده از توانايي عاملها براي درک و عمل در محيط طراحي شده است ودر نهايت اين رفتارها با ابزارهاي تکاملي کنترل شده است، به طوري که نتيجه اش يک الگوريتم ترکيبي MAEA شده است. بخش اول آزمايشات از محکهاي رنگ آميزي گراف و مسائل ارضاء محدوديت باينري از مجموعه داده اي DIMACS Challenge براي تست کارايي MAEA-CSPs براي مسائل ارضاء محدوديت غير جايگشتي استفاده کرده است سپس اين روش با چند الگوريتم ديگر مقايسه شده است و تاثير پارامترها به صورت سيستماتيک آناليز شده است. بخش دوم آزمايشات از يک محک کلاسيک ديگر مسائل ارضاء محدوديت يعني n-وزير براي تست کارآيي مسائل ارضاء محدوديت جايگشتي استفاده کرده است. در MAEA-CSP تمامي عاملها در يک محيط شبکه مانند به صورت شکل زير زندگي ميکنند.

شکل 3-5 مدل فرض شده از محيط شبکه مانند عاملها [3]
هر دايره يک عامل را نشان ميدهد. داده درون دايره موقعيت عامل را درون شبکه مشخص ميکند و دو عامل ميتوانند با هم در تعامل باشند اگر و فقط اگر يک خط اتصال بين آنها باشد.
مکانيزمي که در اين روش براي استفاده از EA در نظرگرفته شده است تا حدودي با EA هاي سنتي متفاوت است. در EA هاي سنتي، آن دسته از افرادي99 که توليد فرزند خواهند کرد معمولا از بين تمام افراد بر اساس تابع برازش 100 اشان انتخاب ميشوند. بنابراين يک تابع توزيع عمومي101 از يک جمعيت بايد تعيين شود. اما در حالت طبيعي، يک انتخاب سراسري102 وجود ندارد و يک تابع توزيع عمومي هرگز نميتواند تعيين شود. در حقيقت يک انتخاب طبيعي واقعي تنها در يک محيط محلي اتفاق ميافتد و هر فرد تنها ميتواند با محيط اطرافش در تعامل باشد. به اين معني که، در هر مرحله، يک تکامل طبيعي تنها يک نوع از پديده هاي محلي است. اين اطلاعات ميتواند تنها پس از يک فرآيند انتشار به صورت جهاني به اشتراک گذاشته شود. در شبکه فوق، عاملها براي رسيدن به اهدافشان با يکديگر رقابت خواهند کرد به طوريکه هر عامل بتواند منابع بيشتري به دست آورد. از آنجا که هر عامل تنها محيط محلي خود را درک ميکند رفتارهاي ر
قابتي اش تنها ميتواند بين او و همسايگانش اتفاق بيفتد. هيچ انتخاب سراسري بين همه وجود ندارد، بنابراين يک تابع توزيع عمومي نياز نيست. يک عامل با همسايگانش در تعامل است، به طوريکه اطلاعات به آنها منتقل ميشود و به اينصورت اطلاعات به تدريج در کل شبکه منتشر ميشود. اين مدل از شبکه عاملها به مکانيزم تکامل واقعي در طبيعت نسبت به مدل يک جمعيت در EA هاي سنتي بسيار نزديکتر است.
با استفاده از رفتارهاي طراحي شده، عاملها در طول روند تعامل با محيط و ديگر عاملها، هر عامل تا حد ممکن انرژياش را افزايش ميدهد به طوريکه MAEA-CSP ميتواند راه حلها را بيابد. در اين روش عاملها به اين صورت تعريف ميشوند: يک عامل a يک عنصر در فضاي جستجوي S است با انرژي برابر با منفي تعداد محدوديتهاي نقض شده در مسأله.
هدف هر عامل ماکسيمايز کردن انرژي به وسيله رفتارهايي است که ميتواند از خود بروز دهد. واضح است که هرچه انرژي يک عامل بالاتر باشد آن عامل، عامل بهتري است. وقتي انرژي يک عامل به صفر افزايش مييابد آن عامل يک راه حل103 شده است. دامنه براي هر متغير متناهي و گسسته است، بنابراين اعضا ميتوانند با اعداد طبيعي شماره گذاري شوند. وقتي تمام دامنه ها به مجموعه اي از اعداد طبيعي منتقل شدند، راه حل هاي اغلب CSP ها ويژگيهاي خاصي به خود ميگيرند. بر اساس آنها، CSP ها ميتوانند به دو گروه تقسيم بندي شوند: فرض کنيد S مجموعه راه حل ها براي يک CSP باشد و تمام مجموعه دامنه ها به وسيله مجموعه اي از اعداد طبيعي ارائه شده باشند. حال اگر هر s ? S يک جايگشت104 از 1, 2, …, n باشد، CSP به عنوان يک مسائل ارضاء محدوديت جايگشتي تعريف ميشود در غير اينصورت به صورت يک مسائل ارضاء محدوديت غير جايگشتي. براي يک مسائل ارضاء محدوديت غير جايگشتي فضاي جستجو هنوز S است. از آنجايي که مسائل ارضاء محدوديت جايگشتي يک مورد خاص از مسائل ارضاء محدوديت غير جايگشتي است فضاي جستجو ميتواند براي اين حالت به مجموعه اي از تمام جايگشتهاي 1, 2, …, n کاهش پيدا کند.
وقتي از EA ها براي حل مسائل استفاده ميشود، فضاي جستجو بايد رمزگذاري105 شود به طوريکه افراد ميتوانند در يک شکل رمزگذاري يکنواخت106 ارائه شوند. به عنوان مثال GA ها معمولا فضاي جستجو را با استفاده از کد باينري رمزگذاري ميکنند، بنابراين هر فرد يک دنبالهاي از بيتهاست. براي مسائل ارضاء محدوديت جايگشتي طبيعي است که هر فرد را به صورت يک جايگشت از 1, 2, …, n ارائه دهيم. براي مسائل ارضاء محدوديت غير جايگشتي، روشي که بيشترين فابليت فهم را دارد يعني واضح ترين روش ارائه هرفرد به صورت يک عنصري از S است که اين توسط اکثريت الگوريتمهاي موجود استفاده ميشود. به عنوان مثال در [26] و [27]، هر فرد توسط يک جايگشت از متغيرها ارائه ميشود و جايگشت به وسيله يک رمزگشاي107 ساده به يک نمونه جزئي108 انتقال مييابد. اين رمزگشا متغيرها را به ترتيبي که در جايگشت آمدهاند در نظر ميگيرد و اولين مقدارممکن از دامنه را به آن متغير نسبت ميدهد. اگر هيچ مقداري بدون شناسايي يک تناقض ممکن نبود آن متغير بدون مقدار رها ميگردد. اين رمزگشا در واقع از يک الگوريتم حريصانه استفاده ميکند بنابراين با يک مسأله جدي روبرو هستيم و آن اين است که براي اغلب CSP ها اين رمزگشا نميتواند هر جايگشتي را به يک راه حل رمزگشايي کند. نتيجه اينک

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *