بخشی از مقاله
چکیده
مسئله زمانبندی دروس دانشگاه یک مسئله بهینه سازی ترکیبی می باشد که در آن مجموعه ای از رویدادها باید در بازه های زمانی موجود زمانبندی شده و در کلاس های مناسب جایدهی شود، ضمن اینکه مجموعه ای از محدودیت های سخت و نرم نیز رعایت می شوند. تهیه چنین جدول زمانبندی برای موسسه های آموزشی کاری بسیار دشوار و زمانبر می باشد زیرا در رده مسائل NP-Hard قرار می گیرد.
کار صورت گرفته در این تحقیق تلاش دارد بجای استفاده از یک جمعیت اولیه و انجام مراحل الگوریتم ژنتیک بر روی آن، جمعیتهای متفاوتی ایجاد نماید که بطور همزمان مورد تحلیل قرار می گیرند. ساختار کروموزم در تمامی این جمعیتها یکسان است، اما هر جمعیت میتواند مراحل انتخاب، تکثیر و جهش خاص خود را داشته باشند. پس از گذشت چند نسل، توسط الگوریتمهای نخبهگرا به تبادل کروموزم بین آنها میپردازیم. با اضافه کردن معیار فاصله تا امکانپذیر بودن راه حل، جمعیت های اولیه با کارایی بالاتری ایجاد می کنیم. در نهایت با اضافه کردن جستجو محلی به خروجی الگوریتم ژنتیک باعث بهبود راه حل های ایجاد شده می شویم. نتایج ارزیابی روی مجموعه داده BenPaechter نشان می دهد روش پیشنهادی عملکرد بالاتری نسبت به سایر روش های مشابه دارد.
-1 مقدمه
فرآیند برنامهریزی و زمانبندی دروس در دانشگاه ها فرآیندی چند مرحلهای است، که انجام آن نیازمند همکاری و ارتباط مناسب چند گروه برنامهریزی میباشد. این گروه ها شامل اساتید دانشگاه، مدیران گروهها، مسئول آموزش و مسئول برنامهریزی اتاق ها میباشد. این فرآیند در مراحل اولیه با تعیین منابع قابل برنامهریزی ترم شامل زمان های آزاد و در اختیار اساتید، دروس قابل ارائه ترم و اتاق ها و آزمایشگاه ها و سایر اماکن برگزاری دروس شروع میشود.
همراه با تعیین منابع، شرایط و قیدهای استفاده از منابع نیز بطور ضمنی و یا صریح مشخص میشوند. در مرحله بعد، با توجه به منابع و شرایط استفاده از آنها و همچنین قیدهای کلی تعیین شده، کلاسبندی دروس آغاز شده و استاد، درس، زمان و محل تشکیل هر کلاس تعیین میشود. با پیشرفت این مرحله به دلیل نیاز به حضور ذهن و بخاطر داشتن کلاسبندی های انجام شده، ادامه برنامهریزی و زمانبندی دشوارتر میگردد. علاوه بر این، بعد از انجام برنامهریزی و زمانبندی اولیه، نیاز به اعمال تغییرات اجتناب ناپذیر است که این امر باعث افزایش پیچیدگی زمانبندی میگردد.
لذا توجه به شرایط و توزیع دانشجویان در ورودی های مختلف و دروس گذرانده شده هر گروه، جهت برنامهریزی و زمانبندی صحیح و مناسب و همچنین استفاده بهینه و ماکسیمم از ظرفیت کلاس ها بسیار حائز اهمیت است. مسئله جداول زمانی، به فرایند تخصیص منابع محدود، به تعدادی رویداد، با شرط ارضا تعداد زیادی محدودیت اشاره مینماید. این محدودیتها به دو گروه سخت و نرم تقسیم می شوند.
محدودیتهای سخت به قواعدی اشاره می نماید که رعایت آنها الزامیست و شدنی بودن جوابها را تضمین می نماید. اما قیود نرم محدودیتهایی را شامل می شود که با کیفیت جواب ارائه شده رابطه مستقیم دارد. محدودیتهای سخت بر خلاف محدودیت های نرم در هیچ حالتی نباید نقض شوند. به راه حلی که بتواند هر رویداد را به یک بازه زمانی، به نحوی اختصاص دهد که تمام محدودیتهای سخت ارضا شوند، راه حل عملی مسئله جداول زمانی گفته میشود. الزامی برای ارضا محدودیتهای نرم وجود ندارد، اما کیفیت جداول زمانبندی با افزایش محدودیتهای نرم ارضاء شده، افزایش مییابد. در این تحقیق سعی نمودهایم با ایجاد تغییرات در برخی مراحل الگوریتم ژنتیک و انتخاب روشهای متناسب با مسئله جداول زمانی، کارایی روش مورد نظر را افزایش دهیم.
-2 روش های حل مسئله زمانبندی دروس
مسأله جدول زمانبندی دروس در اصل، شامل تخصیص دروس هفتگی به بازه های زمانی و اتاق های برگزاری کلاس ها است. اگر شروطی مانند عدم تخصیص یک کلاس در یک ساعت به چند درس، یا عدم تلاقی زمانی در دروس یک استاد را به مسأله اضافه کنیم، مشخص می شود که مسأله طراحی جداول زمان بندی، میتواند یک مسأله ارضای محدودیت - CSP - 1 قلمداد شود. روش های متعددی برای حل این نوع مسائل به کار گرفته شده که برخی از آنها عبارتند از: الگوریتم رنگ آمیزی گراف ، استفاده از توابع هیوریستیک و روش های جمعیت گرا یا تکاملی. در روش های جمعیت گرا که یکی از محبوب ترین روش های حل مسئله زمانبندی است از ایده های تکاملی و بهبود جمعیتی استفاده میشود.
الگوریتم مورد استفاده در پروژه حاضر، الگوریتم ژنتیک بوده که یکی از قوی ترین و پرکاربردترین الگوریتم ها در مسائل بهینه سازی است . - Rohini et al, 2016 - یکی از دلایل محبوبیت الگوریتم های ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته می باشد. از کارهای انجام شده در این زمینه میتوان به موارد متعدد اشاره نمود. در - Burke ea al ,1994 - الگوریتم ژنتیکی پیشنهاد شد که تنها روی بازه های زمانی قابل قبول اعمال می شد و به طور تعاملی با کاربر در ارتباط بود. در - Doria et al, 2004 - روشی مبتنی بر الگوریتم های ممتیک همراه با یک جستجوی محلی موثر ارائه شد که بر روی داده های اولین مسابقه جدول زمانبندی در سال 1994 اعمال شد. در - Pillay and Banzhaf, 2010 - از یک الگوریتم ژنتیک هوشمند برای طراحی جداول زمانبندی امتحانات سود برده اند.
دیدگاه آنان یک دیدگاه دو مرحله ای بوده است که در مرحله اول محدودیت های سخت و در مرحله دوم محدودیت های نرم به چالش کشیده می شوند. در این تحقیق به طور خاص مزایای الگوریتم ژنتیک آشکار شده و نتایج امیدوار کنندهای از آن گزارش شده است. در سال 2007 گامی و همکارانش یک الگوریتم ژنتیک را برای حل مسئله برنامه ریزی ترمی دانشگاهی به کار گرفتند. هدف اصلی این تحقیق کاهش تعداد تداخلات است که برای تحقق این هدف از دو رویکرد الگوریتم ژنتیک اصلاح شده و الگوریتم ژنتیکی مشارکتی بهره گرفته اند .[2] در تحقیقی دیگر یک الگوریتم ژنتیک با راهبرد استراتژی جستجو و یک تکنیک جستجوی محلی برای حل مسئله جدول زمانی دروس دانشگاه پیشنهاد دادند.
راهبرد استراتژی جستجو در ایجاد فرزند مورد استفاده قرار می گیرد. در انتها نیز یک روش جستجوی محلی به منظور بهبود کیفیت راه حل ها و کارایی بالاتر استفاده می شود .[3] در [4] بر اساس رویدادها و با گروه بندی دانشجویان به حل این مسئله زمانبندی دروس دانشگاه پرداختند. این روش از ترکیب الگوریتم ژنتیک با جستجوی محلی سعی در گروه بندی دانشجویان در رویدادهای امکان پذیر و امکان ناپذیر دارد. حامد بابایی ایده دسته بندی رهیافت های تحقیق در عملیات جهت حل مسئله ی جدول زمان بندی دروس دانشگاه را مطرح ساخت. این تحقیق در سه کلاس تکنیک مبتنی بر تئوری رنگ آمیزی گراف، متد IP/LP و تکنیک مبتنی بر قید انجام شده است.
[5] یک مطالعه مقایسه ای بین الگوریتم ژنتیک، الگوریتم شبیه سازی آنیلینگ و یک الگوریتم ترکیبی ژنتیک و آنیلینگ به منظور حل مسئه زمانبندی دروس دانشگاه در [6] انجام شد. در روش ترکیبی از الگوریتم ژنتیک برای ساخت جمعیت اولیه، در شبیه سازی آنیلینگ استفاده شده است. نتایج عملی برتری روش ترکیبی را نشان می دهد. در تحقیقی دیگر از یک مدل بهبود یافته الگوریتم ژنتیک موازی بافت ضخیم - CGPGA - به منظور حل این مسئه استفاده می شود.
ایده اصلی این روش بر روی پلت فرم محاسبات ابری با هادوپ انجام گرفته و از مدل برنامه نویسی Map/Reduce بهره می گیرد. خواننده برای مطالعه بیشتر می تواند به [7] مراجعه کند. کومار از متد AHP به منظور حل این مسئله استفاده کرده است. این روش در واقع یک فرایند تحلیل سلسله مراتبی دو مرحله ای است و به تازگی ارائه شده است. این متد بیشتر به منظور حل مسائل چند هدفه غیر خطی استفاده می شود.[8]
-3 داده های زمانبندی دروس دانشگاه
در این تحقیق از مجموعه داده BenPaechter که یکی از معروف ترین مجموعه داده ها در زمینه زمانبندی دروس دانشگاه است، برای انجام آزمایشات استفاده شده است. این مجموعه داده در سال 2005 توسط بن پاچتر و همکارانش تولید شده است و از «http://code.ulb.ac.be» قابل دسترس است. مجموعه داده BenPaechter از 12 نمونه در سه اندازه کوچک، متوسط و بزرگ تشکیل شده است. در جدول 1 مشخصات نمونه های این مجموعه داده را مشاهده می کنید.
الگوریتم ژنتیک پیشنهادی :
ورودی : یک نمونه از مجموعه داده BenPaechter
- مقداردهی پارامترهای الگوریتم }تعداد اعضای جمعیت - - NP، نرخ آمیزش - - Pc، نرخ جهش - - Pm، تعداد جمعیت ها - - Mp، تعداد تکرار جستجو محلی - - N_LS، تعداد نسل ها - .{ - G خروجی : زمان و شماره اتاق مربوط به هر رویداد
- به تعداد Mp مراحل زیر به صورت موازی و مجزا انجام شود.
- به تعداد NP کروموزوم به صورت تصادفی-هیوریستیکی تولید شود.
- مقدار برازندگی کروموزوم های تولید شده به صورت موازی محاسبه شود. -3 به تعداد G مراحل زیر تکرار شود :
- با توجه به اپراتور چرخ رولت دو والد - کروموزوم - انتخاب شود. -2 با توجه به اپراتورهای آمیزش معرفی شده سه فرزند تولید شود.
- اپراتور بهبود روی سه فرزند تولید شده اعمال و برازندگی آنها محاسبه شود. -4 اپراتور جهش به ازای هر فرزند تولید شده به صورت زیر اعمال شود :
- اگر مقدار فرزند صفر باشد، سه اپراتور جهش به ترتیب و به احتمال Pm اعمال می شوند.
- در غیر این صورت به احتمال Pm دو اپراتور جهش محلی و فرامحلی فقط به ازای رویدادهای تخصیص داده نشده اعمال می شود و اپراتور جهش مبادله بدون در نظر گرفتن احتمال اعمال می شود.
- مشخص کردن جمعیت نسل بعد با توجه به سه فرزند تولید شده -6 تعیین بهترین کروموزوم در بین تمامی Mp ها
- اعمال الگوریتم جستجوی محلی به تعداد تکرار N_LS روی بهترین کروموزوم تولید شده
-4 روش پیشنهادی
در این تحقیق رویکرد نوینی برای برنامه ریزی دروس هفتگی دانشگاه مطابق با شکل 1 ارائه می شود. روش انتخابی در این پژوهش، الگوریتم ژنتیک است که به علت بررسی هم زمان چندین جواب و پیمایش تصادفی فضای حالت، مناسب این مسأله می باشد. پس از اعمال الگوریتم ژنتیک استاندارد بر نمونه های مختلف و بررسی جواب ها، این نتیجه حاصل شد که این روش به علت جستجوی تصادفی در تمامی فضای حالت - که بسیاری از این حالات، محدودیت های سخت را نیز نقض می کنند - ، نیازمند بهبود است. در نتیجه با انجام اصلاحاتی در این الگوریتم، نظیر اعمال ترمیم بر روی فرزندان، هوشمند کردن عملگرها و استفاده از ساختار موازی رویکرد نوینی برای حل این مسئله ایجاد شد. در ادامه مراحل الگوریتم پیشنهادی را بیان می کنیم.
1؛-4 ارائه شکل جواب
طول کروموزوم در مسئله زمانبندی دروس دانشگاه به تعداد رویدادها مرتبط است. از طرفی هر رویداد شامل دو ژن با مشخصه های سانس - زمان رویداد - و شماره اتاق می باشد. مقادیر شماره اتاق با توجه به تعداد اتاق های نمونه ورودی تعیین می شود. سانس کلاس با توجه به استاندارد BenPaechter دارای مقادیری بین 1 تا 45 - هر روز 9 ساعت - در 5 روز باشد. نمونه ای از کروموزوم پیشنهادی را در شکل 2 مشاهده می کنید.
2؛-4 ایجاد جمعیت اولیه
ما در این تحقیق کروموزم ها را به صورت هیوریستیکی از فضای جستجو انتخاب می کنیم. تولید تصادفی جمعیت اولیه در مسئله های دارای محدودیت، منجر به تولید کروموزوم های غیر قابل قبول می شود. دلیل این امر عدم وجود هیچ پیش شرطی برای تولید و جلوگیری از بروز تناقضات است. در ادامه روش ارائه شده برای تولید جمعیت اولیه را شرح می دهیم.
گام : 1 ایجاد کل حالات انتخابی برای یک کروموزوم؛ در ابتدا کل حالت های انتخابی برای یک ژن از کروموزوم با توجه به سانس های کلاس و تعداد اتاق ها مشخص می شود. به عنوان مثال اگر تعداد سانس برای یک جدول زمانبندی 5 و تعداد اتاق ها 3 باشد، تعداد کل حالات برابر - 5×3 - 15 خواهد بود. برای درک بهتر این موضوع جدول 21 را مشاهده کنید. هر حالت از این شکل در واقع یک ژن از کروموزوم است که میتوان به یک رویداد نسبت داده شود.
گام : 2 درهم ریختن 2حالات انتخاب؛ برای انتخاب کروموزوم ها از کل فضای جستجو و جلوگیری از تولید کروموزوم های تکراری فضای حالات ایجاد شده در گام اول را برای تولید هر کروموزوم درهم میریزیم.
گام : 3 یافتن بهترین حالت برای رویدادها؛ برای تولید کروموزوم باید زیرمجموعه ای به تعداد رویدادها از کل حالات تولید شده انتخاب شود. برای هر رویداد یک حالت انتخاب می شود. برای هر رویداد اولین حالتی که انتخاب آن باعث ایجاد محدودیت های سخت برای کروموزوم نمی شود را بعنوان مشخصات آن رویداد در نظر می گیریم. سپس حالت انتخابی از کل فضای حالات حذف شده تا برای رویداد های دیگر استفاده نشود. برای رویدادهایی که هیچ حالتی برای آنها یافت نمی شود، عدد -1 قرار می دهیم. این ساختار باعث ایجاد کروموزوم هایی بدون محدودیت سخت خواهد شد.
3؛-4 ارزیابی جدول زمانبندی
در مسئله زمانبندی دروس دانشگاه، معیار ارزیابی نقض محدودیت های مسئله می باشد. تابع ارزیابی با بررسی محدودیت های سخت و نرم مسئله، مقدار نقض هر یک را محاسبه و براساس آن میزان برازندگی کروموزوم را تعیین می کند. برای هر یک از محدودیت ها وزنی مشخص می شود که بیان کننده میزان اهمیت هر یک می باشد.
