Construct the pool of trial solutions generated in before step.
}
شکل ۴-۲- ساختار کلی عملگر پیشنهادی
در روش فوق بر روی هر کدام از جوابهای موجود در مجموعه p1، یک روش جستجوی چندعملگری اعمال شده و نتیجه آن مجموعه ای از جوابهای بهینه محلی است که درهمسایگی جواب مذکور قرار دارند. تمام جوابهای بهینه محلی حاصل از اعمال این روش بر روی جوابها، در استخری از جوابها جمع آوری می شوند.
برای بهبود جوابها، همسایگی آنها جستجو شده و بررسی می شود. عملگرهای جستجوی همسایگی که در اینجا استفاده شده اند، شامل ۴ عملگر شرح داده شده است.
هر کدام از این عملگرها بخشی از جوابهای همسایه را جستجو می کنند و بخشی دیگر ممکن است فقط توسط عملگر دیگری حاصل شوند، لذا در صورت استفاده از یک عملگر جستجوی همسایگی ممکن است بعضی از جوابهای همسایه مستعد از دست بروند. به همین دلیل در این تحقیق از روش جستجوی چند عملگری استفاده شده است که الگوریتم آن شرح داده خواهد شد.
از۴ عملگر بالا در روش جستجوی چند عملگری برای تولید جوابهای همسایه استفاده شده است. فلوچارت الگوریتم روش جستجوی چند عملگر در زیر نشان داده شده است.
شکل ۴-۳- فلوچارت الگوریتم روش جستجوی چند عملگر
در روش جستجوی بکار گرفته شده در این تحقیق، همانطور که در الگوریتم آن مشاهده می شود، مجموعه ای ازجوابها(papprox) که در ابتدا فقط شامل جواب اولیه است، ساخته می شود. در هر تکرار این روش، یک عضو از این مجموعه که تا به حال بررسی نشده است بطور تصادفی انتخاب شده و با استفاده از۴ عملگر جستجوی همسایگی که شرح داده شدند، جوابهای همسایه تولید خواهند شد. سپس با بهره گرفتن از مقایسه میزان برازندگی جوابها، مجموعه papprox به روز شده و تا زمانی که همه اعضای این مجموعه بررسی شوند، این کار تکرار می شود. در پایان الگوریتم، مجموعه papprox که شامل جوابهای بهینه محلی است که در همسایگی جواب اولیه قرار دارند، به عنوان نتیجه الگوریتم برگردانده می شود.
۴-۲-۵- جستجوی همسایگی تصادفی ( دسته p2 )
جهت پیاده سازی جستجوی همسایگی تصادفی برای زنبورهای گروه دوم، در این پایان نامه از یک عملگر جستجوی همسایگی موازی استفاده شده است. این رویه از ۴ عملگر شرح داده شده در بخش قبل بصورت همزمان یا موازی استفاده می کند. اگر عملگر های شرح داده شده را با نمادهای ls1,ls2,ls3,ls4 نشان دهیم، فلوچارت ساختار رویه موازی بصورت زیر است:
شکل ۴-۴- فلوچارت ساختار رویه موازی
همانطور که در ساختار بالا مشاهده می شود، برای هر جواب موجود در p2 : هر کدام از عملگرها بطور جداگانه بر روی جواب مذکور اعمال شده و در نهایت از بین ۴ جواب خروجی عملگرها و جواب ورودی، یکی از آنها با توجه به میزان برازندگی انتخاب شده و بعنوان خروجی رویه شرح داده شده گزارش می شود.
۴-۲-۶- محاسبه مقدار برازندگی
جهت محاسبه تابع برازندگی از معیار تعریف شده در بخش شرط توقف و انتخاب جمعیت اولیه استفاده می شود. در واقع همانطور که گفته شد، جوابها با بهره گرفتن از قاعده دب سطح بندی شده و برای هر جواب، با توجه به سطح آن جواب، معیار پراکندگی محاسبه گردیده و معیار cs بعنوان تابع برازندگی محاسبه می شود. برای هر جواب، هر چه cs کمتر باشد، برازندگی آن جواب بیشتر است.
۴-۲-۷- انتخاب
در هر مرحله از الگوریتم بهینه سازی کلونی زنبورها، از بین مکانهای قبلی و مکانهای جدید زنبورها، N ( اندازه جمعیت) مکان بعنوان بهترین جوابها (با توجه به میزان برازندگی) انتخاب خواهند شد. نحوه انتخاب به این صورت است که برای همه این مکانها میزان برازندگی محاسبه شده و سپس مکانها با توجه به ترتیب صعودی مقدار cs مرتب شده و در نهایت N تای اول بعنوان جمعیت جواب تکرار بعد انتخاب خواهند شد.
۴-۲-۸- رویه بهبود
در ساختار پیشنهادی الگوریتم بهینه سازی کلونی زنبورها، یک رویه بهبود طراحی شده است که در پایان هر تکرار بر روی جوابهای انتخاب شده در بخش قبل اعمال شده و آنها را بهبود میدهد. جوابهای خروجی رویه بهبود بعنوان جمعیت تکرار بعد الگوریتم انتخاب می شوند. پیاده سازی رویه بهبود در این پایان نامه بر پایه جستجوی همسایگی متغیر [۱۳۴] است که در ادامه شرح داده می شود.
ساختار VNS از ۴ ساختار جستجوی همسایگی[۱۳۵] استفاده می کند. این ساختارها همان عملگرهای جستجوی محلی هستند که قبلا توضیح داده شدند. این چهار ساختار در قالب VNS استفاده شده که فلوچارت ساختار کلی VNS بصورت زیر است:
شکل ۴-۵- فلوچارت الگوریتم VNS
هر کدام از جوابهای موجود در جمعیت جواب به الگوریتم VNS داده می شود و یک جواب بعنوان خروجی دریافت خواهد شد. سپس رویه اصلاحی بر روی مابقی ماتریسهای جواب اعمال شده و بصورت شدنی اصلاح شده و جایگزین جواب ورودی خواهد شد.
در واقع ساختار کلی رویه بهبود بصورت زیر خواهد بود:
Improvement method
{For each si in input population
Si=apply VNS procedure on si.
Si=check feasibility method.
}
۴-۲-۹- به روز رسانی آرشیو پارتو
با توجه به اینکه مدل ارائه شده سه هدفه می باشد، الگوریتم پیشنهادی بر پایه آرشیو پارتو طراحی گردیده است. جوابهای با کیفیت (سطح اول) تولید شده از ابتدای الگوریتم در مجموعه آرشیو پارتو نگهداری می شوند تا هیچ جواب با کیفیتی از بین
نرود. جهت به روز رسانی آرشیو پارتو، در پایان هر تکرار الگوریتم، کلیه جوابهای موجود در آن تکرار، جوابهای موجود در آرشیو پارتو و جوابهای جدید تولید شده توسط عملگرهای الگوریتم، در یک استخر جواب ریخته شده و سطح بندی میشوند. سپس جوابهای موجود در سطح اول بعنوان جوابهای آرشیو پارتو انتخاب می گردند.
۴-۳- الگوریتم ژنتیک
الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند. این الگوریتم برای اولین بار در قرن ۲۰معرفی شد[۱۲۷]. این الگوریتم یک الگوریتم فرا ابتکاری بر پایه جمعیت است (در هر تکرار با جمعیتی از جوابها کار می کند). به هر جواب در جمعیت جوابها در این الگوریتم کروموزوم گفته می شود. این الگوریتم با جمعیتی از جوابها شروع شده و با بهره گرفتن از عملگرهای جهش، تقاطع و تجدید نسل، جوابهای جدیدی را تولید می کند. هر کدام از بخشهای الگوریتم به اختصار در ادامه شرح داده می شود.
تولید جمعیت اولیه:
همانظور که گفته شد، الگوریتم ژنتیک یک الگوریتم بر پایه جمعیت است. در واقع در هر تکرار یا نسل این الگوریتم با جمعیتی از جوابها (کروموزوم) سر وکار دارد. اندازه جمعیت در همه تکرارهای الگوریتم باید یکسان باشد. در ابتدای کار این الگوریتم باید جمعیتی از جوابهای اولیه که تعدادشان بعنوان پارامتر الگوریتم است، تولید شوند.
جهش:
در هر تکرار الگوریتم درصدی از جوابها انتخاب شده و یک عملگر جستجوی همسایگی بر روی این جوابها اعمال خواهد شد که به این عملگر، عملگر جهش گفته می شود و تعداد جوابهایی که برای اعمال این عملگر انتخاب می شوند بستگی به نرخ جهش دارند. نرخ جهش عددی بین ۰ و ۱ بوده و بعنوان پارامتر، بصورت ورودی الگوریتم است. مثلا اگر نرخ جهش ۰٫۲ باشد، ۲۰ درصد جوابهای موجود در جمعیت برای اعمال عملگر جهش انتخاب خواهند شد.
تقاطع:
یکی دیگر ازعملگرهای الگوریتم ژنتیک، عملگر تقاطع است که بر روی دو جواب یا دو والد انتخاب شده اعمال می شود و دو فرزند تولید می کند. تعداد جوابهایی که برای عملگر تقاطع انتخاب می شوند، بستگی به نرخ تقاطع دارند. نرخ تقاطع یک عدد بین ۰ و ۱ بوده و جزو پارامترهای ورودی الگوریتم می باشد. اگر نرخ تقاطع ۰٫۶ باشد، ۶۰ درصد جوابهای موجود در جمعیت که تا به حال هیچ عملگری بر روی آنها اعمال نشده است، برای اعمال عملگر تقاطع انتخاب می شوند.
تجدید نسل:
تعدادی از جوابهای موجود در جمعیت که دو عملگر جهش و تقاطع بر روی آنها اعمال نشده است بدون هیچ گونه تغییری به نسل بعد منتقل خواهند شد. که تعداد این جوابها نیز بستگی به نرخ تجدید نسل دارد.
لازم به ذکر است که جمع نرخهای سه عملگر الگوریتم ژنتیک باید برابر با ۱ باشد.
انتخاب والدین:
همانطور که در توضیح عملگر تقاطع گفته شد، برای اجرای این عملگر دو جواب بعنوان والدین انتخاب شده و به این عملگر داده می شوند.
تابع برازندگی:
این تابع برای هر کدام از جوابها محاسبه شده و معیاری برای مقایسه جوابها میباشد.
۴-۴- فلوچارت الگوریتم ژنتیک
فرم در حال بارگذاری ...
