مقالات و پایان نامه ها درباره : حل مسئله زمانبندی سیستم باز با الگوریتم ژنتیک چند جمعیتی با … – منابع مورد نیاز برای مقاله و پایان نامه : دانلود پژوهش های پیشین |
![]() |
عملگر حذف و کپی[۸۸]
در این روش به صورت تصادفی دو یا سه ژن جهت حذف شدن انتخاب شده و ژنهای قبلی به جای آنها کپی می شود . شکل ۲-۱۹ عملگر حذف و کپی را نشان میدهد
شکل ۲‑۱۹: عملگر حذف و کپی [۱]
عملگر حذف وتولید مجدد[۸۹]
در این روش ژنهای بین دو نقطه تصادفی حذف شده و به صورت تصادفی مجددا تولید میشود. شکل ۲-۲۰ عملگر حذف و تولید مجدد را نشان میدهد.
شکل ۲‑۲۰: عملگر حذف و تولید مجدد [۱]
پارامترهای الگوریتم ژنتیک
احتمال تبادل و احتمال جهش دو پارامتر اصلی در الگوریتمهای ژنتیک است. احتمال تبادل به صورت درصد بوده و بیان میکند که شانس اتفاق افتادن تبادل چقدر است. در صورتی که هیچ تبادلی روی ندهد، فرزندان کپی از والدین خواهند بود. تبادل به این امید انجام میشود که کروموزومهای جدید بخشهای مفید کروموزومهای شایسته را به ارث ببرند. احتمال جهش نیز بیان میکند که شانس اتفاق افتادن جهش چقدر است.
پارامترهای دیگری نیز برای الگوریتمهای ژنتیک موجود است. یکی از این پارامترها، اندازه جمعیت است که حداکثر تعداد کروموزومها را در یک جمعیت ژنتیکی مشخص میکند. اگر اندازه جمعیت کم باشد، الگوریتم ژنتیک امکانات کمی برای عمل تبادل خواهد داشت، زیرا در این صورت تنوع کروموزومها کمتر خواهد بود. از طرف دیگر اگر اندازه جمعیت زیاد باشد سرعت الگوریتم ژنتیک کم خواهد بود. و پارامتر بعدی حداکثر تعداد نسلهایی است که قرار است تولید شود.
همگرایی[۹۰]
به طور کلی یک فرمول صریح و جامع ریاضی درباره همگرایی وجود ندارد. یکی از معیارهای همگرایی را میتوان به این صورت بیان کرد که وقتی یک درصدی از کروموزومهای جمعیت شبیه هم میشوند، می تواند فرض کرد که همگرایی صورت گرفته است. این درصد ممکن است ۸۰٪ یا ۸۵٪ باشد.
شرط خاتمه الگوریتم ژنتیک
تعیین شرایط خاتمه الگوریتم ژنتیک به نوع مساله و دانش بیرونی بستگی دارد. میتوان از هر یک از راههای زیر یا ترکیبی از راههای زیر برای تصمیم گیری در مورد اتمام الگوریتم استفاده نمود.
-
- رسیدن به یک مقدار شایستگی مشخص
-
- حداکثر تعداد نسلها
-
- کم شدن تنوع و همگرایی جمعیت
-
- عدم بهبود شایستگی پس از گذشت تعدادی نسل
مزایای الگوریتم ژنتیک
اولین و مهمترین نقطه قوت الگوریتم ژنتیک این است که الگوریتم ژنتیک ذاتاً موازی است. اکثر الگوریتمهای دیگر موازی نیستند و فقط میتوانند فضای مساله مورد نظر را در یک جهت، در یک لحظه جستجو کنند و اگر راه حل پیدا شده یک جواب بهینه محلی باشد و یا زیر مجموعه ای از جواب اصلی باشد باید تمام کارهایی که تا به حال انجام شده را کنار گذاشت و دوباره از اول شروع کرد. از آنجایی که الگوریتم ژنتیک چندین نقطه شروع دارد، در یک لحظه میتواند فضای مساله را از چند جهت مختلف جستجو کند. اگر یکی به نتیجه نرسید سایر راه ها ادامه مییابند و منابع بیشتری در اختیار آنها قرار میگیرد [۴۵،۷۱].
دومین نقطه قوت الگوریتم ژنتیک این است که الگوریتم ژنتیک در مورد مسائلی که حل میکند هیچ چیزی نمیداند. در واقع الگوریتم ژنتیک در راه حلهای کاندید، تغییرات تصادفی اعمال میکند و سپس از تابع شایستگی برای سنجش این که آیا آن تغییرات پیشرفتی ایجاد کرده است یا نه، استفاده میکند. مزیت این تکنیک این است که به الگوریتم ژنتیک اجازه میدهد تا با ذهنی باز شروع به حل کند. از آنجایی که تصمیمات الگوریتم ژنتیک اساساً تصادفی است، بر اساس تئوری همه راه حلهای ممکن به روی مساله باز است عمل میکند.
مزیت دیگر الگوریتم ژنتیک این است که به صورت همزمان قادر به پیشنهاد چند جواب است.
معایب الگوریتم ژنتیک
الگوریتمهای ژنتیک علاوه بر مزایای ذکر شده دارای معایبی نیز میباشد که تعدادی از آنها به شرح زیر است [۴۳،۶۵]:
-
- الگوریتم ژنتیک در گامهای اول، ناحیههایی از فضای حالت مساله که بهینههای سراسری و محلی در آن واقع شده است را به خوبی شناسایی میکند ولی در ادامه مسیر به سمت بهینه سراسری بسیار کند عمل میکند.
-
- دومین مشکل متداول الگوریتم ژنتیک عدم پایداری است. یعنی جوابهایی که از اجراهای مختلف الگوریتم حاصل میشوند، تفاوت زیادی دارند. این مساله ممکن است برای مساله مفید نبوده و حتی غیر قابل اعتماد باشد.
کارهای انجام شده
همانطور که در مقدمه ذکر شد برای حل مساله زمانبندی سیستم های تولید انعطاف پذیر عموما از روش های ابتکاری[۹۱] استفاده می شود در این فصل الگوریتم های ابتکاری ارائه شده برای حل مساله زمانبندی سیستم های باز و یا سیستم هایی نزدیک به سیستم باز که با توجه به شرایط آنها قابل استناد بوده ذکر شده است و معایب ومزایای آن ها مورد بررسی قرار گرفته است.
الگوریتم [۹۲]ETPN-GA
Li و Xie یک الگوریتم ژنتیک تعبیه شده در پتری نت زمانی[۹۳] به نام ETPN-GA برای زمانبندی سیستم های تولید قابل پیکربندی مجدد ارائه دادند که هدف آن کمینه کردن زمان اتمام کارها و هزینه های پیکربندی مجدد است.
ایده اصلی این الگوریتم استفاده از پتری نت برای مدل کردن سیستم و در نظر گرفتن توالی شلیک انتقال ها در مدل پتری نت، برای نمایش کروموزوم است. در این الگوریتم یک عملگر تبادل و عملگر جهش، مختص این روش نمایش کروموزوم ارائه شده است. از مزایای این الگوریتم استفاده از پتری نت به عنوان ابزاری برای مدل سازی، زمانبندی، شبیه سازی و ارزیابی کارایی سیستم های تولید انعطاف پذیر است. و از معایب آن در نظر نگرفتن مساله توزیع شدگی در سیستم های تولید انعطاف پذیر و عدم توجه به مساله نگهداری و اعمال محدودیت های زیاد برای سیستم های تولید انعطاف پذیر است.
Saito و همکارانش نیز کار مشابهی را با بهره گرفتن از الگوریتم ژنتیک و پتری نت رنگی[۹۴] ارائه دادند همچنین می توان کار مشابهی را در [۷۵،۷۶] مشاهده نمود.
الگوریتم AFS Petri Net
Delgadillo و Chedid یک الگوریتم ژنتیک بر پایه پتری نت زمانی برای زمانبندی سیستم های انعطاف پذیر ارائه کردند که هدف آن کمینه کردن زمان تولید با توجه به مسئله پیکر بندی مجدد است، این الگوریتم دارای سه مرحله است که عبارتند از:
-
- در مرحله اول سیستم تولید انعطاف پذیر با پتری نت مدل می شود.
-
- در مرحله دوم با بهره گرفتن از الگوریتم ژنتیک یک زمانبندی نزدیک به بهینه تولید می شود.
-
- در مرحله سوم سیستم با توجه به زمانبندی تولید شده و با بهره گرفتن از مدل پتری نت، سیستم شبیه سازی می شود.
این الگوریتم نیز برای نمایش کروموزوم از توالی شلیک انتقال ها در مدل پتری نت استفاده می کند. عملگر انتخاب آن روش مسابقه ای[۹۵] و عملگر تبادل آن تبادل تک نقطه ای[۹۶] است و برای جهش دو ژن بصورت تصادفی انتخاب شده مکان آنها هم جابجا می شود.
از مزایای این الگوریتم استفاده از پتری نت برای مدل سازی، شبیه سازی و زمانبندی سیستمهای تولید انعطاف پذیر است و از معایب آن، اعمال محدودیت های زیاد برای سیستم های تولید انعطاف پذیر و در نظر نگرفتن مساله توزیع شدگی و مساله نگهداری است.
الگوریتم GA-ACO[97]
Rossi و Boschi یک الگوریتم ابتکاری ترکیبی برای حل مساله زمانبندی کار کارگاهی با ماشینهای موازی ارائه دادند که هدف آن کمینه کردن زمان اتمام کارها است. در این الگوریتم از ترکیب الگوریتم ژنتیک و کلونی مورچگان برای حل مسئله استفاده شده است. شکل ۲-۲۱ مراحل الگوریتم ارائه شده را نشان می دهد.
شکل ۲‑۲۱: مراحل الگوریتم GA-ACO
در این الگوریتم از عملگر تبادل مبتنی بر کار و عملگر جهش شیفتی استفاده شده است. شکل ۲-۲۲ عملگرتبادل مبتنی بر کار و شکل ۲-۲۳ عملگر شیفتی استفاده شده در این الگوریتم را نشان می دهد. از مزایای این الگوریتم استفاده از ترکیب الگوریتم ژنتیک با الگوریتم کلونی مورچگان است و از معایب این الگوریتم در نظر نگرفتن مساله نگهداری، مساله توزیع شدگی و عدم توجه به هزینه های تولید است.
شکل ۲‑۲۲: عملگر مبتنی بر کار
شکل ۲‑۲۳: عملگر جهش شیفتی
الگوریتم GA-Fuzzy
Raja و همکارانش برای بهینه سازی چند هدفه زمانبندی ماشین های موازی[۹۸] (PMS) ترکیبی از الگوریتم ژنتیک و منطق فازی[۹۹] را ارائه دادند. در این روش از الگوریتم ژنتیک برای تولید زمانبندی بهینه تصادفی و از منطق فازی برای انتخاب بهترین زمانبندی از میان زمانبندی های تصادفی تولید شده با توجه به چندین هدف استفاده شده است. در این الگوریتم نیز از توالی انجام کارها برای نمایش کروموزوم استفاده شده است. شکل ۲-۲۴ یک کروموزوم نمونه را نشان می دهد. همچنین از عملگر تبادل تک نقطه ای برای تولید فرزند استفاده شده است. عملگر جهش نیز جای دو ژن تصادفی یک کروموزوم را با هم تعویض می نماید.
فرم در حال بارگذاری ...
[سه شنبه 1401-04-14] [ 04:02:00 ب.ظ ]
|