Get a site

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

 

پایان نامه کارشناسی ارشد دانشکده علوم انسانی  

گروه مدیریت

 عنوان:

مدل­سازی دومرحله­ای با الگوریتم ژنتیک برای حل مسئله برنامه ­ریزی دروس دانشگاهی(مورد مطالعه: دانشکده علوم انسانی دانشگاه علم و هنر یزد)

استاد مشاور:

دکتر علیرضا ناصر صدرآبادی

مهرماه ۱۳۹۲

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

چکیده:

مسئله­های زمان­بندی و برنامه ­ریزی، سازگارسازی و هماهنگ کردن مجموعه ­ای از نهادها مانند رخدادها، فعالیت­ها، افراد، ابزار و دستگاه­ها، خودروها، مکان­ها و مانند این­ها در یک الگوی مکان- زمان است. در این دسته از مسئله­ها هدف این است که منابع در دسترس به بهترین روش ممکن مورد بهره ­برداری قرار گیرند و محدودیت­ها و شرایط موجود مورد توجه قرار گرفته و برآورده شوند.

بنابراین، لزوم در نظر گرفتن متغیر­های متناظر با دروس، اساتید، کلاس­ها، روزهای هفته و ساعات قابل برنامه ­ریزی در روز سبب می­شود که با یک مسئله­ برنامه ­ریزی ریاضی از نوع برنامه ­ریزی غیر­خطی با اعداد صحیح و با ابعاد بزرگ مواجه باشیم­که­حتی نرم­افزار­های قوی نیز نمی­توانند آن را در زمان کم حل کنند، بنابراین الگوریتم­های فرا­ابتکاری مورد توجه قرار گرفته­اند که بتوانند مسائل بهینه­سازی با ابعاد بزرگ را با زمان اجرای مناسب تا حدودی حل کنند. مبنای اجرای تحقیق حاضر، حل مسئله زمان­بندی با بهره گرفتن از تکنیک الگوریتم ژنتیک و استفاده از نرم­افزار MATLAB قرار داده شده، به صورتی که با توجه به رعایت تمام محدودیت­های مدل طراحی شده،­ برای هر درس، رشته­هایی حاوی بازه­های زمانی، تولید شده و با جریمه هر سلول درصورتی که محدودیت­ها را رعایت نکنند، تابع برازندگی برای این کروموزوم­ها محاسبه می­شود، از مزیت­های این تکنیک روش آزمون و خطا برای تغییر عملگرهای ژنتیکی است که با جستجو در فضای حل وسیع­تری به طور تصادفی با توجه به مقدار تابع برازنگی بهترین جواب­ها را در زمانی نسبتاً کوتاه تولید می­ کند. در نهایت برای چهار گروه مقطع کارشناسی ارشد دانشکده علوم­انسانی دانشگاه علم و هنر یزد، با فرض عدم محدودیت تعداد کلاس­ها، جداول زمانی دروس دانشگاهی به تفکیک آورده شده است.

کلمات کلیدی: مدل زمان­بندی دروس دانشگاهی- ترجیحات اساتید- الگوریتم ژنتیک- محدودیت سخت- محدودیت نرم

فهرست مطالب

عنوان                                                                                                                                صفحه

فصل اول: کلیات. ۱

۱-۱- مقدمه ۲

۱-۲- بیان موضوع . ۳

۱-۳- اهمیت و ضرورت تحقیق . ۴

۱-۴- تعریف مسئله ۵

۱-۵- اهداف تحقیق ۶

۱-۶- سؤالات اساسی تحقیق ۶

۱-۷- قلمرو تحقیق . ۶

۱-۸- روش انجام تحقیق . ۷

۱-۹- موارد کاربرد تحقیق . ۹

۱-۱۰- شرح اصطلاحات و واژه­های به کار­گرفته در تحقیق . ۹

۱-۱۱- محدودیت­های تحقیق ۱۰

۱-۱۲- خلاصه و جمع­بندی . ۱۰

فصل دوم: ادبیات تحقیق. ۱۱

۲-۱-  مقدمه. ۱۲

۲-۲-  تعاریف و مبانی نظری . ۱۳

۲-۲-۱- برنامه ­ریزی دروس دانشگاهی . ۱۳

۲-۲-۲- مسائل NP-complete  . ۱۵

۲-۲-۳- روش­های بهینه­سازی. ۱۷

۲-۲-۳-۱-روش­های ریاضی(دقیق) . ۱۷

۲-۲-۳-۲- روش­های تقریبی . ۱۸

۲-۲-۴- معرفی الگوریتم ژنتیک ۲۱

۲-۲-۴-۱- انواع الگوریتم­های ژنتیکی. ۳۰

۲-۲-۴-۲- مزایای الگوریتم­های ژنتیکی. ۳۱

۲-۲-۴-۳- محدودیت­های الگوریتم­های ژنتیکی . ۳۲

۲-۲-۴-۴- استراتژی­های برخورد با محدودیت­های ژنتیکی . ۳۳

۲-۲-۴-۵- بهبود الگوریتم­های ژنتیکی ۳۴

۲-۲-۴-۶- چند نمونه از کاربردهای الگوریتم­های ژنتیکی ۳۴

۲-۳- پیشینه تحقیق ۳۵

۲-۳-۱-مروری بر تاریخچه ۳۵

۲-۳-۲- مطالعات داخلی ۳۷

۲-۳-۳- مطالعات خارجی ۴۴

۲-۴- خلاصه و جمع­بندی ۵۵

فصل سوم: روش تحقیق . ۵۶

۳-۱- مقدمه . ۵۷

۳-۲-روش تحقیق . ۵۷

۳-۳- نوآوری­های تحقیق. ۵۸

۳-۴- جامعه و نمونه آماری. ۵۸

۳-۵- اطلاعات کلی مورد نیاز در مسائل برنامه ­ریزی دروس دانشگاهی ۵۹

۳-۶- معرفی محدودیت­های سخت و نرم در مسائل بهینه­سازی ۶۰

۳-۷- مفروضات کلی مسائل برنامه ­ریزی دروس دانشگاهی . ۶۱

۳-۸- تعریف کلی مسئله برنامه ­ریزی دروس دانشگاهی ۶۳

۳-۹- تعریف مدل پیشنهادی مسئله برنامه ­ریزی دروس دانشگاهی  . ۶۵

۳-۱۰- روش­های حل مدل پیشنهادی مسئله برنامه ­ریزی دروس دانشگاهی ۶۸

۳-۱۰-۱- الگوریتم­های ژنتیک . ۶۸

۳-۱۰-۲- شبه کد الگوریتم در مدل پیشنهادی ۶۹

۳ -۱۰-۳- تابع برازندگی و عملگرهای ژنتیکی ۷۱

۳-۱۱- معرفی نرم افزار ۷۲

۳-۱۲-خلاصه و جمع­بندی ۷۲

فصل چهارم: تجزیه و تحلیل داده­ ها . ۷۳

۴-۱- مقدمه. ۷۴

۴-۲- بیان مسئله ۷۴

۴-۳- نمایش ریاضی مدل پیشنهادی مسئله برنامه ­ریزی دروس دانشگاهی . ۷۵

۴-۳-۱-تابع هدف مدل اول    ۷۵

۴-۳-۲- محدودیت­های مدل اول ۷۷

۴-۳-۳- مدل دوم ۸۱

۴-۴- نتایج حل مدل پیشنهادی مسئله برنامه ­ریزی دروس دانشگاهی . ۸۳

۴-۵- خلاصه و جمع­بندی . ۱۰۲

فصل پنجم: نتیجه گیری و پیشنهاد­ها ۱۰۳

۵-۱- مقدمه ۱۰۴

۵-۲- نتیجه ­گیری. ۱۰۴

۵-۳- پیشنهاد­­ها ۱۰۷

۵ -۳- ۱- پیشنهاد­های کاربردی ۱۰۷

۵-۳- ۲- پیشنهاد­ها برای تحقیقات آتی ۱۰۸

پیوست­ها . ۱۰۹

پیوست (الف)- جدول ترجیحات اساتید. ۱۱۰

پیوست (ب)- کد نوشته شده در نرم­افزار، برای گروهی با همه محدودیت­ها. ۱۱۱

 فهرست مراجع ۱۱۷

مقدمه

مسئله­های زمان­بندی و برنامه ­ریزی، سازگارسازی و هماهنگ نمودن مجموعه ­ای از نهاد­ها مانند رخدادها، فعالیت­ها، افراد، ابزار و دستگاه­ها، خودروها، مکان­ها و مانند این­ها در یک الگوی مکان- زمان است. در این دسته از مسئله­ها هدف این است که منابع در دسترس به بهترین روش ممکن مورد بهره ­برداری قرار گیرند و محدودیت­ها و شرایط موجود مورد توجه قرار گرفته و برآورده شوند (مسعودیان و استکی، ۱۳۸۸). مسائل زمان­بندی ماهیتاً مسائل پویایی بوده و لحاظ نمودن انواع انعطاف پذیری­ها منجر به رفع مشکلات گلوگاهی، بهبود عملکرد سیستم و ایجاد مزیت رقابتی می­شوند (نهاوندی و عباسیان، ۱۳۸۹). زمان­بندی کلاس­ها در سطح دانشگاه بسیار پیچیده است، این بدان علت است که در زمان­بندی کلاس­های دانشگاه، عامل­های زیادی اثرگذار هستند و شمار و انواع زیادی از محدودیت­ها نیز باید برآورده شوند (بابایی زاده، ۱۳۹۰).

در این مسئله­ها سعی بر این است که مجموعه ­ای از منابع معین، متشکل از کلاس­ها، اساتید دروس تحت شرایط خاص به مجموعه ­ای از ساعت­های درسی اختصاص یابد. بنابراین، لزوم در نظر گرفتن متغیر­های متناظر با دروس، اساتید، کلاس­ها، روزهای هفته و ساعات قابل برنامه ­ریزی در روز سبب می­شود که با یک مسئله برنامه ­ریزی ریاضی از نوع برنامه ­ریزی غیر­خطی صفر و یک مواجه باشیم که حتی نرم افزار­های قوی نیز نمی­توانند آن را در زمان کم حل کنند، بنابراین الگوریتم­های فراابتکاری مورد توجه قرار گرفته­اند که بتوانند مسائل بهینه­سازی با ابعاد بزرگ را با زمان اجرای مناسب تا حدودی حل کنند (خلیلی و منصورزاده، ۱۳۸۵).

از میان الگوریتم­های فرا­ابتکاری الگوریتم ژنتیک یکی از قوی­ترین و پرکاربرد­ترین الگوریتم­ها در مسائل جستجو و بهینه­سازی است. یکی از دلایل محبوبیت الگوریتم­های ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته می­باشد، این الگوریتم­ها از قانون تکامل پیروی می­ کنند. عمل تکامل توسط آمیزش کروموزوم­ها و عمل جهش بر روی آن­ها انجام می­شود و کروموزوم­هایی که دارای برازندگی بیشتری هستند شانس بیشتری برای انتقال به نسل­های بعد را دارند (مسعودیان و استکی، ۱۳۸۸).

۱-۲- بیان موضوع

با توجه به تعداد روزافزون دانشجویان، رشته­های جدید، کمبود کلاس­ها، اتاق­های کنفرانس و آزمایشگاه­ها و تعداد رو به افزایش درس­های ارائه شده برای دانشجویان، برنامه ­ریزی با محدودیت­های بسیاری برای ساخت یک جدول مناسب مواجه خواهد بود (مسعودیان و استکی، ۱۳۸۸).

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

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

مسئله برنامه ­ریزی دروس دانشگاهی از جمله مسائل NP-hard است که به لحاظ تاثیر عوامل بسیار و وجود محدودیت­های مختلف از مشهورترین مسائل بهینه­سازی است (راستگارامینی، ۱۳۹۱). یکی از دسته­های خاص مسائل زمان بندی را جدول­بندی زمانی می­نامند. جدول­بندی زمانی، در واقع زمان­بندی مجموعه ­ای از رویدادهای هم­پیوند، در کم­ترین بازه­های زمانی است به گونه­ای که منابع مورد نیاز، همزمان توسط بیش از یک رویداد استفاده نشوند (دتین و همکاران، ۲۰۰۹.م).

در این مسئله سعی بر این است که مجموعه ­ای از منابع معین، متشکل از کلاس­ها، اساتید و دروس تحت شرایط خاص به مجموعه ­ای از ساعت­های درسی اختصاص یابد (خلیلی و منصورزاده، ۱۳۸۵). با توجه به توضیحات و پیچیدگی مسئله، روش­های مختلفی برای حل این مسئله در مقالات مختلف پیشنهاد شده است (غافری، ۱۳۸۷)، مانند برنامه ­ریزی­های خودکار (باشی زاده، ۱۳۹۱) و در نظرگیری معیار­های ارزیابی نظیر ترجیحات اساتید ­(­اولویت زمانی و اولویت درسی­) و رعایت محدودیت­هایی مانند تعداد ظرفیت کلاس­ها می­باشد (راستگار­امینی، ۱۳۹۱).

در مسئله زمان­بندی کلاس­های دانشگاه، این محدودیت­ها به دو دسته محدودیت­های سخت و محدودیت­های نرم گروه بندی می­شوند. محدودیت­های سخت، محدودیت­هایی هستند که در هر زمان­بندی، باید رعایت شوند. اگر یک زمان­بندی، این دسته از محدودیت­ها را نقض کند، آن زمان­بندی پذیرفتنی نخواهد بود. هر چه این محدودیت­ها بیشتر برآورده شوند، زمان­بندی به دست آمده از مطلوبیت بیشتری برخوردار خواهد بود (بابایی زاده، ۱۳۹۰).

الگوریتم ژنتیک یکی از قوی­ترین و پرکاربردترین الگوریتم­ها در مسائل جستجو و بهینه­سازی است. یکی از دلایل محبوبیت الگوریتم­های ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته می­باشد، این الگوریتم­ها از قانون تکامل پیروی می­ کنند. عمل تکامل توسط آمیزش کروموزوم­ها و عمل جهش بر روی آنها انجام می­شود و کروموزوم­هایی که دارای برازندگی بیشتری هستند، شانس بیشتری برای انتقال به نسل­های بعد را دارند یکی از دلایل محبوبیت الگوریتم­های ژنتیکی عدم نیاز به مدل ریاضی سطح بالا و پیشرفته می­باشد (مسعودیان و استکی، ۱۳۸۸). این الگوریتم­ها بر روی یک سری از جواب­های مسئله، به امید به دست آوردن جواب­های بهتر، قانون بقای بهترین را اعمال می­ کند. در هر نسل به کمک فرایند انتخابی متناسب با ارزش جواب­ها و تولید مثل جواب­های انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شده ­اند، تقریباً جواب­های بهتری از جواب نهایی به دست می­آید (باوی و صالحی، ۱۳۸۹).

۱-۳- اهمیت و ضرورت تحقیق

مسئله زمان­بندی کلاس­های دانشگاه، چالشی جدی برای مدیران دانشگاهی در هر نیم­سال تحصیلی است، زیرا در این­گونه مسائل با محدودیت­های فراوانی مواجه خواهیم بود، تمامی محققان در این زمینه اتفاق نظر دارند که مسئله جدول­های زمانی دارای فضای پاسخ نمایی بوده و مانند تمامی مسائل NP-hard  نیاز به استفاده از الگوریتم­های هوشمند جهت حل آن اجتناب ناپذیر است (غافری، ۱۳۸۷).

دستیابی به یک برنامه زمان­بندی پذیرفتنی که محدودیت­های سخت را برآورده نماید و بتواند محدودیت­های نرم را تا حد ممکن برآورده کند، کاری بس دشوار و بسیار زمان­بر است (بابایی زاده، ۱۳۹۰). در مورد محدودیت­های سخت می­توان به قوانین و مقررات آموزشی اشاره نمود که این گونه محدودیت­ها حتماً باید در نظر

 

گرفته شوند زیرا  نشان­دهنده اهمیت نحوه برنامه ­ریزی درسی می­باشد (حاجی یخچالی، ۱۳۷۸)، و رعایت نکردن این قوانین و مقررات به عنوان محدودیت­های سخت نشان­دهنده نامعتبر بودن برنامه درسی می­باشد (دهقانی و ذاکر تولائی، ۱۳۸۵ ).

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

۱-۴-­تعریف مسئله

با توجه به مواردی از قبیل ساختار دروس دانشگاهی، انواع دروس دانشگاهی، دسترسی به منابع و دوره­های زمانی، مسئله زمان­بندی دروس دانشگاهی با هدف معین و محدودیت­های سخت و نرم تعریف خواهد شد، هدف مسئله زمان­بندی دروس، حداقل نمودن فاصله بین دو کلاس متوالی در برنامه نیمسال گروه دانشجویان است به صورتی که محدودیت­هایی از قبیل تداخل برنامه اساتید، تداخل برنامه دانشجویان، تداخل برنامه کلاس­ها، ترجیحات اساتید، تعداد جلسات مورد نیاز هر درس در هفته، وسایل و تجهیزات مورد نیاز برگزاری هر درس، ظرفیت کلاس­ها، زمان­های استفاده از کلاس­ها، دروس از پیش زمان­بندی شده و از این دست محدودیت­ها که در قوانین و مقررات آموزشی آورده شده و رعایت کردن آنها اجباری است نیز لحاظ گردند، بدین ترتیب مسئله زمان­بندی این پژوهش با در نظر گرفتن هدف و محدودیت­های مسئله به صورت یک مدل برنامه ­ریزی غیر­خطی صفر و یک (با توجه به تابع هدف و یافتن متغیرهای صفر و یکی) درآمد و برای حل این مسئله، روش ابتکاری کدنویسی در نرم افزار ریاضی MATLAB جهت رسیدن به جواب نهایی مطلوب به کار گرفته شد.

۱-۵-­اهداف تحقیق

هدف اصلی از اجرای این پژوهش، دسترسی به یک برنامه درسی بهینه با رعایت کردن تمامی شرایط برای مقاطع کارشناسی ارشد در دانشکده فنی­- مهندسی دانشگاه علم و هنر می­باشد. اهداف فرعی که در طول اجرای پروژه محقق گردیده به شرح ذیل است:

  • دستیابی به مدلی با در نظرگرفتن ترجیحات اساتید
  • یافتن بازه­های زمانی مناسب با رعایت کردن حداقل فاصله بین بازه ها برای دروس هر گروه

۱-۶-سوالات پژوهشی

در این پژوهش به سوالات زیر پاسخ داده می­شود:

  • با توجه به محدودیت­های مسئله زمان­بندی دروس دانشگاهی چه مدلی مناسب است؟
  • کدام بازه­های زمانی به عنوان جواب نهایی مدل، به دست آمده و مطلوب می باشند؟

۱-۷-قلمرو تحقیق

قلمرو تحقیق در سه بعد موضوعی، مکانی و زمانی در این پژوهش به شرح زیر می­باشد:

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

قلمرو مکانی: قلمرو مکانی این پژوهش دانشکده فنی- مهندسی دانشگاه علم و هنر یزد است، که با توجه به وجود مقاطع کارشناسی و کارشناسی ارشد این دانشکده، ۴ گروه­ از مقاطع کارشناسی ارشد سال ۱۳۹۱ انتخاب

شده ­اند، می­توان این پژوهش را برای گروه­های مختلف و تعداد بیشتری از گروه­ها در مقاطع کارشناسی و کارشناسی ارشد در این دانشکده اجرا نمود.

قلمرو زمانی: قلمرو زمانی این پژوهش اطلاعات تمامی گروه­های مقطع کارشناسی ارشد در نیم­سال دوم تحصیلی سال ۱۳۹۱ می­باشد. که داده­های این نیم­سال، مورد استفاده جهت نوشتن مدل و سپس حل آن بوده است.

۱-۸-روش انجام تحقیق

در این پژوهش ابتدا کلیه منابع اطلاعاتی در زمینه مسئله مورد نظر یعنی مدل­سازی برای زمان بندی دروس دانشگاهی مطالعه شد و با در نظر گرفتن محدودیت­های سخت و نرم این مسئله و مصاحبه­ای که با مسئولان  برنامه ­ریزی دروس دانشگاهی در دانشکده فنی- مهندسی دانشگاه علم و هنر یزد انجام شد، مدل ریاضی دو­مرحله­ای غیر­خطی با متغیرهای صفر و یک نوشته شد و پس از آن برای حل مدل کدهای مورد نظر برای الگوریتم ژنتیک، ثبت و برای دست­یابی به جواب نهایی مسئله اجرا شدند.

تعداد صفحه :۱۳۹

قیمت :۳۷۵۰۰ تومان

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

و در ضمن فایل خریداری شده به ایمیل شما ارسال می شود.

پشتیبانی سایت  [email protected]