Population-Based Optimization Genetic Algorithm Approaches for Solving the Travelling Salesman Problem

Population-Based 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

1. 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.

2. 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, K-Boltzmann constant, T- Temperature

3. 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;

4. 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.

5. CROSSOVER/RECOMBINATION

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

   1. 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

   2. Cyclic Crossover (CX)

      Cycle performs recombination under the constraint that each gene comes from the parent or the other[1].

   3. 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.

6. 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].

7. TERMINATION CRITERIA

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

8. 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.

9. 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 n-i+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

10. 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 NP-Hard 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.

11. REFERENCES

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

2. 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.

3. 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.

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

5. 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 680-749, Republic of Korea

6. An Evolutionary Algorithm for Large Traveling Salesman Problems Huai-Kuang Tsai, Jinn-Moon Yang, Yuan-Fang Tsai, and Cheng-Yan Kao IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICSPART B: CYBERNETICS, VOL. 34, NO. 4, AUGUST 2004.

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

8. 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.

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