الگوریتم بهینه سازی PSO چند هدفه (MOPSO)

الگوریتم های زمانبندی بر اساس PSO

پديدهPSO، براي اولين بار توسط کندي و ابرهارت در سال 1995 مطرح شد. PSO يک الگوريتم محاسبه اي تکاملي الهام گرفته از طبيعت و براساس تکرار مي‌باشد. منبع الهام اين الگوريتم، رفتار اجتماعي حيوانات، همانند حرکت دسته جمعي پرندگان و ماهي‌ها بود. از اين جهت که PSO نيز با يک ماتريس جمعيت تصادفي اوليه، شروع مي‌شود، شبيه بسیاری دیگر از الگوریتم های تکاملی همچون الگوريتم ژنتيک پيوسته است. برخلاف الگوریتم ژنتیک، PSO هيچ عملگر تکاملي همانند جهش و تزويج ندارد. هر عنصر جمعيت، يک ذره ناميده مي‌شود (که همان معادل کروموزوم درGA) است. در واقع الگوريتم PSO از تعداد مشخصي از ذرات تشکيل مي شود که به طور تصادفي، مقدار اوليه مي¬گيرند. براي هر ذره دو مقدار وضعيت و سرعت، تعريف مي شود که به ترتيب با يک بردار مکان و يک بردار سرعت، مدل مي‌شوند. اين ذرات، بصورت تکرارشونده اي در فضاي n بعدي مسئله حرکت مي کنند تا با محاسبة مقدار بهينگي به عنوان يک ملاک سنجش، گزينه‌هاي ممکن جديد را جستجو کنند. بُعد فضاي مسئله، برابر تعداد پارامترهاي موجود در تابع مورد نظر براي بهينه سازي مي باشد. يک حافظه به ذخيرة بهترين موقعيت هر ذره در گذشته و يک حافظه به ذخيرة بهترين موقعيت پيش آمده در ميان همة ذرات، اختصاص مي‌يابد. با تجربة حاصل از اين حافظه ها، ذرات تصميم مي گيرند که در نوبت بعدي چگونه حرکت کنند. در هر بار تکرار، همة ذرات در فضاي nبُعدي مسئله حرکت مي کنند تا بالاخره نقطه بهينه عام، پيدا شود. ذرات، سرعت‌هايشان و موقعيت‌شان را بر حسب بهترين جواب‌هاي مطلق و محلي به‌روز مي‌کنند.
الگوريتمPSO، بردار سرعت هر ذره را به‌روز کرده و سپس مقدار سرعت جديد را به موقعيت و يا مقدار ذره مي‌افزايد. به‌روز کردن‌هاي سرعت، تحت تأثير هر دو مقدار بهترين جواب محلي و بهترين جواب مطلق قرار مي‌گيرند. بهترين جواب محلي و بهترين جواب مطلق، بهترين جوابهايي هستند که تا لحظه‌ي جاري اجراي الگوريتم، به ترتيب توسط يک ذره و در کل جمعيت به دست آمده‌اند. مزيت اصلي PSO اين است که پياده‌سازي اين الگوريتم ساده بوده و نياز به تعيين پارامتر‌هاي کمي دارد. همچنين PSO قادر به بهينه‌سازي توابع هزينه‌ي پيچيده با تعداد زياد مينيمم محلي است. از آنجایی که الگوریتمPSO در اصل برای حل مسائل پیوسته توسعه داده شده است، برای حل مسائل گسسته از قبیل زمانبندی نیاز به بازمهندسی دارد.