بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
یک الگوریتم ترکیبی جدید مبتنی بر بهینهسازي دستهجمعی ذرات و الگوریتم فرهنگی براي محیطهاي پویا
چکیده
بسیاري از مسائل بهینهسازي در دنیاي واقعی پویا میباشند . در اینگونه مسائل، بهینه در طول زمان تغییر پیدا میکند. در این نوع مسائل علاوه بر پیدا کردن بهینه سراسري میبایست آن را در طول زمان دنبال کرد.
در این مقاله، الگوریتم ترکیبی جدیدي مبتنی بر الگوریتم دستهجمعی ذرات و الگوریتم فرهنگی براي محیطهاي پویا پیشنهاد شده است. ایده اصلی مطرح شده در این مقاله جستجوي بهینه سراسري با استفاده از الگوریتم دستهجمعی ذرات است و براي ایجاد تنوع و عدم همگرایی زودرس دستهي ذرات عملگر جهش هدایت شدهاي مبتنی بر دانش ذخیره شده در فضاي باور الگوریتم فرهنگی معرفی شده است. علاوه بر آن، با بهکار بردن دانش تاریخچهي فضاي باور الگوریتم فرهنگی، سعی در پیشبینی حرکت قلهها در طی فرآیند بهینه-سازي میکند.
نتایج حاصل از این الگوریتم ترکیبی پیشنهادي، بر روي معیار قلههاي متحرك ارزیابی شده و با نتایج حاصل از چندین الگوریتم معتبر مورد مقایسه قرار گرفته است. نتایج بهدست آمده نشان دهندهي کارائی بالاي الگوریتم ترکیبی پیشنهادي در مقایسه با سایر الگوریتمها میباشد.
کلمات کلیدي
محیطهاي پویا، الگوریتم بهینهسازي دستهجمعی ذرات، الگوریتم فرهنگی، فضاي باور، معیار قلههاي متحرك.
Particle swarm optimization, Cultural Algorithms, Dynamic
Environments, Moving peak Benchmark.
.1 مقدمه
یافتن بهترین راهحل براي مسائل دنیاي واقعی امروزه مورد توجه بسیاري از محققین قرار گرفته شده است. از آنجا که این مسائل ماهیت پویا دارند و محیط در حال تغییر ممکن است بهینه آن نیز تغییر کند، در این مسائل معمولاً چندین بهینه محلی وجود دارد که یکی از آنها بهینه سراسري است. بنابراین، الگوریتمها باید سعی در دنبال کردن بهینه سراسري داشته باشند. از آنجا که اکثر الگوریتمها مانند الگوریتم بهینهسازي دستهجمعی ذرات به سمت بهینه حرکت میکنند، به نظر انتخاب خوبی براي این مسائل محسوب میشوند ولی مشکل این الگوریتم ها این است که سرانجام به یک بهینه همگرا میشوند. بنابراین، تنوع لازم را در محیط از دست میدهند. در صورت تغییر در محیط
همگرا شدن به نقطه بهینه جدید در صورت امکان بسیار زمانگیر است. یک روش مناسب براي سرعت بخشیدن بر فرآیند بهینهسازي پس از تغییر محیط، استفاده از اطلاعات و دانش ذخیره شده جستجوهاي قبلی میباشدام. ا اگر محیط بسیار شدید تغییر کند، استفاده از دانش گذشته میتواند موجب انحراف بهینهسازي شود و در آن مورد به نظر میرسد استراتژي شروع مجدد، بهترین روش باشدام. ا معمولاً در اکثر مسائل تغییرات، شدید و عمده نمیباشد.
الگوریتم بهینهسازي دستهجمعی ذرات یا 1PSO، در سال 1995 توسط Kennedy و Eberhart معرفی شد .[1] این یک الگوریتم بهینهسازي است که از روي زندگی جمعی و گروهی پرندگان الهام میگیرد تا به راه حل بهینه برسد. تاکنون نسخههاي متعددي از آن براي بهینهسازي در محیطهاي ایستا و پویا معرفی شده است. یک مشکل اساسی این الگوریتم از دست دادن تنوع پس از مدتی است که باعث همگرایی زودرس و گیر افتادن در بهینه محلی میشود و مشکل دیگر بهخصوص براي محیطهاي پویا، بلا استفاده شدن حافظه پس از تغییر محیط میباشد. راهحلهاي متنوعی براي حل این دو مشکل پیشنهاد شده است که در بخشهاي بعدي به آنها اشاره میشود.
الگوریتمهاي فرهنگی2 توسط Reynolds در سال 1994مطرح شد. این الگوریتم از تکامل فرهنگ انسانها و تأثیر پذیري افراد یک جامعه از آن و اثر آن در ایجاد نسلهاي آینده الهام گرفته شده است. این الگوریتم از حوزه دانش براي فرآیند جستجو استفاده میکند. اضافه شدن حوزه دانش در بهبود کارائی الگوریتمهاي تکاملی مؤثر است و فرآیند جستجو را هوشمندانهتر می کند. در-واقع، اضافه شدن حوزه دانش مکانیزمی براي کاهش فضاي جستجو از طریق هرس کردن قسمتهاي نامناسب آن میباشد .[2] این الگوریتم داراي دانشهاي مختلفی در فضاي باور خویش است که به امر جستجو کمک میکند. در بخشهاي آتی به تفصیل به آنها میپردازیم.
در این مقاله، یک الگوریتم بهینهسازي ترکیبی مبتنی بر الگوریتم بهینهسازي دستهجمعی ذرات و الگوریتم فرهنگی پیشنهاد شده است، که در این الگوریتم با توجه به ایجاد تنوع در محیط و عدم همگرایی زودرس، جهش هدایت شدهاي مبتنی بر دانش ذخیره شده در فضاي باور الگوریتم فرهنگی طراحی شده است، که باعث حفظ تنوع مناسب ذرات در جمعیت میشود. علاوه بر آن، با بهکار بردن دانش تاریخچهي فضاي باور الگوریتم فرهنگی، سعی در پیشبینی حرکت قلهها پس از تغییر محیط در طی فرآیند بهینهسازي میکند.
الگوریتم پیشنهادي با یک جمعیت بر روي سناریوهاي مختلف معیار قلههاي متحرك([3] (3MPB، که از معروفترین بنچماركهاي محیطهاي پویا است بهکار رفته و کارائی آن با الگوریتمهاي [4] mQSO، [5] CellularPso و [6] Adaptive mQSO مقایسه شده است. نتایج آزمایشات نشان میدهد که الگوریتم پیشنهادي با توجه به تک جمعیتی بودن آن از کارایی قابل قبولی بر خوردار است.
ادامه این مقاله بدین ترتیب سازماندهی شده است: در بخش دوم مروري بر الگوریتم بهینهسازي دستهجمعی ذرات (PSO) و کارهاي انجام شده قبلی براي انطباق با محیطهاي پویا مطرح میشود. در بخش سوم به الگوریتمهاي فرهنگی و قسمتهاي مختلف آن پرداخته میشود. در بخش چهارم الگوریتم پیشنهادي طرح میگردد. در بخش پنجم نتایج آزمایشات مورد بررسی قرار میگیرند و بخش نهایی به بیان نتیجهگیري میپردازد.
.2 الگوریتم بهینه سازي دسته جمعی ذرات
این الگوریتم با یک گروه از جوابهاي تصادفی شروع بهکار میکند. سپس براي یافتن جواب بهینه در فضاي مسئله با بهروز کردن موقعیت و سرعت هر ذره به جستجو میپردازد. هر ذره بهصورت چند بعدي با دو مقدار Xij و Vij که به ترتیب معرف مکان و سرعت مربوط به بعد j ام از i امین ذره هستند تعریف میشود. در هر مرحله از حرکت جمعیت، هر ذره با توجه به دو مقدار بهترین بهروز میشود. اولین مقدار بهترین جواب از لحاظ شایستگی است که تاکنون براي هر ذره به طور جداگانه بهدست آمده است. این مقدار بهترین تجربه فردي است که pbest نامیده میشود. مقدار بهترین دیگر که توسط PSO بهدست میآید، بهترین مقداریست که تاکنون توسط تمام ذرهها در میان جمعیت به-دست آمده است. این مقدار بهترین تجربه گروهی است که gbest نامیده میشود. پس از یافتن دو مقدار pbest و gbest هر ذره سرعت و مکان جدید خود را با دو رابطه زیر بهروز میکند:
به طوريکه w وزن اینرسی، c1 و c2 ضرایب شتاب و r1 و r2 اعداد تصادفی در بازه 1)و(0 میباشند.
.1-2 الگوریتم بهینه سازي دسته جمعی ذرات در محیط هاي پویا
تحقیقات متعددي در زمینه بهینهسازي Pso در محیطهاي پویا انجام گرفته است. Blackwell و Branke در مراجع [7] و [8] روش چند دستگی ذرات، استفاده از مفاهیم ضدهمگرایی و انحصار با هدف پوشش قلههاي مختلف و نیز ایجاد تنوع در محیط را معرفی کردند .[7]
Lung و Dumitrescu دو جمعیت با اندازههاي برابر براي شناسایی و دنبال کردن بهینه متحرك در محیطهاي پویا معرفی کردند که یکی از این جمعیتها مسئول حفظ تنوع در فضاي جستجو می باشد و جمعیت دیگر مسئول پیدا کردن بهینه سراسري میباشد. حفظ تنوع در جمعیت، با بهکار بردن الگوریتم تفاضلات تکاملی مبتنی بر ازدحام4 که براي بهینهسازي چند هدفه بهکار می-رود، صورت میپذیرد در حالیکه Psoمستقیماً براي پیدا کردن بهینه سراسري مورد استفاده قرار میگیرد .[9]
هاشمی و میبدي در مرجع [5] ، با بهرهگیري از تعاملات محلی در اتوماتاي سلولی و تقسیم کردن جمعیت ذرات در داخل سلول هاي اتوماتاي سلولی و مشخص کردن تعداد معینی ذره در هر سلول سعی بر حفظ تنوع در جمعیت نمودند.
Moyed Daneshyari و Gary G.yen در مرجع [10]، روش ترکیبی مبتنی بر الگوریتم فرهنگی و الگوریتم دستهجمعی ذرات را معرفی کردند که در آن روش، الگوریتم فرهنگی به عنوان چارچوبی اطلاعاتی براي Pso نقشآفرینی میکند. این روش پیشنهادي از دانشهاي موجود در الگوریتم فرهنگی براي تشخیص تغییرات محیط، زمان مهاجرت بین دستههاي ذرات و دافعهي بین ذرات براي حفظ تنوع و انتخاب ذرات در سه سطح شخصی، محلی و سراسري بهره میبرد.
.3 الگوریتم فرهنگی
یک سیستم دوگانه وراثتی است، که دو فضاي جستجو را ارائه میدهد. یکی فضاي جمعیت5 که بر مبناي نظریه ژنتیکی داروین است و دیگري فضاي باور6 که یک قسمت از فرهنگ را ارائه میکند، که این مورد، وجه تمایز بین الگوریتم ژنتیک با الگوریتم فرهنگی است .[2]
فضاي باور، در واقع اطلاعات فرهنگ افراد را مدل میکند. فضاي جمعیت، افراد را در سطح ژنوتایپی7 یا فنوتایپی8 ارائه میدهد. هر دو فضا بهصورت موازي با هم کار میکنند و بر روي هم تأثیر میگذارند.
براي ارتباط دادن بین این دو فضا یک پروتکل ارتباطی تعریف میشود. یکی براي انتخاب گروهی از افراد تا فضاي باور را شکل دهند و دیگري روشی براي تأثیر این فضاي باور بر روي تولید افراد در فضاي جمعیت است.
بهطور کلی الگوریتم فرهنگی بهصورت زیر عمل میکند:
در هر نسل ابتدا افراد مانند الگوریتم ژنتیکی در فضاي جمعیت وارد شده و توسط تابع شایستگی9 ارزیابی میشوند. سپس توسط تابع پذیرش10 افرادي را که مناسب شکل دادن به فضاي باور است را انتخاب میکند و تجربیات پذیرفته شده افراد، براي ساختن و تغییر فضاي باور بهکار برده میشود (در اینجا فرهنگ شبیهسازي میشود).
فرهنگ ایجاد شده در فضاي باور، بر روي تکامل جمعیت در فضاي جمعیت تأثیر میگذارد. این تأثیر با تغییر دادن عملگر جهش11 و اعمال آن عملگر در تولید فرزندان صورت میگیرد.
اجزاي الگوریتم فرهنگی بهصورت زیر میباشد:
• فضاي جمعیت
• فضاي باور
• تابع پذیرش
• تابع تأثیر12
که هر کدام در بخشهاي آینده شرح داده خواهد شد.
.1-3 فضاي جمعیت
این فضا در واقع فضاي اصلی جمعیت میباشد و با مقدار دهی اولیه کار خود را شروع کرده و استخراج فرهنگ و ذخیرهي آن در فضاي باور در این قسمت انجام میگیرد.
.2-3 فضاي باور
در فضاي باور، تجربیات عمومی شده افراد موفق از فضاي جمعیتی ، بهدست آمده و این تجارب در سراسر نسل و نسلهاي بعدي شکل گرفته و ذخیره می-شود. این تجارب بر تمامی نسلها تأثیرگذار است و به نسلهاي آینده منتقل میگردد.
درواقع، این فضا براي هرس کردن فضاي جمعیت مؤثر است. هر فرد یک ذره در فضاي جستجو است که فضاي باور براي دور ساختن افراد از ناحیههاي نامطلوب و سوق دادن آنها به سمت ناحیههاي امیدبخش و نزدیک به جواب بهکار برده میشود .[11][2]
دانشهاي مختلفی فضاي باور را تشکیل میدهند که به شرح زیر است:
• دانش موقعیتی13
• دانش معیار14
• دانش تاریخچه15
دانشهاي دیگري نیز به مرور براي کاربردهاي مختلف ایجاد شد [12] که در این مقاله از سه مورد بالا استفاده میشود.
.1-2-3 این قسمت از فضاي باور بهترین راهحلهاي پیدا شده در هر نسل را ذخیره میکند. این قسمت از دانش براي بهینهسازي توابع اعداد حقیقی در محیطهاي ایستا معرفی شد [13]، که شامل تعدادي از افراد خوب است که بهترین آنها براي تأثیر گذاري در تولید نسل بعدي در نظر گرفته میشود. در
اینجا دانش موقعیتی شامل بهترین ذره سراسري است((s={pgd}، و طبق رابطه زیر بهروز میشود:
.2-2-3 دانش معیار
این منبع دانش، مجموعه بازههاي خوب و امیدبخش را که از مجموعه اي از ذرات خوب استخراج شده است، براي هر بعد از مسئله نگهداري میکند. این دانش طبق رابطه زیر میباشد:
در اینجا، D معرف تعداد ابعاد مسأله است و هر Xi بهصورت زیر تعریف میشود:
در اینجا li و ui به ترتیب حد بالا و حد پایین بعد iام میباشند، Li و Ui مقدار تابع شایستگی در آن حدود میباشد .[15][14]
دانش معیار طبق روابط زیر بهروز میشود:
طبق این دانش، فضاي جستجو رفتهرفته کوچکتر و به ناحیههاي خوب نزدیکتر میشود.
.3-2-3 دانش تاریخچه
این دانش اولین بار براي محیطهاي پویا پیشنهاد شد .[16] هدف از این دانش پیداکردن الگوي تغییرات محیط بود. دانش تاریخچه لیستی از محل و مقدار بهترین فرد پیدا شده تا قبل از تغییر محیط جاري را نگهداري میکند . براي بهروز درآوردن این دانش، بهینه پیداشدهي جاري قبل از تغییر محیط به لیست اضافه میگردد. در این مقاله از این دانش براي پیشبینی حرکت آینده قلهها استفاده میشود.
.3-3 تابع پذیرش
این تابع افراد شایسته را در هر نسل براي شکلدهی به فضاي باور، انتخاب میکند. در مرجع [16]، تعداد افراد انتخابی بهصورت پویا طبق رابطه زیر پیشنهاد شد:
که در آن paccept پارامتري تجربی است که در این مقاله 0.2 فرض شده است. g شمارنده نسل است و در محیطهاي پویا پس از تغییر محیط، g به 1 مقداردهی میشود. popsize نیز تعداد کل فضاي جمعیت میباشد.
.4-3 تابع تأثیر
باورها درفضاي باور براي تغییر دادن افراد و نزدیک کردن آنها به باور سراسري (بهینه کل) بهکار برده میشوند که این تغییرات با استفاده از تابع تأثیر، تحقق مییابد .[2]
فضاي باور با استفاده از عملگر جهش بر روي فضاي جمعیت تأثیر میگذارد، این تأثیر از دو راه ممکن است یکی اندازه جهش و دیگري جهت جهش می باشد. در این مقاله سعی شده است با توجه به دانش موقعیتی و دانش معیار از مراجع [2] و [15] تابع تأثیر استخراج
