مجموعه آموزشی پی استور - https://programstore.ir

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

در این مقاله، الگوریتم خفاش BA که یک الگوریتم بهینه‌سازی فرا ابتکاری [1] الهام گرفته از طبیعت است و برای حل وظایف بهینه‌سازی مهندسی معرفی‌شده است، را مورد بحث قرار می‌دهیم. اگر علاقه‌مند به الگوریتم‌های فرا ابتکاری هستید در این مقاله با ما همراه باشید.

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

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

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

ود.

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

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

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

 

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

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

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

حدود 1000 گونه مختلف خفاش وجود دارد. اندازه‌های آن‌ها می‌تواند بسیار متفاوت باشد، از خفاش زنبوری کوچک حدود 1.5 تا 2 گرم گرفته تا خفاش‌های غول‌پیکر با طول بال‌های حدود 2 متر و وزن تا حدود 1 کیلوگرم. اکثر خفاش‌ها تا حدی از پژواک یابی استفاده می‌کنند.

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

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

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

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

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

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

علاوه بر این، فرکانس داده‌شده ذاتاً به یک طول موج مرتبط است. به‌عنوان‌مثال، محدوده فرکانسی [20 کیلوهرتز، 500 کیلوهرتز] مربوط به طیفی از طول‌موج‌ها از 0.7 میلی‌متر تا 17 میلی‌متر در هوا می‌باشد. بنابراین، بسته به سهولت اجرا و سایر عوامل، می‌توانیم تغییر را برحسب فرکانس f یا طول‌موج λ توصیف کنیم تا برای کاربردهای مختلف مناسب باشد.

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

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

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

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

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

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

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

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

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

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

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

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

فرمول

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

فرمول

در ساده ترین حالت، α = γ و α = γ = 0.9 تا 0.98 را در شبیه سازی های خود استفاده کرده ایم.

شبه کد الگوریتم خفاش 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 در متلب Matlab [5]

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

در این بخش سورس کد الگوریتم بهینه ساز خفاش BA در متلب Matlab قرار گرفته شده است. این سورس کد به زبان متلب Matlab برای الگوریتم بهینه سازی خفاش Bat Algorithm به اختصار BA نوشته شده است

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

تنظیم فرکانس

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

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

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

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

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

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

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

پاورپوینت الگوریتم بهینه ساز خفاش BA در 17 صفحه در قالب ppt. یا pptx. با قابلیت ویرایش و توضیحات اضافی برای برخی صفحات در قالب Note آماده دانلود می باشد.

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

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

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

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

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

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