یک رهیافت جدید برای جایگاه یابی مسائل چند مدی با استفاده از الگوریتم بهبود یافته جهش قورباغه

نوع مقاله: مقاله علمی فارسی

نویسندگان

1 کارشناس ارشد مهندسی برق کنترل-دانشکده مهندسی -دانشگاه شهید باهنرکرمان

2 دانشیار بخش مهندسی دانشگاه شهید باهنرکرمان

چکیده

: مسأله جایگاه یکی از روش‌های مهم برای بهینه سازی مسایل چند مدی است. بیشتر روش‌های موجود در مسأله جایگاه نیاز به تعیین دقیقی از پارامترهای جایگاه به منظور عملکرد بهتر دارد. مشکل اصلی الگوریتم­های ابتکاری در حل مسائل چند بعدی قدرت همگرایی آنها به یک جواب (عموماً بهینه فرا محلی) است. الگوریتم جهش قورباغه، از جمله الگوریتم‌های ابتکاری است که در سال­های اخیر تا کنون نسخه‌ای از آن برای حل مسائل چند مدی ارائه نشده است. در این مقاله نسخه‌ای از این الگوریتم برای حل مسائل چند مدی با حفظ ساختار‌های اساسی ارائه و با روش‌های مطرح مقایسه شده است. نتایج آزمایش‌ها روی توابع محک استاندارد توانایی الگوریتم پیشنهادی را تأیید می­کند.

کلیدواژه‌ها


عنوان مقاله [English]

A new niche technique for multimodal function optimization using Shuffled Frog leaping algorithm

نویسندگان [English]

  • Eman Sayedi 1
  • mohammd Barati 1
  • Malihe Maghfoori Farsangi 2
  • Hossen Nezamabadi 2
1 Department of electrical engineering, Faculty of Engineering, Shahid Bahonar University, Kerman, Iran
2 Department 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-4- به هم آمیختن جمعیت[19]

 

پس از تکامل درونی چندین نسل، تمام مجموعه­ها به هم آمیخته و بر اساس ارزش شایستگی آنها به صورت نزولی مرتب می­شوند. سپس دوباره به چند زیر مجموعه تقسیم می‌گردند و روند تکامل در هر مجموعه تا زمانی که به معیار توقف برسد ادامه می­یابد.

 

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): حرکت غیر دقیق قورباغه بدتر به سمت قورباغه بهتر 

شکل (2): حرکت غیر دقیق قورباغه بدتر به سمت قورباغه بهتر

با توجه به این عدم قطعیت ، موقعیت قورباغه جدید با شایستگی کمتر لزوما به مسیر مستقیمی که بین موقعیت جدیدش و موقعیت بهترین قورباغه است، محدود نمی‌شود. بنابراین قورباغه بدتر می‌تواند از روی خط مستقیم پرش کند. این ایده به یک قانون پرش جدید منتهی می‌شود که در شکل (3) نشان داده شده است.

شکل (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): ایده جدا سازی قله‌ها به وسیله تابع قله-دره

شکل (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] -Multimodal

[2] -Crowding

[3]-Deterministic crowding

[4] -Fitness sharing

[5] -Sequential niche

[6] - Restricted tournament selection

[7] - parallelization

[8] -Clustering

[9] -Clearing

[10] -Speciation

[11]Shuffled frog leaping (SFL)

[12] Lansey

[13] -Eussuf

[14]- Memplex

[15] -Culture

[16]-Heuristic

[17]-random

[18] Global best

[19] Shuffled of population

[20] - Zhen

[21] - Li

[22] - Huynh

[23] New shuffled frog leaping (NSFL)

[24] -Hill- valley function

[25] -Ursem

[26] - Goldberg

[27] - Richardson

[28]- Himmelblau

[29] - Imrani

[30] -Alami

[31] - Michols

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 [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 بار اجرای مستقل الگوریتم.

 

Function

الگوریتم‌هان

الگوریتم پیشنهادی

Mean_best

Best_answer

Worst_answer

SD

evaluate

Mean_best

Best_answer

Worst_answer

SD

evaluate

F1

5.9526e-05

2.6461e-05

7.2310e-05

3.177e-5

50000

0

0

0

0

35000

F2

0.0045

0.0024

0.0075

0.0018

50000

2.3207e-213

1.8278e-222

2.3188e-212

0

50000

F3

4.4987e-15

1.0080e-017

3.1450e-014

9.5e-15

50000

0

0

0

0

45000

F4

6.0352e-14

2.2777e-014

1.5774e-013

3.78e-14

50000

5.67393e-237

1.30685e-241

4.55618e-236

0

50000

F5

92.7849

26.2614

419.5713

117.7615

50000

0

0

0

0

4000

F6

0

0

0

0

8500

0

0

0

0

600

F7

0.0235

0.0038

0.1415

0.0419

50000

2.4646e-04

7.1464e-05

6.82636e-04

2.2e-04

50000

F8

-7.6244e+03

-9.2729e+03

-7.0617e+003

688.4169

50000

-1.25694e+04

-1.25694e+04

-1.25694e+04

0

1000

F9

46.1882

16.9143

70.6420

19.4128

50000

0

0

0

0

4000

F10

0.8419

0.0035

1.6484

0.7565

50000

0

0

0

0

35000

F11

0.0441

1.4482e-004

0.1058

0.0360

23000

0

0

0

0

3000

F12

1.0121

1.8416e-006

2.0943

1.6030

50000

1.57054e-32

1.57054e-32

1.57054e-32

2.88e-48

4000

F13

9.3631e-16

1.3934e-016

1.2814e-015

5.13e-16

50000

1.34978e-32

1.34978e-32

1.34978e-32

2.88e-48

4000

زیرنویس‌ها

[1] -Multimodal

[1] -Crowding

[1]-Deterministic crowding

[1] -Fitness sharing

[1] -Sequential niche

[1] - Restricted tournament selection

[1] - parallelization

[1] -Clustering

[1] -Clearing

[1] -Speciation

[1]Shuffled frog leaping (SFL)

[1] Lansey

[1] -Eussuf

[1]- Memplex

[1] -Culture

[1]-Heuristic

[1]-random

[1] Global best

[1] Shuffled of population

[1] - Zhen

[1] - Li

[1] - Huynh

[1] New shuffled frog leaping (NSFL)

[1] -Hill- valley function

[1] -Ursem

[1] - Goldberg

[1] - Richardson

[1]- Himmelblau

[1] - Imrani

[1] -Alami

[1] - Michols