Musa PEKER, Baha ŞEN, Pınar Yıldız KUMRU

An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method

Owing to its complexity, the traveling salesman problem (TSP) is one of the most intensively studied problems in computational mathematics. The TSP is defined as the provision of minimization of total distance, cost, and duration by visiting the n number of points only once in order to arrive at the starting point. Various heuristic algorithms used in many fields have been developed to solve this problem. In this study, a solution was proposed for the TSP using the ant colony system and parameter optimization was taken from the Taguchi method. The implementation was tested by various data sets in the Traveling Salesman Problem Library and a performance analysis was undertaken. In addition to these, a variance analysis was undertaken in order to identify the effect values of the parameters on the system. Implementation software was developed using the MATLAB program, which has a useful interface and simulation support.

Anahtar Kelimeler:

Ant colony system, Taguchi method, route planning, traveling salesman problem

An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method

Keywords:

Ant colony system, Taguchi method, route planning, traveling salesman problem,

PDF

___

B. ¨ Ozkan, U. Cevre, A. U˘ gur, “[Route planning with a hybrid optimization technique]”, Akademik Bili¸sim, Vol. 44, pp. 173–183, 2008 (article in Turkish with an abstract in English).
˙I. Me¸secan, ˙I. ¨ O. Bucak, ¨ O. Asilkan, “Searching for the shortest path through group processing for TSP”, Mathematical and Computational Applications, Vol. 16, pp. 53–65, 2011.
J.Y. Potvin, “The TSP: a neural network perspective”, ORSA Journal on Computing, Vol. 5, pp. 328–348, 1993. L.M. Gambardella, M. Dorigo, “Solving symmetric and asymmetric TSPs by ant colonies”, Proceedings of IEEE International Conference on Evolutionary Computation, pp. 622–627, 1996.
S. Yigit, B. Tugrul, F.V Celebi, “A complete CAD model for type-I quantum cascade lasers with the use of artificial bee colony algorithm”, Journal of Artificial Intelligence, Vol. 5, p. 76, 2012.
T. Keskint¨ urk, H, S¨ oyler, “Global ant colony optimization”, Journal of the Faculty of Engineering and Architecture of Gazi University, Vol. 21, pp. 689–698, 2006.
M. Peker, B. S ¸en, S ¸. Bayır, “Using artificial intelligence techniques for large scale set partitioning problems”, World Conference on Innovation and Software Development, ˙Istanbul, 2011.
C. Blum, “Ant colony optimization: Introduction and recent trends”, Physics of Life Reviews, Vol. 2, pp. 353–373, 200 TSPLIB. University of Heidelberg. Available at http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ (accessed 13.04.2011).
B. Angeniol, G.S.L.C Vaubois, J.Y.L. Texier, “Self-organizing feature maps and the traveling salesman problem”, Neural Networks, Vol. 1, pp. 289–293, 1988.
S. Somhom, A. Modares, T. Enkawa, “A self-organizing model for the traveling salesman problem”, Journal of the Operational Research Society, Vol. 48, pp. 919–928. 1997.
K. Alaykıran, O. Engin, “Ant colony meta heuristic and an application on TSP”, Journal of the Faculty of Engineering and Architecture of Gazi University, Vol. 1, pp. 69–76, 2005.
R. Pasti, L.N.D. Castro, “A neuro-immune network for solving the traveling salesman problem”, Proceedings of the International Joint Conference on Neural Networks, pp. 3760–3766, 2006.
I. Vallivaara, “A team ant colony optimization algorithm for the multiple travelling salesmen problem with minmax objective”, 27th IASTED International Conference on Modelling, Identification, and Control (MIC 2008), pp. 1–6, 200
M. Dorigo, L.M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem”, IEEE Transactions on Evolutionary Computation, Vol. 1, pp. 53–66, 1997.
I. Ellabib, P. Calamai, O. Basir, “Exchange strategies for multiple ant colony system”, Information Sciences, Vol. 177, pp. 1248–1264, 2007.
H.D. Nguyen, I. Yoshihara, K. Yamamori, M. Yasunaga, “Implementation of an effective hybrid GA for large-scale traveling salesman problem”, IEEE Transactions on System, Man, and Cybernetics – Part B, Vol. 37, pp. 92–99, 200 X.F. Xie, J. Liu, “Multiagent optimization system for solving the traveling salesman problem”, IEEE Transactions on Systems, Man, and Cybernetics – Part B: Cybernetics, Vol. 39, pp. 489–502, 2008.
J. Yi, W. Bi, G. Yang, Z. Tang, “A fast elastic net method for traveling salesman problem”, Proceedings of the 8th International Conference on Intelligent Systems Design and Applications, pp. 462–467, 2008.
M. Saadatmand-Tarzjan, M. Khademi, M.R. Akbarzadeh-T, H.A. Moghaddan, “A novel constructive-optimizer neural network for the traveling salesman problem”, IEEE Transactions on Systems, Man, and Cybernetics – Part B: Cybernetics, Vol. 37, pp. 754–770, 2007.
J.G. Sauer, L. Coelho. “Discrete differential evolution with local search to solve the traveling salesman problem: fundamentals and case studies”, Proceedings of the 7th IEEE International Conference on Cybernetic Intelligence Systems, pp. 1–6, 2008.
X. Shi, L. Wang, Y. Zhou, Y. Liang, “An ant colony optimization method for prize-collecting traveling salesman problem with time windows”, 4th International Conference on Natural Computation, Vol. 7, pp. 480–484, 2008.
L. Li, S. Ju, Y. Zhang, “Improved ant colony optimization for the traveling salesman problem”, Proceedings of the International Conference on Intelligent Computation Technology and Automation, Vol. 1, pp. 76–80, 2008.
F. Liu, G. Zeng, “Study of genetic algorithm with reinforcement learning to solve the TSP”, Expert Systems with Applications, Vol. 36, pp. 6995–7001, 2009.
C.Y. Chien, S.M. Chen, “A new method for handling the traveling salesman problem based on parallelized genetic colony systems”, International Conference on Machine Learning and Cybernetics, pp. 2828–2833, 2009.
C.B. Cheng, K.P. Wang, “Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm”, Expert Systems with Applications, Vol. 36, pp. 7758–7763, 2009.
H.M. Naimi, N. Taherinejad, “New robust and efficient ant colony algorithms: Using new interpretation of local updating process”, Expert Systems with Applications, Vol. 36, pp. 481–488, 2009.
Y. Marinakis, M. Marinaki, “A hybrid genetic–particle swarm optimization algorithm for solving the vehicle routing problem”, Expert Systems with Applications, Vol. 37, pp. 1446–1455, 2010.
D. Karabo˘ ga, B. G¨ orkemli, “A combinatorial artificial bee colony algorithm for Traveling Salesman Problem”, International Symposium on Innovations in Intelligent Systems and Applications, pp. 50–53, 2011.
X.M. You, S. Liu, Y.M. Wang, “Quantum dynamic mechanism-based parallel ant colony optimization algorithm”, International Journal of Computational Intelligence Systems, pp. 101–113, 2010.
T.A.S. Masutti, L.N.D. Castro, “A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem”, Information Sciences, Vol. 179, pp. 1454–1468, 2009.
L. Bianchi, L.M. Gambardella, M. Dorigo, “An ant colony optimization approach to the probabilistic travelling salesman problem”, Lecture Notes in Computer Science, Vol. 2439, pp. 883–892, 2002.
C.F. Tsai, C.W. Tsai, C.C. Tseng, “A new and efficient ant-based heuristic method for solving the traveling salesman problem”, Expert Systems, Vol. 20, pp. 179–186, 2003.
M. Dorigo, L.M. Gambardella, “Ant colonies for the travelling salesman problem”, BioSystems, Vol. 43, pp. 73–81, 19 A. Baykaso˘ glu, T. Dereli, I. Sabuncu, “An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems”, Omega: The International Journal of Management Science, Vol. 34, pp. 385–396, 200 A.E. Eiben, R. Hinterding, Z. Michalewicz, “Parameter control in evolutionary algorithms”, IEEE Transactions on Evolutionary Computation, Vol. 3, pp. 124–141, 1999.
F.T.S. Chan, R. Swarnkar, “Ant colony optimization approach to a fuzzy goal programming model for machine tool selection and operation allocation problem in an FMS”, Robotics and Computer-Integrated Manufacturing, Vol. 22, pp. 353–362, 2006.
S.P. Simon, N.P. Padhy, R.S. Anand, “An ant colony system approach for unit commitment problem”, Electrical Power & Energy Systems, Vol. 28, 315–323, 2006.
O. Karpenko, J. Shi, Y. Dai, “Prediction of MHC class II binders using the ant colony search strategy”, Artificial Intelligence in Medicine, Vol. 35, pp. 147–156, 2005.
L. Shi, J. Hao, J. Zhou, G. Xu, “Ant colony optimization algorithm with random perturbation behavior to the problem of optimal unit commitment with probabilistic spinning reserve determination”, Electric Power Systems Research, Vol. 69, pp. 295–303, 2004.
T. Keskint¨ urk, M.B. Yıldırım, M. Barut, “An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times”, Computers & Operations Research, Vol. 39, pp. 1225–1235, 2012. M. Dorigo, L.M. Gambardella, “Ant colonies for the TSP”, BioSystems, Vol. 43, pp. 73–81, 1997.
A.O. Bozdo˘ gan, A.E. Yılmaz, M. Efe, “Performance analysis of Swarm Optimization approaches for the generalized assignment problem in multi-target tracking applications”, Turkish Journal of Electrical Engineering & Computer Sciences, Vol. 6, pp. 1059–1076, 2010.
Wikipedia. Ant Colony Optimization. Available at http://en.wikipedia.org/wiki/ant colony optimization (accessed 02011).
K. Alaykıran, O. Engin, A. D¨ oyen, “Using ant colony optimization to solve hybrid flow shop scheduling problems”, Journal of Advanced Manufacturing Technology, Vol. 35, pp. 541–550, 2007.
L. Xie, H.B. Mei, “The application of the ant colony decision rule algorithm on distributed data mining”, Communications of the International Information Management Association, Vol. 7, pp. 85–94, 2007.
A. Akdaglı, K. G¨ uney, D. Karaboga, “Pattern nulling of linear antenna arrays by controlling only the element positions with the use of improved touring ant colony optimization algorithm”, Journal of Electromagnetic Waves and Applications, Vol. 8, pp. 4–10, 2002.
T. St¨ utzle, H. Hoos, “The MAX-MIN ant system and local search for the TSP”, Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 309–314, 1997.
D. Karaboga, K. Guney, A. Akdagli, “Antenna array pattern nulling by controlling both amplitude and phase using modified touring ant colony optimisation algorithm”, International Journal of Electronics, Vol. 91, pp. 241–251, 200 M. Dorigo, V. Maniezzo, A. Colorni, “Ant system: optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics: Part B: Cybernetics, Vol. 26, pp. 29–41, 1996.
J. Zhang, X. Hu, X. Tan, J.H. Zhong, Q. Huang, “Implementation of an ant colony optimization for job shop scheduling problem”, Transactions of the Institute of Measurement and Control, Vol. 28, pp. 93–108, 2006.
H. Zeng, T. Pukkala, H. Peltola, S. Kellom¨ aki, “Application of ant colony optimization for the risk management of wind damage in forest planning”, Silva Fennica, Vol. 41, pp. 315–332, 2007.
M. Dorigo, G.D. Caro, L.M. Gambardella, “Ant algorithms for discrete optimization”, Artificial Life, Vol. 5, pp. 137–172, 1999.
A. U˘ gur, D. Aydın, “Visualization with Java of ant system algorithm”, Akademik Bili¸sim, pp. 572–576, 2006.
Z. Dan, H. Hongyan, H. Yu, “The optimal selection of the parameters for the ant colony algorithm with smallperturbation”, International Conference on Computing, Control and Industrial Engineering, pp. 16–19, 2010.
H. Duan, G. Ma, S. Liu, “Experimental study of the adjustable parameters in basic ant colony optimization algorithm”, IEEE Congress on Evolutionary Computation, pp. 149–156, 2007.
G. Wang, W. Gong, R. Kastner, “System level partitioning for programmable platforms using the ant colony optimization”, International Workshop on Logic and Synthesis, 2004.
J.H. Zhao, Z. Liu, M.T. Dao, “Reliability optimization using multi objective ant colony system approaches”, Reliability Engineering and System Safety, Vol. 92, pp. 109–120, 2007.
Y. Zhang, B. Feng, S. Ma, “Text clustering based on fusion of ant colony and genetic algorithms”, Frontiers of Electrical and Electronic Engineering, Vol. 4, pp. 15–19, 2009.
G. Taguchi, E. Elsayed, T. Hsiang, Quality Engineering in Production Systems, New York, McGraw-Hill, 1989.
E. Canıyılmaz, F. Kutay, “An alternative approach to analysis of variance in Taguchi method”, Journal of the Faculty of Engineering and Architecture of Gazi University, Vol. 18, pp. 51–63, 2003.
S. Sa˘ gıroglu, N. ¨ Ozkaya, “An intelligent face features generation system from fingerprints”, Turkish Journal of Electrical Engineering & Computer Sciences, Vol. 17, pp. 183–203, 2009.
C. G¨ olo˘ glu, N. Sakarya, “The effects of cutter path strategies on surface roughness of pocket milling of 1.2738 steel based on Taguchi method”, Journal of Materials Processing Technology, Vol. 206, pp. 7–15, 2008.
Minitab Inc. Minitab Statistical Analysis Software. G. Taguchi, S. Chowdhury, Y. Wu, Taguchi’s Quality Engineering Handbook, New Jersey, Wiley-Interscience, 2004. ¨ O. Yeniay, “A comparison of the performances between a genetic algorithm and the Taguchi method over artificial problems”, Turkish Journal of Engineering & Environmental Sciences, Vol. 25, pp. 561–568, 2001.
C. G¨ olo˘ glu, C. Mızrak, “Customer driven product determination with fuzzy logic and Taguchi approaches”, Journal of the Faculty of Engineering and Architecture of Gazi University, Vol. 25, pp. 9–19, 2010.
E. Bonabeau, M. Dorigo, G. Theraulaz, Swarm Intelligence: From Natural to Artificial Systems, Oxford, Oxford University Press, 1999.
K. Danisman, I. Dalkiran, F.V. Celebi, “Design of a high precision temperature measurement system”, Lecture Notes in Computer Science, Vol. 3973, pp. 997–1004, 2006.
S. Mazzeo, I. Loiseau, “An ant colony algorithm for the capacitated vehicle routing”, Electronic Notes in Discrete Mathematics, Vol. 18, pp. 181–186, 2004.
C.F. Tsai, C.W. Tsai, H.C. Wu, T. Yang, “ACODF: A novel data clustering approach for data mining in large databases”, The Journal of Systems and Software, Vol. 73, pp. 133–145, 2004.
P. Korosec, J. Silc, B. Robic, “Solving the mesh-partitioning problem with an ant-colony algorithm”, Parallel Computing, Vol. 30, pp. 785–801, 2004.
C.S. Chang, L. Tian, F.S. Wen, “A new approach to fault section estimation in power systems using ant system”, Electric Power System Research, Vol. 49, pp. 63–70, 1999.
Y.H. Song, C.S. Chou, T.J. Stonham, “Combined heat and power economic dispatch by improving ant colony search algorithm”, Electric Power System Research, Vol. 52, pp. 115–121, 1999.
M.H. Afshar, “Improving the efficiency of ant algorithms using adaptive refinement: application to storm water network design”, Advances in Water Resources, Vol. 29, pp. 1371–1382, 2006.
M. Randall, A. Lewis, “A parallel implementation of ant colony optimization”, Journal of Parallel and Distributed Computing, Vol. 62, pp. 1421–1432, 2002.
S.C. Chu, J.F. Roddick, J.S. Pan, “Ant colony system with communication strategies”, Information Sciences, Vol. 167, pp. 63–76, 2004.
S.S. Weng, Y.H Liu, “Mining time series data for segmentation by using ant colony optimization”, European Journal of Operational Research, Vol. 173, pp. 921–937, 2006.
K.F. Doerner, W.J. Gutjahr, R.F. Strauss Hartl, C. Stummer, “Pareto ant colony optimization with ILP processing in multi objective project portfolio selection”, European Journal of Operational Research, Vol. 171, pp. 830–841, 200 K.C. Ying, C.J. Liao, “An ant colony system for permutation flow-shop sequencing”, Computers & Operations Research, Vol. 31, pp. 791–801, 2004.
C. Rajendran, H. Ziegler, “Two ant-colony algorithms for minimizing total flowtime ant in permutation flow shops”, Computers & Industrial Engineering, Vol. 48, pp. 789–797, 2005.
S.J. Shyu, B.M.T. Lin, P.Y Yin, ”Application of ant colony optimization for no-wait flow shop scheduling problem to minimize the total completion time”, Computers & Industrial Engineering, Vol. 47, pp. 181–193, 2004.
L.M. De Campos, J.M. Fernandez-Luna, J.A. Gamez, J.M. Puerta, “Ant colony optimization for learning Bayesian network”, International Journal of Approximate Reasoning, Vol. 31, pp. 291–311, 2002.
A. Lim, J. Lin, B. Rodrigues, F. Xiao, “Ant colony optimization with hill climbing for the bandwidth minimization problem”, Applied Soft Computing, Vol. 6, pp. 180–188, 2006.
R. Gao, J. Wu, “An improved ant colony optimization for routing in cognitive radio network”, International Journal of Advancements in Computing Technology, Vol. 3, pp. 73–81, 2011.
D. Merkle, M. Middendorf, H. Schmeck, “Ant colony optimization for resource-constrained project scheduling”, IEEE Transactions on Evolutionary Computation, Vol. 6, pp. 333–346, 2002.
X. Benlian, W. Zhiquan, “A multi-objective-ACO-based data association method for bearings-only”, Communications in Nonlinear Science and Numerical Simulation, Vol. 12, pp. 1360–1369, 2007.
H. Duan, X. Yu, “Hybrid ant colony optimization using memetic algorithm for TSP”, Proceedings of the IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning, pp. 92–95, 2007. C.F. Tsai, C.W. Tsai, C.C. Tseng, “A new hybrid heuristic approach for solving traveling salesman problem”. Information Science, Vol. 166, pp. 67–81, 2004.
J.J. Ortiz, I. Requena, “Azcatl-CRP: An ant colony-based system for searching full power control rod patterns in BWRs”, Annals of Nuclear Energy, Vol. 33, pp. 30–36, 2006.
H.R. Maier, A.C. Zecchin, L. Radbone, P. Goonan, “Optimizing the mutual information of ecological data clustering using evolutionary algorithms”, Mathematical and Computer Modelling, Vol. 44, pp. 439–450, 2006.
R.J. Kuo, H.S Wang, T.L Hu, S.H. Chou, “Applications of ant k-means on clustering analysis”, Computers & Mathematics with Applications, Vol. 50, pp. 1709–1724, 2005.
J.A. Gamez, J.M. Puerta, “Searching for the best elimination sequence in Bayesian networks by using ant colony optimization”, Pattern Recognition Letters, Vol. 23, pp. 261–277, 2002.
R.J. Kuo, Y.P. Kuo, K.Y. Chen, “Developing a diagnostic system through integration of fuzzy case-based reasoning and fuzzy ant colony system”, Expert Systems with Applications, Vol. 28, pp. 783–797, 2005.
P.Y. Yin, “Ant colony search algorithm for optimal polygonal approximation of plane curves”, Pattern Recognition, Vol. 36, pp. 1783–1797, 2003.
T. St¨ utzle, H.H. Hoos, “MAX–MIN ant system”, Future Generation Computer System, Vol. 16, pp. 889–914, 2000.