پیاده سازی جدول زمانی با استفاده از الگوریتم ژنتیک

/
/
/

پیاده سازی جدول زمانی با استفاده از الگوریتم ژنتیک

مسئله جدولبندي زماني دروس در اصل، شامل تخصيص دروس هفتگي به بازه هاي زماني و اتاق های برگزاري كلاسها است. اگر شروطي مانند عدم تخصيص يك كلاس در يك ساعت به چند درس، يا عدم تلاقي زماني در دروس يك استاد را به مسأله اضافه كنيم، مشخص ميشود كه مسأله طراحي جداول زمانبندي، ميتواند يك مسأله ارضاي محدوديت (CSP) قلمداد شود. با توجه به تعداد روزافزون دانشجويان، رشته هاي جديد، كمبود كلاسها، اتاقهاي كنفرانس و آزمايشگاه و تعداد رو به افزايش درسهاي ارائه شده براي دانشجويان، با محدوديتهاي بسياري براي ساخت يك جدول مناسب مواجه هستيم. روشهاي متعددي براي حل اين نوع مسائل به كار گرفت مانند روشهاي جمعيتگرا يا تكاملي. انواع معمول اين روشها در كاربرد طراحي جدول زمانبندي عبارتند از:
الگوريتمهاي ژنتيكي، الگوريتمهاي كلوني مورچه ها، الگوريتمهاي ممتيك
الگوريتم هاي ژنتيك از قانون تكامل پيروي ميكنند. براي شروع اين الگوريتمها نياز به يك نسل اوليه تصادفي ميباشد كه مجموعه اي معمولاً تصادفي از جوابهاي مسأله است. سپس اين جوابها تا رسيدن به يك سطح بهينه عمومي تكامل پيدا ميكنند. عمل تكامل توسط آميزش كروموزومها و عمل جهش بر روي آنها انجام ميشود و كروموزومهايي كه داراي برازندگي بيشتري هستند شانس
بيشتري براي انتقال به نسلهاي بعد (تجديد نسل) را دارند. در مسأله مورد بحث ما كروموزوم ها در اصل همان جداول زماني ميباشند.

از كارهاي انجام شده در اين زمينه ميتوان به موارد متعددی اشاره نمود. پيچر و رانكين روشي مبتني بر الگوريتم هاي ممتيك همراه با يك جستجوي محلي موثر ارائه دادند كه بر روي داده هاي اولين مسابقه جدول زمان بندی اعمال شد. بورك، اليمن و وير در دانشكدة علوم كامپيوتر دانشگاه ناتينگهام، الگوريتم ژنتيكي را پيشنهاد كرده اند كه تنها روي بازه هاي زماني قابل قبول اعمال مي شود و به طور تعاملي با كاربر ارتباط دارد. اربن و كپلر نيز جداولي بهينه براي دروس هفتگي را به كمك الگوريتم هاي ژنتيكي طراحي و پياده سازي نموده اند.
با توجه به پر محاسبه بودن الگوريتمهاي ژنتيكي، تلاشهايي در جهت افزايش سرعت آنها نيز صورت گرفته است. در اين راستا آبرامسون و ابلا در تحقيق خود از الگوريتمهاي ژنتيك موازي در حل مسأله طراحي جداول زمانبندي براي مدارس سود برده اند و مزيت زماني نسبتاً بالايي را نسبت به الگوريتمهاي ژنتيك عادي گزارش كرده اند. گروهی دیگر از محققین روشهاي تركيبي و هايبريد را براي حل اين مسأله پيشنهاد كرده اند. همچنين بليگيانيس و همكاران براي طراحي جداول زمانبندي دبيرستانها در كشور يونان، الگوريتمي وفقي بر مبناي محاسبات تكاملي پيشنهاد و پياده سازي كرده اند نتايج عملي كار ايشان روي تعداد زيادي از دبيرستانهاي يونان و در مقايسه با چند الگوريتم ديگر مطلوب گزارش شده است. به طور مشابه، پيلاي و بن ژاف نيز در تحقيق خود از يك الگوريتم ژنتيك مطلع و هوشمند براي طراحي جداول زمانبندي امتحانات سود برده اند. ديدگاه آنان يك ديدگاه دو مرحله اي بوده است كه در مرحله اول محدوديتهاي سخت و در مرحله دوم محدوديتهاي نرم به چالش كشيده ميشوند.

جدول زمان بندی دانشکده با استفاده از الگوریتم ژنتیک:

در این بخش از يك الگوريتم ژنتيك استاندارد در طراحي جداول زمانبندي برای یک دانشکده استفاده شده که فرضيات مسأله بصورت زیر هستند:
وروديها:
ليست دروس اصلي و آزمايشگاهي دانشكده، ليست كلاسهاي درس و آزمايشگاههاي موجود در دانشكده، ليست اساتيد دانشكده
خروجي:
جدول بهينه برنامه ريزي دروس
پارامترها:
– اندازه جمعيت ژنتيكي: ۱۰۰۰
– طول كروموزوم (تعداد خانه هاي جدول):
براي محاسبه طول كرومزوم از رابطه زير استفاده شده:
Lc = H × (C + A)
كه در اينجا H تعداد كل بازه هاي زماني يك ساعتي در يك هفته C تعداد کلاس ها و A تعداد آزمايشگاهها ميباشد.

در اينجا هر كرومزوم معادل يك جدول زماني فرض شده است. در نمايش دو بعدي ستونهاي اين جدول بازه هاي زماني و سطرهاي آن مكانها (كلاسها) را مشخص ميكنند. همان طور كه پيشتر ذكر شد روش كدگذاري جايگشتي ميباشد. در روش كدگذاري جايگشتي كروموزوم يك آرايه n عضوی صحیح است که اعداد ۱ تا n به عناصر مختلف آن منسوب می شوند. چون معمولاً يك كلاس در تمام ساعات هفته اشغال نيست، تعدادي از خانه هاي جدول خالي ميماند كه با صفر پر ميشوند. در ساخت اين جدول، ابتدا كلاسهاي درس و سپس آزمايشگاهها درج ميشوند. هدف از اين كار اين است كه نقض محدوديتهاي سخت را كم كنيم چون يك كلاس درس نميتواند در آزمايشگاه تشكيل شود و بر عكس. توابع ادغام و جهش ما نيز براي هربخش به طور جداگانه عمل خواهند كرد. دو پارامتر ورودي به توابع جهش و ادغام اضافه شد كه ابتدا و انتهاي بازه اي كه بايد ادغام يا جهش روي آن صورت گيرد را مشخص ميكند. يعني هرگاه قرار است ادغام يا جهش روي كروموزومي صورت گيرد، اين عمل با توجه به اين بازه مجاز انجام خواهند شد. در حقيقت در روش به كار گرفته شده، هرگز يك كلاس درسي در يك آزمايشگاه و يا يك آزمايشگاه در يك كلاس درسي واقع نخواهد شد. به همين دليل است كه مقدار دهي اوليه را شبه تصادفي، و نه كاملاّ تصادفي در نظر ميگيريم. رخدادها در مكانها اتفاق ميافتند (كلاسهاي درس و آزمايشگاهها) و كروموزومها همان جداول زماني هستند كه هر يك داراي برازش مربوط به خود ميباشند. چنان چه اندازه جمعيت خيلي بزرگ باشد، سرعت اجراي الگوريتم به شدت كاهش خواهد يافت. از طرفي اگر اندازه جمعيت كوچك باشد، مسأله خيلي زود به جوابي كه لزوماً بهينه نيست همگرا خواهد شد. راه حل پيشنهادي اين است كه اندازه جمعيت تابعي از تعداد رخدادها و طول كروموزومها باشد. يعني هر چقدر تعداد رخدادها بيشتر باشد جمعيت را بزرگتر، و هر چه طول كروموزومها بيشتر باشد جمعيت را كوچكتر در نظر ميگيريم. وظيفه اپراتور جهش جلوگيري از يكدستي جامعه و افتادن الگوريتم بدام نقاط بهينه محلي است. در اینجا جهت پياده سازي اپراتور جهش، سه ايده ابتكاري مورد استفاده قرار گرفته:
– جهش از طريق جابه جايي تعدادي از ژنها (دروس) درزير بازه مجاز خود (كلاس يا آزمايشگاه) محقق مي گردد تا از توليد كروموزومهاي نامعتبر اجتناب شود.
– چون جامعه با تكرار نسلها به سمت يكنواختي ميرود، نرخ جهش براي جلوگيري از يكنواختي تدريجاً افزايش مييابد.
– فضاهاي خالي جدول جابه جا نميشوند.
اگر نقض تمام محدوديتهاي سخت و نرم به صفر برسد، مفهوم اين است كه جدولي بهينه به دست آورده ايم و الگوريتم متوقف ميشود. يكي از شروط خاتمه معمول در الگوريتمهاي ژنتيك اين است كه اگر مقادير برازش جداول به يك مقدار يكسان همگرا شود، الگوريتم متوقف گردد. البته در اين روش خطر به دام افتادن در يك ماكزيمم محلي وجود دارد. براي اجتناب از اين مشكل در روش پيشنهادي به محض كاهش اختلاف مابين برازشها كه نشانه يكنواختي جامعه است، نرخ جهش افزايش مييابد. بدين ترتيب شرط توقف الگوريتم در رسيدن به جدول بهينه يا تكرار تعداد مشخصي از نسلها محدود ميشود. در يك مسأله ارضاي محدوديت، محدوديتها به دو دسته سخت و نرم تقسيم ميشوند. شرايط سخت آنهايي هستند كه در صورت عدم برآورده شدن آنها، پاسخ (در اينجا جدول) قابل قبول نخواهد بود. محدوديتهاي نرم نيزمواردي هستند كه رعايت آنها موجب بهتر شدن پاسخ خواهد شد. تابع ارزيابي مورد استفاده جهت محاسبه برازش پاسخها، شامل دو بخش است. بخش اول جريمه مربوط به نقض محدوديتهاي سخت و بخش دوم جريمه مربوط به نقض محدوديتهاي نرم را محاسبه ميكند. وزن جريمه محدوديتهاي سخت بسيار بالاتر انتخاب شده است محدوديتهاي سخت به شرح زير در نظر گرفته شدند:
الف) تداخل ساعات يك استاد: اگر به دو درس مختلف در يك زمان، يك استاد اختصاص داده شده باشد جريمه هاي نسبتاً بالا براي آن در نظر گرفته می شود.
ب) تداخل دروس دانشجويان يك ورودي خاص: از آنجا كه دروس ارائه شده براي دانشجويان يك ورودي خاص نبايد داراي تداخل باشند، براي اين محدوديت نيز جریمه ای نسبتاً بالا در نظر گرفته شده است.
پ) مكان نامناسب براي كلاسها و يا آزمايشگاهها: يك كلاس درس نميتواند در يك آزمايشگاه تشكيل شود و يا بر عكس.
ث) عدم اتصال ساعات دروس: چون هر سه ساعت دروس آزمايشگاهي بايد پشت سرهم ارائه شود، همچنين براي درس هاي سه واحدي، دو ساعت از سه ساعت آنها بايد پيوسته باشد، در صورت عدم اتصال اين ساعات، جريمه اي خواهيم داشت. ضمناً دروسي نيز وجود دارند كه تنها دو ساعت در هفته هستند كه اين دو ساعت نيز بايد پيوسته باشد.
ج) در نظر گرفتن امكانات لازم براي دروس آزمايشگاهي: هر درس آزمايشگاهي بايد در آزمايشگاه خاص خودش برگزار شود.
محدوديتهاي نرم نيز به شرح زير در نظر گرفته شدند:
الف) ارائه دروس سه واحدي غير آزمايشگاهي در ۳ ساعت متوالي: بهتر است دروس مهم و تخصصي در سه ساعت متوالي ارائه نشود؛ زيرا موجب كاهش كيفيت آموزش ميگردد.
ب) ارائه دروس سه واحدي غير آزمايشگاهي در يك روز: بهتر است دروس تخصصي و مهم علاوه بر رعايت شرط قبلي، در يك روز نيز ارائه نشود و ترجيحاً در دو روز ارائه گردد.
پ) ارائه دروس سه واحدي غير آزمايشگاهي در دو روز پشت سرهم: ترجيحاً بايد ساعات دروس سه واحدي در طول هفته پخش شده باشند (شامل يك تك ساعت و يك دو ساعت).
ت)عدم فاصله بين دروس يك گروه در يك روز: بهتر است در برنامه دانشجويان بين ساعات برگزاري كلاسهاي آنها ساعات خالي وجود نداشته باشد.
ث) ترجيحات اساتيد: هر استاد ترجيحات خود را به اين صورت كه صبح يا بعد از ظهر روزهاي خاصي را ميتواند در دانشكده حضور داشته باشد اعلام ميكند.
ج) ظرفيت مكانها: اندازه مكانها نبايد كمتر از تعداد دانشجويان درسي باشد كه در اين مكان تشكيل ميشود.
در نهايت جريمه كلي شامل مجموع وزن جريمه هاي سخت و نرم ميباشد كه جريمه هاي سخت، وزن بسيار بيشتري نسبت به جريمه هاي نرم دارند.

در مقاله بررسی شده خصوصيات الگوريتم ژنتيك به عنوان ابزاري مناسب در بهينه سازي پاسخهاي يك مسأله CSP مورد بررسي قرار گرفته سپس مسأله طراحي جداول زمانبندي براي دروس دانشگاهي به عنوان يك مسأله كاربردي CSP معرفي و يك راه حل ژنتيكي استاندارد براي آن ارائه شده است. به كمك افزايش نرخ جهش و ادغام و در مقابل انتقال نيمه بهتر جمعيت در نسل بعد، شبه تصادفي بودن مرحله مقدار دهي اوليه، و ديگر تغييراتي كه در الگوريتم ژنتيك معمولي اعمال شده از همگرا شدن الگوريتم جلوگيري شده و نتايج مطلوبي حاصل گشته است. همچنين نشان داده شده كه اجتناب از مقداردهي اوليه كاملاً تصادفي و سعي در گريز از مينيمم هاي محلي با دستكاري در پارامتر جهش ميتواند در بهبود بازدهي الگوريتم ژنتيكي در اين بهينه سازي خاص مؤثر باشد. خصوصاً كه در جستجوهاي غير سراسري مانند الگوريتم ژنتيك، همگرايي پيش از موعد موجب يكنواختي جامعه و به دام افتادن در يك اپتيموم محلي ميشود.

پیاده سازی زمان بندی کلاسهای دانشکده کامپیوتر با استفاده از الگوریتم ژنتیک در c#

کدی که در ادامه آورده شده در visual studio 2008 اجرا شده است.
زمانبندی برنامه کلاسها یک مسئله NP hard است. این مسئله با الگوریتم جستجوی هیوریستیک می توان برای پیدا کردن یک راه حل بهینه حل کرد ولی فقط برای موارد ساده کاربرد دارد. برای ورودی های پیچیده تر پیدا کردن یک راه حل خوب مدتی طول می کشد یا ممکن است غیر ممکن باشد. در اینگونه مواقع است که از الگوریتم ژنتیک استفاده می شود.
زمانی که برنامه زمانی یک کلاس (مدرسه یا دانشگاه) نوشته می شود باید ملزومات زیادی در نظر گرفته شود (تعداد اساتید، دانشجویان، کلاسها،درسها، اندازه کلاسها، تجهیزات آزمایشگاهی داخلی کلاسها، و بسیاری دیگر..). این ملزومات را می توان با توجه به اهمیت آنها به چندین گروه تقسیم کرد. ملزومات اصلی که اگر یکی از آنها در نظر گرفته نشود برنامه زمانی غیرقابل اجرا می شود بصورت زیر هستند:
یک کلاس تنها می تواند در یک اتاق خالی که قبلا استفاده نشده تشکیل شود
هیچ استاد یا دانشجویی نمی تواند بیش از یک کلاس در آن واحد داشته باشد
یک کلاس باید تعداد صندلی کافی به اندازه دانشجویان داشته باشد
اگر کلاسی به کامپیوتر نیاز داشت باید در اتاقی تشکیل شود که مجهز به کامپیوتر باشد
برخی از ملزومات را می توان رعایت نکرد و زمان بندی هنوز هم قابل اجرا باشد:
زمان مناسب برای گلاس از نظر اساتید
اتاق های برگزاری کلاس ها از نظر اساتید
پراکندگی زمانی و فضایی کلاس ها برای دانشجویان و اساتید
در این مثال تنها ملزومات اصلی پیاده سازی شده است.
آبجکت هایی که class schedule را می سازند:
Professor
کلاس Professor یک ID و نام استاد مربوطه را دارد به علاوه شامل لیستی از کلاس هایی است که این استاد می تواند تدریس کند.
Students Group
کلاس StudentsGroup یک ID و نام گروه دانشجویان به علاوه تعداد دانشجویان (اندازه گروه) را دارد. به علاوه شامل لیستی از کلاس هایی است که این گروه در آن شرکت می کنند.
Classroom
کلاس Room شامل ID و نام آن اتاق به همراه تعداد صندلی ها و اطلاعاتی درباره تجهیزات کلاس (کامپیوتر) است. اگر کلاس کامپیوتر داشته باشد انتظار می رود که برای هر صندلی یک کامپیوتر باشد. ID ها بصورت اتوماتیک ایجاد می شوند.
Course
کلاس Course شامل ID نام آن درس است.
Class
CourseClass شامل مرجعی از دروسی است که کلاس به آن دروس اختصاص دارد و همین طور شامل مرجعی از اساتیدی که درس می دهند و لیستی از گروه های دانشجویانی که در این کلاس های شرکت می کنند. به علاوه تعداد صندلی های (مجموع اندازه گروه های داتشجویان) مورد نیاز در هر کلاس را نیز ذخیره می کندو همین طور اطلاعاتی درباره اینکه کلاس نیاز به کامپیوتر دارد یا خیر و طول دوره کلاس (به ساعت).
کروموزوم:
اولین چیزی که باید هنگام کار با الگوریتم ژنتیک در نظر بگیریم این است که راه حل خود را چطور به گونه ای نشان دهیم که برای عملیات ژنتیک مانند crossover و mutation مناسب باشد. به علاوه باید بدانیم چگونه میزان خوب بودن راه حل خودرا تعیین کنیم. به عبارت دیگر باید بتوانیم fitness value راه حل خود را اندازه گیری کنیم.
نحوه نمایش:
چگونه می توان یک کروموزوم را برای برنامه زمانی کلاس ها نمایش داد؟ برای هر ساعت به یک فضای خالی نیاز داریم (زمانی – مکانی)، فرض می کنیم که زمان کپسولهای یک ساعته است، برای هر اتاق، هر روز.
به علاوه فرض می کنیم که کلاس ها نمی توانند قبل از ۹ صبح شروع شوند و باید قبل از ۹ شب یا راس ۹ تمام شوند (مجموعا ۱۲ ساعت) و روزهای کاری از دوشنبه تا جمعه است یعنی مجموعا ۵ روز.
می توان از یک std::vector با سایز ” ۱۲*۵* تعداد اتاق ها” استفاده کرد. اسلات باید یک std::list باشد زیرا در طول اجرای این الگوریتم در یک فاصله زمانی-مکانی اجازه چندین کلاس داده می شود. یک hash map دیگر نیز وجود دارد که برای به دست آوردن اولین اسلات زمان-مکان که در آن کلاس شروع می شود (موقعیت آن در بردار) از آدرس آبجکت class استفاده می شود. هر ساعت از یک کلاس ورودی جداگانه ای در بردار دارد ولی تنها یک ورودی در هر کلاس در hash map وجود دارد. برای مثال اگر کلاسی ۱ بعدازظهر شروع شود و ۳ ساعت طول بکشد در اسلات های ۱pm، ۲pm و ۳pm ورودی خواهد داشت.
کروموزوم ها توسط کلاس Schedule نمایش داده می شوند و نمایش زمان بندی یک کلاس را در این دو مشخصه نگه می دارند:
// Time-space slots, one entry represent one hour in one classroom
vector<list<CourseClass*>> _slots;

// Class table for chromosome
// Used to determine first time-space slot used by class
hash_map<CourseClass*, int> _classes;
به علاوه کروموزوم باید fitness value و پارامترهایی را که توسط عملیات ژنتیک استفاده می شود ذخیره کند.
fitness value در اینجا ذخیره می شود:
// Fitness value of chromosome
float _fitness;

// Flags of class requiroments satisfaction
vector<bool> _criteria;
پارامترهای کروموزوم:

// Number of crossover points of parent’s class tables
int _numberOfCrossoverPoints;

// Number of classes that is moved randomly by single mutation operation
int _mutationSize;

// Probability that crossover will occure
int _crossoverProbability;

// Probability that mutation will occure
int _mutationProbability;

Fitness
اکنون باید به کروموزوم fitness value اختصاص دهیم. در این الگوریتم تنها ملزومات اصلی برای محاسبه فیتنس زمانبدنی کلاس استفاده شده اند. بصورت زیر:
• هر کلاس می تواند از ۰ تا ۵ امتیاز داشته باشد
• اگر کلاسی از یک اتاق خالی استفاده کرد به امتیازش اضافه می شود
• اگر کلاسی نیاز به کامپیوتر داشت و در اتاقی قرار گرفت که کامپیوتر دارد، امتیاز کلاس افزایش می یابد
• اگر کلاسی در یک اتاقی قرار گیرد که صندلی به اندازه کافی دارد امتیازش افزایش می یابد
• اگر استاد کلاس دیگری در آن زمان نداشته باشد بازهم امتیاز کلاس افزایش می یابد
• آخرین چیزی که چک می شود این است که اگر هر گروه دانشجویی که در یک کلاس شرکت کرده در همان زمان کلاس دیگری نداشته باشد امتیاز کلاس افزایش داده می شود.
• اگر کلاسی هر یک از این قوانین را در هر اسلات زمانی-مکانی که اشغال می کند در نظر نگیرد، امتیازش افزایش نمی یابد.
• امتیاز کلی زمانبندی کلاس مجموع امتیازات همه کلاس هاست.
• fitness value بصورت schedule_score/maximum_score محاسبه می شود و maximum_score برابر با تعداد کلاس ها ضرب در ۵ است.
fitness value ها با اعداد اعشاری (با دقت یک رقم اعشار) در محدوده ۰ تا ۱ نمایش داده می شوند.

Crossover
عملیات crossover داده های داخل hash map دو والد را ترکیب می کند و سپس برداری از اسلات ها با توجه به محتوای hash map جدید ایجاد می کند. crossover، hash mapهای هر دو والد رابه بخش هایی با اندازه تصادفی تقسیم می کند. تعداد بخش ها با تعداد نقاط crossover (به علاوه یک) در پارامترهای کروموزوم تعیین می شود. سپس متناوبا بخش های والدین را به کروموزوم جدید کپی می کند و یک بردار جدید از اسلات ها ایجاد می کند.

// Performes crossover operation using to chromosomes
// and returns pointer to offspring
Schedule* Crossover(const Schedule& parent2) const;
Mutation
عملیات میوتیشن بسیار ساده است. یک کلاس را به طور تصادفی می گیرد و آن را به یک اسلات دیگر که بصورت تصادفی انتخاب شده منتقل می کند. تعداد کلاس هایی که قرار است در یک عملیات واحد انتقال یابند با اندازه میوتیشن در پارامترهای کروموزوم تعیین می شود.

// Performs mutation on chromosome
void Mutation();
Algorithm
الگوریتم ژنتیک بسیار ساده است. برای هر نسل، دو عملیات اصلی انجام می دهد:
۱٫ بصورت تصادفی N جفت والد از بین جمعیت موجود می گیرد و N کروموزوم جدید با اجرای عملیات crossover بر روی جفت والدها ایجاد می کند.
۲٫ بصورت تصادفی N کروموزوم را از بین جمعیت فعلی انتخاب می کند و آنها را با کروموزوم های جدید جایگزین می کند. اگر این کروموزوم ها جزء بهترین کروموزوم های داخل جمعیت باشند الگوریتم آنها را انتخاب نمی کند.
و این دو عمل انقدر تکرار می شود تا بهترین کروموزوم ها به fitness value ای مساوی ۱ برسند (یعنی تمام کلاس های داخل زمانبندی ملزومات را رعایت کنند). الگوریتم ژنتیک M تا از بهترین کروموزوم های داخل جمعیت را حفظ میکند و تضمین می کند که آنها تازمانی که در بین بهترین کروموزوم ها باشند جایگزین نخواهند شد.

// الگوریتم ژنتیک
class Algorithm
{

private:

// جمعیت کروموزومها
vector<Schedule*> _chromosomes;

// نشان می دهد که آیا کروموزوم به جمعیت بهترین کروموزوم ها تعلق دارد یا خیر
vector<bool> _bestFlags;

// شاخص های بهترین کرومزومها
vector<int> _bestChromosomes;

// تعداد بهترین کروموزوهایی که اخیرا در گروه کروموزوم های برتر قرار گرفته اند
int _currentBestSize;

// تعداد کروموزوم هایی که با کروموزوم های نسل جدید جایگزین شده اند
int _replaceByGeneration;
ScheduleObserver* _observer;

// پروتوتایپ کروموزوم ها در جمعیت
Schedule* _prototype;

// نسل فعلی
int _currentGeneration;

// حالت اجرای الگوریتم
AlgorithmState _state;

// همگام سازی اجرای الگوریتم ها
CCriticalSection _stateSect;

static Algorithm* _instance;

// همگم سازی تولید و انهدام نمونه ها
static CCriticalSection _instanceSect;

public:
static Algorithm& GetInstance();

//آزادسازی حافظه مورد استفاده
static void FreeInstance();

// شروع الگوریتم ژنتیک
Algorithm(int numberOfChromosomes,
int replaceByGeneration,
int trackBest,
Schedule* prototype,
ScheduleObserver* observer);

// آزادسازی منابع استفاده شده
~Algorithm();

// شروع و اجرای الگوریتم
void Start();

// متوقف ساختن اجرای الگوریتم
void Stop();

// برگرداندن نشانگر به بهترین کروموزوم نسل
Schedule* GetBestChromosome() const;

// برگرداندن نسل فعلی
inline int GetCurrentGeneration() const { return _currentGeneration; }

// برگرداندن نشانگر به ناظر الگوریتم
inline ScheduleObserver* GetObserver() const { return _observer; }

private:

// سعی در اضافه نمودن کروموزوم ها به گروه بهترین کروموزوم ها
void AddToBest(int chromosomeIndex);

// اگر کروموزم به گروه بهترین کروموزوم ها تعلق داشت true بر می گرداند
bool IsInBest(int chromosomeIndex);

// پاک سازی گروه بهترین کروموزوم ها
void ClearBest();

};
Observing
کلاس ScheduleObserver رویدادهایی را که توسط الگوریتم ژنتیک فعال می شوند کنترل می کند. این کلاس به پنجره نمایشی اپلیکیشن پیام می فرستد. به علاوه می توانید با فراخوانی متد WaitEvent() تا زمانی که اجرای الگوریتم تمام نشده یا متوقف نشده thread مربوط به فراخواننده را بلاک کنید.
// هندل کردن رویدادهایی که زمانی که الگوریتم بهترین کروموزم را پیدا می کند رخ می دهند
void NewBestChromosome(const Schedule& newChromosome);

// هندل کردن رویدادهای زمانی که حالت اجرا تغییر می کند
void EvolutionStateChanged(AlgorithmState newState);

// بلاک کردن رشته فراخوانی
inline void WaitEvent() //…
اگر بخواهیم متد NewBestChromosome را تغییر دهیم باید اگر می خواهیم بهترین کروموزوم رانگه دارید ، با استفاده از متد MakeCopy در کلاس Schedule از آن یک هارد کپی تهیه کنید زیرا الگوریتم می تواند آن کروموزوم را در نسل بعد پاک کند.
Configuration File
انواع آبجکتها:
۱٫ professor (#prof tag) – توصیف اساتید.
۲٫ course (#course tag) – توصیف درس.
۳٫ room (#room tag) – توصیف اتاق کلاس.
۴٫ group (#group tag) – توصیف گروه دانشجویی.
۵٫ course class (#class tag) –توصیف یک کلاس و برقراری ارتباط میان استاد، درس و دانشجو.
هر آبجکتی با تگ مربوط به خود شروع می شود و با تگ #end خاتمه می یابد. همه تگ ها باید در خطوط جداگانه باشند. در بدنه آبجکت، هر خط حاوی تنها یک کلید و مقدار (اتریبیوت) است که با کاراکتر = جدا شده است. هر اتریبیوت تنها باید یک بار مشخص شود، به جز اتریبیوت گروه در آبجکت #group که می تواند چندین اتریبیوت گروه بگیرد. تگ ها و نام های کلیدی به حروف بزرگ و کوچک حساس هستند.

در ادامه لیستی از اتریبیوت های آبجکت ها آورده شده است:
#prof
o id (number, اجباری) – آی دی استاد.
o name (string, اجباری) – نام استاد.
۲٫ #course
o id (number, اجباری) – آی دی درس.
o name (string, اجباری) – نام درس.
۳٫ #room
o name (string, اجباری) – نام اتاق.
o size (number, اجباری) – تعداد صندلی های اتاق.
o lab (boolean, اختیاری) –مشخص می کند که کلاس یک لابراتوار است (کامپیوتر دارد) یا خیر. اگر پر نشود
مقدار پیش فرض در نظر گرفته می شود یعنی faulse
۴٫ #group
o id (number, اجباری) –آی دی گروه دانشجویی.
o name (string, اجباری) – نام گروه دانشجویی.
o size (number, اجباری) – تعداد دانشجویان هر گروه.
۵٫ #class
o professor (number, اجباری) –
آی دی استاد; ایجاد ارتباط استاد با کلاس.
o course (number, اجباری) –
آی دی درس; ایجاد ارتباط درس با کلاس.

o group (number, اجباری) –
آی دی گروه دانشجویی; ایجاد ارتباط گروه دانشجویی با کلاس; هر کلاس می تواند به چندین گروه دانشجویی مرتبط شود

o duration (number, اختیاری) –
طول زمان کلاس (به ساعت)، اگر تعیین نشود مقدار پیش فرض ۱ است
o lab (boolean, اختیاری) –
اگر کلاس نیاز به کامپیوتر داشته باشد true است اگر تعیین نشود مقدار پیش فرض که false است در نظر گرفته می شود
آبجکت های استاد، گروه دانشجویی و درس باید قبل از اینکه به آبجکت کلاس درس مرتبط شوند تعیین شده باشند.
نمونه ای از تنظیمات داخل فایل GaSchedule.cfg یا configuration file:
در فایل تنظیماتی که به برنامه به عنوان ورودی می دهیم ابتدا نام دانشجویان و id آنها، سپس نام درس ها و id مربوط به هر یک از آنها سپس نام کلاس ها اینکه لابراتوار هستند یا خیر (کامپیوتر دارند یا ندارند) و ظرفیت آنها (تعداد صندلی هایشان) و در نهایت اینکه برای هر پروفسور چه کلاسی با چه مدت زمانی و برای چه گروهی در نظر گرفته شده است، وارد می کنیم.

#course
id = 1
name = Introduction to Programming
#end

#course
id = 2
name = Introduction to Computer Architecture
#end

#course
id = 3
name = Business Applications
#end

#group
id = 1
name = 1O1
size = 19
#end

#group
id = 2
name = 1O2
size = 19
#end

#class
professor = 1
course = 1
duration = 2
group = 1
group = 2
#end

#class
professor = 1
course = 1
duration = 2
group = 3
group = 4
#end

#class
professor = 9
course = 1
duration = 3
group = 1
lab = true
#end

#class
professor = 9
course = 1
duration = 3
group = 2
lab = true
#end
parse کردن فایل configuration:
parse کردن یک فایل تنظیمات توسط کلاس Configuration انجام می شود. متد ParseFile فایل تنظیمات را باز کرده و parse می کند. این متد به دنبال تگ های آبجکت های می گردد و متد مناسب برای یک parsing object را فراخوانی می کند. متد ParseFile آبجکتی که قبلا parse شده را پاک نیز می کند.
public:
void ParseFile(char* fileName);

private:

Professor* ParseProfessor(ifstream& file);
StudentsGroup* ParseStudentsGroup(ifstream& file);
Course* ParseCourse(ifstream& file);
Room* ParseRoom(ifstream& file);
CourseClass* ParseCourseClass(ifstream& file);
برای parse کردن فایل:

Configuration::GetInstance().ParseFile( “GaSchedule.cfg” );

آبجکت های parse شده در hash map ای به جز hash map مربوط به کلاس های درسی نگهداری می شوند تا بتوان سریع و به آسانی به آنها دسترسی داشت.

private:

hash_map<int, Professor*> _professors;
hash_map<int, StudentsGroup*> _studentGroups;
hash_map<int, Course*> _courses;
hash_map<int, Room*> _rooms;

list<CourseClass*> _courseClasses;

کلاس Configuration شامل متدهایی برای بازیابی اطلاعات parse شده و آبجکت ها نیز می باشد.

public:
inline Professor* GetProfessorById(int id) //…
inline int GetNumberOfProfessors() const //…

inline StudentsGroup* GetStudentsGroupById(int id) //…
inline int GetNumberOfStudentGroups() const //…

inline Course* GetCourseById(int id) //…
inline int GetNumberOfCourses() const //…

inline Room* GetRoomById(int id) //…
inline int GetNumberOfRooms() const //…

inline const list<CourseClass*>& GetCourseClasses() const //…
inline int GetNumberOfCourseClasses() const //…

در زیر نتیجه اجرای برنامه و جدول زمانی به دست آمده در نسل های مختلف را می توان دید:

درشکل فوق fitness value برابر با ۱ را داریم یعنی یکی از بهترین Solution ها را به دست آورده ایم. با ۱۰۳۰۳ تکرار یا نسل.

در نسل ۵۸۷ مقدار فیتنسی نزدیک به ۱ و معادل با ۰٫۹۴۸۱۴۸ را داریم.

همان طور که مشاهده می شود در نسل ۴۰۹۹ مقدار فیتنس کمی بیشتر از حالت قبل است و به ۰٫۹۸۵۱۸۵ رسیده است. با مقایسه این نسل و نسلی که فیتنس ۱ دارد دیده می شود که کلاس های جمعه، دوشنبه و سه شنبه تغییر خواهند کرد.
مراجع:
An Evolutionary Algorithm for High School Timetabling, Jonathan Domrös -Jörg Homberger, Practice and Theory of Automated Timetabling (PATAT 2012), 29-31 August 2012, Son, Norway

An Informed Genetic Algorithm For The Examination Timetabling Problem, Pillay N., Banzhaf W., Journal of Applied Soft Computing, Vol. 10, 2010, pp. 457–۴۶۷٫

طراحي جدول زمانبندي خودكار براي دروس دانشگاهي با استفاده از الگوريتم هاي ژنتيك، نشريه علمي پژوهشي فناوري آموزش، سال چهارم، جلد ۴
http://www.codeproject.com/Articles/23111/Making-a-Class-Schedule-Using-a-Genetic-Algorithm

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.3342&rep=rep1&type=pdf

http://www.cs.le.ac.uk/~syang/Papers/MISTA09.pdf

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

It is main inner container footer text