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 91
- Downloads 0
Simulation of Route Optimization with load balancing Using AntNet System
This paper is based on analysis of the performance of load balancing and route optimization in computerized networks. The complete system model shows the scenario of Packet distribution between nodes, and if cong...
Adaptive ARA Algorithm (AARA): Proposed Modifications and Experimental Results
A survey on context aware system & intelligent Middleware’s
Context aware system or Sentient system is the most profound concept in the ubiquitous computing. In the cloud system or in distributed computing building a context aware system is difficult task and programmer...
Privacy Protection in Distributed Industrial System
Abstract: Although awareness is constantly rising, that industrial computer networks (in a very broad sense)can be exposed to serious cyber threats, many people still think that the same countermeasures, developed...
Optimizing Migration of the Application Data in Cloud Environment Using ACO Algorithm and RSA Encryption
Abstract: Taking the advantages of the capabilities offered by cloud computing requires either an application to be built especially for it, or for existing application to migrated to it. The main focus on migrate the ap...