K: ضریب ثابت
که در این مسئله ۵۰ K= به کمک سعی و خطا، مناسب تشخیص داده شده است. با توجه به الگوریتم پیشنهادی مشخصاً نتایج حاصل از این آزمون به مراتب بهتر از استفاده از الگوریتم ژنتیک استاندارد است.
نعیمی و منجمی در سال ۱۳۸۸، در مقاله خود با عنوان “الگوریتم چند جمعیتی ژنتیک برای حل مسئله جداول زمانی” تلاش دارند بهجای استفاده از یک جمعیت اولیه و انجام مراحل الگوریتم ژنتیک بر روی آن، جمعیتهای متفاوتی (مانند طایفههای مختلفی از انسانها) ایجاد نماید. ساختار کروموزومی در تمامی این جمعیتها یکسان است؛ اما هر جمعیت میتواند مراحل انتخاب، تکثیر و جهش خاص خود را داشته باشد و پس از گذشت چند نسل، توسط الگوریتمهای نخبهگرا به تبادل کروموزوم بین آنها پرداخته شده است. از آنجایی که کارایی مدلهای مختلف الگوریتم ژنتیک به شدت وابسته به نوع داده ها است، روش به کار گرفته شده در این مطالعه به دلیل امکان استفاده از روش های مختلف در هر جمعیت، خطر قرار گرفتن در ماکسیمم محلی را کاهش میدهد.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

روش تبادل کروموزومها، بهترینهای جمعیتهای دیگر (بر اساس تابع برازش) را به جای بدترین کروموزوم هر جمعیت جایگزین مینماید؛ این روش جایگزینی، مانع از گسترش تاثیرات منفی یک روش نامناسب در سایر جمعیتها شده است.
در این مطالعه دو جمعیت وجود دارد که هر جمعیت دارای ۳۰۰ کروموزوم بوده که جهت افزایش سرعت دستیابی به جواب، ایجاد جمعیت اولیه به صورت کاملاً تصادفی نخواهد بود. برای ایجاد هر کروموزوم ابتدا ترتیبی تصادفی از دروس انتخاب شده و کد آن را در اولین خانه (زمان و کلاس) مناسب با محدودیتهای آن درس قرار داده شدهاست. تابع برازش مورد استفاده در این مطالعه از فرمول ( ۲-۳ ) محاسبه شدهاست.
Fitness = 200 ( w * hard + soft + 1 ) (2-3)
نتایج به دست آمده در این مطالعه نشان میدهد که کارایی این روش به طور متوسط در تمامی نسلها نسبت به حالت تک جمعیتی بهتر است ولی باید دقت داشت که افزایش بیرویه تعداد جمعیت و یا جابهجایی کروموزوم در فواصل نسلی کوتاه به دلیل به وجود آوردن دستورات جانبی زیاد بهره وری را کم میکند.
عباسیان در سال ۱۳۸۹ در مقاله خود با عنوان “حل مسئله زمانبندی کارگاهی چندهدفی انعطافپذیر پویا به وسیله الگوریتم ژنتیک توسعهیافته ” در پی یافتن بهترین مجموعه وزنی بودهاست، وی پس از مدلسازی مسئله، الگوریتم ژنتیک پیشنهادی با کروموزومهای دو بعدی پویا را برای حل، ارائه کردهاست و نتایج حاصل و مقایسه آن با روش های فراابتکاری، نشان دهنده بهبود به میزان بیشتری در میانگین جوابهای به دست آمده در سه سطح انعطافپذیری جزئی، متوسط و کامل است.
امینطوسی و صدوقییزدی در سال ۱۳۸۹، در مقاله خود با عنوان ” کلاسبندی فازی بهینه دانشجویان با بهره گرفتن از یک تابع فازی در حل مسئله برنامه ریزی ژنتیکی دروس هفتگی دانشگاه ” الگوریتم جدیدی در تفکیک دانشجویان ارائه کردهاند که در آن با یک نمایش جدید بیتی داده ها و معیارهای خوشهبندی، جداسازی مناسب دانشجویان را انجام دادهاند، این تفکیک باعث کاهش میزان تداخل دروس دانشجویان در برنامه هفتگی میشود. ابتدا با بهره گرفتن از خوشه بندی، میانگین فازی دانشجویان به k دسته تقسیم شده، سپس با توجه به معیارهای میزان دور بودن مراکز خوشهها میزان متراکم بودن هر خوشه، میزان هم ورودی بودن دانشجویان هر خوشه و
نسبت ابعاد خوشهها و با بهره گرفتن از یک تابع فازی، ارزش خوشهبندی تعیین گردیدهاست و با انتخاب ویژگیهای مناسب، بهترین تفکیک دانشجویان به دست میآید. با اعمال الگوریتم پیشنهادی روی مجموعهای از داده های واقعی، نسبت به فرم خوشهبندی بر اساس سال ورود، تعداد تداخلات درسی به طور متوسط به میزان ۸۰% کاهش یافته است.
باباییزاده در سال ۱۳۹۰ در مقاله خود با عنوان ” یک سیستم پشتیبانی تصمیم برای زمانبندی کلاسهای دانشگاه ” سیستمی دارای چهار زیرسیستم به شرح زیر تعریف نموده:
پایگاه داده
یگان گفتمان
یگان پردازشگر
یگان بهینه سازی
برای پیادهسازی این سیستم پشتیبان تصمیم، برنامه کامپیوتری با کمک زبان سیشارپ و پایگاه داده اکسس تهیه شده است. به منظور حل مسئله در یگان بهینه سازی، هیوریستیکهای رنگآمیزی گراف به کار گرفته شدهاست. روش پژوهشی این مقاله میدانی و پیمایشی است. درنهایت، سیستم پیشنهادی برای زمانبندی کلاسهای یک نیمسال تحصیلی دانشکده علوم انسانی دانشگاه خلیج فارس به کار گرفته شده است. نتایج نشان میدهد در مقایسه با شیوه کنونی، سیستم پشتیبان تصمیم ارائه شده از نظر برآورده نمودن محدودیتها و همچنین صرفهجویی در زمان و هزینه عملکرد بسیار خوبی دارد.
راستگارامینی در سال ۱۳۹۱، در مقالهای با عنوان ” مدلسازی و ارائه روشحل برای مسئله زمانبندی دروس دانشگاهی و تخصیص استاد - درس در دانشکده صنایع دانشگاه صنعتی اصفهان"، یک مدل ریاضی صفرویک برای مسئله زمانبندی آموزشی با در نظرگیری ترجیحات اساتید در مورد بازههای زمانی و موضوعات درسی و یک تابع هدف جدید که کمینهسازی تعداد دروس همزمان با دانشجویان مشترک طراحی کرده و با فرض مشخص بودن تعداد دانشجویان متقاضی ثبتنام در هر دو درس، ابتدا کلیه دروس اعم از دو یا سه واحدی در بازههای زمانی متناسب با دروس سه واحدی برنامه ریزی میشوند که این امر تعداد متغیرها و محدودیتهای مسئله را به شدت کاهش میدهد.
سپس جواب به دست آمده، به عنوان داده ورودی مدلهای خطی صفر و یک جدید قرار میگیرد که با جایابی مجدد دروس دو واحدی در بازههای مجاز، جواب حاصل ارتقا یابد.
روش حل مسئله در این مطالعه، بهینه سازی جمعیت مورچگان است که با فرضهای اولیه برای این الگوریتم، گراف نمایش مسئله تشکیل شده و مراحل بروز رسانی فرومون در پیش گرفته شدهاست و مسیر ایجاد شده جوابی که کمترین مقدار تابع هدف را داشته باشد، به عنوان بهترین جواب انتخاب میشود و سپس بروزرسانی عمومی به منظور تقویت جوابهای بهتر در هر تکرار بعد از این که کلیه مورچهها پاسخ هایشان را ایجاد نمودند، فقط برای مسیر مورچهای که بهترین جواب را تولید کردهاست، انجام میشود.
الگوریتم یاد شده بر روی داده های واقعی اجرا گردیده و در ابعاد کوچک و متوسط با روش دقیق برنامه ریزی صفر و یک مقایسه گردیدهاست. نتایج نشان میدهد الگوریتم پیشنهادی در زمان منطقی و بسیار کمتر از زمان لازم برای حل مدل ریاضی در ابعاد کوچک منطبق بر روش دقیق و در ابعاد متوسط با خطایی کمتر از ۴.۵% عمل میکند.
باشیزاده در سال ۱۳۹۱، در مقاله خود با عنوان ” بهینه سازی برنامه ریزی هفتگی دروس دانشگاهی با روش های جستجوی محلی ” کوشش کردهاست با ارائه الگوریتمهای جستجوی محلی مناسب، یک برنامه هفتگی که محدودیتهای سخت در آن رعایت شده و بهبود حاصل شود.
ورودی این روش پیشنهادی یک برنامه قابل قبول است که به وسیله یک الگوریتم جستجوی خاص مسائل ارضا محدودیت به دست آمده است. این ورودی قابل قبول، جهت نیل به سمت جواب بهینه به الگوریتم پیشنهادی ارائه میشود. نتایج به دست آمده نشانداده که این روش برای داده های واقعی در فضایی با ابعاد بالا و محدودیتهای پیچیده، عملکرد بسیار خوبی داشتهاست. مقدار تابع شایستگی، ناخوشایندی برنامه را نشان میدهد، با تشخیص نقض محدودیتها و جمعکردن ناخوشایندی هر کدام از آنها مقداری را برمی گرداند که به صورت نسبی نشان دهنده میزان ناخوشایندی برنامه است. در این مطالعه از سه الگوریتم تپه نوردی، شبیهسازی حرارت و بهینه سازی تکراری تصادفی با همسایگیهای ترکیبی استفاده شدهاست.
افسری و افتخاری، در مقالهای با عنوان ” برنامه ریزی دروس دانشگاهی با سیستم مورچه- فازی ” مسئله برنامه ریزی درسی بهعنوان یک مسئله بهینه سازی ترکیبی را فرمولهبندی و حل کردهاند. هدف از برنامه ریزی، ایجاد یک برنامه زمانی معتبر و قابل اجرا در یک محیط واقعی بدون تداخل و حداکثر رضایتمندی است، برای افزایش قدرت راهحل از تئوری مجموعه های فازی در الگوریتم جمعیت مورچگان استفاده شده است. مسئله به طور کاملاً مناسب با یک گراف چندگانه شبیهسازی شده و ماتریس ردپا نیز دقیقاً معین شدهاست. همچنین پارامترهای بسیار زیادی از مسئله در نظر گرفته شدهاست که در کارهای قبلی این مسئله با چنین ابعادی هرگز در نظر گرفته نشده است. روش پیشنهادی در یک محیط واقعی با پارامترهای واقعی مورد آزمایش قرار گرفته و نتایج بسیار مطلوبی بهدست آمده است که نشان دهنده قدرت بالای سیستم مورچه-فازی در مسئله برنامه ریزی دروس میباشد.
بابایی و حیدرزاده در مقاله خود با عنوان ” مروری بررهیافتهای تحقیق درعملیات برروی مسئلهی جدول زمانبندی دروس دانشگاهی ” با هدف دستهبندی کردن رهیافتهای تحقیق درعملیات جهت حل مسئله جدول زمانبندی دروس دانشگاهی درسه کلاس تکنیک مبتنی برتئوری رنگآمیزی گراف، متد برنامه ریزی خطی و برنامه ریزی عدد صحیح و تکنیک مبتنی برقید حل این مسئله را بررسی کردهاست.
شفیعی در سال ۱۳۹۱، در پایان نامه خود با عنوان ” حل مسئله جدول زمانبندی دروس دانشگاه ” مبنای حل مسئله جدول زمانبندی، روش رنگآمیزی گراف است که گامی جدید در بهبود فرایند آموزش توسط یکی از جدیدترین روش های مورد بحث در دنیای فناوریها و نرمافزارهای آموزشی میباشد.گراف مذکور را با یک الگوریتم بهینه و با رعایت تمامی محدودیتهای قوی (شرایط ضروری جهت صحت و کارایی جداول زمانبندی)، و محدودیتهای ضعیف (شرایط اضافی که باعث بهبود جداول زمانبندی میشوند)و اعمال نظرات و خواسته های دانشجویان و اساتید، رنگآمیزی کرده و آن را به یک جدول زمانبندی بدون تداخل تبدیل میکند.
۲-۳-۳- مطالعات خارجی
آبرامسون^[۳۸] در سال ۱۹۹۱ در مقالهای با عنوان ” حل مسئله جدولزمانی با بهره گرفتن از تبرید شبیهسازیشده ” به حل مسئله جدول زمانی اشاره دارد، این مسئله شامل چندین نوع برنامه ریزی است، نظیر کلاس دانشجویان، اساتید و اتاقها و از طرفی برنامه بازههای زمانی را شامل میشود. برای حل از روش مونتکارلو که همان تبرید شبیه سازی شده گفته میشود جهت بهینه سازی استفاده شدهاست. ابتدا خود مسئله تعریف شده، سپس روش تبریدشبیهسازی شده توضیح داده میشود. یک جدولزمانی نمونه در این شرایط و محیط تهیه شده و نتایج آزمایشی گزارش گردیدهاست. نتایج نشان میدهد که این روش، جواب سریعتری را نسبت به دیگر روشها ارائه کردهاست.
مسعود و بدری و همکاران در سال^[۳۹] ۱۹۹۶ در مقاله خود با عنوان “مدل دومرحلهای چندهدفه برنامه زمانبندی دروس دانشگاهی” یک روش بهینه سازی دومرحلهای با در نظر گرفتن ترجیحات زمانی دوره های آموزشی و نیز ترجیحات اعضای هیئت علمی، در مرحله اول یک ماتریس که شامل اعضای علمی (ردیف) و دوره ها و عواملی نظیر اولویتها (ستون) بود را شکل داد. در مرحله دوم این روش را در دانشگاه امارات متحده عربی به کار گرفت و نتایج به همان خوبی ترجیحات را پوشش داده و یک خانه زمانی خاص را پشتیبانی میکرد.
مسعود و بدری و همکاران^[۴۰] در سال ۱۹۹۷ نیز کار مشابهی نظیر کار قبلی خود انجام دادند با این تفاوت که ماتریس شکل گرفته شامل اولویت دوره ها در ردیفها (اولین اولویت در اولین خط، دومین اولویت در دومین خط و سومین اولویت در سومین خط) و با حروفی شامل خانه های زمانی رضایتبخش در ستونها (a برای اولین انتخاب، b برای دومین انتخاب و c برای سومین انتخاب)، که در بخش آمار دانشکده علوم اداری و اقتصاد دانشگاه امارات متحده عربی به کار گرفته شد و نتایج آن نیز به خوبی ترجیحات دوره آموزشی بود و اعضای هیئت علمی را در یک خانه زمانی خاص پشتیبانی میکرد.
نات و آندرس^[۴۱] در سال ۱۹۹۸، در مقاله خود با عنوان “مسئله زمانبندی دروس در شرکت آموزش فنی لافتانزا"برای برنامه دوره های شرکت آموزش فنی لافتانزا مسئله را فرموله کرده و یک برنامه ذهنی در طول اولویتهای متفاوت به خوبی الگوریتمهای جستجوی محلی برای تخمین خوب وزنها برای نقشهای مرکب وزین در نظر گرفتهاند؛ که با آزمایشات مختلف محاسباتی برای تخمین عملکرد الگوریتمها بهترین برنامه را تولید کرده که در واقع بهتر از جوابهای معمولی در شرکت آموزش فنی لافتانزا است.
آلبرتو کولورنی و همکاران^[۴۲] در سال ۱۹۹۸ در مقالهای با عنوان “یک الگوریتم ژنتیک برای پاسخگویی به مسئله جدولزمانی” نتایج تحقیقاتی که موارد ممکن را به وسیله الگوریتم ژنتیک برای حل مسئله زمانی وجود دارد را پیشنهاد میکند. ابتدا مدلی شامل تعریفی از ساختارهای هیوریستیکی برای تابع هدف و تولید کردن عملگرهای ژنتیکی که بتوانند در ماتریسهای ارائه شده به کار گرفته شوند آورده شده، سپس گزارشی از خروجی های اجرای سیستم برای تولید جدولزمانی یک مدرسه که رضایتبخش نیز بوده است آورده شدهاست. بعد از آن مقایسهای بین دو جفت الگوریتم صورت گرفته که نتایج نشان داده است که الگوریتم ژنتیک با جستجوی محلی و جستجوی ممنوع بهتر از تبرید شبیهسازی شده و روش دستی کار کرده است.
بورونیکو^[۴۳] در سال ۲۰۰۰ در مقاله خود با عنوان “مدلسازی کمی و فناوری رانده برنامه ریزی دروس” یک مدل چندهدفه سلسلهمراتبی به کمک مدیران دانشگاه کسب و کار با برنامه ریزی دوره های دپارتمان دروس کارشناسی ارائه کرده است. مدل ریاضی در رابطه با یک مدل شبیهسازی رویداد گسسته مورد استفاده قرار گرفتهاست که مدلی است برای ثبتنام پروژه های دانشجویان در دوره های زمانی. نتایج حاصل از مدل نشان میدهد برنامههای دانشکده کسب و کار باید به اولویتهای مهمی نظیر حداقل کردن تعارضات درسی دانشجویان، محدود کردن استفاده از دانشکده کمکی و پیوستن به ترجیحات در انتساب اعضای هیئت علمی برای یک بخش توجه کند.
مونتانا و مارشال^[۴۴] در سال ۲۰۰۰ در مقاله خود با عنوان ” الگوریتمهای ژنتیک برای مسائل واقعی و پیچده زمانبندی دروس دانشگاهی” با توجه به رویکرد خود موارد زیر را در پیش گرفتهاند:
دامنه خاص نمایندگی کروموزوم و اعمال ژنتیکی
تابع تخمین چند هدفه
مقداردهی اولیه اکتشافی جمعیت
تغییر زمان پویا
همکاری متقابل با اپراتورهای انسانی
برانیمیر و مارین^[۴۵] در سال ۲۰۰۲، در مقاله خود با عنوان “حل مسئله جدول زمانبندی به وسیله الگوریتم ژنتیک ” برای حل مسئله برنامه جدولزمانی شرح دادهاند، این الگوریتم در موارد کوچک و بزرگ مورد آزمایش قرار گرفته است، عملکرد الگوریتم با اصلاح اپراتورهای ژنتیکی اساسی که تعارضهای جدید ایجاد میکند به میزان قابل توجهی در فرد افزایش مییابد.
ین زن ونگ^[۴۶] در سال ۲۰۰۳ در مقاله خود با عنوان “استفاده از روش های الگوریتم ژنتیک به منظور حل مسائل برنامه زمانبندی دروس دانشگاهی” به محدودیتهایی نظیر تعارض در ساعات تدریس، ساعات ترجیحی اساتید و پیوستگی ساعات درسی اشاره دارد و با در نظر گرفتن این موارد، روش های الگوریتم ژنتیک را برای مواجه شدن با محدودیتهای چندگانه به کار گرفته و به نتایج بسیار قابل قبولی برای مدرسان در مورد زمانبندی دروس دانشگاهی دست یافته است.
نات و مانوئل^[۴۷] در سال ۲۰۰۳ در مقاله خود با عنوان ” یک رویکرد ژنتیکی برای یافتن برنامهزمانی رضایتبخش برای کلاسها ” برای یافتن یک برنامه زمانی خوب که منجر به استفاده صحیح از هر کلاس، در ارتباط با زمان، فضا و محدودیتهای دیگر از اصول الگوریتم ژنتیک استفاده کردهاند. برنامه الگوریتم ژنتیک مقداردهی یک برنامه تصادفی به نمایندگی از یک فرد میباشد.
این فرد توسط جهشها تغییر میکند و توسط تابع برازندگی متناسب اندام میگیرد، که فردی در آن اصلاح یا نگهداری میشود یا دور ریخته میشود. برنامه نهایی برای هر دوره آموزشی با مقدار تابع برازندگی آن نمایش داده میشود.
آیدین و سردار^[۴۸] ۲۰۰۳ در مقاله خود با عنوان” الگوریتم ژنتیک مبتنی بر سیستم زمانبندی دروس دانشگاهی ” یک سیستم گسترش یافته شامل یک نرم افزار هوشمند و منعطف تعریف نمودهاند که به صورت اتوماتیک وظیفه برنامه زمانبندی دروس را انجام میدهد و تمام ویژگیهای خاص دانشکده مهندسی دانشگاه آتیلیم را یافته است.
هانا و کیت^[۴۹] در سال ۲۰۰۳ در مقاله خود با عنوان ” جدول زمانی دروس دانشگاهی با محدودیتهای نرم” طراحی رویکرد و تکنیکهای پاسخ را برای گسترش یک سیستم جدول زمانی در دانشگاه پوردوو توضیح میدهد. اولین مسئله طراحی یک سیستم هوشمند برای کمک به ساختار اجزای بزرگتر دانشگاه مادر است. سپس با اصلاح روش های جستجو، جوابهای اولیه تولید شده بهبود بخشیده میشوند که برای پاسخگویی به این مسئله کاربرد دارد.
هارولد و مارکون^[۵۰] در سال ۲۰۰۵ در مقالهای با عنوان ” یک جستجوی ممنوع هیوریستیکی با استراتژیهای موثر برای مسئله جدول زمانی استاد - درس ” از روش هیوریستیکی برای پاسخگویی رضایتبخش استفاده شده است، این روش یک جستجوی ممنوع هیوریستیکی با دو حافظه مختلف مبتنی بر استراتژیهای موثر برای مسئله جدول زمانی استاد - درس است.
نتایج نشان میدهد که کاربرد این روش برای مجموعهای از این روشها، جوابهای بهتری از روش جستجوی ممنوع مبتدی ارائه میکند.
کوین سال در سال۲۰۰۶، در طرح پژوهشی خود با عنوان ” برنامه زمانبندی اعضای هیئت علمی با بهره گرفتن از الگوریتم ژنتیک” هدف خود را بررسی برنامههای قابل قبول در زمان نسبتاً سریع با بهره گرفتن از تکنیکها و الگوریتمهای ژنتیک معرفی میکند.
جولا و خاتونناصری در سال ۲۰۰۷، در مقالهای با عنوان ” ارائه یک جستجوی محلی جدید برای حل مسئله برنامه ریزی دروس دانشگاهی با بهره گرفتن از الگوریتم ممتیک ” به چگونگی حل مسئله جدولزمانی دروس دانشگاهی به کمک الگوریتم ممتیک پرداختهاند و سپس الگوریتم جستجوی محلی جدیدی که منجر به دستیابی به پاسخهای بهتر برای حل این مسئله میشود، معرفی شدهاست.
تابع شایستگی که سهم عمدهای در زمان اجرای الگوریتم به خود اختصاص میدهد طبق فرمول (۲-۴) محاسبه گردیده:
F(T)=   (T) (2-4)
که در آن   : میزان جریمه نقض محدودیت j
(T)   : تعداد نقضها در جدول برنامه ریزی T و برای هر محدودیت است.