 Open Access
 Total Downloads : 449
 Authors : Ankur Sharma, Vijay Maheshwari, Ratan Mishra
 Paper ID : IJERTV2IS50397
 Volume & Issue : Volume 02, Issue 05 (May 2013)
 Published (First Online): 16052013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
PopulationBased Optimization Genetic Algorithm Approaches for Solving the Travelling Salesman Problem
Ankur Sharma Shobhit University Meerut
Vijay Maheshwari Assistant Professor Shobhit University Meerut
Ratan Mishra
Assistant Professor
G.L. B.I.T.M. Gr. Noida
ABSTRACT
The Travelling Salesman Problem or the TSP is a representation of problems known as combinatorial optimization problems. In TSP, a map of cities is given to the salesman and he has to visit all the cities only once to complete a tour such that the length of the tour returning to the starting is the shortest among all possible tours for this map. The cost is assigned to the edges of a finite complete graph, and the goal is to find a Hamiltonian cycle, a cycle passing through all the vertices, of the graph while having the minimum cost. In TSP, Hamiltonian cycles are called tours. In this paper population based optimization Genetic Algorithm approach is used to solve TSP. various solutions are considered during the search procedure, and the population evolves until a solution satisfies the termination criteria.
General Terms
Genetic Algorithm (GA), Travelling Sales man Problem (TSP), Allele, Crossover, Mutation and Selection.
Keywords
Cyclic Crossover (CX), Order Crossover (OX), Partially Matched Crossover (PMX), Hamiltonian Cycle

INTRODUCTION
GA is especially appropriate for solving difficult optimization problems, for which conventional optimization methods are less efficient[1]. The problem is to find the shortest tour that passes through each vertex in a given graph exactly once and returns to the starting location. The fitness value measures how close the individual is to the optimum solution. A set of individuals is called a population that evolves from one generation to the next generation of new individuals and removal of some old ones[3]. The process starts with an initial population created randomly with the help of a function. This function has a constraint that an allele (feature value) of each chromosome must not be repeated in that chromosome[2]. It is called parent population. Each chromosome is the combination of numbers (allele). Each chromosome represents a Courier delivery tour (Hamiltonian cycle) where an each allele represents itself as a location and a path between location[4]. Two selected parent chromosomes can be combined by a crossover operator; it
must be replace the weakest chromosome in the population. Selection of each chromosome is performed by an algorithm according to the fitness of the chromosome. A new chromosome must be better than the replaced one. In this paper we will apply Ordered Crossover (OX), Cyclic Crossover (CX) and Partially Matched Crossover (PMX) operators to generate the optimal solution to TSP and compare their performances with each other. The Genetic Algorithm consists of four major stages: Generation of Random population, Selection, Crossover and Mutation[5]. The first step is only performed for the first iteration, but the other three steps are performed each iteration.

GENERATION OF POPULATION
We use random search approach for the generation of initial population. It only explores the search space by randomly selecting solutions & evaluates their fitness[1]. If the search space is finite, random search is guaranteed to reach the optimal solution. Gibbs law probability formula for finding the solution is:
P = e^(E/K*T)
Where E Energy, KBoltzmann constant, T Temperature

FITNESS FUNCTION
1 mark is assigned to pass each fitness function, while 0 marks are assigned in the case of failure. Chromosome is implemented in the form of array of size 10. The representation of chromosome is as following
Chromo [1] = 2; Chromo [2] = 3; Chromo [3] = 5;
Chromo [4] = 7; Chromo [5] = 10; Chromo [6] = 1;
Chromo [7] = 6; Chromo [8] = 4; Chromo [9] = 8;
Chromo [10] = 9;

SELECTION
The process of Selection is one of the critical phases in the process of evolution. Some of the best fit chromosomes are selected from parent population according to some selection criteria. We use maximum point and minimum distance criteria in this paper. The selection process used in this paper is as follows:
Parent1
Parent2
: 4 8 7  3
: 3 1 4  2
6 5
7 9
 1 10 9 2
 10 8 6 5
2
7
9
1 10 5 3
Value>fitness Offspring2 : 2 1 4
3
6
5
10 8 7 9

Initialize the population of individuals

Initialize the array[2*Psize] where Psize is the size of the population

Initialize the crossover array[Csize].

While values has next() Offspring1 : 4 8 6

Get the key and value, key>Individual key and

If the number of processed individuals < Psize then wait for individuals to be processed

Else

Apply crossover and Mutation

Increment processed by 1

If all individuals have been processed

Remove the previous ones

Perform selection and crossover for the final time

End if
If the fitness function of new solution is better than the fitness function of the current one, the solution is accepted. If the fitness function is not improved the new solution is retained with the probability:
P = e^(f(y)f(x))/K*T
Where, f(y)f(x) is the difference of the fitness function between the new and the old solution.


CROSSOVER/RECOMBINATION
Selected solutions are used for crossover. In this paper OX, CX and PMX population based optimization operators are considered.

Ordered Crossover (OX)
For given two parent chromosomes, two random crossover points are selected partitioning them into left, middle and right section from parent 1 and its middle section is determined by the genes in the middle section of parent 1 in the order in which the values appear in the parent 2. Similar process is applied to offspring 2.
Parent 1 : 4 2  1 3  6 5
Parent 2 : 2 3  1 4  5 6
Offspring 1 :
4 2  3 1  6
5
Offspring 2 :
2 3  4 1  5
6

Cyclic Crossover (CX)
Cycle performs recombination under the constraint that each gene comes from the parent or the other[1].

Partially Matched Crossover (PMX)
PMX can be applied to solve TSP[6]. Chromosomes are simply sequences of integers, where each integer represents a different city and order represents the time at which a city is visited. It may be viewed as a crossover of permutations that guarantees that all positions are found exactly once in each offspring. Suppose All the cities are sequentially numbered starting from 1. The route between the cities is described with an array with each element of array representing the number of the city. The array represents the sequence in which the cities are traversed to complete a tour[7]. Each chromosome must contain each and every city exactly once. In PMX two crossover points are randomly chosen and the region between them is determined. This regon is called Crossover region.
Where each offspring contains ordering information partially determined by each of its parents, PMX can be applied to the problems with permutation representation. If a parent has a rank higher than the threshold, then the parent is allowed to participate in the next round called Mutation. In the phase of Mutation, two random bits are chosen from every individual in population and swapped[8]. This process is repeated till values of the results are optimal or near optimal.


MUTATION
Mutation plays the role of recovering the lost genetic materials as well as for randomly disturbing genetic information. It is supposed to help for the exploration of the whole search space, also viewed as a background operator to maintain genetic diversity in the population[2].

TERMINATION CRITERIA
We will terminate the algorithm by equal fitness for the fittest selected chromosomes in respective iteration.

STEPS OF GENETIC ALGORITHM

Begin Genetic Algorithm

Initialize the population

Calculate the Cost of every individual (Fitness Value)

Same Ranked Individuals in the population are Randomly Deleted.

While termination criteria is reached

Select the parents from the current population using a selection algorithm

Generate new offsprings from the parents, perform crossover and mutation

Add the new offsprings into the population

End of While

The final population is the output.


EXPERIMENTAL DESCRIPTION
Suppose there are 10 different locations as shown in fig 1, a salesman is appointing to deliver courier in those locations. A tour can be mapped using the different type of representations like Paths with distances using Adjacency, ordinal and matrix.
Path The path representation is a simple way of representing chromosomes in a population. If the ith city is in the jth spot, then its the jth city visited.
The adjacency representation is a complete tour of n cities. The city j is listed.
Ordinal The ordinal representation is more flexible than above representation, the ith element can be represented from 1 to ni+1 values
Matrix The matrix binary representation as shown in Table 1, the row i and column j is 1 if and only if there is a path from city i to j. otherwise its zero.
Fig 1: Locations to deliver courier
Table 1. Adjacency Matrix of the above locations
i/j
13
20
34
49
57
63
73
84
92
10
13
0
5
0
8
17
12
6
21
30
25
20
5
0
4
7
15
0
0
23
31
24
34
0
4
0
0
7
0
12
15
17
0
49
8
7
0
0
6
4
9
13
15
0
57
17
15
7
6
0
0
13
0
7
4
63
12
0
0
4
0
0
5
5
7
4
73
6
0
12
9
13
5
0
8
12
10
84
21
23
15
13
0
5
8
0
7
6
92
30
31
17
15
7
7
12
7
0
3
10
25
24
0
0
4
4
10
6
3
0
In the above table, non zero numbers represent the distance between two locations. Zero (0) represents no path between two locations and the bold numbers represent the path between two locations due to sudden change in route. Table is used here to show the type of route between two locations. By Performing 10 iterations shown in fig 2, to find the shortest distance among them applying CX, PMX and OX operators used in GA and compare the results with each other below (shown in Table 2).
Analysis shows that in some of the iterations all the operators give the same optimal solution whereas in some of the iterations PMX operator gives more optimal solution and in some of the iterations OX operator gives more optimal solution but only in two iterations CX operator gives more optimal solution.
Fig 2: comparison of CX , PMX and OX operators
Table 2.
No. of iterations
Shortest distances PMX
Shortest distances CX
Shortest distances OX
1.
78
78
94
2.
85
85
85
3.
86
96
86
4.
152
156
112
5.
96
106
113
6.
197
118
137
7.
68
68
68
8.
100
100
100
9.
139
83
72
10.
104
104
104

CONCLUSION AND FUTURE WORK
Different operators have been used in this paper to design a new genetic algorithm keeping in mind the merits and demerits of various approaches. This solution to TSP can be applied to different optimization problems like shipping, aviation industry and setting up factories across the globe[9]. The overall cost of transport can be reduced. Lot of research has been in done in Gentic Algorithms to optimize NPHard problems. The performance of optimization can be enhanced in future by using Hybrid operator.
The contributions of this paper are as follows

Design of a Robust Genetic Algorithm.

Comparison of different approaches used by Genetic Algorithm.


REFERENCES

Introduction to genetic algorithm by S.N.Shivanandnam and S.N.Deepa.

G. Clarke and J.W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res., vol. 12, pp. 568581, 1964.

D. Whitely, T. Starkweather, and F. DAnn, Scheduling problems and traveling salesman: The genetic edge recombination operator, in Proc. 3rd Int. Conf. Genetic Algorithms, 1989, pp. 133140.

R. Wong, Integer programming formulations of the travelling salesman problem, in: Proceedings of the IEEE International Conference of Circuits and Computers, 1980, pp. 149152.

An efficient genetic algorithm for the traveling salesman problem with precedence constraints Chiung Moon a,*, Jongsoo Kim a, Gyunghyun Choi a, Yoonho Seo Department of Industrial Engineering, Hanyang University, Ansan 425 791, Republic of Korea b School of Industrial Engineering, University of Ulsan, Ulsan 680749, Republic of Korea

An Evolutionary Algorithm for Large Traveling Salesman Problems HuaiKuang Tsai, JinnMoon Yang, YuanFang Tsai, and ChengYan Kao IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICSPART B: CYBERNETICS, VOL. 34, NO. 4, AUGUST 2004.

The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach John Silberholz1 and Bruce L. Golden2.

The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach by John Silberholz, University of Maryland Bruce Golden, University of Maryland Presented at INFORMS 2007 Coral Gables, January 2007.

Neural Network, Fuzzy Logic , Genetic Algorithm:Systhesis and application by S Rajshekharan and GA Vijayalakhmi Pai.