شبیه سازی بهینه و ارائه الگوریتم BA
اسلاید 1: شبیه سازی بهینه و ارائه الگوریتم BAدرس شبیه سازیاستاد راهنما :جناب آقای دکتر شهانقیارائه دهنده:هدی فتحیپاییز 89
اسلاید 2: فهرست مطالبمقدماتی در مورد شبیه سازی بهینه ارائه الگوریتم شبیه سازی بهینه BAمثال
اسلاید 3: مقدماتی در مورد شبیه سازی بهینههدف بهترین ترکیب متغیر برای استفاده به عنوان ورودی یک مدل شبیه سازی است .قدم 1 : generation counter=0قدم 2 :تشکیل جمعیت اولیه برای شبیه سازیقدم3 : ارزیابی برازندگی جمعیت با اجرای شبیه سازیقدم4 : تولید نسل بعدیقدم 5 : ایجاد ترکیب بعدی بوسیله الگوریتم بهینه سازی(بازترکیب جمعیت)قدم6 : ارزیابی ترکیب بدست امده به وسیله شبیه سازیقدم7 : چک کردن شرط خاتمه و توقف یا بازگشت به قدم4
اسلاید 4: روش های شبیه سازی بهینه1- رتبه بندی و انتخاب 2- جستجو مبنی بر گرادیان3- تخمین احتمالی4- متدولوژی پاسخ سطح5- بهینه سازی مسیر نمونه6- روش های ابتکاری7-روش های مبنی بر مدل8- روش های ترکیبیروشهای اماری هستند که برای انتخاب بهترین جواب از میان مجموعه ای از جواب ها گسترش یافته اندمجموعه ای از بهترین متغیر های ورودی را گرفته و در مسیر گرادیان حرکت می کند فرایندی تکرارشونده است که از مجموعه ای از متغیر های ورودی حرکت را شروع میکند به سمت همسایگی حل موجود می رود.ریشه در طراحی ازمایش اماری دارد و هدف ان بدست اوردن رابطه تابعی تقریبی بین خروجی ها و ورودی های تابع هدف استاز چندین شبیه سازی استفاده کرده وسپس سعی می کند تا نتایج براورد شده را بهینه سازداز متدهای ابتکاری برای حل مسائل پیچیده شبیه سازی استفاده می کننداز یک توزیع احتمالی در فضای جواب استفاده می کند برای اینکه دریابد بهترین جواب در کجا واقع شده است ترکیبی از روش های بالا جهت حل مسائل پیچیده شبیه سازی است
اسلاید 5: استفاده ازba در شبیه سازی بهینهبا توجه به روش های گفته شده در شبیه سازی بهینه الگوریتم ba روشی مبنی بر مدل است که تابع هدف حاصل از شبیه سازی به عنوان ورودی وارد این الگوریتم شده و آن را بهینه می سازد.
اسلاید 6: مقدمه BAمحققان علاقه مند به تولید الگوریتم های جستجویی هستند که بتوانند جواب های بهینه را در زمان معقولی بدست اورند.الگوریتم بر مبنای جمعیت ((SOA یک الگوریتم جستجوی توانادر تعیین محل جواب های مناسب می باشد.الگوریتم می تواند در زمره ابزارهای بهینه سازی هوشمند قرار گیرد.
اسلاید 7: الگوریتم Swarm-based Optimization Algorithm (SOA) : این الگوریتم ها متدهایی الهام گرفته از طبیعت هستند که ما را به سمت جواب های بهینه می کشانند .تفاوت میان این الگوریتم ها و الگورتم های جستجوی مستقیم مانند بالارفتن از تپه در این است که SOA ها به جای یک حل منفرد مجموعه ای از حل ها را در نظر میگیرند.همانطور که یک جمعیتی از جوابها در هر تکرار بررسی می شود ،خروجی هر تکرار نیز یک جمعیت از جواب هاست.
اسلاید 8: SOAبرخی کاربردهای الگوریتم ارتشUS از این الگوریتم ها در کنترل ماشین های ارتش استفاده می کند. NASA برای نقشه های نجومی از این روش استفاده می کند.برخی محققان استفاده از این متدها را جهت داده کاوی پیشنهاد می کنند.
اسلاید 9: SOA مثال هایی از Genetic Algorithm (GA)Particle Swarm Optimization (PSO) AlgorithmAnt Colony Optimization (ACO) Algorithms, such as AS, ACS, MMAS, etc.Bees Algorithm (BA) or Honey Bee AlgorithmTermite Algorithm … Other SOAs
اسلاید 10: زنبورها در طبیعت الگوریتم زنبورها را پیشنهاد می کنند زنبورها در طبیعتالگوریتم زنبور عسل
اسلاید 11: زنبورها در طبیعت گلها با گردافشانی و شهد کمتر که باتلاش کمتری قابل جمع اوری هستند توسط زنبورهای بیشتری بازدید می شوند در حالی که گلها با شهد کمتر تعداد زنبور کمتری در اطراف خود جمع می کنند.
اسلاید 12: زنبورها در طبیعتزنبورهای دیده بان به صورت رندوم از گلزاری به گلزار دیگر حرکت می کنند.
اسلاید 13: زنبورها در طبیعتزنبورهایی که به کندو بازمی گردند براساس معیار مشخصی گلزارهای مختلف را ارزیابی می کنند.(ارزیابی بر اساس ترکیبی از معیارها از قبیل میزان شکر و ...)
اسلاید 14: زنبورها در طبیعتهر کندو دارای مکانی به نام سالن رقص می باشد
اسلاید 15: زنبورها در طبیعتزنبورها از طریق این رقص پیام های زیر را دریافت می کنند :مسیر گلزارهافاصله از کندو رتبه بندی کیفیت برازندگی این اطلاعات زنبورهای پیرو را به سمت گلزار می فرستد.
اسلاید 16: زنبورها در طبیعتبیشتر زنبورهای پیرو به دنبال زنبور رقصنده به سمت گلزارهایی می روند که امید بیشتری برlی یافتن نکتار در گروه انها وجود دارد.وقتی زنبورها به سمت ناحیه ای مشابه بروند دوباره به صورت رندوم در گلزار پراکنده می شوند و دوباره به هنگام بازگشت به کندو رقص چرخشی انجام می دهند وبدین ترتیب زنبورهای بیشتری را با خود همراه می کنند.بیشتر زنبورها به گلزارهایی با میزان نکتار بیشتر می روند.
اسلاید 17: زنبورها در طبیعتبنابراین بر اساس برازندگی گلزار می تواند مملو از زنبور یا متروک گردد.
اسلاید 18: الگویتم زنبورها(BA) )(Lousich and Teodorovich)الگوریتم زنبورها الهام گرفته از زنبورها در طبیعت است.
اسلاید 19: مراحل الگوریتم مقداردهی اولیه جمعیتارزیابی برازندگی جمعیت while (هنگامی که به شرط توقف نرسیده ایم) شکل دهی جمعیت جدیدانتخاب مکان هایی جهت جستجوی همسایگی فرستادن زنبورها به سمت مکان های انتخاب شده و ارزیابی برازندگی انتخاب شایسته ترین زنبور هر گلزار فرستادن زنبورهای باقیمانده جهت جستجوی تصادفی وارزیابی برازندگی انهاEnd while
اسلاید 20: پارامترهای الگوریتم BAالگوریتم BA برای اجرا به یک سری پارامتر نیاز دارد که عبارت اند از :تعداد زنبورهای دیده بان nتعداد مکان های انتخاب شده mتعداد مکان های برگزیده e تعداد زنبورهای فرستاده شده به بهترین مکانnep یاn2تعداد زنبورهای فرستاده شده به m-e مکان دیگرnsp یاn1اندازه اولیه گلزارها ngh که شامل مکان و همسایگی ان است تعداد تکرار مراحل الگوریتمi max
اسلاید 21: فلوچارت الگوریتم زنبورها21Evaluate the Fitness of the Population Determine the Size of Neighbourhood(Patch Size ngh)Recruit Bees for Selected Sites(more Bees for the Best e Sites) Select the Fittest Bee from Each SiteAssign the (n–m) Remaining Bees to Random SearchNew Population of Scout Bees Select m Sites for Neighbourhood SearchNeighbourhood SearchInitialise a Population of n Scout Bees
اسلاید 22: توصیف مراحل الگوریتم1- الگوریتم با n زنبور دیده بان که به طور تصادفی در فضای جستجو قرار می گیرند شروع می شود (برای مثالn=100)2- برازندگی مکان های دیده شده به وسیله زنبورهای دیده بان بعد از برگشت در مرحله 2 ارزیابی می شود ارزیابی 100زنبور دیده بان در جدولی همانند جدول زیر ذخیره می شود. سپس جدول براساس ارزیابی از مقدار بزرگتر به کوچکتر مرتب می شود. 123456……...9910020%50%60%30%80%10%………35%72%
اسلاید 23: توصیف مراحل الگوریتم3- m مکان بهترین انتخاب می شوند(ارزش گذاری به m زنبور دیده بان ازn تا) (برای مثالm=10 ) سپس ما e مکان بهترین را به صورت تصادفی انتخاب می کنیم (زنبور دیده بان) از میان m تابه صورت تصادفی انتخاب می شوند.برای مثال e=2 پس m-e=10-2=8 1234567891080%78%75%72%69%66%65%60%59%58%
اسلاید 24: توصیف مراحل الگوریتم4- یک همسایگی مکان جستجو به وسعتngh انتخاب می شود،که برای update کردن m زنبور اظهار شده در مرحله قبل لازم است.
اسلاید 25: توصیف مراحل الگوریتم5-فرستادن زنبورها به مکان های انتخاب شده و ارزیابی برازندگی مکان ها تعداد n2 زنبور به صورت تصادفی انتخاب شده و به e مکان فرستاده می شوند.(n2=40 (تعداد n1 زنبور به صورت تصادفی انتخاب شده که تعداد انها از n2 کمتر است که به m-e مکان فرستاده شوند(n1=20)
اسلاید 26: توصیف مراحل الگوریتم6- انتخاب بهترین زنبور از هر مکان (بیشترین برازندگی)برای شکلدهی جمعیت بعدی این موضوع در طبیعت وجود ندارد .بهترین زنبور هر مکان ازm مکان به صورت زیر انتخاب می شود.اولین مکان انتخاب خواهد شد (برای مثال یک مکان از e مکان(جدول شامل n2=40 زنبور ساخته خواهد شد که ارزش هر زنبور مساوی ارزش زنبور دیده بان اصلی است با مقدار کمی تعدیل بسته به همسایگی ngh.
اسلاید 27: توصیف مراحل الگوریتماطلاعات از 40 زنبور گرفته شده و با تابع برازندگی ارزیابی می شود.نتایج در جدولی موقتی ذخیره خواهند شد .جدول مرتب شده و بهترین مقدار انتخاب می شود.مرحله6 برای m مکان تکرار می شود.در اخر ما بهترین زنبورها m=10 را خواهیم گرفت که در ابتدای جدول قرار می گیرند.(n=100)123…4082%81.2%79.9%…79.2%123456…1011…9910082%79%77%73%70%67%…58.2%
اسلاید 28: توصیف مراحل الگوریتم7- جمعیت اغازین جدید:زنبورهای باقیمانده در جمعیت باید به طور تصادفی به اطراف فضای جستجو فرستاده شوند (مقادیر از 11 تا100 در جدول قبلی) جمعیت جدید به صورت زیر است.123456…1011…9910082%79%77%73%70%67%…58.2%Random valuesRandom valuesRandom valuesRandom values
اسلاید 29: توصیف مراحل الگوریتم8- شمارنده حلقه افزایش می یابد مراحل 2 تا7 تا رسیدن به شرط توقف تکرار می شوند (انتهای شماره تکرارهاimax)(برای مثالimax=1000)در انتهای هر تکرار ،جمعیت 2 قسمت خواهد شد . نمایندگان هر جمعیت جدید از هر گلزار انتخاب شده و زنبورهای دیده بان دیگر برای انجام جستجوهای تصادفی ماموریت می یابند.
اسلاید 30: مثالی سادهمثال استفاده ازBA رابرای بدست اوردن بیشترین مقدار یک تابع ریاضی نشان می دهد.(بهینه تابعی) که این تابع از شبیه سازی بدست آمده است.
اسلاید 31: مثالی ساده31Graph 1. Initialise a Population of (n=10) Scout Bees with random Search and evaluate the fitness.xy**********1- اولین قدم شکلدهی جمعیت با10زنبور دیده بان با جستجوی تصادفی و ارزیابی مقدار برازندگی است.(n=10)
اسلاید 32: مثالی ساده2- ارزیابی برازندگی جمعیتجدولی از 10 مقدار ساخته می شود وبه صورت نزولی از بیشترین مقدارy به کمترین مقدار مرتب می شوند.
اسلاید 33: مثالی ساده33Graph 2. Select best (m=5) Sites for Neighbourhood Search: (e=2) elite bees “▪” and (m-e=3) other selected bees“▫”xy▪▫▪▫▫*****me3- m مکان بهترین انتخاب می شود (بهترین براورد m مکان از n مکان)(m=5,e=2,m-e=3)
اسلاید 34: مثالی ساده34xy▪▫▪▫▫Graph 3. Determine the Size of Neighbourhood (Patch Size ngh)4- انتخاب یک همسایگی مکان جستجو بسته به اندازهngh
اسلاید 35: 5- فرستادن تعداد بیشتری زنبور به مکانهای انتخاب شده و ارزیابی برازندگی مکان ها فرستادن زنبورها به مکان های e (مکان های مرغوب)و مکان های m-e (مکان های نامرغوب)n2=4 (مرغوب)n1=2 (نامرغوب)مثالی ساده35▪▫▪▫▫****Graph 4. Recruit Bees for Selected Sites (more Bees for the e=2 Elite Sites) *********** * * ** *
اسلاید 36: مثالی ساده6- انتخاب بهترین زنبورها از هر مکان (بیشترین برازندگی)برای شکل دهی جمعیت جدید 36xy▪▫▪▫▫****Graph 5. Select the Fittest Bee * from Each Site**********
اسلاید 37: مثالی ساده7- شکلدهی جمعیت جدید انتخاب 5 مقدار قدیمی و تخصیص مقادیر تصادفی به n-m مقدار باقی مانده37xy*Graph 6. Assign the (n–m) Remaining Bees to Random Search***o*oooome
اسلاید 38: مثالی ساده8- شمارنده حلقه افزایش می یابد ومراحل2 تا 7 تکرار می شود،تا زمانی که به شرط توقف برسیم (شماره تکرار پایانیimax )38xy*Graph 7. Find The Global Best point****
اسلاید 39: مساله زمان بندی یک ماشینتعریف مساله : یک تعداد از کارها باید بدون وقفه در یک ماشین انجام شود . همه مشاغل در زمان صفر در دسترس اند و هر کدام زمان اجرای خود را دارند (pi) و نیاز به دقیقا یک عملیات دارند .زودی کار : اگر زمان اتمام cj از کار j کوچکتر یا مساوی با موعد مقرر (سررسید)d آن باشد زودی کار برابر است باEj=d-cj
اسلاید 40: مساله زمان بندی یک ماشینتاخیر کار: اگر زمان اتمام cj از کار j بزرگتر ازموعد مقرر (سررسید)d آن باشد تاخیرکار برابر است باTj=cj-dهدف بدست آمده از شبیه سازی: پیدا کردن یک توالی s از n کار است به طوری که جمع جریمه زودی و تاخیر انجام یک کار را min کند.F(s) = (αj . Ej + βj . Tj)به طوری که α و β به ترتیب جریمه زودی و تاخیر در واحد زمان می باشند.
اسلاید 41: استفاده از BA در زمان بندی کار یک ماشینتعاریفهدف : تعیین برنامه زمان بندی کامل عملیات تعیین شده در مسالهمسیر : فرض می کنیم هر راه حل به عنوان یک مسیر از کندو به منبع تغذیه می باشد.ارزیابی پارامترها : زنبورها با بهترین makespan احتمال بیشتری برای اضافه کردن راه خود به لیست حل های برگزیده خواهند داشت .makespan : تفاوت زمان بین شروع و پایان یک توالی از عملیات(فاصله و شیرینی شهد)
اسلاید 42: 42
اسلاید 43: پارامترهای الگوریتمBAValueParametersParametersWhen the number of jobs n is less than 100, b = 2n . Otherwise, b = 400Populationb200Number of selected sitesm100Number of elite sitese6Initial patch sizengh50Number of bees around elite pointsnep30Number of bees around other selected pointsnsp
اسلاید 44: مساله زمان بندی یک ماشینd=round[SUM p*h]h=0.2,0.4,0.6,0.8(restrictive factor)Sum p= sum of processing time∆ avg=∑{[(FBA-Fref)/Fref]*100}/RFBA=fitness function value generated by the bees algoritmFref= fitness function value generated by Biskup and feldmanR=total number of run
اسلاید 45: Minimum deviation of the results45DPSO : Discrete Particle Swarm Optimization, TS : Tabu Search , GA : Genetic Algorithm, HTG : Tabu Search + Genetic Algorithm, HGT : Genetic Algorithm + Tabu Search, Bees : Bees Algorithm
اسلاید 46: برخی کاربردهای الگوریتم BAآموزش شبکه عصبی برای الگو شناسی زمان بندی کارها برای ماشین های تولیدی دسته بندی اطلاعات بهینه سازی طراحی اجزای مکانیکی بهینه سازی چند گانه میزان کردن کنترل کننده های منطق فازی برای ربات های ورزشکار
اسلاید 47: منابعZheng Jun, Tan Yu-An, Zhang Xue-” An improved dynamic structure-based neural networks determination approaches to simulation optimization problems”, Verlag London Limited 2010Pham DT, Ghanbarzadeh A. Multi-Objective Optimization using the Bees Algorithm, Proceedings of IPROMS 2007 ConferencePham DT, Muhamad Z, Mahmuddin M, Ghanbarzadeh A, Koc E, Otri S. Using the bees algorithm to optimise a support vector machine for wood defect classification. IPROMS 2007 Innovative Production Machines and Systems Virtual Conference, Cardiff, UK.Pham DT, Koc E, Ghanbarzadeh A, and Otri S. Optimization of the weights of multi-layered perceptrons using the Bees Algorithm, Proc 5th International Symposium on Intelligent Manufacturing Systems, Turkey, 2006.Pham DT, Soroka AJ, Koc E, Ghanbarzadeh A, and Otri S. Some applications of the Bees Algorithm in engineering design and manufacture, Proc Int. Conference on Manufacturing Automation (ICMA 2007), Singapore, 2007.Pham DT, Ghanbarzadeh A, Koc E, and Otri S. Application of the Bees Algorithm to the training of radial basis function networks for control chart pattern recognition, Proc 5th CIRP International Seminar on Intelligent Computation in Manufacturing Engineering (CIRP ICME 06), Ischia, Italy, 2006.Pham DT, Otri S, Ghanbarzadeh A, and Koc E. Application of the Bees Algorithm to the training of learning vector quantisation networks for control chart pattern recognition, Proc Information and Communication Technologies (ICTTA06), Syria, p. 1624-1629, 2006.Pham DT, Castellani M, and Ghanbarzadeh A. Preliminary design using the Bees Algorithm, Proc Eighth International Conference on Laser Metrology, CMM and Machine Tool Performance, LAMDAMAP, Euspen, UK, Cardiff, p. 420-429, 2007.47
اسلاید 48: Thanks for your attention48
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.