A Study of crossover operators for Genetic Algorithms to solve TSP
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, Student Mtech (Cse), , Proff. Mrs. Shakti Arora
Keywords
Related Articles
- EP ID EP162903
- DOI 10.9790/0661-16440508
- Views 108
- Downloads 0
A Novel Three-Dimensional Adaptive Localization (T-Dial)Algorithm for Wireless Sensor Networks
Abstract: Wireless Sensor Networks is one of the most important area of research. Over the time, WSN isexpanding its reach from scientific research and monitoring to industrial as well as military operations. With itsinc...
Image Based Authentication for Folder Security using Persuasive Cued Click-Points and SHA
Abstract: In this paper Image Based Authentication application is applied on folder’s (folders that are confidential to user) ,since the studies till date have shown that textual passwords are more prone that the...
Leveraging Map Reduce With Hadoop for Weather DataAnalytics
Abstract : Collecting, storing and processing of huge amounts of climatic data is necessary for accurateprediction of weather. Meteorological departments use different types of sensors such as temperature, humidity...
Language Mobile Learning Design: The Tamazight Language
Even though Tamazight language in Morocco has been legitimate for eleven years and official for almost two years, its learning needs a huge effort to successfully make it in this enormous batch of existing unformat...
Improved Intrusion Detection System Using Discriminative learning Approach (A Review)
Abstract: With the advent of anomaly-based intrusion detection systems, many approaches and techniques have been developed to track novel attacks on the systems. High detection rate of 98% at alow alarm rate of 1% can be...