پایان نامه با کلید واژگان
مدل ریاضی، معیار ارزیابی، فرآیند تحلیل، استراتژی ها

پایان نامه با کلید واژگان مدل ریاضی، معیار ارزیابی، فرآیند تحلیل، استراتژی ها

دی ۸, ۱۳۹۷ 0 By mitra1--javid

ی و مقالات مربوط جمعآوری شده است. مسأله از طریق توسعه مدل ارائه شده توسط آلاداگ۷۵ و همکارانش در سال ۲۰۰۹ [۲۵]، تعریف شده است.

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

۳-۵- مدل ریاضی
محدودیتهای مسأله به دو دسته سخت و نرم تقسیم میشوند. محدودیتهای نرم از طریق تابع پنالتی ارزیابی میشوند، و تابع هدف مدل ریاضی مسأله از مجموع وزن دهی شده توابع پنالتی محدودیتهای نرم تشکیل میشود و محدودیتهای سخت مسئله، محدودیتهای مدل ریاضی را تشکیل میدهند.

۳-۵-۱- محدودیتهای سخت
محدودیتهای سخت مسأله عبارتند از:
(H1): همه دروس باید مطابق با تعداد دورههای زمانی مورد نیاز، زمانبندی شود (زمانبندی کامل تمام دروس).
(H2): هیچ استادی نمیتواند دو درس را بطور همزمان تدریس کند (تداخل برنامه اساتید).
(H3): باید بین جلسات هر درس حداقل یک روز فاصله باشد.
(H4): هیچ کلاسی نمیتواند به طور همزمان به دو درس تخصیص داده شود (تداخل برنامه کلاسها).
(H5): هر درسی باید به کلاس متناسب با نیازش تخصیص داده شود.
(H6): باید همه دورههای زمانی ممنوع و از قبل تخصیص داده شده به دانشجویان، استاد و کلاس در نظر گرفته شود.
(H7): جلسات درسی یک گروه درسی مشابه نباید تداخل داشته باشد (تداخل برنامه دانشجویان).

۳-۵-۲- محدودیتهای نرم
و محدودیتهای نرم مسأله عبارتند از:
(S1): کلاسهای درسی دانشجویان تا جایی که امکان دارد باید فشرده و بیکاری آنها حذف شود.
(S2): نباید ساعات درسی دانشجویان در هر روز، بیش از حد تعیین شده، باشد.
(S3): دانشجویان نباید در یک روز فقط یک درس داشته باشند.
(S4): اساتید نباید به دورههای زمانی که برایشان نامطلوب است تخصیص داده شوند.
(S5): باید تعداد دانشجویان با ظرفیت کلاس تخصیص داده شده همخوانی داشته باشد.
(S6): تمام جلسات یک درس باید در یک کلاس مشابه تشکیل شود.
(S7): تمام جلسات یک درس در دورههای زمانی مشابه برگزار شود.
(S8): به دورههای زمانی پایان روز، درسی تخصیص داده نشود.
محدودیتهای S1، S2 وS3 مربوط به ترجیحات دانشجویان، محدودیتهای S4 مربوط به ترجیحات اساتید و محدودیتهای S5، S6 و S8مربوط به ترجیحات دانشگاه و S7 نیز مربوط به ترجیحات دو گروه دانشجویان و اساتید است.

۳-۵-۳- پارامترها و مجموعههای مدل
با توجه به تعریف و شرایط مسأله، در مدلسازی از پارامترها و مجموعهها جدول (۳-۱) استفاده شده است.

جدول۳-۱٫ پارامترها و مجموعهها

مجموعه دروس

مجموعه جلسات

امjام درس k  جلسه

مجموعه گروه درسی

مجموعه جلسات گروه درسی

امiام گروه درسی jجلسه

مجموعه اساتید

امk مجموعه جلسات درسی استاد

مجموعه دورههای زمانی

امl مجموعه دورههای زمانی روز

مجموعه روزها

امi مدت زمان جلسه

مجموعه کلاسها

امr مجموعه کلاسهای نوع

امندr جلسات درسی که نیازمند کلاس نوع

انواع کلاسها

امr تعداد کلاس های نوع

مجموعه جلسات درسی که از قبل تخصیص داده شده

امiمجموعه دورههای زمانی تخصیص داده شده به جلسه

امi مجموعه دورههای زمانی ممنوع شده برای جلسه

۳-۵-۴- متغیر تصمیم
در این مدل تنها از یک متغیر تصمیم استفاده شده است:
اگر جلسه درسی i به دوره زمانیt در کلاس aتخصیص داده شود

در غیر اینصورت

۳-۶- مدل ریاضی تک هدفه
مدل ریاضی مسأله تک هدفه در فرمولبندی (۳-۱)-(۳-۹) نشان داده شده است:

(۳-۱)

(۳-۲)

(۳-۳)

(۳-۴)

(۳-۵)

(۳-۶)

(۳-۷)

(۳-۸)

(۳-۹)
۳-۷- تشریح مدل ریاضی
تابع هدف (۳-۱) بر اساس محدودیتهای نرم مسأله بیان شده است. اجزای fS1(x), . . . , fS8(x) تابع هدف، مطابق با محدودیتهای S8، … ،S2،S1 است و ضرایب wS1, . . . , wS8نیز نشان دهنده وزن و اهمیت هر یک از محدودیتهای نرم (جریمه تخطی برنامه از هر یک از محدودیتهای نرم متناظر) میباشد. مقدار ضرایب w به ترتیب ۳، ۱، ۱، ۲، ۲، ۲، ۲، ۲ در نظر گرفته شده است.
محدودیتهای (۳-۲) تا (۳-۹) بر اساس محدودیتهای سخت مسأله فرموله شده که تطابق هر یک از آنها بدین شرح است: محدودیتهای (۳-۲) تا (۳-۶) مطابق با H5 ، … ،H2،H1، محدودیتهای (۳-۷) و (۳-۸) مطابق با H6 و محدودیت (۳-۹) متناظر با H7 میباشد.

۳-۸- الگوریتم جستجوی ممنوعه (TS)
الگوریتم جستجوی ممنوعه یکی از الگوریتمهای فراابتکاری است که با یک رویه تکرار شونده، با یک جواب شدنی شروع شده و با انجام حرکتهایی به سمت یک بهینه محلی هدایت میشود. از اصول اساسی به کار رفته در این الگوریتم میتوان مجاز دانستن حرکتهایی که بهبودی به همراه ندارند اما ممکن است جواب را به سمت جواب بهینه سراسری هدایت کنند، استفاده از لیست ممنوعه و استراتژیهای تنوعبخشی جهت جلوگیری از قرار گرفتن الگوریتم در جو
اب بهینه محلی و استفاده از استراتژی تقویت جهت همگرایی به سمت جواب بهینه سراسری، را نام برد. عناصر و سیاستهای بکار گرفته شده ما در این الگوریتم به شرح زیر است:

مطلب مشابه :  پایان نامه رایگان دربارهانرژي، معادله‌ي، چگالي، پتانسيل

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

جدول ۳-۲٫ مشخصات ماتریس های جواب
درایه ها
ارتفاع ماتریس
ستون اتریس
سطر ماتریس
نام ماتریس جواب
۱-۰
جلسات درسی
دوره زمانی
کلاس
برنامه جلسات درسی
کد جلسات درسی

دوره زمانی
کلاس
برنامه جلسات درسی
کد دروس

دوره زمانی
کلاس
برنامه دروس
کد اساتید

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

دوره زمانی
کلاس
برنامه دانشجویان

۳-۸-۲- تولید جواب اولیه
در الگوریتم پیشنهادی، استراتژی تولید جواب اولیه به صورت تصادفی است. اما با توجه به نوع مسأله و محدودیتهای موجود، بدست آوردن جواب اولیه شدنی به صورت تصادفی در یک مرحله غیر ممکن است. از اینرو ما از یک الگوریتم ابتکاری تکاملی برای تولید جواب اولیه استفاده کردهایم. در هر تکرار از این الگوریتم، یک جلسه درسی به صورت تصادفی انتخاب و به یک کلاس و دوره زمانی که به صورت تصادفی انتخاب شده تخصیص داده میشود. الگوریتم در هر مرحله، شدنی بودن تخصیص را بررسی و تا جایی که تمام جلسات دروس زمانبندی و یک جدول زمانی شدنی بدست آید، ادامه پیدا میکند.

۳-۸-۳- همسایگی
در الگوریتم پیشنهادی در هر تکرار، برای انتخاب همسایگی، از استراتژی همسایگی آمده در شکل (۳-۲٫ الف) استفاده شده است. در این استراتژی یک جلسه درسی به صورت تصادفی انتخاب شده و به یک کلاس خالی در یک دوره زمانی، منتقل میشود.

۳-۸-۴- لیست ممنوعه
در الگوریتم مورد استفاده، لیست ممنوعه به صورت گردشی با طول ثابت که درصدی از تعداد جلسات درسی است، در نظر گرفته شده است. به صورتی که در هر تکرار الگوریتم، خصوصیات حرکت صورت گرفته برای تغییر همسایگی در لیست ممنوعه قرار میگیرد. و نحوه خروج از لیست ممنوعه بر اساس روش ۷۶FIFO است.

۳-۸-۵- معیار آرمانی
معیار آرمانی، معیاری است که بر خلاف روال طبیعی الگوریتم و علیرغم اینکه یک حرکت در لیست ممنوعه باشد، ممنوع بودن آن مورد خاص را لغو کرده و اجازه دهد آن متغیر وارد جستجو شود. معیارهای آرمانی انواع مختلفی دارد که ما از معیار آرمانی به شرح زیر استفاده نمودهایم:
حرکتی که جواب حاصل از آن از بهترین جواب تا آن تکرار بهتر باشد.

۳-۸-۶- استراتژی لیست کاندید
به طور کلی در نظر گرفتن کل همسایگیها، جوابهایی با کیفیت بالا تولید خواهد کرد اما ممکن است بسیار زمانبر باشد. از این رو ما در مسائل بزرگ و متوسط از نمونهگیری تصادفی و در مسائل کوچک کل همسایگی را به عنوان لیست کاندید برای جستجو انتخاب کردهایم.

۳-۸-۷- استراتژی تقویت
استراتژی تقویت به معنای یافتن حرکت‌های خوب و افزایش انجام آن حرکت‌ها در الگوریتم است. ما در الگوریتم پیشنهادی از دو حلقه تکرار استفاده کردهایم، به طوری که شروع هر حلقه داخلی از بهترین جواب بدست آمده از حلقههای پیشین است. برای مثال اگر تعداد کل تکرارهای الگوریتم ما ۱۰۰۰ عدد باشد ما آن را به ۱۰ حلقه ۱۰۰تایی تقسیم کردیم، به طوری که نقطه شروع حلقه ۴ بیرونی از بهترین جواب بدست آمده از ۳۰۰ (۱۰۰*۳) تکرار قبلی است.

۳-۸-۸- استراتژی تنوع بخشی
روش‌های مبتنی بر جستجوی محلی ممکن است از کشف و جستجو در مناطق بهتر باز بماند و بنابراین به جواب‌هایی برسد که از جواب بهینه، بسیار دور هستند. استراتژی تنوع‌ بخشی، مکانیزمی است که در جهت حل این مشکل تلاش می‌کند و یکی دیگر از اهداف آن جلوگیری از قرار گرفتن فرآیند حل در یک بهینگی محلی است. ما در الگوریتم پیشنهادی از روش شروع مجدد۷۷ استفاده نمودهایم. به گونهای که اگر بعد از چند تکرار مشخص جواب بهتری بدست نیاید، الگوریتم از یک جواب تصادفی شروع میکند.

مطلب مشابه :  پایان نامه با کلید واژگاننظام مالی، آزادسازی مالی، نهادهای قانونی، توسعه مالی

۳-۸-۹- معیار توقف
برای هر الگوریتم ابتکاری باید معیاری جهت توقف جستجو تعریف شود. به این معیارها شروط پایانی میگویند. معیار توقف الگوریتم ما ماکزیمم تعداد تکرار در نظر گرفته شده است.
خلاصه عناصر و سیاستهای بکار گرفته شده در این الگوریتم در جدول (۳-۳) آمده است.
جدول ۳-۳٫ عناصر الگوریتم جستجوی ممنوعه
استراتژی های بکار گرفته شده
عناصر الگوریتم
بردار x_ita در مسأله جدول زمانی
جوابx.
جواب شدنی تصادفی با الگوریتم تکاملی تصادفی
جواب اولیه
جواب شدنی با توجه به محدودیتهای مسأله
فضای حل
تابع هدف مدل
معیار ارزیابی
در مسائل کوچک کل همسایگی
، در مسائل بزرگ نمونهگیری تصادفی
استراتژی انتخاب کاندید
استراتژی همسایگی(۳-۲٫ الف)
استراتژی ساختار همسایگیها
ذخیره نوع حرکت کاندید به همسایگی منتخب
لیست ممنوعه
انتخاب هر جواب اگر بهترین جواب تا آن مرحله است، حتی اگر آن جواب در لیست ممنوعه باشد
معیار آرمانی
بر اساس بهترین تابع هدف، لیست ممنوعه، معیار آرمانی
انتخاب بهترین همسایگی
شروع مجدد از بهترین جواب
استراتژی تقویت
شروع مجدد با جواب تصادفی شدنی
استراتژی تنوع بخشی
ماکزیمم تعداد تکرار
معیار توقف

فلوچارت الگوریتم در شکل (۳-۱) نشان داده شده است.

۳-۹- الگوریتم جستجوی همسایگی متغیر در جستجوی ممنوعه (TS-VNS)
الگوریتم جستجوی همسایگی متغیر (VNS) یکی از الگوریتمهای فراابتکاری است که بر اساس تغییرات سیستماتیک ساختار همسایگی میباشد و برای جستجوی جواب بهینه در فضای مسائل بهینه سازی ترکیبی بکار میرود. تغییرات سیستماتیک از طریق تغییر موقعیت از یک همسایگی به همسایگی دیگر جواب در حین جستجوی فضای جواب صورت میگیرد. روش VNS ساختارهای همسایگی مناسب و متنوع را به کار میگیرد و به این ترتیب جستجوی جواب را در نواحی مختلف از فضای جواب انجام میدهد و از این طریق، از خطر افتادن در بهینه محلی که در بسیاری از مسائل بهینهسازی ترکیبی محتمل است، جلوگیری میکند.
ما در الگوریتم (TS-VNS) از روش VNS به عنوان استراتژی انتخاب همسایگی در جستجوی ممنوعه استفاده نمودهایم. در این الگوریتم از چهار نوع استراتژی همسایگی استفاده نمودهایم که در شکل (۳-۲) نشان داده شده است. دیگر عناصر و سیاستهای بکار گرفته شده در این الگوریتم همانند جدول (۳-۳) میباشد.

۳-۹-۱- استراتژیهای ساختار همسایگی
استراتژیهای استفاده شده در الگوریتم پیشنهادی عبارت است از:
استراتژی۱: یک جلسه درسی به صورت تصادفی انتخاب شده و به یک کلاس خالی در یک دوره زمانی، منتقل میشود. در شکل (۳-۲٫ الف) درس i انتخاب و به کلاس ۲ که در دوره زمانی ۴ خالی است، تخصیص یافته است.
استراتژی۲: دو جلسه درسی به صورت تصادفی انتخاب شده و کلاس و دوره زمانی آنها با هم تعویض میشود. در شکل (۳-۲٫ ب) دو درس i و j انتخاب و کلاس و دوره زمانی آنها با هم تعویض شده است.
استراتژی۳: دو جلسه درسی به صورت تصادفی انتخاب شده و همزمان هر کدام به یک کلاس خالی در یک دوره زمانی، منتقل میشوند. در شکل (۳-۲٫ پ) دو درس i و i’ همزمان انتخاب، و i به کلاس ۲ در دوره زمانی ۴ و i’ به کلاس ۴ در دوره زمانی ۳ تخصیص یافته است.
استراتژی۴: چهار جلسه درسی به صورت تصادفی انتخاب و جای کلاس و دوره زمانی آنها دو به دو با هم تعویض میشود. در شکل (۳-۲٫ ت) چهار درس i،j ، i’، j’ انتخاب و کلاس و دوره زمانی آنها دو به دو با هم تعویض شده است.

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