آموزش رایگان کدنویسی الگوریتم pso در متلب (MATLAB)

در این ویدیو به آموزش کدنویسی الگوریتم بهینه سازی ازدحام ذرات (PSO) در متلب (MATLAB) پرداخته می شود. در ادامه میتوانید این ویدیو را به رایگان دانلود کنید. در انتها نیز کدهای متلب الگوریتم pso قرار داده شده است. این الگوریتم جزء الگوریتم های فراابتکاری می باشد و با يك ماتريس جمعیت تصادفی اولیه، شروع می شود در واقع الگوريتم PSO از تعداد مشخصی از ذرات تشكیل می شود كه به طور تصادفی، مقدار اولیه می گیرند.

دانلود کدهای متلب

مقدمه

بهینه سازی تکراری، یکی از قدیمی ترین انواع بهینه سازی است. روش کار این نوع از روش های بهینه سازی را می توان در چند کلمه خلاصه کرد، بهبود وضعیت قبلی تا رسیدن به نقطه ی بهینه با مقدار خطای قابل قبول. بنابراین طرح های مختلفی را برای این نوع از روش ها می توان ایجاد کرد و این ماندگاری به بهبود وضعیت تا رسیدن به خطای قابل قبول باعث شده است تا دامنه ی وسیعی از مسائل را بتوان بر اساس این روش ها حل کرد. چنین روش های تکراری را می توانیم به سادگی در دنیای اطرافمان و مخصوصا طبیعت به چشم ببینیم. ازین رو می توان از روش های مختلف ریاضی برای بهینه سازی مسائل مختلف، روش ها و رفتارهای مختلف زیستی و ایده های ادامه یک نسل برای فهم این روش ها الگو برداری کرد. بر اساس این مدل ها، هر عضو یک نسل شباهت رفتار را به الگوهای اولیه تشخیص می دهد و باقی اعضای نسل بر اساس آن و شبیه به آن رفتارهای خود را الگو برداری می کنند. در جنبه ی اول تشخیص پارامترهایی که برتری هر عضو نسل را در بهبود و تغییر سریع الگوهای رفتاری خود نسبت به حالات رفتاری گذشته اش را مشخص می کند، ضروری به نظر می رسد. اگر هدف به سمت بهینه ترین و بهترین مسیر ادامه نسل نزدیک شده باشد، به تمامی اعضای نسل اطلاعات مربوط به آن مسیر داده می شود و تمامی اعضای نسل مسیر خود را با رفتن به سمت آن مسیر بهینه الگو برداری می کنند. به عنوان مثال کوتاه ترین مسیر برای رسیدن به هدف که میتواند تولید یک نسل سازگارتر با شرایطی خاص باشد، می تواند یکی از پارامترهای مشخص کننده برتری رفتار یک نسل به رفتار نسل دیگر باشد. واضح است که با انجام این نوع از الگوهای رفتاری امکان رفتن و حرکت کردن اعضای یک نسل به سمت یک مکان بهینه ی محلی و در نتیجه دور شدن از بهینه ترین مکان موجود وجود دارد. برای از بین بردن این وضعیت و رها شدن از این محدودیت به وجود آمده، نیازمند کمک گرفتن از مفهومی تازه به نام جابجایی ذرات هستیم و همچنین اجازه دادن به تکرار این وضعیت تا مدتی طولانی و هماهنگ شدن نهایی تمام ذرات و رسیدن به بهینه ترین و ایده آل ترین مکان برای هدف در نظر گرفته شده. تا زمانی که این رفتار به صورت دسته جمعی و به صورت مداوم تکرار می شود می توان گفت که روند حرکتی نسل در نظر گرفته شده نسبتا صحیح و ایمن است. در این نوع از الگوهای گفته شده قدرت به خاطر سپردن بهترین الگوی رفتاری برای هر فرد یا ذره از یک نسل انتخاب شده برای بهبود وضعیت فعلی خود آن فرد یا ذره به بهترین و بهینه ترین حالت الزامی است.

الگوریتم PSO با یک ماتریس جمعیت تصادفی اولیه، شروع می شود، شبیه بسیاری دیگر از الگوریتم های تکاملی همچون الگوریتم ژنتیک است. برخلاف الگوریتم ژنتیک هیچ عملگر تکاملی همانند جهش ده ندارد. هر عنصر جمعیت، یک زره نامیده می شود است. در واقع الگوریتم PSO از تعداد مشخصی از ذرات تشکیل می شود که به طور تصادفی، مقدار اولیه می گیرند. برای هر ذره رو مقدار وضعیت و سرعت، تعریف می شود که به ترتیب با یک بردار مکان و یک بردار سرعت، مدل می شوند. این رات، بصورت تکرار شونده ای در فضای n بعدی مسئله حرکت می کند تا با محاسبه مقدار بوینکی به عنوان یک ملاك سنجش، گزینه های ممکن جدید را جستبو کنند. بعد فضای مسئله، برابر تعداد پارامترهای موجود در تابع مورد نظر برای بهینه سازی می باشد. یک حافظه به زخيره بهترین موقعیت هر ذره در گذشته و یک حافظه به زخيره بهترین موقعیت پیش آمده در میان همه ذرات، اختصاص می یابد. با تجربه حاصل از این حافظه ها, ذرات تصمیم می گیرند که در نوبت بعدی، چگونه حرکت کنند. در هر بار تکرار، همه ذرات در فضای n بعدی مسئله حرکت می کنند تا بالاخره نقطه بعينه عام، پیرا شود. ذرات، سرعت هایشان و موقعیت شان را بر حسب بهترین جواب های مطلق و محلی به روز می کنند.

چارچوب کلی الگوریتم PSO

PSO یک الگوریتم تکاملی است که با جواب های تصادفی شروع شده و در بین جوابهای تولیدی جستجو را ادامه می دهد. هر جواب بالقوه ذره نامیده می شود. ذرات در فضای جواب مساله با یک سرعت پویا که برگرفته از تجربه خود ذره و تجربه هم قطارها می باشد، حرکت می کنند. الگوریتم PSO بر خلاف الگوریتمهای تکاملی دیگر، از عملگرهای صافی مانند تقاطع در الگوریتم قورباغه) استفاده نمی کند. در این روش جواب ها در فضای جستجو باقی می مانند تا اطلاعات آنها به اشتراک گذاشته شود و جستجو را به سمت بهترین موقعیت در فضای جواب هدایت کنند. برای به روز رسانی سرعت و موقعیت ذرات، در ابتدا باید بهترین موقعیت هر ذره و بهترین موقعیت در بین کل ذرات در هر مرحله، بهروز شود. فلوچارت PSO در شکل زیر نشان داده شده است. در شکل مذکور p – best، بهترین جواب از لحاظ شایستگی است که تاکنون برای هر ذره به طور جداگانه به دست آمده است و g- best، بهترین مقداری است که تا کنون توسط تمام ذره ها در میان جمعیت به دست آمده است.

مراحل الگوریتم استاندارد PSO که در شکل بالا آمده است به شرح زیر می باشد:

1. از جمعیت اولیه به صورت تصادفی تشکیل می شود.
2. شایستگی ذرات به وسیله تابع برازندگی مشخص می شود.
3. موقعیت ذره با بهترین موقعیتی که ذره قبلا داشته است (p-best)، مقایسه شده و در صورت برتری بر p-best ، جایگزین آن می شود.
4. بهترین ذره در بین کل جمعیت مشخص شده و در صورت برتری بر g-best ، جایگزین آن می شود.
5. سرعت ذره به وسیله فرمولی مشخص به روز میشود.
6. موقعیت ذره نیز به وسیله فرمولی مشخص به روز می شود.
7. در صورت برآورده نشدن شرط توقف به مرحله ۲ میرویم در غیر این صورت بهترین ذره در تکرار نهایی به عنوان جواب الگوریتم ذخیره می گردد.

به منظور به روز رسانی سرعت و موقعیت ذرات لازم است چگونگی ارتباط میان آنها مدل شود. الگوهای مختلفی در این رابطه ارائه شده که در ادامه به مهمترین آنها اشاره می شود. دو مدل کلی برای الگوریتم PSO وجود دارد که مدل بهترین جهان و مدل بهترین همسایگی نام دارند. تفاوت بین این دو مدل در مجموعه ذراتی است که هر ذره با آنها تبادل اطلاعات می کند.

مدل بهترین جهان

در مدل بهترین جهان همه ذرات با یکدیگر در ارتباط هستند و در اجرای الگوریتم فقط یک جواب به عنوان بهترین جواب ذخیره می شود. در این مدل بهترین ذره مانند یک جاذب عمل می کند و بقیه ذرات را به سمت خود متمایل می سازد. بنابراین اگر این ذره به روز نشود الگوریتم به یک همگرایی زودرس و نابهنگام دچار می شود.

مدل بهترین همسایگی

در مدل بهترین همسایگی برای جلوگیری از همگرایی زودرس از چند جاذب استفاده می شود. برای هر ذره، یک زیر مجموعه از ذرات در نظر گرفته میشود که همسایگان ذره نامیده میشوند. به عبارت دیگر توپولوژی همسایگی ذرات به یکی از صورت هایی است که در بخش بعد اشاره می شود. در این مدل برای هر ذره، به جای بهترین جواب در بین کل جواب ها، | از مفهوم بهترین همسایه استفاده می کنیم. این بهترین جواب از بین همسایگان ذره انتخاب شده و g-best نامیده میشود. اجرای این روش، با گسترش اطلاعات مربوط به موقعیتهای خوب، به سایر ذرات کمک می کند. اگر توپولوژی مورد استفاده، توپولوژی ستاره باشد، مدل بهترین همسایگی به مدل بهترین جهان تبدیل میشود. مسلما هر چه تعداد همسایه های یک ذره کمتر باشد، سرعت همگرایی کمتر خواهد شد اما احتمال افتادن در دام حداقل محلی کم می شود.

انواع توپولوژی

نتایج ارائه شده توسط کندی نشان دهنده تاثیر مهم توپولوژی در نتایج الگوریتم های فراابتکاری است. اما توپولوژی بهینه وابسته به نوع مساله است. توپولوژی در واقع ساختار یک شبکه را به صورت نمادین آشکار می سازد و به درک ما از نحوه ارتباط ذرات کمک می کند.

توپولوژی ستاره

در این توپولوژی هر ذره می تواند با سایر ذرات موجود در جمعیت ارتباط داشته باشد. توپولوژی مربوط به الگوریتم PSO استاندارد، یک توپولوژی ستاره است. این توپولوژی برای مساله هایی که بهينه محلی ندارند بسیار کارا می باشد، اما برای مساله هایی با بهینه های محلی متعدد، در پیدا کردن جواب بهینه مشکل دارد زیرا در این حالت همه ذرات تحت تاثیر یک ذره هستند و احتمال توقف در یک حداقل محلی، زیاد است. شکل زیر توپولوژی ستاره را نشان می دهد.

توپولوژی حلقه

در این حالت هر ذر دارای دو همسایگی است. به عنوان مثال ذره 1+i همسایه دو ذره 1 و 2 +i است. بنابراین همه ذرات به طور غیر مستقیم تبادل اطلاعات می کنند. مسیر طولانی نسبی بین دو ذره i و 2i تبادل اطلاعات بین آنها را کاهش می دهد. این باعث میشود آنها به ناحیه های متفاوتی از فضای جستجو بروند، زیرا همه ذرات تحت تاثیر یک ذره نیستند. اما در این توپولوژی سرعت همگرایی کاهش پیدا می کند.

توپولوژی چرخ

توپولوژی بعدی که توسط کندی مورد بررسی قرار گرفت توپولوژی چرخی نام دارد که در آن همه ذرات فقط به یک ذره به نام دره کانونی متصل هستند. ذره کانونی موقعیت خود را به سمت بهترین ذره تنظیم می کند و اگر این تنظیم بهبودی ایجاد کند، آن را به بقیه ذرات اطلاع میدهد.

الگوریتم PSO بر اساس رفتار اجتماعی

در بخش قبل انواع الگوریتم PSO بر اساس توپولوژی همسایگی ذرات بیان شد. در این بخش به معرفی مدل های الگوریتم PSO بر اساس نوع رفتار یک ذره با سایر ذرات و نحوه اعتماد به جمعیت و اعتماد به خود می پردازیم.

مدل اعتماد فردی

در مدل اعتماد فردی، یک ذره برای به روز کردن سرعت خود، فقط به تجربه های خودش بسنده می کند. کندی با آزمایش این حالت از PSO متوجه شد که نسبت به حالت استاندارد کارایی ضعیفی دارد. یکی از دلایل ضعف این مدل این است که هیچ برهم کنشی بين ذرات وجود ندارد.

مدل اعتماد جمعی

در مدل اعتماد جمعی یک ذره برای به روز کردن سرعت خود، فقط به تجربه های جمعیت اکتفا می کند. کندی با آزمایش این مدل بر روی بعضی مسائل نتایج بهتری نسبت به مدل استاندارد به دست آورد، اما در حالت کلی استفاده از نسخه استاندارد، توصیه شد

مزیت های الگوریتم PSO

اکثر تکنیکهای تکاملی روند زیر را دنبال می کنند:

۱. شروع به کار با یک جمعیت تصادفی اولیه

٢. محاسبه مقدار شایستگی برای هر جواب

٣. تولید مجدد جمعیت بر اساس مقادیر شایستگی

۴. اگر نیاز برآورده نشده باشد همین روند از مرحله ۲ تکرار می شود.

همان طور که مشاهده می شود PSO نقاط مشترک زیادی با دیگر الگوریتم ها در طی این فرایند مشابه دارد، اما وجود یکسری تفاوت ها آن را از سایر روش ها متمایز کرده است. مهمترین مساله سادگی PSO است که از چند نظر قابل بررسی است. اول اینکه پیاده سازی آن بسیار ساده بوده و برنامه آن از چند خط فراتر نمی رود، در ثانی این سادگی موجب بالا رفتن سرعت در محاسبات و رسیدن سریع به جواب دلخواه با حجم کم حافظه مورد نیاز می شود. برای درک بهتر، در ادامه تفاوت های PSO با GA بیان می شود. مکانیزم تسهیم اطلاعات در PSO با GA متفاوت است به طوری که در GA تمام کروموزوم ها اطلاعات را با همدیگر به مشارکت می گذارند، بنابراین کل جمعیت همانند یک گروه به سمت منطقه بهینه حرکت می کند اما در PSO تنها p-best و g-best اطلاعات را به سایرین میدهند و در سیر تکامل، ذرهها تنها تحت تاثیر بهترین جوابها حرکت می کنند و بنابراین تمام ذره ها به سرعت به بهترین جواب در اغلب موارد همگرا می شوند. نقطه ضعف GA محاسبات پر هزینه آن است ولی PSO همان کارآمدی را در یافتن جواب بهینه دارد و با توجه به عملگرهای کم آن، از لحاظ محاسباتی نیز کم هزینه است.

کاربردهای pso

PSO از نظر مفهومی ساده است. پارامترهای کمی دارد و اجرای آن راحت می باشد. این الگوریتم در زمینه های مختلفی کاربرد دارد. در کل، PSO در مورد زمینه های کاری با سایر الگوریتمهای تکاملی اشتراک دارد  PSO در حوزه وسیعی از حل مسائل از جمله در بهینه سازی توابع مشکل و چند متغیره با سرعت و کارایی بالا قابل استفاده است در ادامه جهت آشنایی به برخی کاربرد های PSO اشاره می شود:

• شبکه های عصبی مصنوعی
• مسائل بهینه سازی محدودیت دار
• مسائل مینیمم – ماکزیمم
• مسائل بهینه سازی چندهدفه
• مسیریابی پویا
• و سایر کاربردها