Turkish Journal of Mathematics and Computer Science

Yazarlar: Abid HUSSAIN, Yousaf Shad MUHAMMAD, Muhammad Nauman SAJİD

Konular:Mühendislik

Anahtar Kelimeler:Genetic algorithms,NP-hard,Traveling salesman problems,Path-representation,Crossover operators

Özet: The genetic algorithm is one of the best algorithms in order to solve many combinatorial optimization problems, especially traveling salesman problem. The application of genetic algorithms to problems which are not amenable to bit string representation and traditional crossover has been a growing area of interest. One approach has been to represent solutions by permutations of a list, and “permutation crossover” operators have been introduced to preserve the legality of offspring. There are many existing schemes for permutation representation like PMX, OX, and CX etc. In this paper, we extend the CX scheme which produces healthy offspring based upon survival of the fittest theory. Comparison of the proposed operator with other ones for ten benchmarks TSPLIB instances vividly shows its pros at the same accuracy level. Also, it requires less time for tuning of genetic parameters and provides narrower confidence intervals on the results than other operators.

---