An Improved Genetic Algorithm Crossover Operator for Traveling Salesman Problem

Abstract

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.

Keywords

• Genetic algorithms,NP-hard,traveling salesman problems,path-representation,crossover operators

References

1. Ahmed, Z.H., Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator, Int J Biom Bioinformatics. 3(2010), 96–105.
2. Bhide, S., John, N., Kabuka, M.R., A Boolean neural network approach for the traveling salesman problem, IEEE T COMPUT., 42(1993), 1271–1278.
3. Bland, R.G., Shallcross, D.F., Large traveling salesmen problems arising from experiments in x-ray crystallography, Oper. Res. Lett., 8(1988), 125–128.
4. Bolanos, R.I., Eliana, M.T.O., Mauricio, G.E., A population-based algorithm for the multi traveling salesman problem, International Journal of Industrial Engineering Computations, 7(2016), 245–256.
5. Davis, L., Applying Adaptive Algorithms to Epistatic Domains, In: Proceedings of the International Joint Conference on Artificial Intelligence, 1985, 162–164.
6. Deep, K., Adane, H.M., New variations of order crossover for traveling salesman problem International Journal of Combinatorial Optimization Problems and Informatics, 2(2011), 2–13.
7. Dorigo, M., Gambardella, L.M., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE T EVOLUT COMPUT., 1(1997), 53–66.
8. Dorigo, M., Maniezzo, V., Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1996), 29–41.

9. Finke, G., Claus, A., Gunn, E., A two-commodity network flow approach to the traveling salesman problem, Congressus Numerantium, 41(1984), 167–178.
10. Gen M, Cheng R. Genetic algorithms and Engineering design. John Wiley and Sons, London, UK. 1997.
11. Ghadle, K.P., Muley, Y.M., Traveling salesman problem with MATLAB programming, International Journal of Advances in Applied Mathematics and Mechanics, 2(2015), 258–266.
12. Glover, F., Artificial intelligence, heuristic frameworks and tabu search, Managerial and Decision Economics, 11(1990), 365–375.
13. Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Publishing Company, 1989.
14. Goldberg, D.E., Lingle, R., Alleles, loci, and the traveling salesman problem, In: Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications. Hillsdale, New Jersey: Lawrence Erlbaum, 1985, 154–159.
15. Holland, J.H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, University of Michigan Press, Oxford, UK, 1975.
16. Hussain, A., Muhammad, Y.S., Sajid M.N., Hussain, I., Shoukry A.M., Gani, S., Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator, COMPUT INTEL NEUROSC., 2017(2017), 1–7.
17. Kennedy, J., Eberhart, R.C., Shi, Y., Swarm intelligence, morgan kaufmann publishers. Inc., San Francisco, CA, 2001.
18. Kirkpatrick, S. Toulouse, G., Configuration space analysis of traveling salesman problems, Journal de Physique, 46(1985), 1277–1292.
19. Kumar, N., Karambir, R.K., A comparative analysis of PMX, CX and OX crossover operators for solving traveling salesman problem, International Journal of Latest Research in science and technology, 1(2012), 98–101.
20. Larranaga, P., Kuijpers, C.M., Murga, R.H., Inza, I., Dizdarevic, S., Genetic algorithms for the traveling salesman problem: A review of representations and operators, ARTIF INTELL REV, 13(1999), 129–170.
21. Lin, S., Kernighan, B.W., An effective heuristic algorithm for the traveling salesman problem, OPER RES, 21(1973), 498–516.
22. Michalewicz, Z., Genetic Algorithms+ Data Structures= Evolution Programs. Springer, 3rd edition, 1996.
23. Miliotis, P., Using cutting planes to solve the symmetric traveling salesman problem, MATH PROGRAM, 15(1978), 177–188.
24. Moon, C., Kim, J., Choi, G., Seo, Y., An efficient genetic algorithm for the traveling salesman problem with precedence constraints, EUR JOPER RES., 140(2002), 606–617.
25. Nagata, Y., Soler, D., A new genetic algorithm for the asymmetric traveling salesman problem, EXPERT SYST APPL., 39(2012), 8947–8953.
26. Oliver, I.M., Smith, D., Holland, J.R., Study of permutation crossover operators on the traveling salesman problem, In: Grefenstette, J. J. (ed.) Genetic Algorithms and Their Applications, Proceedings of the Second International Conference. Hillsdale, New Jersey: Lawrence Erlbaum, 1987, 224–230.
27. PiwoAska, A. Genetic algorithm finds routes in traveling salesman problem with profits, Zeszyty Naukowe Politechniki BiaAostockiej. Informatyka, (2010), 51–65.
28. Potvin, J.Y., Genetic algorithms for the traveling salesman problem, ANN OPER RES., 63(1996), 337–370.
29. Ravikumar, C.P., Parallel techniques for solving large scale traveling salesperson problems, Microprocessors and Microsystems, 16(1992), 149–158.
30. Reinelt G. TSPLIB http://www. iwr. uni-heidelberg. de/groups/comopt/software. TSPLIB95. 2014.