Open Access
Subscription Access
Open Access
Subscription Access
Solution Concept in TSP Problem Applied to Genetic Algorithm
Subscribe/Renew Journal
The main purpose of this study is to propose a new representation method of chromosomes using binary matrix and new fittest criteria to be used as method for finding the optimal solution for TSP. The concept of the proposed method is taken from genetic algorithm of artificial inelegance as a basic ingredient which has been used as search algorithm to find the near-optimal solutions. Here we are introducing the new fittest criteria for crossing over, and applying the algorithm on Symmetric as well as asymmetric TSP, also presenting asymmetric problem in a new and different way.
Keywords
Genetic Algorithm, Fittest Criteria, Asymmetric Travelling Salesman Problem.
Subscription
Login to verify subscription
User
Font Size
Information
- B. Freisieben and P. Merz, New Genetic Local Search Operator for Travelling salesman Problem, Conference on Parallel Problem Solving From nature, app. 890-899, 1996.
- P. van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Applications, Kluwer Academic, 1987,
- M. Dorigo and L. M. Gambradella, Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem, JEEE Transaction on Evolutionary Computation, Vol. l, pp. 53-66, 1997.
- D.E. Goldberg, Genetic Algorithm in Search, Optimization and Machine Learning. Addison-Wesley, 1989.
- Naef Taher Al Rahedi and Jalal Atoum, Solving TSP problem using New Operator in Genetic Algorithms, American Journal of Applied Sciences 6(8):1586-1590, 2009.
- Goldberg D., Computer-Aided Pipeline Operations Using Genetic Algorithms and Rule Learning. Part I; Genetic Algorithms in pipeline Optimization, Engineering with Computer 3, 1987.
- Greffenstette, J., Genetic Algorithms Made Easy, 1991.
- Poli, R., el. al. (Eds), Evolutionary Image Analysis, Signal Processing and Telecommunications Springer, 1999.
- Tsai, H. K., Yang, J. M., Tsai, Y. F., and Kao, C. Y. (2004). An evolutionary algorithm for large traveling salesman problems. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 34(4), 1718-1729
- G. Clarke and J.W. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Oper. Res., vol. 12, pp. 568–581, 1964.
- D. Whitely, T. Stark weather, and F. D’ Ann, “Scheduling problems and traveling salesman: The genetic edge recombination operator,” in Proc. 3rd Int. Conf. Genetic Algorithms, 1989, pp. 133–140.
- S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, pp. 498–516, 1983.
- F. Alizadeh, R. M. Karp, L. A. Newberg, and D. K. Weisser, “Physical mapping of chromosomes: A combinatorial problem in molecular biology,” in Proc. 4th ACM-SIAM Symp. Discrete Algorithms (SODA), 1993, pp. 52–76.
- C. Korostensky and G. H. Gonnet, “Using traveling salesman problem algorithms for evolutionary tree construction,” Bioinformatics, vol. 16, no. 7, pp. 619–627, 2000.
- H. J. Bremermann, M. Rogson, and S. Salaff, “Search by evolution,” in Biophysics and Cybernetic Systems. Washington, DC: Spartan, 1965, pp. 157–167.
- M. Oliver, D. J. Smith, and J. R. C. Holland, “A study of permutation crossovers on the TSP,” in Proc. 2nd Int. Conf. Genetic Algorithm Their Applications, 1987, pp. 224–230.
- Handbook Genetic Algorithms, L. Davis, Ed., Van Nostrand, New York, 1991, pp. 332–349.
- H. Mühlenbein, M. Gorges-Schleuter, and O. Krämer, “Evolution algorithms in combinatorial optimization,” Parallel Comput., vol. 7, pp. 65–85, 1988.
- J. J. Grefenstette, “Incorporating problem specific knowledge into genetic algorithms,” Genetic Algorithms Simulated Annealing, pp. 42–60, 1987.
- B. Freisleben and P. Merz, “New genetic local search operators for the traveling salesman problem,” in Proc. Parallel Problem Solving Nature IV (PPSN IV), 1996, pp. 890–899.
Abstract Views: 190
PDF Views: 0