بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
روش جدیدي براي الگوریتم PSO باینري
چکیده: امروزه با بزرگ شدن مسائل و اهمیت یافتن سرعت رسیدن به پاسخ و عدم پاسخگویی روشهاي کلاسیک، از الگوریتمهاي جستجوي رندوم به جاي جستجوي همه جانبه فضاي مسئله، استقبال بیشتري می شود. در این بین در سالهاي اخیر استفاده از الگوریتمهاي جستجوي هیوریستیک (شهودي) رشد چشمگیري داشته است. الگوریتم جستجوي PSO با تنظیم مسیر حرکت یک جمعیت از ذرات در فضاي مساله بر پایه اطلاعات مربوط به بهترین کارآیی قبلی مربوط به هر ذره و بهترین کارآیی قبلی مربوط به همسایگان هر ذره عمل جستجو را در فضاي مساله انجام میدهد. الگوریتم PSO ذاتا یک الگوریتم پیوسته است. براي حل مسائل گسسته، نسخه باینري آن نیز ارائه شده است. نسخه باینري این الگوریتم همگرایی مناسبی ندارد.
این موضوع ناشی از وجود دو ضعف عمده در الگوریتم است. در این مقاله ضمن بررسی ضعفهاي الگوریتمPSO باینري متداول، نسخه جدیدي براي الگوریتم PSO باینري ارائه میشود. این نسخه با الگوریتم باینري متداول در حل مسائل مختلف مقایسه شده و نتایج آن آمده است. نتایج آزمایش برتري قاطع نسخه پیشنهادي به نسخه متداول را خصوصا در موضوع همگرایی الگوریتم نشان میدهد.
کلمات کلیدي: روشهاي جستجوي هیوریستیک، الگوریتم PSO، الگوریتم PSO باینري، همگرایی.
1 مقدمه
1PSO یک تکنیک بهینه سازي مبتنی بر قوانین احتمال است که توسط دکتر راسل ابرهارت و دکترجیمز کندي در سال 1995 ارائه شد و از رفتار اجتماعی پرندگان یا ماهیها در پیدا کردن غذا، الهام گرفته شده است.[1] فرض بر این است که یک گروه از پرندگان بصورت تصادفی در یک منطقه به دنبال غذا میگردند در حالیکه تنها در یک قسمت از ناحیه جستجو، غذا وجود دارد. پرندگان از مکان غذا اطلاعی ندارند و تنها میزان فاصله خود تا آن محل را می دانند. استراتژي بکار رفته این است که پرندگان به دنبال پرنده اي حرکت میکنند که نزدیکترین فاصله را تا غذا دارد. درPSO هر جواب مسئله، یک پرنده در فضاي جستجو است که ذره٢ نام دارد. هر ذره داراي یک مقدار شایستگی است که توسط تابع شایستگی مسئله بدست می آید. پرنده اي که به غذا نزدیک تر است، شایستگی بیشتري دارد. این الگوریتم ماهیت پیوسته دارد و در کارهاي متعدد کارایی خود را ثابت کرده است. امروزه این الگوریتم در بسیاري از کاربردها استفاده میشود.[7-2]
بسیاري از مسائل وجود دارد که ماهیت گسسته دارند. علاوه بر آن در بسیاري از کاربردها حل مسائل با فضاي پیوسته نیز در فضاي گسسته انجام میشود. بنابراین از آنجایی که هم مسائل گسسته و هم مسائل پیوسته در یک فضاي گسسته قابل حل هستند، نیاز به الگوریتم PSO باینري احساس میشود. دکتر ابرهارت و دکتر کندي که مبدعان الگوریتم PSO هستند، نسخه باینري این الگوریتم را ارائه کردند.[8] نسخه باینري پیشنهادي اگر چه در پیدا کردن بهینه موثر عمل میکند، اما متاسفانه از همگرایی خوبی برخوردار نیست.
در این مقاله یک الگوریتم PSO باینري جدید ارائه شده است که مشکلات الگوریتم باینري متداول را برطرف می- کند. الگوریتم پیشنهادي ضمن برخورداري از همگرایی مناسب، جواب بهینه را نیز به سرعت پیدا میکند. ادامه این مقاله این گونه سازمان دهی شده است که در بخش دوم الگوریتم PSO پیوسته ارائه میشود. الگوریتم PSO باینري متداول در بخش سوم تشریح میشود. مشکلات الگوریتم PSO باینري متداول و همچنین الگوریتم باینري پیشنهادي در بخش چهارم بحث و بیان میشود. بخش پنجم مسائلی را معرفی میکند که الگوریتم روي آن آزموده شده است. نتایج آزمایش و مقایسه با الگوریتم PSO باینري متداول در بخش ششم میآید. بخش هفتم به جمع بندي میپردازد.
2 الگوریتم PSO
PSO با یک گروه از جوابهاي تصادفی (ذره ها) شروع به کار میکند، سپس براي یافتن جواب بهینه در فضاي مسئله با به روز کردن مکان ذرهها به جستجو میپردازد. هر ذره بصورت چند بعدي (بسته به طبیعت مسئله) با دو مقدار X id و Vid که به ترتیب معرف موقعیت مکانی و سرعت بعد d ام از I امین ذره هستند، مشخص میشود. در هر مرحله از حرکت جمعیت، مکان هر ذره با دو مقدار بهترین به روز میشود. اولین مقدار، بهترین جواب از لحاظ شایستگی است که تا کنون براي هر ذره بطور مجزا بدست آمده است و p_best نام دارد و دیگري بهترین مقداري است که تا کنون توسط تمام ذرهها در میان کل جمعیت بدست آمده است، این مقدار g_best نام دارد. اگر براي هر ذره یک همسایگی تعریف شود، این مقدار در آن همسایگی محاسبه می شود، در این شرایط این مقدار l_best نامیده میشود.
در هر تکرار الگوریتم بعد از یافتن دو مقدار p_best وg_best (یا (l_best، سرعت و مکان جدید هر ذره طبق روابط 1 و 2
به روز میشود.
که در رابطه 2، w وزن اینرسی در بازه 1 و 0، c1 و c2 ضرایب یادگیري یا شتاب در بازه 1 تا 2 (که معمولا c1 c2 در نظر گرفته می شود) و rand عددي تصادفی در بازه 1]،[0 است. همچنین مقدار نهائی سرعت هر ذره براي جلوگیري از واگرائی الگوریتم به یک بازه محدود میشود . vid −vmax , vmax شرط خاتمه الگوریتم، همگرایی آن یا توقف بعد از تعداد معینی از تکرار است.
الگوریتم PSO باینري
در سال 1997 توسط مبدعان PSO، مدل باینري آن جهت حل مسائل گسسته ارائه شد.[8] در این مدل موقعیت هر ذره با دو مقدار (صفر و یک) در هر بعد مشخص میشود.
یعنی هر ذره در یک فضاي محدود به صفر و یک حرکت میکند و vid احتمال یک بودن xid را بیان میکند. بروز کردن سرعت ذرهها با استفاده از رابطه 1 انجام میشود. از آنجائیکه vid در الگوریتم باینري بصورت تابع احتمال تعریف شده است، باید به بازه 1]،[0 محدود شود. بنابراین رابطه 2 به رابطه 3 تغییر می کند. در رابطه 3، ابتدا باید vid توسط تابع سیگموید (رابطه (4 به بازه 1]،[0 منتقل شود، سپس موقعیت جدید ذره محاسبه شود.[8]
که rand همانند قبل یک عدد تصادفی در بازه 0]،[1 است.
همانطور که مقدار Vid در الگوریتم پیوسته به یک بازه متقارن محدود میشود، در الگوریتم باینري نیز Vid به یک مقدار بیشینه محدود میشود( .( vid vmax بطور متداول مقدار Vmax برابر 6 در نظر گرفته میشود. اگرچه با این مقدار، خروجی تابع احتمال بکار رفته به بازه 0/9975]، [0/0025 محدود میشود، اما این محدودیت باعث همگرایی بهتر الگوریتم میشود.
4 معایب الگوریتم PSO باینري متداول و توصیف الگوریتم پیشنهادي
1-4 معایب الگوریتم PSO باینري متداول
ذرهها در PSO پیوسته با دو کمیت x و v تعریف میشوند که x موقعیت ذره ها، همان جوابهاي مسئله و v معرف سرعت براي هر ذره است که نشان دهنده میزان تغییر در موقعیت آینده ذره، نسبت به موقعیت فعلی آن است. مقادیر بزرگ v نشان میدهد که موقعیت جاري ذره مناسب نبوده و تا رسیدن به مکان بهینه، در فضاي مسئله فاصله زیادي دارد. بنابراین جابجائی بیشتري براي ذره لازم است تا خود را به مکان بهینه نزدیک کند(رابطه .(2 از طرف دیگر، مقادیر کوچک v حاکی از نزدیک شدن مکان ذره به جواب مسئله است. به گونهاي که اگر موقعیت ذره با موقعیت بهینه یکی شود سرعت ذره صفر شده و این نشان دهنده آن است که دیگر جابجائی ذره لازم نیست.
درPSO باینري تعاریف متفاوتی از x و v ارائه شده است.
بطوریکه سرعت ذره به جاي آنکه ذره را به سمت جوابهاي بهینه مساله هدایت کند، بصورت تابع احتمالات یک یا صفر شدن x مطرح می شود. به عبارت دیگر، مقدار vid احتمال اینکه مقدار xid یک یا صفر باشد را تعیین می کند. براي آنکه مقدار احتمال باید در بازه صفر و یک بگنجد، vid از تابع سیگموید میگذرد. تابع سیگموید که جهت محدود کردن vid بکار می رود در شکل 1 آمده است.
همانطور که مشاهده میشود درPSO باینري، بزرگ بودن مقدار vid نشان دهنده تغییرات زیاد xid نیست، بلکه متناسب با بزرگ بودن vid (در جهت مقادیر مثبت) احتمال یک بودن xid ، بدون توجه به مقدار قبلی آن، افزایش می- یابد. به همین نحو متناسب با بزرگ بودن vid (در جهت مقادیر منفی) احتمال صفر بودن xid ، بدون توجه به مقدار قبلی آن، زیاد می شود. از سوي دیگر، اگر vid برابر صفر شود مقدار xid ثابت نمانده و با احتمال %50 یک و با همین احتمال صفر خواهد بود. با توجه به آنچه که بحث شد، می-توان ایرادات زیر را به PSO باینري متداول وارد دانست.
الف) در حالیکه بزرگ شدن vid در جهت مثبت و منفی با یکدیگر فرقی ندارد و نشاندهنده این است که موقعیت ذره براي این بعد خاص باید تغییر کند، در الگوریتم باینري متداول بین این دو حالت فرق قائل شده است به گونهاي که بزرگ شدن آن در جهت مثبت باعث افزایش احتمال یک شدن موقعیت پرنده و بزرگ شدن آن در جهت منفی باعث افزایش احتمال صفر شدن آن میشود. همچنین، وقتی سرعت ذره براي یک بعد مشخص به صفر نزدیک میشود، به معنی آن است که ذره در آن بعد موقعیت مناسبی دارد.
این در حالی است که با تابع احتمال سیگموید، احتمال صفر یا یک شدن موقعیت پرنده در آن بعد برابر خواهد شد.
ب)موقعیت قبلی ذره براي محاسبه موقعیت بعدي آن در نظر گرفته نمیشود.
هر چند PSO باینري متداول بعنوان یک الگوریتم کارامد در یافتن جواب بهینه آزمایش شده است[2] و نتایج آزمایشهاي انجام شده در بخش پنجم این مقاله نیز موید این مطلب است، ولی با بررسی میانگین تابع شایستگی مشخص میشود علی رغم یافتن جوابهاي خوب توسط الگوریتم، جمعیت به این جوابها همگرا نمی شود. در تکرارهاي ابتدایی الگوریتم افزایش میانگین مشاهده میشود که نشان دهنده نزدیک شدن ذره ها به جواب بهینه است ولی در ادامه ذره ها از جواب بهینه دور میشوند. هنگامی که الگوریتم به جواب بهینه رسید باید احتمال تغییر موقعیت ذرهها به صفر نزدیک شود در حالیکه درست در همین موقع، احتمال صفر شدن یا یک شدن بدون توجه به حالت قبلی به 0/5 میرسد و همین موضوع همگرایی الگوریتم را به مخاطره میاندازد.
2-4 الگوریتم PSO باینري پیشنهادي
چنانچه بتوان با ارائه تابع احتمال مناسب، ضعفهاي الگوریتم باینري متداول را حل نمود، مشکل همگرایی الگوریتم برطرف خواهد شد. در الگوریتم پیشنهادي با ایجاد دو تغییر نسبت به الگوریتم متداول، تعاریف xid و vid با مدل اصلی سازگار شده و نتایج حاصله نشان از همگرائی جمعیت دارد.
در این الگوریتم به جاي تابع سیگموید از تابع رابطه 5 (شکل (2 استفاده شده است. با جایگزینی تابع احتمال رابطه 5 به جاي رابطه 4، مشکل الف که در بخش 1-4 به آن پرداخته شده، برطرف میشود. به عبارت دیگر، با تابع جدید میان سرعتهاي بزرگ مثبت و منفی دیگر فرقی نیست. از سوي دیگر براي رفع مشکل ب، رابطه 6 جایگزین رابطه 3 شده است. در این حالت بزرگ بودن vid نشان دهنده موقعیت نامناسب ذره است و باعث تغییر آن از صفر به یک یا از یک به صفرمی شود و کوچک بودن vid احتمال تغییر xid را کاهش میدهد و در نهایت زمانی که vid صفر شود موقعیت ذره بدون تغییر باقی می ماند.
5 مسائلی براي آزمایش
براي آزمایش کردن روش پیشنهادي و اطمینان از عملکرد آن، روش پیشنهادي به همراه الگوریتم PSO باینري متداول، در بهینه سازي 4 مساله استاندارد آزموده شده است. این توابع در بسیاري از تحقیقات بهینه سازي مورد استفاده قرار میگیرند.
در توابع الف، ب وج پیدا کردن مقدار مینیمم تابع و درتابع د، ماکزیمم تابع مد نظر است.
6 نتایج و مقایسه
الگوریتم پیشنهادي که از این به بعدNBPSO نامیده می-شود به همراه الگوریتم متداول که از این به بعد BPSO نامیده میشود در حل مسائل بخش 5 در شرایطی برابر پیاده سازي شدهاند. در هر دو روش از مدل محلی با همسایگی برابر 3
