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

نیروی انسانی میتواند مسأله را در راستای جوابهای مناسبتر هدایت کند، در حالی که روشهای کامپیوتری به صورت کامل، قادر به یافتن این جوابهای مناسب نیستند. به همین دلیل، بیشتر سیستمهای حل، امکان تغییر و دستکاری در جواب را برای کاربر فراهم میسازند.
در این تحقیق مدیر گروه دانشکده به عنوان کاربر سیستم در نظر گرفته شده است، مدیر گروه با ۱۰ بار اجرای مدل با الگوریتمهای فراابتکاری، با طرح غربالگری۳ برنامه برتر از ۱۰ برنامه را انتخاب، و با فرآیند تصمیمگیری AHP سه برنامه را رتبهبندی و برترین برنامه را انتخاب میکند. در صورت لزوم، تعدیلات نهایی (دستی) نیز بر روی گزینه بدست آمده از فرایند AHP، توسط مدیر گروه انجام میشود.
شکل (۳-۴) فلوچارت فرآیند تصمیمگیری را نشان میدهد.

پیادهسازی AHP در فرآیند یک تصمیم گیری شامل ۵ فاز است:
۳-۱۰-۱- درخت سلسه مراتبی
در این فاز باید عواملی که در تصمیمگیری مهم میباشند را در قالب یک درخت تصمیمگیری بصورت سلسه مراتبی بیان کنیم که سطح اول آن هدف مسأله، سطح دوم معیارها و سطح سوم گزینههای مورد بررسی است. هدف مسأله ما تهیه و تنظیم جدول زمانی دانشگاهی مطلوب، معیارهای سنجش مسأله، ترجیحات اساتید، دانشجویان و دانشگاه است. هر کدام از این ترجیحات در قالب محدودیتهای نرم سنجیده میشوند، و گزینهها نشان دهنده برنامه دروس حاصل از خروجی الگوریتمهای فراابتکاری در مرحله قبل است. شکل (۳-۵) فلوچارت درخت سلسه مراتبی مسأله را نشان میدهد.

۳-۱۰-۲- انجام مقایسات زوجی
در AHP عناصر هر سطح با عنصر مربوط به خود در سطح بالاتر، بصورت زوجی مقایسه میشود. به طوری که در این مرحله میبایست تمامی معیارها با همدیگر در یک ماتریس، و گزینهها نسبت به هر یک از معیارها، به صورت زوجی مقایسه شوند. در مقایسات زوجی تصمیمگیرندهها، برای امتیازدهی از جدول (۲-۳) استفاده شده است. برای مقایسه زوجی معیارها، از یک دانشجو، یک استاد و مدیر گروه به عنوان نماینده دانشگاه استفاده شده است. و مقایسه زوجی گزینهها نسبت به هر یک از معیارها، توسط مدیر گروه انجام گرفته است.

۳-۱۰-۳- محاسبه ضرایب اهمیت
پس از بدست آوردن ماتریسهای زوجی در مرحله قبل، میبایست ضریب اهمیت معیارها و گزینهها نسبت به هر یک از معیارها در هر ماتریس زوجی محاسبه گردد. ما از روش میانگین هندسی برای محاسبه ضرایب استفاده نمودهایم.

۳-۱۰-۴- تعیین امتیاز نهایی گزینهها
در این مرحله با فرمول (۳-۱۰)، امتیاز هر گزینه جهت اولویتبندی محاسبه میشود:
(۳- ۱۰)

که در آن وزن گزینه i نسبت به معیار j و وزن معیار j است.

۳-۱۰-۵- بررسی سازگاری سیستم
یکی از مزیتهای فرآیند تحلیل سلسه مراتبی امکان بررسی سازگاری در قضاوتهای انجام شده برای تعیین ضریب اهمیت معیارها است. به عبارت دیگر در تشکیل ماتریس مقایسه زوجی معیارها چقدر سازگاری در قضاوتها رعایت شده است؟ گامهای محاسبه این شاخص در بخش۲-۹-۵ تشریح شده است. به دلیل اینکه ما از روش میانگین هندسی برای محاسبه ضرایب استفاده کردهایم به جای محاسبه از L به عنوان روش تقریبی از فرمول (۳-۱۱) استفاده نمودیم [۲]:
(۳- ۱۱)

که در آن برداری است که از ضرب ماتریس مقایسه زوجی معیارها در بردار (بردار وزنی معیارها) به دست میآید.

۳-۱۱- مدل ریاضی چند هدفه
در بخش مدل تک هدفه، تابع پنالتی مورد استفاده برای هر یک از محدودیتهای نرم، به صورت شمارش تعداد تخطی استفاده شده، که در آن نوع و مقدار تخطی در نظر گرفته نشده است. در این بخش تابع پنالتی مورد استفاده، مقدار تخطی از محدودیتهای نرم را در نظر میگیرد. با توجه به اینکه دیمانسیون تابع پنالتی در این بخش برای هر یک از محدودیتها متفاوت است، تابع هدف مدل در دوسطحf1(x) و f2(x) در نظر گرفته شده است. توابعی که دیمانسیون آنها دوره زمانی است در تابع هدفf1(x) و توابعی که دیمانسیون آنها جلسات درسی است در f2(x) آمده است. مدل ریاضی مسأله دو هدفه در فرمولبندی (۳-۱۲) تا (۳-۲۰) نشان داده شده است:

(۳- ۱۲)

(۳- ۱۳)

(۳- ۱۴)

(۳- ۱۵)

(۳- ۱۶)

(۳- ۱۷)

(۳- ۱۸)

(۳- ۱۹)

(۳- ۲۰)

(۳- ۲۱)

تابع هدف (۳-۱۲) بر اساس محدودیتهای نرمS1 ، S2،S4 مسأله و تابع هدف (۳-۱۳) بر اساس محدودیتهای نرمS3 ، S5،S6 ، S7، S8 مسأله بیان شده است. ضرایب wS1, . . . , wS8بکار رفته در دو تابع هدف نیز نشان دهنده وزن و اهمیت هر یک از محدودیتهای نرم (جریمه تخطی برنامه از هر یک از محدودیتهای نرم متناظر) میباشد. مقدار ضرایب به ترتیب ۳، ۱، ۱، ۲، ۲، ۲، ۲، ۲ در نظر گرفته شده است.
محدودیتهای (۳-۱۴) تا (۳-۲۰) بر اساس محدودیتهای سخت مسأله فرموله شده که تطابق هر یک از آنها بدین شرح است: محدودیتهای (۳-۱۴) تا (۳-۱۸) مطابق با H5 ، … ،H2،H1 محدودیتهای (۳-۱۹) و (۳-۲۰) مطابق با H6 و محدودیت (۳-۲۱) متناظر با H7 میباشد.

۳-۱۲- الگوریتم ژنتیک چند هدفه (NSGA II)
در این بخش عناصر الگوریتم ژنتیک با مرتب سازی نامغلوب پیشنهادی توضیح داده میشود. بسیاری از عناصر این الگوریتم، مانند عملگر انتخاب و یا نحوه انجام نخبهگرایی به طور کلی برای تمام الگوریتمهای ژنتیک با مرتب سازی نامغلوب یکی است اما عناصری مانند عملگر تقاطع و جهش باید به تناسب مسأله انتخاب شوند.

۳-۱۲-۱- نحوه نمایش جواب و جمعیت اولیه
نحوه نمایش جواب در این الگوریتم همانند نما
یش جواب در الگوریتم جستجوی ممنوعه است که در بخش۳-۸-۱ توضیح داده شده است. هر ماتریس برنامه جلسات درسی به عنوان کروموزوم، و هر یک از درایههای ماتریس که یک جلسه درسی به یک کلاس و دوره زمانی تخصیص داده شده به عنوان یک ژن در نظر گرفته شده است [۲۹].
جمعیت اولیه شامل مجموعهای با اندازه از پیش تعیین شده از نقاط جستجو (کروموزومها) است. در الگوریتم ما جمعیت اولیه به صورت تصادفی و همانند روش تشریح شده در بخش ۳-۸-۲ تولید میشود.
۳-۱۲-۲- انتخاب
برای تمام الگوریتمهای ژنتیک با مرتبسازی نامغلوب از عملگر انتخاب تورنمنت دو-دویی استفاده میشود. این عملگر به این ترتیب است که از جمعیت کنونی دو کروموزوم به طور تصادفی انتخاب شده، با هم مقایسه میشوند و هر کدام که بهتر باشد، انتخاب میشود. معیارهای انتخاب در NSGA II در درجه اول، رتبه جواب و در درجه دوم فاصله تراکمی مربوط به جواب است. هر چقدر رتبه جواب کمتر باشد و دارای فاصله تراکمی بیشتری باشد، مطلوبتر است.

۳-۱۲-۳- تقاطع
جستجوی فضا با تولید کروموزومهای جدید از کروموزومهای قبلی صورت میگیرد. عملگر تقاطع از دو کروموزوم انتخاب شده به صورت تصادفی، با احتمال مشخص و انجام عملیات در طول رشتهها کروموزومهای جدید میسازد، به طوری که ویژگیهای ساختار والدین و در ساختار فرزندان ترکیب شود.
فرایند تقاطع در الگوریتم ما بدین شرح است: بعد از فرایند انتخاب دو والد، از هر یک از کروموزومهای والد، یک دوره زمانی به صورت تصادفی انتخاب میکنیم، و با جابجایی ژنهای دو دوره زمانی والدها با هم، فرزندان تشکیل میشود. جهت شدنی ماندن فرزندان در جابجایی ژنها شرایط زیر باید رعایت شود:
هر درس (ژن) می تواند جابجا شود، تنها اگر دوره زمانی و کلاس متناظر آن خالی باشد.
هیچ تداخلی بین درس (ژن) انتقالی و دروس زمانبندی شده قبلی در آن دوره زمانی نباشد.
شکل (۳-۶) مثالی از این فرآیند را نشان میدهد. در این شکل دو ماتریس اول کروموزوم والدین هستند، و ماتریس سوم و چهارم روند تولید فرزندان را نمایش میدهد. دوره زمانی ۲ و ۸ از والد ۱ و والد ۲ به صورت تصادفی انتخاب شده است. فرزند ۱ از کپی کردن ژنهای دوره زمانی ۸ والد ۲ در دوره زمانی ۲ والد ۱ با شرایط ذکر شده تولید میشود. همچنین فرزند ۲ از کپی کردن ژنهای دوره زمانی ۲ والد ۱ در دوره زمانی ۸ والد ۲ با شرایط ذکر شده تولید میشود. در مرحله بعدی دروس تکراری باید از ماتریس فرزندان حذف شود. درس ۸ و ۲۲ در ماتریس فرزند ۱ و درس ۶ از ماتریس فرزند ۲ حذف میشود [۲۹].

۳-۱۲-۴- جهش
به ازای انواع سیستمهای کدینگ برای کروموزومها، عملگرهای متفاوتی برای جهش استفاده میشود. عملگر جهش با احتمال مشخصی روی یک یا چند ژن کروموزوم که به طور تصادفی انتخاب شده تغییراتی ایجاد میکند و مقدار آن را تغییر میدهد. این عملگر به عنوان یک عملگر پایهای برای حفظ پراکندگی جمعیت در نظر گرفته میشود، به طوری که قسمتهای جدیدی از فضا که عملگرهای انتخاب و تقاطع به آن دسترسی پیدا نکرده نیز جستجو شود. فرآیند جهش در الگوریتم ما بدین گونه است که به صورت تصادفی یک جلسه درسی (ژن) انتخاب و به یک دوره زمانی و یک کلاس خالی که به طور تصادفی انتخاب شده است، منتقل میشود.
شکل (۳-۷) مثالی از این فرآیند را نشان میدهد. ماتریس اول والد و ماتریس دوم فرزند است. این فرزند از طریق انتخاب تصادفی درس ۲۴ و جهش آن از کلاس ۱ و دوره زمانی ۹ به دوره زمانی۵ و کلاس ۳ تولید شده است [۲۹].

۳-۱۲-۵- معیار توقف
برای هر الگوریتم ابتکاری باید معیاری جهت توقف جستجو تعریف شود. به این معیارها شروط پایانی میگویند. معیار توقف الگوریتم ما ماکزیمم تعداد تکرار در نظر گرفته شده است.
فلوچارت الگوریتم NSGA II بکار رفته در این تحقیق در شکل (۳-۸) نشان داده شده است.

۳-۱۳- الگوریتم جستجوی ممنوعه چند هدفه (MOTS)
در این بخش از یک الگوریتم جستجوی ممنوعه چند هدفه ابتکاری ، که فلوچارت آن در شکل (۳-۹) آمده است، استفاده شده است. این الگوریتم برای حل مدل چند هدفه، پیشنهاد شده است. این الگوریتم در دو فاز طراحی شده است، در فاز اول الگوریتم به دنبال مینیمم کردن تابع هدف اول و در فاز دوم، الگوریتم به دنبال مینیمم کردن تابع هدف دوم است. در هر فاز الگوریتم از بهترین جواب بدست آمده در فاز قبلی به عنوان جواب اولیه، شروع میکند. در این الگوریتم برای تغییر فازها یا به عبارت دیگر حرکت از فاز اول به فاز دوم و بالعکس، در طول اجرای الگوریتم، از سیاست چرخ رولت پویا استفاده شده است. الگوریتم در هر تکرار با استفاده از چرخ رولت، یک مقدار احتمال، برای هر یک از توابع هدف مطابق با فرمولهای ۳-۲۲ و ۳-۲۳ محاسبه میکند. در هر تکرار، تابع هدفی به عنوان معیار ارزیابی انتخاب میشود که احتمال آن بزرگتر باشد.
(۳-۲۲)

(۳-۲۳)

در فرمولهای بالا و نشان دهنده احتمال بکارگیری توابع هدف اول و دوم در هر تکرار است. نشان دهنده جزء صحیح، تعداد کل تکرارها، تعداد تکرارهای گذشته (شماره تکرار) در هر تکرار و پارامتری است که تعداد تغییرات احتمالی فازهای الگوریتم را در کل تکرارها بیان میکند.
تمام عناصر و سیاستهای بکار گرفته شده در هر فاز از این الگوریتم، همانند جدول (۳-۳) میباشد. جوابهای حاصل از هر تکرار الگوریتم، در آرشیو پاراتو ذخیره و پاراتوی نامغلوب نهایی همانند الگوریتم NSGA II محاسبه میشود.

۳-۱۴- جمعبندی

در این فصل مدلهای تک هدفه و دو هدفه ارائه شده برای مسأله
جدول زمانی دروس دانشگاهی به صورت کامل تشریح شده است. با توجه به NP-Hard بودن مسأله، برای حل مدلها از الگوریتمهای فراابتکاری استفاده شده است. در مدل تک هدفه از الگوریتم جستجوی ممنوعه (TS) و الگوریتم جستجوی همسایگی متغیر در جستجوی ممنوعه (TS-VNS) برای حل مدل استفاده شده است. با استفاده از فرآیند تصمیمگیری AHP، جدولهای زمانی بدست آمده از الگوریتمهای فرابتکاری، رتبهبندی و گزینه برتر انتخاب میشود. در مدل دو هدفه از الگوریتم ژنتیک چند هدفه (NSGA II) و الگوریتم جستجوی ممنوعه چند هدفه (MOTS) استفاده شده است. در این فصل تمام عناصر و پارامترهای الگوریتمها بکار رفته تشریح شده است.

فصل چهارم
محاسبات و یافتههای تحقیق

دیدگاهتان را بنویسید