الگوریتم کلونی زنبورعسل
اسلاید 1: 1 - 65
اسلاید 2: 2الگوریتم کلونی زنبورعسل - 65
اسلاید 3: تاریخچه :3Dervis karabogaالگوریتم زنبور اولین بار در سال 2005 توسعه یافت ؛ این الگوریتم شبیه سازی رفتار جستجوی غذای گروه های زنبور عسل است. در این الگوریتم، الگوریتم نوعی از جستجوی محلی انجام می دهد که با جستجوی تصادفی ترکیب شده است - 65
اسلاید 4: 4زنبور در طبیعت:کلونی زنبورها درطبیعت شامل منابع غذایی و زنبورها می باشد.منابع غذایی:1- کیفیت منبع2- آسانی دستیابی به منبع3- فاصله از کندو - 65
اسلاید 5: 5زنبورها:زنبورها شامل سه دسته هستند.1- زنبور پیشرو: این زنبور مسئولیت پیدا کردن مواد غذایی جدید، شهد جدید و منابع را دارد.2- زنبورکارگر: به طرف منابع غذایی از پیش تعیین شده فرستاده میشود و موقعیت همسایه ها را نیز بررسی میکند. 3- زنبورناظر: زنبوری که در کندو با دریافت اطلاعات منابع غذایی از زنبور کارگر و پیشرو منابع غذایی را برای جمع آوری شهد انتخاب میکند. - 65
اسلاید 6: 6AکندوCDBجستجوی زنبورهای پیشرو - 65
اسلاید 7: 7AکندوCDBپایان جستجوی زنبور های پیشرو - 65
اسلاید 8: رقص چرخشی8فاصله از کندو: میزان چرخشکیفیت منبع : میزان ارتعاشاتجهت منبع : زاویه نسبت به خورشید - 65
اسلاید 9: 9کندوAB10CDBارسال زنبور های کارگر - 65
اسلاید 10: 10کندوA8B10C5D2B10محاسبه برازندگی منابع - 65
اسلاید 11: 11ABکندوCD0.40.30.10.2محاسبه احتمال ارسال زنبور های ناظر - 65
اسلاید 12: 12کندوA8B10C5D2B10ارسال زنبور های ناظر - 65
اسلاید 13: منابع متروکه: منابعی که نیروی محاسباتی را به هدر میدهد و تلاش برای بهبود کارساز نیست. این منبع بعد از چند بار برای بهبود یافتن و عدم موفقیت جایگزین میشود.13 - 65
اسلاید 14: 14کندوA8B10C5D2 - 65
اسلاید 15: 15دو مفهوم مهم درالگوریتم زنبور عسل::Exploitation توانایی پرورش پاسخ های فعلی برای رسیدن به پاسخ های بهتر:Explorationتوانایی تولید پاسخ های جدید و متفاوت - 65
اسلاید 16: الگوریتم تپه نوردی16313∎22211∎222313423232∎123241∎2312∎15132∎21514121241∎1311322131∎F(x)=0+1+1+0+1+1+1+1=6 - 65
اسلاید 17: وجود منبع متروکشرط خاتمهمشخص کردن پارامتر های اولیهتولید پاسخ های اولیه(جستجو زنبورهای پیشرو)انتخاب منابع بهتربرسی همسایگی ها(حرکت زنبور های کارگر)جستجوی منبع جدیدپایان خیربلهخیربلهشروع17فلوچارت الگوریتم زنبور عسل - 65
اسلاید 18: مرحله اول: مشخص کردن پارامترهای مسئلهجمعیت اولیه، تعداد زنبورهای کارگر و پیشروابعاد مسئلهتابع برازندگیمحدوده مسئلهشاخص محاکمهحد مجاز برای شاخص محاکمه18 - 65
اسلاید 19: مرحله دوم : جستجوی منابع توسط زنبورهای پیشرو19 : جواب i ام و بعد j امr: عددی تصادفی بین صفر و یکMin : حد پایینMax : حد بالا - 65
اسلاید 20: مرحله سوم:انتخاب منابع بهتربدست آوردن تابع هزینه برای هر منبعحذف درصد مشخصی از منابع با پایین ترین کارایی fit(xᵢ)=20 - 65
اسلاید 21: مرحله چهار: حرکت زنبورهای کارگر و ناظر 21t : زنبور t امj : بعد پاسخ : موقعیت زنبور : انتخاب تصادفی یک زنبور کارگر: انتخاب یک عدد تصادفی ما بین (1،1-) - 65
اسلاید 22: روشهای ارسال زنبورهای ناظر:22تخصیص زنبور های ناظر به منابع با توجه به برازندگی آنها (چرخ رولت)Pi : احتمال انتخاب i امین زنبورکارگر S : تعداد زنبور کارگر: مقدار برازندگی - 65
اسلاید 23: مرحله پنجم: تعیین منبع متروکهبررسی شاخص محاکمه برای هر منبع:در صورتی که شاخص محاکمه بزرگتر یا برابر حد مجاز باشد و آن منبع بهترین .جواب مسئله نباشد منبع متروک میشود23 - 65
اسلاید 24: مرحله ششم: جستجوی منبع جدید بجای منابع متروکجستجوی سراسریمنابعی که متروک شده اند باید توسط منابع جدید جایگزین شوند24 - 65
اسلاید 25: مرحله هفتم: شرایط خاتمهبه یک مقدار مشخص از تابع هزینه برسیم.تعداد تکرار را محدود کنیم.جوابها همگرا شوند.25 - 65
اسلاید 26: کلونی زنبور عسل مصنوعیزنبور کارگرزنبور ناظرزنبور پیشرو26ثبت بهترین راه حل پیدا شده تا کنون - 65
اسلاید 27: وجود منبع متروکشرط خاتمهمشخص کردن پارامتر های اولیهتولید پاسخ های اولیه(جستجو زنبورهای پیشرو)انتخاب منابع بهتربرسی همسایگی ها(حرکت زنبور های کارگر)جستجوی منبع جدیدپایان خیربلهخیربلهشروع27فلوچارت الگوریتم زنبور عسل - 65
اسلاید 28: جستجوی الگوریتم زنبور در فضای مسئله :28 - 65
اسلاید 29: 29 - 65
اسلاید 30: 30 - 65
اسلاید 31: حل مسئله رنگ آمیزی گراف:مسئله :گرافی به شکل زیر داریم . میخواهیم خانه های این گراف را به نحوی با 3 رنگ ، رنگ امیزی کنیم که هیچ یک از خانه های مجاور یکدیگر همرنگ نباشند. گراف شامل 7 خانه می باشد .31 - 65
اسلاید 32: کد کردن مسئله :قبل از حل مسئله توسط الگوریتم زنبور باید مسئله را به شکلی در آوریم که توسط این الگوریتم قابل حل باشدهر جواب را به صورت زیر معرفی میکنیم :abcdefgهر کدام از خانه های آرایه فوق معرف یکی از گره های گراف است و مقادیر مجاز برای هر خانه1 ، 2 و 3 است که معرف سه رنگ است برای مثال قرمز ، آبی و سبز. مثلا :32 - 65
اسلاید 33: مرحله اول: تعیین پارامتر های اولیهcs =11زنبور پیشرو 4 (جواب های اولیه) زنبور کارگر 7 ) 3تا برای بهترین منبع و برای دو منبع متوسط هر کدام دو زنبور) D = 7 k = 1 , 2 , 3 , 4F(xᵢ)= مجموع تعداد تناقض ها برای تمام خانه های مجاور و همرنگ Cᵢ= شاخص محاکمه, L=cs*d/2=11*7/2=38 اگر Cᵢ>=L منبع i ام به شرطی که بهترین منبع نباشد با یک جواب تصادفی تعویض می شودXmin=1 ; Xmax=3هدف: رسیدن به fit (xᵢ) = 1 33 - 65
اسلاید 34: مرحله دوم: تولید جوابهای اولیه مسئله (ارسال زنبورهای پیشرو )منبع اول:x₁a= 1 + 0.71 * ( 3 – 1 )= 2x₁b= 1 + 0.14 * (3 – 1 )= 1x₁c= 1 + 0.57 * (3 – 1 )= 2x₁d= 1 + 0.0 * (3 – 1 )= 1x₁e= 1 + 0.85 * (3 – 1 )= 3x₁f= 1 + 0.42 * (3 – 1 )= 2x₁g= 1 + 0.28 * (3 – 1 )= 234Xij=Xjmin+r(Xjmax-Xjmin) - 65
اسلاید 35: منابع اولیه:35j0=a1=b2=c3=d4=e5=f6=gمنبع 12121322منبع 21232131منبع 33123121منبع 41233231 - 65
اسلاید 36: مرحله سوم: انتخاب منابع بهترfit(xᵢ) = 1 / (1+F( xᵢ ) )بدست آوردن کارایی منبع اول:F(x1)=1+0+1+0+0+1+1=4fit(x1)= 1/ (1+4)= 0.2 25% منابع با کمترین کارایی حذف میشوند و بقیه منابع نگه داشته میشوند.36 - 65
اسلاید 37: F(x1)= 4 fit(x1)= 0.2 F(x2)= 2 fit(x2)= 0.33 F(x3)= 6 fit(x3)= 0.142 F(x4)= 4 fit(x4)= 0.2منبع سوم حذف میشود:بهترین منبع: منبع 2(ارسال سه زنبور)منابع متوسط: منبع 1 و منبع 4 (ارسال دو زنبور)37j0123456منبع 12121322منبع 21232131منبع 33123121منبع 41233231 - 65
اسلاید 38: مرتب کردن منابع با توجه به برازندگی :38 - 65
اسلاید 39: j0123456X1(t)1232131X3=Xk1233231⏀10.30.30.10.210.220.350.01X1(t+1)1231.791.5631مرحله چهار: حرکت زنبورهای کارگر(بررسی همسایگی ها)حرکت زنبور کارگر اول :i = 1k =339Xij(t+1)=Xij(t)+r(Xij(t)-Xkj(t))X1j(t+1)=X1j(t)+r(X1j(t)-X3j(t)) - 65
اسلاید 40: if xij < 0 xij = 3 + xijIf xij > 3 xij = xij – 3 اگر اعداد خارج از محدوده بودند ، بازه را دورانی در نظر میگیریم .X1( t +1 )1232231گرد کردن اعداد :40 - 65
اسلاید 41: F( x1 (t + 1 ) ) = 4fit(x1 (t + 1 ) )= 0.2C1=0منبع10123456fitپیشرو12321310.33کارگر112322310.241 - 65
اسلاید 42: حرکت زنبور کارگر دوم:j0123456X1(t)1232131X1(t+1)1332131I = 1K =2F(x(t+1))=6 fit(x1(t+1))=0.142 C1=0منبع10123456fitپیشرو12321310.33کارگر112322310.2کارگر21332131014242 - 65
اسلاید 43: حرکت زنبور کارگر سوم:j0123456X1(t)1232131X1(t+1)2132131I = 1K =3F(x(t+1))=6 fit(x1(t+1))=0.142 C1=1منبع10123456fitپیشرو12321310.33کارگر112322310.2کارگر213321310142کارگر321321310.14243 - 65
اسلاید 44: حرکت زنبور کارگر چهارم :I= 2k = 1j0123456X2(t)2121322X2(t+1)2121312fit( x2 (t + 1 ) ) = 0.2 F(x2( t +1 )) = 4 C2=1منبع20123456Fitپیشرو21213220.2کارگر421213120.244 - 65
اسلاید 45: زنبور کارگر پنجم به منبع دوم فرستاده میشود و زنبور کارگر ششم و هفتم به منبع سوم فرستاده میشوند منبع20123456Fitپیشرو21213220.2کارگر421213120.2کارگر521312210.2منبع30123456Fitپیشرو12332310.2کارگر612322310.2کارگر712321310.33C2=1C3=045 - 65
اسلاید 46: مرحله پنجم: وجود منبع متروکدر مراحل قبل شاخص های محاکمه را بدست اوردیم و هیچ کدام به limit نرسیده بودند و متروک نمیشوندC1=1 , C2=1 , C3=025% پایین کارایی متروک شده بودند . به جای جواب های متروک جواب های تصادفی قرار می دهیم46 - 65
اسلاید 47: مرحله ششم: جستجوی منبع جدیدجستجوی منبع جدید توسط زنبور پیشرو چهارم:2131213F(x4)= 2Fit(x4)= 0.3347 - 65
اسلاید 48: مرحله هفتم: شرط خاتمهبالاترین کارایی هر منبع را انتخاب میکنیم وسپس شرط خاتمه را روی آن بررسی میکنیم:j0123456fitF(x)منبع 112321310.334منبع 221213220.28منبع 312321310.332منبع 421312130.332شرط خاتمه برقرارنیست 48 - 65
اسلاید 49: چرخه دوم مساله:مرحله دوم: انتخاب منابع بهترjjj0123456fitF(x)منبع 112321310.334منبع 312321310.332منبع421312130.332مراحل الگوریتم تکرار میشود تا به شرط خاتمه برسیم49 - 65
اسلاید 50: حل مسئله n وزیر:50مرحله اول: تعیین پارامتر های اولیهcs =11زنبور پیشرو 4 (جواب های اولیه) زنبور کارگر 7 ) 3تا برای بهترین منبع و برای دو منبع متوسط هر کدام دو زنبور) D = 8 k = 1 , 2 , 3 , 4F(xᵢ)= تعداد برخورد هاCᵢ= شاخص محاکمه, L=cs*d/2=11*8/2=44 اگر Cᵢ>=L منبع i ام به شرطی که بهترین منبع نباشد با یک جواب تصادفی تعویض می شودXmin=0 ; Xmax=7هدف: رسیدن به fit (xᵢ) = 1 - 65
اسلاید 51: مرحله دوم: ارسال زنبورهای پیشرو و تولید جوابهای اولیه مسئلهمنبع اول:x₁₀= 0 + 0.71 * ( 7 – 0 )= 5x₁₁= 0 + 0.14 * (7 – 0 )= 1x₁₂= 0 + 0.57 * (7 – 0 )= 4x₁₃= 0 + 0.0 * (7 – 0 )= 0x₁₄= 0 + 0.85 * (7 – 0 )= 6x₁₅= 0 + 0.42 * (7 – 0 )= 3x₁₆= 0 + 0.28 * (7 – 0 )= 2x₁₇= 0 + 0.14 * (7 – 0 )= 7∎∎∎∎∎∎∎∎Xij=Xjmin+r(Xjmax-Xjmin)51 - 65
اسلاید 52: j01234567منبع 151406327منبع 202546317منبع 301234756منبع 472346510منابع اولیه:52 - 65
اسلاید 53: مرحله سوم: انتخاب منابع بهتر∎∎∎∎∎∎∎∎fit(xᵢ) = 1 / (1+F( xᵢ ) )بدست آوردن کارایی منبع اول:F(x1)=0+1+1+0+1+1+1+1=6fit(x1)= 1/ (1+6)= 0.142 25% منابع با کمترین کارایی حذف میشوند و بقیه منابع نگه داشته میشوند.53 - 65
اسلاید 54: j01234567منبع 151406327منبع 202546317منبع 301234756 F(x1)= 6 fit(x1)= 0.142 F(x2)= 8 fit(x2)= 0.111 F(x3)= 10 fit(x3)= 0.09 F(x4)= 12 fit(x4)= 0.07منبع چهار حذف میشود:بهترین منبع: منبع 1(ارسال سه زنبور)منابع نرمال: منبع 2 و منبع 3 (ارسال دو زنبور)54 - 65
اسلاید 55: j01234567X1(t)51406327X3=Xk01234756⏀10.20.30.10.210.220.350.010.12X1(t+1)614.2-0.636.441.61.977.12مرحله چهار: حرکت زنبورهای کارگرحرکت زنبور کارگر اول :I = 1K =3Xij(t+1)=Xij(t)+r(Xij(t)-Xkj(t))X1j(t+1)=X1j(t)+r(X1j(t)-X3j(t))55 - 65
اسلاید 56: if xij < 0 xij = 8 + xijIf xij > 7 xij = xij – 8 برای از بین بردن اعداد خارج از محدوده، بازه را دورانی در نظر میگیریم .X1( t +1 )614-16227گرد کردن اعداد :614-1622761476227-1+8=756 - 65
اسلاید 57: 6147622761475203F( x1 (t + 1 ) ) = 4fit(x1 (t + 1 ) )= 0.2C1=0منبع101234567fitپیشرو514063270.142کارگر1504672130.257 - 65
اسلاید 58: حرکت زنبور کارگر دوم:j01234567X1(t)51406327X1(t+1)50362714I = 1K =2F(x(t+1))=2 fit(x1(t+1))=0.33 C1=0منبع101234567fitپیشرو514063270.142کارگر1504672130.2کارگر2503627140.3358 - 65
اسلاید 59: حرکت زنبور کارگر سوم:j01234567X1(t)51406327X1(t+1)60415327I = 1K =2F(x(t+1))=5 fit(x1(t+1))=0.16 C1=0منبع101234567fitپیشرو514063270.142کارگر1504672130.2کارگر2503627140.33کارگر3604153270.1659 - 65
اسلاید 60: حرکت زنبور کارگر چهارم :I= 2 k = 1j01234567X2(t)02546317X2(t+1)10572643fit( x2 (t + 1 ) ) = 0.1 F(x2( t +1 )) = 10 منبع201234567Fitپیشرو025463170.111کارگر4105726430.160 - 65 C2=0
اسلاید 61: زنبور کارگر پنجم به منبع دوم فرستاده میشود و زنبور کارگر ششم و هفتم به منبع سوم فرستاده میشوند منبع201234567Fitپیشرو025463170.111کارگر4105726430.1کارگر5014723560.125منبع301234567Fitپیشرو012347560.09کارگر6720413560.125کارگر7623057140.125C2=0C3=061 - 65
اسلاید 62: مرحله پنجم: وجود منبع متروکدر مراحل قبل شاخص های محاکمه را بدست آوردیم و هیچ کدام به limit نرسیده بودند و متروک نمیشوندC1=0 , C2=0 , C3=025% پایین کارایی متروک شده بودند62 - 65
اسلاید 63: مرحله ششم: جستجوی منبع جدیدجستجوی منبع جدید توسط زنبور پیشرو چهارم:35146027F(x4)= 2Fit(x4)= 0.3363 - 65
اسلاید 64: مرحله هفتم: شرط خاتمهبالاترین کارایی هر منبع را انتخاب میکنیم وسپس شرط خاتمه را روی آن بررسی میکنیم:j01234567fitF(x)منبع 1504672130.24منبع 2014723560.118منبع 3720413560.118منبع4351460270.332شرط خاتمه برقرارنیست 64 - 65
اسلاید 65: چرخه دوم مساله:مرحله دوم: انتخاب منابع بهترjjj01234567fitF(x)منبع 1504672130.24منبع 3720413560.118منبع4351460270.332مراحل الگوریتم تکرار میشود تا به شرط خاتمه برسیم65 - 65
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.