عنوان مقاله
اپراتورهای جدیدالگوریتم های ژنتیکی برای مسئله فروشنده دوره گرد
فهرست مطالب
چکیده
مقدمه
GA پیشنهاد شده
پیچدگی زمانی GA پیشنهاد شده
نتایج آزمایش
نتیجه گیری
بخشی از مقاله
کراس اور ترتیبی اصلاح شده: نقطه کراس اور تصادفاً انتخاب شده، رشته های والد را به زیررشته های راست و چپ تقسیم می کند. زیررشته های راست والدینs1 وs2 انتخاب شده است. بعد از انتخاب شهرها، فرایند شبیه به کراس اور ترتیبی می باشد. تنها اختلاف آن است که به جای انتخاب موقعیت های تصادفی در تور والد، کلیه موقعیت ها در سمت راست نقطه کراس اور تصادفاًانتخاب شده، انتخاب شده است.
کلمات کلیدی:
New Operators of Genetic Algorithms for Traveling Salesman Problem Shubhra Sankar Ray, Sanghamitra Bandyopadhyay and Sankar K. Pal Machine Intelligence Unit Indian Statistical Institute Kolkata 700108 {shubhra_r, sanghami, sankar}@isical.ac.in Abstract This paper describes an application of genetic algorithm to the traveling salesman problem. New knowledge based multiple inversion operator and a neighborhood swapping operator are proposed. Experimental results on different benchmark data sets have been found to provide superior results as compared to some other existing methods. Keywords: knowledge based multiple inversion, order crossover, knowledge based neighborhood swapping. 1. Introduction The Traveling Salesman Problem (TSP) is one of the top ten problems, which has been addressed extensively by mathematicians and computer scientists. Its importance stems from the fact there is a plethora of fields in which it finds applications e.g., DNA fragment assembly, VLSI design. The classical formulation is stated as: Given a finite set of cities and the cost of traveling from city i to city j, if a traveling salesman were to visit each city exactly once and then return to the home city, which tour would incur the minimum cost? Formally, the TSP may be defined as follows [1]: Let {1, 2, ... n} be the labels of the n cities and C = [ci,j] be a n×n cost matrix where ci,j denotes the cost of traveling from city i to city j. The total cost A of a TSP tour is given by
