حل TSP به روش الگوریتم ژنتیک

TSP مخفف عبارت Traveling Salesman Problem و به معنای مسئله فروشنده دوره گرد می باشد. TSP یک نمونه بارز از مسائل ترکیبی بهینه سای است که تحقیقات بسیاری از محققان در این زمینه را به سوی خود جلب کرده است. این فروشنده دوره گرد باید از n شهر عبور کرده ، با این شرایط که باید از تمام شهرها عبور کرده و از هر شهر فقط یکبار گذر کند، یعنی هر مسیر باید شرایط یک گراف هملیتونی را داشته باشد. آنچه در این مقاله شرح داده ام پروسه حل این مسئله به روش الگوریتم ژنتیک است که در مرحله همبری روشی جدید (بهبود در روش ERX) به کار گرفته شده است. کدنویسی این الگوریتم در نرم افزار MATLAB انجام شده است.

کلیدواژه ها:

الگوریتم ژنتیک ، TSP ، چرخ رولت Mutation ، Offspring ، Crossover