سیستم های بهینه سازی گروه ذرات (pso)

سیستم های بهینه سازی گروه ذرات (pso)

اسلاید 1: 1 انسان در طبیعت حقیقت را جستجو می کند و در خویشتن خوبی را

اسلاید 2: 2بررسي سيستم هاي بهينه‌سازي گروه ذرات(pso) استاد راهنما : جناب آقاي دكتر طباطبايي تهيه وتنظيم : 1- عبدالرضا شمس 2-حسين ابريشمي 3- سيده اكرم هاشمي

اسلاید 3: 3فهرستچكيده مقالهمقدمه - تعريف موضوع - تاريخچه توضيح الگوريتم psoكاربردهانتيجه گيري منابع

اسلاید 4: 4PSO Particle swarm Optimitation الگوریتم PSO یك الگوریتم جستجوی اجتماعی است كه از روی رفتار اجتماعی دسته‌های پرندگان مدل شده است. در ابتدا این الگوریتم به منظور كشف الگوهای حاكم بر پرواز همزمان پرندگان و تغییر ناگهانی مسیر آنها و تغییر شكل بهینه‌ی دسته به كار گرفته شد.

اسلاید 5: 5مثالهايي از pso در طبيعت :حركات جمعي پرندگانحركات دسته جمعي ماهيها كندوي زنبور عسلكلوني مورچه ها ant colonyخانه سازي موريانه ها گله هاي حيوانات تجمعات باكتريها

اسلاید 6: 6اساس كار PSO بر این اصل استوار است كه در هر لحظه هر particle مكان خود را در فضای جستجو با توجه به بهترین مكانی كه تا كنون در آن قرار گرفته است(p best) و بهترین مكانی كه در كلهمسایگی‌اش وجود دارد(g best) ، تنظیم می‌كند.

اسلاید 7: 7در PSO، particleها در فضای جستجو جاری می‌شوند. تغییر مكان particleها در فضای جستجو تحت تأثیر تجربه و دانش خودشان و همسایگانشان است. بنابراین موقعیت دیگر particleهای Swarm روی چگونگی جستجوی یك particle اثر می‌گذارد. نتیجه‌ی مدل‌سازی این رفتار اجتماعی فرایند جستجویی است كه particleها به سمت نواحی موفق میل می‌كنند. Particleها در Swarm از یكدیگر می‌آموزند و بر مبنای دانش بدست آمده به سمت بهترین همسایگان خود می‌روند.

اسلاید 8: 8Particle Swarm Optimization

اسلاید 9: 9بررسي رفتار پرندگان

اسلاید 10: 10بهينه‌سازي گروه ذرات )PSO(

اسلاید 11: 11تاريخچه pso

اسلاید 12: 12الگوريتم جامع پرندگان pso يك تكنيك بهينه سازي بر پايه قوانين احتمال مي باشد. كه ايده اوليه آن توسط راسل ابرهارت ( دانشمند علوم كامپيوتر ) و جيمز كندي ( روانشناس مسائل اجتماعي ) در سال 1995 ارائه شد . Russell EberhartJames Kennedy

اسلاید 13: 13اين الگوريتم ازرفتار اجتماعي پرندگان در حين جستجوي غذا براي هدايت مجموعه پرندگان به منطقه اميد بخش در فضاي جستجو استفاده مي كند. الگوريتم جامع پرندگان ذاتا يك الگوريتم بهينه سازي پيوسته است.

اسلاید 14: 14چند تعريف بهينه سازي روندي است براي يافتن و مقايسه کردن راه حلهاي ممکن تا وقتي که پاسخ بهتري پيدا نشود.پاسخ خوب يا بد با توجه به هدفي يا اهدافي مشخص تعيين مي شود.

اسلاید 15: 15روشهاي بهينه سازي جمعيتيالگوريتمهايي هستند که عموما با تقليد از طبيعت وحرکات گروهي حيوانات PSO و .... طراحي و ايجاد مي شوند .به لحاظ گوناگوني روشهاي جستجو و بهينه سازي از روشهاي کلاسيک بهترند!

اسلاید 16: 16ايدة پايه:هر ذره در حال جستجو براي نقطة بهينه است.هر ذره در حال جابجايي است (در غير اينصورت نمي‌تواند جستجو كند!)به دليل اين جابجايي، داراي سرعت است.هر ذره در هر مرحله، موقعيتي را كه بهترين نتيجه را در آن داشته به خاطر مي‌سپارد. (بهترين موقعيت فردي هر ذره)دلايل فوق بتنهايي خيلي خوب نيستند. ذرات به اين كمك احتياج دارند كه بدانند در كجا به جستجو بپردازند.

اسلاید 17: 17ايدة پايه :ذرات در گروه ذرات با هم همياري مي‌كنند. ذرات اطلاعاتي كه دربارة موقعيتي كه در آن هستند را با هم تبادل مي‌كنند.اين همياري بايد خيلي ساده باشد. همياري در PSO پايه بشكل زير مي‌باشد: - يك ذره داراي همسايگيهاي منتسب به خودش است.- يك ذره تطابق ذراتي را كه در همسايگيش هستند، مي‌داند و از موقعيت ذره‌اي كه بهترين تطابق را دارد استفاده مي‌كند (بهترين موقعيت سراسري).- از اين موقعيت بسادگي براي تنظيم سرعت ذره استفاده مي‌شود.

اسلاید 18: 18ويژگيها و كاربردها:مزايا:يك روش مرتبة صفر است و نيازي به عمليات سنگين رياضي مثل گراديان‌گيري احتياج ندارد.يك روش مبتني بر جمعيت است. از مشاركت ذرات استفاده مي‌كند.كاربردها:آموزش شبكه عصبيبهينه‌سازي تابعبازشناسي الگو

اسلاید 19: 19مثال ساده از مشخصه‌هاي اين الگوريتم و ويژگي مشاركت:

اسلاید 20: 20مقداردهي اولية موقعيتها و سرعتها:

اسلاید 21: 21گام 2: ارزيابي تابع تطابق و تعيين بهترين موقعيتها1- تطبيق هر كدام از ذرات را ارزيابي مي‌كنيم.2- بهترين راه‌حل هر كدام از ذرات را با تطابق فعليشان مقايسه مي‌كنيم و برابر با موقعيت بهتر قرار مي‌دهيم.3-بهترين راه‌حل سراسري در كل ذرات را حساب مي‌كنيم.

اسلاید 22: 22گام 3: بروزرساني موقعيتها و سرعتهابررسي شرط پايان: اگر 1- به مينيمم خطا برسيم. 2- حداكثر دفعات اجراي الگوريتم به پايان برسد. 3- در چند تكرار مشخص تابع تطابق تغيير نكند.آنگاه الگوريتم به پايان مي‌رسد.در غير اينصورت به گام 2 برو.

اسلاید 23: 23بهينه‌سازي الگوريتمهاي دوبعدي مبتني بر آنتروپي از لحاظ سرعت اجرا: از الگوريتم بهينه‌سازي PSO استفاده مي‌كنيم. سه نكتة مهم را بايد در نظر بگيريم:تابع معيار چيست؟تعداد ذرات چقدر باشد؟ابعاد مسئله چقدر است؟

اسلاید 24: 24يك ذره چه كارهايي را انجام مي‌دهد؟يك ذره در هر مرحلة زماني (Timestep) بايد به يك موقعيت جديد جابجا شود. اين جابجايي با تنظيم سرعت ذره انجام مي‌شود. تنظيم سرعت بقرار زير است:- سرعت فعليبعلاوة- سهم وزن‌يافتة تصادفي در جهت بهترين موقعيت منفرد هر ذرهبعلاوة- سهم وزن‌يافتة تصادفي در جهت بهترين موقعيت موجود در همسايگي ذرهتنظيم موقعيت بشكل زير است:مقدار قديمي موقعيتبعلاوة- سرعت جديد

اسلاید 25: 25بهترين تجربهحرکت ذره در راستاي بهترين تجربه کل جمعيتبهترين کليحرکت ذره در راستاي بهترين تجربه خودحرکت ذره در راستاي قبليحرکت جديدچگونگي حرکات ذرات ؟

اسلاید 26: 26همسايگان179568432

اسلاید 27: 27همسايگيها:geographicalsocial

اسلاید 28: 28همسايگيها:Global

اسلاید 29: 29همسايگيهاي دايره‌اي:دايرة مجازي15764382همسايگيهاي ذرة 1

اسلاید 30: 30Particles Adjust their positions according to a ``Psychosocial compromise’’ between what an individual is comfortable with, and what society reckonsمن در اينجا هستم!بهترين موقعيت همساية منبهترين موقعيت منفردxpgpivi-proximityg-proximity

اسلاید 31: 31شبه-كد كامپيوتري:Equation (a)v[] = c0 *v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) در روش اصلي c1=1 است ولي در بسياري از الگوريتمهاي مطرح شده اين مقدار را ثابت نمي‌گيرند و آنرا تغيير مي‌دهند.Equation (b)present[] = present[] + v[] http://www.swarmintelligence.org/tutorials.phpاثر حافظة ذرهاثر گروه ذراتجابجايي فعلي

اسلاید 32: 32 For each particle     Initialize particle END Do     For each particle         Calculate fitness value         If the fitness value is better than its peronal best             set current value as the new pBest     End     Choose the particle with the best fitness value of all as gBest     For each particle         Calculate particle velocity according equation (a)         Update particle position according equation (b)     End While maximum iterations or minimum error criteria is not attained شبه‌-كد كامپيوتري:http://www.swarmintelligence.org/tutorials.php

اسلاید 33: 33سرعت ذرات در هر بعد را به Vmax محدود مي‌كنيم. بدين معني كه اگر سرعت در يك جهت بخواهد از اين مقدار بيشتر شود، آنگاه سرعت در آن بعد به Vmax محدود مي‌شود.دليل: از جابجايي سريع ذرات در فضاي جستجو مي‌توانيم جلوگيري كنيم. شبه-كد كامپيوتري:http://www.swarmintelligence.org/tutorials.php

اسلاید 34: 34نحوة پايان الگوريتم:1- اجراي تعداد ماكزيمم دفعاتي كه براي اجراي الگوريتم در نظر گرفته شده است.2- عدم تغيير مقدار تابع تطابق در تعداد معيني تكرار پشت سر هم.3- كاهش ميزان خطا از يك حد معين.

اسلاید 35: 35الگوريتم پايه:for each particleبروزرساني سرعتthen moveAt each time step tمقادير تصادفي در داخل حلقهبروزرساني موقعيت

اسلاید 36: 36پارامترها:تعداد ذراتC1 (اهميت مربوط به بهترين هر ذره)C1 (importance of personal best)C2 (اهميت مربوط به بهترين همسايگيها)C2 (importance of neighbourhood best) Vmax

اسلاید 37: 37پارامترها را چگونه انتخاب بكنيم؟The right wayاين راه ...Or this way

اسلاید 38: 38پارامترها:تعداد ذراتنشان داده شده است كه 10-50 معمولاً كافي مي‌باشد.C1 (اهميت مربوط به بهترين هر ذره)C2 (اهميت مربوط به بهترين همسايگيها)معمولاً C1+C2 = 4. فقط بدلايل تجربي انتخاب شده است. Vmax: خيلي كم- سرعت پايين خيلي زياد- ناپايدار

اسلاید 39: 39مثال:

اسلاید 40: 40مثال:

اسلاید 41: 41تعيين تطبيقي تعداد ذرات:There has been enough improvementbut there has been not enough improvementalthough Im the worstIm the bestI try to kill myselfI try to generate a new particle

اسلاید 42: 42ضرايب تطبيقي:هر چقدر من بهتر باشم، بيشتر مسير خودم را دنبال مي‌كنم.اگر همساية من بهتر باشد، بسمت همساية خودم تمايل پيدا مي‌كنم.avrand(0…b)(p-x)

اسلاید 43: 43الگوریتم بهینه سازی کولونی مورچه هاANT COLONY OPTIMIZATION ALGORITHM

اسلاید 44: 44شما می دانید؟!مورچه ها موجوداتی کور، بی حافظه و بسیار کم هوشند هستند!مورچه ها نمی خوابند!مورچه ها می توانند تا 50 برابر وزن خود را تحمل کنند!حس بویایی مورچه با سگ برابر است!

اسلاید 45: 45الگوریتم های جستجوالگوريتم های جستجوی رندومالگوریتم های جستجوی همه جانبهالگوريتمهاي هيوريستيک

اسلاید 46: 46الگوریتم های هیوریستیک (شهودی):الگوريتم هاي تکاملي با الهام از علم ژنتيک و تکاملشبکه هاي عصبي با الهام ازعملکرد سلولهاي مغزسيستم هاي فازي بر پايه قوانين زباني انسانالگوریتم بهینه سازی به کمک کولونی مورچه ها(ACO)تکنيک هايي با الهام از قوانين فيزيکي و بيولوژيکي

اسلاید 47: 47هوش جمعی (swarm Intelligence)جمعیتی از اعضا عمل ساده ای را انجام می دهند ولی در نهایت تمام گروه مسئله پیچیده ای را حل می کنند.اين نوع هوشمندی هيچ نيازی به کنترل مرکزی و ديد کلی نسبت به سيستم ندارد بعبارت دیگر اين تعاملات غالبا غريزی بوده و بدون نظارت انجام می گيرندنمونه بارز این هوشمندی در رفتار حشراتی که بصورت کولونی زندگی می کنند، دیده می شود

اسلاید 48: 48خود سازمانده بودن (self organization)خانه سازی زنبور خانه سازی موریانه هاجستجوی غذا

اسلاید 49: 49خانه سازی موریانه هارفتار سوم: اتصال ستون ها به یکدیگر رفتار اول: حرکت تصادفی در محیط ساختن گلوله های خاکیرفتار دوم: تبدیل گلوله های خاک به ستون

اسلاید 50: 50خانه ای بدون نقشه قبلی و بدون نظارت یک مغز مرکزی

اسلاید 51: 51جستجوی غذا ((forage for food رفتار اول: رد پای فرمونیرفتار دوم: جستجوی مسیر با فرمون بیشتر

اسلاید 52: 52مسیر یابی مورچه ها

اسلاید 53: 53

اسلاید 54: 54بررسی عملکرد مورچهجستجوی رندوم در فضا :فیدبک مثبت :فیدبک منفی :هماهنگی :احتمال گمشدن مورچهاحتمال یافتن مسیری بهینه تر از مسیر فعلیدنبال کردن رد پای فرمونیتقویت مسیر های بهینه ترتبخیر رد پا هاپوشش تغییر عوامل محیطیانتقال اطلاعات مسیرهماهنگی در یافتن مسیر بهینه

اسلاید 55: 55الگوریتم بهینه سازی کولونی مورچه ها(ACO)نسخه اولیه ACO در سال 1991 توسط دوریگو تحت عنوان سیستم مورچه معرفی شدشبیه سازی رفتار مورچه ها ی طبیعت در مورچه های مصنوعی

اسلاید 56: 56شکل کلی مسائل قابل حل با ACOs: مجموعه جوابهای مسئلهF(s,t): تابع هزینه که باید کمینه شودΩ: مجموعه قیود مسئلهالگوریتم جستجوی ما باید در فضای مسئله (s) به دنبال جواب مناسبی بگردد که به ازای آن تابع هزینه F(s,t) کمینه شود ضمن اینکه مجموعه محدودیتهایی مثل Ω نیز به مسئله اعمالشده باشد

اسلاید 57: 571- تبدیل مسئله به پارامتر های عددی :معمولا مسائل به صورت گراف در نظر گرفته می شوند که هر یال آن دارای دو مشخصه است: میزان رد پای موجود در یال مقدار هیوریستیک یال که اغلب در ارتباط با تابع هزینه است

اسلاید 58: 582- در نظر گرفتن چند مورچه مصنوعی:  یک کولونی شامل M مورچه در نظر گرفته می شود که مانند مورچه های واقعی دو رفتار را از خود نشان می دهند:می توانند با گذشتن از هر یال به آن ردپا اضافه کننددر انتخاب مسیر، مسیر های دارای ردپای بیشتر را ترجیح می دهند در سه مورد با مورچه های واقعی تفاوت دارند:کاملا کور نیستند و بینایی مسئله را تشخیص می دهندحافظه کوچکی دارندکه آنها را قادر می سازد اطلاعات مربوط به مسیر خود را تا مدت کوتاهی نگه دارنددر محیطی با زمان گسسته زندگی می کنند و در طول مسیر مشاهده نمی شوند

اسلاید 59: 593- جایابی اولیه برای مورچه ها :M مورچه به صورت رندوم روی N گره گراف توزیع می شوند و تا آخرین مرحله مورچه ای از دست نمی دهیم و مورچه ای هم اضافه نمی کنیم

اسلاید 60: 604- حرکت بین گره ها و جستجوی گراف: مورچه ها برای دستیابی به جواب بهینه بین گره ها حرکت می کنند اگر به جابجایی مورچه از گره i به j یک قدم بگوییم، با تکرار چند حرکت پیاپی، سفر مورچه کامل می شود. هر سفر مورچه یک جواب از مسئله است و با اتمام سفر هر M مورچه یک سیکل پایان می یابد مورچه ها بکمک حافظه شان ارزیابی شده و ردپاها بروزرسانی می شوندسیکل بعدی با ردپاهای جدید انجام می شوداین سیکلها تا پیش آمدن شرایط توقف و رسیدن به جواب شبه بهینه تکرار می شود

اسلاید 61: 61هدایت الگوریتم بسمت جواب بهینهقوانین احتمالی حرکت: توابع احتمالی که مورچه ها طبق آن روی یالهای گراف حرکت تصادفی دارندقوانین بروز رسانی رد پاها: قوانینی که بعد از زمان مشخصی ردپای مسیرها را برای حرکات بعدی عوض می کند

اسلاید 62: 62 ملاک توقف)Stopping Criterion(بعد از تکرار های مشخص، الگوریتم زمانی متوقف شود که حدس بزنیم جواب مناسبی را پیشنهاد می کندزمانی که وضعیت رکود پیش آمده باشد

اسلاید 63: 63انواع مسائل قابل حل با ACOTeraveling Salseman problemGraph ColoringNetwork Routing

اسلاید 64: 64 T=T+1سفر مورچه ها تمام شده ؟بروز کردن ردپاهاشرایط توقف سیکل ها پیش آمده؟بهترین سفر را به خروجی بدهپایانحافظه مورچه ها را پاک کنNc=Nc+1NONOYESYESشروعT=0 شمارنده زمانمورچه ها بصورت رندوم در شهر ها قرار می گیرندهر مورچه شهر بعد را طبق تابع P انتخاب می کندNc=1 شمارنده سیکلهر مورچه در شهری که انتخاب کرده قرار می گیرد طول سفر هر مورچه را محاسبه می کنیم

اسلاید 65: 65کاربردها:1- طراحي بهينه حجم مخزن 2- طراحی مدارات الکترونیکی3- بهينه سازي شكل گنبدهاي فضاكار يك لايه 4- حل مسئله فروشنده دوره گردTSP 5- مسير يابي شبكه هاي كامپيوتري ANTNET

اسلاید 66: 66کاربردها-1 1- امروزه جهت استفاده بهينه از منابع آب موجود در يك حوزه و يا اقتصادي تر نمودن ابعاد سدها بطور قابل ملاحظه اي از مدلهاي بهينه ساز استفاده مي گردد. در اين موارد می توان ازالگوريتم PSO جهت طراحي بهينه حجم مخزن، براي تامين مطمئن نياز آبي استفاده نمود. الگوريتم PSO در واقع براي بهينه سازي مسائل پيوسته توسعه يافته و در آن راه حل بهينه مسئله از طريق اثر متقابل بين تعداد زيادي جزء (Particle) بدست مي آيد. همچنين براي در ك بهتر از كاربرد اين روش، حجم مخزن سد دز جهت تامين مطمئن نياز ماهيانه در پايين دست سد ، بكار گرفته شده است. نتايج حاصله از مقايسه اي جوابهاي اين الگوريتم و روش بهينه سازي خطي نشان دهنده كارآمدي اين الگوريتم در رسيدن به راه جوابهاي بهينه براي طراحي بهينه مخازن سدها مي باشد.

اسلاید 67: 67کاربردها-2با توجه به اينكه در طراحي مدارات الكترونيكي به علت وجود محدوديت در روال طراحي مجبوريم از مدارات و مدلهاي تقريبي براي المانهاي مختلف استفاده كنيم كه اين موضوع در مدارات پيچيده ، بسيار بزرگ و چند طبقه ايجاد مشكل مي كند ، در اين حالت دست يافتن به ابزاري كه به كمك آن بدون نياز به اطلاعات خيلي خاص و پيچيده بتوان به طراحي مناسبي براي يك مدار رسيد ايده آل است كه يكي از روشهاي نوين الهام گرفته شده از طبيعت روش psoمي باشد.

اسلاید 68: 68كاربردها-3سازه هاي فضاكار يكي از رايج ترين آنها سازه هاي سه بعدي مي باشند . آناليز و طراحي اين سازه ها براي پوشش سقف با دهانه هاي بزرگ از جمله استاديومهاي ورزشي – نمايشگاههاي تجاري – مراكز تفريحي و ... استفاده مي شود. زيرا پوشش اين سقفها بدون استفاده از ستونهاي داخلي ضروري مي باشد. در گنبدهاي فضا كار يك لايه بهترين فرم معادله منحني گنبد و موقعيت قرار گيري هر مدار گنبد مسئله مهم براي طراحان سازه است كه به علت وابسته بودن اين متغيرها به يكديگر به راحتي نمي توان ساختار مناسبي براي شكل گنبدها مشخص كرد.در اين جا با استفاده از الگوريتم pso مي توان بهينه ترين درجه معادله منحني و مختصات گره هاي هر مدار را جهت طراحي گنبد تعيين نمود.

اسلاید 69: 69نتيجه گيري : سيستمهاي بسياري در طبيعت وجوددارند كه از تعدادي عوامل غير هوشمند و يا هوش اندك تشكيل شده اند . علي رغم وجود يك ساختار كنترلي متمركز ، تعاملات ساده ميان عوامل باعث به وجود آمدن نوعي رفتار جمعي هوشمندانه مي گردد. با الهام از اين سيستمها روشهايي براي حل مسايل بهينه سازي تركيبي ابداع و در بسياري از موارد با موفقيت به كار گرفته شده اند از جمله حل مسئله فروشنده دوره گرد TSP و مسير يابي شبكه هاي كامپيوتري و ... نام برد.

اسلاید 70: 70مراجع: Kennedy, J. and Eberhart, R., “Particle Swarm Optimization,” Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia 1995, pp. 1942-1945. Venter, G. and Sobieski, J., “Particle Swarm Optimization,” Structural Dynamics, and Materials Conference, Denver, CO., April 2002.Kennedy, J. and Eberhart, R., Swarm Intelligence, Academic Press, 1st ed., San Diego, CA, 2001.

اسلاید 71: 71مراجع:[1] P.Tarasewich, and P.R.McMullen, Swarm intelligence: power in numbers., Appears in communication of ACM, Agust 2002, 45(8), 62-67.[2] M.Dorigo, V.Maniezzo, and A.Colorni, The Ant System: optimization by a colony of cooperating agents., IEEE Transaction on systems, Man, and Cyberneticspart B, vol. 26, no.1, 1996, pp. 1-13.[3] M.Dorigo, and G.D.Caro, Ant colony optimization: A new metaheuristic., Proceedings of the evolutionary computation, Washington DC, pp. 1470-1477,july 1999.

اسلاید 72: 72بکوش تا عظمت در نگاه تو باشد نه در آنچه به آن می نگری