بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
معرفی الگوریتم خفاش و انواع بهبودیافته و کاربردهای آن
چکیده
هوش جمعی یکی از قوی ترین تکنیک های بهینه سازی می باشد که برمبنای رفتارهای گروهی است . الگوریتم خفاش یکی از الگوریتم های فرا ابتکاری می باشد که براساس اصل انعکاس صدای خفاش ودریافت صدا توسط این پرنده عمل می کند که درسال 0202 توسط یانگٌ ارائه شد.در این مقاله به انواع الگوریتم خفاش و کاربرد های آن پرداخته و نیز با بررسی های انجام شده مشاهده شده است که الگوریتم خفاش ساده دچار ضعف ها و مشکلاتی میباشد که سپس به چندین الگوریتم اصلاح شده خفاش می پردازیم. با بررسی های انجام شده مشاهده میشود که الگوریتم خفاش ساده در فضاهای گسسته دچار مشکل همگرایی هست از این رو الگوریتم خفاش اصلاح شده برای فضاهای گسسته را معرفی کرده ایم . و نیز یکی از مشکلات الکوریتم خفاش در ابعاد بالا هست که از این رو به معرفی الگوریتم اصلاح شده خفاش برای مقیاس های بزرگ و همچنین الگوریتم خفاش اصلاح شده BADG برای ابعاد بالاتر می پردازیم. همچنین الگوریتم خفاش چند هدفه را برای حل مسائلی که چند هدف را بصورت موازی و توام دنبال میکنند درحل مسائل معرفی کرده ایم.
مقدمه:
امروزه گرایش به استفاده از الگوریتم های الهام گرفته از طبیعت ومبتنی بر هوش جمعی حیوانات بسیار زیاد است .به خصوص در مقوله ی تکنیک های بهینه سازی این الگوریتم ها مورد استقبال زیادی قرار گرفته اند.با نگاه دقیق به طبیعت وتنوع بسیار زیاد حیواناتی که به صورت جمعی درزندگی خود از روش ها ومتدهای خاصی پیوری می کنند،بدیهی است که الگوریتم های زیادی را می توان با الهام ازآنها مطرح کرد.الگوریتم خفاش مبتنی بر ویژگی پژواک یابی ریزخفاش ها است.[1] درحالت کلی دونوع خفاش وجود دارد که نوع اول بزرگ خفاش ها هستند ونوع دوم ریزخفاش ها نام دارند .ریزخفاش ها ازاین ویژگی برای پرواز درشب وشکار استفاده می کنند .الگوریتم خفاش با استفاده از تکنیک تنظیم فرکانس،تنوع راه حل های موجود درجمعیت را افزایش می دهند
.1 الگوریتم خفاش:
الگوریتم بهینه سازی خفاش الهامی از خصوصیات ردیابی خفاش های کوچک درجستجوی شکار می باشد .به طوری که خفاش های کوچک می توانند درتاریکی مطلق با انتشار صدا ودریافت آن به شکار طعمه های خود بپردازند .برای توسعه این الگوریتم از سه قانون آرمانی زیر استفاده می شود:
· همه خفاش ها از انعکاس صدا برای تشخیص فاصله استفاده می کنند وتفاوت بین مواد غذایی و موانع پیشرو را می دانند.در واقع بدین وسیله مسیر و هندسه اجسام را تشخیص داده و پردازش تصویر را انجام می دهند.
· پرواز خفاش ها به طور تصادفی با سرعت vi درمکان xiبا فرکانس ثابت fminو طول موج مختلف λ وبلندی صوت A0 به منظور شکار طعمه صورت می گیرد.همچنین آنها می توانند به طور خودکار امواج پخش شده ونرخ پالس های ارسالی خود را (rϵ[0,1]) با توجه به نزدیکی شکارشان تنظیم کنند.
· باتوجه به اینکه ممکن است بلندی صدا دربسیاری از جهات مختلف متفاوت باشد لذا فرض می کنیم که بلندی صدا از R0 (بیشترین مقدار) تا )Rminکمترین مقدار) متغیر می باشد. [1]
طبق قوانین بیان شده،مکان xit و سرعت vit برای هر خفاش مجازی i ام درتکرار t وهمچنین فرکانس fiبه صورت زیر محاسبه می گردد:
که در آن β ∈ [0,1] یک بردار تصادفی با توزیع یکنواخت می باشد وx∗ بهترین مکان فعلی است که در هر تکرار پس از مقایسه با موقعیت خفاش های مجازی انتخاب می شود. معمولا فرکانس fرا با fmin = 0 وfmax = 100 درنظر می گیرند. درهر تکرار ،در جستجوی محلی یکی از جواب ها به عنوان بهترین جواب ها انتخاب شده وموقعیت جدید هرخفاش به طور محلی با گام تصادفی به صورت زیر به روز می شود:
که در آن ϵ ∈ [−1,1] یک عدد تصادفی بوده وAt =< Ati >ومیانگین بلندی صدای خفاش ها درتکرار t می باشد .همچنین بلندی صدای Ai ونرخ پالی ارسالی rدرهر تکرار به صورت زیر به روز می شود:
که درآن α وγ مقدار ثابت می باشند. درساده ترین مورد می توان α = γ = 0.9to0.98 درنظر گرفت. همچنین زمانی که 0 < α < 1 وr > 0، وقتی t → ∞ داریم: rit+1 → ri0 و . Ait+1 → 0
-1-1 گام های اساسی و کد اصلی الگوریتم خفاش :
بنابرین گام های اساسی در الگوریتم خفاش در جدول (0) و نیز فلوچارت آن در شکل((0 نشان داده شده است:[1]
حال در شکل زیر فلوچارت الگوریتم خفاش را نشان داده و گام ها و مراحل الگوریتم خفاش را به ترتیب در آن مشخص کرده ایم.
به منظور مقایسه ی عملکرد الگوریتم جدید ، باید آنرا دربرابر الگوریتم های اکتشافی مانند؛الگوریتم ژنتیک((GA و بهینه سازی ازدحام ذرات (PSO) مورد مقایسه انجام داد (جدول(. ((0 با توجه به مقایسات انجام داده شده نتیجه میگیریم که الگوریتم خفاش از مزیت سادگی وانعطاف پذیری برخوردار است .این الگوریتم به دلیل ویژگی های میزانسازی فرکانس،بزرگنمایی خودکار وکنترل پارامتر،این الگوریتم توانایی حل مسائل گوناگونی را دارا می باشد.
-1-2انواع الگوریتم خفاش :
یکی از مزایای کلیدی الگوریتم خفاش، توانایی همگرایی سریع درمرحله ابتدایی بوسیله سوئیچ ازاکتشاف به استخراج است. این ویژگی باعث می شود این الگوریتم،یک الگوریتم تاثیرگذار برای کاربردهایی مثل دسته بندی ودرکل زمانی که یک راه حل سریع نیازمند است،باشد.هرچند که با اجازه دادن به الگوریتم به سوئیچ سریع به مرحله استخراج ،با تغییر سریع A وr، بعد از چند مرحله ابتدایی الگوریتم دچار رکود می شود.به منظور بهبود کارایی الگوریتم،متدها واستراتژی های زیادی مطرح شده اند تا تنوع راه حل را افزایش دهند که منجربه تولید نسخه های متخلفی از الگوریتم خفاش شده است .
ازانواع مختلف این الگوریتم می توان به موارد زیر اشاره کرد:
-0 الگوریتم خفاش برمبنای منطق فازی: خانٍ و همکارانش با ترکیب قوانین فازی با مجموعه قوانین الگوریتم خفاش یک نوع الگوریتم جدید را ارائه دادند.این الگوریتم به الگوریتم خفاش بر مبنای منطق فازی شناخته می شود.[2]
-0 الگوریتم خفاش چند منظوره: یانگ با بررسی الگوریتم خفاش، الگوریتم جدیدی بر پایه قوانین الگوریتم خفاش برای حل مسائل بهینه سازی چند هدفه که بطور همزمان چند معیار و هدف را بررسی می کند، ارائه داد.[3]
-3 الگوریتم خفاش :K-means کوماراسامیَ و واهیُ با تلفیق روش k به همراه مجموعه قوانین خفاش، الگوریتم کارآمدی را برای طبقه بندی ارائه دادند.[4]
-4 الگوریتم خفاش برمبنای نظریه آشوب: لینِ و همکارانش با بهره گیری از پروازهای لوی و نقشه های نامنظم برای انجام برآورد پارامتر در تکنیک های طبیعی و پویا، الگوریتم خفاش برمبنای نظریه آشوب را ارائه دادند.[5]
-5 الگوریتم خفاش باینری: ناکاموراّ و همکاران برای حل مشکلات انتخاب ویژگی و طبقه بندی ها یک مدل گسسته از مجموعه قوانین خفاش یافتند.[6]
-6 الگوریتم خفاش برمبنای عامل تفاضلی پرواز لوی: شیْ و همکارانش برای رفع دشواری بهینه سازی با بکارگیری عامل تفاضلی و پرواز لوی نوع جدیدی از مجموعه قوانین خفاش را ارائه دادند.[7]
-7 الگوریتم خفاش بهبود یافته: جمیل و همکارانش باترکیب عالی از پروازهای لوی و نسخه های ظریف پالس انتشار و بلندی صدا، الگوریتم خفاش بهبود یافته را عرضه کردند. آن ها این الگوریتم را با 72 ویژگی گوناگون تست کردند.مشاهده شد که این الگوریتم بسیار کارآمد می باشد.[8]
درمورد الگوریتم خفاش پیشرفت های زیادی حاصل شده وهمانطور که اشاره شد انواع مختلفی ازاین الگوریتم ارائه شده است .دراین قسمت اشاره ای ضمنی به گونه های دیگری از این الگوریتم خواهیم کرد.برای مثال یانگ و وانگَ ازجهش برای افزایش تنوع راه حل های مناسب استفاده کردند و از این روش درزمینه ی تطابق تصویر استفاده کردند.[9] علاوه بر این وانگ و گواُ الگوریتم خفاش را با الگوریتم هارمونی ترکیب کرده وگونه ای جدید با عنوان الگوریتم خفاش هیبریدی را بوجود آوردند که در بهینه سازی عددی معیارهای تابعی کاربرد دارند.[10]
-1-3 کاربردهای الگوریتم خفاش:
الگوریتم استاندارد خفاش وتعدد ورژن های مختلف آن نشانگر محدوده ی بالای کاربردهای آن است .درواقع ازسال0202 که یانگ این الگوریتم را مطرح کرد،الگوریتم خفاش تقریبا درتمامی زمینه های بهینه سازی،دسته بندی،پردازش تصویر کاربرد داشته است .درادامه ی این مقاله مختصرا به برخی از کاربردهای مهم این الگوریتم اشاره شده است .
- دسته بندی ،خوشه بندی وداده کاوی
- پرداش تصویر
- منطق فازی
- بهینه سازی متوالی
- بهینه سازی ترکیبی وزمانبندی
- مسائل معکوس وتخمین پارامتر
ژوًٌ و همکارانش الگوریتم خفاش ترکیبی جدیدی برای مسیریابی وسایل نقلیه ارائه شده است.[11] مروری مجدد و ارائه روشی جدید برای بهینه سازی مسائل مهندسی مکانیک گرایش طراحی کار بردی انجام شده است.[12] کاوهٌٌ و همکارش الگوریتم خفاش بهبود یافته برای مسائل بهینه سازی خرپا و سازه های استاتیکی در مقیاس های بزرگ را ارائه دادند.[13] کومارٌٍ و همکارانش به بررسی کاربرد الگوریتم خفاش در بهینه سازی توزیع توان(قدرت) برق پرداختند.[14]
