الگوریتم ترکیبی جهش قورباغه (SFLA)یک الگوریتم ممتیک متاهیوریستیک جدید است که توابع ریاضی کارا و قابلیت جستجوی سراسری را دارد. مساله فروشنده­ی دوره­گرد (TSP)یک مساله­ی بهینه­سازیِ ترکیبیِ پیچیده است که به عنوان محکی برای ارزیابیِ سودبخشی و کاراییِ الگوریتم­های بهینه­سازی که به تازگی پیشنهادشده­اند، استفاده می­شود. زمانیکه از الگوریتم ترکیبی جهش قورباغه برای حل TSP استفاده می­شود، memeplex و submemeplex ساخته می­شوند و روند الگوریتم، به ویژه جستجوی محلی در submemeplex به دقت مطابق SFLAِ اصلی می­شود. نتایج تجربی نشان می­دهند که الگوریتم ترکیبیِ جهش قورباغه برای حل مسائل TSP ای که مقیاس کوچکی دارند کارا است. به ویژه در TSP ای که 51 شهر دارد، الگوریتم موفق می­شود 6 مسیر که کوتاهتر از مسیر بهینه­ی ایجاد شده توسط TSPLIB هستند را بیابد. طول کوتاهترین مسیر به جای اینکه برابر با 429.98 که در سایر مراجع ذکر شده باشد ، برابر 428.87 است.

مساله­ی معروف فروشنده­ی دوره­­گرد (TSP) یک مساله­ی بهینه­سازیِ ترکیبی متداول است که معمولاً جهت ارزیابی کارایی الگوریتم­های متاهیوریستیک بکارگرفته می­شود. در حال حاضر الگوریتم­های متاهیوریستیک عمدتاً شامل الگوریتم ژنتیک (GA)، الگوریتم بهینه­سازیِ کلونی مورچه­ها (ACO) و الگوریتم بهینه­سازی گروه ذرات (PSO) می­باشند. هر یک از این الگوریتم­های متاهیوریستیک توانایی­ها و ضعف­هایی برای حل مساله­ی TSP دارند. برای مثالGA ممکن است زمان بسیار زیادی را برای جستجوی پاسخ بهینه صرف کند ، درصورتیکه ACO کلاً تعدادی پارامتر دارد و زمان کمتری صرف می­کند. اما ACO به آسانی در بهینه­ی محلی می­افتد. PSO نسبتاً ساده است و توجه پژوهشگران را در زمینه­های مختلف جلب کرده است. اخیراً دو پژوهشگر به نام­های Muzaffar Eusuff و Kevin Lansey از طریق مشاهده­، تقلید و مدلسازیِ رفتار قورباغه­ها که غذاهای موجود بر روی سنگ­های مجزایی که به صورت تصادفی در تالاب قرارگرفته­اند را جستجو می کنند، یک الگوریتم متاهیوریستک جدید با نام الگوریتم ترکیبی جهش قورباغه (SFLA) ایجاد کردند.

SFLA : Shuffled frog-leaping algorithm

TSP : Traveling Salesman Problem

GA : Genetic Algorithm

ACO : Ant Colony Optimization

PSA :Particle Swarm Algorithm

دریافت کامل مقاله

• افزودن جدید
• جستجو

نظر ها (1)

• |94.182.99.xxx |2011-11-14 21:27:14 mr  - حل مساله TSP با استفاده از الگوریتم ترکیبی جهش قور
  it is good
  • 0
  • 0

  پاسخبازگو

نوشتن نظر

Your Contact Details:

نام:

ایمیل: اعلام نکردناعلام کردن

آدرس سایت:

نظر:

عنوان:

قالب نوشته:         -رنگ-آبی کمرنگسیاهآبیبنفشخاکستریسبزلیموییقرمز آلبالوییسرمه ایزیتونیزرشکیقرمزنقره ایآبی سیرسفیدزرد -اندازه-ریزکوچکمعمولیبزرگبسیار بزرگ

Message:

Security

کد آنتی اسپم نمایش داده شده در عکس را وارد کنید.

Powered by !JoomlaComment 4.0 beta2