بخشی از مقاله
چکیده-
الگوریتم runner-root، یک الگوریتم بهینه سازی فراابتکاری جدید میباشد که برای حل مسائل بهینهسازی پیچیده بسیار مفید میباشد. این الگوریتم از گیاهانی از قبیل توتفرنگی و گیاه عنکبوتی الهام گرفته شده است که سرعت همگرایی و دقت بالایی در حل مسائل تکگانه و چندگانه و دستیابی به نقطه بهینه سراسری دارد. در این مقاله برای ایجاد توازن بین اکتشاف و استخراج عاملها، یک روش برای تطبیق پویای پارامترها در الگوریتم بهینهسازی فراابتکاری runner-root ارائه شده است.
همچنین الگوریتم فراابتکاری runner-root با الگوریتم حداقل جمعیت جستجو ترکیب شده است که در آن با استفاده از بردارهای متعامد، فضای جستجوی مسئله را به طور کامل پوشش میدهیم. در این مقاله، ما برای بهبود همگرایی و حفظ تنوع جمعیت در حین فرآیند جستجو، از قوانین فازی برای کنترل پارامترهای کلیدی الگوریتم runner-root استفاده میکنیم تا به بهترین انطباق پویای ممکن مقدار این پارامترها برسیم.
کارایی الگوریتم پیشنهادی توسط توابع ریاضی پایه CEC’2005 استاندارد که شامل مسائل تکگانه و چندگانه میباشد، ارزیابی می شود و نتایج با الگوریتم runner-root مقایسه می شود. نتایج شبیهسازی نشان میدهد که الگوریتم پیشنهادی دارای دقت و سرعت همگرایی بالاتری نسبت به الگوریتم runner-root میباشد و توانایی الگوریتم در رسیدن به بهینه سراسری مسئله، افزایش یافته است.
-1 مقدمه
در چند دهه اخیر، استفاده از الگوریتمهای تکاملی برای حل مسائل گوناگون جستجو و بهینهسازیهای پیوسته و گسسته، رشد فزایندهای داشته است. مهمترین عاملی که سبب شده تا استفاده از این الگوریتمها به این اندازه مورد توجه جوامع علمی مختلف قرار گیرد، سادگیاِعمال شدن و کاربرد آنها برای حل مسائل با ماهیت بسیار متفاوت است. هر چند استفاده از این الگوریتمها هیچ گونه ضمانتی را برای یافتن پاسخ بهینه به دست نمیدهد، اما توانایی بیبدیل این الگوریتمها در کشف پاسخهای نزدیک به بهینه در زمانی به نسبت کوتاه، موجبات شهرت فراوان آنها را فراهم ساخته است
در سال های اخیر تحقیقات زیادی بر روی الگوریتم های تکاملی با الهام از طبیعت یا جوامع انسانی، صورت گرفته است. یکی از جدیدترین الگوریتمهای تکاملی که جدیداً معرفی شده است الگوریتم فراابتکاری بهینه سازی runner-root میباشد که سرعت همگرایی و دقت بالایی در حل مسائل تکگانه - unimodal - و چندگانه - multimodal - و دستیابی به نقطه بهینه سراسری دارد . به منظور بالا بردن دقت و نرخ همگرایی این الگوریتم، در این مقاله ایده هایی برای بهبود الگوریتم پیشنهاد شده است.
منطق فازی یا منطق چند مقداری براساس نظریه مجموعه فازی که توسط زاده در سال 1965 پیشنهاد شده است، میباشد. که به ما در مدلسازی دانش از طریق استفاده از قوانین فازی if-then کمک میکند. نظریه مجموعه فازی یک جبر سیستماتیک در رابطه با اطلاعات زبانی فراهم میکند ، و محاسبات عددی را با استفاده از برچسبهای زبانی تعیین شده توسط توابع عضویت، بهبود میبخشد
یکی از روشهایی که در الگوریتم های تکاملی منجر به دستیابی به پاسخهای بهتر در یک مسئله بهینه سازی می گردد انطباق پارامتر پویا در الگوریتم می باشد. در سالهای اخیر تعدادی از محققان تلاش کردهاند برای بهبود کارایی این الگوریتمها، تکنیکهای مختلفی را برای تطبیق پویای پارامترهای مهم بکار ببرند. یکی از این تکنیکها استفاده از منطق فازی میباشد.
آلبرتو سومبرا و همکارانش [4]، یک الگوریتم جستجوی گرانشی جدید ارائه دادند که پارامتر آلفای الگوریتم با بکاربردن منطق فازی تغییر پیدا میکند و به هر عامل در الگوریتم، گرانش و سرعت متفاوتی می دهد و به این ترتیب بین اکتشاف و استخراج عاملها توازن ایجاد میشود، و در انتها باعث بهبودی عملکرد الگوریتم میشود.
پاتریشیا ملین و همکارانش [5]، همگرایی و تنوع جمعیت در الگوریتم بهینهسازی ازدحام ذرات - PSO - را بهبود میدهند، به این طریق که دو پارامتر کلیدی الگوریتم، ضریب یادگیری شناختی - c1 - و ضریب یادگیری اجتماعی - c2 - را برای رسیدن به بهترین تطبیق پویای ممکن از مقدار پارامترها، فازی میکنند و سرانجام کارایی الگوریتم را بالا میبرند.
فوریه والدز و همکارانش [6]، یک الگوریتم ترکیبی از الگوریتم بهینهسازی ازدحام ذرات - PSO - و الگوریتم ژنتیک - GA - ارائه دادند که از سه سیستم فازی برای بهبود کارایی الگوریتم ترکیبی استفاده کردهاند. اولین سیستم فازی برای مقدار بهینه تابع محک مورد نظر تصمیمگیری میکند و دو سیستم فازی دیگر، برای پیدا کردن پارامترهای بهینه به بهترین روش ممکن - برای PSO پارامترهای c1 و c2، برای GA پارامترهای برش k1 و جهش - k2 استفاده میشود.
اندازه جمعیت یک پارامتر اساسی در کارایی فراابتکاریهای مبتنی بر جمعیت است. جمعیت بزرگتر اکتشاف را تقویت میکند ولی نسلهای کمتری را تولید میکند و این میتواند شانس همگرایی را کاهش دهد. جستجو کردن با جمعیت کوچک میتواند شانس همگرایی و استفاده کارآمد از ارزیابیهای تابع - FEs - را افزایش دهد، ولی میتواند خطر همگرایی زودرس را تحریک کند .[7] تکنیک های مختلفی برای تنوع بیشتر جمعیت از قبیل آشوب، آنتروپی، عملگرهای ژنتیک و غیره وجود دارند.
لئو و همکارش [8]، در سال 2014 روشی به عنوان بهبود الگوریتم زنبور عسل آشوبناک با استفاده از آنتروپی ارائه دادند، که در این روش با در نظر گرفتن بینظمی موجود در جمعیت، بدترین عضو را به سمت کاهش این بینظمی با استفاده از آنتروپی محاسبه شده ی کل جمعیت، حرکت می دهند و به این ترتیب همهی اعضای گروه در فرآیند تکامل مؤثر خواهند بود.
رائو و همکاران [9]، در سال 2012 الگوریتم جهش قورباغه را با جایگزینیِ بدترین راهحل در هر زیرجمعیت، با حاصل ترکیب بهترین راهحل زیرجمعیت و بهترین راهحل جمعیت، برای طراحی بهینه سیلندر مرکب چند لایه پیشنهاد کردهاند، و کارایی الگوریتم را بالا بردند.
بلوف-روهلر و همکارش [10]، یک الگوریتم جدید با نام حداقل جمعیت جستجو - Minimum Population Search - ، در سال 2013 برای جمعیتی با دو عضو ارائه دادهاند که به طور ویژه برای کار کردن با یک جمعیت بسیار کوچک طراحی شده است. برای کنترل کردن همگرایی و ایجاد تنوع، آستانه همگرایی بهعنوان یک جزء اصلی این الگوریتم در نظر گرفته شده است. بردارهای متعامد، به فرآیند جستجو در MPS اجازه میدهد که تمام ابعاد مسئله - دو بُعد - را پوشش دهد. در ابعاد بالاتر یک مشکل این روش، به دست آوردن بردار متعامد با ابرصفحهی d بُعدی میباشد d - بُعد مسئله است - ، که این محاسبه، هزینه محاسباتی بالایی دارد.
روهلر و همکارش [11]، برای رفع این مشکل در سال 2015 از مرکز ثقل جمعیت در الگوریتم استفاده کردند، به این علت که اعضای جاری جمعیت، نمایندگانی از بهترین نواحی جستجو میباشند و مرکز ثقل تمام این اطلاعات را فقط در یک نقطه ثبت میکند. در نسخه MPS با استفاده از مرکز ثقل، گام متعامد با در نظر گرفتن یک بردار عمود بر خط والد-مرکز ثقل، انجام میشود. این سادهسازی در الگوریتم MPS باعث میشود هزینه محاسباتی کمتر شود و از اطلاعات تمام جمعیت استفاده کرد.
در این مقاله، برای ایجاد توازن بین اکتشاف و استخراج عاملها و حفظ تنوع جمعیت در حین فرآیند جستجو، از قوانین فازی برای کنترل پارامترهای کلیدی الگوریتم runner-root استفاده میکنیم تا به بهترین انطباق پویای ممکن مقدار این پارامترها برسیم. همچنین برای بهبود سرعت همگرایی و ایجاد تنوع در جمعیت الگوریتم runner-root، از الگوریتم حداقل جمعیت جستجو استفاده میکنیم که در آن با استفاده از بردارهای متعامد، فضای جستجوی مسئله را به طور کامل پوشش میدهیم. کارایی الگوریتم پیشنهادی توسط توابع ریاضی پایه & - &ʼ2005 استاندارد ارزیابی و نتایج با الگوریتم runner-root مقایسه میشوند.
بخش بندی مطالب این مقاله به صورت زیر است: در بخش 2، خلاصه ای از مفاهیم پایه آمده است، در بخش 1-2، سیستمهای منطق فازی بطور خلاصه معرفی شدهاند. در بخش 2-2، الگوریتم حداقل جمعیت جستجو بر اساس مرکز ثقل آمده است. و بخش 3-2، به تشریح الگوریتم فراابتکاری runner-root پرداخته است. در بخش 3، روش پیشنهادی مورد بحث قرار گرفته است. در بخش 4، نتایج تجربی روش پیشنهادی، بر روی تعدادی تابع محک مورد ارزیابی قرار گرفته است، و در نهایت نتیجهگیری نیز در بخش 5 ارائه شده است.
-2 خلاصهای از مفاهیم پایه
در این بخش در مورد مفاهیم پایهای که در این مقاله استفاده شدهاند صحبت میکنیم. در ابتدا با سیستمهای منطق فازی و الگوریتم حداقل جمعیت جستجو آشنا میشویم و بعد از آن به تشریح الگوریتم فراابتکاری میپردازیم.
-1-2 سیستمهای منطق فازی
تمام سیستمهای منطق فازی نوع اول - Fuzzy Logic - Systems بطور وسیع در کاربردهای مهندسی استفاده شدهاند. مزیت اصلی سیستمهای منطق فازی اینست که میتواند دانش رمزگذاری شده که توسط انسان قابل فهم میباشد را بعنوان رولهای فازی کلامی داخل کند. بعلاوه، سیستمهای منطق فازی میتواند از عهده ابهام، عدم دقت، عدم قطعیت برآید
یک سیستم منطق فازی نوع اول از چهار جزء اصلی ساخته شده است: فازی کردن ورودی، موتور استنتاج فازی، رول بیس فازی و غیر فازی کردن خروجی. سیستم منطق فازی،ممدانیِ فرض شده است، رول بیس فازی رول های کلامی فازی را به شکل قابل فهم، حفظ می کند. بعنوان یک مثال، فرض کنید رول Rk بصورت رابطه - 1 - است:
که سمبل A jk مجموعه فازی ورودی اُمj و B k مجموعه فازی خروجی را نشان می دهد، n ابعاد بردار ورودی x میباشد، و yk متغیر خروجی وابسته میباشد. هر المان از بردار ورودی در ابتدا با استفاده از تابع عضویت فازی مربوطه فازی میشود.
بطور مثال گوسین، مثلثی، ذوزنقه ای و غیره - . فازی کردن ورودی xi در مجموعه فازی Aik یک درجهی عضویتAik - xi - را نتیجه میدهد. با بکاربردن مینیمم t-norm، شدت قدرت رولRk میتواند بصورت رابطه - 2 - محاسبه شود:
بمحض بکاربردن شدت قدرت رول از طریق عملگر t-norm - بطور مثال مینیمم یا حاصلضرب - برای هر تالی رول، مجموعه های فازی خروجی با بکاربردن عملگر - -conormمثلاًt عملگر ماکسیمم - جمع می شوند، که در نتیجه یک مجموعه فازی خروجی B بدست می آید. توضیح جزئیات پردازش استنتاج فازی در [3] میتواند پیدا شود.
سرانجام، مجموعه فازی خروجی B غیرفازی میشود به این ترتیب مقدار خروجی پایانی بدست میآید. چندین تکنیک غیرفازی کردن در نوشتهها می تواند پیدا شود [13]مثلاً. غیرفازی کنندهی مرکز ثقل - centroid - ، غیرفازی کنندهی مرکز مجموعها، غیرفازی کنندهی ارتفاعها، یا غیرفازی کنندهی مرکز مجموعهها. در این مقاله با توجه به رابطه - 3 - ، غیرفازی کنندهی مرکز ثقل برای تولید مقدار خروجی پایانی y استفاده می شود:
-2-2 الگوریتم حداقل جمعیت جستجو بر اساس مرکز ثقل
برای اینکه مطمئن شویم جمعیت اولیه به خوبی تقسیمبندی شده است، نقاط اولیه روی قطر فضای جستجو انتخاب میشوند. در ابعاد بالا، هر عضو جمعیت با بکار بردن رابطه - 4 - مقداردهی اولیه میشود.
sk ، kاُمین عضو جمعیت است، rsi اعداد تصادفی هستندکه میتوانند - یا باشند و bound مرز بالا و پایین هر بُعد میباشد. این روش منجر میشود که، راهحلهای اولیه نسبت به راهحلهای تصادفی یکنواخت، توزیع بهتری داشته باشند.
سپس در هر نسل، الگوریتم MPS بر اساس مرکز ثقل، یک مجموعه ساده از عملیات را انجام میدهد. اول، مقادیر آستانه همگرایی طبق رابطه - 5 - به روز رسانی میشود، و در ادامه مرکز ثقل جمعیت - - xcentroid محاسبه میشود .
در رابطه - 5 - ، diagonal قطر فضای جستجو و کسری از آن، FEs مجموع تعداد توابع ارزیابی قابل دسترس و k تعداد توابع ارزیابی استفاده شده، میباشد و پارامتر نرخ تنزل آستانه را کنترل میکند - max _ step دو برابر min _ step است - .
سپس هر عضو به عنوان راهحل والد، برای ایجاد یک فرزند بکارگرفته میشود. در این مرحله فقط راه حلها تولید خواهند شد.
