Knowledge Application to Crossover Operators in Genetic Algorithm for Solving the Traveling Salesman Problem

Introduction

Genetic algorithms (GA) are very common and the simplest techniques to resolve the optimization problems in the search space. Firstly, it is necessary to recognize the problem in order to find the ideal solution and a GA that is capable to produce an optimum solution (Skinner, 2010). The selection and evolution principles of GA are mainly helpful in solving a given problem. GA are used to flourishing in an atmosphere within which there is an immense set of candidate solutions and in which the search space is irregular and has numerous ups and downs. The real genetic algorithm can perform in any surroundings; however, that is going to be significantly inferior largely by situation specific algorithms in the less complex search areas. Therefore, it should be acknowledged that GA are not the most effective alternative at all the time. Occasionally GA will take some time to run so each time not possible for actual time use. However, GA are comparatively one of the effective strategies to rapidly generate excellent results for a problem. Below mentioned are the steps involved in GA (Beasley et al., 1993; Mitchell et al., 1991):

• 1.

  Encode the Solutions

• 2.

  Generate fitness function

• 3.

  Make the Selection

• 4.

  Applying the Mutation/ Crossover

• 5.

  Decode the Solution

As illustrated by Fig.1, GA initiates with some set of pre-assumed solutions encoded in the form of chromosomes, called initial population. The fitness value of every solution is computed using a fitness function, that measures how much a solution or individual is close to the optimum solution. This evaluation leads to the appropriate selection of solutions for further crossover and mutation operations. Crossover is helpful in generating various combinations of unoptimized solutions whereas mutation leads to an innovative partial solution (Siwach et al., 2012; Penev, 2005; Ahmed, 2010). And in last, some particular individuals are selected based upon a criterion that leads to the formation of next generation and finding the optimum solution.

Figure 1.

Structure of Genetic Algorithm

Representation Of Tsp

Traveling Salesman Problem is a combinatorial problem of finding the shortest closed path covers each city in a given set of cities. TSP consider various set of permutation and each permutation defines a tour for the salesman. Consider, there are m cities named , then there can be m permutations . Purpose is to find a permutation Pi, which should have minimum sum of all the Euclidean distances between every node and its successor node. Assuming and as the coordinates of two nodes in the graph, its Euclidean distance E defined as (Siwach et al., 2012):