A New Genetic Algorithm Using Order Coding and a Novel Genetic Operator

Abstract:

This paper focuses on improving the efficiency of the genetic algorithm, analysis the shortages of the algorithm at coding method and mutation operator and selected a TSP problem to simulate. First of all, the initial population was taken by order coding to speed up the algorithm convergence. In addition, the inversion operation and migration operation had been added into the mutation process. The experimental results show that without sacrificing convergence speed and the scale of population the improved algorithm has an extraordinary increase on optimal solutions and efficiency.

• Periodical: Advanced Materials Research (Volumes 765-767)
• Pages: 662-666
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.765-767.662
• Online since: September 2013
• Authors: Yun He Wang, Li Fang Liu
• Keywords: Inversion Operation, Migration Operation, Mutation Operator, Order Coding

References

[1] Xu Z B, Chen Z P, Zhang X S. Theoretical development on genetic algorithms: a review [J]. Advances in Mathematics, 2000, 29(2): 97-114.

[2] Armon A, Avidor A, Schwartz O. Cooperative TSP [M]. Algorithms–ESA 2006. Springer Berlin Heidelberg, 2006: 40-51.

DOI: 10.1007/11841036_7

[3] Merz P, Freisleben B. Genetic local search for the TSP: New results [C]. Evolutionary Computation, 1997., IEEE International Conference on. IEEE, 1997: 159-164.

DOI: 10.1109/icec.1997.592288

[4] Tsai H K, Yang J M, Tsai Y F, et al. An evolutionary algorithm for large traveling salesman problems [J]. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 2004, 34(4): 1718-1729.

DOI: 10.1109/tsmcb.2004.828283

[5] Beasley D, Martin R R, Bull D R. An overview of genetic algorithms: Part 1. Fundamentals [J]. University computing, 1993, 15: 58-58.

[6] Schmitt L M. Theory of genetic algorithms [J]. Theoretical Computer Science, 2001, 259(1): 1-61.

[7] Poon P W, Carter J N. Genetic algorithm crossover operators for ordering applications [J]. Computers & Operations Research, 1995, 22(1): 135-147.

DOI: 10.1016/0305-0548(93)e0024-n

[8] Deep K, Thakur M. A new crossover operator for real coded genetic algorithms [J]. Applied Mathematics and Computation, 2007, 188(1): 895-911.

DOI: 10.1016/j.amc.2006.10.047

[9] Chan K Y, Aydin M E, Fogarty T C. Main effect fine-tuning of the mutation operator and the neighbourhood function for uncapacitated facility location problems [J]. Soft Computing, 2006, 10(11): 1075-1090.

DOI: 10.1007/s00500-005-0044-4

[10] Deep K, Thakur M. A new mutation operator for real coded genetic algorithms [J]. Applied mathematics and Computation, 2007, 193(1): 211-230.

DOI: 10.1016/j.amc.2007.03.046