بررسي مسأله زمان‌بندي درسي دانشگاهي با استفاده از ترکيب الگوريتم ممتيک بهبوديافته و الگوريتم سردشدن شبيه‌سازي شده
محورهای موضوعی : مهندسی برق و کامپیوترمجید جودکی 1 , محمدعلی منتظری 2 * , سیدرسول موسوی 3
1 - دانشگاه صنعتی اصفهان
2 - دانشگاه صنعتی اصفهان
3 - دانشگاه صنعتی اصفهان
کلید واژه: الگوریتم سردشدن شبيه‌سازي شده الگوريتم ممتيک جستجوي محلي مسأله زمان‌بندي درسي دانشگاهي,
چکیده مقاله :
مسأله زمان‌بندی به‌عنوان يکی از مسایل پيچيده بهينه‌سازی شناخته می‌شود. يک نمونه از مسایل زمان‌بندی، برنامه‌ريزي درسي دانشگاهی است که هر نيم‌سال در دانشکده‌هاي يک دانشگاه انجام مي‌شود. تنوع محدوديت‌ها در اين مسأله باعث مي‌شود برنامه‌ريزي در دانشکده‌هاي مختلف به گونه‌های متفاوتی انجام شود. کارهاي زيادي براي حل اين مسأله انجام شده است که اکثر آنها از روش‌هاي فرامکاشفه‌اي بهره برده‌اند. در اين مقاله يک مسأله زمان‌بندي واقعي مورد بررسي قرار مي‌گيرد و يک روش مبتني بر الگوريتم ممتيک بهبوديافته که از الگوريتم سردشدن شبيه‌سازي شده به‌عنوان رويه جستجوی محلی خود استفاده مي‌کند، ارائه مي‌شود. منظور از بهبود در الگوريتم ممتيک، استفاده از روش‌های مکاشفه‌ای در توليد جمعيت اوليه و همچنين تغيير عملگر تقاطع در اين الگوريتم مي‌باشد. همچنين يک عملگر به نام عملگر بهبود جهت بهبود راه حل‌هاي توليدشده و کاهش تعداد نقض محدوديت‌ها طراحي شده است. به‌کارگيري روش سردشدن شبيه‌سازي شده به‌عنوان رويه جستجوي محلي در الگوريتم ممتيک باعث افزايش توانايي بهره‌برداري اين الگوريتم خواهد شد. کارآمدی اين روش در مقايسه با برخی روش‌هاي جديد، با توجه به نتايج به‌دست آمده بر روي داده‌هاي استاندارد نشان داده شده است. همچنين مقايسه نتايج حاصل از اين روش با روش انجام‌شده به‌صورت دستي بر روي داده‌هاي واقعي نشان‌دهنده برتري اين روش مي‌باشد.
Course timetabling is a complex problem, happening at the beginning of every semester at universities. One of the most important problems related to this issue is various constraints. As a result of this, timetabling is performed in various methods at different departments. Many works have been performed to solve this problem which majority of them have used metaheuristic based techniques. In this paper, an algorithm is based on hybridization of improved memetic algorithm and simulated annealing algorithm is proposed. Improvement in memetic algorithm means heuristic initializes population and modification in crossover operator. Also, an operator which is called improvement is designed for improvement of created chromosomes and decrease of violation of constraints. In addition, utilization of simulated annealing will result to increase of the exploitive search ability of memetic algorithm. The experimental results which based on standard data indicate this method is more efficient in comparison with some other new methods.