CFP last date
22 April 2024
Call for Paper
May Edition
IJCA solicits high quality original research papers for the upcoming May edition of the journal. The last date of research paper submission is 22 April 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A Learning Automata based Algorithm for Solving Traveling Salesman Problem improved by Frequency-based Pruning

by Mir Mohammad Alipour
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 46 - Number 17
Year of Publication: 2012
Authors: Mir Mohammad Alipour
10.5120/7007-9328

Mir Mohammad Alipour . A Learning Automata based Algorithm for Solving Traveling Salesman Problem improved by Frequency-based Pruning. International Journal of Computer Applications. 46, 17 ( May 2012), 7-13. DOI=10.5120/7007-9328

@article{ 10.5120/7007-9328,
author = { Mir Mohammad Alipour },
title = { A Learning Automata based Algorithm for Solving Traveling Salesman Problem improved by Frequency-based Pruning },
journal = { International Journal of Computer Applications },
issue_date = { May 2012 },
volume = { 46 },
number = { 17 },
month = { May },
year = { 2012 },
issn = { 0975-8887 },
pages = { 7-13 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume46/number17/7007-9328/ },
doi = { 10.5120/7007-9328 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:39:58.534423+05:30
%A Mir Mohammad Alipour
%T A Learning Automata based Algorithm for Solving Traveling Salesman Problem improved by Frequency-based Pruning
%J International Journal of Computer Applications
%@ 0975-8887
%V 46
%N 17
%P 7-13
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Many real world industrial applications involve finding a Hamiltonian path with minimum cost. Some instances that belong to this category are transportation routing problem, scan chain optimization and drilling problem in integrated circuit testing and production. Distributed learning automata, that is a general searching tool and is a solving tool for variety of NP-complete problems, together with 2-opt local search is used to solve the Traveling Salesman Problem (TSP). Two mechanisms named frequency-based pruning strategy (FBPS) and fixed-radius near neighbour (FRNN) 2-opt are used to reduce the high overhead incurred by 2-opt in the DLA algorithm proposed previously. Using FBPS only a subset of promising solutions are proposed to perform 2-opt. Invoking geometric structure, FRNN 2-opt implements efficient 2-opt in a permutation of TSP sequence. Proposed algorithms are tested on a set of TSP benchmark problems and the results show that they are able to reduce computational time, while maintaining the average solution quality at 0. 62% from known optimal.

References
  1. G. Laporte, "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, vol. 59, no. 2, pp. 231-247, 1992.
  2. G. Laporte, "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, vol. 59, no. 2, pp. 231-247, 1992.
  3. D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, "An analysis of several heuristics for the traveling salesman problem," SIAM Journal on Computing, vol. 6 , no. 3, pp. 563-581, 1977.
  4. A. M. Frieze, "An extension of Christofides heuristic to the k-person travelling salesman problem," Discrete Applied Mathematics, vol. 6, no. 1, pp. 79-83, 1983.
  5. B. Chandra, H. Karloff, and C. Tovey, "New results on the old k-opt algorithm for the traveling salesman problem," SIAM Journal on Computing, vol. 28, no. 6, pp. 1998-2029, 1999.
  6. S. Lin and B. W. Kerninghan, "An effective heuristic algorithm for the traveling salesman problem," Operations Research, vol. 21, no. 2, pp. 498-516, 1973.
  7. E. H. L. Aarts, J. H. M. Korst, and P. J. M. Vanlaarhoven, "A quantitative analysis of the simulated annealing algorithm - A case study for the traveling salesman problem," Journal of Statistical Physics, vol. 50, no. 1-2, pp. 187-206, 1988.
  8. J. Knox, "Tabu search performance on the symmetric traveling salesman problem," Computers & Operations Research, vol. 21, no. 8, pp. 867-876, 1994.
  9. B. Freisleben and P. Merz, "A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems," in Proceedings of International Conference on Evolutionary Computation, 1996. pp. 616-621.
  10. P. Merz and B. Freisleben, "Genetic local search for the TSP: New results," in Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, 1997. pp. 159-164.
  11. C. M. White and G. G. Yen, "A hybrid evolutionary algorithm for traveling salesman problem," in Proceedings of Congress on Evolutionary Computation, 2004, CEC2004. , 2004. pp. 1473 -1478.
  12. L. M. Gambardella and M. Dorigo, "Solving symmetric and asymmetric TSPs by ant colonies," in Proceedings of IEEE International Conference on Evolutionary Computation, 1996. 1996. pp. 622-627.
  13. T. Stützle and H. Hoos, "MAX-MIN ant system and local search for the traveling salesman problem," in Proceedings of ICEC'97 - 1997 IEEE 4th International Conference on Evolutionary Computation, 1997. pp. 308-313.
  14. P. Lucic and D. Teodorovic, "Computing with Bees: Attacking Complex Transportation Engineering Problems," International Journal on Artificial Intelligence Tools, vol. 12, no. 3, pp. 375-394, 2003.
  15. M. Alipour, "Solving Traveling Salesman Problem Using Distributed Learning Automata improved by 2-opt local search heuristic," Proceedings of First CSUT Conference on Computer, Communication and Information Technology, Computer Science Department, Tabriz University, Tabriz, Iran, pp. 256-264 Nov. 2011.
  16. J. L. Bentley, "Fast algorithms for geometric traveling salesman problems," ORSA Journal on Computing, vol. 4, no. 4, pp. 387–441, 1992.
  17. K. S. Narendra and K. S. Thathachar, "Learning Automata: An Introduction," (Prentice-Hall, New York, 1989).
  18. M. A. L. Thathachar and P. S. Sastry, "A hierarchical system of learning automata that can learn the globally optimal path," Information Science 42 (1997) 743–766.
  19. M. A. L. Thathachar and B. R. Harita, "Learning automata with changing number of actions," IEEE Trans. Systems, Man, and Cybernetics SMG17 (1987) 1095–2400.
  20. M. A. L. Thathachar and V. V. Phansalkar, "Convergence of teams and hierarchies of learning automata in connectionist systems," IEEE Trans. Systems, Man and Cyber-netics 24 (1995) 1459–1469.
  21. S. Lakshmivarahan andM. A. L. Thathachar, "Bounds on the convergence probabilities of learning automata," IEEE Trans. Systems, Man, and Cybernetics, SMC-6 (1976) 756–763.
  22. K. S. Narendra and M. A. L. Thathachar, "On the behavior of a learning automaton in a changing environment with application to telephone traffic routing," IEEE Trans. Systems, Man, and Cybernetics SMC-l0(5) (1980) 262–269.
  23. M. Alipour, "A learning automata based algorithm for solving capacitated vehicle routing problem," International Journal of Computer Science Issues Vol. 9, Issue 2, No 1, pp. 138–145 March 2012.
  24. J. S. Gero and V. A. Kazakov, "Evolving design genes in space layout planning problems," Artificial Intelligence in Engineering, vol. 12, no. 3, pp. 163–176, 1998.
  25. J. S. Gero, V. A. Kazakov, and T. Schnier, "Genetic engineering and design problems," in Evolutionary Algorithms in Engineering Applications, D. Dasgupta and Z. Michalewicz, Eds. Berlin: Springer, 1997, pp. 47–68.
Index Terms

Computer Science
Information Sciences

Keywords

Traveling Salesman Problem Distributed Learning Automata Frequency-based Pruning Strategy Fixed-radius Near Neighbour

Powered by PhDFocusTM