بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه روشی برای بهبود حل مسئله زمانبندی دروس دانشگاه با الگوریتم ژنتیک با
روش تغییر هوشمند ضریب جهش
Presented a method to improve the genetic algorithm to solve University Course Scheduling
Smart way of changing the mutation rate
چکیده
هدف از این پروژه یافتن راه حل های متفاوت برای مساله زمانبندی , خصوصا زمانبندی درس های دانشگاهی و زمانبندی امتحانات که امروزه یکی از مشکلات اساسی دانشگاههای کشور می باشد است .
تاکنون روش های متفاوتی برای حل این مساله ابداع شده است ,با افزایش رشته های گوناگون دانشگاهی و ارائه دروس مختلف در یک دانشگاه کار زمانبندی کلاس های درسی دشوار شده است .
در این تحقیق ما روش های متفاوت را برسی نموده و مشاهده کردیم که برای این کار فرمول خاصی وجود ندارد و نحوه کار یک امر تجربی است . در این مقاله انواع روش های قبلی مورد بررسی قرار گرفته و با استفاده از الگوریتم ژنتیک هوشمند با جهش اتوماتیک به حل مساله زمانبندی دانشگاه می پردازیم , و در پایان با استفاده از زبان برنامه نویسی سی شارپ با داده های واقعی از دانشگاه غیرانتفاعی شهرستان نهاوند و قیود مساله, مساله زمانبندی دانشگاه را طراحی و پیاده سازی نمودیم . این سیستم با توجه به داده های ورودی یک برنامه زمانبندی مناسب را تولید می کند و ممکن است بهترین برنامه نباشد ولی تمام شرایط لازم برای یک برنامه زمانبندی را رعایت می کند .
.
واژههای کلیدی: :زمانبندی دروس دانشگاه ; متا هیوریستیک ; الگوریتم ژنتیک ; الگوریتم سرد و گرم فلزات; الگوریتم های عقبگرد ;الگوریتم ممتیک
1
-1 مقدمه
طراحی جدول زمانبندی دروس دانشگاه امروزه یکی از مشکلات کارکنان آموزش دانشگاه می باشد . با گسترش رشته های تحصیلی و ثبت نام دانشجویان امروزه نیاز به یک برنامه که بتواند نیاز جامعه دانشگاهی کشور را برآورده نماید دیده می شود. مساله زمانبندی دروس دانشگاه جزو مسایل ارضای محدودیت در قلمرو هوش مصنوعی می باشد .
در این پایان نامه با استفاده از داده های واقعی دانشگاه غیر انتفاعی مرکز نهاوند و با الگوریتم ژنتیک برنامه زمانبندی دروس دانشگاه با زبان c# پیاده سازی شده است .
در این پیاده سازی تغییراتی در الگوریتم ژنتیک اساندار به وجود آمده است تا بتوان در مدت زمان کمتری از الگوریتم ژنتیک اساندارد بتوان به یک جدول بهینه خوش تعریف دست یافت .
و بر اساس نتایج بدست آمده از پیاده سازی برنامه توانسته تا حدودی بهتر از برنامـه ژنتیـک اسـتاندارد عمـل نمایـد . در الگـوریتم ژنتیک اساندارد بعد از گذر 1000 نسل توانسته به جواب نزدیک به بهین دست ژیدا نماید و در این پیاده سازی با توجـه بـه نتـایج بعد از گذر 600 نسل به یک جدول خوش تعریف که همه محدودیت های سخت و بیشتر محدودیت های نرم را بر طرف نماید.
-2 آشنایی با مساله زمانبندی
مساله زمانبندی مطابق زیر تعریف می شود : زمانبندی به صورت یک مساله واگذاری در نظر گرفته می شود که در آن n نفر را به m منبع در دسترس مثل زمان یا شغل یا مکان نسبت می دهیم,به طوری که به همه اهداف خود برسیم . یا نزدیک به هدف بهینه باشیم و همه محدودیت های مساله بر اثر این واگذاری تقریبا" برقرار شوند .
1-2 جدول زمانی Time Tabling
جدول زمانی TIME TABLING نشان دهنده این است که چه وقت ( در چه قطعه زمانی ) پیشامدهای بخصوصی می توانند رخ دهند. وقتی به اطراف خود نگاه می کنیم بسیاری از فعالیت ها نیاز به زمانبندی دارند و نتیجه آن را بوسیله یک جدول زمانی نشان می دهند .
2-2 محدودیت های مساله زمانبندی
در حالت کلی برای تهیه هر جدول زمانی دو نکته زیر باید رعایت شود : اول اینکه دو پیشامد در یک زمان و یک مکان خاص رخ دهد دوم اینکه منابع در دسترس برای سرویس دادن به همه پیشامدها در هر زمان باید کافی باشد.
به عبارت ساده تر مساله باید شدنی باشد. اما در مسائل دنیای واقعی مثل زمانبندی دروس دانشگاه تعداد محدودیت ها بیشتر از این می باشد , و حتی در هر دانشگاه بر اساس ضوابط و مقررات مربوط به هر دانشگاه این محدودیت ها ممکن است از یک دانشگاه به دانشگاه دیگر متفاوت باشد.
3-2 محدودیت های مساله جدول زمانی Time Tabling
محدودیت های مساله جدول زمانی به دو دسته تقسیم می شوند
1-3-2 محدودیت های سخت
برای شدنی بودن جدول زمانی در نظر گرفته می شوند . در واقع شرط لازم برای زمانبندی هستند . وجـود ایـن محـدودیت هـا در جدول زمانی باعث ابطال جدول زمانی می شود . به عنوان مثال قرار دادن دو درس متفاوت برای یک استاد در یک زمـان مشـخص یک محدودیت سخت محسوب می شود .
2-3-2 محدودیت های نرم
برای انعطاف پذیری و کیفیت بهتر جدول زمانی در نظر گرفته می شوند . یک جدول زمانی با کیفیت بالا یعنی جدولی کـه شـدنی باشد و کمترین تعداد عدم برقراری در محدودیت های نرم را تا حد قابل قبول داشته باشد . قابل قبول بـودن در اینجـا بسـتگی بـه نوع مساله و مقدار منابع در دسترس در مساله دارد .به عنوان مثال در برنامه زمانبندی دروس دانشگاه اگر در زمـان 12 تـا 2 ظهـر
2
برای استادی درس در نظر گرفته شده به علت نبود امکانات کلاسی در صورتی که دانشگاه بخشنامه داده که در این سـاعت کـلاس برگزار نشود یک محدودیت نرم اتفاق افتاده این محدودیت جدول زمانی را نامعتبر نمی کند ولی بهتر است از این محدودیت ها نیز دوری نماییم .
4-2 مساله زمانبندی کلاسهای دانشگاه
عمداتا" در دانشگاه دو نوع مساله زمانبندی داریم : زمانبندی برنامه کلاسی و زمانبندی برنامه امتحانی. ما در این مقاله به مساله زمانبندی برنامه کلاسی پرداخته ایم .
مساله زمان بندی کلاس های دانشگاه همواره یکی از مهمترین مسائل سیستم های آموزشی - دانشگاهی است . فرض کنید N درس داریم که باید برنامه ریزی شوند . برای هر درس M استاد درخواست تدریس داده اند و L کلاس در اختیار داریم . واضح است که برنامه را باید طوری تنظیم کرد که به بهترین نحو ممکن باشد . بدین معنی که بهینه برای دانشگاه , اساتید و دانشجویان باشد .
5-2 اهداف سیستم
اهداف یک سیستم زمانبندی دروس :
(1 ثبت درخواست های اساتید که شامل دروس برای تدریس و ساعات حضور ایشان برای تدریس می باشد .
(2 سرعت روند زمانبندی مساله : برنامه ریزی سنتی به روش دستی برای داده های زیاد از سرعت مطلوبی برخوردار نیست (3 کمک به مدیر در تنظیم برنامه (4 اعمال محدودیت های در نظر گرفته شده
(5 تنظیم برنامه بهینه و یا نزدیک به بهینه (6 ارائه گزارش برنامه
6-2 فرضیات مساله زمانبندی کلاس ها
فرضیات مساله زمانبندی کلاس ها در چهار گروه ساختار دروس ,انواع دروس ,منابع مورد نیاز و دوره های زمانی برای دروس مورد بررسی قرار می گیرد .
1-6-2 ساختار دروس دانشگاهی
دروس در دانشگاه بصورت تئوری ,عملی ,پژوهشی و یا به صورت ترکیبی از دروس تئوری و عملی ارائه می گردد . دروس تئوری توسط اساتید ارائه می شوند و در برنامه هفتگی متناسب با تعداد واحد های درس یک جلسه تا دو جلسه برای ارائه مورد نیاز است دروس پژوهشی , دروسی هستند که دانشجویان با حضور در کارگاه ها , آزمایشگاه ها و مراکز کامپیوتری و مراکز تربیت بدنی دروس را به صورت عملی می گذرانند . بعضی از دروس به صورت تئوری- عملی ارائه می شوند.
2-6-2 انواع دروس دانشگاهی
در بسیاری از دانشگا ها دروس به دو گروه , دروس اجباری و اختیاری تقسیم می گردند .
3-6-2 دسترسی به منابع
منابع مساله زمانبندی کلاس های درس دانشگاهی ,درس, اساتید و فضا های آموزشی است.
4-6-2 دوره های زمانی
دوره های زمانی یک روز , دوره های زمانی است که دروس در آن برنامه ریزی می شوند . ودر هر دوره زمانی یک ساعت و نیم , 15دقیقه برای استراحت و تعویض کلاس ها است .
7-2 محدودیت های مساله زمانبندی کلاس های درس
محدودیت های مساله زمانبندی دروس دانشگاه با توجه به قوانین و ضوابط دانشگاه متفاوت مـی باشـد کـه بـه چنـد نمونـه اشـاره میکنیم
1-7-2 تداخل
تداخل امکان پذیر نیست , چون در دسته محدودیت های سخت قرار می گیرد تداخل در موارد زیر پیش می آید
3
1-1-7-2 تداخل برنامه اساتید
در یک ساعت (دوره زمانی ) یک استاد بیش از یک درس داشته باشد.
2-1-7-2 تداخل برنامه دانشجویان
در یک ساعت ( دوره زمانی ) یک گروه از دانشجویان (به عنوان مثال دانشجویان سال دومی ) بیش از یک درس داشته باشند .
2-7-2 زمان های حضور اساتید
برنامه زمانبندی باید با توجه به زمان های که اساتید برای حضورشان به آموزش ارائه داده اند باشد.
3-7-2 زمانبندی کلاس های درس
زمانبندی کلاس های درس باید کامل باشد برنامه زمانبندی کلاس های درس زمانی کامل می باشـد کـه کلیـه دروس مـورد نیـاز کلیه گرایش ها در جدول زمانبندی موجود باشد و ساعات مورد نیاز هر درس در هفته برای آن تخصصی داده شود و اسـاتیدی کـه دروس را ارائه می دهند نیز مشخص شده باشند .
4-7-2 تعداد جلسات مورد نیاز در هفته
در جدول زمانبندی کلاس های درس باید تعداد جلسات مورد نیاز در هفته برای دروس و همچنین فاصله بین جلسات ارائه در نظر گرفته شود . به عنوان نمونه دروس 3 واحدی باید در دو جلسه یک ساعت و نیمه در هفته ارائه شود و نمـی تـوان آنهـا را در یـک جلسه 3 ساعته برنامه ریزی نمود و باید بصورت دو جلسه یک ساعت و نیمه در دو روز مختلف برنامه ریزی شوند .
5-7-2 وسایل و تجهیزات مورد نیاز
وسایل و تجهیزات مورد نیاز به منظور ارائه دروس فراهم باشددر ارائه بعضی از دروس نیاز بـه امکانـاتی از قبیـل ویـدیو پروجکشـن ,امکانات کامپیوتری و غیره است, لذا کلاسی که برای ارائه دروس در نظر گرفته می شود باید دارای این امکانات باشد .
6-7-2 ظرفیت کلاس
با توجه به تعداد دانشجویان ثبت نام شده در هر درس , کلاسی متناسب که امکان پذیرش آن تعداد دانشجو را دارد انتخاب گردد.
7-7-2 دروس از پیش زمانبندی شده
دروس از پیش زمانبندی شده باید در نظر گرفته شود دروسی که توسط سایر دانشکده ها بصورت دروس سرویس ارائه می گردنـد امکان تغییر در زمان بندی آنها وجود ندارد .
8-7-2 زمان های استفاده از کلاس ها
زمان های استفاده از کلاس ها در نظر گرفته شود در برنامه زمانبندی , زمان هایی که کلاس ها قابل استفاده هسـتند نیـز بایـد در نظر گرفته شود . در برخی از دانشگا ها کلاس ها بصورت مشترک در اختیار دانشکده های مختلف قرار می گیرند .
8-2 هیوریستیک
هیوریستیک ها عبارتند از معیارها ,روشها یا اصولی برای تصمیم گیری بین چند گزینه خط مشی و انتخاب اثربخش ترین برای دستیابی به اهداف مورد نظر .
9-2 انواع الگوریتم های هیوریستیک 1-9-2 الگوریتم هایی که بر هدایت هیوریستیک یک الگوریتم سازنده یا جستجوی محلی متمرکز می شوند
به گونه ای که آن الگوریتم بتواند بر شرایط حساس ( مانند فرار از بهینه محلی ) غلبه کند . به این الگوریتم ها متا هیوریستیک گفته می شود .
2-9-2 الگوریتم هایی که بر ترکیب یک چارچوب یا مفهوم هیوریستیک متمرکز می شوند
با گونه هایی از برنامه ریزی ریاضی ( معمولا روش های دقیق ) متمرکز می شوند . هیوریستیک های دارای یک مشکل اساسی هستند و آن گیر افتادن در بهینه های محلی می باشد .برای بهبود این الگوریتم ها نوعی جدید از الگوریتم ها معرفی شدند به نام
4
الگوریتم های متا هیوریستیک از بین این الگوریتم ها می توان : بازپخت شبیه سازی شده , جستجوی ممنوع , الگوریتم های ژنتیک , شبکه های عصبی, کلونی مورچه را نام ببرد .
- 3 پیشینه ی تحقیق
در چهل سال گذشته , تهیه جدول های زمان بندی یکی از زمینه های مهم پژوهشی بوده که به وسیله ی گروه های پژوهشی هوش مصنوعی و پژوهش عملیاتی مد نظر قرار گرفته شده است .
روش های مختلفی برای حل این مساله ارایه شده است . یکی از نخستین روش های حل این مسئله مدل سازی ریاضی است . در این روش مساله زمان بندی به صورت یک مدل برنامه ریزی خطی عدد صحیح مدل سازی می شود . اما بسیاری از پژوهشگران به دلیل زمان اجرای زیاد,از روش های دقیق چشم پوشی کرده اند و به سوی الگوریتم های ابتکاری روی آوردند .
الگوریتم های اولیه که برای حل مساله جدول زمانی به کار گرفته شدند عبارت بودن از : الگوریتم های عقبگرد و الگوریتم رنگ آمیزی گراف . در استفاده از الگوریتم رنگ آمیزی گراف برای حل مساله زمانبندی هر گره به یک بازه و هر رنگ به یک استاد اشاره دارد[2] .الگوریتم های اکتشافی [3] و الگوریتم های عقبگرد [4] با استفاده از ایجاد فضای مساله سعی در پیدا کردن بهترین جواب می کنند ولی این الگوریتم ها به علت بزرگ بودن فضای حالت مساله فاقد کارایی می باشند .
پس از این مرحله به کارگیری الگوریتم شبیه سازی ذوب فلزات و الگوریتم جستجوی تابو برای حل مساله جدول زمانبندی .مطرح شدند . الگوریتم جستجوی تابو نوعی جستجوی محلی حافظه دار است که در هر حرکت در فضا مساله بهترین همسایه را ذخیره می کند . [6] ولی این دو نیز فاقد قابلیت کافی برای حل مساله مورد نظر بودند و دلیل آن عدم جستجوی موازی مانند الگوریتم پرتو محلی بود . در واقع این دو الگوریتم فقط قابلیت کار بر روی یک جدول زمانی را در هر اجرا داشتند . البته اخیرا" از نوعی الگوریتم جستجوی تابو [7,8] با قابلیت پردازش موازی استفاده شده است که از نظر کیفیت جواب تقریبا" با الگوریتم ژنتیک برابری می کند . امروزه عمده تحقیقات برای حل مساله جدول زمانبندی بر روی الگوریتم ژنتیک , الگوریتم ممتیک , ابر الگوریتم های اکتشافی و برنامه سازی منطق محدودیت ها می باشند . الگوریتم ممتیک که از جدیدترین الگوریتم های جستجو می باشد حاصل ترکیب جستجوی محلی و الگوریتم ژنتیک می باشد. . [9] ابر الگوریتم اکتشافی حاصل ادغام چندین الگوریتم جستجوی متفاوت و هیوریستیک مناسب است . [10] برنامه سازی منطق محدودیت ها از منطق مرتبه اول استفاده می نماید . . [11] الگوریتم ژنتیک نیز از روشهای مناسب و پرکاربرد برای حل مساله جدول بندی زمانی می باشد . [12,13,16] در واقع این چهار الگوریتم جزو قویترین و مناسب ترین الگوریتم ها برای حل مساله جدول بندی زمانی به شمار می روند .
- 4 الگوریتم ژنتیک
مقوله ژنتیک با انتشار کتاب چارلز داروین که در آن نظریه تکاملی خود را مطرح کرده بود در سال 1859 مطرح شد . الگوریتم ژنتیک به روش الهام گرفته از طبیعت جاندار است که می توان از ان به عنوان یک روش عددی , جستجوی مستقیم و
تصادفی معرفی کرد.الگوریتمی مبتنی بر تکرار که در کاربرد های بسیاری مثل پردازش تصویر,مسایل ترکیبی و .. به کار برده می شود .الگوریتم ژنتیک به عنوان بک الگوریتم یک الگوریتم محاسباتی بهینه سازی , با در نظر گرفتن مجموعه ای از نقاط فضای جواب در هر تکرار محاسباتی , بنحو موثری نواحی مختلف فضای جواب را جستجو می کند .
1-4 حل مساله جدول بندی دروس دانشگاه با الگوریتم ژنتیک
مساله زمانبندی دروس دانشگاه دارای ورودی های :
· لیست دروس اصلی و آزمایشگاهی دانشکده
· لیست کلاس هی درس و آزمایشگا ه های موجود در دانشکده
· لیست اساتید
خروجی های مساله :
جدول بهینه سازی برنامه ریزی دروس
پارامتر های :
• اندازه جمعیت
• طول کروموزوم
• حداکثر تعداد نسل
• احتمال عملگر ترکیب
• احتمال عملگر جهش
اندازه جمعیت ژنتیکی معمولا , 1000 و طول کروموزوم از رابطه
بدست می آید که در آن H تعداد کل بازه های زمانی یک ساعتی در یک هفته و C تعداد کلاس ها , A تعداد آزمایشگاه ها می باشد . [17] حداکثر تعداد نسل از رابطه
بدست می آید . در این پیاده سازی حداکثر تعداد نسل و شرط توقف به صورت دستی متوقف می شود . از طریق کلیک روی دکمه توقف برنامه .مهمترین قسمت برنامه زمانبندی کد کردن کروموزوم برنامه می شود ,در این پایان نامه هر کروموزوم یک آرایه دو بعدی فرض شده است که ستو نهای آن بازه های زمانی یک ساعته و سطر های آن را کلاس ها تشکیل می دهند [17].
شکل((1 نمایش ساختار کروموزوم برای جدول زمانبندی
6
شکل (2) نمایش کروموزوم به صورت آرایه دو بعدی
2-4 روش کد کردن کروموزوم
برای کد کردن کروموزوم ها در بانک اطلاعاتی برای روز شنبه , E1 یک شنبه , E2 دوشنبه , E3 سه شنبه , E4 چهارشنبه ,E5 و پنج شنبه E6 در نظر گرفته شده است و روز های هفته به بازه های زمانی 1 ساعته تقسیم می شوند برای نمونه
شنبه به کد های
E11-E12-E13-E14-E15-E16-E17-E18
تبدیل می شوند که به این معنی می باشند : E11 روز شنبه ساعت 8 تا 10
E12 روز شنبه ساعت 10 تا 12
E13 روز شنبه ساعت 12 تا 2
E14 روز شنبه ساعت 2 تا 4
E15 روز شنبه ساعت 4 تا 6
و به این شکل روزهای دیگر هفته در کروموزوم کد می شوند [1]
