Comparison of Different Genetic Crossover operators fortravelling salesman problem
Journal Title: IOSR Journals (IOSR Journal of Computer Engineering) - Year 2014, Vol 16, Issue 4
Abstract
Abstract: The travelling salesman problem (TSP) is the most well-known combinatorial optimization problem. TSP is used to find a routing of a salesman who starts from a home location, visits a prescribed set of cities and returns to the original location in such a way that the total distance travelled is minimized and each city is visited exactly once . This problem is known to be NP-hard, and cannot be solved exactly in polynomial time. Many exact and heuristic algorithms have been developed in the field of operations research (OR) to solve this problem . TSP is solved very easily when there is less number of cities, but as the number of cities increases it is very hard to solve, as large amount of computation time is required. The numbers of fields where TSP can be used very effectively are military and traffic. Another approach is to use genetic algorithm to solve TSP because of its robustness and flexibility . Some typical applications of TSP include vehicle routing, computer wiring, cutting wallpaper and job sequencingIn genetic algorithms, crossovers are used as a main search operator for TSP. There were a lot attempts to discover an appropriate crossover operator. This paper presents the strategy which used to find the nearly optimized solution to these type of problems. It is the order crossover operator (OX) which was proposed by Davis, which constructs an offspring by choosing a subsequence of one parent and preserving the relative order of cities of the other parent.
Authors and Affiliations
Poonam , Proff. Mrs. Shakti Arora
Keywords
Related Articles
- EP ID EP142162
- DOI 10.9790/0661-16440104
- Views 91
- Downloads 0
A Preprocessing Scheme for Line Detection with the Hough Transform for Mobile Robot Self-Navigation
Abstract: This paper presents the pre-processing scheme used for a vision system for a self-navigating mobile robot which relies on straight line detection using the Straight Line Hough transform. The straight line Hough...
Context-Centred Mobile Applications Development For Effective Adoption Of Mobile Technology
Abstract: Recent approaches in mobile computing consider context to be central to the design and implementation of mobile applications. Context considerations enables the mobile application to respond to the needs and pu...
Examining Performance of Bluetooth Network In The Presence of Wi-Fi System
Abstract: More recently, there has been a growing interest in cognitive techniques, which allow devices and even whole networks to monitor the environment in order to dynamically select and use the channel that aff...
The Cyberspace and Intensification of Privacy Invasion
Abstract: The widespread adoption of cyberspace for exceptional socio-economic activities, especially as it isconnecting populations around the globe in ways never foreseen is raising fresh security issues. What is...
Optical Character Recognition (OCR) System
Abstract: In the running world, there is growing demand for the software systems to recognize characters incomputer system when information is scanned through paper documents as we know that we have number ofnewspa...