بخشی از مقاله
چکیده
الگوریتم سیاه چاله، یک الگوریتم تکاملی است که به علت سادگی و کارایی مناسبش مورد توجه محققان قرار گرفته است. ترکیب الگوریتم سیاه چاله با الگوریتم جستجوی گرانشی - BHGSA - به منظور افزایش پوشش سراسری فضای جستجو، در این مقاله ارائه شده است. روش پیشنهادی بر روی 20 تابع محک از مجموعه توابع CEC 2014، مورد آزمایش قرار گرفته است. مقایسه الگوریتم ترکیبی با الگوریتمهای سیاه چاله، جستجوی گرانشی و بهینهسازی ازدحام ذرات، نشان دهنده کارایی بالاتر الگوریتم پیشنهادی است.
1 مقدمه
بهینهسازی به این مفهوم است که بین پارامترهای یک تابع به دنبال مقادیری باشیم که تابع را کمینه و یا بیشینه نمایند. کلیهی مقادیر مناسب جهت این امر را، راهحلهای ممکن و بهترین مقدار از این مقادیر را، راهحل بهینه مینامند. وجود مسائل پیچیده و مسائلی که نیاز به بهینهسازی دارند، باعث مطرح شدن تعداد زیادی الگوریتم بهینهسازی شده است. در چند دهه اخیر، الگوریتمهای تکاملی در بسیاری از زمینههای علوم مهندسی و علمی استفاده شدهاند. الگوریتم تکاملی با تولید جمعیت اولیه که هر عضو، کاندیدی از پاسخ مساله میباشد، آغاز میگردد. مقدار تابع هدف به ازای هر عضو جمعیت که معیار سنجش آن عضو میباشد، محاسبه شده و در نهایت با اتخاذ یک روش انتخاب، جوابهای نامناسبتر در هر مرحله، دور ریخته میشود. مراحل مذکور با انتخاب پاسخهای بهتر در هر مرحله، تا زمانی که پاسخ بهینه در مساله کشف نگردد، تکرار خواهد شد .[1]
در سالهای اخیر تحقیقات زیادی بر روی الگوریتمهای تکاملی با الهام از طبیعت یا جوامع انسانی، صورت گرفته است. از جمله این الگوریتمها میتوان به الگوریتم ژنتیک [2]، الگوریتم بهینهسازی ازدحام ذرات [3]، سیستم ایمنی مصنوعی [4]، الگوریتم بهینهسازی مورچگان [5]، الگوریتم جستجوی باکتریایی [6]، الگوریتم جستجوی گرانشی [7] و الگوریتم سیاهچاله [8] اشاره نمود. الگوریتم سیاه چاله - BH 1 - یک روش ابتکاری است که از پدیده طبیعی سیاه چاله الهام گرفته شده است، و به دلیل سادگی و سهولت اجرا، توجه زیادی را به خود جلب کرده و از زمان ابداعش برای حل بسیاری از مسائل بهینهسازی عملی [9-12] به کار برده شده است.
الگوریتم جستجوی گرانشی - GSA2 - روش بهینهسازی براساس هوش جمعی است که با الهام از مفاهیم جرم و نیروی جاذبه و شبیهسازی قوانین مرتبط با آن ارائه شده است .[7] این الگوریتم در کاربردهای مختلفی [14-17] استفاده شده است. در این مقاله، ما به بررسی ترکیب مکانیزمهای موثر هر یک از دو الگوریتم BH و GSA به هنگام جستجوی راهحل مسائل بهینهسازی پیوسته میپردازیم. با این هدف که بتوان یک الگوریتم ترکیبی فراهم نمود که توانایی بالاتری نسبت به هریک از دو الگوریتم ذکر شده در یافتن جواب بهینه سراسری برای حل مسائل بهینهسازی داشته باشد.
سایر مطالب در این مقاله، به این شرح می باشد؛ بخش دوم به توضیح الگوریتمهای سیاه چاله و جستجوی گرانشی میپردازد. بخش سوم الگوریتم ترکیبی سیاه چاله و جستجوی گرانشی - BHGSA - توضیح داده میشود. در بخش چهارم آزمایشات و نتایج مورد بحث و بررسی قرار میگیرند و در نهایت در بخش پنجم نتیجهگیری بیان میشود.
.2 مفاهیم پایه
در این بخش به بررسی الگوریتم سیاه چاله و الگوریتم جستجوی گرانشی میپردازیم.
.1-2 الگوریتم سیاه چاله
الگوریتم سیاه چاله یک الگوریتم تکاملی است که در سال 2013 توسط حاتملو معرفی گردید و اولین بار بر روی مسئلهی خوشهبندی دادهها مورد استفاده قرار گرفت. این الگوریتم از پدیده سیاه چاله الهام گرفته شده است و مشابه دیگر الگوریتمهای مبتنی بر جمعیت، الگوریتم BH با جمعیت اولیه از راهحلهای نامزد برای یک مسئله و بهینهسازی تابع هدف، که برای آنها محاسبه میشود، شروع میشود. در هر تکرار از الگوریتم سیاه چاله، بهترین نامزد انتخاب شده، سیاه چاله در نظر گرفته میشود، و سپس شروع به کشیدن نامزدهای دیگر اطرافش میکند، که ستاره نامیده میشوند. اگر یک ستاره بیش از حد به سیاه چاله نزدیک شود، توسط سیاه چاله بلعیده خواهد شد و برای همیشه از بین میرود. در این صورت، یک ستاره جدید - راه حل نامزد - به طور تصادفی تولید و در فضای جستجو قرار داده میشود و شروع به جستجوی جدید میکند .[8]
مانند سایر الگوریتمهای مبتنی بر جمعیت، در الگوریتم سیاه چاله جمعیت راه حلهای نامزد - ستارهها - به طور تصادفی تولید و در فضای جستجو مسائل یا تابع قرار میگیرند . پس از مقدار دهی اولیه، مقدار برازش جمعیت، ارزیابی و بهترین نامزد در جامعه، که دارای بهترین مقدار برازش است، به عنوان سیاه چاله انتخاب میشود و بقیه تشکیل ستاره طبیعی میدهند. سیاه چاله توانایی جذب ستارههایی که آن را احاطه کردهاند، دارد. پس از مقدار دهی اولیه سیاه چاله و ستارهها، سیاه چاله شروع به جذب ستاره اطرافش و تمام ستاره ها شروع به حرکت به سمت سیاه چاله میکنند. جذب ستاره توسط سیاه چاله به شرح زیر فرموله شده است:
که در فرمول - 1 - ، xi - t - و xi - t+1 - مکانهای ستاره iام در تکرار t و t+1، به ترتیب میباشند. xBH محل سیاه چاله در فضای جستجو است. rand یک عدد تصادفی در بازه 1]،[0 است. N تعداد ستاره - راه حل نامزد - است. در حرکت ستارهها به سمت سیاه چاله، یک ستاره ممکن است به یک مکان با هزینه پایینتر از سیاه چاله برسد. در این صورت، سیاه چاله به محل آن ستاره حرکت میکند و بالعکس. سپس الگوریتم BH با سیاه چاله در محل جدید ادامه خواهد یافت و پس از آن ستارهها شروع به حرکت به سمت این محل جدید میکنند.
علاوه بر این، احتمال عبور از افق رویداد در حرکت ستارهها به سمت سیاه چاله وجود دارد. هر ستاره که از افق رویداد سیاه چاله عبور کند توسط سیاه چاله مکیده میشود. هر بار که یک نامزد - ستاره - میمیرد - که توسط سیاه چاله مکیده شده است - یک راه حل نامزد دیگر متولد شده و به طور تصادفی در فضای جستجو توزیع و شروع به جستجوی جدید میکند. این کار برای حفظ ثابت تعداد راهحل نامزد است. بعد از نقل مکان همه ستارهها تکرار بعدی صورت میگیرد. شعاع افق رویداد در الگوریتم سیاه چاله با استفاده از معادله - 2 - محاسبه میشود:
که در فرمول - 2 - ، fBH مقدار برازش سیاه چاله است و fi مقدار برازش ستاره iام است. N تعداد ستاره - راه حل نامزد - است. هنگامی که فاصله بین یک راهحل نامزد و سیاه چاله - بهترین نامزد - کمتر از R است، آن نامزد سقوط و یک نامزد جدید ایجاد میشود و به طور تصادفی در فضای جستجو توزیع میشود .[8] بر اساس توضیحات مراحل اصلی الگوریتم سیاه چاله به شرح زیر خلاصه شده است:
گام:1 ایجاد جمعیت اولیهای از ستارگان با موقعیت تصادفی در فضای جستجو گام:2 ارزیابی برازش برای هر ستاره.
گام:3 انتخاب ستارهای با بهترین برازش به عنوان سیاه چاله گام:4 تغییر مکان هر ستاره با استفاده از رابطه - 1 - گام:5 اگر یک ستاره به موقعیتی با برازش بهتر از سیاه چاله دست یابد، موقعیت آنها را عوض کن.
گام:6 اگر یک ستاره به افق رویداد - رابطه - - 2 - وارد شود، آن ستاره حذف و به جای آن یک ستاره جدید به صورت تصادفی در فضای جستجو ایجاد کن گام:7 اگر یکی از معیارهای خاتمه - بهترین برازش و یا حداکثر تعداد تکرار - محقق شد از برنامه خارج شو در غیر این صورت برو به گام 2.
