آموزش الگوریتم خفاش BA — توضیح و تشریح الگوریتم BAT

مقدمه و تاریخچه الگوریتم خفاش BA

الگوریتم‌های بهینه‌سازی مدرن، اغلب از طبیعت الهام گرفته‌شده‌اند و معمولاً مبتنی بر هوش جمعی هستند و راه‌های الهام گرفته‌شده در این الگوریتم‌ها متنوع می‌باشد درنتیجه این مدل از الگوریتم‌ها می‌توانند انواع مختلفی داشته باشند.

بااین‌حال، همه این الگوریتم‌های فراابتکاری تمایل دارند از برخی ویژگی‌های خاص برای فرمول‌بندی کلیدی استفاده کنند. برای مثال، الگوریتم‌های ژنتیک از ویژگی‌های تکامل داروینی سیستم‌های بیولوژیکی الهام گرفته‌شده‌اند و از عملگرهای ژنتیکی مانند متقاطع و جهش و انتخاب مناسب‌ترین عنصر استفاده می‌شود.

از سوی دیگر، بهینه‌سازی ازدحام ذرات PSO براساس رفتار ازدحام پرندگان و ماهی‌ها بوده و این سیستم چندعاملی ممکن است ویژگی‌های نوظهور هوش ازدحام یا گروهی را داشته باشد. این الگوریتم‌ها و شاید تعداد دیگری از این نوع الگوریتم‌ها می‌توانند بسیار مفید باشند، اما همچنان در برخورد با مسائل بهینه‌سازی چندوجهی دارای اشکالاتی هستند.

به‌عنوان یک ویژگی جدید، الگوریتم خفاش (این الگوریتم اولین بار توسط آقای یانگ Yang در سال ۲۰۱۰ معرفی شد) براساس ویژگی‌های پژواک مکان‌یابی خفاش‌ها است همچنین BA از تکنیک تنظیم فرکانس برای افزایش تنوع راه‌حل‌ها در جمعیت استفاده می‌کند. الگوریتم BA برای ایجاد تعادل بین اکتشاف و بهره‌برداری در طول فرآیند جستجو از تکنیک تقلید از تغییرات نرخ انتشار پالس و صدای خفاش‌ها هنگام جستجوی طعمه بهره می‌برد.

الگوریتم خفاش BA استاندارد

الگوریتم استاندارد خفاش براساس پژواک یا ویژگی‌های بایو سونار یا همان مکان‌یابی براساس صوت خفاش‌ها می‌باشد. قبل از اینکه جزئیات الگوریتم را تشریح کنیم، اجازه دهید به‌طور خلاصه این نوع مکان‌یابی را معرفی کنیم.

پاورپوینت الگوریتم بهینه ساز خفاش BA

کلیک کنید

پژواک یا مکان یابی صوتی میکرو خفاش‌ها در الگوریتم خفاش BA

حدود ۱۰۰۰ گونه مختلف خفاش وجود دارد. اندازه‌های آن‌ها می‌تواند بسیار متفاوت باشد، از خفاش زنبوری کوچک حدود ۱.۵ تا ۲ گرم گرفته تا خفاش‌های غول‌پیکر با طول بال‌های حدود ۲ متر و وزن تا حدود ۱ کیلوگرم. اکثر خفاش‌ها تا حدی از پژواک یابی استفاده می‌کنند.

در میان همه گونه‌ها، میکرو خفاش‌ها یا به عبارتی خفاش‌های بسیار کوچک به‌طور گسترده از پژواک استفاده می‌کنند، درحالی‌که مگا خفاش‌ها یا خفاش‌های بسیار بزرگ این کار را نمی‌کنند.

میکرو خفاش‌ها معمولاً از نوعی پژواک برای تشخیص طعمه، اجتناب از موانع و تعیین محل شکاف‌های خود در تاریکی استفاده می‌کنند. آن‌ها می‌توانند یک پالس صدای بسیار بلند منتشر کنند و به پژواکی که از اجسام اطراف بازمی‌گردد گوش دهند. پالس آن‌ها در خواص متفاوت است و بسته به گونه می‌تواند با استراتژی‌های شکار آ‌ن‌ها مرتبط باشد.

ما عمدتاً به برخی از ویژگی‌های مکان یابی صوتی علاقه‌مندیم تا بتوانیم برخی از آن‌ها را با تابع هدف یک مسئله بهینه‌سازی مرتبط کنیم که امکان فرمول‌بندی یک الگوریتم خفاش BA هوشمند را ممکن می‌سازد.

الگوریتم خفاش BA

براساس توضیحات بالا و ویژگی‌های مکان‌یابی خفاش، آقای یانگ الگوریتم خفاش را با سه قانون ایده ال زیر توسعه داد:

• همه خفاش‌ها از پژواک برای حس کردن فاصله استفاده می‌کنند و همچنین تفاوت بین مواد غذایی یا شکار و موانع پس‌زمینه را به روشی جادویی می‌دانند.
• خفاش‌ها به‌طور تصادفی با سرعت v_i در موقعیت x_i با فرکانس f_min، طول‌موج متغیر λ و بلندی صدای A_۰ برای جستجوی طعمه پرواز می‌کنند. آن‌ها می‌توانند به‌طور خودکار طول‌موج (یا فرکانس) پالس‌های ساطع‌شده خود را تنظیم کنند و نرخ ساطع شدن پالس r∈ [۰، ۱] را بسته به نزدیکی هدفشان تنظیم کنند.
• اگرچه بلندی صدا می‌تواند از بسیاری جهات متفاوت باشد، ما فرض می‌کنیم که بلندی صدا از یک A_۰ بزرگ (مثبت) تا یک مقدار ثابت حداقل A_min متغیر است.

برای سادگی، ما از ردیابی پرتو در این الگوریتم خفاش BA استفاده نمی‌کنیم، اگرچه می‌تواند یک ویژگی جالب برای گسترش بیشتر باشد. به‌طورکلی، ردیابی پرتو می‌تواند ازلحاظ محاسباتی گسترده باشد، اما قادر است یک ویژگی بسیار مفید برای هندسه محاسباتی و سایر کاربردها باشد.

علاوه بر این، فرکانس داده‌شده ذاتاً به یک طول موج مرتبط است. به‌عنوان‌مثال، محدوده فرکانسی [۲۰ کیلوهرتز، ۵۰۰ کیلوهرتز] مربوط به طیفی از طول‌موج‌ها از ۰.۷ میلی‌متر تا ۱۷ میلی‌متر در هوا می‌باشد. بنابراین، بسته به سهولت اجرا و سایر عوامل، می‌توانیم تغییر را برحسب فرکانس f یا طول‌موج λ توصیف کنیم تا برای کاربردهای مختلف مناسب باشد.

حرکت خفاش ها در الگوریتم خفاش BA

هر خفاش با یک سرعت v_i^tو یک مکان x_i^t، در تکرار t، در یک فضای جستجو d بعدی یا فضای راه‌حل مرتبط است. در میان تمام خفاش‌ها، بهترین راه‌حل فعلی ^*x وجود دارد. بنابراین، سه قانون فوق را می‌توان به‌صورت معادلاتی برای x_i^t و سرعت v_i^t به‌صورت شکل زیر تولید کرد:

که β ∈ [۰, ۱] یک بردار تصادفی است که از توزیع یکنواخت گرفته‌شده است. همان‌طور که قبلاً ذکر شد، ما می‌توانیم از طول‌موج یا فرکانس برای پیاده‌سازی استفاده کنیم، بسته به‌اندازه دامنه مسئله موردنظر، از f_min = 0 و f_max= O(1) استفاده خواهیم کرد.

در ابتدا، به هر خفاش به طور تصادفی یک فرکانس اختصاص داده می‌شود که به طور یکنواخت از [f_min, f_max] گرفته می‌شود. به همین دلیل، الگوریتم خفاش را می‌توان به‌عنوان یک الگوریتم تنظیم فرکانس برای ارائه ترکیبی متعادل از اکتشاف و بهره‌برداری در نظر گرفت.

میزان بلندی صدا و انتشار پالس اساساً مکانیزمی را برای کنترل خودکار و بزرگنمایی خودکار در منطقه با راه‌حل امیدوارکننده فراهم می‌کند. الگوریتم خفاش یکی از الگوریتم های بهینه سازی است که سورس کد آن در محیط پایتون Python نوشته شده است. این سورس کد آماده دریافت و قابل اجرا در پایتون است. برای اطلاعات بیشتر و دریافت این سورس کد بر روی لینک زیر کلیک نمایید.

الگوریتم بهینه ساز خفاش BA در پایتون Python

کلیک کنید

تغییرات بلندی صدا و ضربان پالس

به‌منظور ارائه یک مکانیسم مؤثر در الگوریتم خفاش BA برای کنترل اکتشاف و بهره‌برداری و تغییر به مرحله بهره‌برداری در صورت لزوم، باید بلندی A_i و نرخ r_i انتشار پالس را در طول تکرارها تغییر دهیم. بلندی صدای معمولاً زمانی که یک خفاش طعمه خود را پیدا کرد کاهش می‌یابد، درحالی‌که سرعت انتشار پالس افزایش می‌یابد.

درنتیجه بلندی صدا را می‌توان به‌عنوان هر مقدار راحتی یا آسایش، بین A_min و A_max انتخاب کرد، با فرض اینکه A_min = 0 به این معنی است که خفاش تازه طعمه را پیداکرده است و به‌طور موقت انتشار هرگونه صدا را متوقف کرده است. با این فرضیات معادله زیر راداریم:

که α و γ اعداد ثابت هستند. در اصل، در اینجا α شبیه به ضریب خنک‌کننده در شبیه‌سازی حرارتی است. برای هر ۱ > α > صفر و γ > 0 معادله زیر را داریم:

در ساده‌ترین حالت، α = γ و α = γ = 0.۹ تا ۰.۹۸ را در شبیه سازی‌های خود استفاده کرده‌ایم.

شبه کد الگوریتم خفاش BA

Set the initial values fmin , fmax, population size n, loudness constant α, rate of pulse emission γ, the initial loudens  A0, the min loudens A min, initial rate of pulse emission  r0 and max number of iteration Max tr.
Set t = 0 
For ( i = 1; i ≤ n ; i++) do
      Generate the initial bat population x_i^t
      Generate the initial bat velocities v_i^t
      Assign the initial frequency fi to each x_i^t
       evaluate the initial population by calculating objective function ) f(x_i^t) each solution in population 
      set the initial values of the pulse rate ri  and loudness Ai
end for
Repeat
     Set t = t+1
     Generate new solution  x_i^t  with eq 3
     Update the bat velocities v_i^t as eq 1 ,2 
     Evaluate the new population by calculating objective function f(x_i^t) for each solution in the population
     Select the best solution x_i^*(t)   
     If rand > ri then
         Select a solution among the best solutions
         Generate a local search solution around the selected best solution
    End if
    Generate a random new solution 
    If rand < A , f(x_i^t<f(x*)) then
          Accept new solution
          Increase the rate of pulse emission ri and loudness A0
     End if
     Evaluate the new population by calculating the objective function f(x_i^t)  for each  solution in population  
     Rank the population and select the best solution x*  from population
Until ( t < Maxtr)
produce the best solution

انواع الگوریتم خفاش BA

الگوریتم خفاش BA استاندارد، مزایای زیادی دارد و یکی از مزایای کلیدی آن این است که می‌تواند با تغییر از اکتشاف به بهره‌برداری، همگرایی بسیار سریع را در مراحل اولیه ایجاد کند. این خصیصه آن را به یک الگوریتم کارآمد برای کاربردهایی مانند طبقه‌بندی و موارد دیگر درزمانی که به یک راه‌حل سریع نیاز است تبدیل می‌کند.

بااین‌حال، اگر به الگوریتم اجازه دهیم خیلی سریع با تغییر سریع A و r به مرحله بهره‌برداری تغییر کند، ممکن است پس از چند مرحله اولیه منجر به رکود شود. به‌منظور بهبود عملکرد، روش‌ها و استراتژی‌های زیادی برای افزایش تنوع راه‌حل و درنتیجه ارتقای عملکرد، تلاش شده است که چند نوع خوبی از از الگوریتم خفاش تولید شود.
با یک بررسی سریع به‌صورت تئوری، انواع الگوریتم خفاش زیر را می‌توان نام برد:

الگوریتم خفاش منطق فازی (FLBA)

آقای خان و همکارانش در سال (۲۰۱۱) با واردکردن منطق فازی به الگوریتم خفاش، یک نوعی را ارائه کردند که آن را الگوریتم خفاش فازی نامیدند.

الگوریتم خفاش چند هدفه (MOBA)

یانگ در سال (۲۰۱۱) الگوریتم خفاش BA را برای مقابله با بهینه‌سازی چندهدفه گسترش داد، که اثربخشی آن را برای حل چند معیار طراحی در مهندسی نشان داده است.

الگوریتم خفاش k-means به اختصار (KMBA)

آقایان کوماسامی و واهی در سال (۲۰۱۲) ترکیبی از K-means و الگوریتم خفاش را برای خوشه‌بندی کارآمد ارائه کردند.

الگوریتم خفاش آشوب‌ زده (CBA)

آقای لین و همکارانش در سال (۲۰۱۲) یک الگوریتم خفاش آشوب‌زده را با استفاده از پروازهای L´evy و نقشه‌های آشوب‌زده برای انجام تخمین پارامتر در سیستم‌های بیولوژیکی پویا ارائه کرد.

الگوریتم خفاش باینری (BBA)

ناکامورا و همکارانش در سال (۲۰۱۲) یک نسخه گسسته از الگوریتم خفاش را برای حل مشکلات طبقه‌بندی و انتخاب ویژگی توسعه داد.

الگوریتم عملکرد Bat و L´evy پروازها (DLBA)

آقای شی و همکارانش در سال (۲۰۱۳) گونه‌ای از الگوریتم خفاش را با استفاده از عملگر دیفرانسیل و پروازهای L´evy برای حل مسائل بهینه‌سازی ارائه کرد.

الگوریتم بهبود یافته خفاش (IBA)

جمیل و همکارانش نیز در سال (۲۰۱۳) الگوریتم خفاش را با ترکیب خوبی از پروازهای L´evy و تغییرات ظریف بلندی صدا و نرخ انتشار پالس گسترش دادند. همچنین IBA را در مقابل بیش از ۷۰ عملکرد مختلف آزمایشی آزمایش کردند و ثابت کردند که الگوریتم بسیار کارآمدی است.

الگوریتم بهینه ساز خفاش BA در متلب Matlab

کلیک کنید

کارربرد الگوریتم خفاش BA

الگوریتم استاندارد خفاش و انواع مختلف آن به این معنی است که برنامه‌ها نیز بسیار متنوع هستند. درواقع، از زمانی که الگوریتم اصلی خفاش توسعه‌یافته است.یعنی از سال ۲۰۱۰، الگوریتم‌های خفاش تقریباً در هر زمینه‌ای از بهینه‌سازی، طبقه‌بندی، پردازش تصویر، انتخاب ویژگی، زمان‌بندی، داده‌کاوی و موارد دیگر استفاده‌شده‌اند. در ادامه مقاله، به‌طور تیتروار به برخی از کاربردها اشاره خواهیم کرد:

• بهینه سازی مداوم
• بهینه سازی ترکیبی و زمان بندی
• مسائل معکوس و تخمین پارامتر
• طبقه بندی، خوشه بندی و داده کاوی
• پردازش تصویر
• منطق فازی و سایر کاربردها

چرا الگوریتم خفاش BA کارآمد است؟

چرا الگوریتم خفاش این‌قدر کارآمد است؟ دلایل زیادی برای موفقیت الگوریتم‌های مبتنی بر خفاش وجود دارد. با تجزیه‌ و تحلیل ویژگی‌های کلیدی و به‌روزرسانی معادلات، می‌توانیم سه نکته/ویژگی کلیدی زیر را خلاصه کنیم:

تنظیم فرکانس

BA از پژواک و تنظیم فرکانس برای حل مشکلات استفاده می‌کند. اگرچه پژواک به‌طور مستقیم برای تقلید از عملکرد واقعی در واقعیت استفاده نمی‌شود و از تغییرات فرکانس استفاده می‌شود.

این قابلیت می‌تواند عملکردهایی را ارائه دهد که ممکن است مشابه ویژگی کلیدی مورداستفاده در بهینه‌سازی ازدحام ذرات و جستجوی هماهنگی باشد. بنابراین، BA دارای مزایای دیگر الگوریتم‌های مبتنی بر هوش ازدحام است.

بزرگنمایی خودکار

BA مزیت مشخصی نسبت به سایر الگوریتم‌های فرا ابتکاری دارد. یعنی BA قابلیت بزرگنمایی خودکار در منطقه‌ای را دارد که راه‌حل امیدوارکننده‌ای در آن یافت شده است.

این بزرگنمایی با تغییر خودکار از حرکات اکتشافی به بهره‌برداری فشرده محلی همراه است. درنتیجه، BA در مقایسه با سایر الگوریتم‌ها، حداقل در مراحل اولیه تکرارها، نرخ همگرایی سریعی دارد.

کنترل پارامتر

بسیاری از الگوریتم‌های فرا ابتکاری از پارامترهای ثابت با استفاده از برخی پارامترهای از پیش تنظیم‌شده وابسته به الگوریتم استفاده می‌کنند. در مقابل، BA از کنترل پارامتر استفاده می‌کند، که می‌تواند مقادیر پارامترهای (A و r) را با ادامه تکرارها تغییر دهد. این کار روشی را برای تغییر خودکار از اکتشاف به بهره‌برداری درزمانی که راه‌حل بهینه نزدیک می‌شود، فراهم می‌کند. این امر مزیت دیگری برای الگوریتم خفاش BA نسبت به سایر الگوریتم‌های فرا ابتکاری می‌دهد.

سخن آخر در مورد الگوریتم خفاش BA

در این مقاله در مورد الگوریتم خفاش BA که یکی از الگوریتم‌های فرا ابتکاری مبتنی بر هوش جمعی است که از طبیعت و رفتار خفاش‌ها در طبیعت الهام گرفته‌شده است صحبت کردیم. این الگوریتم از رفتار جمعی خفاش‌ها برای یافتن غذا و تشخیص شکارچی یا موانع از طریق تولید صداهایی که در این مقاله از آن بانام پژواک نام‌برده شده استفاده می‌کند بدین‌صورت که خفاش‌ها از طریق تولید صدا و بازتاب آن متوجه می‌شوند که مانع یا غذا در چه فاصله‌ای قرار دارد و به‌این‌ترتیب اطراف خود را به خوبی می‌توانند ببینند.

با استفاده از این روش در سیستم‌ها و مسائل بهینه‌سازی و شبکه‌های کامپیوتری و غیره می‌توان به تکنیک‌های جدیدی در کاربرد این قضیه در مسائل هوا و فضا و مسائل بهینه‌سازی مسیریابی در روترها و غیره دست‌یافت. در این مقاله علاوه بر توضیح الگوریتم خفاش BA توضیحاتی در مورد عملکرد الگوریتم و کاربردهای آن نیز آورده شده است. از اینکه تا انتهای مقاله با ما همراه بودید سپاسگزارم.