مقاله الگوریتم آشوب ناک گله شیرها

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

الگوریتم آشوب ناک گله شیرها
چکیده
در سالهای اخیر تحقیقات زیادی در زمینه الگوریتم های تکاملی با الهام از طبیعت یا جوامع انسانی ، صورت گرفته است. یکی از جدیدترین الگوریتم های تکاملی مطرح شده الگوریتم بهینه سازی گله شیرها است ، که خصوصیات بسیار خوبی را در سرعت همگرایی و دقت بالا در حل مسائل با ابعاد بزرگ و دستیابی به نقطه بهینه کلی از خود نشان داده است. به منظور بالا بردن دقت و نرخ همگرایی این الگوریتم ، در این مقاله روشی برای بهبود الگوریتم پیشنهاد شده است و درقالب الگوریتم بهینه سازیگله-شیرهای بهبودیافته (MLPO) ارائه شده است. به طور معمول تولید ضریب باروری برای تولید مثل و جمعیت اولیه به صورت تصادفی صورت میگیرد که میتواند منجر بهکاهش کارایی الگوریتم گردد. جهت مقابله با این موضوع ایده استفاده از روش - آشوب برای تولید ضریب باروری با استفاده از چندین تابع پیشنهاد شده است. نتایچ آزمایشها نشانداده شده بهبود روش - پیشنهادی نسبت به الگوریتم اولیه بهینه سازی گله شیرها است.
کلماتکلیدی: الگوریتم بهینه سازی گله شیرها ، الگوریتم های تکاملی ، تابع برازندگی ، آشوب ، ضریب باروری

1. مقدمه

جهانیکه در آن زندگی میکنیم به طور مداوم در حال تغییراست. هر موجودی که قصد ماندن در چنین جهان طبیعتی را داشته باشد، بایستی بتواند خود را با شرایط اطراف تطبیق دهد. توسعه علم بهینه سازی بر خواسته از آرزوی انسان برای رسیدن به کمال است. اما از آنجاییکه میداند قادر نیست تمام شرایط حاکم بر بهترین را به خوبی بشناسد، در بیشتر موارد به جای بهترین جواب یا بهینه مطلق به یک جواب رضایتبخش بسنده مینماید. بنابراین میتوان الگوریتم هایی را پذیرفت که هیچ تضمینی در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتایج آنها، به طورمتوسط بهترین تقابلکیفیت و زمان حل برای مسئله مورد بررسی را به همراه داشته اند. به این الگوریتم ها، الگوریتم های هیورستیک1 گفته میشود.
هیورستیکها عبارتاند از معیارها، روشها یا اصولی برای تصمیمگیری بین چند گزینه و انتخاب اثربخشترین برای دستیابی به اهداف مورد نظر در حالت کلی سه دسته از الگوریتم های هیورستیک قابل تشخیص است:
· الگوریتم هاییکه بر ویژگیهای ساختاریمسئله و ساختارجواب متمرکز میشوند و با استفاده ازآنها الگوریتم های-سازنده یا جستجوی محلی تعریف میکنند.
· الگوریتم هاییکه بر هدایت هیورستیک یک الگوریتم سازنده یاجستجویمحلی متمرکزمیشوند به گونهایکه آن- الگوریتم ها بتواند بر شرایط حساس (مانندفرار از بهینه محلی(2 غلبه کند. به این الگوریتم ها متاهیورستیک3گفته می-شود.
· الگوریتم هاییکه برترکیب یک چارچوب یا مفهوم هیورستیک با گونه هایی از برنامه ریزی ریاضی متمرکزمیشوند. یکی از جدیدترین الگوریتم های تکاملیکه معرفیشده است، الگوریتم بهینه سازی گلهشیرها است که خصوصیات بسیارخوبی را درسرعت همگرایی و دقت بالا در حل مسائل با ابعاد بزرگ و دستیابی به نقطه بهینه ی کلی از خود نشان - داده است. به منظور بالابردن دقت و نرخ همگرایی این الگوریتم در این مقاله روشهایی برای بهبود الگوریتم پیشنهاد شده است.
نتیجه پیادهسازی نشان میدهد که استفاده از روشهای مطرح شده در الگوریتم بهینه سازی گله شیرها، دقت و سرعت یافتن جوابهای بهینه را بهبود میدهد. روشهای متفاوتی برای حل یک مسئله بهینه سازی وجود دارد. اکثر این روشها از فرآیندهای طبیعی الهام گرفته شده اند. این روشهامعمولاًبا مجموعهایی از متغیرها آغاز میشوند و سپس برای بدست آوردنکمینه یا بیشینه تابع هدف تکامل مییابند.
دراین مقاله روشهایی برای بهبود الگوریتم بهینه سازی گله شیرها4 پیشنهادشده است. به طور معمول تولید ضریب باروری برای تولید مثل به صورت تصادفی صورت میگیرد که میتواند منجر به کاهش کارایی الگویتم گردد. جهت مقابله با این موضوع ضریب باروری بر اساس مقدار تابع برازندگی5 و استفاده ازروشآشوب6 برایتولید ضریب - باروری پیشنهاد شده است.
ساختار ادامه مقاله به صورت زیر است: در بخش 2 مروری برکارهای گذشته انجام میگیرد. در بخش 3 الگوریتم بهینه سازی گله شیرها روش پیشنهادی ارائه میگردد. بخش 4 به معرفی روشپیشنهادی ارائه می گردد. در بخش 5 بررویتابعآزمایش مورد ارزیابی قرار گرفته است. در نهایت نتیجهگیری وکارهایآینده دربخش 6 نشان داده شده است.

.2 مروری برکارهای گذشته
الگوریتم ژنتیک(GA) 7، یکی از محبوبترین تکنیکها درتحقیقات محاسبات تکاملی است. الگوریتم ژنتیک از عملگرهای الهامگرفته شده از تنوع ژنتیکی طبیعی و انتخاب طبیعیاستفاده میکند.[1-7-2] نمونهی دیگر بهینه سازی ازدحامذرات (PSO)8 است که توسط ابرهات و کندی9 در سال 1995 توسعه پیدا کرد. این الگوریتم بهینه -سازی تصادفی از رفتار اجتماعی گروه پرندگان یا دسته ماهیها الهامگرفته شده است 4]و.[3 بهینه سازی کلونی مورچگان(ACO) 10، الگوریتم بهینه سازی تکاملی دیگری است که از مطالعات و مشاهدات بر روی کلونی مورچهها الهام گرفته شده است.[2-5-6] از سوی دیگر الگوریتم تبرید شبیهسازی شده(SA) 11 یک الگوریتم بهینه سازی فرا ابتکاری12 ساده و اثر بخش در حل مسائل بهینه سازی است که روش مبنی بر تکنیک تبرید تدریجیاست. تکنیک تبریدتدریجی به وسیله متالورژیستها13برای رسیدن به حالتیکه در آن ماده جامد، به خوبی مرتب و انرژی آنکمینه شده باشد، استفاده میشود. اینتکنیک شامل قراردادن ماده دردمای بالا و سپسکمکردن تدریجی این دماست.[7-9] علاوه - بر این روشهای شناخته شده، تحقیقات برروی الگوریتم های بهینه سازی الهام ازطبیعت همچنان ادامه دارد. در[10] یک تکنیک بهینه سازی جدید به نام متد انفجاری نارنجک(GEM) 14 و ایدههای اساسی آن، شامل مفهوم مسیرجستجوی بهینه (OSD) به دقت تشریح شده است. در [11] یک متد بهینه سازی ازدحام ذرات جدید مبتنی بر الگوریتم انتخاب - کلونال15 جهت پیشگیری ازهمگرایی زودرس و تضمین تنوع جمعیت پیشنهاد شده است.

.3 الگوریتم بهینه سازی گله شیرها
رفتارهای غریزی طبیعی این حیوان باعث طراحی استراتژی جستجو بهینه سازی در حل مسائل پیوسته گردیده است. با مطالعه مشخصات الگوریتم ، به این نتیجه میرسیم که الگوریتم گلهشیرها حساسیت بسیار بالایی به پارامترهای خود نداردکه ایننشاندهنده محکم بودن الگوریتم یا به اصطلاح مقاوم بودن16 الگوریتم میباشد؛ که درآن بروزرسانی جمعیت و رقابتهای اعضاء دوتا از مهمترین فاکتورهای استراتژی عملکرد خودگله(نخبه گزینی)17 و الگوریتم میباشد.
الگوریتم بهینه سازی گلهشیرها که توسط وانگ بو18 درسال 2012 معرفی شده یکی از جدیدترین و قویترین - روشهای بهینه سازیتکاملیاست؛ که به دلیل الگوریتم خاص و اصلاح یافتهاییکه دارد باعث حل بیشتر مشکلات و ضعفهای الگوریتم بهینه سازی تکاملی قبلتر مانند الگوریتم ژنتیک و الگوریتم ازدحامذرات گرفته تا الگوریتم رقابت - استعماری19که نسبتاًجدیدتر است شده و بنابراین دارای تواناییهمگرایی بسیار سریعتر و قدرت یافتن نقاط بهینه کلی به صورت بسیاردقیقتری است. در الگوریتم بهینه سازیگله شیرها با تغییر فضای جستجو کمک شایانی به جستجوی محلی درحین جستجوی عمومی میکند و به جوابهای بسیار دقیقتر و قابل اعتمادتری دست مییابند.

3.1 جزییات الگوریتم بهینه سازی گلهشیرها
در ادامه این بخش ابتدا مباحث پایه بررسی شده، سپس نحوه بدست آوردن جوابهای برتر با استفاده از رابطه-ایکه در بخش 2-1-3 نشانداده شده است، در ادامه استراتژی تقاطع و نحوه مقیاسبندی فضای جستجو بررسی شده و در نهایت روابطی برای بدست آوردن بهترین جوابها بیان شده است.

3.1.1 مباحث پایه
در شکل (1) جزئیات و فلوچارت الگوریتم بهینه سازی گله شیرها را مشاهده میکنید. همانند سایر الگوریتم های تکاملی، الگوریتم گله شیرها هم با یک جمعیت اولیه کارخود را شروع میکند یعنی جمعیتی متشکل از شیرها. جمعیت اولیه گله را 50 تایی فرض میکنیم، .M=50 درمسائل با n بعد اعضا گروه به صورت xik نمایش داده شدهکه برابر گله kام و عضو i ام است.

2.1.3 بدست آوردن دو جواب برتر
در الگوریتم گلهشیرها، همچنان که دو شیر توانایی بیشتری درهدایتگله دارد تا به نسبت یک شیر، بنابراین دو جواب برتر هر مرحله را بدست آورده و نگاه میداریم. فرمولهای ذکر شده در قسمتهای بعد، ازمقاله lpo می باشد؛ بنابراین در رابطه (1) داریم:

3.1.3 استراتژی crossover، تقاطع
هر تولید مثل به صورت 4 تایی انجام میشود با 2 تا ازبهترین جوابها اما فقط یک جواب تولید شده میتواند تا آخر زنده بماند؛ که نحوهی استراتژی زاد و ولد20 به این صورت میشود:

برای بدستآوردن اینضریب الگوریتم بهصورت تصادفیآن را تولید میکند به این صورتکه mc0 اولیه را تنظیم میکند و از رابطه (6)، mcik را بدست میآورد.

که رابطه (1,1) rand اعداد تصادفی بین 0 و 1 تولید میکند بنابراین mcik متفاوت برایxik بدست میآید. از چهار فرزند فقط یکیاز آنها درمرحله آخر زنده میماند که از رابطه (7) استفاده میکند:


جایی کهxk+1 عضو اول در مرحله k+1 میباشد به طور مشابه +1 عضو jام میباشد (j=2,3,…,M)
3.1.4 مقیاس بندی فضای جستجو
برای محاسبه مقیاس پذیری فضای جستجو از رابطه (8) استفاده می کنیم:

چنانچه الگوریتم روند بهینه سازی را ادامه ندهد متوقف میشود و ما نیاز داریم از روی2 جواب بهترین هر تکرار بهترین جهت با
بعدکارکرد تکاملی را بدست آوریم از رابطه((9 و(:(10

براساس بهترین بعد بدست آمده، 2 عضو بهترین به اینگونه بهینه می شوند:

ε مجموعه گامهای جستجو میباشند(گروهی از جوابها). فاصله اقلیدسی از x و j=1, 2,…, 2000 میباشد.
3.1.5 ایجاد بهترین جوابها
برای بدست آوردن بهترین جوابها از روابط (14) و (15) که در ادامه توضیح داده شده استفاده میکنیم:

درشکل (1) رسم شده است که نحوه اجرای الگوریتم را به خوبی نمایش میدهد.