Research Article
Study of Some Recent Crossovers Effects on Speed and Accuracy of Genetic Algorithm, using Symmetric Travelling Salesman Problem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 80 - Issue 6 |
| Published: October 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 },
year = { 2013 },
volume = { 80 },
number = { 6 },
pages = { 1-6 },
doi = { 10.5120/13862-1716 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%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%T
%J International Journal of Computer Applications
%V 80
%N 6
%P 1-6
%R 10.5120/13862-1716
%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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- TSPLIB,http://www. iwr. uniheidelberg. de/groups/comopt/software/TSPLIB95/.
- 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.
- 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.
- 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
Keywords