پیاده‌سازی مسئله فروشنده دوره‌گرد با الگوریتم ژنتیک GATSP 1.7 Beta

الگوریتم ژنتیک یکی از معروفترین الگوریتمهای متاهیوریستیک است که تا کنون کتب و مقالات بسیار زیادی در مورد انواع آن (مثل 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 بوده است.

دیگر مطالب مرتبط با متاهیوریستیک:

About محمد شمس

برنامه‌نویس، طراح انیمیشن و علاقمند به هوش مصنوعی

3 Comments

  1. سلام
    من برنامه را با ۹۹ نقطه آغاز کردن ولی خطوط روی هم افتاد. اشکال از چیست؟؟؟؟؟؟؟

    Mohsen K.Nazar

  2. درست است.
    خطوطی که از روی هم رد شده‌اند، به یکدیگر متصل نیستند. فقط خود نقاط شماره دار، نقطه اتصال هستند.

  3. سلام خسته نباشید.میشه لفطا یک مثال عددی با الگوریتم ژنتیک حل کنید و مراحل را واضح توضیح دهید.؟

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *


5 × 6 =