بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
کاربرد الگوریتم بهینه سازي PSO در بهینه سازي چندهدفه بهره برداري از مخازن سدها
خلاصه
بهرهبرداري از مخازن سدها همواره از مسائلی بوده است که بهینه کردن توابع هدف متضاد در آنها مد نظر بوده است. کاربرد روشهاي تکاملی در بهینه سازي بهره برداري از سدها در دو دهه اخیر مورد توجه بسیاري از محققین قرار گرفته است. از روشهاي نوین در این دسته، روش بهینهسازي دسته ذرات(PSO) 1 است که تاکنون بیشتر براي حل مسائل تک هدفه مورد استفاده قرار گرفته است. در این مقاله سعی شده است تا با استفاده از رویکردي نوین، الگوریتم بهینهسازي PSO براي حل مسئله بهینه سازي چند هدفه بهرهبرداري از مخزن مورد استفاده قرار گیرد. لزوم یافتن جوابهاي غیر پست با تنوع بالا و یافتن بهینه فراگیر2 مناسب براي دسته ذرات در الگوریتم چندگانه PSO، از جمله مواردي هستند که در این تحقیق مورد بحث و بررسی قرار گرفته اند. کاربرد این روش در مورد بهره برداري بهینه از سد سفیدرود با درنظر گرفتن دو هدف تامین نیاز پائیندست و تخلیه رسوب مورد بررسی قرار گرفته است.
کلمات کلیدي : الگوریتم بهینه سازي چندگانه PSO، مسائل چندهدفه، جبهه پارتو، بهرهبرداري از مخازن سدها
1. مقدمه
در دهههاي اخیر همزمان با مطرح شدن مسائل بهینهسازي جدید روشهاي جدید بهینهسازي نیز ابداع شدند. مهمترین گروه از این روشهاي بهینهسازي روشهاي تکاملی میباشند که توانایی حل مسائل با ابعاد بزرگ و تعداد متغیرهاي زیاد را دارا هستند. از سوي دیگر مسائل مورد توجه در مدیریت منابع آب از مسائلی هستند کهغالباً داراي تعداد متغیرهاي تصمیم زیاد هستند و بهینهسازي توابع هدف غیرخطی کهبعضاً در تضادي با یکدیگر نیز هستند در آنها مطرح است. از این رو استفاده از روشهاي تکاملی چندگانه در این گونه مسائل در سالهاي اخیر مورد توجه قرار گرفته است. در سالهاي اخیر در حل مسائل تکهدفه مهندسی آب از الگوریتم PSO استفادههاي زیادي شده است با این حال به دلیل نو بودن الگوریتمهاي چندگانه دسته ذرات3 (MOPSO) در مسائل چندهدفه آب، از این روش استفاده چندانی نشده است. Gill و همکاران [1] (2006) از MOPSO براي تخمین پارامترهاي یک مدل بارش-رواناب Sacramento با 13 پارامتر استفاده نمودند. همچنین براي کالیبره کردن یک مدل برداري با سه پارامتر براي پیش بینی رطوبت خاك از MOPSO استفاده کردند.
Reddy و Kumar در سال [2] 2007 براي حل مسائل چند هدفه بهره برداري از مخزن روش EM-MOPSO را پیشنهاد کردند. این نوع از PSO براي یافتن راه حل مناسب از یک آرشیو خارجی با اندازه متغیر استفاده می¬کند. Baltar و [3] Fontane در سال 2008 از MOPSO براي حل مسائل چند هدفه استفاده نمودند و کاربرد آن را در سه جنبه بررسی کردند: -1 حل توابع نمونه براي مقایسه با نسخه هاي دیگر MOPSO و
نیز الگوریتم هاي دیگر، -2 مسئله بهره برداري ازمخزن چند کاربرده با چهار تابع هدف و -3 بهره برداري کیفی از مخزن سد با سه تابع هدف. الگوریتم مربوطه با استفاده از یک آرشیو خارجی جواب هاي غیر پست را ذخیره می¬کند و بر اساس جبهه پارتو آنها را مقایسه می¬کند. نتایج به دست آمده با نتایج حاصل از روش قید ε با بهینه سازي غیر خطی ( ( ε-NLP مقایسه شده است. [4] Liu با استفاده از ترکیب عملگرهاي مختلف به کار رفته در NSGA-II (مرتب کردن بر اساس غیر پستی، مرتب کردن بر اساس فاصله ازدحام و نخبه گرایی) و همچنین یک عملگر جهش در PSO، یک مدل بارش-رواناب را بهینه سازي کرد. مدل بارش-روانابی که وي به کار برد مدل NAM است که MIKE11 نیز از آن استفاده می¬کند. توابع هدف
c1 c2 ≤ 4
مورد استفاده در مدل وي، مجموع مربعات اختلاف دبی پیک مشاهداتی و دبی هاي پیک شبیه سازي شده و نیز مجموع مربعات اختلاف دبی حداقل مشاهداتی و دبی هاي حداقل شبیه سازي شده می¬باشند که باید کمینه گردند. وي نتایج کاربرد این مدل براي یک حوضه آبریز واقعی را با الگوریتم
NSGA-II مقایسه کرد که نتایج به دست آمده حاکی از بهبود جوابها به ویژه در پراکندگی و تنوع جوابهاي غیرپست بود. در ادامه این مقاله، جزئیات الگوریتم MOPSO مورد استفاده در این تحقیق و نتایج کاربرد آن براي بهینه سازي بهره برداري از مخزن ارائه شده است.
2. الگوریتم بهینه سازي دسته ذرات
الگوریتم دسته ذرات اولین بار در سال 1995 توسط Kennedy و [5] Eberhart مطرح شد. در تدوین این روش از پرواز گروهی پرندگان و شناي گروهی ماهی ها و زندگی اجتماعی آنان الهام گرفته شده که با استفاده از یک سري روابط ساده فرمول بندي شده است. مانند همه الگوریتم هاي تکاملی دیگر، الگوریتم دسته ذرات نیز با ایجاد یک جمعیت تصادفی از افراد شروع می¬شود که در اینجا به عنوان یک گروه از ذره ها خوانده می-
شوند. مشخصات هر ذره در گروه، براساس مجموعه اي از پارامترها تعیین می¬شود که باید مقادیر بهینه آنها تعیین شود. در این روش، هر ذره یک نقطه از فضاي جواب مسئله را نشان می¬دهد. هر کدام از ذرات داراي حافظه هستند، یعنی بهترین موقعیتی که در فضاي جستجو به آن می¬رسند را به خاطر می¬سپارند. بنابراین حرکت هر ذره در دو جهت صورت می¬گیرد: -1 به سوي بهترین موقعیتی که تاکنون اختیار کرده اند و -2 به سوي بهترین موقعیتی که همه ذرات تا به حال اختیار کرده اند. در این روش، تغییر موقعیت هر ذره در فضاي جستجو تحت تاثیر تجربه و دانش خود و همسایگانش است.
فرض کنید در یک مسئله خاص، فضایی D بعدي داریم و i امین ذره از گروه می¬تواند با یک بردار سرعت و یک بردار موقعیت نمایش داده شود. تغییر موقعیت هر ذره با تغییر در ساختار موقعیت و سرعت قبلی امکان پذیر است. هر ذره، اطلاعاتی شامل بهترین مقداري که تاکنون به آن رسیده (بهینه شخصی(1 و موقعیت X t را داراست. این اطلاعات، حاصل مقایسه تلاش هایی است که هر ذره براي یافتن بهترین جواب انجام می¬دهد.
همچنین هر ذره بهترین جوابی را که تا کنون در کل گروه بدست آمده است، از مقایسه مقادیر بهینه ذرات مختلف می¬شناسد ( بهینه فراگیر.(2 هر ذره
براي رسیدن به بهترین جواب سعی می¬کند موقعیت خود را با استفاده از اطلاعات زیر تغییر دهد:
• موقعیت کنونی ( ( X t • سرعت کنونی ( (V t
• فاصله بین موقعیت کنونی و بهینه شخصی • فاصله بین موقعیت کنونی و بهینه فراگیر
بدین ترتیب سرعت هر ذره و به تبع آن موقعیت جدید آن به صورت زیر تغییر می¬کند:
که در آن: سرعت ذره i در تکرار جدید، Vit سرعت ذره i در تکرار فعلی، X it موقعیت کنونی ذره، X it 1 موقعیت ذره در تکرار جدید، pbesti بهترین موقعیتی که ذره i تا کنون اختیار کرده است و gbestt بهترین موقعیت بهترین ذره (بهترین موقعیتی که تمام ذرات تا کنون اختیارکرده اند) است. rand (0,1) یک عدد تصادفی بین صفر و 1 است که براي حفظ تنوع و گوناگونی گروه به کار می¬رود. c1 و c2 به ترتیب پارامترهاي شناختی و اجتماعی هستند. انتخاب مقدار مناسب براي این پارامترها منجر به تسریع همگرایی الگوریتم و جلوگیري از همگرایی زودرس در بهینه هاي محلی می¬شود. تحقیقات اخیر نشان می¬دهد که انتخاب مقدار بزرگتري براي پارامتر شناختی c1 نسبت به پارامتر اجتماعی c2 مناسب تر است، اما بایستی همواره شرط رعایت شود. پارامتر w اینرسی وزنی نام دارد که براي تضمین همگرایی در دسته ذرات به کار می¬رود. اینرسی وزنی، جهت کنترل تاثیر سوابق سرعت هاي پیشین بر سرعت هاي جاري مورد استفاده قرار می¬گیرد. بر اساس تحقیقات انجام شده، مقداري بین 0/4 و 0/7 براي w مناسب است.
3. مسائل چند هدفه و مفهوم بهینه پارتو
در مسائل چند هدفه به جاي یک تابع هدف، چندین تابع هدف باید بصورت همزمان بهینه شوند. در چنین شرایطی معمولاً مسئله داراي بیش از یک جواب بهینه خواهد بود که به آنها جوابهاي بهینه پارتو گفته می شود. مفهوم بهینه پارتو به این صورت قابل تشریح است که ( یک بهینه پارتو است اگر براي هر دیگر عضو دامنه مجاز و داشته باشیم ( براي یک مسئله کمینه سازي )
که در آن n تعداد متغیرهاي فضاي تصمیم و k تعداد توابع هدف است. به عبارت دیگر x* یک بهینه پارتو است اگر هیچ بردار x دیگري وجود نداشته باشد که به ازاي بهبود بخشیدن برخی از توابع هدف حداقل یک تابع هدف را بدتر نکند. جوابهاي بهینه پارتو تحت عنوان جوابهاي غیر پست نیز شناخته می شوند.
4. الگوریتم به کار رفته در این تحقیق
در سال 2005، Raquel و[6] Naval نوع جدیدي از الگوریتم دسته ذرات چند هدفه به نام MOPSO-CD2 را پیشنهاد کردند. همان طور که می¬دانیم مکانیسم فاصله ازدحام3 اولین بار توسط Deb و همکاران (2002) [7] ارائه شد و در الگوریتم NSGA-II به کار برده شده است. در MOPSO-CD هم از این روش براي یافتن پاسخ هاي بهینه و نیز حذف جوابهاي غیر پست در هنگامی که آرشیو پر است استفاده می¬شود. فرایند فاصله ازدحام همراه با یک اپراتور جهش موجب می¬شود تا تنوع جوابهاي غیر پست در سرتاسر فضاي ممکن جوابها حفظ شود. همچنین نسبت به سایر الگوریتم ها (مانند (NSGA-II، این الگوریتم در یافتن تمام جوابهاي غیر پست در فضاي جستجو قوي تر است، که ویژگی مذکور به خاطر استفاده از آرشیو خارجی (آرشیوي از جوابهاي غیر پست که در گذشته پیدا شده اند) و همچنین به خاطر نوع اپراتورجهش آن است. اپراتور جهش باعث می¬شود تا قابلیت جستجوي الگوریتم بالا رود و از همگرایی زودهنگام آن جلوگیري شود. همچنین کاربرد روش فاصله ازدحام در این الگوریتم در مقایسه با کاربرد شبکه سازگار4 در Coello) MOPSO و همکاران ([8] باعث یافتن تنوع و توزیع بهتري از جواب هاي غیر پست شده است. در ادامه به توضیح بیشتر اجزاء این الگوریتم می¬پردازیم.
مقدار فاصله ازدحام براي هر جواب تخمینی از چگالی جوابها در اطراف آن است. براي محاسبه فاصله ازدحام ابتدا جوابها را بـر حسـب یکـی از توابع هدف به صورت نزولی مرتب می¬کنیم. براي محاسبه فاصله ازدحام منتسب به هر نقطه روي یک جبهه مشخص، نقاط قبل و بعـد نسـبت بـه توابـع هدف مسئله انتخاب و مطابق شکل (1) یک مستطیل (در سطح دو بعدي) تشکیل می¬شود. بدیهی است در صـورتی کـه تعـداد توابـع هـدف بـیش از 2 باشد، نقاط مورد نظر یک مکعب تشکیل خواهند داد.
همانطور که در این شکل نشان داده شده، اعداد واقع بر جبهه پارتو، به شکل توپر دیده می¬شوند و سایر جواب ها با دایره هاي توخالی نمایش داده شده اند. براي محاسبه فاصله ازدحام جواب iام در این شکل، مستطیلی ترسیم شده که جواب هاي بعدي و قبلی نسبت به دو تابع هدف، در گوشه هاي آن قرار گرفته اند. فاصله ازدحام براي این نقطه معادل متوسط اضلاع این مستطیل است. هرچه فاصله ازدحام کمتر باشد، نشان دهنده تراکم بیشتر جوابها است. لازم به ذکر است در شرایطی که مسئله داراي بیش از دو تابع هدف باشد، نقاط i-1 و i+1 براي تمام توابع هدف یکسان نخواهد بود.
5. انتخاب پاسخ هاي بهینه فراگیر
انتخاب مناسب پاسخ هاي بهینه فراگیر در الگوریتم دسته ذرات چند هدفه یک مرحله مهم محسوب می¬شود، چون تابع قابلیت همگرایی الگوریتم و توانایی آن در دست یابی به مجموعهاي متنوع از جوابهاي غیر پست در فضاي تصمیم است. در MOPSO-CD، یک آرشیو خارجی محدود، جوابهاي غیر پست را ذخیره می¬کند. براي یافتن پاسخ هاي بهینه، دسته ذرات باید در نقاط مشخص متراکم نشود تا بتواند همه فضاي جستجو را پوشش دهند. براي این منظور، در این روش به جواب هاي غیر پستی که مقدار فاصله ازدحام بیشتري دارند، اولویت بیشتري داده می¬شود. در آرشیو خارجی، جواب هاي غیر پست بر اساس مقدار فاصله ازدحام و به صورت نزولی مرتب میشوند. آنگاه در هر مرحله از چند جواب بالاي آرشیو ( مثلا
10 درصد بالاي آرشیو) یکی به طور تصادفی انتخاب میشود. این ترتیب نزولی در آرشیو خارجی در جاي دیگر نیز ما را یاري میکند و آن هنگامی
است که آرشیو پر باشد. در چنین مواقعی از جوابهاي غیر پست پائین آرشیو ( مثلا 10 درصد پائین) یکی به صورت تصادفی انتخاب میشود و جواب غیر پست جدید که در تکرار اخیر پیدا شده است جایگزین آن می¬شود. شکل (2) خلاصه مراحل این الگوریتم را نشان می¬دهد.
شکل -1 نحوه محاسبه فاصله ازدحام در یک مسئله دو هدفه حداقل سازي (Deb 2002)
