مشخص شده احتمال انتخاب هر کروموزوم در روش چرخ گردان محاسبه شده است شکل 2-13 تفاوت احتمال انتخاب کروموزوم ها در روش چرخ گردان را به صورت درصدی نشان میدهد.
جدول ‏24: احتمال انتخاب در روش چرخ گردان برای داده‌های فرضی [1]
شماره کروموزم
مقدار تابع شایستگی
احتمال انتخاب
1
286/0
022/0
2
663/0
051/0
3
079/1
083/0
4
261/1
097/0
5
711/9
747/0
انتخاب رتبه بندی79
این روش مانند چرخ گردان از نوع روش‌های انتخاب تصادفی وزندار است. با این تفاوت که در این روش وزن بر اساس رتبه کروموزوم تعیین میشود. این تکنیک از نظر ساختار مشابه روش چرخ گردان است اما نوع توزیع قطاعهای دایره در آنها متفاوت است. روش انتخاب رتبه‌بندی برای رفع مشکل ایجاد والدین مشابه در روش چرخ گردان مطرح شده است. در این روش ابتدا بر اساس میزان شایستگی، کروموزومها را مرتب نموده سپس به بدترین کروموزوم مقدار شایستگی یک داده می‌شود. به کروموزوم بعدی مقدار دو و به همین نحو تا آخر ادامه می‌یابد. اگر تعداد کروموزومهای جمعیت n باشد، بهترین کروموزوم مقدار شایستگی برابر n خواهد داشت. حال بر اساس مقدار شایستگی جدید، مانند روش چرخ گردان احتمال و محدوده عددی هر کروموزم مشخص می‌شود.
گرچه روش رتبهبندی مشکل روش چرخ گردان را برطرف نموده اما به آهستگی همگرا میشود زیرا بهترین کروموزومها تفاوت چندانی با بقیه کروموزوم‌ها ندارد شکل 2-14 تفاوت احتمال انتخاب کروموزوم‌ها در روش رتبهبندی را به صورت درصدی نشان میدهد.
انتخاب نخبه‌گرا80
در این روش تعداد معینی از بهترین کروموزومها در جمعیت جدید کپی می‌شوند. این روند باعث افزایش کارایی الگوریتم ژنتیک می‌شود، زیرا مانع از گم شدن جوابهای خوب به دست آمده می‌شود. این روش به عنوان روشی کمکی در کنار سایر روش‌ها قابل اعمال است.
انتخاب مسابقه‌ای81
این روش که شبیه رقابت در طبیعت عمل می‌کند، توسط گلدبرگ ارائه شده است. در این روش یک زیر مجموعه کوچکی از کروموزومها ( معمولا دو یا سه کروموزوم ) به صورت تصادفی انتخاب شده و بهترین کروموزوم از نظر مقدار شایستگی در این مجموعه انتخاب می‌شود. به تعداد کروموزومهای ‌مجموعه فوق، اندازه مسابقه82 می‌گویند. این روش در جمعیت‌های بسیار بزرگ به عنوان بهترین روش شناخته می‌شود. شکل 2-15 انتخاب مسابقه‌ای را نشان می‌دهد.
عملگر تبادل83
در طبیعت، نتیجه حاصل از جفتگیری دو موجود زنده فرزندی خواهد بود که ترکیبی از صفات والدین خود را به همراه خواهد داشت. در الگوریتم ژنتیک نیز عملگری به نام تبادل وجود دارد که از دو کروموزوم والد، یک یا دو فرزند را بوجود می‌آورد. اثرگذاری این مرحله در همگرایی کروموزمها به سمت پاسخ مورد نظر به حدی است که معمولا الگوریتم ژنتیک را بوسیله نوع عملگر تبادل آن معرفی می‌کنند. در زیر متداولترین روشهای تبادل معرفی شده است.
عملگر تبادل تک نقطهای84
در این روش که توسط دیویس ارائه شده است یک نقطه به صورت تصادفی در طول دو کروموزومی که به عنوان والد انتخاب شده‌ است، در نظر گرفته میشود. کروموزوم‌ها از آن نقطه به دو قسمت تقسیم می‌شوند. قسمت اول از والد اول و قسمت دوم از والد دوم در کنار هم فرزند اول را ساخته و قسمت دوم از والد اول در کنار قسمت اول از والد دوم ،فرزند دوم را ایجاد میکند. شکل 2-16 عملگر تبادل تک نقطه‌ای را نمایش می‌دهد.
عملگر تبادل دو نقطه ای85
در این روش به صورت تصادفی دو نقطه از کروموزوم والد انتخاب می‌شود. در نتیجه کروموزوم‌ها به سه قسمت تقسیم می‌شوند دو قسمت بیرون دو نقطه، از والد اول و قسمت بین دو نقطه، از والد دوم در کنار هم فرزند اول را ساخته و قسمت بین دو نقطه از والد اول در کنار دو قسمت خارج از دو نقطه از والد دوم، فرزند دوم را ایجاد میکند. شکل 2-17 عملگر تبادل دو نقطه‌ای را نشان می‌دهد.
عملگر جهش86
یکی دیگر از عوامل تحول‌زا در موجودات زنده، ‌جهش است. به پیدایش هر نوع تغییر در ژن‌های یک کروموزوم، جهش گفته می‌شود. در واقع جهش ژنتیکی در نگاه عامه مردم به تغییرات منفی در ساختار کروموزومی اشاره میکند. البته از آنجایی که این تغییرات به صورت تصادفی است امکان ایجاد کروموزوم‌های نامناسب در آن زیاد است. در برخی حالات بدون جهش امکان رسیدن به جواب مناسب وجود ندارد. به عنوان مثال اگر مقدار یک بیت در تمام کروموزومها صفر (یا یک) باشد با هیچ یک از روشهای مطرح شده در جفتگیری نمیتوان مقدار این بیت را یک (یا صفر) نمود، چون فرآیند تبادل بر اساس انتقال خصوصیات از والدین به فرزندان عمل میکند. از آنجایی که این ژن در هیچ والدی یک(یا صفر) نیست در نتیجه فرزندی نمیتوان تولید نمود که مقدار این ژن در آن یک ( یا صفر) باشد.
عملگر معکوس سازی87
در این روش به صورت تصادفی دو نقطه در کروموزوم انتخاب شده و ژن‌های بین این دو نقطه معکوس می‌شود. شکل 2-18 عملگر معکوس سازی را نشان می‌دهد.
عملگر حذف و کپی88
در این روش به صورت تصادفی دو یا سه ژن جهت حذف شدن انتخاب شده و ژن‌های قبلی به جای آن‌ها کپی میشود . شکل 2-19 عملگر حذف و کپی را نشان می‌دهد
عملگر حذف وتولید مجدد89
در این روش ژنهای بین دو نقطه تصادفی حذف شده و به صورت تصادفی مجددا تولید می‌شود. شکل 2-20 عملگر حذف و تولید مجدد را نشان می‌دهد.
شکل ‏220: عملگر حذف و تولید مجدد [1]
پارامترهای الگوریتم ژنتیک
احتمال تبادل و احتمال جهش دو پارامتر اصلی در الگوریتم‌های ژنتیک است. احتمال تبادل به صورت درصد بوده و بیان می‌کند که شانس اتفاق افتادن تبادل چقدر است. در صورتی که هیچ تبادلی روی ندهد، فرزندان کپی از والدین خواهند بود. تبادل به این امید انجام می‌شود که کروموزوم‌های جدید بخش‌های مفید کروموزوم‌های شایسته را به ارث ببرند. احتمال جهش نیز بیان می‌کند که شانس اتفاق افتادن جهش چقدر است.
پارامترهای دیگری نیز برای الگوریتم‌های ژنتیک موجود است. یکی از این پارامترها، اندازه جمعیت است که حداکثر تعداد کروموزوم‌ها را در یک جمعیت ژنتیکی مشخص می‌کند. اگر اندازه جمعیت کم باشد، الگوریتم ژنتیک امکانات کمی برای عمل تبادل خواهد داشت، زیرا در این صورت تنوع کروموزوم‌ها کمتر خواهد بود. از طرف دیگر اگر اندازه جمعیت زیاد باشد سرعت الگوریتم ژنتیک کم خواهد بود. و پارامتر بعدی حداکثر تعداد نسل‌هایی است که قرار است تولید شود.
همگرایی90
به طور کلی یک فرمول صریح و جامع ریاضی درباره همگرایی وجود ندارد. یکی از معیارهای همگرایی را میتوان به این صورت بیان کرد که وقتی یک درصدی از کروموزوم‌های جمعیت شبیه هم می‌شوند، میتواند فرض کرد که همگرایی صورت گرفته است. این درصد ممکن است 80٪ یا 85٪ باشد.
شرط خاتمه الگوریتم ژنتیک
تعیین شرایط خاتمه الگوریتم ژنتیک به نوع مساله و دانش بیرونی بستگی دارد. می‌توان از هر یک از راه‌های زیر یا ترکیبی از راه‌های زیر برای تصمیم گیری در مورد اتمام الگوریتم استفاده نمود.
رسیدن به یک مقدار شایستگی مشخص
حداکثر تعداد نسل‌ها
کم شدن تنوع و همگرایی جمعیت
عدم بهبود شایستگی پس از گذشت تعدادی نسل
مزایای الگوریتم ژنتیک
اولین و مهمترین نقطه قوت الگوریتم ژنتیک این است که الگوریتم ژنتیک ذاتاً موازی است. اکثر الگوریتم‌های دیگر موازی نیستند و فقط می‌توانند فضای مساله مورد نظر را در یک جهت، در یک لحظه جستجو کنند و اگر راه حل پیدا شده یک جواب بهینه محلی باشد و یا زیر مجموعه ای از جواب اصلی باشد باید تمام کارهایی که تا به حال انجام شده را کنار گذاشت و دوباره از اول شروع کرد. از آنجایی که الگوریتم ژنتیک چندین نقطه شروع دارد، در یک لحظه می‌تواند فضای مساله را از چند جهت مختلف جستجو کند. اگر یکی به نتیجه نرسید سایر راه ها ادامه می‌یابند و منابع بیشتری در اختیار آن‌ها قرار می‌گیرد [45،71].
دومین نقطه قوت الگوریتم ژنتیک این است که الگوریتم ژنتیک در مورد مسائلی که حل می‌کند هیچ چیزی نمی‌داند. در واقع الگوریتم ژنتیک در راه حل‌های کاندید، تغییرات تصادفی اعمال می‌کند و سپس از تابع شایستگی برای سنجش این که آیا آن تغییرات پیشرفتی ایجاد کرده است یا نه، استفاده می‌کند. مزیت این تکنیک این است که به الگوریتم ژنتیک اجازه می‌دهد تا با ذهنی باز شروع به حل کند. از آنجایی که تصمیمات الگوریتم ژنتیک اساساً تصادفی است، بر اساس تئوری همه راه حل‌های ممکن به روی مساله باز است عمل می‌کند.
مزیت دیگر الگوریتم ژنتیک این است که به صورت همزمان قادر به پیشنهاد چند جواب است.
معایب الگوریتم ژنتیک
الگوریتم‌های ژنتیک علاوه بر مزایای ذکر شده دارای معایبی نیز می‌باشد که تعدادی از آن‌ها به شرح زیر است [43،65]:
الگوریتم‌ ژنتیک در گام‌های اول، ناحیه‌هایی از فضای حالت مساله که بهینه‌های سراسری و محلی در آن واقع شده است را به خوبی شناسایی می‌کند ولی در ادامه مسیر به سمت بهینه سراسری بسیار کند عمل می‌کند.
دومین مشکل متداول الگوریتم‌ ژنتیک عدم پایداری است. یعنی جواب‌هایی که از اجرا‌های مختلف الگوریتم حاصل می‌شوند، تفاوت زیادی دارند. این مساله ممکن است برای مساله مفید نبوده و حتی غیر قابل اعتماد باشد.
کارهای انجام شده
همانطور که در مقدمه ذکر شد برای حل مساله زمانبندی سیستم های تولید انعطاف پذیر عموما از روش های ابتکاری91 استفاده می شود در این فصل الگوریتم های ابتکاری ارائه شده برای حل مساله زمانبندی سیستم های باز و یا سیستم هایی نزدیک به سیستم باز که با توجه به شرایط آنها قابل استناد بوده ذکر شده است و معایب ومزایای آن ها مورد بررسی قرار گرفته است.
الگوریتم 92ETPN-GA
Li و Xie یک الگوریتم ژنتیک تعبیه شده در پتری نت زمانی93 به نام ETPN-GA برای زمانبندی سیستم های تولید قابل پیکربندی مجدد ارائه دادند که هدف آن کمینه کردن زمان اتمام کارها و هزینه های پیکربندی مجدد است.
ایده اصلی این الگوریتم استفاده از پتری نت برای مدل کردن سیستم و در نظر گرفتن توالی شلیک انتقال ها در مدل پتری نت، برای نمایش کروموزوم است. در این الگوریتم یک عملگر تبادل و عملگر جهش، مختص این روش نمایش کروموزوم ارائه شده است. از مزایای این الگوریتم استفاده از پتری نت به عنوان ابزاری برای مدل سازی، زمانبندی، شبیه سازی و ارزیابی کارایی سیستم های تولید انعطاف پذیر است. و از معایب آن در نظر نگرفتن مساله توزیع شدگی در سیستم های تولید انعطاف پذیر و عدم توجه به مساله نگهداری و اعمال محدودیت های زیاد برای سیستم های تولید انعطاف پذیر است.
Saito و همکارانش نیز کار مشابهی را با استفاده از الگوریتم ژنتیک و پتری نت رنگی94 ارائه دادند همچنین می توان کار مشابهی را در [75،76] مشاهده نمود.
الگوریتم AFS Petri Net
Delgadillo و Chedid یک الگوریتم ژنتیک بر پایه پتری نت زمانی برای زمانبندی سیستم های انعطاف پذیر ارائه کردند که هدف آن کمینه کردن زمان تولید با توجه به مسئله پیکر بندی مجدد است، این الگوریتم دارای سه مرحله است که عبارتند از:
در مرحله اول سیستم تولید انعطاف پذیر با پتری نت مدل می شود.
در مرحله دوم با استفاده از الگوریتم ژنتیک یک زمانبندی نزدیک به بهینه تولید میشود.
در مرحله سوم سیستم با توجه به زمانبندی تولید شده و با استفاده از مدل پتری نت، سیستم شبیه سازی می شود.
این الگوریتم نیز برای نمایش کروموزوم

این مطلب رو هم توصیه می کنم بخونین:   منابع تحقیق درمورداستراتژی، استراتژی ها، استراتژیک
دسته‌ها: No category

دیدگاهتان را بنویسید