افزایش سازگاری فیلتر ذره ای با استفاده از روش های کلاسیک و الگوریتم اجتماع ذرات

نوع مقاله: مقاله علمی فارسی

نویسنده

استادیار، دانشکده مهندسی برق و کامپیوتر - دانشگاه بیرجند – بیرجند - ایران

چکیده

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

کلیدواژه‌ها


عنوان مقاله [English]

Increasing consistency of particle filter using the classic method and particle swarm algorithm

نویسنده [English]

  • Ramazan havangi
استادیار، دانشکده مهندسی برق و کامپیوتر - دانشگاه بیرجند – بیرجند - ایران
چکیده [English]

Particle filter is one of the main filters to estimate of non-linear/ non- Gaussian systems. However, it is inconsistent over time. Since the choice of the proposal distribution and the resampling method are is very important to improve the accuracy and consistency, in this paper, increasing consistency of particle filter is done using improved sampling and resampling. To optimize the sampling step, particle swarm optimization (PSO) has been merged into the importance sampling. PSO causes the particles to move to the high probability region of the posterior before sampling and therefor the distribution of particles is improved. In order to reduce the impact of resampling on the accuracy and consistency, a new resampling approach is proposed. The new resampling method can maintain diversity among the particles and ensure that the resampled particles asymptotically approximate the samples from the posterior probability density function of the true state. The main advantage of the proposed method is that it reduces computational cost. This is because the proposed resampling method is performed on only part of the particles. The validity of the proposed filter is evaluated using simulation. The results show that the proposed method has better performance than classical filters.

کلیدواژه‌ها [English]

  • Particle Filter
  • Degeneracy
  • particle swarm optimization(PSO)
  • Proposl distribution
  • Resampling

تخمین سیستم‌های غیر خطی موضوع مهمی در بسیاری از کاربردها مانند ردیابی و موقعیت‌یابی است. از دیدگاه تئوری بیزین مسئله تخمین عبارت است از: تخمین تابع چگالی احتمال پسین[i]]2-1[. با دانستن تابع چگالی احتمال پسین می‌توان تخمین بهینه حالت‌ها را نسبت به هر تابع معیاری محاسبه کرد. به‌طورکلی، بسته به مدل فرآیند و اندازه‌گیری، دو دسته جواب برای حل مسئله بیزین وجود دارد: 1. روش‌های پارامتریک (فیلترهای گوسین)؛ 2. روش‌های غیرپارامتریک. معروف‌ترین روش پارامتریک، فیلتر کالمن (KF) است. فیلترکالمن روشی بهینه برای تخمین سیستم‌های خطی است ]3 [.در سیستم‌های غیرخطی با نویز سفید گوسی می‌توان از فیلتر کالمن توسعه‌یافته(EKF) استفاده کرد]5-4[. در بسیاری از کاربردهای عملی با سیستم‌های غیرخطی - غیرگوسی سروکار داریم که در این گونه سیستم‌ها فیلتر کالمن توسعه‌یافته به‌صورت بهینه عمل نخواهد کرد ]5-4[. برای تخمین چنین سیستم‌هایی باید از فیلترهای غیرپارمتریک استفاده کرد. فیلتر ذره‌ای معروف‌ترین فیلتر غیرپارامتریک است. فیلتر ذره‌ای در اصل یک پیاد‌ه‌سازی مبتنی بر روش مونت - کارلو است که به‌طور وسیعی در تخمین سیستم‌های غیرخطی - غیرگوسی کاربرد دارد. در فیلتر ذره‌ای، تابع چگالی احتمال پسین با مجموعه‌ای از ذرات تخمین زده می‌شود ]7-6[. وقتی ذرات به‌طور مناسبی ‌وزن‌دهی و انتقال داده شوند، تابع چگالی احتمال پسین‌ می‌تواند به‌طور متوالی در طول زمان تخمین زده شود. با استفاده از تعداد محدودی از ذرات می‌توان هر سیستم غیرخطی را تخمین زد. با وجود مزایای زیادی که فیلتر ذره‌ای در تخمین سیستم‌های غیرخطی - غیرگوسی دارد، دارای نقطه ضعف بزرگی است. در فیلتر ذره‌ای حتی با انتخاب اولیة تعداد زیاد ذرات، ممکن است هیچ ذره‌ای در نزدیکی حالت صحیح قرار نگیرد. این ضعف در فیلتر ذره‌ای به پدیده تباهیدگی[ii] معروف است. برای کاهش تباهیدگی در فیلتر ذره‌ایِ استاندارد از نمونه‌برداری مجدد استفاده می‌شود ]8,2[. نمونه‌برداری مجدد ضمن اینکه برای فیلتر ذره‌ای حیاتی است، سبب پدیده‌ دیگری به‌نام فقر نمونه‌ها می‌شود. در این حالت تنوع میان ذرات از بین می‌رود و در بدترین حالت، همه ذرات به یک نقطه از فضای حالت ریزش می‌کنند ]10-9[.

تاکنون پژوهشگران مختلفی بر روی این موضوع کار کرده‌اند. در مراجع ]12-11[ فیلتر ذره‌ای توسعه‌یافته[iii] (EPF) ارائه شده است. در روش EPF، از فیلتر کالمن توسعه‌یافته (EKF) در طراحی تابع توزیع پیشنهادی استفاده شده است. در مراجع ]14-13 [فیلتر ذره‌ای بی‌رد (UPF)[iv] ارائه شده است. در UPF [v] از UKF برای بهبود تابع توزیع پیشنهادی و درنتیجه کاهش تعداد دفعات استفاده شده است. علاوه بر این، چندین روش کلاسیک در مقالات برای حل مسئله تباهیدگی پیشنهاد شده است که ازجمله آن‌ها می‌توان به فیلتر ذره‌ای تطبیقی ]16-15[ و فیلتر ذره‌ای کمکی ]17 [اشاره کرد. از طرف دیگر، پژوهشگران مختلفی برای حل مسئله تباهیدگی از محاسبات نرم استفاده کرده‌اند]23-18[. برای نمونه در ]18[ با واردکردن اپراتورهای الگوریتم ژنتیک در فیلتر ذره‌ای، فیلتر الگوریتم ژنتیک معرفی شده است. در مرجع ]19[ برای حل مسئله تباهیدگی در فیلتر ذره‌ای از استراتژی‌های تکاملی استفاده شده است. این فیلترها به‌منظور حل مسئله تباهیدگی با استراتژی تکاملی ترکیب شده‌اند. در مراجع ]21-20[ برای حل مسئله تباهیدگی، گام نمونه‌برداری فیلتر ذره‌ای با PSO بهبود داده شده است. برای این منظور ذرات با PSO به گونه‌ای حرکت داده شده‌اند که تابع درست‌نمایی[vi] ماکزیمم شود. عملکرد فیلتر ارائه‌شده، تنها از نظر دقت با استفاده از شبیه‌سازی با فیلتر ذره‌ای مقایسه شده است. یکی از نقاظ ضعف این روش، این است که موجب کاهش تنوع میان ذرات و درنتیجه کاهش سازگاری و افزایش ناپایداری فیلتر می‌شود. در] 23-22[ از سیستم‌های عصبی و فازی برای بهبود فیلتر ذره‌ای استفاده شده است

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

ساختار بقیه مقاله به شرح زیر است. در بخش 2، فیلتر ذره‌ای به‌طور مختصر بررسی شده است. الگوریتم PSO در بخش 3 معرفی شده است. در فصل 4، بهبود فیلتر ذره‌ای ارائه شده است. در بخش 5، الگوریتم پیشنهادی با استفاده از شبیه‌سازی‌های مختلف ارزیابی شده است و در بخش 6، نتیحه‌گیری شده است.

 

1- فیلتر ذره‌ای

سیستم غیرخطی زیر را در نظر بگیرید:

(1)

 

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

 

شکل(1): توصیف تابع پسین با فیلتر ذره‌ای

 

(2)

 

 

که بیانگر تعداد ذرات است. شکل (1) توصیف تابع پسین با فیلتر ذره‌ای را نشان می‌دهد. فیلتر ذره‌ای تابع پسین  را به‌صورت زیر تقریب می‌زند ]2-1 [:

(3)

 

 

که تابع دلتای دیراک است. وزن مربوط به  و  است.

نمونه‌برداری مستقیم از تابع چگالی احتمال اصلی (که به تابع توزیع هدف[vii] معروف است) ممکن نیست؛ ازاین‌رو، از روش نمونه‌برداری پراهمیت[viii] استفاده می‌شود. در روش نمونه‌برداری پراهمیت، به جای نمونه‌برداری مستقیم از تابع هدف از یک تابع توزیع پیشنهادی، نمونه‌برداری می‌شود.

درصورتی‌که تابع توزیع پیشنهادی به‌صورت  در نظر گرفته شود، وزن مربوط به ذرات به‌صورت زیر است ]2[:

(4)

 

این شیوة به‌دست‌آوردن تابع چگالی احتمال پسین به نمونه‌‌برداری پراهمیت بازگشتی SIS[ix] معروف است]2,1[. به‌منظور جلوگیری از پدیده تباهیدگی،  الگوریتم SIS با نمونه‌گیری مجدد معرفی شده است ]15[ که به الگوریتم SIR معروف است و دارای سه گام نمونه‌برداری، محاسبه وزن نمونه‌ها و نمونه‌برداری مجدد است:

1- نمونه‌برداری

 

ذرات با نمونه‌برداری از توزیع پیشنهادی به ‌دست می‌آیند.

2- محاسبه وزن نمونه‌ها

 

3-نمونه‌گیری مجدد

ذرات با وزن بالاتر جایگزین ذرات با وزن کمتر می‌شوند.

 

2- الگوریتم بهینه‌سازی اجتماع ذرات

کندی و ابرهات، الگوریتم بهینه‌سازی ‌اجتماع ذرات را در سال 1995 معرفی کردند]23[. الگوریتم PSO شباهت بسیاری به الگوریتم‌های جمعیتی مانند ژنتیک دارد. این الگوریتم از مجموعه‌ای از پاسخ‌های ممکن استفاده می‌کند که این پاسخ‌ها تا زمانی که پاسخ‌های بهینه یافت شود و یا شرایط پایان‌یافتن الگوریتم محقق شود، به حرکت خود در فضای جست‌وجو ادامه می‌دهند. باوجوداین، الگوریتم PSO در مقایسه با سایر الگوریتم‌های جمعیتی بسیار ساده‌تر است؛ زیرا این الگوریتم از عملگرهای تقاطع و جهش استفاده نمی‌کند. در عوض PSO از اعداد حقیقی تصادفی و ارتباط سراسری در گروه‌های ذرات بهره می‌گیرد و دارای عملکرد آسان‌تری است. در الگوریتم اجتماع ذرات دو عامل اساسی بر روی کارایی الگوریتم نتیجه مستقیم دارد: الگوریتم و اندازه جمعیت. ضرایب الگوریتم مجموعه‌ای از اعداد حقیقی هستند که در معادله الگوریتم ظاهر می‌شوند و مسیر حرکت ذرات را در فضای جست‌وجو معین می‌کنند. در روش‌های متداول، این ضرایب عموماً به‌صورت ثابت یا متغیر هستند. در الگوریتم PSO  تعدادی از ذرات در فضای جست‌وجو حرکت می‌کنند و هر ذره بهترین تجربه شخصی خود را اعم از بردار موقعیت و نیز بردار سرعت حفظ می‌کند و کل گروهِ ذرات نیز بهترین تجربه جمعی را حفظ می‌کنند. بردار سرعت در هر لحظه بر اساس سه عامل سرعت در گام قبل، بهترین تجربه شخصی و بهترین تجربه جمعی به‌روز می‌شود و پس از آن موقعیت هر ذره براساس این سرعت جدید به‌روز می‌شود. به‌طورکلی اگر  نشان‌دهندة موقعیت ذره  در فضای جست‌وجو در لحظه باشد، موقعیت  با افزودن سرعت  به موقعیت فعلی به‌صورت زیر تغییر می‌کند ]25-24[:

(5)

 

(6)

 

 

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

 

3- بهینه‌سازی فیلتر ذره‌ای

در این بخش، بهینه‌سازی فیلتر ذره‌ای مدّ نظر است. ازآنجایی‌که عملکرد فیلتر ذره‌ای به‌طور عمده به نمونه‌برداری و روش نمونه‌برداری مجدد وابسته است، این بهینه‌سازی با بهبود نمونه‌برداری و نمونه‌برداری مجدد انجام شده است. 

 

4-1 بهینه‌سازی نمونه‌برداری

انتخاب تابع توزیع پیشنهادی یکی از گام‌های مهم در فیلتر ذره‌ای است. عمومی و ساده‌ترین انتخاب برای تابع توزیع پیشنهادی، تابع انتقال حرکت است ]2-1[:

(7)

 

 

 

شکل(2): هم‌پوشانی بین درست‌نماییو توزیع پیشنهادی]20[

 

انتخاب تابع توزیع پیشنهادی به این صورت باوجود سادگی، دارای مشکلاتی است. درصورتی‌که تابع توزیع پیشنهادی  پهن‌تر از تابع درست‌نمایی[x] باشد، به تعداد ذرات کمی، وزن بالایی اختصاص می‌یابد. این موضوع در شکل (2) نشان داده شده است. این پدیده سبب می‌شود که ذرات به‌سرعت تباهیده شوند که در متون مربوط به فیلترهای ذره‌ای، این مشکل به پدیده تباهیدگی معروف است. در صورت رخ‌دادن این پدیده، تلاش زیادی برای به‌روزرسانی ذراتی می‌شود که سهم‌شان در تقریب تابع چگالی احتمال پسین تقریباً ناچیز است. ازطرفی، تباهیدگی سبب خواهد شد که بعد از مرحله نمونه‌برداری مجدد تنوع میان ذرات از بین برود و سبب ایجاد پدیده‌ای به‌نام  فقر نمونه ‌شود. نسخه‌های مختلفی از فیلتر ذره‌ای برای حل این مشکل معرفی‌ شده‌اند که ازجملة آن‌ها می‌توان به  فیلتر‌ ذره‌ای کمکی (APF) ]18[، فیلتر ذره‌ای توسعه‌یافته (EPF)، فیلتر ذره‌ای بی‌رد (UPF)]14-13[  اشاره کرد که همه این روش‌ها محاسبات فیلتر ذره‌ای را افزایش می‌‌دهند.

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

 

(8)

با توجه به قانون بیز،  را می‌توان به‌صورت زیر تجزیه کرد:

 

بنابراین مسئله بهینه‌سازی از نوع ماکزیمم‌سازی و به‌صورت زیر است:

 

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

 

 

برای سادگی می‌توان از تابع هدف لگاریتم گرفت:

 

 

با تعریف  رابطه بالا را می‌توان به فرم بازگشتی زیر نوشت:

 

 

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

(10)

 

 

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

 

 

تابع برازندگی سوق می‌دهد. با مجموعه ذرات جدید (ذرات جابه‌جاشده)، فرآیند نمونه‌برداری براساس تابع توزیع پیشنهادی انجام می‌شود؛ بنابراین گام نمونه‌برداری به‌صورت زیر اصلاح می‌شود:

1-   نمونه‌برداری از تابع توزیع پیشنهادی

ذرات به‌صورت زیر از تابع انتقال حرکت نمونه‌برداری می‌شوند:

 

2-   بردن ذرات به ناحیه پراهمیت تابع چگالی احتمال پسین توسط PSO

3-    محاسبه وزن ذرات

 

 

4-2-   بهبود نمونه‌برداری مجدد

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

 

شکل(3): نمونه‌برداری مجدد

 

به عبارت دیگر، نمونه‌برداری مجدد، یک نگاشت از اندازه تصادفی  به اندازه تصادفی  با وزن‌های یکنواخت است که نمونه‌های تصادفی مجموعه جدید  با نمونه‌برداری مجدد تولید می‌شوند. پروسه نمونه‌برداری مجدد به چندین طریق، ممکن است صورت بگیرد؛ اما ساده‌ترین روش آن به‌صورت زیر است که برای هر  دو گام زیر باید اجرا ‌شود ]2[:

1-   تولید یک عدد تصادفی  که به‌طور یکنواختی در فاصله [0 1] توزیع شده باشد.

2-   جمع‌کردن تا زمانی‌که داشته باشیم

 

در این صورت ذره جدید  به‌صورت  است.

اگرچه نمونه‌برداری مجدد، مسئله تباهیدگی را کاهش می‌دهد، اما سبب حذف برخی ذرات خوب از مجموعه نمونه‌ها و در بدترین حالت فیلتر واگرا خواهد شد. همچنین، هر زمان که نمونه‌برداری مجدد انجام می‌شود، کل تاریخچه مسیر برای همیشه از بین می‌رود. این سبب ازبین‌رفتنِ تنوع میان ذراتی می‌شود که حالت‌های گذشته را ارائه می‌کنند. همان‌طور که زمان می‌گذرد، تعداد ذرات مجزا و درنتیجه واریانس نمونه‌ها کاهش و ناسازگاری فیلتر، افزایش می‌یابد. برای حل این مشکل، تعیین زمان نمونه‌برداری مجدد و چگونگی انجام آن مهم است. برای تعیین زمان نمونه‌برداری مجدد، تعداد ذرات مؤثر  ارائه پیشنهاد شده است. تعداد ذرات مؤثر  به‌صورت زیر محاسبه می‌شوند:

(11)

 

 

که  وزن نرمال شده ذره-ام و  تعداد ذرات است. هر وقت که مقدار به زیر مقدار آستانه از پیش تعیین شده برسد، نمونه‌برداری مجدد انجام می‌شود. در حوزه فیلترهای ذره‌ای، الگوریتم‌های زیادی برای نمونه‌برداری مجدد ارائه شده است. معروف‌ترین الگوریتم‌های نمونه‌برداری مجدد، نمونه‌برداری مجدد چند جمله‌ای[xi]، نمونه‌برداری مجدد طبقه‌طبقه‌شده[xii]، نمونه‌برداری مجدد سیستماتیک[xiii] و نمونه‌برداری مجدد باقیمانده طبقه‌طبقه‌شده RSR[xiv] هستند ]10-9[ که در بیشتر کاربردها معمولاً از RSR استفاده می‌شود.

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

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

1)    دسته‌بندی ذرات به ذرات با وزن متوسط، ناچیز و زیاد

2)    انجام نمونه‌برداری مجدد روی ذرات با وزن ناچیز و زیاد

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

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

 

 

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

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

 

5- شبیه‌سازی و نتایج

برای ارزیابی عملکرد فیلتر ذره‌ای پیشنهادی، سیستم غیرخطی زیر در نظر گرفته شده است. میزان غیرخطی‌بودن این سیستم زیاد است و به همین دلیل در مقالات زیادی جهت ارزیابی عملکرد فیلترها استفاده شده است ]13,4[:

 

(11)

 

 

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

شکل(4): تخمین به‌دست‌آمده از فیلترها ()

 

5-1- ارزیابی عملکرد

 در ابتدا فرض می‌شود در همه الگوریتم‌ها، نویز پروسه و اندازه‌گیری به‌صورت زیر باشد:

(12)

 

 

همچنین تعداد ذرات  در نظر گرفته شده است. شکل‌های (4-7) نتایج را برای این شرایط نشان می‌دهند. نتایج از روش مونت کارلو با 50 بار اجرا به ‌دست آمده‌اند.

در شکل (4) روش پیشنهادی PF،  EPF و UPF، حالت واقعی و حالت تخمین زده شده را رسم کرده است. ملاحظه می‌شود که با این فیلتر پیشنهادی در مقایسه با سایر روش‌ها، حالت تخمین زده شده از حالت واقعی انحراف کمتری دارد.

برای ارزیابی بیشترِ دقت روش پیشنهادی و مقایسه عملکرد آن با سایر الگوریتم‌ها از جمله PSO-PF ]21-2 [، مقدار جذر میانگین مربع خطا (RMSE) بررسی شده است. مقدار RMSE روش پیشنهادی، PF، EPF، EPF، PSO-PF و UPF بر حسب زمان در شکل (5) و میانگین و انحراف استاندارد آن در شکل(6) نشان داده شده است. هر میله در شکل(6) نشان‌دهنده میانگین و انحراف استاندارد RMSE است. نتایج نشان می‌دهند که عملکرد فیلتر پیشنهادی بهتر از سایر روش‌ها است. این بدان علت است که نمونه‌برداری و نمونه‌برداری مجدد در روش پیشنهادی بهبود یافته است. در روش پیشنهادی، ترکیب PSO با تابع توزیع پیشنهادی سبب بهبود توزیع نمونه‌ها و سرعت‌بخشیدن به همگرایی مجموعه ذرات می‌شود؛ بنابراین اثر هر ذره افزایش یافته و تنوع میان ذرات بهبود پیدا کرده است. نهایتاً الگوریتم نمونه‌برداری مجددِ جدید، موجب افزایش تنوع میان ذرات و درنتیجه سازگاری و دقت می‌شود.

 

شکل(5): RMSE نسبت به زمان()

شکل(6): RMSE فیلترها ()

 

مطابق شکل(7) تنوع میان ذرات در روش پیشنهادی بیش از سایر فیلترها است؛ درنتیجه، در روش پیشنهادی، ذرات می‌توانند تقریب بهتری از تابع چگالی احتمال پسین بزنند و دقت تخمین‌ها بهبود پیدا می‌کند. همچنین تنوع ذرات در الگوریتم PSO-PF از همه کمتر است. الگوریتم PSO-PF، اگرچه مطابق شکل (6) دقتی در حد EPF دارد، اما ازآنجایی‌که تنوع میان ذرات آن کم است از سازگاری کمتری برخوردار است.

 

شکل (7) : تنوع میان ذرات ( )

 

جدول(1): عملکرد فیلترها با تعداد ذرات مختلف()

Number Particle

Methods

RMSE

Processing Time

Mean

Var

100

Proposed Method

0.84

0.96

0.3

UPF

1.7

2.1

1.29

EPF

1.88

2.3

0.51

PF

2.2

2.52

0.14

50

Proposed Method

1.17

1.1

0.18

UPF

1.92

2.21

0.66

EPF

2.7

3.19

0.26

PF

3

3.27

0.08

10

Proposed Method

2.3

1.92

0.10

UPF

3.25

4

0.20

EPF

3.47

4.68

0.09

PF

4.8

5.5

0.03

 

عملکرد روش پیشنهادی با تعداد ذرات مختلف در مقایسه با PF ، EPF و UPF در جدول (1) نشان داده شده است. مشاهده می‌شود، وابستگی عملکرد PF به تعداد ذرات از همه فیلترها بیشتر و روش پیشنهادی کمترین وابستگی را به تعداد ذرات دارد. این موضوع بدان علت است که در روش پیشنهادی، PSO ذرات را در ناحیه با احتمال بالا قبل از نمونه‌برداری قرار می‌دهد. به‌علاوه الگوریتم نمونه‌برداری مجدد جدید تنوع میان ذرات را حفظ می‌کند و باعث می‌شود ذرات نمونه‌برداری مجدد شده به‌طور مجانبی نمونه‌ها را از تابع چگالی احتمال پسین حالت واقعی تقریب بزنند. به عبارت دیگر، روش پیشنهادی می‌تواند از فقر نمونه‌ها جلوگیری کند و در نتیجه به تعداد ذرات زیاد نیازی نیست. امتیاز الگوریتم جدید این است که آن می‌تواند هزینه محاسباتی را کاهش دهد؛ زیرا نمونه‌برداری مجدد روی تنها بخشی از ذرات انجام می‌شود. همان‌طور که در جدول (1) نشان داده شده است، زمان محاسبات الگوریتم پیشنهادی تقریباً نزدیک PF است؛ ازاین‌رو روش پیشنهادی برای به‌دست‌آوردن دقت تخمین یکسان با سایر روش‌ها به تعداد ذرات کمتری لازم است.

سپس عملکرد فیلتر پیشنهادی با دیگر فیلترها در شرایطی مقایسه می‌شود که نویز پروسه و اندازه‌گیری به‌صورت زیر است:

(13)

 

 

شکل‌های (8-11) نتایج را برای این حالت نشان می‌دهد. نتایج با 50 بار اجرا به ‌دست آمده است. شکل(8) حالت واقعی و حالت‌های تخمین زده شده توسط فیلترها را نشان می‌دهد. مقدار RMSE در طول  زمان در شکل (9) و میانگین و انحراف استاندارد آن در شکل (10) نشان داده شده است. مشاهده می‌شود که در این حالت، عملکرد فیلتر ذره‌ای بدتر از حالت قبل است؛ درحالی‌که عملکرد روش پیشنهادی در این حالت تقریباً با حالت قبل یکسان است. درصورتی‌که نویز پروسه نسبت به نویز اندازه‌گیری بیشتر باشد، به دلیل اینکه فقر نمونه بیشتر در فیلتر ذره‌ای اتفاق می‌افتد، دقت تخمین‌ها و تنوع میان ذرات کمتر می‌شود. از شکل (11) مشاهده می‌شود، تنوع میان ذرات در فیلتر ذره‌ای نبست به حالت قبل به‌طور چشمگیری نسبت به سایر فیلترها کاهش یافته است.

 

شکل(8): تخمین به‌دست‌آمده از فیلترها ()

 

شکل(9): RMSE نسبت به زمان ( )

 

 

شکل (10): عملکرد فیلترها ()

 

 

شکل(11): تنوع میان ذرات ()

 

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

 

 

 

جدول (2): عملکرد فیلترها با تعداد ذرات مختلف ()

Number Particle

Methods

RMSE

Processing Time

Mean

Var

100

Proposed Method

0.86

0.9

0.3

UPF

3.6

1.98

1.29

EPF

4

2.2

0.51

PF

6

6.05

0.14

50

Proposed Method

1.2

1.18

0.18

UPF

3.9

2.31

0.66

EPF

4.5

3.3

0.26

PF

6.7

6.8

0.08

10

Proposed Method

2.5

1.95

0.10

UPF

4.5

4.12

0.20

EPF

4.92

4.35

0.09

PF

7.94

8.41

0.03

 

5-2- بررسی سازگاری

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

 

که خطای تخمین، حالت تخمین زده شده و  کواریانس حالت‌های تخمین زده شده در لحظه است. در معادلات بالا، اولین رابطه، لازمه بدون بایاس‌بودن تخمین‌ها است؛ درحالی‌که دومین رابطه، لازمه تطبیق کواریانس است. در عمل، سازگاری به وسیله اجرای چندین بار مونت کارلو و محاسبه NEES ارزیابی می‌شود. اگر حالت واقعی معلوم باشد، NEES به‌صورت زیر است [26]:

 

 

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

 

 

 

برای فیلتر گوسین خطی سازگار،  دارای تابع چگالی احتمال  با درجه آزادی است. برای مطالعه بیشتر درمورد سازگاری یک فیلتر ازطریق متوسط NEES می‌توان به ]26[ مراجعه کرد. برای حالت یک بعدی وسیله، با 50 شبیه‌سازی مونت کارلو، دو سمت احتمال 95% برای  به بازه [0.69  1.35] محدود می‌شود. سازگاری الگوریتم‌ها در شرایطی مقایسه می‌شود که نویز پروسه و اندازه‌گیری به‌صورت زیر است:

(14)

 

 

 

الف

ب

شکل (12): سازگاری: الف) PF ب) روش پیشنهادی

 

شکل (12) سازگاری فیلتر پیشنهادی و فیلتر ذره‌ای را نشان می‌دهد. نتایج حاکی از این است که سازگاری روش پیشنهادی بیشتر از فیلتر ذره‌ای است. این به این دلیل است که تنوع میان ذرات در روش پیشنهادی بیشتر است. نرخ ازدست‌دادن تنوع میان ذرات با ثبت تعداد ذرات مجزا تخمین زده شده است. شکل (11) تعداد ذرات مجزا که بعد از نمونه‌برداری مجدد شمارش شده‌اند را برای حالت  نشان می‌دهد. همان‌طور که ملاحظه می‌شود، تعداد ذرات مجزا در روش پیشنهادی بیشتر از PF است؛ بنابراین انتظار می‌رود که سازگاری روش پیشنهادی بیشتر از سایر روش‌‌ها باشد.

 

6- نتیجه‌گیری

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



[i] Probability density function posterior

[ii] Degeneracy

[iii] Extended particle filter

[iv] Unscented particle filter

[v] Unscented Kalman filter

[vi] Likelihood  function

[vii] Target distribution

[viii] Importance sampling

[ix] Sequence  importance sampling

[x] Likelihood  function

[xi] Multinomial resampling

[xii] Stratified resampling

[xiii] Systematic resampling

[xiv] Residual stratified resampling

[1]        Ristic, B., Arulampalam, S., Gordon, N., in Beyond Kalman Filter:Particle Filters Tracking Applicat, 1st ed. Boston, 2004.

[2]        Arulampalam, S., Maskell, S., Gordon, N., Clapp, T., “A tutorialon particle filters for Online nonlinear/nongaussian Bayesian tracking”, IEEE Trans. Signal Process., Vol. 50, No. 2, pp. 174–188, 2002.

[3]        Chen, S., “Kalman filter for robot vision: A survey”, IEEE Trans. Ind. Electron., Vol. 59, No. 11, pp. 4409–4420, 2012.

[4]        Loiola, M. B. Lopes, R.R., Romano, J.M.T., “Modified Kalman filters for channel estimation in orthogonal space-time coded systems”, IEEE Trans. Signal Proces., Vol. 60, No. 1, pp. 533–538, 2012.

[5]        Roshany-Yamchi, S., Cychowski, M., Negenborn , R.R., De Schutter, B., Delaney, K., Connell, J. , “Kalman filter-based distributed predictive control of large-scale multi-rate systems: Application to power networks”, IEEE Trans. Contr. Syst. T., Vol. 21, No. 1, pp. 27–39, 2013.

[6]        Gustafsson, F. , Gunnarsson, F., Bergman, N. , Forssell, U., Jansson, J. , Karlsson, R., Nordlund, P.J. “Particle filters for positioning, navigation, and tracking”, IEEE Trans. Signal Proces., Vol. 50, No. 2, pp. 425–437, 2002.

[7]        Shenoy, A. , Prakash, J. , Prasad, V., Shah, S., McAuley, K. , “Practical issues in state estimation using particle filters: Case studies with polymer reactors”, Journal  Process Control, Vol. 23, No. 2, pp. 120–131, 2013.

[8]        Park, S., Hwang, J.  Kim, E., Kang, H., “A New Evolutionary Particle Filter for the Prevention of Sample Impoverishment”, IEEE Trans. On Evolutionary Computation, Vol.13, No. 4, pp.801-809,2009.[زهرا1] 

[9]        Xiaoyan, F., Yingmin, J., “An Improvement on Resampling Algorithm of Particle Filters”  , IEEE Transactions Signal Processing, Vol. 58, pp. 5414-5420, 2010.

[10]     Chi, F., Meng, W., Qing-Bo, J. ,  “Analysis and Comparison of Resampling Algorithms in Particle Filter”, Journal of system simulation, Vol. 4, No.4, pp.1101-1105, 2009.[زهرا2] 

[11]     Carter, C. K., et al. , “An extended space approach for particle Markov chain Monte Carlo methods”, arXiv preprint arXiv:1406.5795, 2014.

[12]     Doucet, A., Godsill, S., Andrieu, C. “On sequential Monte Carlo  sampling methods for Bayesian filtering”, Statistics and Computing,  Vol.10, No.3, pp.192–208,2000.[زهرا3] 

[13]     Qing, X., et al., “Decentralized unscented Kalman filter based on a consensus algorithm for multi-area dynamic state estimation in power systems”, International Journal of Electrical Power & Energy Systems, Vol.65,No.1, pp. 26-33,2015.[زهرا4] 

[14]     Merwe, R., Doucet, A., de Freitas, N.,  Wan, E. “The unscented particle filter”, Technical Report CUED/F INFENG/TR 380, Cambridge University Engineering Department, 2000.

[15]     Zhang, G.-Y. , Cheng, Y.-M. , Yang, F., Pan, Q., and Liang, Y., “Design of an Adaptive Particle Filter Based on Variance Reduction Technique”, Acta Automatica Sinica, Vol. 36, No.7, pp. 1020-1024, 2010.[زهرا5] 

[16]     J.Joseph Ignatious, J., UmaMageswari, A., Abraham Lincon, S., “Adaptive Particle Filter Approach to Approximate Particle Degeneracy”, International Journal of Scientific & Engineering Research Vol. 3, No.7, pp. 2229-5518, 2012.

[17]     Kronander, J., Schon, T.B., “Robust auxiliary particle filters using multiple importance sampling”, In Proceedings of the IEEE Statistical Signal Processing Workshop (SSP), pp. 268-271, 2014.

[18]     Higuchi, T., “Monte Carlo filter using the genetic algorithm operators”, Journal of Statistics Computation and Simulation, Vol.59, No.1, pp. 1-23, 1997.[زهرا6] 

[19]     Uosaki, K., Kimura, Y., Hatanaka, T., “ Nonlinear State Estimation by Evolution Strategies Based Particle Filters”, in Proceedings of the IEEE Congress on Evolutionary Computation, 2003.

[20]     Tong, G., Zheng F., Xinhe X. “A particle swarm optimized particle filter for nonlinear system state estimation” IEEE Congress on Evolutionary Computation, CEC 2006, pp. 438 - 442, 2006. 

[21]     Zhang, G., Yongmei C., Feng Y., Quan , P. “Particle filter based on PSO” in Proceedings of International Conference on Intelligent Computation Technology and Automation (ICICTA), pp.121-124 , 2008. [زهرا7] 

[22]     Hao, W., et al., “Fuzzy Particle Filtering for Uncertain Systems”, IEEE Transactions Fuzzy Systems, Vol. 16, pp. 1114-1129, 2008.

[23]     Wang, E., et al., “Application of Neural Network Aided Particle Filter in GPS Receiver Autonomous Integrity Monitoring”, in Proceedings China Satellite Navigation Conference (CSNC), pp. 147-157, 2014.[زهرا8] 

[24]     Clerc, M., Kennedy, J., “The particle swarm—explosion, stability, and convergence in a multidimensional complex space”, IEEE Tran. Evolutionary computation, Vol.6, No.1, pp.58-73, 2002. 

[25]     Na, He., Dianguo, Xu., Huang, L. “The application of particle swarm optimization to passive and hybrid active power filter design”, IEEE Trans. Industrial Electronics, Vol. 56, No.8, pp. 2841-2851, 2009.

[26]     Bar-Shalom, Y., Li, X.R., Kirubarajan, T., Estimation with Applications to Tracking and Navigation , John Wiley and Sons, 2001.