الگوریتم ژنتیک یکی از معروفترین الگوریتمهای متاهیوریستیک است که تا کنون کتب و مقالات بسیار زیادی در مورد انواع آن (مثل Sequntial GA، Adaptive GA، Genetic Programming و …)، روشهای پیاده‌سازی و بهینه‌سازی در آن منتشر شده است.
من هم مدت زیادی در مورد انواع اپراتورهای بهینه و روشهای نوین پیاده‌سازی GA مطالعه کرده‌ام، که ماحصل یکی از آن مطالعات، پیاده‌سازی مسئله TSP در الگوریتم ژنتیک بوده است که البته متاسفانه هنوز فرصت تکمیل این پروژه را بدست نیاورده‌ام.
در حال حاضر در این برنامه روشها و امکانات زیر پیاده‌سازی شده‌اند (این برنامه به تدریج تکمیل خواهد گشت):
  • روشهای انتخاب کروموزومها: Roulette wheel, Tournament Random/Unique, Ranking Linear/Biased و …
  • متدهای ترکیب: 1-point, 2-point, Uniform, GST, GSX, Greedy 1pt, PMX, Circular و …
  • بهینه‌سازی محلی Sengoku-Yoshihara
  • امکان ذخیره و بازیابی نقشه‌های TSP
  • امکان تعیین و تغییر تمامی پارامترها مثل نرخهای جهش، ترکیب، انتخاب و … در حین اجرای الگوریتم و به شکل داینامیک
  • امکان رسم نمودار پیشرفت الگوریتم بر اساس مقادیر برازش در هر نسل، به منظور مقایسه کارایی و کاربرد الگوریتمها در مواردی مانند همگرایی زودرس، همگرایی دیررس، تاثیر نرخ جهش و …

هدف اصلی از پیاده‌سازی این برنامه مقایسه کارایی الگوریتم Genetic و برخی اپراتورهای بهینه شده، در حالتهای Steady-State و Dynamic بوده است.

A Genetic algorithm approach to Traveling Salesman (TSP) problem.

Latest features V1.7:

  • Selection methods: Roulette wheel, Tournament Random/Unique, Ranking Linear/Biased, …
  • Crossover methods: 1-point, 2-point, Uniform, GST, GSX, Greedy 1pt, PMX, Circular, …
  • Also Sengoku & Yoshihara local search technique is implemented as 2 routines, Random and full.
  • Save & Load TSP maps, with 14 initial map.
  • Full charting and analysis tools.

Download GATSP v1.7 Beta Version

Screenshots:

Print this pageEmail this to someoneShare on Google+Share on FacebookShare on LinkedInTweet about this on TwitterShare on RedditShare on TumblrShare on StumbleUponPin on Pinterest