سیدی, ایمان, براتی, محمد, مغفوری فرسنگی, ملیحه, نظام آبادی پور, حسین. (1390). یک رهیافت جدید برای جایگاه یابی مسائل چند مدی با استفاده از الگوریتم بهبود یافته جهش قورباغه. هوش محاسباتی در مهندسی برق, 2(1), 45-56.
ایمان سیدی; محمد براتی; ملیحه مغفوری فرسنگی; حسین نظام آبادی پور. "یک رهیافت جدید برای جایگاه یابی مسائل چند مدی با استفاده از الگوریتم بهبود یافته جهش قورباغه". هوش محاسباتی در مهندسی برق, 2, 1, 1390, 45-56.
سیدی, ایمان, براتی, محمد, مغفوری فرسنگی, ملیحه, نظام آبادی پور, حسین. (1390). 'یک رهیافت جدید برای جایگاه یابی مسائل چند مدی با استفاده از الگوریتم بهبود یافته جهش قورباغه', هوش محاسباتی در مهندسی برق, 2(1), pp. 45-56.
سیدی, ایمان, براتی, محمد, مغفوری فرسنگی, ملیحه, نظام آبادی پور, حسین. یک رهیافت جدید برای جایگاه یابی مسائل چند مدی با استفاده از الگوریتم بهبود یافته جهش قورباغه. هوش محاسباتی در مهندسی برق, 1390; 2(1): 45-56.
یک رهیافت جدید برای جایگاه یابی مسائل چند مدی با استفاده از الگوریتم بهبود یافته جهش قورباغه
: مسأله جایگاه یکی از روش‌های مهم برای بهینه سازی مسایل چند مدی است. بیشتر روش‌های موجود در مسأله جایگاه نیاز به تعیین دقیقی از پارامترهای جایگاه به منظور عملکرد بهتر دارد. مشکل اصلی الگوریتمهای ابتکاری در حل مسائل چند بعدی قدرت همگرایی آنها به یک جواب (عموماً بهینه فرا محلی) است. الگوریتم جهش قورباغه، از جمله الگوریتمهای ابتکاری است که در سالهای اخیر تا کنون نسخه‌ای از آن برای حل مسائل چند مدی ارائه نشده است. در این مقاله نسخه‌ای از این الگوریتم برای حل مسائل چند مدی با حفظ ساختار‌های اساسی ارائه و با روش‌های مطرح مقایسه شده است. نتایج آزمایش‌ها روی توابع محک استاندارد توانایی الگوریتم پیشنهادی را تأیید میکند.
A new niche technique for multimodal function optimization using Shuffled Frog leaping algorithm
نویسندگان [English]
Eman Sayedi1؛ mohammd Barati1؛ Malihe Maghfoori Farsangi2؛ Hossen Nezamabadi2
1Department of electrical engineering, Faculty of Engineering, Shahid Bahonar University, Kerman, Iran
2Department of electrical engineering, Faculty of Engineering, Shahid Bahonar University, Kerman, Iran
چکیده [English]
The niche methods for search algorithms are important techniques in optimization. Most niche techniques need some extra tunable parameters to get a better performance. Achieving a good method for multimodal optimization by heuristic algorithms will be possible if and only if the population diversity is preserved. Shuffled Frog leaping (SFL) algorithm is a new heuristic algorithm that its ability is not proved for solving the multimodal problems. This paper proposes a niche method for SFL. Several benchmark problems are considered for testing the robustness and effectiveness of the proposed method over the results available in the literature. The results show that the proposed method performs well.
کلیدواژه‌ها [English]
Shuffled Frog leaping, Hill-Valey Function, Nich the Cnigues
اصل مقاله
مقدمه
در سالهای اخیر الگوریتمهای جستجوی تصادفی، از جمله الگوریتمهای تکاملی، در حل بسیاری از مسائل دشوار بهینه سازی استفاده شده اند. شکلهای استاندارد این الگوریتم‌ها معمولاً برای پیدا کردن یک بهینه (بهینه فرامحلی Global optimum[1]) طراحی شده‌اند. با وجود این بسیاری از مسائل دنیای واقعی ذاتاً به صورت چند مدی هستند به طوری که چندین نقطه بهینه برای حل آنها وجود دارد. برای حل مسائل بهینه‌سازی با چندین بهینه محلی و فرامحلی ممکن است به مشخص کردن مکان تمامی بهینهها نیاز باشد. در گذشته تکنیکهای زیادی برای پیدا کردن این مکانها ارائه و توسعه یافته‌اند. مسأله جایگاهیکی از روش‌های مهم برای بهینه سازی مسائل چند مدی[1]است. روش‌های جایگاه یابی حتی برای زمانی که هدف پیدا کردن یک نقطه بهینه فرامحلی است مؤثر واقع میشوند. از آنجایی که این روش‌ها به جستجوی موازی چندین بهینه در فضای مسأله میپردازند، لذا الگوریتم کمتر، در بهینههای محلی گیر میکند. موفقیت الگوریتمهای تکاملی در کاربردهای دنیای واقعی با استفاده از روش‌های جایگاه یابی همراه شده است [21-1]. همچنین برای حفظ کردن تنوع جمعیت در الگوریتمهای تکاملی از روش‌های جایگاه یابی استفاده شده است. برای معرفی این روش‌ها، میتوان به روش ازدحامی[2] [5]، روش ازدحامی قطعی[3] [6]، روش تسهیم شایستگی[4][7]، روش جایگاه یابی ترتیبی[5][8]، روش انتخاب رقابت محدود شده[6] [9]، روش موازی سازی[7] [10]، روش خوشه‌بندی[8] [11]، روش پاکسازی[9] [12]، روش حفظ گونه[10][13]، اشاره کرد. عموماً پارامترهای جایگاه برای تعیین کردن فاصله بین دو بهینه نزدیک به هم استفاده میشوند. مثال مشخصی از این موضوع میتوان به در روش تسهیم شایستگی اشاره کرد [7]. دیگر استفادههایی که از پارامترهای جایگاه میشود، انتخاب در روش ازدحامی [5]، مقدار در روش انتخاب مسابقهای محدود شده [9] یا میانگینهای دستهها در روش خوشه بندی است [11و7]. دلایل ارائه روش جدید در مقاله برای حل مسائل چند مدی به شرح زیر است:
1- دشواری در حفظ کردن جوابهای پیدا شده در یک بار اجرای مسأله: برای مثال، روش ازدحامی دی جانگ نمی تواند تمامی قلهها را در تکرارهای رو به جلو حفظ کند [6]. یک الگوریتم جایگاه خوب باید قادر به حفظ کردن و نظم دادن به جوابهای پیدا شده باشد.
2- در روش‌های مرسوم جایگاه میتوان مشاهده کرد که عمل همبری بین دو فرد شایسته از جمعیت در دو جایگاه متفاوت ممکن است باعث تولید یک نوزاد با شایستگی پایین تر از والد شود[3].
3- بعضی از روش‌های جایگاه فقط برای مشخص کردن تمام بهینه فرامحلی طراحی شده اند و از تعیین بهینههای محلی چشم پوشی شده است. برای مثال، در روش‌های جایگاه ترتیبی GA [8]،پاکسازی [12]، SCGA [13]، NichePSO [14]، SPSO [16و15] این امر اتفاق میافتد.
4- پیچیدگی محاسبات بالا. بیشتر روش‌های مربوط به جایگاه به جز روش ازدحامی قطعی از این عیب رنج میبرند. با این حال، بسیاری از محققین بر این عقیده هستند که روش ازدحامی قطعی به تعداد ارزیابی بالایی در پیدا کردن جواب نیاز دارد [17] و از توزیع جمعیتی مناسبی برای پیدا کردن جایگاهها برخوردار نیست [18]. هدف این مقاله توسعه الگوریتم جایگاه با ارائه موارد زیر است:
1- نیازی به پارامترهای مربوط به جایگاه برای مشخص کردن فاصله بین دو نقطه بهینه یا تعدادی از بهینهها نباشد.
2- قادر به مشخص کردن چندین بهینه (بهینه محلی و فرامحلی) و حفظ کردن مکان بهینه جوابهای پیدا شده تا پایان اجرای برنامه باشد.
3- در مقایسه با روش‌هایی که همه نقاط جایگاهها را ارائه میدهند دارای پیچیدگی محاسباتی کمتری باشد.
سازماندهی مقاله به این طریق است که در بخش دوم الگوریتم جهش قورباغه متحرک بیان میشود و در بخش سوم الگوریتم جدید پیشنهادی این مقاله برای جایگاه یابی مسائل چند مدی بیان میگردد. در بخش چهارم نتایج حاصل از پیاده سازی الگوریتم پیشنهادی بر روی توابع محک استاندارد، تحلیل نتایج و مقایسه با بعضی از روش‌های موجود در حیطه مسائل مربوط به جایگاه ارائه و در بخش پنجم نتیجه گیری آورده شده است.
2- الگوریتم جهش قورباغه
الگوریتم جهش قورباغه[11] یکی از الگوریتمهای الهام گرفته از طبیعت است که توسط لنزی[12] و یوسف[13] توسعه داده شد. در این الگوریتم گروهی از قورباغهها ( مجموعهای از جوابها) به چندین زیر مجموعه[14]تقسیم میشوند، که هر قورباغه فرهنگ مختص به خود را دارد و میتواند از فرهنگ‌ها[15] یا ایدههای قورباغههای دیگر در طول روند تکامل استفاده کند [27-22]. مراحل اجرای این الگوریتم در زیر توضیح داده شده است:
2-1-تولید جمعیت اولیه
همانند تمامی الگوریتمهای شهودی[16] جمعیت اولیه (قورباغهها) به صورت تصادفی[17] بین بازه مسأله با توجه به رابطه (1) تولید میشود:
(1)
که در آن، مقدار معادل هر عضو از جمعیت، کران پایین متغیر ، کران بالای متغیر و rand یک مقدار تصادفی بین 0 الی 1 است.
هر قورباغه نمایانگر یک راه حل قابل قبول در مسأله بهینه سازی است که دارای یک مقدار شایستگی است. قورباغهها بر اساس شایستگی شان به صورت نزولی مرتب میشوند و بر اساس روندی خاص به زیر مجموعههای مختلف تقسیم میشوند که در بخش 2-2 توضیح داده شده است.
2-2- دسته بندی قورباغهها
فرض کنید که جمعیت اولیه با P قورباغه تولید شده است. با توجه به شکل(1)، P قورباغه به m مجموعه تقسیم میشوند. روند تقسیم بندی قورباغهها بدین صورت است که قورباغه اول به مجموعه اول، قورباغه دوم به مجموعه دوم و قورباغه m به مجموعه m ام و قورباغه m+1 به مجموعه اول تعلق دارند. این روند به صورت مشابه تا قورباغه آخر تکرار میشود. هر مجموعه m شامل n قورباغه است به طوری که رابطه (2) ارضا میشود:
(2) P =m×n
شکل (1): دسته بندی قورباغهها به m زیر مجموعه
2-3- مراحل جستجوی محلی در الگوریتم SFL
در هر مجموعه موقعیت قورباغه i –ام، بر اساس اختلاف بین قورباغه بهتر (با بهترین شایستگی Xb ) و قورباغه بدتر
( با بدترین شایستگی Xw) با استفاده از معادله زیر به دست می آید:
Position change: (3)
D(i) =rand()
که rand() یک عدد تصادفی یکنواخت بین 0 و1 است. موقعیت جدید قورباغه توسط رابطه (4) به دست میآید که ماکزیمم تغییراتی است که در موقعیت قورباغه میتوان اعمال کرد.
New Position:
(4)
اگر این تغییر موقعیت، قورباغه‌ای با شایستگی بهتر تولید کرد این قورباغه جایگزین قورباغه بدتر میشود. در غیر این صورت، قورباغه با بهترین شایستگی در کل جمعیت (بهینه فرامحلی[18]) Xg جایگزین Xb در معادله (3) شده و قورباغه جدیدی تولید می شود. اگر قورباغه‌ای با شایستگی بهتر تولید شود این قورباغه جایگزین قورباغه بدتر میشود. در غیر این صورت، قورباغه‌ای جدید به صورت تصادفی تولید و جایگزین بدترین قورباغه میگردد.
پس از تکامل درونی چندین نسل، تمام مجموعهها به هم آمیخته و بر اساس ارزش شایستگی آنها به صورت نزولی مرتب میشوند. سپس دوباره به چند زیر مجموعه تقسیم می‌گردند و روند تکامل در هر مجموعه تا زمانی که به معیار توقف برسد ادامه مییابد.
2-5- معایب الگوریتم SFL
در الگوریتمهای تکاملی که بر پایه جمعیت تصادفی هستند، عمدتاً دو جنبه باید بررسی شود: 1- کاوش؛ 2- بهره وری. کاوش به جستجوی بهتر فضای جستجو میپردازد و بهره وری قادر به پیدا کردن بهینه بهتر حول بهترین جواب است. نکته مهم برای داشتن عملکرد مناسب، ایجاد مصالحه بین کاوش و بهره وری است. الگوریتم SFL ممکن است در بعضی از توابع بهینه سازی قادر به پیداکردن بهینه فرامحلی نباشد و به رکود و افتادن در بهینه محلی دچار شود. رکود الگوریتم SFL ممکن است به دو دلیل زیر باشد:
1- در الگوریتم SFL، قورباغهها متناسب با شایستگی شان به صورت نزولی مرتب و سپس همه جمعیت به چند زیر مجموعه تقسیم می‌گردند. این نوع دسته بندی نامتعادل است، زیرا عملکرد زیر مجموعه اول نسبت به زیر مجموعههای دیگر بهتر است. این توزیع نامتعادل قورباغهها باعث ایجاد مشکلاتی در روند یادگیری میشود چون دیگر قورباغههای خوب در زیر مجموعه آخر وجود ندارند.
2- چنانچه که ذکر شد در الگوریتم SFL موقعیت بدترین قورباغه با توجه به رابطه (3) به‌دست میآید. قورباغه بدتر فقط از قورباغه بهتر تاٌثیر میپذیرد و قورباغه بهتر شانس کمتری برای یادگیری پیدا میکند مگر اینکه قورباغههای بهتر در طول تکامل تبدیل به قورباغه بدتر گردند. بنابراین این الگوریتم از مکانیزم یادگیری مناسبی برخوردار نیست.
تاکنون روش‌هایی توسط محققان برای بهبود الگوریتم SFL ارائه شده است. بخش بعدی به بیان این روش‌ها اختصاص مییابد و سپس الگوریتم پیشنهادی این مقاله ارائه میشود.
2-6- مروری بر کارهای انجام شده در بهبود الگوریتم SFL
در سال 2007 ژن[20] و همکارانش الگوریتم ممتیک جدیدی از ترکیب الگوریتمهای SFL وPSO ارائه دادند [24]. سپس در سال 2008 لی[21] و همکارانش مقاله‌ای با عنوان الگوریتم جهش قورباغه آشوبناک ارائه دادند[25]. در [26] از ایده ممتیک در بهبود SFL استفاده شد. در سال 2008، هان[22] پرش غیر دقیق قورباغهها را با اضافه کردن عبارت عدم قطعیت به رابطه (3) اصلاح کرد و گامی جدید در بهبود این الگوریتم برداشت و مکانیزم یادگیری را تا حدی تصحیح کرد [27]. از آنجایی که روش پیشنهادی دراین مقاله بر اساس روش ارائه شده هان است، بنابراین، روش پیشنهادی هان در بخش بعد توضیح داده میشود.
2-7- تصحیح کردن قانون پرش قورباغه با استفاده از روش پیشنهادی هان
پس از ارائه نسخه ابتدایی لنزی و یوسف که در قسمت قبل بیان گردید، در سال 2008 مقاله‌ای با عنوان «بهبود دادن الگوریتم جستجوی قورباغه برای به دست آوردن ضرائب کنترولر PID» توسط هان مطرح شد که به اصلاح قانون پرش قورباغهها منجر گردید (رابطه (3)). بدین گونه که به دلیل درک ناقص، قورباغه با شایستگی بدتر نمی‌تواند دقیقاً در موقعیت قورباغه بهتر قرار گیرد و این حرکت غیر دقیق، باعث میشود که قورباغه با شایستگی بدتر نتواند به طور مستقیم به موقعیت هدف پرش کند. این مورد در شکل (2) برای یک مسأله دو بعدی نشان داده شده است.
شکل (2): حرکت غیر دقیق قورباغه بدتر به سمت قورباغه بهتر
با توجه به این عدم قطعیت ، موقعیت قورباغه جدید با شایستگی کمتر لزوما به مسیر مستقیمی که بین موقعیت جدیدش و موقعیت بهترین قورباغه است، محدود نمی‌شود. بنابراین قورباغه بدتر میتواند از روی خط مستقیم پرش کند. این ایده به یک قانون پرش جدید منتهی میشود که در شکل (3) نشان داده شده است.
شکل (3): پرش قورباغه بدتر از روی خط مستقیم
قانون جدید پرش قورباغه پیشنهادی‌هان به صورت زیر است:
(5)
که مقدار W از رابطه (6) تعیین میگردد:
(6)
که r یک مقدار تصادفی بین 0 و 1 است و c ثابتی است که مقداری بین 1 و 2 دارد و یک عدد تصادفی بین 1- و 1 میباشد. بیشترین درک اجازه داده شده و عدم قطعیت در i-امین بعد از فضای جستجوست که به صورت رابطه زیر تعریف می شود:
(7)
برای هر متغیر مستقل S، 0.1 تا 0.2 بازه مسأله در نظر گرفته میشود. در هر حال، اگر خیلی بزرگ باشد، قانون جهش قورباغه مشخصه هدایتی خود را از دست میدهد.
سپس مقدار پرش جدید در رابطه (5) به مقدار بدترین قورباغه طبق رابطه (8) اضافه میشود:
(8)
بقیه الگوریتم همانند SFL استاندارد است. در قسمت بعد به بیان الگوریتم پیشنهادی این مقاله پرداخته میشود.
3- معرفی الگوریتم جدید پیشنهادی این مقاله برای جایگاه یابی مسائل چند مدی (NSFL [23])
در این بخش ابتدا راهکاری برای دسته بندی قورباغهها برای رفع نخستین عیب الگوریتم SFL (بخش 2-5 )ارائه می شود. سپس روش‌هان توسعه داده می شود و راه حلی برای رفع دومین عیب الگوریتم SFL پیشنهاد می شود.
3-1- دسته بندی قورباغهها با استفاده از تابع قله-دره[24]
به طور کلی، مشخص کردن شعاع همگرایی در روش‌های به دست آوردن جایگاه بسیار سخت است. بنابراین، اگر دو نقطه قله مربوط به تابع چند بعدی متعلق به فضای جستجو را داشته باشیم، دیگر به شعاع همگرایی نیازی نیست. این روش در ابتدا در سال 1999 توسط ارسم[25] معرفی گردید [21]. روش پیشنهادی ارسم در شکل (4 ) نشان داده شده است.
Hill_valley(ip,iq,samples)
minfit=min(fitness(ip), fitness(iq))
for j=1 to samples.length
Calculate point iinterior on the line between the pints ip and iq
If(minfit>fitness(iinterior))
return 1
end if
end for
return 0
شکل (4): شبه کد تابع قله-دره
شکل (5): ایده جدا سازی قلهها به وسیله تابع قله-دره
همان گونه ذکر شد، در الگوریتم SFL جمعیت متناسب با شایستگی مرتب می شود. در روش پیشنهادی، ابتدا دو قورباغه A وB در نظر گرفته، سپس قورباغه‌ای تصادفی بین A و B به نام D با توجه به رابطه (9)تولید میشود.
(9)
اگر مینیمم شایستگی A و Bاز شایستگی D بیشتر شد میتوان این نتیجه را گرفت که A و Bدر قلههای متفاوت هستند، در غیر این صورت، قورباغه B ام و قورباغه A ام مربوط به یک قله هستند و در یک زیر مجموعه قرار میگیرند. ممکن است قورباغه D در موقعیتی همانند شکل (5) باشد.
همان طور که در شکل (5)دیده میشود، مینیمم شایستگی A و B از D کمتر است و همچنان A و B در قلههای متفاوت هستند. در صورت بروز چنین حالتی باید تعداد عددهای تصادفی بین A و B را زیاد در نظر گرفت تا شایستگی عدد تولید شده D از A وB کمتر شود. در اینجا این نکته قابل اهمیت است که در الگوریتم جهش قورباغه متحرک با توجه به مرتب کردن جمعیت قورباغهها متناسب با شایستگی همیشه شایستگی قورباغه B از A کمتر است (مسأله بیشینه سازی). پس از دسته بندی قورباغهها با توجه به جایگاهها، بر روی هر کدام از مجموعهها یک جستجوی محلی انجام میشود. در قسمت بعد با ارائه روشی جدید به بهبود الگوریتم‌هان پرداخته میشود که الگوریتم پیشنهادی بهتر از الگوریتم ارائه شده توسط‌هان عمل می نماید.
3-2- بهبود روش پیشنهادی هان
هرچند روش پیشنهادی هان تا حدودی الگوریتم SFL را بهبود بخشید اما الگوریتم هنوز از مکانیزم یادگیری چندان موثری برخوردار نیست، از آنجایی که پرش مد نظر از اختلاف بین قورباغههای بهتر و بدتر حاصل میشود و از یادگیری بقیه قورباغهها به نحوی جلوگیری میکند، بنابراین، در این مقاله، قانون پرش به صورت زیر تصحیح میشود؛ بدین گونه که پرش مورد نظر از اختلاف تک تک اعضای قورباغهها در هر زیر مجموعه و بدترین عضو از همان مجموعه، به دست میآید:
(10)
که در آن i=1:P و X هر عضو جمعیت یا قورباغه در هر مجموعه و بدترین عضو جمعیت در هر مجموعه است،r یک مقدار تصادفی بین 0 و 1 است و c ثابتی است که مقداری بین 1 و 2 دارد.
سپس موقعیت جدید قورباغه توسط رابطه زیر به دست میآید:
(11)
اگر این تغییر موقعیت، قورباغه‌ای با شایستگی بهتر تولید کرد این قورباغه جایگزین قورباغه بدتر میشود در غیر این صورت جایگزین می شود. بیانگر بهترین قورباغه در کل مجموعههاست. اگر قورباغه بهتری تولید شد جایگزین بدترین قورباغه میگردد. در غیر این صورت، قورباغه‌ای به صورت تصادفی تولید و با توجه به رابطه زیر جایگزین بدترین قورباغه میگردد.
(12)
که rand() یک عدد یکنواخت بین 0 و 1 است.
اما الگوریتم پس از مدتی دچار رکود میگردد، چون یادگیری قورباغه بدتر از بهترینها متوقف میشود. بنابراین، نیاز به حرکت دوباره قورباغهها در جهت دیگر در فضای جستجو است. بنابراین، پس از آنکه یادگیری قورباغه بدتر از بهترین قورباغه در کل فضای جستجو پایان یافت از رابطه (13) برای پرش قورباغه استفاده میشود.
(13)
حال این پرش طبق رابطه (14) به اضافه میگردد و اگر شایستگی قورباغه تولید شده از i–امین قورباغه بهتر شد جایگزین قورباغه‌ای که دچار رکود شده است.
(14)
شایان ذکر است که بقیه الگوریتم همانند SFL استاندارد است. برتری روش پیشنهادی نسبت به الگوریتم هان در پیوست مقاله نشان داده شده است.
در بخش بعد با پیاده سازی الگوریتم پیشنهادی بر روی توابع محک استاندارد، توانایی آن در پیدا کردن مکان تمامی جایگاهها و رسیدن به جواب بهینه سنجیده میشود و با روش‌های مطرح در این زمینه مقایسه می شود.
4- آزمایش‌ها ونتایج و مقایسه با سایر روش‌ها
در این قسمت نتایج حاصل از پیاده سازی الگوریتم پیشنهادی باچند روش دیگر ارائه شده در مقالات گوناگون، برای حل تعدادی از مسائل چند مدی که در آنها هدف یافتن همه بهینههای محلی و فرامحلی است، ارائه شده است. توابع F1 الی F5 توسط گلدبرگ[26] و ریچاردسون[27] معرفی شده‌اند. این توابع برای آزمودن الگوریتم جایگاهیابی توسط محققان مختلف استفاده شده‌اند [17و8و3]. این توابع توسط روابط (15) الی (21) تعریف میشوند. توابع F1 الی F4 در یک بعد تعریف شده و در بازه [1 0] دارای پنج نقطه بهینه است. تابع F1 و F2 دارای پنج نقطه بهینه در مکان‌های 0.1،0.3،0.5،0.7، و 0.9 هستند. برای تابع F1 مقدار بهینهها برابر 1 است، ولی برای تابع F2 مقدار بهینهها با یکدیگر متفاوت است. اما مکان بهینهها در توابع F3 وF4 0.930 ، 0.681 ، 0.450 ،.246 و 0.079 است. برای تابع F3 مقدار بهینهها برابر 1، ولی برای تابع F4 مقدار بهینهها با یکدیگر متفاوت است. تابعF5 به تابع هیملبلائو[28] مشهور است، در فضای دو بعدی تعریف میشود و در ناحیه تعریف شده چهار بهینه در نقاط (3و2)، (3.7790- و3.2834- )، (2.8064- و3.1304) و (3.5840 و 1.8480-) دارد.
(15)
(16)
(17)
(18)
(19)
تابع F6 معروف به تابع فریبنده، توسط عمرانی[29] [19] و عالمی[30] [20] به کار گرفته شده است. این تابع در یک بعد و در فاصله [6 0] تعریف میشود و دارای دو بهینه مرزی است. این تابع دارای یک بهینه محلی در 3X= با مقدار 0.6 و دو بهینه فرامحلی با مقدار 1 در 0X= و 6X= است.
تابع F7 توسط مایکولز[31] معرفی و توسط ژانگ استفاده شده است [28]. این تابع در یک بعد در فاصله [10 10-] تعریف میشود. این تابع 19 بهینه دارد که 3 تا از آنها بهینههای فرامحلی هستند. در این تابع تعداد بهینهها افزایش یافته است تا الگوریتم پیشنهادی جهت یافتن تعداد بیشتر جایگاهها محک زده شود. توابعF6 و F7 توسط روابط (20) و (21) تعریف می شوند.
(20)
(21)
شایان ذکر است که جمعیت اولیه برای توابع F1 تا F6 برابر 50 و برای تابع F7 برابر 150 در نظر گرفته شده است. مقدار Dmax هم برای تمامی توابع برابر با بی نهایت در نظر گرفته شده است.
درصد موفقیت برای حل مسائل چند مدی به صورت نسبت تعداد بهینههای یافته شده توسط الگوریتم به کل بهینههای موجود در فضای مسأله در همه تکرارها تعریف میشود [1]. جدول (1) درصد موفقیت در یافتن نقاط بهینه طی 30 بار اجرای مستقل الگوریتم را با تعدادی از الگوریتمهای دیگر مقایسه میکند. جدول (2) خطای میانگین الگوریتم پیشنهادی را نشان میدهد. برای هر جواب، خطای میانگین به صورت میانگین فاصله اقلیدسی جواب پیدا شده توسط الگوریتم تا مکان بهینه واقعی تعریف میشود. این خطا طبق رابطه (22) محاسبه می شود. در این رابطه مکان واقعی بهینهi ام و مکان بهینه یافته شده توسط الگوریتم و M تعداد بهینههای یافت شده است [2].
(22)
نتایج جدول (2) بیانگر آن است که کارایی الگوریتم پیشنهادی در مقایسه با الگوریتمهای دیگر بهتر بوده است. به عبارت دیگر، الگوریتم پیشنهادی توانسته است در هر بار اجرای برنامه جایگاه نقاط بهینه را پیدا کند.
جدول (1): درصد موفقیت الگوریتم پیشنهادی
Fitness sharing [2]
Deterministic
Crowding[17]
GCPSO[17]
NGSAV[2]
NISFL
تابع
82.7
100
100
100
100
F1
68
93
93
99.3
100
F2
80
90
100
100
100
F3
66.7
90
93
99.3
100
F4
53.3
90
100
100
100
F5
63.7
-
-
98.8
100
F6
32.3
-
-
100
100
F7
جدول (2): بهترین جواب دیده شده در 30 بار اجرای الگوریتم
Mean
Error
Best_Niche
تابع
3.4e -5
0.9000
0.700
0.4995
0.2999
0.100
F1
1.1e -3
0.8976
0.6983
0.4983
0.2994
0.100
F2
1.6e -3
0.9338
0.6810
0.450
0.2466
0.0796
F3
3.9e -4
0.9303
0.6791
0.4494
0.2462
0.0796
F4
2.7e -3
-2.8056
2.1276
3.5843
1.8482
-3.7821
-3.2783
3.00
1.9993
F5
3.8e -3
6.00
2.999
0.000
F6
2.2e -2
-
F7
5- نتیجه گیری
تاکنون برای حل مسائل چند مدی به وسیله الگوریتم جهش قورباغه متحرک روشی ارائه نشده است. الگوریتم جهش قورباغه، از جمله الگوریتمهای تکاملی است که میتواند در حل مسائل چند مدی استفاده شود. در بهینه سازی مسائل چند مدی، همیشه این سوال مطرح بوده است که یافتن تمامی نقاط بهینه بسیار دشوار است. همان طور که بیان شد، استفاده از پارامترهای جایگاه، از جمله پارامترهای شعاع همگرایی عملکرد بدی در مسائل مربوط به جایگاه دارد. با روش پیشنهادی علاوه بر بهبود الگوریتم SFL اقتباش شده از مقاله هان، میتوان به روش تابع فله-دره قلهها را تشخیص داد و جمعیت را متناسب با قلهها در مجموعههای جداگانه دسته بندی کرد. برای ارزیابی توانایی روش پیشنهادی، نتایج بهینه سازی چند تابع محک استاندارد با روش‌های مطرح در این زمینه مقایسه شده است. نتایج آزمایش‌ها بهبود کارایی روش پیشنهادی را تأیید میکند.
1تاریخ ارسال مقاله: 24/11/1389
تاریخ پذیرش مقاله: 18/8/1390
نام نویسنده مسؤول: ملیحه مغفوری
نشانی نویسنده مسؤول: ایران -کرمان -دانشگاه شهید باهنر کرمان – بخش مهندسی برق[1]-
[1] سجاد یزدانی، حسین نظام آبادی پور، (1388). »حل مسائل چند مدی با استفاده از الگوریتم جستجوی گرانشی«، در پانزدهمین کنفرانس سالانه انجمن کامپیوتر ایران، مجموعه مقالات رایانش نرم.
[2] سجاد یزدانی، حسین نظام آبادی پور ، (1389). » یک راه حل گرانشی جدید برای بهینه یابی مسائل چند مدی«، در هجدهمین کنفرانس مهندسی برق ایران ،مجموعه مقالات کامپیوتر.
[3] Mahfoud, S. W., "Niching methods for genetic algorithms",Ph.D. dissertation, Urbana, IL, USA, 1995.
[4] Horn, J., Nafpliotis, N., and Goldberg, D. E., "A Niched Pareto Genetic Algorithm for Multiobjective Optimization", in Proc. of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, vol. 1. Piscataway, New Jersey: IEEE Service Center, pp. 82–87 ,1994.
[5] De Jong, K. A., "An analysis of the behavior of a class of genetic adaptive systems", Ph.D. dissertation, University of Michigan, 1975.
[6] Mahfoud, S. W., "Crowding and preselection revisited", in Parallel problem solving from nature 2, R. M¨anner and B. Manderick, Eds. Amsterdam: North-Holland, pp. 27–36, 1992.
[7] Goldberg D. E., Richardson, J., "Genetic algorithms with sharing for multimodal function optimization", in Proc. of the Second International Conference on Genetic Algorithms, J. Grefenstette, Ed., pp. 41–49,1987.
[8] Beasley, D., Bull, D. R., Martin, R. R., "A sequential
niche technique for multimodal function optimization", Evolutionary Computation, vol. 1, no. 2, pp. 101–125, 1993.
[9] Harik, G. R., "Finding multimodal solutions using restricted tournament selection", in Proc. of the Sixth International Conference on Genetic Algorithms, L. Eshelman, Ed. San Francisco, CA: Morgan Kaufmann, pp. 24–31,1995.
[10] Bessaou, M., P´etrowski, A., and Siarry, P., "Island model cooperating with speciation for multimodal optimization", in Parallel Problem Solving from Nature - PPSN VI 6th International Conference, H.-P. S. et al., Ed. Paris, France: Springer Verlag, 16-20,2000.
[11] Yin, X., Germay, N., "A fast genetic algorithm with sharing scheme using cluster analysis methods in multi-modal function optimization", in the International Conference on Artificial Neural Networks and Genetic Algorithms, pp. 450–457, 1993.
[12] P´etrowski, A., "A clearing procedure as a niching method for genetic algorithms", in Proc. of the 3rd IEEE International Conference on Evolutionary Computation, pp. 798–803, 1996.
[13] Li, J.P., Balazs, M. E., Parks, G. T., Clarkson, P. J., "A species conserving genetic algorithm for multimodal function optimization", Evol. Comput., vol. 10, no. 3, pp. 207–234, 2002.
[14] Brits, A. E. R., van den Bergh, F., "A niching particle swarm optimizer", in Proc. of the 4th Asia-Pacific Conference on Simulated Evolution and Learning 2002(SEAL 2002), pp. 692–696, 2002.
[15] Li, X., "Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization", in Proc. of Genetic and Evolutionary Computation Conference 2004(LNCS3102), K. Deb, Ed, pp. 105–116, 2004.
[16] Parrott, D., Li, X., "Locating and tracking multiple dynamic optima by a particle swarm model using speciation", IEEE Trans. on Evol. Comput., vol. 10, no. 4, pp. 440–458, August 2006.
[17] Brits, R., Negelbrecht, A., van den Bergh, F., "Locating multiple optima using particle swarm optimization", Applied Mathematics and Computation, vol. 189, pp. 1859–1883, 2007.
[18] Sareni, B., Krahenbuhl, L., "Fitness sharing and niching methods revisited", IEEE Trans. on Evol. Comput., vol. 2, no. 3, pp. 97 – 106, Sep. 1998.
[19] El Imrani, A., Bouroumi, A., Zine El Abidine, H., Limouri, M., Essaid, A., "A fuzzy clustering-based niching approach to multimodal function optimization", Cognitive System Research, vol 1, pp 119-133, 2000.
[20] Alami, J., El Imrani, A., Bouroumi, A., "Multi-population cultural algorithm using fuzzy clustering", Applied Soft Computing ,vol. 7 ,pp. 506–519,2007.
[21] R.K. Ursem, "Multinational evolutionary algorithms", in proceedings of congress of Evolutionary Computation (CEC-99), vol. 3, Washington, pp 1633–1640, 1999.
[22] Eusuff, M., Lansey, K., Pasha, F., "Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization", Engineering Optimization, vol. 38, No. 2, pp. 129-154, 2006.
[23] Eusuff, M., Lansey, K., "Optimization of water distribution network design using the shuffled frog leaping algorithm", Journal of Water Resources Planning and Management, vol. 129, no. 2, pp. 210–25, 2003.
[24] Zhen, Z., "A Novel Memetic Algorithm for Global Optimization Based on PSO and SFLA", ISICA, LNCS 4683, pp. 126–135, 2007.
[25] Y. Li and et al, “The Chaos-based Shuffled Frog Leaping Algorithm and Its Application,” Fourth International Conference on Natural Computation,pp.481-485,2008.
[26] lttipong, P., " solving non-linear continous mathematical using shuffled frog leaping and memetic algorithm", Department of Computer Science and information technology, faculty of science, Naresuan university,2008.
[27] Huynh, T.H., "A Modified Shuffled Frog Leaping Algorithm for Optimal Tuning of Multivariable PID Controllers", ICIT IEEE Industrial Technology ,2008 .
[28] Zhang, J., "A novel adaptive sequential niche technique for multimodal function optimization",,Neuro Computing,vol. 69, pp 2396-2401,2006.
پیوست 1: نتایج روش هان با روش پیشنهادی روی توابع محک استاندارد در ادامه مقایسه شده است. نتایج آزمایش‌ها بهبود توانایی الگوریتم پیشنهادی و ضعف الگوریتم هان را تایید میکند. این نتایج نشان می دهد که الگوریتم هان از مکانیزم یادگیری مناسبی برخوردار نیست.
جدول پ- 1-توابع محک کمینه شونده چند مد و با بعد متغیر
Test Function
S
جدول پ- 2- توابع چند مدی که با افزایش بعد، تعداد بهینههای آن افزایش می یابد.
Test Function
S
جدول پ- (3): نتاج پیاده سازی الگوریتم‌هان و الگوریتم پیشنهادی روی توابع جداول (پ- 1 و پ- 2) میانگین بهترین جواب دیده شده(Mean_best)، بهترین جواب دیده شده(Best_answer)،بدترین جواب دیده شده(Worst_answer) ، انحراف معیار (SD)، تعداد ارزیابی(evaluate) و تعداد تکرار 500 با بعد 30 با 10 بار اجرای مستقل الگوریتم.
ابتدای صفحه