Artificial Fish Algorithm to Solve Traveling Salesman Problem

Abstract:

TSP has been studied in many methods by various algorithms. with the increase of the TSP scale, there are some problems appear in the related solution ,such as solving the optimal solution and so on. With the increasing calculation nodes, the convergence degree and computing difficulty of TSP will increase enormously. Artificial fish is an optimize algorithm based on biology model putting forward at present. Proposed a solution for TSP based on the Artificial fish algorithm, describes the mathematic model of TSP, and Expounds the steps of the algorithm in details. by testing the algorithm, we know that, the algorithm can obtain the best solution, in global search, convergence rate,,but the robustness has to be improved in the future.

• Periodical: Applied Mechanics and Materials (Volumes 121-126)
• Pages: 4410-4414
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.121-126.4410
• Online since: October 2011
• Authors: Jian Ping Wang, Yan Pei Liu, Yong Huang
• Keywords: Ant Colony Algorithm (ACA), Artificial Fish Algorithm, Genetic Algorithm (GA), TSP

References

[1] Kirkpatrick S, Gelatt Jr C D, Vecchi M P. Optimization by Simulated Annealing [J]. Science, 1983, 220(4598): 671-680.

DOI: 10.1126/science.220.4598.671

[2] Dorigo M, Maniezzo V, Colorni A. The Ant System: Optimi-zation by a Colony of Cooperating Agents[J]. IEEE Transon Systems, Man, and Cybernetics-Part B, 1996, 26(1): 29-41.

DOI: 10.1109/3477.484436

[3] Dorigo M, Gambardella L M. A Study of Some Properties of Ant-Q[C ]∥Proc of the 44th Int'l Conf on Parallet Prob-lem Solving from Nature, 1996: 656-665.

[4] Hunt J, Cooke D. Learning Using an Artificial Immune System[J]. Journal of Network and Computer Applications, 1996, 19(2): 189-212.

DOI: 10.1006/jnca.1996.0014

[5] James K, Eberhart R C. A Discrete Binary Version of the Particle Swarm Algorithm[C]/Proc of the IEEE Conf on Systems, Man, and Cybernetics, 1997: 4104-4109.

DOI: 10.1109/icsmc.1997.637339

[6] Guo Tao, Michalewicz Z. Evolutionary Algorithms for the TSP[C]/Proc of the 5th Parallel Problem Solving from Nature Conf, 1998: 803-812.

[7] Mitchell J. Branch-and-cut algorithms for combinatorial optimization problems[Z]. Handbook of Applied Optimization, Oxford University Press, 2000: 65-77.

[8] Mitchell J E. Polynomial interior point cutting plane methods[J]. Optimization Methods and Software, 2003, 18(5): 507-534.

DOI: 10.1080/10556780310001607956

[9] Tseng C C, Tsai C F, Tsai C W. A new hybrid heuristic approach for solving large traveling salesman problem[J]. Information Sciences, 2004, 166: 67-81.

DOI: 10.1016/j.ins.2003.11.008

[10] James B O, Abraham P P, Andreas S S. Approximate local search in combinatorial optimization[J]. SIAM J Comput, 2004, 33(5): 1201-1214.

[11] Padberg M. Classical cuts for mixed-integer programming andbranch-and-cut[J]. Mathematical Methods of Operations Re-search, ANN OPER RES, 2005, 139(1): 321-352.

DOI: 10.1007/s10479-005-3453-y

[12] Climer S, Zhang W X. Cut-and-solve: An iterative search strategy for combinatorial optimization problems[J]. Artif Intell, 2006, 170(8-9): 714-738.

DOI: 10.1016/j.artint.2006.02.005