Journal of Information Technology Management University of Tehran
ISSN: 2008-5893 Faculty of Management
EISSN: 2423-5059
Vol. 9, No. 3; PP. 531-548
Fall 2017

Proposing Innovative Genetic Algorithms Model to
Solve the Problem of the Professors’ Educational Planning Considering Students’ Opinions
Laleh Asgari 1, Mohammad Reza Keyvanpour 2
Abstract: Timing of curriculum planning for students and faculty could be done using diverse methods. The present research concerns with curriculum planning for professors considering the students’ opinions. In doing so, the courses and the timing are determined based on the professors’ common timetable, the professors’ intensive courses timing and the class limitations. To achieve this goal, the genetic algorithm methodology was used in two steps. In the first stage, single-point cutting operator was used and in the second stage of the algorithm, a new intelligent operator called cyclic reverse list (RIL) was used provided that gold, silver and bronze time types were used for different courses. The advantages of this algorithm are using a new appropriate function (hot rolled), as well as new criteria and a new operator (RIL). Unlike conventional methods, in this method the appropriateness is considered in proportion with the whole population and we try to remove the impossible solutions. The optimal solution is chosen from among a multitude of provided responses. Therefore, it was found that we can reach the optimal solutions with regard to a better appropriateness.

Key words: Fitness function, Genetic Algorithm, Mimetic Algorithm, Rotatory Inverse List (RIL), Timing.

Msc, Social and Economic System Engineer, Specialized Data Mining Laboratory, Alzahra University, Tehran, Iran
Associate Prof. of Software Engineer, Faculty of Engineering, Alzahra University, Tehran, Iran

Submitted: 20 / December / 2016
Accepted: 09 / April / 2017
Corresponding Author: Laleh Asgari
Email: laasgari@gmail.com

Journal of Information Technology Management
دانشكدة مديريت دانشگاه تهران دورة 9، شمارة 3 پاييز 1396
صص. 548- 531

ارائة مدل ابتكاري الگوريتم ژنتيك براي حل مسئلة برنامة آموزشي
استادان با تأمين نظر دانشجويان
لاله عسگري1، محمدرضا كيوان پور2
چكيده: زمان بندي در برنامه ريزي درسي دانشجويان و استادان با روش هاي متنـوعي صـورت ميگيرد. اين تحقيق به حل مسئلة برنامة آموزشي استادان با تأمين نظر دانشجويان مـي پـردازد .
در اين مسئله، تخصيص درس و زمان به استادان بـا در نظـر گـرفتن سـاعت جلسـة مشـتركاستادان و زمان بندي ساعات تدريس فشردة آنان و محدوديت كلاسها انجام مـي شـود. بـدين منظور، روش الگوريتم ژنتيك در دو مرحله به كار برده شـده اسـت. در مرحلـ ة اول الگـوريتم ، از عملگرِ برش تك نقطهاي استفاده شد و در مرحلة دوم الگوريتم، عملگر هوشمند جديدي به نـامفهرست معكوس حلقوي با در نظر گرفتن زمان هاي طلايي، نقره اي و برنزي بـراي درسهـاي مختلف به كار رفت. مزيت اين الگوريتم استفاده از تابع برازندگي جديد و همچنين معيار انتخـابجديد و يك عملگر جديد است. اين روش برخلاف روش هاي معمول، برازش كل جمعيت را در نظر ميگيرد و تلاش مي كند جواب هاي امكان ناپذير را حـذف كنـد. در ايـن الگـوريتم، جـوابنهايي از جواب هاي بهينة متعدد توليد شده انتخاب ميشود. نتايج نشان داد اين روش با بـرازشبهتري به جوابهاي بهينه مي رسد.

واژه هاي كليدي: الگوريتم ژنتيك، تابع برازندگي، زمان بندي، فهرست معكوس حلقوي، ممتيـكالگوريتم.

كارشناسارشد مهندسي سيستم هاي اقتصاديـ اجتماعي، آزمايشگاه تخصصي دادهكاوي، دانشگاه الزهرا، تهران، ايران
دانشيار مهندسي نرمافزار كامپيوتر، دانشكدة فني مهندسي دانشگاه الزهرا، تهران، ايران

تاريخ دريافت مقاله: 30/09/1395 تاريخ پذيرش نهايي مقاله: 20/01/1396 نويسندة مسئول مقاله: لاله عسگري
E-mail: laasgari@gmail.com
مقدمه
زمانبندي درسي در ساده ترين جمله، يعني تخصيص زمان و كلاس به استاد و درس. زمان بندي درسها در جدول هفتگي، بر اساس معيارها و امكانات محيط، مشخصات درس، سـاعات حضـوراستادان و درخواست دانشجويان صورت مي گيرد. زمان بندي در حركـت قطـار، هواپيمـا ، متـرو و درس دانشجويان، مسابقه هاي ورزشي، امتحان دانشجويان و همايش ها كـاربرد دارد ؛ بـه گونـه اي كه از تداخل زماني دو برنامه با يكديگر جلوگيري ميكند و بـه رضـايت كارفرمـا و اربـابرجـوع ميانجامد. از آنجا كه در بيشتر دانشگاه هاي ايران، دانشجويان ارشد و دكتري در كنار اشتغالي كه دارند، به تحصيل نيز ميپردازند، براي تأمين رضايت دانشجويان بهتر است برنام هاي تنظيم شـودكه تعداد روزهاي تحصيل دانشجوبان را فشرده و در روزهاي متوالي تنظيم كند. همچنين برنامـ ة درسي استادان نيز در روزهاي متوالي تنظيم شود تا ساعات پيوست هاي براي تحقيـق آزاد شـود. از سوي ديگر، در نظر گرفتن ساعت جلسة مشترك براي استادان در روز مشـترك موضـوع مهمـي است. هدف اين تحقيق بهينه سازي زمان استادان و دانشجويان است كه بـا ضـرورت آزادسـازيزمان روزانة استادان و دانشجويان انجام مي شود.
براي زمان بندي از روشهايي همچون برنامهريزي عدد صحيح، برنامهريزي منطقي1 و هوش مصنوعي، تپه نوردي (HC)2، شبيه سازي تغيير دما (SA)3، الگوريتم ژنتيـك، هـايپر هيورسـتيك،متاهيورستيك، الگوريتم جست وجوي متوازن (HSA)4، الگوريتم جسـتوجـوي ممنوعـه5، سـيلبزرگ (GDA)، جست وجوي همسايگي متغير (VNS)6، تئوري مورچه و الگوريتم ژنتيك استفاده شده است. مزيت استفاده از الگوريتم ژنتيك نسبت به روش هاي ديگر، توليد جواب بهينه حتي در تعداد نسلهاي زياد است.
پيشينة پژوهش
يكي از روشهاي مشهور روش تپه نوردي (HC) اسـت . ايـن روش اجـراي سـاده و آسـاني دارد. تله گذاشتن در نقطة بهينه آسان است. روش HC مي تواند براي توليد راه حلهاي با كيفيت خوب با كارهاي ديگر مقايسه شود (اسميت اسمان، ريورز و اسـميت ، 1996). الگـوريتم جسـتوجـو ي
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Logic Programming
Hill Climbing
Simulated Aannealing
Harmony Search Algorithm
Tabu Search
Variable Neighborhood Search (VNS)
ممنوعه نيز از چند صفت حركت همسايگي و چشمپوشي از راه حل هايي كه در تابو ليست هستند، استفاده مي كند (گلور، 1986؛ اسلوني، احمدي و كابرك، 2001).
روش شبيهسازي تغيير دما (SA) راه حلهاي بهتري ارائه ميدهد يا راه حل هاي بدتر را با كم كردن احتمال در جستوجو پيدا مي كند (كرك پاتريك، گلت و وچي، 1983). سيل بزرگ1 نيز به روش SA كار ميكند، اما از مرزي مانند SA بهعنوان روابط استفاده مي نمايد كه به نـدرت كـم مي شود (داك، 1993). راه حل جست وجوي همسايگي متغير (VNS)2 بر پاية اسـتراتژي اسـتفادة بيشتر از ساختار همسايگي و تغيير آنها به طور سيستماتيك در طول جسـت وجـو عمـل مـي كنـد (عبداله، برك و مك كلام، 2005). از روش هاي ديگر، بهينـه سـازي كلـوني مورچگـان (ACO)3 است (دوريگو و كارو، 1999). ACO از رفتار مورچه ها و روشي كه آنها براي غذا كاوش ميكنند، الهام ميگيرد. كارهاي زيادي با استفاده از روش ACO براي زمـانبنـدي امتحانـات در ادبيـاتانجام شده است (الي، 2006). الگوريتم ممتيك نيز تركيب الگوريتم ژنتيك و الگوريتم جستوجوي محلي بهواسطة تركيب كردن الگوريتم جست وجوي محلي است (براك، نوال و وير، 1996).
اشي هارا، ساكاگوچي و ياماموري (2004) با استفاده از عملگرهاي ژنتيـك سـنتي در مسـئلة زمانبندي و با طبقه بندي محدوديت ها، محدوديت ها را به سه گروه ضروري، شـرطي مطلـوب و شرطي دانشجويان دسته بندي كردند و با استفاده از تابع شايستگي خـاص و عملگـرcrossover تك نقطهاي، به توليد جدول زماني پرداختند.
هسو و چااو (2009)، بهكمك روش ابتكاري و در نظرگرفتن محدوديتهاي زماني دانشـجو، بودجة دانشگاه و منابع دانشكده ها و همچنين با استفاده از دو تابع شايستگي، نياز دانشـجويان در اخذ درس يا اخذ دوبارة آن بدون ايجاد تأخير در تحصيل را مشخص كردند و بـا در نظـر گـرفتناندازة كلاس ها به تخصيص منابع پرداختند.
در مسئله اي ديگر، ونگ، ليو و يو (2009) با استفاده از عملگر جديـدي بـه نـام خودلقـاحي4، محدوديتهاي ارائة درس در اتاق مشخص و اضافهنشدن درس هاي تكراري بـه زمـان بنـدي رالحاظ كردند و از استدلال مبتني بر مورد5 روش ذخيره و بازيابي راه حل هاي قبلي براي جلوگيري از تداخل درسها و زمانها بهره بردند.
عبدندهر و آلي (2007) با در نظر گرفتن محدوديتهاي زمان سخنرانيها و برنامهريزي زمان امتحانات و با روش برنامهنويسي منطقي و هوش مصنوعي به حل مسئله پرداختند.
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Great deluge
Variable Neighborhood Search (VNS)
Ant Colony Optimization (ACO)
Self fertilization
Case based Reasoning
بهداد، دهقان و ذاكر تولايي (1385)، به كمك روش پيشرو، مجموع سـاعت هـاي بـي اسـتفادةدانشجويان و استادان را كمينه كردند و با استفاده از تركيب عملگرهاي crossover تك نقطـه اي، دو نقط هاي و يكنواخت، به برنامهريزي روي محدوديت هاي سخت پرداختنـد و بـا لحـاظ كـردنوزن به محدوديتها، تابع شايستگي جديد به دست آوردند.
همر و موهوب (2014) معتقدند ديدگاه متاهيورستيك پيچيده (ETP) ، چند فـاز بـراي حـلمسئلة زمان بندي امتحان منظور مي كند. اين ديدگاه شامل فاز پيش پردازش، فـاز سـاختار و فـاز پيشرفت است.
پيلا (2014) براي حل مسئله اي از الگوريتم درخت پارسه استفاده كرد. اين الگوريتم بـه هـر دانشجو هيورستيكي نسبت ميدهد تا سختي زمانبندي عملـي/ عمـومي را بـراي ا يـن دانشـجو نمايش دهد. الگوريتم بهترتيب هيورستيك و تخصيص به هر دانشجو اجرا مي شـود . هي ورسـتيك به سه بخش تخصيص، درس و جلسه دسته بندي ميگردد. نتايج ايـن مطالعـه نشـان داده اسـت هيورستيك تخصيص و ثانويه براي يافتن راه حل مسئله است.
رودوا، مولر و موري (2010) براي حل يك مسئلة برنامهنويسي برپاية محدوديت، روش هـاي هايپر هيورستيك و روش هاي متاهيورستيك را معرفي كردند، به گونه اي كـه از هـيچ اسـتراتژي نميتوان انتظار داشت از يكديگر بهتر اجرا شود. ويليام و گومز بيان كردند كه مسـائلnp-hard انعطافناپذيرند؛ به اين معنا كه الگوريتم كارايي وجود ندارد تا براي پيدا كردن راهحل بهينه براي انواع مشكلات تضمين شود (مارك و لوئيس، 2006).
وحيد و محدحسين (2014) در پژوهشي، از الگوريتم خاصي به نـام الگـوريتم جسـت وجـو ي متوازن در پنج مرحله استفاده كردند كه عبـ ارتانـد از : 1. مقـداردهي اوليـه پارامترهـاي HSA و UCTP؛ 2. مقداردهي اولية حافظة هارموني (HM) با زمانبندي امكان پـذير تصـادفي بـر پايـة پارامترهاي اندازة حافظة تصادفي (HMS)؛ 3. تعبيه كردن راهحل هارموني جديد؛ 4. به روزرسـانيحافظة هارموني. 5. متوقف كردن معيارها.
ميتال، دوشي و سوناسرا (2015)، پژوهشي با هدف ايجاد جدول زمان بندي خودكار به وسـيلة الگوريتم ژنتيك انجام دادند. آنها سيستمي را پيشنهاد كردند كه در آن جدول زمان بندي بـه طـور مكانيكي رأي انستيتو درست كند. ساختار جدول زمان بندي شامل داده هـاي ورودي، رابطـة بـين داده هاي ورودي، محدوديت هاي سيستم و كاربرد الگوريتم ژنتيـك مـيشـود . ابتكـار ايـن روشالگوريتم توليد جدول زماني اتوماتيك است.
شن جونگ، لين و پي كااو (2007)، در مقالة سيستم زمان بندي تطبيقي با الگـوريتم ژنتيـك، به مرتب كردن برنامه هاي آموزشي استخدامي پرداختند.
كاهار و كندال (2015) مسئلة زمانبندي امتحانات را با هدف در نظر گرفتن محدوديت هـايسخت و نرم به كار بردند. آنان در اين مقاله الگوريتم سـيل بـزرگ را توسـعه يافتـه و تغييـر يافتـه معرفي كردند.
معمولا يافتن راهحل امكانپذير بـراي ني ازهـاي زمـان بنـدي ، روشهـا ي مختلفـي دارد و از كشوري به كًشور ديگر، متفاوت است. چالش زمانبندي خودكـار، وجـود جـواب هـاي غيربهينـ ة متعدد يا به بيان ديگر، بالابردن دقت در حل مسئله است. در اين تحقيـق بـراي تـأمين رضـايتدانشجويان شاغل در حين تحصيل در مقاطع ارشد و دكتري دانشگاه هاي ايران، تنظيم برنامه اي كه تعداد روزهاي تحصيل دانشجويان را فشرده كرده و در روزهاي متوالي چينش كند تا سـاعات پيوستهاي براي تحقيق آزاد شود و ساعت جلسة مشترك براي استادان در روز مشـترك در نظـرگرفته شود، ضروري به نظر ميرسيد. بدين منظور از عملگر جديـد فهرسـت معكـوس حلقـوي1، استفاده شد. اين روش، برازش را نسبت بـه كـل جمعيـت در نظـر مـي گيـرد و تـلاش مـي كنـد جوابهاي امكانناپذير را حذف كند. به كمك اين روش، در هر تكرار، جواب بهينه توليـد شـده و با اين الگوريتم جديد فشردهسازي زمانبندي بدون توليد جواب ناكارآمد، امكان پذير ميشـود . در ارتباط با تفاوت اين روش با الگوريتم جستوجوي متوازن يا ساير روش هاي يادشـده، مـي تـوانگفت كه در اين روش كلية جواب ها امكان پذيرند و با وزن دهي از بين آنها جواب بهينـه انتخـابمي شود، اما در الگوريتم جستوجوي متوازن، بهصورت تصادفي جوابهـاي امكـان ناپـذير توليـدشده و براساس ملاحظة تصادفي و تنظيم پرتاب، حذف ميشوند. ساير روشهاي اشاره شده نيـزدر تعداد تكرارهاي بيشتر، با توليد جواب هاي امكان ناپذير متعدد به جـواب مـي رسـند . از ايـن رو الگوريتمهايي كه سعي در كم كردن جوابهاي غير بهينه دارند، براي مقايسه بـا الگـوريتمRIL پيشنهاد مي شوند. الگوريتمهايي مانند SA ،HC، ممتيك الگوريتم، VNS جواب هـا ي غيربهينـه توليد ميكنند، اما نسبت به يكديگر شدت و ضعف دارند.
مدل مفهومي
از آنجا كه فشرده سازي زمان درس دانشجويان و اسـتادان و نزديـككـردن انتخـاب اسـتادان و دانشجويان براي آزاد ساختن زمان مطالعه و كار همزمان دانشجويان مهم است، در اين تحقيق با استفاده از الگوريتم ژنتيك دو مرحله اي و در نظر گرفتن محدوديت هـاي عـدم تـداخل درس هـا براي هر آرايش ترمي، كمينهشدن ساعات ب ياستفادة دانشجويان، عدم تخصيص كلاس به چنـددرس همزمان و تداخل نداشتن دروس دانشجويان هم رشته و همدوره، به حل مسئله پرداخته شده
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
1. Rotaory InverseList (RIL)
است. براي نيل به اين منظور، روش الگوريتم ژنتيك در دو مرحله اجرا شده است؛ در مرحلة اولالگوريتم، از عملگر برش تك نقطه اي استفاده ميشود و در مرحلة دوم، عملگر هوشـمند جديـديبه نام فهرست معكوس حلقوي با در نظر گرفتن زمان هاي طلايي، نقره اي و برنزي براي دروس مختلف، به كار برده مي شود. مزيت اين الگوريتم استفاده از تابع برازندگي جديد و همچنين معيـارانتخاب جديد و عملگر جديد است. چالش موجود در اين راهكارهـا بـراي حـل مسـائل يادشـده ، نرسيدن به جواب بهينه، توليد جواب غيربهينه و تكرارهاي زياد بـراي رسـيدن بـه جـواب بهينـهاست. اين روش، برازش را نسبت به كل جمعيت در نظر مي گيرد و سـعي در حـذف جـواب هـا ي امكان ناپذير دارد؛ در صورتي كه در روش هاي معمول، برازش براي هر كروموزوم انجام مي شـود(ايكو و همكاران، 2004؛ بهداد و همكاران، 2007؛ پيلا، 2014، جونگ و همكاران، 2007). ايـنامر باعث مي شود كه در هر تكرار، جواب بهينه توليد شود و به كمك اين الگوريتم جديـد ، امكـانفشرده سازي زمان بندي بدون توليد جواب ناكارآمد فراهم آيد. از اين رو، جواب هاي بهينة متعددي توليد مي شود كه با احتساب وزن و اولويت به جواب ها، جـواب نهـايي انتخـاب مـي شـود . بلـوكدياگرام روش پيشنهادي به شرح زير است:

Pp (الف Ewpfa (ب Psa (ج
140989-184667

مرحلة

الگوريتم

اول

پيش

پردازش

روش

استخراج

مرحلة

الگوريتم

دوم

مرحلة

الگوريتم

اول

پيش



قیمت: تومان


پاسخ دهید