بخشی از مقاله
چکیده
الگوریتم بهینه سازی علفهای هرز یک الگوریتم جدید قدرتمند با الهام از تکثیر و رشد علف های هرز است که اولین بار توسط لوکاس و محرابیان در سال 2006 معرفی شد .از آن زمان تا کنون، از این الگوریتم در بسیاری از مسائل مهندسی نظیر حل مسائل چند هدفه، طراحی آنتن و حل معادلات غیر خطی استفاده شده و با توجه به کاربردهای متفاوت نتایج موفقیت آمیزی داشته است .
الگوریتم علفهای هرز با وجود سادگی و کارایی که دارد، از توانایی استخراج خوبی برخوردار نیست و معمولا دقت جوابهای بدست آمده پایین است؛ همچنین از تعدادی پارامتر اولیه برخوردار است که در کیفیت جواب بسیار موثر بوده و در تعیین آنها عموما از روش سعی و خطا استفاده می شود.
در روش پیشنهادی این مقاله، با ایجاد تغییراتی در ساختار الگوریتم علفهای هرز، و نحوه تولید دانه ها در هر تکرار، با استفاده از فرمولی جدید برای واریانس هر دوره؛ علاوه بر حذف تعدادی از پارامترهای قابل تنظیم اولیه، روشی قدرتمند برای حل مسائل بهینه سازی، و خصوصا در ابعاد بالا، ارائهمی گردد .در روش پیشنهادی علاوه بر سادگی بیشتر دقت جوابهای بدست آمده به طور چشمگیری بهبود می یابد .نتایج پیاده سازی صحت این ادعا را تایید می کند .به عنوان مثال در تابعEllipsoid با بعد100 نتایج الگوریتم پیشنهادی نسبت به IWOساده بیش از 99 درصد بهبود را نشان می دهد.
.1 مقدمه
یکی از بهترین روشها در حل مسائل بهینه سازی استفاده از الگوریتمهای تکاملی است. الگوریتمهای تکاملپذیر روشهای بر مبنای جستجوی تصادفیاند که از مدلسازی تکامل بیولوژیکی طبیعی الگوبرداری شدهاند. آنها بر روی پاسخهای ممکنی کار میکنند که از ویژگی برتری برخوردار و نیز بقای نسل بیشتری دارند، لذا تخمین نزدیکتری از پاسخ بهینه بدست میدهند.
الگوریتم بهینه سازی علفهای هرز یک الگوریتم جدید قدرتمند با الهام از تکثیر و رشد علف های هرز است که اولین بار توسط لوکاس و محرابیان در سال 2006 معرفی شد.[1] این روش با وجود سادگی و کارایی که دارد، از توانایی استخراج خوبی برخوردار نیست و معمولا دقت جوابهای بدست آمده پایین است؛ همچنین از تعدادی پارامتر اولیه برخوردار است که در کیفیت جواب بسیار موثر بوده و در تعیین آنها عموما از روش سعی و خطا استفاده می شود. هدف ما ارائه روشی است که در حین ساده تر کردن الگوریتم و حذف تعدادی از این پارامترها، توانایی استخراج الگوریتم را افزایش داده، کیفیت پاسخ ها را بالا ببرد.
.2 مروری بر کارهای انجام شده
الگوریتم علفهای هرز اولین بار در سال 2006، توسط دکتر لوکاس در دانشگاه تهران معرفی گردید.[2] از آن زمان تا کنون، از این الگوریتم برای حل بسیاری از مسائل عملی با ابعاد بالا مانند کنترل گروه رباتها، کنترل رباست و تطبیقی، آنالیز دینامیکهای بازار برق و تخصیص منابع استفاده شده و نتایج موفقیت آمیزی بدست آمده است3]،.[4 در سال 2012 از الگوریتم علفهای هرز، برای حل مسائل خوشه بندی بدون داشتن تعداد خوشه ها استفاده شد.[5] هم چنین از این الگوریتم در کاربردهای مهندسی مانند بهینه سازی پیکربندیهای آنتن8] [6]،[7 به طور موفقی استفاده شده است.
در سال 2012، برای مسیریابی در محیطهای شهری از الگوریتم علفهای هرز، استفاده شد.[9] هم چنین در مقاله ای دیگر در همین سال، از الگوریتم علفهای هرز برای حل دستگاههای معادله دیفرانسیل غیرخطی با رویکردی نوین استفاده شده است
در این میان برخی مقالات با ایجاد تغییراتی سعی در بهبود کارایی این الگوریتم داشته اند. اکثر این تغییرات با اضافه کردن گامهایی در الگوریتم اصلی می باشند که باعث افزایش پیچیدگی روش بوده و نهایتا پاسخهایی بهتر ارائه می دهند.[18-11] برخی از روشهای پیشنهادی نیز با ایجاد تغییراتی در فرمول واریانس موجود در الگوریتم کیفیت جواب را افزایش داده اند.
.3 الگوریتم بهینه سازی علفهای هرز
الگوریتم بهینه سازی علفهای هرز یک الگوریتم جدید قدرتمند با الهام از تکثیر و رشد علف های هرز است که اولین بار توسط لوکاس و محرابیان در سال 2006 معرفی شد . این الگوریتم با الهام از روند رشد علفهای هرز، ایجاد شده است. علفهای هرز گیاهانی هستند که به علت مقاومت و تطبیق پذیری در برابر تغییرات محیط، رشد بی رویه آنها تهدید مهمی برای کشاورزان محسوب می شود.
با الهام از این ویژگی ها، الگوریتم بهینه سازی علفهای هرز بوجود آمده است. این الگوریتم بسیار ساده است و پارامترهای قابل تنظیم نسبتا کمی دارد. مرور کارهای انجام شده در چند سال اخیر نشان می دهد که این الگوریتم، در فضاهای پیوسته و در مسائل با ابعاد بالا، قوی تر از بسیاری از الگوریتمهای تکاملی عمل می کند .گامهای این الگوریتم به صورت زیر می باشد:
1. تولید جمعیت اولیه علفهای هرز به صورت تصادفی.
2. محاسبه برازندگی اعضای جمعیت.
3. تعیین تعداد دانه هایی که هر علف می تواند تکثیر کند: تعداد دانه های قابل تکثیربرای هر عضو جمعیت، متناسب با میزان برازندگی آن عضو است. این مقدار عددی است بین بازه اعدادی که برای بدترین عضو و بهترین عضوتعیین میشود،که به صورت خطی با میزان برازندگی اعضا ارتباط دارد. رابطه زیر تعداد دانه های تکثیر شده توسط عضو i ام را نشان می دهد:
.4 توزیع فرزندان هر عضو در اطراف همان عضو با توزیع نرمال گوسی، میانگین صفر و انحراف معیاری که برای هر نسل از رابطه زیر بدست می آید:
در این رابطه میزان انحراف معیار اولیه و نیز نسل آخر توسط کاربر تعیین می شود. n نیز ضریب مدولاسیون غیرخطی بوده و معمولا بین 1 تا 3 انتخاب می شود.
.5 اعمال مکانیزم حذف رقابتی:
برای اینکه تعداد علفهای هرز، از حد مجاز از پیش تعیین شده تجاوز نکند، مکانیزم حذف رقابتی به اعضای جمعیت اعمال می شود. یعنی هر زمان تعداد کل اعضای جمعیت، به ماکزیمم از پیش تعیین شده توسط کاربر برسد، تمامی اعضا به ترتیب برازندگی مرتب شده و اعضای با برازندگی کمتر از جمعیت حذف می شوند.
.6 تکرار گامهای 2 تا 5 تا برآورده شدن شرط توقف. الگوریتم علفهای هرز با وجود سادگی و قدرت اکتشاف بالا و نیز توانایی بدست آوردن جوابهای مناسب برای مسائل با ابعاد بالا، دارای معایبی از جمله همگرایی زودرس و امکان ابتلا به بهینه های محلی و نیز ضعف در استخراج و پایین بودن کیفیت جوابها است.
از آنجایی که در الگوریتم علفهای هرز جمعیت اولیه به صورت تصادفی ایجاد شده و هیچ اطلاعی از نحوه توزیع و پراکندگی ذرات در دست نیست، تنظیم پارامترها باید بصورت آزمون و خطا انجام گیرد که مستلزم صرف زمان بوده و کیفیت پاسخ نیز تضمینی ندارد. از این رو به نظر می رسد استفاده از انحراف معیار ذرات می تواند در بهبود الگوریتم موثر باشد، زیرا با محاسبه انحراف معیار و استفاده از آن در نحوه توزیع ذرات جدید، از چگونگی پراکندگی ذرات موجود استفاده کرده ایم و با توجه به این پراکندگی ذرات جدید را تولید می کنیم.
در نظریه احتمالات و آمار واریانس نوعی سنجش پراکندگی است. مقدار واریانس با میانگینگیری از مربع فاصله مقدار مورد نظر و یا مشاهده شده با میانگین مقادیر محاسبه میشود. واریانس کمتر بدین معنا است که انتظار میرود که اگر نمونهای از توزیع مزبور انتخاب شود مقدار آن به میانگین نزدیک باشد. ریشه دوم واریانس انحراف معیار نامیده میشود و دارای واحدی یکسان با متغیر اولیه است. انحراف معیار نشان میدهد به طور میانگین دادهها چه مقدار از مقدار متوسط فاصله دارند. برای محاسبه انحراف معیار کافی است ریشه دوم واریانس را حساب کنیم.
.4 روش پیشنهادی این مقاله:
همان طور که اشاره شد الگوریتم علفهای هرز از توانایی استخراج خوبی برخوردار نیست و معمولا دقت جوابهای بدست آمده پایین است. در روش پیشنهادی این پایان نامه، ما تغییراتی را در ساختار الگوریتم اعمال می کنیم به نحوی که علاوه بر ساده تر شدن الگوریتم دقت جوابهای بدست آمده به طور چشمگیری بهبود می یابد. شکل 1 فلوچارت الگوریتم پیشنهادی را نمایش میدهد.
اولین تغیر در روش پیشنهادی این مقاله، حذف گام سوم الگوریتم علف های هرز، یعنی اختصاص مقادیر مختلف تعداد فرزندان به ذرات مختلف است، که در عوض در هر تکرار، به ازای هر ذره، ذره ای جدید تولید میشود.
تغییر بعدی ایجاد فرمولی جدید برای مقدار واریانس توزیع ذرات با استفاده از توزیع نرمال گوسی است. برای این منظور به ازای هر ذره یک عضو چدید در اطراف همان عضو با توزیع نرمال گوسی، میانگین صفر و انحراف معیاری که برای هر نسل از رابطه زیر بدست می آید
