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