در این روش بر خلاف سه روش قبل که از ورود جوابهای غیر موجه جلوگیری میکردند، جواب غیر موجه با احتمال کم امکان حضور مییابند. سه روش فوق دارای این عیب بودند که به هیچ نقطهای بیرون از فضای موجه توجه نمیکردند، اما در بعضی مسائل بهینه سازی، جوابهای غیرموجه درصد زیادی از جمعیت را اشغال میکنند. در چنین شرایطی اگر جستجو فقط در ناحیه موجه انجام گیرد شاید یافتن جواب موجه خیلی وقتگیر و مشکل باشد.
استراتژی جریمهای از متداولترین تکنیکهای مورد استفاده برای سر و کار داشتن با جوابهای غیر موجه میباشد که در آن ابتدا محدودیتهای مسئله در نظر گرفته نمیشوند، پس برای هر تخلف از محدودیتها یک جریمه اختصاص داده میشود که این جریمه در تابع هدف قرار میگیرد.

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

مسئله اصلی چگونگی انتخاب یک مقدار مناسب برای مقدار جریمه میباشد تا در حل مسائل به ما کمک نماید. نکتهای که در روش جریمه وجود دارد این است که یک جواب غیرموجه به سادگی حذف نمیشود، زیرا ممکن است در ژنهای آن اطلاعات مفیدی وجود داشته باشد که با اندکی تغییر به جواب بهینه تبدیل شوند.
۲-۲-۴-۵- بهبود الگوریتم ژنتیک
برای بهبود الگوریتم ژنتیک میتوانیم تغییرات زیر را اعمال کنیم:
استفاده از بهینهگر محلی
تغییر پارامترهایی از قبیل تغییر جمعیت اولیه، نرخ جهش و کسر ادغام (ترکیب)
تغییر الگوریتم ژنتیک باینری به پیوسته و بالعکس
۲-۲-۴-۶- چند نمونه از کاربردهای الگوریتم ژنتیک
نرمافزارهای شناسایی چهره (شناسایی چهره با بهره گرفتن از تصویر ثبت شده. در این روش، شناسایی چهره بر اساس فاصله اجزای چهره و ویژگیهای محلی و هندسی صورت میگیرد که تغییرات ناشی از گیم، تغییرات نور، افزایش سن کمترین تاثیر را خواهد داشت. همچنین گرافها برای چهرههای جدید با بهره گرفتن از الگوریتمهای ژنتیک ساخته شده و با بهره گرفتن از یک تابع تشابه، قابل مقایسه با یکدیگر هستند که این امرتاثیر بسزایی در افزایش سرعت شناسایی خواهد داشت).
توپولوژیهای شبکه های کامپیوتری توزیع شده
بهینه سازی ساختار مولکولی شیمیایی
مهندسی برق برای ساخت آنتنهای برق
مهندسی نرمافزار
بازیهای کامپیوتری
مهندسی مواد
مهندسی سیستم
رباتیک
تشخیص الگو و استخراج داده
حل مسئله فروشنده دورهگرد
آموزش شبکه های عصبی مصنوعی
یاددهی رفتار با رباتها
یادگیری قوانین فازی با بهره گرفتن از الگوریتم ژنتیک
۲-۳-پیشینه تحقیقاتی
در این قسمت ابتدا به تاریخچهای از طرح مسئله برنامه ریزی دروس دانشگاهی اشاره میشود و پس از آن به بررسی مطالعات داخلی و خارجی صورت گرفته در این مسائل پرداخته میشود.
۲-۳-۱- مروری بر تاریخچه
گاتلیب^[۲۵]، ۱۹۶۲ برای اولین بار مسئله جدولزمانی را مطرح نمود، وی مدل خود را به صورت ماتریس گونه تعریف و با بهره گرفتن از رنگآمیزی گراف آن را حل کرد. لیون^[۲۶] مثالی را آورد که در واقع حل مسئله گاتلیب را نقض کرد. همچنین حل این مسئله توسط دمپتر^[۲۷] و اررا ^[۲۸] در سال ۱۹۶۹ نیز نقض گردید.
بعد از آن در سالهای ۱۹۶۶ تا ۱۹۷۰ چندین استراتژی هیوریستیکی برای مسئله جدول زمانی گاتلیب گزارش گردید و در همین سالها نیز ماکون و والکر^[۲۹] با بهره گرفتن از الگوریتم مونت کارلو دانشآموزان را به کلاسها تخصیص دادند و همچنین ولش و پاول^[۳۰] جدولزمانی برنامه امتحانات را به وسیله رنگآمیزی گراف حل نمودند، اما کل صورت مسئله و حل آنها با توجه به شرایط مختلف دیگر نیز دچار مشکل شد. نتایج به دست آمده از پژوهش نافلد^[۳۱] و تارتار^[۳۲] در سال ۱۹۸۵ نشان داده که بالاخره وجود یک رنگآمیزی گراف برای نشان دادن موقعیتهای موجود برای یافتن جواب مسئله جدولزمانی ضروری است اما کافی نیست و همچنین در این سالها از الگوریتم ممتیک نیز در حل مسائل جداول زمانی استفاده شده است.
جکسون و میکائیل^[۳۳] و پاسکال وان^[۳۴] در سالهای ۱۹۸۵ تا ۱۹۹۵، استفاده از محدودیتهای برنامه ریزی منطقی را مبنای حل مسئله جدولزمانی قرار دادند و برای پاسخگویی به این مسئله به تکنولوژی اهمیت فراوانی دادند.
در سالهای ۱۹۹۶ تا ۱۹۹۸ کریستل و همکاران^[۳۵] از به کارگیری وزن یا به عبارتی جریمه بهره گرفتند، به گونهای که هر محدودیت بایستی رعایت شود و نیز برای کم کردن جریمه کل، در برقراری محدودیتهایی که نقض شدهاند تابعی در نظر گرفتند.
بورکه^[۳۶] در سالهای ۱۹۹۸ و ۲۰۰۱ یک جدولزمانی اتومات برای گروه تعریف کرد که با توجه به تغییر شرایط، هر سال یک بار به طور منظم با ایمیل، خدمات بعد از استفاده مربوط را برای مصرفکنندگان میفرستاد.
آل وارس^[۳۷] در سال ۲۰۰۲ برای طراحی و اجرای مسئله برنامه ریزی دروس دانشگاهی از روشحل جستجویممنوع استفاده کرده و به این ترتیب محققان از سالهای ۲۰۰۰ به بعد از روش های مختلف فراابتکاری در حل مسائل جداولزمانی بهره گرفتهاند که در ادامه به شرح مطالعات داخلی و خارجی پیرامون این مسئله پرداخته میشود.
۲-۳-۲- مطالعات داخلی
حاجی یخچالی در سال ۱۳۷۸، در مقالهای با عنوان ” مدل عدد صحیح برای مسئله زمانبندی کلاسهای دانشگاهی: یک مطالعه موردی” مدل صفر و یک برای مسئله زمانبندی کلاسهای دانشگاهی ارائه کرده است. این مدل قوانین آموزش و نیازهای موسسات آموزشی را دربر میگیرد. تابع هدف این مدل حداقل کردن تابع خطی جریمه میباشد. با این تابع هدف، میتوان اولویت میان روزهای هفته، دوره های زمانی در طول روز، کلاسهای ارائه دروس و حتی استاتید را اعمال نمود. علاوه براین با تعریف مناسب ضرایب جریمه، میتوان فاصله های خالی بین برنامه نیمسال برای گروه دانشجویان را کاهش داد. این مدل با نرمافزارهای حلکننده مدل عدد صحیح حل گردیده است. در نهایت این مدل برای دانشکده مهندسی صنایع پیادهسازی شد.
امیدوار در سال ۱۳۸۴، در مقاله خود با عنوان ” طراحی و ساخت سیستم تصمیمیار زمانبندی دروس دانشگاهی با بهره گرفتن از روش برنامه ریزی خطی عدد صحیح” برای حل این مسئله یک مدل ریاضی برنامه ریزی خطی ارائه کرده است. این مدل با توجه به شرایط زمانبندی کلاسهای درس دانشکده مهندسی کامپیوتر دانشگاه صنعتی امیرکبیر ارائه شده است. این مطالعه با اصلاحاتی در مدل عدد صحیح داسکالکی سایز مدل را کاهش داده و در نتیجه، سرعت پاسخگویی و مقدار حافظه مصرفی به طرز چشمگیری کاهش یافته، همچنین افزودن قابلیت‌هایی از قبیل جلوگیری از تکرار جلسات یک درس در یک روز، رعایت فاصله یک روز میان ارائه جلسات یک درس و رعایت موازیبودن زمان ارائه جلسات دروس است که میتوان آن ها را بر درسهای مورد نظر اعمال نمود. برای این منظور محدودیتهای جدیدی تعریف شده و این تغییرات اعمال گردیدهاست.
خلیلی و منصورزاده در سال ۱۳۸۵، در مقالهای با عنوان ” برنامه ریزی درسی در دانشگاه به کمک مدلسازی دو مرحلهای برنامه ریزی ریاضی” ضمن تشریح مسئله و دستهبندی شرایط به شرایط سخت که حتما باید برقرار باشند و شرایط نرم که تا حد امکان بهتر است برقرار باشند مسئله را به صورت یک مسئله برنامه ریزی خطی با اعداد صحیح فرمولبندی کردهاست، آنگاه با وارد کردن متغیرهای قابل برنامه ریزی، طی دو مرحله مسئله را حل نموده به گونهای که در مدل اول، اندیس کلاسها در نظر گرفته نشده و پس از اجرای مدل اول، از جواب بهینه مدل اول استفاده کرده و کلاسها در طی مدل دوم تخصیص داده میشوند.
این مطالعه بر اساس مدل پیشنهادی، یک سیستم نرمافزاری طراحی و ساخته شده که ضمن ارائه این سیستم، آن را با داده های واقعی مربوط به نیمسال دوم ۸۳-۱۳۸۲ دانشکده ریاضی دانشگاه علم و صنعت ایران اجرا شده، نتایج را با حل این مسئله به صورت دستی مقایسه نموده است.
دهقانی و ذاکرتولائی در سال ۱۳۸۵، در مقاله خود با عنوان"رویکردی نوین در زمانبندی دروس دانشگاه با بهره گرفتن از الگوریتم ژنتیک” ضمن به کارگیری الگوریتم ژنتیک، رویکردی شامل اصلاحاتی از قبیل تغییراتی در مدل اولیه مسئله در راستای بهبود زمان اجرا و جلوگیری از پیمایش فضای حالت ناممکن، روشی جدید در رمزگذاری و معرفی عملگرهای هوشمند جهش و ترکیب به منظور انجام اصلاحات در نسلها میباشد. در انتها با اعمال ۲۰ نمونه ورودی مختلف به برنامهای که مخصوص این پژوهش طراحی گردید، تاثیر رویکرد نوین در مقایسه با روش استاندارد، در رسیدن به جواب بهینه سنجیده میشود و نشان داده میشود که رویکرد نوین به طور متوسط در زمان کوتاهتر به جوابهای بهینهتری میرسد. در این مقاله برای محاسبه تابع شایستگی برای هر یک از محدودیتها ضریبی مشخص میشود که بیانکننده میزان اهمیت هر یک میباشد و از فرمول (۲-۱) محاسبه میشود. در این فرمول، w برابر وزن هر محدودیت،   برابر تعداد نقضهای محدودیتهای نرم و   برابر تعداد نقضهای محدودیتهای سخت میباشند.
F(x) =   *   (x) +   *   (x) (2-1)
در این مقاله ۲۰ نمونه از ترکیبهای مختلف دروس و ساعات استادان یک ترم گروه کامپیوتر دانشگاه امام رضا (ع)، به عنوان ورودی به برنامه داده شده و هر دو روش استاندارد و نوین در مورد تمامی آنها اجرا گردیده، سپس در شرایط یکسان مدت زمان رسیدن به جواب و نیز میزان برازش جواب نهایی استخراج گردیده است. الگوریتم نوین در شرایط یکسان برنامه هفتگی مناسبتری را به خروجی ارسال میکند و همچنین مدت زمان اجرا به مراتب بهتر از روش استاندارد بودهاست.
فاضلی در سال ۱۳۸۷ در مقاله خود با عنوان “مدل ریاضی برنامه ریزی پرواز هواپیمای مسافربری” برای نخستین بار مدل ریاضی با ادغام چهار زیر مسئله به طور پیوسته، ساخته و ارائه کردهاست. اما با توجه به بزرگی مقیاس مدل توسعهیافته، حل آن با بکارگیری روش های متداول تحقیق در عملیات امکان پذیر نبوده بنابراین در
حل این مسئله از روش ابتکاری الگوریتم ژنتیک استفاده کرده است و مدل ارائه شده برای داده های واقعی یک شرکت هواپیمایی داخلی به کمک الگوریتم ژنتیک حل شده است.
غافری در سال ۱۳۸۷، در مقاله خود با عنوان “حل مسئله جدول زمانبندی دروس دانشگاهی با بهره گرفتن از الگوریتم ژنتیک و رنگآمیزی گراف” بر اساس محدودیتهای قوی مانند در دسترسبودن اساتیدو نوع اتاق و همچنین محدودیتهای ضعیف، با بهره گرفتن از الگوریتم ژنتیک و رنگآمیزی گراف مسئله زمانبندی دروس دانشگاهی را حل کرده، به این صورت که برای محدودیتهای همزمانی غیر مجاز تدریسها در جداول زمانبندی اساس گراف پیادهسازی شده و در حین استفاده از رنگآمیزی گراف، الگوریتم ژنتیک که یکی از روش های پرکاربرد جهت حل این نوع مسائل است نیز به کار گرفته شدهاست.
در این مقاله برای رنگآمیزی گراف از الگوریتمی که توسط ولش و پاول ابداع شده است، استفاده شده به طوری که ابتدا رئوس گراف بر حسب نزول درجات مرتب شده، سپس از اولین رنگ برای رنگآمیزی اولین راس و هر راسی که مجاور یک راس رنگ نشده قبلی یا همان رنگ نیست استفاده میشود. این عمل با بهره گرفتن از دومین رنگ و رئوس رنگ نشده بعدی تکرار میشود و سپس سومین رنگ و همینطور ادامه داده میشود تا تمام رئوس رنگ شوند.
تابع شایستگی در این مرحله بر اساس تعداد ژنهای غیر۱- عمل میکند و میزان شایستگی هر کروموزوم برابر با تعداد ژنهای مقدار مثبت است و اندازه جمعیت برای تعداد محدودی تدریس(در حدود ۴۰ تدریس)، عدد ۱۰ انتخاب شده و حداقل تعداد نسل برابر با ۲۰۰۰ انتخاب شده است. نتایج به دست آمده از این عملیات اشاره به این دارد که استفاده از الگوریتم ژنتیک در حین به دست آوردن رنگآمیزی گراف برای تشکیل یک جدولزمانی مناسب با رفع تعدادی از محدودیتهای قوی است که با توجه به رفع چند محدودیت قوی با رنگآمیزی گراف و نیز رفع محدودیتهای قوی دیگر، احتمال به نتیجه رسیدن الگوریتمها و بالارفتن سرعت شده است.
مسعودیان و استکی در سال ۱۳۸۸، در مقاله خود با عنوان ” طراحی جدول زمانبندی خودکار برای دروس دانشگاهی با بهره گرفتن از الگوریتمهای ژنتیک"، ابتدا الگوریتمهای ژنتیک مطالعه و بررسی شده، سپس مسئله بهینه سازی جدولزمانی دروس برای یک دانشکده فرضی مورد استفاده قرار گرفته است. در این رویکرد روند تکاملی پاسخها طی تکرار نسلها در یک الگوریتم ژنتیک، نهایتاً منجر به تولید یک جدول زمانبندی دروس خوش
کیفیت گشته است. در مرحله پیادهسازی، به کمک تغییراتی که در روند معمول الگوریتمهای ژنتیک صورت داده شده، نتایج بسیار خوبی در زمینه طراحی جداول زمانبندی دروس دانشگاهی حاصل شده است. اساس کار الگوریتم طراحی شده، حفظ کروموزومهای بهتر جمعیت و اعمال عملگرهای ژنتیکی، بر روی بقیه کروموزومها به منظور بهبود آنها است. در آزمونهای مقایسه بین الگوریتم ژنتیک عادی و پیشنهادی، طی چند مرحله، نقاط قوت الگوریتم پیشنهادی را مشخص کردهاند.
اندازه جمعیت در این مطالعه با توجه به فرمول (۲-۲)، محاسبه شده است :
= k *   (۲-۲)
m: مجموع تعداد کلاسها و آزمایشگاهها
n: تعداد کل بازههای زمانی یک ساعتی در یک هفته
E: تعداد وقایع