کافه دانایی

منبع پایان نامه ارشد درمورد قابلیت اعتماد، جستجوی محلی، بهینه سازی

نیز در بازهی[0,1] قرار دارد که در آن یک، ماکزیمم نرخ ارسال پالس را نشان میدهد.
علاوه بر فرضیات ذکر شده، میتوان به جای استفاده از طول موج، فرکانس را تغییر داد و λ را ثابت فرض کرد زیرا حاصلضرب fλ ثابت است. شبه کد این الگوریتم در شکل زیر آورده شده است.
________________________________________________________
Objective function f(x),x=(x1,…,xd)T
Initialize the bat population xi ,vi, i=(1,1,…,n)
Define pulse frequency fi at xi
Initialize pulse rates ri and the loudness Ai
While (t ri )
Select a solution among the best solutions
Generate a local solution around the selected best solution
End if
Generate a new solution by flying randomly
If ( rand Ai & f )xi) f(x*)
Accept the new solutions
Increase ri and reduce Ai
End if
Rank the bats and find the current best x*
End while
Postprocess results and visualization
________________________________________________________
روابط به روزرسانی سرعت و موقعیت در این الگوریتم دارای شباهتهایی با روابط موجود در بهینه سازی تودهی ذرات میباشد. میتوان گفت الگوریتم خفاش ترکیبی از این الگوریتم و جستجوی محلی است که توسط بلندی صدا و نرخ ارسال پالس کنترل میشود. موقعیتهای جدید xi و سرعت vi در زمان t به صورت زیر میباشند:
f i = fmin+ (fmax – fmin))
vit = vit-1+ ( xit – x*) fi (3-8)
xit = xit-1 + vit
که در آن ک یک بردار تصادفی در بازهی [0,1] میباشد و از یک توزیع یکنواخت به دست میآید. در اینجا x*بهترین موقعیت سراسری جاری است که بعد از مقایسهی تمامی موقعیتهای به دست آمده توسط n خفاش تعیین میشود. در الگوریتم خفاش، بلندی صدا و نرخ ارسال پالس نیز بایستی در طول تکرارها به روزرسانی شوند. بلندی صدا با نزدیک شدن خفاش به طعمه، کاهش مییابد و زمانی که خفاش طعمه را بیابد، مقدار A صفر میشود. در مقابل، نرخ ارسال پالس با یافتن طعمه مقدار ماکزیمم به خود گرفته و یک میشود.
Ait+1 = α Ait
rit+ 1= ri0 [1- exp( γt )] (3-9)
که در آن α وγ ثابت هستند. در حقیقت α مشابه با فاکتور سرد شدن در الگوریتم SA میباشد. برای هر مقدار 0 α <1 و γ>0 زمانی که t به سمت بی نهایت میل کند، Ait به صفر و rit به مقدار ri0 میل میکند به عبارتی :
Ait →0, rit → ri0 as t→0
در ابتدا هر خفاش مقادیر متفاوتی از بلندی صدا و نرخ ارسال پالس دارد. این پارامترها در ابتدا به صورت تصادفی انتخاب میشود. سپس مقدار آنها به روزرسانی میشود.
برای بخش جستجوی محلی، وقتی یک راه حل از بین بهترین راهحلهای موجود انتخاب شد، موقعیت جدید برای هر خفاش بهطور محلی توسط پیادهروی تصادفی به صورت زیر تعیین میشود:
(3-10) xnew = xold+εAt
که در آن ε یک عدد تصادفی در بازهی[-1,1] است و At میانگین بلندی صدای تمامی خفاشها در این زمان است[48]،[49].
3-3-7- راه حل‌های پیشنهادی برای بهبود عملکرد الگوریتم خفاش
3-3-7-1‌- انتخاب جمعیت اولیه براساس قاعده‌ی تولید عدد متضاد51
جهت افزایش نرخ و سرعت همگرایی به جواب، باید برای هر کدام از اعضای جمعیت اولیه تقریب مناسبی زده شود. تولید عدد متضاد از جمله راهکارهایی است که به این منظور استفاده میشود.
اگر Xi یک بردار تصادفی در فضای جستجو باشد بردار متضاد آن به صورت زیر ساخته می‌شوند:
(3-11)
متغیرهای باید در محدوده‌ی تغییرات xi,j یعنی باشند. حال اگر دارای تابع هدف بهتری نسبت به باشد جایگزین آن می‌شود.
3-3-7-2- استراتژی جهش خود تطبیق
همانگونه که پیشتر ذکر شد مشکل اصلی الگوریتم BA گیر کردن در بهینه‌های محلی است. برای حل این مشکل و فرار از بهینه‌های محلی روش جدیدی مبتنی بر دو قانون جهش استفاده شده است. در هر تکرار، هر عضو جمعیت فقط می‌تواند از یکی از این جهش‌ها برای بهبود وضعیت خود استفاده کند. برای انتخاب نوع جهش، برای هر عضو از اعضای جمعیت یک عدد تصادفی تولید میشود. با توجه به مقدار Si یکی از دو نوع جهش برای عضو مورد نظر انتحاب میشود.
* روش جهش اول:
در این روش در هر تکرار kپس از محاسبه میانگین جوابها و اختلاف آن با بهترین جواب، طبق رابطه زیر موقعیت جدید بهدست میآید:
(3-12)
به ترتیب خفاش با بهترین موقعیت از نظر تابع هدف و میانگین موقعیت خفاش‌ها در تکرار جاری می‌باشد. نیز ضریب یادگیری است که با توجه به رابطه‌ی یکی از دو مقدار یک یا دو را اختیار می‌کند. این روش علاوه بر افزایش سرعت همگرایی ،از همگرایی زودرس جلوگیری میکند.
* روش جهش دوم:
روش دوم به منظور جلوگیری از افتادن در بهینه‌های محلی و ایجاد سکون در جمعیت از تئوری موج ضربه‌ای کوچک (Wavelet) کمک میگیرد. تابع موج ضربه‌ای مورلت52 (شکل 3-7) به عنوان تابع موج ضربه‌ای مادر53 به کار می‌رود که فرمول آن به فرم زیر است:
(3-13)
شکل3-7 تابع موج ضربه‌ای مورلت
پارامتر d تعبیه شده در این تابع، کمک می‌کند تا تصمیم‌گیرنده بتواند دامنه‌ی تابع را تعیین کند:
(3-14)
در هر تکرار برای هر خفاش که این جهش را برای تولید بردار طراحی آزمایشی انتخاب کرده، سه عضو متفاوت از جمعیت کنونی انتخاب می‌گردد پس از آن عملگر جهش طبق رابطه زیر اعمال می‌گردد:
(3-15)
که همان می‌باشد و به صورت زیر نوشته می‌شود:
(3-16)
در این رابطه یک عدد تصادفی تولید شده در بازه‌ی [-4,4] می‌باشد و d به صورت زیر نوشته می‌شود:
(3-17)
که حد بالا و پارامتر تعیین‌کننده یکنواختی افزایش تابع d می‌باشند. درتکرارهای ابتدایی الگوریتم، مقدار k نسبت به ماکزیمم تکرار kmax خیلی کوچکتر است پس d براساس رابطه‌ی (17-3) مقدار کوچکی است که در نتیجه آن مقدار Δ بزرگ خواهد بود. اگر 0Δ باشد موجب می‌گردد تا خفاش مورد نظر در جهت بهترین موقعیت کشف شده توسط الگوریتم در این تکرار حرکت کند. اگر 0Δ باشد باعث می‌شود خفاش مورد نظر در خلاف جهت بهترین موقعیت کشف شده توسط الگوریتم در این تکرار حرکت کند. این حرکت در جهت خلاف کمک میکند تا نقاط رها شدهای که ممکن است حاوی اطلاعات مفید باشند کشف شوند. هر چه الگوریتم به ماکزیمم تکرار خود نزدیکتر شود d بسیار بزرگتر می‌گردد در نتیجه آن Δ کوچکتر می‌شود. مقدار کوچک برای Δ باعث می‌گردد الگوریتم BA بیشتر به جستجوی محلی و بهره‌برداری بپردازد.
بعد انتخاب نوع جهش و انجام آن برای هر خفاش‌ها، بردار آزمایشی تولید شده با بردار اولیه ترکیب می‌گردد و بردار جدید تحت رابطه‌ی زیر به دست آید:
(3-18)
حال اگر بردار جدید تابع هدف کوچکتری نسبت به بردار اولیه داشته باشد جایگزین آن می‌شود، در غیر این صورت الگوریتم با همان بردار اولیه به کار خود ادامه می‌دهد.
3-5- معیارهای مقایسه‌ی الگوریتم‌های بهینه‌سازی
در مقایسه الگوریتم‌های بهینه‌سازی دو معیار همگرایی و عملکرد مطرح می‌شود . بعضی از الگوریتم‌ها دارای همگرایی بوده ولی ممکن است عملکرد ضعیفی داشته باشند ، یعنی فرایند بهبود آنها از کارایی و سرعت لازم برخوردار نباشد ؛ برعکس بعضی دیگر از الگوریتم‌ها همگرایی نداشته ولی عملکرد آنها خیلی خوب است . در فاز عملکرد چندین معیار مطرح است که در ادامه بررسی میشود.
3-5-1-کارآیی54
این معیار میزان موفقیت الگوریتم را در تولید جواب‌های بهینه نشان می‌دهد. هرچه بهترین جواب، بدترین جواب و میانگین جواب‌ها به یکدیگر نزدیک‌تر باشند، نشان‌دهندهی کارایی بالای الگوریتم می‌باشند.
3-5-2- انحراف استاندارد55
معیار انحراف استاندارد دومین معیار مورد استفاده برای مقایسه‌ی عملکرد الگوریتم‌های متفاوت در زمینه‌ی حل مسأله‌ی بهینه‌سازی مورد نظر می‌باشد. این معیار به طور گسترده توسط محققین در مقالات زیادی مورد استفاده قرار می‌گیرد. Std نشان‌دهنده‌ی میزان انحراف جواب‌های خروجی نسبت به میانگین جواب‌ها می‌باشد. هر چه Std ‌یک الگوریتم کمتر باشد، نشان می‌دهد که آن الگوریتم دارای عملکرد بهتر و مطمئن‌تری در به دست آوردن جواب است.
3-5-3- قابلیت اعتماد56
قابلیت اعتماد یک معیار مهم در عملکرد الگوریتم می‌باشد. این معیار نشان می‌دهد که الگوریتم ارائه شده در به دست آوردن جواب بهینه‌ی سراسری یا نزدیک به سراسری تا چه حد قابل اعتماد است. برای اندازه‌گیری قابلیت اعتماد یک الگوریتم، یک روش استفاده از معیار درصد موفقیت است. بدین صورت که، در هر بار حل، بهترین جواب برای تابع هدف یادداشت می‌شود، سپس بازه‌ی بین ماکزیمم و مینیمم مقدار به دست آمده به چندین قسمت مساوی تقسیم می‌گردد، حال باید نگاه کرد که در هر یک از بازه‌های تعیین شده چند درصد از شبیه‌سازی‌های انجام شده قرار می‌گیرند. هر چه این درصدها در مقادیر نزدیک به مینیمم مقدار بیشتر داشته باشند نشان‌دهنده‌ی نرخ موفقیت بیشتر الگوریتم هستند.
3-5-4- سرعت همگرایی57
معیار سرعت همگرایی نشان‌دهنده‌ی تعداد تکرارهای مورد نیاز یا تعداد ارزیابی‌های تابع هدف برای یک الگوریتم قبل از رسیدن به جواب بهینه می‌باشد. همچنین از گراف همگرایی نیز برای نشان دادن سرعت همگرایی استفاده می‌کنند.
3-5- تعریف مسائل عددی گوناگون
جدول (3-1) توابع عددی، نمایش ریاضی، مقدار بهینه‌ و نوع آن‌ها را نشان می‌دهد. دلیل انتخاب این توابع آن است که هر یک از آن‌ها نماینده‌ی دسته‌ای از مسائل دنیای واقعی می‌باشند. یک الگوریتم بهینه‌سازی باید بتواند توازن را بین شناسایی و بهره‌برداری برقرار کند، پراکندگی را کنترل کند و از همگرایی زودرس و سکون جلوگیری کند تا بتواند همه‌ی این مسائل را که مشخصات متفاوتی دارند به درستی حل کند.
جدول3-1 توابع عددی مورد استفاده برای تست الگوریتم‌ها
Trait
Opt. Value
Opt. Possition
فرمول
نام تابع
تابع
Multimodal
0
[1,1,…,1]
Generalized Rosenbrock
Multimodal
0
[420.9867,…, 420.9867]
Generalized Schwefel
Multimodal
0
[0,0,…,0]
Generalized Rastrigin
Multimodal
0
[0,0,…,0]
Generalized Ackley
Multimodal
0
[0,0,…,0]
Generalized Griewank
3-5-1- تابع Rosenbrock
این تابع که یک تابع غیر محدب است در سال 1960 توسط Howard H. Rosenbrock برای تست عملکرد الگوریتمهای بهینه سازی معرفی شد. مینیمم کلی این تابع درون یک دره صاف، سهمی شکل، باریک و کشیده قرار دارد. شکل (3-8)، نمایش سه بعدی گرافیکی تابع را به همراه contour آن نشان می‌دهد. همانگونه که از شکل پیداست،این تابع شیب بسیار نرمی در اطراف بهینه‌ی سراسری دارد و گرادیان تابع در جهت خود تابع نمی‌باشد. تمامی این خصوصیات باعث شده که همگرایی الگوریتم به سمت بهینه‌ی سراسری با مشکلاتی همراه باشد. الگوریتم‌هایی که بر روی مسیر حرکت اعضایشان به سمت بهینه‌ی سراسری محدودیت‌های زیادی را اعمال می‌کنند در حل این تابع دچار سکون خواهند شد[50].
ب)
الف)
شکل 3-8 الف) نماش سه بعدی تابع Rosenbrock ب) نمایش contour تابع Rosenbrock