آخرين ارسالهاي تالار

خطا: mod_kunenalatest:كيوننا نسخه 1.7 (يا بالاتر) بر روي سيستم شما نصب نيست!
پیغام
  • Kunena is not installed or the installed Kunena version is not supported. The plug-in has now been disabled. Please install/upgrade Kunena to version 1.7 for the Kunena Discuss Plug-in to function properly.
حل مساله TSP با استفاده از الگوریتم ترکیبی جهش قورباغه مشاهده در قالب PDF چاپ فرستادن به ایمیل
نوشته شده توسط admin   
سه شنبه, 30 آذر 1389 ساعت 17:56

الگوریتم ترکیبی جهش قورباغه (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

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

نظر ها (3)
  • mr  - حل مساله TSP با استفاده از الگوریتم ترکیبی جهش قور
    it is good
  • ناشناس
    عالی بود
  • delsa
    سلام میشه مقاله رو برای منم بفرستین ممنون
تنها کاربران عضو شده می توانند نظر ارسال کنند!
آخرین بروز رسانی در جمعه, 18 فروردین 1391 ساعت 15:13
 
logo-samandehi