بخشی از مقاله
چکیده
امروزه اغلب مسائل بهینهسازی از نوع مسائل NP-hard هستند. از جمله راه حلهای موجود در برخورد با این گونه مسائل، استفاده از الگوریتمهای تقریبی یا ابتکاری است. الگوریتم سیاه چاله - BH - یک روش ابتکاری جدید است که از پدیده سیاه چاله طبیعی الهام گرفته شده است، این الگوریتم سرعتی بالا و ساختاری ساده برای پیادهسازی دارد ولی در جستجوی محلی ضعیف عمل میکند. بنابراین در این مقاله ترکیبی از الگوریتم BH و الگوریتم تبرید تدریجی - - SA با نام BH-SA معرفی میشود. ما از الگوریتم SA برای بهبود جستجوی محلی و فرار از بهینه محلی استفاده کردهایم. روش پیشنهادی بر روی تعدادی تابع محک رایج، مورد آزمایش قرار گرفته است. نتایج آزمایشها نشان میدهد که روش پیشنهادی از دقت بالاتری در رسیدن به جواب بهینه سراسری برخوردار است. به عنوان مثال پاسخ حاصل از میانگینگیری 20 بار اجرای الگوریتم پیشنهادی روی تابع Griewank، نشان میدهد که خطای نسبی روش پیشنهادی 69,44 برابر کمتر از روش BH پایه است.
.1 مقدمه
بهینهسازی شاخهای از علوم است که در آن سعی میشود نقطه بهینه توابع را با توجه به تعدادی محدودیت به دست آورد. امروزه با توجه به این که بسیاری از مسائل بهینهسازی از نوع مسائل NP-hard هستند، میتوان از الگوریتمهای تقریبی یا ابتکاری برای حل این گونه مسائل، استفاده کرد. این گونه الگوریتمها تضمینی نمیدهند که جواب به دست آمده بهینه باشد و تنها با صرف زمان بسیار میتوان جواب به نسبت دقیقی را به دست آورد و در حقیقت بسته به زمان صرف شده، دقت جواب تغییر میکند. با توجه به تضاد بین دو عامل سرعت و دقت، سعی شده این دو عامل در کنار هم بهبود پیدا کنند.
در طول چند دهه اخیر گونه جدیدی از الگوریتمهای تقریبی به نام فرا ابتکاری ایجاد شده اند که سعی دارند روشهای ابتکاری پایه را به منظور جستجوی کارا و موثر فضای جستجو در سطوح بالاتر ترکیب نمایند. انبوه کارهای صورت گرفته روز دنیا حاکی از رشد روزافزون کاربرد این گونه الگوریتمها در مسائل بهینهسازی است. به همین دلیل الگوریتمهای فرا ابتکاری مختلفی در سالهای اخیر ارائه شدهاند. بسیاری از این ایدهها از ملاحظه و بررسی در طبیعت پیرامون الهام گرفته شدهاند.
به عنوان مثال الگوریتم سیاه چاله - BH - از پدیده سیاه چاله طبیعی الهام گرفته شده است که تحت دو عملیات، جذب ستاره و بلعیدن ستاره عمل میکند.[1] همچنین برای غلبه بر مشکلات الگوریتمهای ابتکاری از ترکیب این الگوریتمها استفاده شده است. حسینی و همکارش یک روش جدید ترکیبی با استفاده از الگوریتم ژنتیک - GA - ، بهینهسازی کلونی مورچهها - ACO - و الگوریتم SA، به منظور ارتقاء کنتراست تصاویر ارائه کردند که از SA به عنوان یک روش جستجوی محلی برای تغییر توابع انتقال تولید شده توسط ACO بهره گرفتند.[2] کراسلند و همکارانش از ترکیب الگوریتم GA و SA به منظور بررسی مسئله تعیین محل و اندازه ذخیرهسازی انرژی در شبکههای فشار ضعیف استفاده کردند که در این مساله، SA به منظور جستجوی محلی در داخل GA تعبیه شده است.
[3] جنگ و همکارانش الگوریتم بهینهسازی ازدحام ذرات تبرید تدریجی آشوبناک - CSAPSO - را برای پیشبینی توان عملیاتی پورت، پیشنهاد کردند که از الگوریتم SA به دلیل در نظر گرفتن ذرات بدتر با احتمال مشخص برای پرش از بهینه محلی و بدست آوردن بهینه سراسری استفاده کردند.[4] هووا و همکارانش ترکیبی از جستجوی هارمونی - HS - و SA برای حل مسئله زمانبندی کار چند پردازندگی ارائه کردند که به دلیل ضعف HS در جستجوی محلی، از الگوریتم SA استفاده کردند که مزیت اصلی آن این است که نه تنها راهحل بهتر از وضعیت فعلی را می پذیرد،
بلکه میتواند از بهینه محلی پرش کند. ترکیب SA و HS باعث بهبود جستجوی سراسری و سرعت همگرایی شده است.[5] مقاله ما یک بهبود از الگوریتم سیاه چاله - - BH را ارائه میکند. در الگوریتم پیشنهادی، الگوریتم BH به دلیل ضعفی که در جستجوی محلی دارد باعث میشود تا الگوریتم در بهینه محلی گیر کند. برای حل مشکل الگوریتم BH، آن را با الگوریتم SA ترکیب میکنیم تا بتوانیم با جستجو در همسایگی هر راه حل از بهینههای محلی پرش کنیم.
.2 مفاهیم پایه
.1-2 الگوریتم سیاه چاله - - BH
الگوریتم BH شبیه به پدیده سیاه چاله طبیعی است. در الگوریتم BH جمعیت به طور تصادفی توسط راه حلهای نامزد - ستارهها - در فضای جستجو تولید میشود. پس از مقداردهی اولیه، مقادیر برازندگی از جمعیت ارزیابی و بهترین نامزد در جمعیت، که دارای بهترین مقدار برازندگی است به عنوان سیاه چاله، انتخاب میشود و بقیه ستارهها را تشکیل میدهند. سیاه چاله دارای قابلیت جذب ستارههایی است که آن را احاطه کردند. پس از مقداردهی اولیه سیاه چاله و ستاره ها، سیاه چاله شروع به جذب ستارههای اطراف را میکند. جذب ستارهها توسط سیاه چاله به صورت معادله زیر فرموله شده است: در معادله - 1 - به ترتیب xit و xit 1 موقعیت ستاره i ام در تکرار t و 1 t است. xBH موقعیت سیاه چاله در فضای جستجو و r یک عدد تصادفی در بازه 0,1 است.
در طول حرکت ستارهها به سمت سیاه چاله، احتمال عبور از افق رویداد وجود دارد. هر ستاره که از افق رویداد سیاه چاله عبور کند، توسط سیاه چاله بلعیده میشود و یک ستاره جدید متولد میشود. این کار برای ثابت نگه داشتن تعداد راه حلهای نامزد میباشد. شعاع افق رویداد در الگوریتم BH با استفاده از معادله زیر محاسبه میشود: در معادله - 2 - ، fBH مقدار برازندگی سیاه چاله، fi مقدار برازندگی ستاره i ام و N تعداد ستارهها است. هنگامی که فاصله بین یک ستاره - راهحل نامزد - و سیاه چاله - بهترین نامزد - کمتر از R شود، ستاره از بین میرود و یک ستاره جدید تولید میشود و به طور تصادفی در فضای جستجو توزیع میشود.[1] مراحل اجرای الگوریتم BH در شکل 1 نشان داده شده است.
شکل :1 الگوریتم [6] BH
.2-2 الگوریتم تبرید تدریجی - - SA
الگوریتم SA توسط متروپلیس و همکارانش در سال 1953 معرفی شد[7] و به وسیله کرک پاتریک و همکارانش در سال 1983 عمومیت پیدا کرد.[8] مفهوم اصلی تبرید تدریجی از فرآیند تبرید فلزات در صنعت متالورژی گرفته شده است. الگوریتم SA روشی ابتکاری بر مبنای جستجوی محلی است. این الگوریتم قادر است از گیر افتادن در بهینه محلی با قبول جوابهای بدتر با احتمالی کم، جلوگیری کند. کیفیت جوابهای حاصل از الگوریتم SA موجب شده تا در حل مسائل بهینهسازی ترکیبی پیچیده در حوزههای مختلف مسائل دنیای واقعی مورد استفاده قرار گیرد. الگوریتم SA از یک جواب تصادفی به عنوان جواب اولیه حرکت خود را آغاز میکند و دمای سیستم برابر دمای اولیه قرار میگیرد. در هر تکرار یک جواب همسایه جواب فعلی به دست میآید. مقدار تابع هدف جواب جدید با جواب فعلی مقایسه میشود،
