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

در الگوریتم خوشه‌بندی اسناد پی.اس.اُ، فضای بردار سند چند بعدی به عنوان فضایی مسئله مدل‌سازی می‌شود. هر عبارت در دیتاست سند یک بعد از فضای مسئله ارائه می شود. هر بردار سند می‌تواند به عنوان  ضرب  در فضای مسئله ارائه شود. دیتاست سند کامل می‌تواند به عنوان فضای چند بعدی با یک  تعداد بزرگی از ضرب در  این فضا به دست بیاید.

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

البته جاهای دیگه هم هستند، که فرقی با این نمی کنند.

خلاصه این الگوریتم به شکل زیر است:

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

۲: برای هر ذره:

  1. هر بردار سند در مجموعه سند به عنوان مرکز خوشه تعیین می‌شود
  2. مبتنی بر معادل ۷ مقدار تناسب محاسبه می‌گردد
  3. با استفاده از سرعت و جایگاه ذره معادله ۶ به روزگشته و  راه حل بعدی را تولید می‌کند.

۳: گام ۲ تا زمانی که یک شرط انقضا حاصل شود تکرار می‌گردد.


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

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

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

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

Particle swarm optimization (PSO) algorithm

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

https://screenshots.firefoxusercontent.com/images/7039b196-4734-46d1-b55b-41c7af381133.png

بنابراین سرعت مبتنی بر سه ترکیب محاسبه می‌شود:

  • کسری از سرعت قبلی
  • عنصر شناختی که تابع فاصله ذره از بهترین جایگاه شخصی‌اش است.
  • عنصر اجتماعی که تابع فاصل ذره از بهترین ذره یافته شده است (برای مثال بهترین بهترین‌های شخصی)
 PSO is usually executed until a specified number of iterations have been exceeded or when the velocity updates are close to zero over a number of iterations.

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