نویسندگان
1 کارشناسی ارشد، دانشکده مهندسی کامپیوتر - دانشگاه صنعتی خواجه نصیرالدین طوسی - تهران - ایران
2 استادیار، دانشکده مهندسی کامپیوتر - دانشگاه صنعتی خواجه نصیرالدین طوسی - تهران - ایران
3 استادیار، دانشکده مهندسی برق - دانشگاه صنعتی خواجه نصیرالدین طوسی - تهران - ایران
چکیده
کلیدواژهها
موضوعات
عنوان مقاله [English]
نویسندگان [English]
Bat Algorithm is a type of swarm intelligence algorithm which is inspired by the behavior of little bats which are looking for direction in hunting opportunities. Swarm intelligence algorithms are inspired by the nature which are very efficient on crucial optimization problems. These algorithms are simple, flexible and can be implemented easily as well. Analyzing swarm intelligence algorithms makes their utilization reliable and guarantees finding answers by them. Earlier, stability analysis has been accomplished for some swarm intelligence algorithms including Particle Swarm Optimization and Gravitational Search but sufficient mathematical analysis for the bat algorithm has not been done. For this purpose, in the present paper, we considered Bat Algorithm stability analysis using Lyapunov method. In this study, at first, stability analysis of standard bat algorithm has been analyzed. Because of unsuccessful attempts to analyze the stability of standard algorithm, new updating relations has been introduced to increase the degree of freedom. The stability analysis has been presented for these relations. Experimental results illustrate the stability of the new updating relations.
کلیدواژهها [English]
الگوریتم خفاش، نوعی الگوریتم هوشجمعی است که یانگ در سال 2010 ارائه کرد [1]. این الگوریتم از رفتار خفاشهای کوچک برای جستجوی شکار، الهام گرفته است. ازجمله مزایای الگوریتم خفاش به توانایی تنظیم فرکانس و تمرکز خودکار (تغییرات خودکار میزان انتشار بلندی صدا و پالس، قابلیت تمرکز خودکار را برای این الگوریتم فراهم میکند؛ بهطوریکه استخراج راهحلها در قسمتی از فضای جستجو با نتایج امیدبخش بهتر میشود) اشاره میشود. در سالهای اخیر، پژوهشگران به الگوریتم خفاش توجه بسیاری کردهاند. کاربردهای بسیار زیادی برای این الگوریتم وجود دارد، ازجمله کاربردهای آن به بهینهسازی پیوسته، زمانبندی، تخمین پارامتر، دستهبندی و خوشهبندی، پردازش تصویر و منطق فازی اشاره میشود ]2-10[. همچنین، انواع مختلفی از الگوریتم خفاش ارائه شده است ]11-13[.
بررسی پایداری و همگرایی الگوریتمهای هوشجمعی حائز اهمیت است؛ زیرا تعداد الگوریتمهای هوشجمعی ارائهشده بسیار زیاد است و هیچ تضمینی برای پایداری این الگوریتمها و رسیدن به پاسخ مناسب با آنها وجود ندارد. پیش از این، تحلیل پایداری برای برخی از الگوریتمهای هوشجمعی ازجمله بهینهسازی ازدحام ذرات، جستجوی گرانشی انجام شده است [14, 15]. نخستین مقاله بهمنظور بررسی الگوریتم خفاش مربوط به سال 2017 است که در آن یافتن بهترین تنظیم پارامتر برای دستیابی به نتایج بررسی شده است [6]. همچنین چن و همکاران [23] با استفاده از مدل زنجیرة مارکوف و مدل ماتریس پویا تجزیه و تحلیل نظری برای خفاش استاندارد انجام دادند. آنها مدل سادهای از الگوریتم خفاش استاندارد را بدون تغییرات بلندی صدا و میزان پالس در نظر گرفتند. همچنین در سالهای اخیر در مقالاتی، تنظیم پارامتر الگوریتم خفاش و بهبود این الگوریتم بررسی شده است ]24-25[.
در این مقاله، پایداری الگوریتم خفاش تحلیل میشود. ادامة مقاله به این صورت است: در بخش 2، الگوریتم خفاش استاندارد توضیح داده شده و در بخش 3، روابط بهروزرسانی جدید ارائه شده است. در ادامه، این روابط بهروزرسانی با استفاده از فضای حالت، نمایش داده میشود. سپس با استفاده از روش لیاپانوف، پایداری روابط بهروزرسانی پیشنهادی تحلیل میشود. گفتنی است بهدلیل استفاده از روش لیاپانوف، شرایط به دست آمده محافظهکارانهاند و رعایتنکردن این شرایط، لزوماً به معنی ناپایداری نخواهد بود. بخش 4، فضای پایدار را توصیف کرده است. در بخش 5 نتایج تجربی آمده و در بخش آخر، نتیجهگیری ارائه شده است.
2- الگوریتم خفاش استاندارد
الگوریتم خفاش یکی از الگوریتمهای فراابتکاری الهامگرفته از طبیعت است که در سال 2010 یانگ آن را معرفی کرد [1]. این الگوریتم براساس اصول زندگی خفاشها طراحی شده است و نخستین الگوریتم از انواع الگوریتمهایی است که از تنظیم فرکانس استفاده میکنند. خفاشهای کوچک در تاریکی مطلق با انتشار صدا و دریافت آن، طعمه را شکار و از برخورد با موانع، اجتناب میکنند. الگوریتم خفاش از ویژگیهای ردیابی این خفاشهای کوچک در جستجوی شکار الهام گرفته شده است [1].
برای توسعة این الگوریتم از سه فرض اصلی زیر استفاده شده است [16-18]:
1. همة خفاشها از انعکاس صدا برای تشخیص فاصله استفاده میکنند و تفاوت بین موانع پیش رو و مواد غذایی را میدانند.
2. پرواز خفاشها بهصورت تصادفی با سرعت در مکان است. همچنین، آنها بهطور خودکار فرکانس یا طول موج پالسهای انتشار خود و پالس خروجی را با توجه به میزان نزدیکی هدفشان تنظیم میکنند.
3. هرچند بلندی صدا به روشهای مختلفی تغییر میکند، فرض گرفته میشود بلندی صدا از یک بزرگ به یک مقدار حداقل تغییر میکند.
در این الگوریتم هر خفاش با معیارهای سرعت و مکان در تکرار t ام سنجیده میشود. در میان تمام راهحلها در کل جمعیت، بهترین راهحل وجود دارد؛ بنابراین، با استفاده از روابط 1 تا 3، فرکانس، سرعت و مکان در هر تکرار بهروزرسانی میشوند:
|
(1) |
|
|
(2) |
|
|
(3) |
که در آن یک بردار تصادفی با توزیع یکنواخت است. همچنین، فرکانس هر خفاش بین و خواهد بود که مقدار این دو متغیر به ابعاد مسئله بستگی دارد و معمولاً و در نظر گرفته میشود [1].
در هر تکرار با استفاده از جستجوی محلی، یکی از بهترین جوابها انتخاب شده است و موقعیت جدید هر یک از خفاشها بهطور محلی با گام تصادفی با استفاده از رابطة زیر به روز میشوند:
|
(4) |
که در آن یک عدد تصادفی بوده و میانگین بلندی صدای خفاشها در تکرار t است.
همچنین، بلندی صدای و میزان پالس ارسالی در هر تکرار بهصورت زیر به روز میشود:
|
(5) |
|
|
(6) |
که در آن و مقادیر ثابتاند و برای هر و هنگامی که داریم:
در الگوریتم خفاش تنظیم فرکانس، سرعت و دامنة حرکت ذرات را مشخص میکند. سرعت و دامنة حرکت ذرات با توجه به تغییرات بلندی صدا و پالس انتشار، متفاوت است. تغییرات میزان انتشار بلندی صدا و پالس، قابلیت تمرکز خودکار برای این الگوریتم را فراهم میکند؛ بهطوریکه استخراج راهحلها در قسمتی از فضای جستجو بهتر میشود که نتایج امیدبخشاند. میدانیم فرکانس بالاتر یعنی طول موج کوتاهتر و فاصلة کمتری را طی میکند؛ بنابراین، خفاشها وقتی به طعمه نزدیکترند، صدای آنها فرکانس بیشتری خواهد داشت. تنظیم فرکانس در این الگوریتم موجب موازنة بین اکتشاف و استخراج میشود. شبه کد الگوریتم خفاش در شکل (1) نشان داده شده است.
شکل (1): شبه کد الگوریتم خفاش استاندارد [1]
3- روابط بهروزرسانی جدید و تحلیل پایداری آن
در تلاشهای انجامشده با استفاده از روش لیاپانوف دربارة پایداری یا ناپایداری الگوریتم خفاش استاندارد نمیتوان اظهارنظر کرد؛ زیرا همواره علامت مقادیر ویژة به دست آمده متفاوت بود و امکان اظهارنظر دربارة پایداری یا ناپایداری این الگوریتم وجود نداشت؛ بنابراین، با استفاده از افزایش درجه آزادی الگوریتم و افزودن پارامتر جدید به آن، در جهت همگراشدن الگوریتم خفاش تلاش شد. بدینمنظور، پارامتر w با هدف پایدارشدن الگوریتم، به روابط بهروزرسانی الگوریتم خفاش اضافه شد. روابط بهروزرسانی پیشنهادی بهصورت روابط (7) و (8) خواهد بود:
|
(7) |
|
|
(8) |
در این روابط، پارامترهای w و f بهصورت آزادانه مقدار میگیرند و برای مقداردهی آنها نیاز به پیروی از رابطة خاصی نیست؛ اما ممکن است شرایط پایداری، محدودیتی روی مقادیر پارامترهای w و f اعمال کند.
با استفاده از تعریف ، نمایش فضای حالت روابط بهروزرسانی جدید بهصورت زیر خواهد بود:
|
(9) |
که در آن ماتریس حالت، ماتریس ورودی و ماتریس خروجی است.
بنابراین،
|
(10) |
قضیة لیاپانوف - سیستم در نزدیکی نقطة تعادل در مبدأ پایدار مجانبی است، اگر تابع اسکالری همانند V(x)وجود داشته باشد که شرایط زیر را برآورده کند ]22[:
1. V(x) در محدودهای حول مبدأ S پیوسته است و مشتقهای جزئی آن نیز پیوستهاند.
2. V(x) > 0 برایx≠0
3. V(0) = 0
شرایط 1 تا 3، معین مثبتبودن V(x) را تضمین میکنند و شرط 4 به معنی معین منفیبودن است.
نکته 1. سیستم یک نقطة تعادل منحصربهفرد در و دارد؛ جایی که متغیر با زمان است که میتواند بهترین موقعیت ذرات باشد. اگر ثابت و تغییرناپذیر با زمان باشد، این موضوع برای دینامیک باقی ذرات (ذراتی بهجز بهترین ذره) معتبر نیست. ازاینرو، نقطة تعادل فقط برای بهترین ذره وجود دارد که بهترین راهحل محلی الگوریتم خفاش در تکرار فعلی است و میتواند بهترین راهحل پس از تمام تکرارها باشد. اگر دینامیک بهترین ذرات بهطور صحیح پایدار باشند، تضمین میشود ذره به نقطة تعادل نزدیکتر میشود (درواقع به بهترین ذره نزدیکتر میشود). ممکن است شرایط برای وجود یک نقطة تعادل برای هر ذره در تمام زمانها در الگوریتم خفاش درست نباشد. تجزیه و تحلیل بقیه ذرات (غیر از بهترین ذره) چالشبرانگیز است و در این مقاله بررسی نشده است [15].
تابع اسکالر لیاپانوف v(x)بهصورت زیر تعریف میشود که تمامی شرایط قضیة لیاپانوف بهجز شرط 4 را برآورده میکند. برای برآوردهکردن شرط 4 نیاز است شرایط خاصی برقرار باشد و بررسی شود تحت چه شرایطی این تابع لیاپانوف در تمامی شرایط قضیه صدق میکند.
|
(11) |
برای بررسی شرط چهارم قضیة لیاپانوف باید شرایطی به دست آید که موجب منفیشدن یا همان میشود؛ بنابراین داریم:
|
(12) |
|
|
(13) |
باید منفی معین باشد →
|
(14) |
|
|
(15) |
محاسبة مقادیر ویژه:
|
(16) |
|
|
(17) |
|
|
(18) |
|
|
(19) |
|
|
(20) |
) |
|
(21) |
|
|
(22) |
|
شرایط مدنظر برای مقادیر ویژة منفی بهصورت زیر است که در اینجا بهطور مختصر و در ادامه به تفصیل بیان میشود. هر کدام از شرایط زیر برقرار باشد، موجب همگرایی و پایداری الگوریتم میشود.
1. هنگامی که باشد، آنگاه مقادیر ویژه مختلطاند؛ بنابراین، باید قسمت حقیقی این مقادیر ویژة مزدوج مختلط منفی باشند؛ بنابراین باید باشد؛
2. هنگامی که باشد، آنگاه مقادیر ویژه حقیقیاند؛ بنابراین، باید مقادیر ویژة حقیقی منفی باشند. پس باید باشد.
حال هریک از این شرایط بهطور مفصل بررسی میشوند. برای شرط اول داریم:
|
(23) |
> 0 |
بنابراین، نیاز است چندجملهای درجة 4 بالا برحسب f حل شود و سپس تعیین علامت شود. این چندجملهای درجة 4 با روشهای کاردانو و فراری [19-21] حل میشود و پس از حل چندجملهای، با توجه به علامت ضریب بزرگترین توان و بازههای بین ریشهها میتوان آن را تعیین علامت کرد. حل این چندجملهای درجة 4 با کمک روش فراری در ادامه آمده است:
|
(24) |
|
|
(25) |
→
|
چهار ریشة این معادله بهصورت در نظر گرفته میشود؛ بنابراین، با استفاده از روش فراری و فرمولهای مربوط به این روش، ریشهها بهصورت زیر خواهند بود:
|
(26) |
|
|
(27) |
بهطوریکه:
|
(28) |
|
|
(29) |
|
|
(30) |
|
|
(31) |
|
|
(32) |
|
|
(33) |
بنابراین، ریشههای چندجملهای درجة 4 برحسب w به دست آمدند؛ بنابراین، اگر فرض کنیم آنگاه تعیین علامت تابع g بهصورت زیر خواهد بود:
همانطور که مشاهده میشود برای محاسبة ریشهها در عبارات مربوط به آنها متغیرهای S و Q در مخرج آمدهاند و واضح است اگر هریک از این دو متغیر، مقدار صفر را به خود اختصاص دهند، ریشه تعریفنشده میشود و دچار مشکل میشویم؛ اما روش فراری برای این حالتهای خاص نیز راهحل ارائه داده است و میتوان با استفاده از فرمولهای این روش، در این شرایط خاص، ریشهها محاسبه میشوند [20]. بنابراین، چند رابطه برای محاسبة ریشهها وجود دارد؛ اما با توجه به اینکه نمیتوان همیشه از یک رابطه برای محاسبة ریشهها استفاده کرد و ریشهها نیز عبارتهایی برحسب متغیر w هستند و با توجه به مقدار w، ترتیب بزرگی و کوچکی ریشهها و در نتیجة آن، بازههای مثبت و منفی شدن چندجملهای درجة 4 تغییر میکند؛ بنابراین، نمیتوان رابطه و بازة صریحی به دست آورد. به همین علت تصمیم گرفته شد بازة همگرایی و شرایط پایداری را با استفاده از پیادهسازی و بهصورت عددی و با رسم نمودار به دست آوریم؛ بنابراین در ادامه فقط شرایط غیرصریح کافی برای همگرایی، توضیح داده و روابط آن ارائه میشود. گفتنی است روش لیاپانوف فقط شرایط کافی را مشخص میکند و دربارة شرایط کافی اطلاعاتی به ما نمیدهد.
بنابراین، برای برقراری شرط اول همگرایی باید شرایط زیر برقرار باشد:
1- منفیبودن دلتای معادلة مشخصه
|
(34) |
|
|
(35) |
>0 |
2- منفیبودن قسمت حقیقی ریشههای مزدوج مختلط معادله
|
(36) |
|
|
(37) |
|
|
(38) |
برای اینکه ناحیهای با علامت منفی وجود داشته باشد، حتماً باید باشد؛ در نتیجه:
|
(39) |
بنابراین، باید:
|
(40) |
|w| < |
و
|
(41) |
و همچنین برای برقراری شرط دوم همگرایی باید شرایط زیر برقرار باشد:
1- مثبتبودن دلتای معادلة مشخصه
|
(42) |
|
|
(43) |
0 |
2- منفیبودن ریشهها یا همان مقادیر ویژة حقیقی
|
(44) |
|
|
(45) |
4- توصیف و رسم فضای پایدار
شرایط پایداری بهصورت خلاصه اینچنین توصیف میشود:
|
(46) |
|
|
یا |
|
|
(47) |
|
اگر شرایط بالا را بهصورت عددی و با استفاده از پیادهسازی و رسم نمودار برحسب f و w رسم کنیم، محدودة پایداری یا همگرایی الگوریتم بهصورت شکل (2) خواهد بود.
شکل (2): محدودة پایداری الگوریتم جدید مبتنی بر الگوریتم خفاش
نکته 2. گفتنی است در صورتی که w = 1 باشد، روابط بهروزرسانی پیشنهادی به روابط بهروزرسانی خفاش استاندارد تبدیل خواهد شد. با توجه به اینکه زمانی که مقدار این پارامتر 1 باشد، خارج از محدودة پایداری قرار داریم؛ بنابراین، شرایط به دست آمده برای الگوریتم خفاش استاندارد صدق نمیکند و برای خفاش استاندارد، بازة پایداری به دست نیامده است. توجه به این نکته ضروری است که رعایتنکردن شرایط لیاپانوف، لزوماً به معنی ناپایداری الگوریتم نیست؛ بنابراین همچنان دربارة پایداری یا ناپایداری الگوریتم خفاش استاندارد نمیتوان اظهارنظر کرد.
5- نتایج تجربی
آزمایشها با استفاده از تابع Rosenbrock با ابعاد 16 انجام شده است. برای این آزمایشها اندازة جمعیت 100 و تعداد تکرار 250 در نظر گرفته شده و هر نمودار نشاندهندة میانگین 50 اجرا است. همانطور که در شکل (3) مشاهده میشود، هنگامی که پارامترها در بازة همگرایی قرار دارند، روند کلی نمودار لیاپانوف بهصورت نزولی خواهد بود و مقادیر ویژه همواره منفیاند. درواقع تمام ذرات در جهت نزدیکشدن به بهترین راهحل موجود در جمعیت (gbest) تلاش میکنند؛ بنابراین، تا زمانی که بهترین راهحل موجود در جمعیت ثابت است و تغییری نمیکند، همة ذرات به آن نزدیک میشوند و بنابراین نمودار لیاپانوف نزولی خواهد بود؛ اما زمانی که بهترین راهحل تغییر زیادی میکند، ممکن است نمودار کمی صعود پیدا کند و درواقع در این زمان، همگرایی و پایداری از ابتدا شروع میشود و پس از آن، مجدد روند نمودار نزولی خواهد شد؛ بنابراین، الگوریتم در زمانهای مختلف بهصورت محلی همگرا خواهد بود و همواره مقادیر ویژه منفی باقی میمانند. نمودار مربوط به شکل (3) بهصورت لگاریتمی نمایش داده شده است تا روند کاهش تابع لیاپانوف در طی تکرارها مشهود باشد. همچنین، همانطور که در شکل (4) مشاهده میشود، مقادیر ویژه در بازة همگرایی همواره منفیاند که این امر نشاندهندة پایداری الگوریتم در بازة همگرایی است.
همانطور که در شکل (5) مشاهده میشود، هنگامی که پارامترها در بازة همگرایی قرار ندارند، الگوریتم میتواند هر رفتاری از خود نشان دهد و همگرایی تضمین نمیشود؛ بنابراین، روند کلی نمودار لیاپانوف مربوط به آن نزولی نخواهد بود. نمودار مربوط به شکل (5) بهصورت لگاریتمی نمایش داده شده است تا روند افزایش تابع لیاپانوف در طی تکرارها مشهود باشد. با توجه به شکل (6)، مقادیر ویژه در خارج از بازة همگرایی لزوماً منفی نیستند و بنابراین الگوریتم میتواند همگرا نشود و تضمینی برای پایداری الگوریتم در خارج از بازة همگرایی وجود ندارد.
با توجه به بازة پایداری به دست آمده در شکل (2)، اگر مقادیر پارامتر w مربوط به این بازه را در ماتریس حالت مربوط به معادله 9 (ماتریس A) جایگذاری کنیم، مقادیر ویژة آن یا همان قطبهای سیستم در بازة قرار میگیرند. با توجه به اینکه مقادیر ویژه در داخل دایرة واحد قرار دارند، میتوان پایداری سیستم را نتیجه گرفت.
شکل (3): نمودار لیاپانوف برحسب تکرار در بازة همگرایی
شکل (4): نمودار مقادیر ویژه برحسب تکرار در بازة همگرایی
شکل (5): نمودار لیاپانوف برحسب تکرار خارج از بازة همگرایی
شکل (6): نمودار مقادیر ویژه برحسب تکرار خارج از بازة همگرایی
6- نتیجهگیری
در این مقاله، پایداری الگوریتم خفاش اصلاحشده تحلیل شده است. با هدف پایدارکردن الگوریتم خفاش، درجه آزادی الگوریتم افزایش یافته است و با افزودن یک پارامتر به پارامترهای این الگوریتم، روابط بهروزرسانی جدیدی پیشنهاد شده و سپس از روش لیاپانوف برای به دست آوردن شرایط کافی پایداری و همگرایی به نقطه تعادل استفاده شده است. شرایط به دست آمده بهدلیل استفاده از روش لیاپانوف، محافظهکارانهاند. هنگامی که از روش لیاپانوف برای تحلیل پایداری استفاده میشود، رعایتنکردن شرایط پایداری به معنی ناپایداری سیستم نیست؛ بلکه خارج از محدودة پایداری، پایداری و همگرایی الگوریتم تضمین نمیشود. برای پژوهشهای آتی، میتوان از تابع هزینه در تابع لیاپانوف استفاده کرد یا عملگر جهش به الگوریتم افزود و سپس پایداری الگوریتم با جهش تحلیل شود.
[1]تاریخ ارسال مقاله: 10/12/1397
تاریخ پذیرش مقاله: 08/03/1398
نام نویسنده مسئول: امین نیک انجام
نشانی نویسنده مسئول: ایران ـ تهران ـ دانشگاه صنعتی خواجه نصیرالدین طوسی - دانشکده مهندسی کامپیوتر
)