بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهبود عملکرد الگوریتم کریل مبتنی بر تئوری آشوب
چکیده - الگوریتم بهینه سازی کریل (KHA) که یک الگوریتم بهینه سازی بیولوژیکی است که از رفتار اجتماعی گروهی کریل ها برای حل مسائل بهینه سازی سراسری تقلید می کند. موقعیت هر کریل در زمان وابسته به حرکت القایی از سایر کریل ها، حرکت به سمت غذا و انتشار تصادفی است. در این مقاله تئوری آشوب را با KHA برای بهبود در حل مسائل بهینه سازی سراسری ترکیب می کنیم. نگاشت کیاتیکی در حرکت القایی بکار می رود. روش پیشنهادی بر روی چند مساله ارزیابی بکار می رود. نتایج نشان می دهد که الگوریتم کیاتیک کریل (CKHA) از الگوریتم کریل استاندارد کارایی بهتری دارد.
کلمات کلیدی- کریل ، الگوریتم بهینهسازی کریل (KHA) ، الگوریتم کیاتیکی کریل (CKHA) ، تئوری آشوب
-1 مقدمه
بدست آوردن بهترین جواب ممکن برای یک مساله با توجه به شرایط حاکم بر آن را بهینهسازیمیگویند. بهینهسازی را میتوان فرایندی برای یافتن شرایطی دانست که، مقدار بیشینه و یا کمینه یک تابع در آن رخ میدهد. حل مسائل بهینهسازی پارامتری غیرخطی پیچیده، از مشکلات مهم دنیای امروز است که در مسائل بسیار زیادی کاربرد دارد. در سالهای اخیر برای حل این مسائل به "روشهای ابتکاری برگرفته از طبیعت" روی آورده اند.الگوریتمهای الهام گرفته بیولوژیکی، یکی از مهمترین دستههای الگوریتمهای الهام گرفتهشده از طبیعت و متاهیورستیک است. این الگوریتمهای بیولوژیکی زیستی، از بهترین ویژگیهای موجود در طبیعت، که در طول میلیونها سال تکامل یافتهاند، تقلید میکنند.الگوریتم بهینهسازی کریل((KHA یک الگوریتم بهینهسازی جدید زیستی مبتنی بر هوش جمعی است که درسال 2012 توسط امیرحسین گندمی و امیرحسین علوی براساس زندگی گروهی کریلها در اقیانوس معرفی گردید.[1] این روش براساس شبیهسازی زندگی گروهی کریلها درپاسخ به فرایندهای بیولوژیکی و زیست محیطی خاص است و تقریبا همه ضرایب لازم برای پیادهسازی این الگوریتم از مطالعات در جهان واقعی بدستآمدهاست.
با وجود آنکه، این الگوریتم نسبت به سایر الگوریتمهای تکاملی کارایی بهتری دارد، اما بازهم میتوان برای افزایش دقت و سرعت از ترکیب آن با سایر روشها استفاده کرد. اشکال اصلی این الگوریتم در ارتباط با پارامترهای تصادفی آن است که کارایی الگوریتم را تحت تاثیر قرار میدهد و ممکن است که نتوانند یک پوشش سراسری را در کل فضای جستجو تضمین کند و در نتیجه سرعت و دقت نسبتا کمتر خواهد شد. در حرکت کریلها به سمت غذا و یا ازدحام از اعداد تصادفی استفاده می شود، که این اعداد تصادفی ممکن است کل دامنه را پوشش ندهند. علاوهبراین، به دلیل حرکت کریلها و ایجاد همسایگیهای محلی، کریلها ممکن است به یک نقطه همگرا شوند که این نقطه بهترین موقعیت را در بین سایر ذرات دارا است، اما همیشه بهینه نیست.
آشوب یا کیاس پدیده ای است که میتواند بهعنوان حرکتی در یک دامنهی محدود شناخته میشود که در یک سیستم دینامیک غیرخطی قطعی رخ دادهاست. چنین حرکتی بسیار شبیه پروسهی حرکت تصادفی است. این حرکت به شرایط اولیه بسیار حساس میباشد، که از این خاصیت گاهی با نام اثر پروانهای، برای نشان دادن بیثباتی، یاد میشود.[2]
در الگوریتمهای بهینهسازی برپایه جستجوی تصادفی، می توان از توالیهای کیاتیکی بجای توالیهای تصادفی استفاده کرد که باتوجه به عدم تکرار و تنوع کیاتیکی، جستجوهایی با سرعت بالاتر از جستجوهای تصادفی صورت می گیردو باعث نتایج خوبی میشود.[3,4] از جمله میتوان از ترکیب تئوری آشوب با الگوریتم ژنتیک[5]، الگوریتم بهینهسازی ازدحام ذرات[6,7]، الگوریتم تبرید تدریجی[8]، الگوریتم کلونی مورچگان[9]، الگوریتم کلونی زنبور عسل[10]، الگوریتم رقابت استعماری[11]، الگوریتمNSGA-II [12]و الگوریتم شب پره[13] نام برد که باعث افزایش سرعت و دقت در پاسخها شدهاست و همچنین احتمال قرارگرفتن در بهینههای محلی را کاهش داده و تنوع بیشتری را در پاسخها ایجاد میکند.
هدف در این تحقیق ارائه یک روش ترکیبی جدید بر پایه الگوریتم کریل و تئوری آشوب میباشد تا بتوانیم روشی با پیچیدگی محاسباتی کمتر و دقت بالاتر برای حل مسائل بهینهسازی غیرخطی ابداع کنیم.
-2 الگوریتم بهینهسازی کریل
الگوریتم بهینهسازی کریل، یک الگوریتم جدید زیستی مبتنی بر هوشجمعی است که برای بهینهسازی مسائل غیرخطی پیوسته مناسب است.[1] این جانور سخت پوست که ظاهری شبیه به میگو دارد الگوهای مهاجرتی خاصی برای زندگی در اقیانوس دارد. الگوریتم کریل، از ویژگیهای اصلی این گونهها مانند، توانایی تشکیل جمعیتهای بزرگ، جستجوی محلی و سراسری برای پیداکردن غذا و همچنین تلاش برای بالا بردن چگالی جمعیت گروهی و همچنین حذف کریل های فردی توسط شکارچیان استفاده میکند. تشکیل گروه کریلهاپس از شکار به پارامترهای زیادی وابسته است و بصورت یک فرایند مالتی ابجکتیو است که دارای دو هدف اصلی -1 افزایش تراکم کریلها و -2 رسیدن به غذا است. در الگوریتم بهینهسازی کریل یک روش متاهیورستیک جدید برای حل مسائل بهینهسازی گلوبال در نظرگرفته میشود. افزایش چگالی کریلها (جذب کریلها) و پیدا کردن غذا (در سطحی با تراکم بالای مواد غذایی) به عنوان اهداف استفاده میشوند که در نهایت منجر به این میشود که گروه کریلها به مینیمم گلوبال راهنمایی شوند.
فواید متد پیشنهادی بصورت زیر است:
هر عامل مطابق با برازندگیاش در فرایند کمک میکند
-هر همسایه یک اثر جاذبه و دافعه روی حرکت دیگر کریلها دارد
-بنابراین مانند یک جستجوی محلی برای هر کریل عمل کند.
-مرکز غذا مطابق برازندگی همه کریلها تعیین می شود که برای تخمین بهترین گلوبال موثر است.
شکار و حذف افراد، منجر به کاهش میانگین تراکمکریلها، و فاصله گروهی آنها ازمحل غذا میشود. برازندگی هر کریل به ترکیبی از فاصله تا غذا و فاصله تا بالاترین تراکم جمعیت کریلها بستگی دارد. موقعیت هر کریل در زمان و در سطح دو بعدی تحت کنترل سه عمل زیر است:
(1حرکت ناشی از دیگر کریل ها
(2فعالیت برای یافتن غذا
(3انتشار تصادفی
عامل اول و دوم بعنوان دو استراتژی محلی و سراسری بصورت موازی کار میکنند و باعث بهینهسازی سراسری و محلی میشوند و سومین عامل، برای انجام یک جستجوی تصادفی به متدولوژی اضافه شدهاست.
برای این که الگوریتم قادر به جستجو در فضاهایی با ابعاد دلخواه باشد، مدل لاگرانژی به یک فضای N بعدی تصمیم تعمیم داده شده است.
Ni حرکت القایی از دیگر کریلها است،Fi فعالیت برای یافتن غذا است و Di انتشار تصادفی کریل شماره i است.
در طبیعت کریلها سعی میکنند، تراکم بالا را حفظ کنند و با توجه به اثرات متقابل بر یکدیگر حرکت می کنند. i که جهت حرکت القایی اشان است به چگالی ازدحام محلی (اثرمحلی)، چگالی ازدحام محل هدف (اثرهدف) و دافعه چگالی ازدحام (اثردافعه) بستگی دارد. این حرکت به این صورت تعریف میشود.
Nmax ماکزیمم سرعت القایی و wn اینرسی حرکت القایی در بازه[0,1] آخرین حرکت القایی است. یک اثر محلی است که توسط همسایگان ایجاد میشود و اثر هدف است که توسط بهترین کریل تولید میشود. مقدار Nmax برابر 0.01(ms-1) در نظر گرفتهمیشود. اثر همسایگان میتواند مانند یک جاذبه و دافعه در یک جستجوی محلی در نظر گرفته شود. اثر همسایهها در حرکت یک کریل را این طور تعریف میکنیم:
Kbest و Kworst مقدار برازندگی بهترین و بدترین کریل، Ki مقدار تابع هدف برای کریل iام، kj برازندگی همسایه jا م، X موقعیتهای مربوط و NN تعداد همسایهها است. سمت راست روابط (ط) و (ن) و (د) شامل چند بردار یکه و تعدادی مقدار برازندگی نرمالایز است که بردارها جهتهای القایی را توسط همسایهها نشان میدهند و هر مقدار تاثیر یک همسایه را نشان میدهد که میتواند جاذب یا دافع باشد و مقدار نرمالایز میتواند مثبت یا منفی باشد.
برای انتخاب همسایهها میتوان از(Sensing Distance (ds در اطراف یک کریل استفاده کرد (شکل(1
ds,i مقدار فاصله حسی برای کریل iام است و N تعداد کریلها. با استفاده از 7 اگر فاصله دو کریل کمتر از فاصله حسی باشد، انگاه آنها همسایه هستند.
تاثیر یک کریل با بهترین برازندگی بر روی کریل iام است کهما را به بهینه سراسری نزدیک میکند.
cbest ضریب تاثیر کریلی با بهترین برازندگی بر روی کریل iام است. این ضریب باعث می شود که بهترین کریل موثرتر از بقیه همسایه ها باشد.
Rand یک مقدار تصادفی ین 0 و 1 است که برای بالا بردن مقدار اکتشاف است، I تعداد تکرار واقعی وImax ماکزیمم تعداد تکرارها است.
حرکت برای یافتن غذا با دو پارامتر اصلی محل موادغذایی و تجربه قبلی در مورد محل غذا برای کریل iام بدین صورت است:
VF سرعت یافتن غذا با مقدار 0.02(ms-1) است، wf اینرسی حرکت به سمت غذا است که بین[0,1] است، Foldi آخرینحرکت به سمت غذا، مقدار جاذبه غذا و اثر بهترین برازندگی کریل iام تاکنون است.
برای محاسبه مقدار جاذبه غذا نخست باید مرکز غذا پیدا شود. در این الگوریتم، مرکز مجازی غلظت غذا مطابق با توزیع برازندگی کریل ها تخمین زده میشود.
cfood ضریب غذا است. تاثیر غذا در گروههای کریل در طول زمان کاهش مییابد. ضریب غذا بدین صورت محاسبه می شود:
جاذبه غذا احتمال جذب جمعیت کریلها را به سمت بهینه سراسری افزایش میدهد و براین اساس، کریلها پس از چند تکرار در اطراف بهینه سراسری هستند.
تاثیر برازندگی بهترین کریل برروی کریل iام با فرمول زیر بدست میآید:
kibest بهترین موقعیت قبلی ملاقات شده در کریل iام است.
انتشار فیزیکی کریلها یک فرآیند تصادفی است که برحسب یک ماکزیمم سرعت انتشار و یک بردار جهت تصادفی باشد.
ماکزیمم سرعت انتشار فیزیکی و بردار جهت تصادفی استکه آرایهای از مقادیر تصادفی بین 1- و 1 است. هرچه موقعیت یک کریل بهتر شود، حرکت تصادفی باید کمتر شود. بنابراین ترم دیگری مانند (14) به فرمول انتشار فیزیکی اضافه شدهکه این اثر را در نظر میگیرد. و بطور پیوسته با افزایش تعداد تکرار، به صورت خطی سرعت تصادفی را کاهش میدهد.
بطورکلی فرکانس حرکت تعریف شده، موقعیت یک کریل را به سمت برازندگی بهتر تغییر میدهد . حرکت بـه سـمت غـذا و حرکـت القـایی شامل دو استراتژی محلی و دو استراتژی سراسری اسـت کـه بصـورت موازی برای ساختن یک الگوریتم قوی کار میکنند. مطابق فرمولهای قبلی حرکت القایی از دیگر کریلها و حرکت به سمت غذا، برای کریل iام، میتواند هم قدرت جذب و هم قدرت دفـع داشـته باشـد و انتشـار فیزیکی نیز یک جستجوی تصادفی را در این الگوریتم انجام مـیدهـد. بردار موقعیت یک کریل در طول زمان t تا با فرمـول زیـر نشـان داده میشود:
باید توجهشود که یکی از مهمترین ثابتها استو مانند یک عامل مقیاسگذاری در بردار سرعت است . کاملا به فضای جستجو بستگی دارد و میتوان آن را از فرمول زیر بدست آورد:
NV تعداد کل متغیرها، LBj و UBj بترتیب حد پایین و بالای متغیر jام است. بنابراین تفریق مطلق آن ها فضای جستجو را
