بایگانی برچسب برای: سرعت بیشینه برشی

بهینه‌سازی ازدحام ذرات (PSO) قسمت 2

الگوریتم بهینه‌سازی دومرحله‌ای ازدحام ذرات

ر این مقاله روشی جدید مبتنی بر هوش جمعی برای حل مسائل بهینه سازی با روش الگوریتم بهینه‌سازی دومرحله‌ای ازدحام ذرات (particle swarm optimization algorithm) ارائه می‌شود. روش پیشنهادی, با استفاده از دو مرحله تحرک و همگرایی جمعیت, به نتایج جالبی در انواع توابع می‌رسد. در این روش جمعیت اولیه ذرات مقداردهی شده و سپس این ذرات در هر مرحله ابتدا خود را از نواحی نامناسب دور کرده و پس از آن به نواحی مناسب مهاجرت می‌کنند و در نهایت در این نواحی سعی در نزدیک شدن به نقاط بهینه را دارند. ویژگی الگوریتم، نتیجه گرفتن در توابع با ابعاد بالا و همچنین توابع دارای اکسترمم‌های محلی زیاد است. حرکت در جهت دور شدن از نواحی نامناسب، باعث می‌شود تا الگوریتم در مواجه با مسائل با ابعاد بسیار بزرگ و نیز مسائلی که در آن‌ها جمعیت دارای توزیع اولیه نامناسبی است نیز به خوبی عمل کرده و نتایج مناسبی از خود نشان دهد. پراکندگی نامناسب جمعیت اولیه, در الگوریتم بهینه‌سازی گروه ذرات تأثیر منفی دارد. این الگوریتم با مهاجرت کلی ذرات به سمت فضای مناسب، به نقاط بهینه همگرا می‌شود. در انتها ضمن آزمودن روش پیشنهادی بر روی چند تابع محک شناخته شده و مقایسه با الگوریتم بهینه‌سازی گروه ذرات مشاهده می‌شود که روش پیشنهادی به نتایج بهتری می‌رسد.

psoیک الگوریتم رایانه‌ای مبتنی بر جمعیت و کتره‌ای برای حل مسئله‌است. PSOیک نوع هوش جمعی مبتنی بر اصول روانشناسی اجتماعی و فراهم آوردن بینشی در رفتار اجتماعی و کمک کردن به کاربردهای مهندسی است.

الگوریتمPSO برای اولین بار در ۱۹۷۵ توسط Kennedyو C.Eberhart توصیف شد. این تکنیک‌ها بسیار رشد کرده‌اند و نسخه اصلی این الگوریتم به‌طور واضحی در نسخه‌های امروزی قابل شناخت است. تاثیرگذاری اجتماعی و یادگیری اجتماعی یک شخص را قادر می‌سازد تا ثبات دانستنی‌هایش را برقرار سازد. انسان‌ها مسائلشان را به کمک صحبت با دیگران و نیز به کمک برهم کنش با باورهایشان، گرایش هایشان و تغییر رفتارشان حل می‌کنند؛ این تغییرات را می‌توان به‌طور نمونه به شکل حرکت افراد به سوی یکدیگر در فضای آگاهی اجتماعی مجسم کرد.

ذرات جمعی شبیه سازی شده، این نوع از بهینه‌سازی اجتماعی می‌باشند. مسئله داه شده و چند راه برای ارزیابی مسئله پیشنهادی به ….. در شکل کلی “تابع شایستگی”حضور دارند. ساختار ارتباطی یا شبکه اجتماعی برای واگذار کردن هر همسایگی به یک فرد تعریف شده تا آن فرد با آن همسایگی بر هم کنش داشته باشد. سپس گروه کارگزاران به عنوان مهمان‌های سرزده برای راه حل‌های مسئله تعریف می‌شوند که آن‌ها را به نام “ذرات” نیز می‌شناسیم؛ از این رو آن‌ها را “ذرات دسته جمعی” نام نهاده‌ایم.

یک فرایند تکراری برای بهبود کاندیداها در طی حرکت ذرات در نظر گرفته شده‌است. ذرات مکرراً شایستگی راه حل‌های کاندیدا را ارزیابی می‌کنند و موقعیتی را که در آن بهترین موفقیت را داشته‌اند، به خاطر می سپارند. بهره راه حل کارگزاران “بهترین ذره” یا “بهترین محل” نامیده می‌شود. هر ذره این اطلاعات را برای دیگر ذرات موجود در همسایگی قابل دسترسی می‌کند.

همچنین آن‌ها نیز می‌توانند ببینند که دیگر ذرات موجود در همسایگی در کجا بهترین موفقیت را داشته‌اند.

رکت‌ها در فضای جستجو بوسیلهٔ موفقیت‌های قبلی ؛ با افرادی که بیشتر مواقع همگرایی دارند، سرانجام بهتر از حالتی است که نزدیک شدن به جواب بوسیله عواملی فاقد هوش جمعی ولی با همین روش صورت گیرد.

گروه به صورت نمونه بوسیله ذرات در فضای چند بعدی که مکان و سرعت دارد، مدل سازی می‌شود.

این ذرات در میان این ابر فضا(فضای دارای بیش از سه بعد) پرواز می‌کنند و دو توانایی ضرورری دارند:

۱-حافظه‌ای برای ذخیره‌سازی بهترین مکان خود۲-آگاهی در مورد بهترین موقعیت در همسایگی خود یا در کل فضای پاسخ‌ها اعضای دسته جمعی مکان‌های خوب را به یکدیگر از طریق ارتباط انتقال می‌دهند و موقعیت و سرعتشان را با مکان‌های خوب تنظیم می‌کنند.

هر ذره برای اعمال تغییری مناسب در مکان و سرعت خود اطلاعات زیر را دارا می‌باشد:

۱-“بهترین عمومی” که برای همه شناخته شده‌است و هنگامی که هر ذره بهترین مکان جدیدی را شناسایی کند، فوراً برای بقیه ذرات اطلاعات مربوطه را به روزرسانی می‌کند.

۲-“بهترین همسایگی”که ذره از طریق ارتباط با زیر مجموعه‌های گروه، آن را بدست می‌آورد.

۳-“بهترین محلی”که بهترین راه حلی است که ذره تاکنون تجربه کرده‌است.

همه ذرات شروع به تأثیرپذیری از “بهترین عمومی” می‌کنند تا سرانجام به آن نزدیک شوند. ذرات در فضای جستجو در نزدیکی “بهترین عمومی” سیر می‌کنند و بقیه فضا را کاوش نمی‌کنند، به این پدیده”همگرایی” گفته می‌شود. اگر ضریب اینرسی سرعت را کوچک انتخاب کنیم، تمام ذرات می‌توانند سرعتشان را کاهش دهند تا اینکه در “بهترین عمومی” به سرعت صفر نزدیکتر شوند. یک را خروج از وضعیت همگرایی اولیه(نامطلوب) این است که دوباره به موقعیت ذرات (پس از رخ دادن همگرایی)مقدار اولیه بدهیم.

منبع

الگوریتم بهینه سازی ازدحام ذرات(PSO)

الگوریتم pso

مقدمه

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

 الگوریتم pso

تعاریف اولیه الگوریتم PSO

فرض کنید یک فضای جستجوی d بعدی داریم. i اُمین ذره در این فضای d بعدی باب بردار موقعیت Xi به شکل زیر توصیف می گردد:

1

بردار سرعت i اُمین ذره نیز با بردار Vi به شکل زیر تعریف می گردد:

2

بهترین موقعیتی که ذره i اُم پیدا کرده است را با Pi .best تعریف می کنیم:

3

بهترین موقعیتی که بهترین ذره در بین کل ذرات پیدا کرده است را با Pg .best به صورت زیر تعریف می کنیم:

4

برای به روز رسانی محل هر کدام از ذرات از رابطه زیر استفاده می کنیم:

5

  • W : ضریب وزنی اینرسی (حرکت در مسیر خودی) که نشان دهنده میزان تأثیر بردار سرعت تکرار قبل 14 بر روی بردار سرعت در تکرار فعلی 15 است.
  • c1 : ضریب ثابت آموزش (حرکت در مسیر بهترین مقدار ذره مورد بررسی)
  • c2 : ضریب ثابت آموزش (حرکت در مسیر بهترین ذره یافت شده در بین کل جمعیت)
  • rand1 , rand2: دو عدد تصادفی با توزیع یکنواخت در بازه 0 تا 1
  •  (Vi(t-1 بردار سرعت در تکرار (t-1) ام
  •  (Xi(t-1 بردار موقعیت در تکرار (t-1) ام

برای جلوگیری از افزایش بیش از حد سرعت حرکت یک ذره در حرکت از یک محل به محل دیگر (واگرا شدن بردار سرعت)، تغییرات سرعت را به رنج Vmin تا  Vmax محدود می کنیم؛ یعنی6 . حد بالا و پایین سرعت با توجه به نوع مسئله تعیین می گردد.

محدود سازی فضا

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

7

مکانیزمی که برای لحاظ کردن این قید استفاده می شود، بصورت زیر است:

x=max(0,x)

در تابع فوق مقادیر مجاز x؛ یعنی 0≤x بدون هیچ گونه تغییری نگاشت می شوند اما مقادیر غیر مجاز x؛ یعنی 0>x به مقدار مجاز x=0 نگاشت می شوند. در حالت کلی تر اگر بخواهیم محل ذرات بصورت 17 باشد، برای محدودسازی می توان از رابطه زیر استفاده کرد:

8

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

مراحل اجرای الگوریتم PSO

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

مرحله 1، تولید تصادفی جمعیت اولیه ذرات

تولید تصادفی جمعیت اولیه بطور ساده عبارت است از تعیین تصادفی محل اولیه ذرات با توزیع یکنواخت در فضای حل (فضای جستجو). مرحله تولید تصادفی جمعیت اولیه تقریباً در تمامی الگوریتم های بهینه سازی احتمالاتی وجود دارد. اما در این الگوریتم علاوه بر محل تصادفی اولیه ذرات، مقداری برای سرعت اولیه ذرات نیز اختصاص می یابد. رنج پیشنهادی اولیه برای سرعت ذرات را می توان از رابطه زیر استخراج کرد.

9

انتخاب تعداد ذرات اولیه

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

بطور خلاصه، تعداد جمعیت اولیه با توجه به مسئله تعیین می گردد. در حالت کلی تعداد ذرات اولیه مصالحه ای بین پارامترهای درگیر در مسئله است. بطور تجربی انتخاب جمعیت اولیه ذرات به تعداد 20 تا 30 ذره انتخاب مناسبی است که تقریباً برای تمامی مسائل تست به خوبی جواب می دهد. می توانید تعداد ذرات را کمی بیشتر از حد لازم نیز در نظر بگیرید تا کمی حاشیه ایمنی در مواجهه با مینیمم های محلی داشته باشید.

ارزیابی تابع هدف (محاسبه هزینه یا برآزندگی) ذرات

در این مرحله باید هر یک از ذرات را که نشان دهنده یک حل برای مسئله مورد بررسی است، ارزیابی کنیم. بسته به مسئله مورد بررسی، روش ارزیابی متفاوت خواهد بود. مثلاً اگر امکان تعریف یک تابع ریاضی برای هدف وجود داشته باشد، با جایگذاری پارامترهای ورودی (که از بردار موقعیت ذره استخراج شده اند) در این تابع ریاضی، به راحتی مقدار هزینه این ذره محاسبه خواهد شد. توجه داشته باشید که هر ذره حاوی اطلاعات کاملی از پارامترهای ورودی مسئله است که این اطلاعات استخراج شده و در تابع هدف قرار می گیرد.

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

ثبت بهترین موقعیت برای هر ذره (Pi .best)  و بهترین موقعیت در بین کل ذره ها (Pg .best)

در این مرحله با توجه به شماره تکرار، دو حالت قابل بررسی است:

  • اگر در تکرار اول باشیم (t=1). موقعیت فعلی هر ذره را به عنوان بهترین محل یافت شده برای آن ذره در نظر می گیریم.

10

در سایر تکرارها مقدار هزینه به دست آمده برای ذرات در مرحله 2 را با مقدار بهترین هزینه به دست آمده برای تک تک ذرات مقایسه می کنیم. اگر این هزینه کمتر از بهترین هزینه ثبت شده برای این ذره باشد، آنگاه محل و هزینه این ذره جایگزین مقدار قبلی می گردد. در غیر این صورت تغییری در محل و هزینه ثبت شده برای این ذره ایجاد نمی شود؛ یعنی:

11

به روز رسانی بردار سرعت تمامی ذره ها

12

ضرایب w,c1, c2 با توجه به مسئله مورد نظر به روش تجربی تعیین می گردند. اما به عنوان یک قانون کلی در نظر داشته باشید که w باید کمتر از یک باشد زیرا اگر بزرگتر از یک انتخاب شود، (V(t دائماً افزایش می یابد تا جایی که واگرا گردد. همچنین توجه داشته باشید، هرچند در تئوری ضریب w می تواند منفی نیز باشد اما در استفاده عملی از این الگوریتم هیچ گاه این ضرایب را منفی در نظر نگیرید زیرا منفی بودن w موجب ایجاد نوسان در (V(t می شود. انتخاب مقدار کوچک برای این ضریب (w) نیز مشکلاتی را در پی خواهد داشت. اغلب در الگوریتم PSO مقدار این ضریب را مثبت و در رنج 0.7 تا 0.8 در نظر می گیرند. c2و c3 نیز نباید زیاد بزرگ انتخاب شوند زیرا انتخاب مقادیر بزرگ برای این دو ضریب باعث انحراف شدید ذره از مسیر خودی می شود. اغلب در الگوریتم PSO مقدار این ضرایب را مثبت و در رنج 1.5 الی 1.7 در نظر می گیرند.

لازم به یادآوری است که الزاماً مقادیر پیشنهادی فوق تنها انتخاب های ممکن برای ضرایب w,c1, c2نیست بلکه با توجه به مسئله مورد بررسی ممکن است انتخاب های بهتری غیر از موارد فوق وجود داشته باشد.

تست همگرایی

تست همگرایی در این الگوریتم مانند سایر الگوریتم های بهینه سازی است. برای بررسی الگوریتم روش های گوناگونی وجود دارد. برای مثال می توان تعداد مشخصی تکرار را از همان ابتدا معلوم کرد و در هر مرحله بررسی کرد که آیا تعداد تکرارها به مقدار تعیین شده رسیده است؟ اگر تعداد تکرارها کوچکتر از مقدار تعیین شده اولیه باشد، آن گاه باید به مرحله 2 بازگردید در غیر این صورت الگوریتم پایان می پذیرد. روش دیگری که اغلب در تست همگرایی الگوریتم استفاده می شود، این است که اگر در چند تکرار متوالی مثلاً 15 یا 20 تکرار تغییری در مقدار هزینه بهترین ذره ایجاد نگردد، آنگاه الگوریتم پایان می یابد، در غیر این صورت باید به مرحله 2 بازگردید. دیاگرام گردشی (فلوچارت) الگوریتم PSO در شکل نشان داده شده است.

فلوچارت الگوریتم pso

فلوچارت الگوریتم pso

منبع

منابع

  1. fa.wikipedia.org
  2. fa.wikipedia.org
  3. http://matlabiran.ir

بهینه‌سازی ازدحام ذرات (PSO) قسمت 1
بهینه‌سازی ازدحام ذرات (PSO) قسمت 2

/0 دیدگاه /توسط

بهینه‌سازی ازدحام ذرات (PSO) قسمت 1

روش بهینه‌سازی ازدحام ذرات

روش بهینه‌سازی ازدحام ذرات (به انگلیسی: Particle swarm optimization) یا به اختصار روش PSO، یک روش سراسری کمینه‌سازی است که با استفاده از آن می‌توان با مسائلی که جواب آن‌ها یک نقطه یا سطح در فضای n بعدی می‌باشد، برخورد نمود. در اینچنین فضایی، فرضیاتی مطرح می‌شود و یک سرعت ابتدایی به آن‌ها اختصاص داده می‌شود، همچنین کانال‌های ارتباطی بین ذرات درنظر گرفته می‌شود. سپس این ذرات در فضای پاسخ حرکت می‌کنند، و نتایج حاصله بر مبنای یک «ملاک شایستگی» پس از هر بازهٔ زمانی محاسبه می‌شود. با گذشت زمان، ذرات به سمت ذراتی که دارای ملاک شایستگی بالاتری هستند و در گروه ارتباطی یکسانی قرار دارند، شتاب می‌گیرند. علی‌رغم اینکه هر روش در محدوده‌ای از مسائل به خوبی کار می‌کند، این روش در حل مسائل بهینه‌سازی پیوسته موفقیت بسیاری از خود نشان داده است.

انواع الگوریتم ازدحام ذرات

الگوریتم ازدحام ذرات پیوسته

مقدمه

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

در ادامه کمی به توضیح مفهوم هوش جمعی میپردازیم.

هوش جمعی

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

اولین الگوریتم ازدحام ذرات

در سال ۱۹۹۵ ابرهارت و کندی برای اولین بار PSO به عنوان یک روش جستجوی غیر قطعی برای بهینه‌سازی تابعی مطرح گشت این الگوریتم از حرکت دسته جمعی پرندگانی که به دنبال غذا میباشند، الهام گرفته شده‌است. گروهی از پرندگان در فضایی به صورت تصادفی دنبال غذا میگردند. تنها یک تکه غذا در فضای مورد جستجو وجود دارد. هر راه حل که به آن یک ذره گفته میشود، PSO در الگوریتم معادل یک پرنده در الگوریتم حرکت جمعی پرندگان میباشد. هر ذره یک مقدار شایستگی دارد که توسط یک تابع شایستگی محاسبه میشود. هر چه ذره در فضای جستجو به هدف (غذا در مدل حرکت پرندگان) نزدیکتر باشد، شایستگی بیشتری دارد. همچنین هر ذره دارای یک سرعت است که هدایت حرکت ذره را بر عهده دارد. هر ذره با دنبال کردن ذرات بهینه در حالت فعلی، به حرکت خود در فضای مسئله ادامه میدهد.

به ا ین شکل است که گروهٔ از ذرات در آغاز کار به صورت تصادفی به وجود می‌آیند و با به روز کردن نسلها سعی در یافتن راه‌حل بهینه می‌نمایند. در هر گام، هر ذره با استفاده از دو بهترین مقدار به روز می‌شود. اولین مورد، بهترین موقعیتی است که تاکنون ذره موفق به رسیدن به آن شده‌است. موقعیت مذکور شناخته و نگهداری می‌شود که این بهترین مقدار نوستالژی آن ذره نیز گفته میشود که آن را با pbest نمایش میدهیم. بهترین مقدار دیگری که توسط الگوریتم مورد استفاده قرار میگیرد، بهترین موقعیتی است که تا کنون توسط جمعیت ذرات بدست آمده‌است که آن را gbest میگوییم (هوش جمعی).

پس از یافتن بهترین مقادیر، سرعت و مکان هر ذره با استفاده از رابطه ۶ و ۷به روز می‌شود.

رابطه 6{\displaystyle v(t+1)=v(t)+c1*rand(t)*(pbest(t)-position(t)+c2*rand(t)*(gbest(t)-position(t))}

رابطه 7 {\displaystyle position(t+1)=position(t)+v(t+1)}

سمت راست معادله ۶ از سه قسمت تشکیل شده‌است که قسمت اول، سرعت فعلی ذره است ({\displaystyle v(t)}) و قسمتهای دوم ({\displaystyle c1*rand(t)*(pbest(t)-position(t))}) و سوم ({\displaystyle c2*rand(t)*(gbest(t)-position(t))}) میزان تغییر سرعت ذره و جهت آن به سمت بهترین تجربه شخصی (نوستالژی) و بهترین تجربه گروه (هوش جمعی) را به عهده دارند. اگر قسمت اول را در این معادله درنظر نگیریم ({\displaystyle v(t)})، آنگاه سرعت ذرات تنها با توجه به موقعیت فعلی و بهترین تجربه ذره و بهترین تجربه جمع تعیین می‌شود و عملاً تأثیر سرعت کنونی و لختی آن حذف می‌شود. به این ترتیب، بهترین ذره گروه، در جای خود ثابت می‌ماند و سایرین به سمت آن ذره حرکت می‌کنند. در واقع حرکت دسته جمعی ذرات بدون قسمت اول معادله ۶، پروسه ای خواهد بود که طی آن فضای جستجو به تدریج کوچک می‌شود و جستجویی محلی حول بهترین ذره شکل می‌گیرد. در مقابل اگر فقط قسمت اول معادله ۶ را در نظر بگیریم، ذرات راه عادی خود را می‌روند تا به دیواره محدوده برسند و به نوعی جستجویی سراسری را انجام میدهند. پارامترهای c1 و c2 (مقدار آن حدود ۲ است) میزان اهمیت و وزن هوش جمعی و نوستالژی را مشخص می‌کنند. پارامتر {\displaystyle rand(t)}

با صفر قرار دادن یا ندادن پارامترهای c1 و c2 سه حالت مختلف زیر به وجود می‌آید:

  1. هیچ‌کدام از این دو پارامتر را صفر نگذاریم که میشود pso با لختی سرعت، هوش جمعی و نوستالژی.
  2. وزن نوستالژی را صفر کنیم و فقط براساس هوش جمعی و لختی عمل کنیم.
  3. وزن هوش جمعی را صفر کنیم و فقط براساس نوستالژی و لختی عمل کنیم.

برای مقداردهی اولیه توسط رابطه ۸ عمل میکنیم. سرعت اولیه نیز طبق ۹ صفر است.

رابطه 8 {\displaystyle x(0)=x_{min}+rand(x_{max}-x_{min})}

رابطه 9 {\displaystyle v(0)=0}

شبه کد الگوریتم PSO:

For each particle
    Initialize particle
End For
Do
For each particle
    Calculate fitness value of the particle fp
    /*updating particle’s best fitness value so far)*/
    If fp is better than pBest
    set current value as the new pBest
End For
/*updating population’s best fitness value so far)*/
Set gBest to the best fitness value of all particles
For each particle
    Calculate particle velocity according equation
    Update particle position according equation
End For While maximum iterations OR minimum error criteria is not attained

اما در مورد شرط توقف باید گفت که راههای زیر موجود است:

  • ‌ تعداد تکرار معین
  • رسیدن به یک شایستگی آستانه
  • یک تعداد تکرار که شایستگی تغییر نکند (مثلاً اگر بعد از ۱۰ تکرار شایستگی ثابت بود و بهتر نشد).
  • راه آخر بر اساس چگالی تجمیع اطراف نقطه بهینه است. به این صورت که میگوییم اگر ۸۰ درصد ذرات در فاصلهای کمتر از ۲۰ درصد بیشترین فاصله نسبت به بهترین جواب قرار داشتند، الگوریتم باید متوقف شود.

روش آخر به این صورت است که طبق رابطه ۱۰ می‌توان را بدست آورد. همان‌طور که گفته شد{\displaystyle R_{norm}} یک مقدار بین ۰ و ۱ است و همین‌طور F بیشترین فاصله بین دو ذره در حالت کنونی است.

رابطه 10 {\displaystyle R_{norm}=\left({\frac {R_{max}}{F}}\right)}

مشکل اساسی اولین الگوریتم ازدحام ذرات

یک مشکل اساسی فرمول ارائه شده برای الگوریتم ازدحام ذرات اولیه اینست که دائماً سرعت افزایش می‌یابد و هیچ برنامه‌ای برای کاهش آن ارائه نشده است، درصورتیکه لازم است هر چه به بهینه سراسری نزدیک می‌شویم سرعت کمتر شود تا ذره ما از بهینه سراسری عبور نکند.

برای این کار چند راه حل ارائه شده‌است.

استفاده از سرعت بیشینه برشی

در این روش برای جلوگیری از زیاد شدن بیش از اندازه سرعت، یک سرعت بیشینه تعریف میشود تا هرگاه سرعت به بیش از آن رسید برش داده شود.

{\displaystyle v\prime (t+1)={\begin{cases}v(t+1)&v(t+1)<v_{max}\\v_{max}&v(t+1)>=v_{max}\end{cases}}}

استفاده از سرعت بیشینه تانژانت هیپربولیکی

در این روش از یک تابع تانژانت هیپربولیک برای محدود کردن سرعت به یک مقدار خاص استفاده می‌شود. تفاوت این حالت با حالت برشی اینست که در این حالت تابع ما مشتق پذیر در همهٔ نقاط است درحالیکه در حالت برشی مشتق پذیری از بین می رود.

{\displaystyle v\prime _{ij}(t+1)=tanh({\frac {v_{ij}(t+1)}{v_{maxj}}})v_{maxj}(t)}

در حالت برشی در نقطه برش مشتق پذیری از بین میرود؛ ولی در تانژانت هیپربولیک این مشکل وجود ندارد.

استفاده از ضریب کاهنده سرعت

در این روش از یک که باید بین ۰ و ۱ باشد، استفاده می‌شود. در غیر این صورت اگر بیش از ۱ باشد، سرعت افزاینده خواهد بود.

۱۴

حال تعیین کردن خود این یک مسئله است که روش‌های متعددی برای آن وجود دارد.

روش اول:

۱۵

روش دوم:

۱۶

در این روش باید را طوری تعیین کنیم که کمتر از ۱ شود.

روش سوم:

۱۷

برای می‌توان ۰٫۹ را انتخاب کرد و برای مقدار ۰٫۲ مناسب است.

روش چهارم:

در این روش براساس مقدار شایستگی تغییر می‌کند که این روش مناسب تری از روش‌های بالا است.

۱۸
۱۹

که شایستگی راه‌حل بهینه سراسری است.

روش پنجم:

در این روش که جدیدترین روش است یک پارامتر X خی که در کل سرعت ضرب می‌شود.

۲۰
۲۱ + ,
۲۲ ; k ∈[۰٬۱]
استفاده از تابعی برحسب تکرار برای سرعت بیشینه

در این روش سعی می‌شود تا از یک سرعت بیشینه به صورت تابعی از تکرار استفاده شود. در این روش سرعت بیشینه طبق رابطه ۱۳ برای هر بعد جداگانه حساب می‌شود.

[null 13]

این قابلیت باعث میشود که سرعت بیشینه با توجه به نیاز ما برای تنظیم وزن کاوش و انتفاع در هر تکرار مربوطه تعیین شود.

الگوریتم ازدحام ذرات آسنکرون

الگوریتم ازدحام ذرات گفته شده نوع سنکرون بود، یک نوع دیگری از این الگوریتم وجود دارد که به آن آسنکرون گویند. در این حالت پس از محاسبه شایستگی هریک از ذرات اگر بهینه سراسری عوض شد بلافاصله به‌روزرسانی میشود. این کار باعث میشود که سرعت همگرایی تا حدودی افزایش یابد؛ ولی امکان پیاده‌سازی موازی را می‌گیرد.

الگوریتم ازدحام ذرات تمام آگاه

ذرات با اطلاع هم و با هماهنگی حرکت می‌کنند و یک ذره حرکت بقیه را نیز در حرکت خودش دخالت می‌دهد.

۲۳

که یک عدد تصادفی است که به هر سرعت ذره یک وزن می‌دهد. در این حالت طبق رابطه هر ذره کاملاً کورکورانه بردار حرکت سایر ذرات را مد نظر قرار میدهد و با گرفتن برآیندی از جهت و اندازه حرکت همه، جهت و اندازه خود را بدست میآورد.

الگوریتم ازدحام ذرات استخوان خالی

این الگوریتم نسبت به الگوریتمهای قبلی خیلی سریع تر همگرا می‌شود و دارای دو نسخه است که در نسخه اول سرعت به شیوه زیر محاسبه می‌شود.

نسخه اول:

۲۴
۲۵
۲۶

نسخه دوم:

در این حالت در نیمی از حالات از روش استخوان خالی و در نیمی از الگوریتم ازدحام ذرات معمول استفاده میشود.

۲۷
الگوریتم ازدحام ذرات پیش کشیدن و پس زدن

در این الگوریتم ذره به سمت بهینه سراسری جذب می‌شود وقتی که به مقدار آستانه اول برسد، دفع می‌شود تا به جستجوی بیشتری بپردازد و این دفع شدن تا جایی ادامه پیدا میکند که به آستانه دوم برسد. عملیات جذب شدن با فرمول ۳۲ ولی دفع شدن با فرمول ۳۳ صورت می‌گیرد.

[null 32]
[null 33]
الگوریتم ازدحام ذرات شکار و شکارچی

هنگامی که ذرات همگرا شوند یک پارامتر ترس اعمال می‌کنیم با احتمال که باعث دور شدن ذرات از بهینه سراسری می‌شود و درنتیجه جستجو بیشتر می‌شود.

۳۴
۳۵
الگوریتم ازدحام ذرات چندشروعه

در این روش عملاً یک ذره را جهش می‌دهیم. برای وقتی است که مقدار شایستگی در چند تکرار بهبودی ندارد.

جمع‌بندی

الگوریتم ازدحام ذرات دودویی

این یکی از الگوریتم‌هایی است که برای مسائل جایگذاری یا عدم جایگذاری استفاده می‌شود. برای این کار باید از یک نگاشت برای تبدیل از پیوسته به دودویی استفاده شود.

منبع

بهینه‌سازی ازدحام ذرات (PSO) قسمت 1
بهینه‌سازی ازدحام ذرات (PSO) قسمت 2

/0 دیدگاه /توسط