Email this article 
Open Access
Subscription or Fee Access
Random-Keys Golden Ball Algorithm for Solving Traveling Salesman Problem
(*) Corresponding author
DOI: https://doi.org/10.15866/iremos.v8i1.5302
Abstract
This paper presents a new metaheuristic approach called RKGB algorithm for solving the combinatorial optimization problems. RKGB is based on soccer concepts; it uses the random keys representation to encode solutions. We propose an efficient adaptation of two algorithms for solving the traveling salesman problem (TSP): GB and RKGB; the booth algorithms have been never tested with TSP. To validate the proposed approach, numerous simulations were conducted on 36 instances of TSPLIB. The RKGB algorithm is compared with GB algorithm and other existing metaheuristics. According to the obtained results, the RKGB algorithm yields optimal solutions in less time. Some tests are conducted on TSPLIB instances for an efficient configuration of RKGB’s parameters. In this work we can deduce that our proposed approach is effective in solving NP-hard optimization problems.
Copyright © 2015 Praise Worthy Prize - All rights reserved.
Keywords
References
M.Malek, Search methods for traveling salesman problems, Department of Electrical and Computer Engineering, The University of Texas, Austin, 1988.
R.M.Gary, et S.D.Johnson, Computers and Intractability a Guide to the Theory of NP-Completeness, WH Freman and Co, 1979.
V.Ungureanu, Traveling Salesman Problem with Transportation. Computer Science, Vol. 14, no 2, p. 41, 2006.
B. Gavish and Graves S. C. The Travelling Salesman Problem and Related Problems. Working Paper OR-078-78, Operations Research Center, MIT, Cambridge, MA, 1978.
Filip, Exnar et Otakar, Machač. The travelling salesman problem and its application in logistic practice. WSEAS Transactions on Business and Economics, Vol. 8, no 4, pp. 163-173, 2011.
Baum, E. B. Iterated descent: A better algorithm for local search in combinatorial optimization problems. Manuscript, 1986.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A. and Teller ,E.. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21, pp. 1087-1092, 1953.
http://dx.doi.org/10.1063/1.1699114
Allwright, RA.James et Carpenter, D. B. A distributed implementation of simulated annealing for the travelling salesman problem. Parallel Computing, Vol. 10, no 3, pp. 335-338, 1989.
http://dx.doi.org/10.1016/0167-8191(89)90106-3
F.Glove, Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, Vol. 13, no 5, pp. 533-549, 1986.
http://dx.doi.org/10.1016/0305-0548(86)90048-1
J. Knox et F.Glover, Comparative Testing of Traveling Salesman Heuristics Derived from TABU Search, Genetic Algorithms, and Simulated Annealing. 1989.
A.Colorni, M.Dorigo, V.Maniezzo, et al, Distributed optimization by ant colonies, In : Proceedings of the first European conference on artificial life, pp. 134-142, 1991.
J.H.Holland, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press, 1975.
S.Salcedo-sanz, J.Del ser, I. Landa-torres, et al. The Coral Reefs Optimization algorithm: a novel metaheuristic for efficiently solving optimization problems. The Scientific World Journal, Vol. 2014, 2014.
http://dx.doi.org/10.1155/2014/739768
F.C.Yang et Y.P.Wang, Water flow-like algorithm for object grouping problems. Journal of the Chinese Institute of Industrial Engineers, Vol. 24, no 6, pp. 475-488, 2007.
http://dx.doi.org/10.1080/10170660709509062
A.Kaveh, et M.Khayatazad, A new meta-heuristic method: ray optimization. Computers & Structures, Vol. 112, pp. 283-294, 2012.
http://dx.doi.org/10.1016/j.compstruc.2012.09.003
E.Osaba, F.Diaz, et E.Onieva, A novel meta-heuristic based on soccer concepts to solve routing problems. In : Proceeding of the fifteenth annual conference companion on Genetic and evolutionary computation conference companion. ACM, pp. 1743-1744, 2013.
http://dx.doi.org/10.1145/2464576.2480776
E.Osaba, F. Diaz, R. Carballedo, et al. Focusing on the Golden Ball Metaheuristic: An Extended Study on a Wider Set of Problems. The Scientific World Journal, Vol. 2014, 2014.
http://dx.doi.org/10.1155/2014/563259
https://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/
G.A.Croes, A method for solving traveling-salesman problems. Operations Research, Vol. 6, no 6, pp. 791-812, 1958.
http://dx.doi.org/10.1287/opre.6.6.791
S. Lin, Computer solutions of the traveling salesman problem. Bell System Technical Journal, The, Vol. 44, no 10, pp. 2245-2269, 1965.
http://dx.doi.org/10.1002/j.1538-7305.1965.tb04146.x
M.Fischetti, J.J.Salazar Gonzalez, et P.Toth, A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, Vol. 45, no 3, pp. 378-394, 1997.
http://dx.doi.org/10.1287/opre.45.3.378
C.D.Tarantilis, Solving the vehicle routing problem with adaptive memory programming methodology. Computers & Operations Research, Vol. 32, no 9, pp. 2309-2327, 2005.
http://dx.doi.org/10.1016/j.cor.2004.03.005
L.Davis, Applying adaptive algorithms to epistatic domains. In: IJCAI. pp. 162-164, 1985.
Z.Wei, F.Ge, Y. Lu, et al. Chaotic ant swarm for the traveling salesman problem. Nonlinear dynamics, Vol. 65, no 3, pp. 271-281, 2011.
http://dx.doi.org/10.1007/s11071-010-9889-x
I.Kuo, S.J.Horng, T.W.Kao, et al. A hybrid swarm intelligence algorithm for the travelling salesman problem. Expert systems, Vol. 27, no 3, pp. 166-179, 2010.
http://dx.doi.org/10.1111/j.1468-0394.2010.00517.x
C.K.Ting, C.H.Su, et C.N.Lee, Multi-parent extension of partially mapped crossover for combinatorial optimization problems. Expert Systems with Applications, Vol. 37, no 3, pp. 1879-1886, 2010.
http://dx.doi.org/10.1016/j.eswa.2009.07.082
T.A.Masutti, et L. N.de Castro, A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Information Sciences, Vol. 179, no 10, pp. 1454-1468, 2009.
http://dx.doi.org/10.1016/j.ins.2008.12.016
Yi.Liu, S.Xiong, et H.Liu, Hybrid simulated annealing algorithm based on adaptive cooling schedule for TSP. In : Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation. ACM. pp. 895-898, 2009.
http://dx.doi.org/10.1145/1543834.1543969
A.Puris, R.Bello, Y.Martínez, et al., Two-stage ant colony optimization for solving the traveling salesman problem. In : Nature Inspired Problem-Solving Methods in Knowledge Engineering. Springer Berlin Heidelberg. pp. 307-316, 2007.
http://dx.doi.org/10.1007/978-3-540-73055-2_33
C.F.Tsai, C.W.Tsai, et C.C.Tseng, A new hybrid heuristic approach for solving large traveling salesman problem. Information Sciences, Vol. 166, no 1, pp. 67-81, 2004.
http://dx.doi.org/10.1016/j.ins.2003.11.008
S.M.Soak, et B.H.Ahn, New genetic crossover operator for the TSP. In : Artificial Intelligence and Soft Computing-ICAISC 2004. Springer Berlin Heidelberg. pp. 480-485, 2004.
http://dx.doi.org/10.1007/978-3-540-24844-6_71
J.C.Bean, Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, Vol. 6, no 2, pp. 154-160, 1994.
http://dx.doi.org/10.1287/ijoc.6.2.154
Kennedy and R. C.Eberhart, Particle Swarm Optimization, IEEE International Conference on Neural Networks, pp.1942-1948, 1995.
http://dx.doi.org/10.1109/icnn.1995.488968
Karthikaikannan, D., Ravi, G., Optimal placement of FACTS devices using small population based particle swarm optimization, (2013) International Review on Modelling and Simulations (IREMOS), 6 (3), pp. 834-841.
Gupta, A., A Novel evolutionary neural network based temperature forecaster using ant colony optimization metaheuristic, (2011) International Review on Computers and Software (IRECOS), 6 (4), pp. 481-485.
Refbacks
Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize
