• محاسبات به طور دقیق انجام می شوند و هیچ گونه تقریبی نظیر خطی سازی تابع هدف، گرد کردن نتایج و تغییر متغیر­های گسسته به پیوسته و برعکس وجود ندارند.

واژگان الگوریتم ژنتیک

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

فرایند های اصلی الگوریتم ژنتیک

عملگر ژنتیک، فرایند انتقال موروثی ژن­ها را برای ایجاد فرزندان جدید در هر نسل تقلید می­ کند. بخش مهمی از الگوریتم ژنتیک ایجاد کروموزوم­های جدید موسوم به فرزندان از طریق کروموزم­های قدیمی، موسوم به والدین است. این فرایند مهم توسط عملگرهای ژنتیک صورت می­گیرد. به طور کلی، این اعمال توسط دو عملگر عمده انجام می شوند: عملگر تقاطع و عملگر جهش.

• عمگر تقاطع: بر روی دو کروموزوم اعمال می­ شود و دو فرزند به وسیله­ ترکیب ساختار دو کروموزوم والد ایجاد می­شوند.

• عملگر جهش: این عملگر در کروموزوم­های متفاوت، تغییرات تصادفی برنامه­ ریزی­نشده­ای ایجاد می­ کند و ژن هایی را که در جمعیت اولیه وجود نداشته اند، وارد جمعیت می­ کند.

• مکانیزم انتخاب: برای انتخاب بهترین جواب­ها برای تولید مجدد جمعیت جدید باید از روشی استفاده کرد که حتی الامکان بهترین جواب را انتخاب کند. در این پایان نامه، از روش انتخاب چرخ رولت استفاده می­ شود.

مراحل اجرای الگوریتم ژنتیک

پس از بیان مفاهیم پایه­ای الگوریتم ژنتیک، اینک می توان مراحل مختلف استفاده از این الگوریتم را بررسی کرد. برای این مراحل، ابتدا با توجه به مساله، متغیرهایی که باید تعیین شوند، مشخص می­شوند. سپس، آنها را به نحو مناسبی کدگذاری و به شکل کروموزوم نمایش می­دهیم. بر اساس تابع هدف، مقدار برازندگی برای کروموزوم­ها تعریف می­ شود و جمعیت اولیه دلخواهی نیز به طور تصادفی انتخاب می­ شود. پس از آن، مقدار تابع برازندگی برای هر کروموزوم جمعت اولیه حساب می شود. سپس مراحلی مطابق با شکل ۳-۲ طی می­شوند.

شکل ‏۳‑۲ یک نمودار گردشی برای الگوریتم ژنتیک

کلیات الگوریتم زنبور عسل

در علوم کامپیوتر و تحقیق در عملیات، الگوریتم زنبور عسل یک الگوریتم جستجو بر مبنای جمعیت است که در سال ۲۰۰۵ توسط کاراباگو^[۳۲] پیشنهاد شد]۵۴[. در حالت پایه الگوریتم ترکیبی از انواع جستجو در همسایگی را به وسیله­ جستجوی تصادفی انجام می­دهد. این الگوریتم می ­تواند برای بهینه سازی ترکیبی و تابعی استفاده شود.

رفتار زنبور عسل

یک کلونی زنبور عسل می ‌تواند مسافت­های طولانی را طی کند و نیز در جهت‌ های گوناگون پخش شود تا منابع غذایی را پیدا کند و از آن ن بهره‌ برداری کند. قطعات گلدار با مقادیر زیادی شهد و گرده که با تلاشی کم قابل جمع آوری است، به وسیله­ تعداد زیادی زنبور بازدید می‌شود، به طوری که قطعاتی از زمین که گرده یا شهد کمتری دارند، تعداد کمتری زنبور را جلب می‌کند. فرایند جستجوی غذای یک کلونی به وسیله­ زنبورهای دیده­­بان^[۳۳] آغاز می‌شود که برای جستجوی منبع غذایی امید بخش (دارای امید بالا برای وجود شهد یا گرده) فرستاده می‌شوند. زنبورهای دیده‌بان به صورت تصادفی از منبع غذایی به منبع دیگر حرکت می‌کنند. در طول فصل برداشت محصول (گل‌دهی)، کلونی با آماده نگه داشتن تعدادی از جمعیت کلونی به عنوان زنبور دیده‌بان به جستجوی خود ادامه می‌دهد. هنگامی که جستجوی همه منبع غذایی پایان یابد، هر زنبور دیده‌بان، بالای منبع غذایی که اندوخته­ی کیفی مطمینی از شهد و گرده دارد، رقص خاصی را اجرا می‌کند. این رقص که به نام رقص چرخشی^[۳۴] شناخته می­ شود، اطلاعات مربوط به منبع غذایی (نسبت به کندو)، فاصله تا منبع غذایی و کیفیت منبع غذایی را به زنبورهای دیگر انتقال می­دهد. این اطلاعات زنبورهای دیگر و پیرو را به سوی منبع غذایی می‌فرستد. بیشتر زنبورهای پیرو به سوی منبع غذایی می­روند که امید بخش­تر هستند و امید بیشتری برای یافتن شهد و گرده در آنها وجود دارد. وقتی همه زنبورها به سمت ناحیه­ای مشابه بروند، دوباره به صورت تصادفی و به علت محدوده­ رقصشان در پیرامون منبع غذایی پراکنده می­شوند تا به موجب این کار سرانجام نه یک منبع غذایی ، بلکه بهترین گل­های موجود درون آن تعیین موقعیت شوند. الگوریتم زنبور عسل نقطه­ای در فضای پارامتری متشکل از پاسخ ‌های ممکن را به عنوان منبع غذا بررسی می­ کند. زنبورهای دیده­بان ( کارگزاران شبیه ‌سازی شده) به صورتی تصادفی فضای پاسخ­ها را ساده می­ کنند و به وسیله­ تابع شایستگی کیفیت، موقعیت­های بازدید شده را گزارش می­ دهند. جواب‌­های ساده شده رتبه ­بندی می­‌شوند و دیگر زنبورها نیروهای تازه­ای هستند که فضای پاسخ‌­ها را در پیرامون خود برای یافتن بالاترین رتبه محل­ها جستجو می­ کنند که منبع غذایی (گلزار) نامیده می‌­شود. الگوریتم به صورت گزینشی دیگر منبع غذایی را برای یافتن نقطه­ی بیشینه­­ی تابع شایستگی جستجو می‌کند.

ویژگی مشترک الگوریتم­ها

در این بخش، ویژگی­های مشترک دو الگوریتم ارائه می شوند.

محاسبه مقادیر برازش

برازش هر جواب برابر است با بزرگ­ترین ضریب ماتریس تقاضای سفر بدست آمده از حل جواب یا µ.
برای محاسبه مقدار µ برای هر جواب، با ثابت در نظر گرفتن متغیر­های تصمیم ­گیری توپولوژی شبکه ( y_l، z_ij و k_ij ) با بهره گرفتن از روش موضعی مقدار سیگنال را محاسبه و بهنگام می کنیم. سپس، با بهره گرفتن از رویه جستجوی خطی مقدار بهینه تابع هدف در هر تکرار بدست می ­آید.

(۳-۱۵)

برای محاسبه مقدار µ، یک روش حل دقیق بر پایه جستجوی خطی توسعه یافته است. از آنجا که تابع هدف مدل سطح بالای U متشکل از یک متغیر و به صورت خطی است، لذا جواب بهینه آن حتماً در مرز فضای موجه قرار دارد. بنابراین، جواب بهینه مقداری است که همه محدودیت­های (۳-۱۵) به ازای آن ارضا شده باشند و افزایش در مقدار آن منجر به ناموجه شدن جواب به ازای دست­کم یکی از این محدودیت­ها شود. بر اساس این ایده، روش حل توسعه یافته برای محاسبه ظرفیت ذخیره بهینه خود در دو مرحله عمل می­ کند: در مرحله اول، سعی می­­شود که یک کران بالای UB و یک کران پایین LB اولیه برای مقدار µ بدست آید و در مرحله دوم، با کمک جستجوی خطی یک بعدی، مقدار بهینه متغیر محاسبه می­ شود.
از آنجا که مقدار بهینه بر روی مرز فضای جواب­های شدنی قرار دارد، بنابراین کران پایین آن یک مقدار در داخل فضای شدنی و کران بالای آن یک مقدار در خارج از فضای شدنی خواهد بود. به منظور تعریف کران­های بالا و پایین اولیه، از مقدار ۰ برای متغیر آغاز می­ شود و هر بار یک مقدار ثابت کوچکتر از ۱ به آن اضافه می­ شود تا جایی که مقدار متغیر در خارج از فضای شدنی قرار گیرد. مقدار افزایشی انتخاب شده برای الگوریتم برابر ۰٫۵ است. قابل ذکر است که این مقدار افزایشی بر این اساس انتخاب شده­است که مقدار حداکثر ضریب ماتریس تقاضا در شبکه ­های واقعی معمولاً یک یا حداکثر دو رقمی است. قدم­ها به شرح زیر هستند:
آماده ­سازی: قرار ده µ =۰ ؛ LB=0 ؛ UB=∞.
مرحله اول: قدم­های زیر را تا زمانی که مقدار UB تغییر کند، تکرار کن:

• قرار ده µ=µ+۰٫۵٫

• مقدار بهینه متغیر سیگنال را با بهره گرفتن از روش موضعی تنظیمات سیگنال محاسبه کن. مقادیر تعادلی x_ij را با حل مساله سطح پایین و با توجه به مقدار متغیر سیگنال محاسبه کن.

• اگر همه محدودیت­های (۳-۵) برقرارند، آنگاه قرار ده LB=µ ، در غیر اینصورت قرار ده UB=µ.

• قرار ده µ_a=LB و µ_b=UB.

مرحله دوم: مادام که µ_a - µ_b>ε تکرار کن:

• قرار ده λ = (µ_a+ µ_b)/2.

• مقدار بهینه متغیر سیگنال را با بهره گرفتن از روش موضعی تنظیمات سیگنال محاسبه کن. مقادیر تعادلی x_ij را با حل مساله سطح پایین و با توجه به مقدار متغیر سیگنال محاسبه کن.