Study of Crossover operators in Genetic Algorithm for Travelling Salesman Problem

Main Article Content

Isha Gupta
Anshu Parashar

Abstract

Genetic Algorithm (GA) is an approximate algorithm that doesn’t always aim to find the shortest tour but to find a reasonably short tour quickly, which is a search procedure inspired by the mechanisms of biological evolution. In genetic algorithms, crossovers are used as a main search operator for TSP. The role of crossovers is to generate offspring that are better tours by preserving partial tours from the parents. In this paper Travelling Salesman Problem is taken as domain. TSP has been known to be NP-complete and is a standard example of such problems. In this paper various Crossover Operators are studied like Partially-Mapped Crossover operator (PMX), Cyclic Crossover Operator (CX), Order Crossover Operator (OX), Linear Crossover Operator (LOX) and Sequential Constructive crossover operator (SCX). Brief discussion about these operators is represented.

 

 

Keywords- Cyclic crossover, Partially-mapped crossover, order crossover, Linear Crossover, Sequential crossover, Genetic algorithm, Travelling salesman problem.

Downloads

Download data is not yet available.

Article Details

Section
Articles