الگوريتم ژنتيك (GA)

[ravegoat]

اجازه دهید که یک بار دیگر این مسئله و نحوه ی تعریف آن با GA را مرور کنیم:

در اين مسئله فروشنده بايد فرضا" از هشت جزيره ي A، B تا H به ترتيبي عبور كند كه حداقل فاصله ي ممكن براي سفر به تمام اين جزيره ها را پيموده باشد. در اين مسئله ترتيب پيمايش جزيره ها، متغير طراحي است و مسافت طي شده، تابع هدف خواهد بود كه مقدار آن بايد كمينه شود. براي كد كردن متغير طراحي مي توان اين ايده را به كار بست:
يك كروموزوم 8 بيتي تعريف مي كنيم كه بيت اول آن از سمت چپ، نام اولين جزيره اي است كه فروشنده به آن سفر مي كند. بيت دوم نام دومين جزيره اي خواهد بود كه فروشنده به آن مي رود و الي آخر. پس كروموزوم زير نشان مي دهد:

B|A|C|E|H|F|D|G

كه فروشنده سفر خود را از جزيره ي B آغاز كرده است. بعد به جزيره ي A رفته است و طبق همين روند، سفر او در جزيره ي G خاتمه يافته است.

در مسئله ی فروشنده ی دوره گرد (TSP) مجاز نیستیم از یک شهر بیش از یک بار عبور کنیم. در نتیجه اگر براساس تولید مثل های معرفی شده در این بخش بخواهیم این مسئله را حل کنیم در کروموزوم فرزند ممکن است یک شهر دو یا چند بار تکرار شود که برخلاف فرض مسئله خواهد بود. در چنین مواردی از تولید مثل هایی تحت عنوان Order Crossover استفاده می شود. روند کامل حل TSP با GA را می توانید از پیوست دریافت نمایید.