عنوان پایان‌نامه
ارائه یک الگوریتم تر کیبی ( الگوریتم کرم شب تاب وکلونی مورچه ) بهینه برای حل مسئله جداول زمانی دروس دانشگاه
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 104..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79233;کتابخانه پردیس یک فنی شماره ثبت: 104..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79233
- تاریخ دفاع
- ۲۹ دی ۱۳۹۵
- دانشجو
- حمیدرضا اسماعیلی پور
- استاد راهنما
- امین قدوسیان
- چکیده
- مسئله جداول زمانی، به فرآیند تخصیص منابع محدود مکانی- زمانی، به تعدادی رویداد، با شرط ارضاء تعداد زیادی محدودیت، اشـاره می نماید. گرچه تعریف فوق دامنه بسیار وسیعی از مسائل را در بر می گیرد اما عموماً مسئله جداول زمانی به طراحی برنامه کلاسی یا امتحانات، در محیطهای آموزشی اشاره می نماید. در این تحقیق، بر روی تهیه برنامه کلاسی دانشگاه تمرکز شده است. باتوجه به افزایش تعداد دانشجویان، ایجاد رشته های جدید و کمبود فضاهای آموزشی، با محدودیت های بسیاری برای ساخت یک برنامه کلاسی مناسب مواجه هستیم. از آنجایی که مسئله جداول زمانی، از جمله مسائل NP-complete به شمار می رود، نیاز به استفاده از الگوریتم های هوشمند جهت حل آن قطعی است الگوریتم ژنتیک یکی از روشهای پرکاربرد جهت حل مسئله جداول زمانی می باشد. کار صورت گرفته در این زمینه تلاش دارد با ایجاد تغییرات در این الگوریتم، بجای استفاده از یک جمعیت اولیه و انجام مراحل الگوریتم ژنتیک بر روی آن، جمعیت های متفاوتی ایجاد نماید. ساختار کروموزومی در تمامی این جمعیت ها یکسان است، اما هر جمعیت می تواند مراحل انتخاب، جفت گیری، جهش و تابع برازش خاص خود را داشته باشد. پس از گذشت چند نسل، توسط الگوریتم های نخبه گرا به تبادل کروموزوم بین جمعیت ها می پردازیم. از آنجایی که کارایی مدل های مختلف الگوریتم ژنتیک به شدت وابسته به نوع داده ها می باشد، روش مطرح شده به دلیل امکان استفاده از روش های مختلف در هر جمعیت، خطر قرار گرفتن در اکسترمم محلی را کاهش داده و سرعت رسیدن به جواب مناسب را افزایش می دهد. به دلیل استفاده از الگوریتم نخبه گرا در تبادل کروموزوم بین جمعیتها از گسترش تاثیرات منفی یک روش نامناسب در سایر جمعیت ها جلوگیری می شود.
- Abstract
- The timetables issue talks about the allocation process of the constrained temporal-spatial sources and about some events, on condition of removing numerous constraints. Although the mentioned definition covers a variety of issues, the question of timetables focuses on the designing of syllabi and assessments in educational atmospheres. This research concentrates on designing university syllabi and lesson plans. Considering the ever increasing number of university students and new academic fields of study and the scarcity of educational atmospheres, we have various constraints ahead to make a proper syllabus. Since the issue of timetables is one of the NP-complete issues, the application of intelligent algorithms is indispensably required. Genetic algorithm is one of the most practical methods to find a solution to designing timetables. The research done here is aimed at making various populations, by changing the algorithm, instead of using primary population and applying the genetic algorithm on it. The chromosome structure in all the populations is the same, but each of them could have its own specific selection, crossover, mutation and fitness function phases. After some generations, we will process the chromosome exchange by elitist algorithms. Due to the fact that the efficiency of various models of genetic algorithms are deeply dependent on the types of data, the discussed method decreases the risk of being in local minimum since it can use different methods in each population and hence it accelerates the pace towards the appropriate answer. Applying elitist algorithms in chromosome exchange among the populations hinders the negative effects extension of one i
