SI: Swarm Intelligence

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

الگوریتم ممتیکی مبتنی بر الگوریتم بهینه سازی ذرات

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

شکل 1: تغییرات محیط قله ها در مسئله قله های متحرک

روند الگوریتم پیشنهادی:

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

شکل2: شبه کد الگوریتم پیشنهادی ممتیکی مبتنی بر ازدحام ذرات

  بکارگیری الگوریتم ازدحام ذرات در الگوریتم پیشنهادی

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

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

1-     مقدار دهی اولیه موقعیت و سرعت ذرات

2-     بروزرسانی بردار سرعت

3-     بروزرسانی موقعیت

Vid(t+1)=ꞷVid(t)+C1r1(pId-xid (t))+C2r2(pgd-xid (t))

xid (t+1)=xid (t)+ Vid(t+1)                                                                 معادله(1)

که در معادله (1) منظور از  پارامتر اینرسی، Vid(t) سرعت i امین ذره، xid موقعیت i امین ذره، r1,r2  اعداد تصادفی مستقل با توزیع یکنواخت، C1,C2 فاکتورهای یادگیری (ثابت های  C1,C2 به ترتیب پارامتر ادراکی و پارامتر اجتماعی نامیده می شود)، pId بهترین جواب محلی و  pgd بهترین جواب مطلق می باشند. همان طور که در شکل 5 نشان داده شده است الگوریتم ازدحام ذرات، بردار سرعت هر ذره را بروز می کند و سپس مقدار سرعت جدید را به موقعیت و یا مقدار سرعت ذره اضافه می کند.

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

شکل 3: چگونگی حرکت ذره و بروزرسانی موقعیتش

 

بکارگیری سیستم فازی در الگوریتم ازدحام ذرات

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

شکل4: ورودی و خروجی سیستم فازی در الگوریتم ازدحام ذرات

توابع سیستم فازی در شکل های5و6 قابل مشاهده می باشد.

شکل5: پنجره نمایش قوانین

شکل6: قوانین فازی

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

چرا الگوریتم پیشنهادی برای مسائل پویا مناسب می باشد؟

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

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

این پست خلاصه ای از مقاله "حل مسئله قله های متحرک با استفاده از یک الگوریتم ممتیکی مبتنی بر الگوریتم بهینه سازی ذرات فازی" آقایان مرتضی علی زاده، محمدرضا میبدی، علیرضا رضوانیان که در مجله علمی- پژوهشی انجمن کامپیوتر ایران در سال 1392 چاپ گردیده است، می باشد.

مراجع:

[1] مرتضی علی زاده، محمدرضا میبدی، علیرضا رضوانیان، مقاله "حل مسئله قله های متحرک با استفاده از یک الگوریتم ممتیکی مبتنی بر الگوریتم بهینه سازی ذرات فازی"، مجله علمی- پژوهشی انجمن کامپیوتر ایران،1392 .

 
نظرات (0)
نام :
ایمیل : [پنهان میماند]
وب/وبلاگ :
برای نمایش آواتار خود در این وبلاگ در سایت Gravatar.com ثبت نام کنید. (راهنما)