A Simulated Study of Genetic Algorithm with a New Crossover Operator using Traveling Salesman Problem

Abstract

This work shows improvement with a modified form of the existing partially-mapped crossover operator for the traveling salesman problem. This novel crossover approach has been presented to get solutions by order of a list, and “permutation crossover”operators, while preserving the legality of offspring. Results are compared with many existing schemes for permutation representation, like partially-mapped, order, and cycle crossovers, etc. Our modified form of partially-mapped crossover operator searches the existing bits outside the crossover sites, whereas the existing partially-mapped crossover searches within the crossover sites. This approach is easy to understand as well as to apply on benchmark problems. Comparison of the proposed operator with traditional ones for several benchmarks TSPLIB instances widely shows its advantages at the same accuracy level. Also, it requires less time for tuning of genetic parameters and provides much narrower confidence intervals on the results, compared to other operators.