Orthogonal Genetic Algorithm and its Application in Traveling Salesman Problem

Abstract:

The traveling salesman problem (TSP) is one of the most widely studied NP-hard combinatorial optimization problems. Its statement is deceptively simple, and yet it remains one of the most challenging problems and traditional genetic algorithm trapped into the local minimum easily for solving this problem. Therefore, based on a simple genetic algorithm and combine the base ideology of orthogonal test then applied it to the population initialization, crossover operator, as well as the introduction of adaptive orthogonal local search to prevent local convergence to form a new orthogonal genetic algorithm. The new algorithm shows great efficiency in solving TSP with the problem scale under 300 under the experiment results analyze.

• Periodical: Advanced Engineering Forum (Volumes 6-7)
• Pages: 290-293
• DOI: https://doi.org/10.4028/www.scientific.net/AEF.6-7.290
• Online since: September 2012
• Authors: Han Min Liu, Qing Hua Wu, Xue Song Yan
• Keywords: Fitness Function, Local Search, Orthogonal Genetic Algorithm

References

[1] J. Holland, Adaptation in natural and artificial systems. University of Michigan press, (1975).

[2] Durbin R, Willshaw D. An Anlaogue Approach to the Traveling Salesman Problem Using an Elastic Net Approach. Nature, 326, 6114, (1987) 689-691.

DOI: 10.1038/326689a0

[3] T. Guo and Z. Michalewize. Inver-Over operator for the TSP. In Parallel Problem Sovling from Nature(PPSN V), Springer-Verlag press, (1998) 803-812.

DOI: 10.1007/bfb0056922

[4] Z.C. Huang, X.L. Hu and S.D. Chen. Dynamic Traveling Salesman Problem based on Evolutionary Computation. In Congress on Evolutionary Computation(CEC'01), IEEE Press, (2001) 1283-1288.

DOI: 10.1109/cec.2001.934338

[5] Aimin Zhou, Lishan Kang and Zhenyu Yan. Solving Dynamic TSP with Evolutionary Approach in Real Time. In Congress on Evolutionary Computation(CEC'03), (2003) 951-957.

DOI: 10.1109/cec.2003.1299769

[6] H. Yang, L.S. Kang and Y.P. Chen. A Gene-pool Based Genetic Algorithm for TSP. Wuhan University Journal of Natural Sciences 8(1B), (2003) 217-223.

[7] X.S. Yan, L.S. Kang et. al: An Approach to Dynamic Traveling Salesman Problem. Proceedings of the Third International Conference on Machine Learning and Cybernetics, IEEE Press, Shanghai, (2004) 2418-2420.

[8] X.S. Yan, A. M Zhou, L. S Kang et, al; TSP Problem Based on Dynamic Environment. Proceedings of the 5th World Congress on Intelligent Control and Automation, IEEE press, Hangzhou, China, (2004) 2271-2274.

[9] Leung Yiu-Wing, Wang Yuping. An orthogonal genetic algorithm with quantization for global numerical optimization. IEEE Transactions on Evolutionary Computation, (2001), 5(1): 41-53.

DOI: 10.1109/4235.910464

[10] [X.S. Yan, Hui Li et. al: A Fast Evolutionary Algorithm for Combinatorial Optimization Problems. Proceedings of the Fourth International Conference on Machine Learning and Cybernetics, IEEE Press, (2005) 3288-3292.

DOI: 10.1109/icmlc.2005.1527510

[11] H.M. Liu et, al. Orthogonal Genetic Algorithm and Its Application in Function Optimization. Applied Mechanics and Materials Vols. 121-126 (2012) pp.4528-4531.

DOI: 10.4028/www.scientific.net/amm.121-126.4528