We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Study of Some Recent Crossovers Effects on Speed and Accuracy of Genetic Algorithm, using Symmetric Travelling Salesman Problem

by Hassan Ismkhan, Kamran Zamanifar
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 80 - Number 6
Year of Publication: 2013
Authors: Hassan Ismkhan, Kamran Zamanifar
10.5120/13862-1716

Hassan Ismkhan, Kamran Zamanifar . Study of Some Recent Crossovers Effects on Speed and Accuracy of Genetic Algorithm, using Symmetric Travelling Salesman Problem. International Journal of Computer Applications. 80, 6 ( October 2013), 1-6. DOI=10.5120/13862-1716

@article{ 10.5120/13862-1716,
author = { Hassan Ismkhan, Kamran Zamanifar },
title = { Study of Some Recent Crossovers Effects on Speed and Accuracy of Genetic Algorithm, using Symmetric Travelling Salesman Problem },
journal = { International Journal of Computer Applications },
issue_date = { October 2013 },
volume = { 80 },
number = { 6 },
month = { October },
year = { 2013 },
issn = { 0975-8887 },
pages = { 1-6 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume80/number6/13862-1716/ },
doi = { 10.5120/13862-1716 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:53:47.681846+05:30
%A Hassan Ismkhan
%A Kamran Zamanifar
%T Study of Some Recent Crossovers Effects on Speed and Accuracy of Genetic Algorithm, using Symmetric Travelling Salesman Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 80
%N 6
%P 1-6
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Travelling Salesman Problem (TSP) is one of the most famous optimization problems. The Genetic Algorithm (GA) is one of metaheuristics that have been applied to TSP. The Crossover and mutation operators are two important elements of GA. There are many TSP solver crossover operators. In this paper, we state implementation of some recent TSP solver crossovers at first and then we use each of them in GA to solve some Symmetric TSP (STSP) instances and finally compare their effects on speed and accuracy of presented GA.

References
  1. P. LARRANAGA, C. M. H. Kuijpers, R. H. Murga, I. Inza and S. Dizdarevic. "Genetic algorithms for the travelling salesman problem: A review of representations and Operators". Artificial Intelligence Review, vol. 13, pp. 129-170, April. 1999.
  2. J. J. Grefenstette, R. Gopal, B. Rosmaita, and D. VanGucht, "Genetic algorithms for the traveling salesman problem," in Proc. the 1st International Conference on Genetic Algorithms, 1985, pp. 160–168.
  3. G. E. Liepins, M. R. Hilliard, Mark Palmer and Michael Morrow, "Greedy genetics," in Proc. the Second International Conference on Genetic algorithms and their application, October 1987, pp. 90-99.
  4. J. Y. Suh, D. V. Gucht, "Incorporating heuristic information into genetic search," in Proc. the Second International Conference on Genetic algorithms and their application, October 1987, pp. 100-107.
  5. P. Jog, J. Y. Suh, and D. V. Gucht, "The effects of population size, heuristic crossover, and local improvement on a genetic algorithm for the traveling salesman problem," in Proc. the Third International Conference on Genetic Algorithms, 1989, pp. 110-115. B. A. Julstrom. "Very greedy crossover in a genetic algorithm for the traveling salesman problem. " 1995 ACM symposium on applied computing, 1995, pp. 324-328.
  6. H. D. Nguyen, I. Yoshihara, K. Yamamori, and M. Yasunaga, "Greedy genetic algorithms for symmetric and asymmetric TSPs," IPSJ Trans. Math. Modeling and Appl. , vol. 43, no. SIG10 (TOM7), pp. 165–175, Nov. 2002.
  7. H. Sengoku and I. Yoshihara, "A fast TSP solver using GA on JAVA," in Proc. 3rd Int. Symp. Artif. Life and Robot. , 1998, pp. 283–288.
  8. A. Takeda, S. Yamada, K. Sugawara, I. Yoshihara, and K. Abe, "Optimization of delivery route in a city area using genetic algorithm," in Proc. 4th Int. Symp. Artif. Life and Robot. , 1999, pp. 496–499.
  9. B. Freisleben and P. Merz, "A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems," in Proc. the 1996 IEEE International Conference on Evolutionary Computation, (Nagoya, Japan), pp. 616-621, 1996.
  10. B. Freisleben and P. Merz, "New Genetic Local Search Operators for the Traveling Salesman Problem," in Proc. the 4th Conference on Parallel Problem Solving from Nature – PPSN IV, (H. -M. Voigt, W. Ebeling, I. Rechenberg, and H. -P. Schwefel,eds. ), pp. 890-900, Springer, 1996.
  11. TSPLIB,http://www. iwr. uniheidelberg. de/groups/comopt/software/TSPLIB95/.
  12. 12. Z. Tao. "TSP Problem solution based on improved Genetic Algorithm". Fourth International Conference on Natural Computation. ICNC '08. Vol. 1, pp. 686-690, 2008.
  13. H. Ismkhan and K. Zamanifar. "Using ants as a genetic crossover operator in GLS to solve STSP". 2010 International Conference of Soft Computing and Pattern Recognition (SoCPaR), Cergy-Pontoise, France, 2010, pp. 344 – 348.
  14. G. Vahdati, M. Yaghoubi, M. Poostchi and S. Naghibi. "A New Approach to Solve Traveling Salesman Problem Using Genetic Algorithm Based on Heuristic Crossover and Mutation Operator," in Proc. SoCPaR, 2009, pp. 112-116.
Index Terms

Computer Science
Information Sciences

Keywords

Symmetric Traveling Salesman Problem STSP Crossover Genetic Algorithm GA.

Powered by PhDFocusTM