الگوریتم پی.اس.اُ برای خوشه‌بندی شبکه‌های حسگر

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

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

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

در هر تکرار جایگاه و سرعت ذره آی با استفاده از معادله ۵ و ۶ بااقتباس از ۴ و ۸ به دست می‌آید.

یه چند تا مزیت دارد،

  • شکل ساده‌ای دارد
  • پیاده‌سازیش آسان است
  • پیچیدگی الگوریتمیش کم است
  • بار محاسباتی و پارامترهاش کم است

اما اشکالاتش یعنی دراوبک‌ها یا دیس‌ادونتیج‌ها

  • به آسانی در بهینه‌سازی محلی گیر می‌افتد که دلیلش هم تقریب زود هنگام است
  • یکی از انتقادات شدید که بش وارد است این است که ذرات ممکن است فراتر از ناحیه جستجو پرواز کنند

راهکار برطرف کردن مشکل

ترکیب با دیگر الگوریتم‌ها

یا نگه داشتن تنوع بهینه‌ سازی محلی و جهانی

بهبود یافته این الگوریتم

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

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

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

دیدگاه‌تان را بنویسید: