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 92
- Downloads 0
Develop a mobility model for MANETs networks based on fuzzy Logic
Abstract: The study and research in the field of networks MANETs depends alleged understand the protocols well of the simulation process before they are applied in the real world, so that we create an environment similar...
Analysis of Binpacking
The main objective of this problem is to pack objects of fixed volume into bins, each of them having a maximum capacity, so as to minimize the total number of bins used. Binpacking is an Np-complete problem as the...
Survey and Analysis on Migration of Legacy System to Service Oriented Architecture
A number of new generation languages have been evolved for the past few years and have been adapted by the industries. As a result of which the project done under 3GL are becoming Legacy and also the informat...
Secured Cloud Information Accountability for Data Sharing Using Identity Based Encryption Algorithm
Abstract : Cloud Computing provides scalable services which can be used by user on a need basis. These services can be accessed through the internet. User stores important data (mainly, financial and health data) o...
Evaluating Total Cost of Ownership for University EnterpriseResource Planning: Case of Maseno University
Abstract: Higher learning institutions (HEI) are investing in IT to attain operational excellence. Organizationslooking to reduce technology costs typically look for ways to reduce the Total Cost of Ownership (TCO)...