Proceedings of the World Congress on Engineering 2011 Vol II

WCE 2011, July 6 - 8, 2011, London, U.K.

Genetic Algorithm Performance with Different

Selection Strategies in Solving TSP
Noraini Mohd Razali, John Geraghty

Abstract—A genetic algorithm (GA) has several genetic The different selection strategy used in the GA process
operators that can be modified to improve the performance of will significantly affect the performance of the algorithm
particular implementations. These operators include parent differently. This study is intended to examine the
selection, crossover and mutation. Selection is one of the performance of GA when using different selection strategy
important operations in the GA process. There are several ways
specifically in solving the travelling salesman problem
for selection. This paper presents the comparison of GA
performance in solving travelling salesman problem (TSP) (TSP). TSP is a classical example of a NP-hard
using different parent selection strategy. Several TSP instances combinatorial optimization problem. Many production and
were tested and the results show that tournament selection scheduling problems can be reduced to a simple concept that
strategy outperformed proportional roulette wheel and rank- there is a salesman who must travel from city to city, visiting
based roulette wheel selections, achieving best solution quality each city exactly once and returning to the home city [2]. It
with low computing times. Results also reveal that tournament
and proportional roulette wheel can be superior to the rank-
is possible for the salesman to select the orders of the cities
based roulette wheel selection for smaller problems only and visited so that the total distances travelled in his tour is as
become susceptible to premature convergence as problem size small as possible which will apparently save him time and
increases. money [2]. Although TSP is conceptually simple, it is
difficult to obtain an optimal solution. The main difficulty of
Index Terms— Genetic algorithm, Selection, Travelling this problem is the enormous number of possible tours; (n-
salesman problem, Optimization
1)!/2 for symmetric n cities tour. As the number of cities in
the problem increases, the numbers of permutations of valid
tours are also increase. It is this factorial growth that makes
I. INTRODUCTION
the task of solving the TSP immense even for modest n sized

B asic genetic algorithm (GA) is generally composed of

two processes. The first process is selection of
individuals for the production of the next generation and the
problems.
The remainder of this paper is organized as follows:
Section II presents a brief summary of the previous works on
second process is manipulation of the selected individuals to selection strategy. Section III contains an overview of the
form the next generation by crossover and mutation genetic algorithm for TSP, while Section IV describes into
techniques. The selection mechanism determines which more detail on selection strategy that used in the
individuals are chosen for mating (reproduction) and how experiments. Section V tests the performance of GA and
many offspring each selected individual produces. The main discusses the experimental results. The conclusions are
principle of selection strategy is “the better is an individual; summarized in Section VI.
the higher is its chance of being parent.” Generally,
crossover and mutation explore the search space, whereas II. PREVIOUS WORK ON SELECTION STRATEGY
selection reduces the search area within the population by
Several researchers have studied the performance of GA
discarding poor solutions. However, worst individuals
using different selection strategy; yet almost none of them
should not be discarded and they have some chances to be
tested on TSP problem. The performance of GA is usually
selected because it may lead to useful genetic material. A
evaluated in terms of convergence rate and the number of
good search technique must find a good trade-off between
generations to reach the optimal solution. Jadaan et al. [3]
exploration and exploitation in order to find a global
for example compared the results of GA between
optimum [1]. Hence, it is important to find a balance
proportional roulette wheel and rank-based roulette wheel
between exploration (i.e. poor solutions must have chance to
selection method using several mathematical fitness
go to the next generation) and exploitation (i.e. good
functions and found that rank-based outperformed
solutions go to the next generation more frequently than
proportional in number of generations to come out with the
poor solutions) within the mechanism of the selection.
optimal solution. He observed that rank-based is steadier,
Manuscript received March 6, 2011; revised March 21, 2011. This work faster, certainty and more robust towards the optimum
was supported by the University Malaysia Pahang (UMP) in collaboration solutions than proportional roulette wheel. On the other
with Dublin City University, Ireland. Noraini Mohd Razali is with School
hand, Zhong et al. [4] compared proportional roulette wheel
of Mechanical & Manufacturing Engineering, Dublin City University,
Ireland (e-mail: norainimbr@[Link]). John Geraghty is with with tournament selection, with tournament size equal 6 at
Enterprise Research Process Centre, Dublin City University, Ireland (e- seven general test functions and concluded algorithm with
mail: [Link]@[Link]). the tournament selection is more efficient in convergence

ISBN: 978-988-19251-4-5 WCE 2011

ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online)
Proceedings of the World Congress on Engineering 2011 Vol II
WCE 2011, July 6 - 8, 2011, London, U.K.

than proportional roulette wheel selection. Julstrom [5] in TSP [10]. The TSP consists a number of cities, where
investigated the computing time efficiency of two types of each pair of cities has a corresponding distance. The aim is
rank-based selection probabilities; linear ranking and to visit all the cities such that the total distance travelled will
exponential ranking probabilities and compared with be minimized. Obviously, a solution, and therefore a
tournament selection. He pointed that tournament selection chromosome which represents that solution to the TSP, can
is preferred over rank-based selection because repeated be given as an order, that is, a path, of the cities.
tournament selection is faster than sorting the population to The procedure for solving TSP can be viewed as a
assign rank-based probabilities. In addition, Mashohor et al. process flow given in Fig. 1. The GA process starts by
[6] evaluated the performance of PCB inspection system supplying important information such as location of the city,
using three GA selection method; deterministic, tournament maximum number of generations, population size,
and roulette wheel and discovered that deterministic has the probability of crossover and probability of mutation. An
ability to reach the highest maximum fitness with lowest initial random population of chromosomes is generated and
number of generations for all test images. This is then the fitness of each chromosome is evaluated. The population
followed by roulette wheel and tournament selection. is then transformed into a new population (the next
Goh et al. [7] in his work entitled sexual selection for “generation”) using three genetic operators: selection,
genetic algorithms focused on the selection stage of GA and crossover and mutation. The selection operator is used to
examined common problems and solution methods for such choose two parents from the current generation in order to
selection schemes. He proposed a new selection scheme procreate a new child by crossover and/or mutation. The
called sexual selection and compared the performance with new generation contains a higher proportion of the
commonly used selection methods in solving the Royal road characteristics possessed by the „good‟ members of the
problem, the open shop scheduling and the job shop previous generation and in this way good characteristics are
scheduling problem. He claimed that the proposed selection spread over the population and mixed with other good
scheme performed either on-par or better than roulette wheel characteristics. After each generation, a new set of
selection on average when no fitness scaling is used. The chromosomes where the size is equal to the initial population
new scheme also performed better on average when size is evolved. This transformation process from one
compared to tournament selection in the more difficult test generation to the next continues until the population
cases when no scaling is used. Apart from that, Goldberg converges to the optimal solution, which usually occurs
and Deb [8] did comprehensive studies on proportional, when a certain percentage of the population (e.g. 90%) has
ranking, tournament and Genitor (steady state) selection the same optimal chromosome in which the best individual is
schemes on the basis of solutions to differential equations. taken as the optimal solution.
Their studies have been performed to understand the
expected fitness ratio and convergence time. They found
that ranking and tournament selection outperformed
proportional selection in terms of maintaining steady
pressure toward convergence. They further demonstrated
that linear ranking selection and stochastic binary
tournament selection have identical expectations, but
recommended binary tournament selection because of its
more efficient time complexity.

III. GENETIC ALGORITHM FOR TSP

This section provides the general overview of the genetic
algorithm component and operation for solving TSP.
Genetic algorithm is an optimization method that uses a
stochastic approach to randomly search for good solutions to
a specified problem. These stochastic approaches use
various analogies of natural systems to build promising
solutions, ensuring greater efficiency than completely
random search. The basic principles of GA were first
proposed by Holland in 1975 [9]. The GA operation is based
on the Darwinian principle of „survival of the fittest‟ and it
implies that the fitter individuals are more likely to survive Fig. 1. Genetic algorithm procedure for TSP
and have a greater chance of passing their good genetic
features to the next generation. In genetic algorithm, each IV. SELECTION STRATEGY FOR REPRODUCTION
individual i.e. chromosome that is a member of the The selection strategy addresses on which of the
population represents a potential solution to the problem. chromosomes in the current generation will be used to
There are a number of possible chromosome representations, reproduce offspring in hopes that next generation will have
due to a vast variety of problem types. The „path‟ even higher fitness. The selection operator is carefully
representation is more natural to represent the chromosome formulated to ensure that better members of the population

ISBN: 978-988-19251-4-5 WCE 2011

ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online)
Proceedings of the World Congress on Engineering 2011 Vol II
WCE 2011, July 6 - 8, 2011, London, U.K.

(with higher fitness) have a greater probability of being population because they lost a tournament.
selected for mating or mutate, but that worse members of the
population still have a small probability of being selected,
and this is important to ensure that the search process is
global and does not simply converge to the nearest local
optimum. Different selection strategies have different
methods of calculating selection probability. The differing
selection techniques all develop solutions based on the
principle of survival of the fittest. Fitter solutions are more
likely to reproduce and pass on their genetic material to the Fig. 3. Procedure for tournament selection
next generation in the form of their offspring. There are
three major types of selection schemes will be discussed and
B. Proportional Roulette Wheel Selection
experimented in this study; tournament selection, roulette
wheel, and rank-based roulette wheel selection. The In proportional roulette wheel, individuals are selected
subsequent section will describe the mechanism of each with a probability that is directly proportional to their fitness
strategy. A more detailed of selection method can be found values i.e. an individual‟s selection corresponds to a portion
of a roulette wheel. The probabilities of selecting a parent
in [8, 11, 12, 13].
can be seen as spinning a roulette wheel with the size of the
A. Tournament Selection segment for each parent being proportional to its fitness.
Tournament selection is probably the most popular Obviously, those with the largest fitness (i.e. largest segment
selection method in genetic algorithm due to its efficiency sizes) have more probability of being chosen. The fittest
and simple implementation [8]. In tournament selection, n individual occupies the largest segment, whereas the least fit
individuals are selected randomly from the larger have correspondingly smaller segment within the roulette
wheel. The circumference of the roulette wheel is the sum of
population, and the selected individuals compete against
all fitness values of the individuals. The proportional
each other. The individual with the highest fitness wins and
roulette wheel mechanism and the algorithm procedure are
will be included as one of the next generation population.
depicted in Fig. 4 and Fig. 5 respectively. In Fig. 4, when the
The number of individuals competing in each tournament is wheel is spun, the wheel will finally stop and the pointer
referred to as tournament size, commonly set to 2 (also attached to it will point on one of the segment, most
called binary tournament). Tournament selection also gives a probably on one of the widest ones. However, all segments
chance to all individuals to be selected and thus it preserves have a chance, with a probability that is proportional to its
diversity, although keeping diversity may degrade the width. By repeating this each time an individual needs to be
convergence speed. Fig. 2 illustrates the mechanism of chosen, the better individuals will be chosen more often than
tournament selection while Fig. 3 shows the procedure for the poorer ones, thus fulfilling the requirements of survival
tournament selection. The tournament selection has several of the fittest. Let f1, f2,…, fn be fitness values of individual 1,
advantages which include efficient time complexity, 2,…, n. Then the selection probability, P i for individual i is
especially if implemented in parallel, low susceptibility to define as,
takeover by dominant individuals, and no requirement for
pi 

fitness scaling or sorting [8, 12]. fi (1)
n
j 1 j
f

The basic advantage of proportional roulette wheel

selection is that it discards none of the individuals in the
population and gives a chance to all of them to be selected.
Therefore, diversity in the population is preserved.
However, proportional roulette wheel selection has few
Fig. 2. Selection strategy with tournament mechanism
major deficiencies. Outstanding individuals will introduce a
bias in the beginning of the search that may cause a
In the above example, the tournament size, Ts is set to premature convergence and a loss of diversity. For example,
three, which mean that three chromosomes competing each if an initial population contains one or two very fit but not
other. Only the best chromosome among them is selected to the best individuals and the rest of the population are not
reproduce. In tournament selection, larger values of good, then these fit individuals will quickly dominate the
tournament size lead to higher expected loss of diversity [12, whole population and prevent the population from exploring
14]. The larger tournament size means that a smaller portion other potentially better individuals. Such a strong
of the population actually contributes to genetic diversity, domination causes a very high loss of genetic diversity
making the search increasingly greedy in nature. There which is definitely not advantageous for the optimization
might be two factors that lead to the loss of diversity in process. On the other hand, if individuals in a population
regular tournament selection; some individuals might not get have very similar fitness values, it will be very difficult for
sampled to participate in a tournament at all while other the population to move towards a better one since selection
individuals might not be selected for the intermediate probabilities for fit and unfit individuals are very similar.

ISBN: 978-988-19251-4-5 WCE 2011

ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online)
Proceedings of the World Congress on Engineering 2011 Vol II
WCE 2011, July 6 - 8, 2011, London, U.K.

Moreover, it is difficult to use this selection scheme on For linear rank-based selection, the biasness could be

2.0  SP  1.0 and the expected sampling rate of the best

minimization problems whereby the fitness function for controlled through the selective pressure SP, such that
minimization must be converted to maximization function as
in the case of TSP. Although to some degree this solves the individual is SP, the expected sampling rate of the worst
selection problem, it introduces confusion into the problem. individual is 2-SP and the selective pressure of all other
The best chromosome in the TSP problem, for instance, will population members can be interpreted by linear
continually be assigned a fitness value that is the maximum interpolation of the selective pressure according to rank.
of all other fitness functions, and thus we are seeking the Consider n the number of individuals in the population, Pos
minimum tour but the fitness maximizes the fitness value. As the position of an individual in the population (least fit
a consequence several other selection techniques with a individual has Pos=1, the fittest individual Pos=n) and SP
the selective pressure. Instead of using the fitness value of an
probability not proportional to the individual‟s fitness values
individual, the rank of individuals is used. The rank for an
have been developed to encounter proportional selection
individual may be scaled linearly using the following
problem. In general there are two types of such non-
formula,
proportional selection operators: tournament based selection
 ( Pos  1) 
Rank( Pos)  2  SP   2.( SP  1).
techniques which already been described in the previous

(n  1) 
(2)

section, and the rank-based selections that assign the
probability value depending on the order of the individuals
according to their fitness values, which will be discussed in
TABLE 1 contains the fitness values of the individuals for
the following section. various values of the selective pressure assuming a
population of 11 individuals and a minimization problem.
TABLE 1. EXAMPLE OF SCALED RANK WITH DIFFERENT SP
VALUES

Individual Scaled rank Scaled rank

Rank
fitness value with SP=2.0 with SP=1.1
1 1 2.0 1.1
3 2 1.8 1.08
4 3 1.6 1.06
7 4 1.4 1.04
Fig. 4. Selection strategy with roulette wheel mechanism 8 5 1.2 1.02
9 6 1.0 1.00
10 7 0.8 0.98
15 8 0.6 0.96
20 9 0.4 0.94
30 10 0.2 0.92
95 11 0 0.9

Rank-based selection schemes can avoid premature

convergence and eliminate the need to scale fitness values,
but can be computationally expensive because of the need to
sort populations. Once selection probabilities have been
Fig. 5. Procedure for proportional roulette wheel assigned, sampling method using roulette wheel is required
to populate the mating pool. Rank-based selection scheme
C. Rank-based Roulette Wheel Selection helps prevent premature convergence due to “super”
individuals, since the best individual is always assigned the
Rank-based roulette wheel selection is the selection
same selection probability, regardless of its objective value.
strategy where the probability of a chromosome being
However this method can lead to slower convergence,
selected is based on its fitness rank relative to the entire
because the best chromosomes do not differ so much from
population. Rank-based selection schemes first sort
individuals in the population according to their fitness and other ones. The different between roulette wheel selection
then computes selection probabilities according to their with proportionate fitness and rank-based fitness is depicted
ranks rather than fitness values. Hence rank-based selection in Fig. 6a and Fig. 6b respectively while the GA procedure
can maintain a constant pressure in the evolutionary search for rank-based selection implementation is given in Fig. 7.
where it introduces a uniform scaling across the population
and is not influenced by super-individuals or the spreading
of fitness values at all as in proportional selection. Rank-
based selection uses a function to map the indices of
individuals in the sorted list to their selection probabilities.
Although this mapping function can be linear (linear
ranking) or non-linear (non-linear ranking), the idea of rank-
based selection remains unchanged. The performance of the
selection scheme depends greatly on this mapping function.
Fig. 6a. Proportionate fitness Fig. 6b. rank-based fitness

ISBN: 978-988-19251-4-5 WCE 2011

ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online)
Proceedings of the World Congress on Engineering 2011 Vol II
WCE 2011, July 6 - 8, 2011, London, U.K.

the quality of solution reduces as the size of instance

increase. The percentage of deviation from the known
optimal solution concerning problems in the TSPLIB can be
seen as a chart in Fig. 8. It shows that GA with rank-based
roulette wheel selection is superior than that of tournament
and proportional roulette wheel where the results of rank-
based roulette wheel does not gives any deviation (0%) from
the optimal solution for the three instances: burma14, bay29,
and dantzig42, and less than 1% deviation for eil51.
Fig. 7. Procedure for rank-based roulette wheel Tournament selection apparently gives better results than
proportional roulette wheel for all size of problems tested.
V. COMPUTATIONAL EXPERIMENTS AND RESULTS
TABLE 2. RESULTS OF THE BEST SOLUTION FOR ALL
INSTANCES
A. Experimental Set-up
This section will focus on computational experiment that Instances Known Tournament Proportional Rank-
use three GA selection schemes discussed in this paper to optimal based
obtain optimal solution for TSP. The algorithms are coded in solution
MATLAB version 2009b. The performance of GA is tested 10-city - 2.8567 2.8567 2.8567
20-city - 4.0772 4.0772 4.0772
at eight TSP instances: randomly generated of 10-city, 20- 30-city - 4.8352 4.9075 4.6683
city, 30-city and 40-city, and the known optimal solution 40-city - 6.1992 6.5127 5.7311
TSP instances taking from TSPLIB [15]; burma14, bay29, burma14 30.8785 30.8785 30.8785 30.8785
bay29 9074 9077 9079 9074
dantzig42 and eil51. For all experiments, the GA procedure dantzig42 679 725 760 679
employed a combination of linear order crossover and eil51 425 470 513 430
inversion mutation for producing offspring at every
generation. The tournament size used in the tournament
selection is set to 2, while the selective pressure used in the
rank-based selection is set to 1.1 for all runs. The objective
of the experiment is to investigate the performance of GA
with different selection strategies in terms of number of
generations and iteration time to come out with the optimal
solution for TSP.
One of the main difficulties in building a practical GA is
in choosing suitable values for parameters such as
population size, probability of crossover (Pc), and
probability of mutation (Pm). In this experiment, we follow Fig. 8. Deviation from known optimal solution
De Jong‟s guideline which is to start with a relatively high
Pc (≥ 0.6), relatively low Pm (0.001-0.1), and a moderately The performance graphs in Fig. 9 show the minimum
sized population [16]. The selections of parameter values are distance found by the algorithm in each generation. As we
very depend on the problem to be solved. This experiment can see from the graph, the distance reduced towards
will use a constant population size which is approximately optimal solution as the generation increased and finally
10 times larger than number of instance. Noted that the converged at a certain generation. For instance in dantzig42,
larger the population size, the longer computation time it it shows that the algorithm with tournament and proportional
takes. In this experiment, the GA parameters were obtained roulette wheel selection converged at generation 82 and 135
from the screening experiment and trial run. For each respectively, where there is no more improvement made
experiment, the algorithms were run ten times and the lowest after this generation. On the other hand rank-based selection
travelling distance is taken as a final result. For all is able to reach optimal solution without premature
experiments in this study, termination is performed when convergence. Although with slower convergence (i.e. high
number of generation reached the maximum number of number of generations), rank-based algorithm performs
generation. The maximum number of generation is set highly competitive in terms of solution quality, achieving
earlier in the program code. minimum travelling distance.
The graphs in Fig. 10 compare the iteration time between
B. Experimental Results three different strategies. Obviously, rank-based roulette
TABLE 2 shows the best results obtained for eight TSP wheel consumes the highest iteration time, hence high
instances run with different selection strategy. It is clearly computation time due to large number of generations
shows that GA with rank-based roulette wheel selection involved to complete the evolution process. The iteration
always gives the highest solution quality (i.e. minimum time for tournament is slightly better than proportional
travelling distance) for all TSP instances tested. This is then roulette wheel in producing comparable results of minimum
followed by tournament and proportional roulette wheel. travelling distance. This indicates that in general tournament
Tournament and proportional roulette wheel is able to is superior to proportional roulette wheel in achieving good
achieve optimal solution for small size instances; however quality solution with less computation time.

ISBN: 978-988-19251-4-5 WCE 2011

ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online)
Proceedings of the World Congress on Engineering 2011 Vol II
WCE 2011, July 6 - 8, 2011, London, U.K.

3.5
3.4
10-city
9
8
20-city lowest traveling distance in the tour. Therefore it can be
3.3 7
3.2
6 conclude that tournament selection is more appropriate for
3.1
Distance

Distance
5
3
2.9
ranking
proportional
4
tournament
proportional RW
small size problem while rank-based roulette wheel can be
3
2.8
2.7
tournament
2
ranking used to solve larger size problem. There is always a trade-off
2.6 1
2.5 0 between computation time and the solution quality. If
0 10 20 30 40 0 50 100 150
Generations Generations solution quality is the main concern and computation time is
14

12
30-city
18
16
40-city still negotiable, then rank-based selection strategy is the best
10
14
12
choice.

Distance
Distance

8 10

6
ranking
proportional
8
tournament
proportional
Future work could be to evaluate the interaction between
6
4

2
tournament
4
ranking
selection pressure and selection strategies. For example,
2
0
0 50 100 150 200 250 300
0
0 200 400 600 800
instead of using binary tournament, we could vary the
Generations Generations
tournament size to increase the selection pressure. Future
50 2.5

45
burma14 bay29 work could also extend the model to include precedence
2

40
1.5
constraint TSP. Precedence constraint can increase problem
Distance
Distance

35 tournament
proportional 1
tournament
proportional
complexity and may results in a different convergence
30

25
ranking
0.5
ranking
behavior, which could lead to a conclusion on whether a
20
0 20 40 60
0
0 200 400 600 800
superior selection method exists without regard to problem
Generations Generations
size and complexity.
2.5 1.6
dantzig42 eil51
1.4
2

1.5
1.2
1
REFERENCES
Distance

Distance

tournament 0.8 tournament

1 proportional 0.6 proportional
[1] D. Beasley, D. Bull, and R. Martin, An Overview of genetic
0.5
ranking 0.4 ranking algorithms: Part 1, Fundamentals, University Computing, vol. 2, pp.
0.2
58-69, 1993
0 0
0 200 400 600 800 0 250 500 750 1000 [2] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys,
Generations Generations
The Traveling Salesman Problem, John Wiley & Sons Ltd. , 1985
[3] O. A. Jadaan, L. Rajamani, C. R. Rao, “Improved Selection Operator
Fig. 9. Performance graph for all instances showing number of generations for GA,” Journal of Theoretical and Applied Information
to converge Technology, 2005
[4] J. Zhong, X. Hu, M. Gu, J. Zhang, “Comparison of Performance
(sec) (sec)
between Different Selection Strategies on Simple Genetic
250 350 Algorithms,” Proceeding of the International Conference on
200
300
Computational Intelligence for Modelling, Control and automation,
250
150 tournament 200 tournament
and International Conference of Intelligent Agents, Web
100
proportional 150 proportional Technologies and Internet Commerce, 2005
B. A. Julstrom, It‟s All the Same to Me: Revisiting Rank-Based
ranking ranking

50
100 [5]
50

0 0
Probabilities and Tournaments, Department of Computer Science, St.
10-city 20-city 30-city 40-city burma14 bay29 dantzig42 eil51 Cloud State University, 1999
[6] S. Mashohor, J. R. Evans, T. Arslan, Elitist Selection Schemes for
Fig. 10. Iteration time comparisons Genetic Algorithm based Printed Circuit Board Inspection System,
Department of Electronics and Electrical Engineering, University of
Edinburgh, 974 – 978, 2005
[7] K. S. Goh, A. Lim, B. Rodrigues, Sexual Selection for Genetic
VI. CONCLUSIONS Algorithms, Artifial Intelligence Review 19: 123 – 152, Kluwer
In this paper we have described three types of selection Academic Publishers, 2003
[8] D.E. Goldberg and K. Deb, A comparative analysis of selection
strategy in the GA procedure to solve TSP and compare schemes used in genetic algorithms, in: G.J.E. Rawlins (Ed.),
their performance in terms of solution quality and number of Foundations of Genetic Algorithms, Morgan Kaufmann, Los Altos,
generations to come out with the best solution. From the 1991, pp.69–93.
[9] J. H. Holland, Adaptation in natural and artificial systems, The
results of experiment on eight TSP instances, it can be University of Michigan press, 1975
conclude that the quality of solution improved with rank- [10] P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza, S. Dizdarevic,
based roulette wheel selection scheme. We have found Genetic algorithms for the Travelling Salesman Problem: A Review
optimal solutions for every TSP instance we have tried of Representations and Operators, Artificial Intelligence Review 13:
129 – 170, 1999
except for eil51, to within 0.9% deviation of a known [11] Handbook of Evolutionary Computation, IOP Publishing Ltd. and
optimal solution. GA cannot be expected reliably to find Oxford University Press, 1997
optimum solutions, but it can yield excellent near optimal [12] T. Blickle, L. Thiele, A Comparison of Selection Schemes used in
Genetic Algorithms. TIK-Report, Zurich, 1995
solutions, which are adequate for most practical problems [13] J. E. Baker, “Adaptive selection methods for genetic algorithm,”
where input data are only approximate. The results also Proceeding of an International Conference on Genetic Algorithms
revealed that the GA based tournament selection is more and Their Applications, 100 – 111, 1985
[14] D. Whitley, “The genitor algorithm and selection pressure: Why rank-
efficient in obtaining minimum total distance with less based allocation of reproductive trials is the best,” In Proceeding of
number of generation and fastest iteration time compared to the 3rd International Conference on Genetic Algorithms, 1989
the other two strategies. However, this is only applicable for [15] G. Reinelt, TSPLIB – A Travelling Salesman Problem Library. ORSA
Journal on Computing, Vol.3, No.4, 376 – 384, 1991
small problem size (i.e. 10-city, 20-city and burma14). As
[16] K. De Jong, W. M. Spears, “Using Genetic Algorithms to Solve NP
the size of problem increase, tournament selection as well as Complete Problems,” Proceedings of the Third International
proportional roulette wheel becomes susceptible to Conference on Genetic Algorithm, Morgan Kaufman, Los Altos, CA,
premature convergence. Rank-based selection on the other 124 – 132, 1989
hand continues to explore the search space and reaching the

ISBN: 978-988-19251-4-5 WCE 2011

ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online)