=Paper=
{{Paper
|id=Vol-1746/paper-27
|storemode=property
|title=Genetic Algorithms in Traveling Salesman Problem
|pdfUrl=https://ceur-ws.org/Vol-1746/paper-27.pdf
|volume=Vol-1746
|authors=Nevila Xoxa,Valbona Dhjaku,Igli Tafa
|dblpUrl=https://dblp.org/rec/conf/rtacsit/XoxaDT16
}}
==Genetic Algorithms in Traveling Salesman Problem==
https://ceur-ws.org/Vol-1746/paper-27.pdf
Genetic Algorithms in Traveling Salesman Problem
Nevila XOXA Valbona DHJAKU Igli TAFA
Albanian Academy of Science Credins Bank Polytechnic University of Tirana
Tirana Tirana Information Technology Faculty
nevila.xoxa@akad.gov.al vdhjaku@gmail.com Computer Engineering Department
itafaj@gmail.com
A suitable encoding is found by thinking that every
Abstract solution to our problem has a unique code, in the shape of
a vector or a matrix. After that a starting population is
Genetic algorithms are a revolutionary created in a completely random way. For each individual
technique which used operators like mutation, of this population a natural selection level is calculated
crossover and selection in resolving optimization which is used as coefficient to compare it with the other
problems. They have been used with success in individuals and finding out which is closer to the ideal
multiple problems. The TSP (Traveling Salesman solution. Through these coefficients are used to select the
Problem) is one of these problems. It consists in individuals that will be crossed over with each other.
finding the route with minimal length, passing by The crossover is the process where 2 individuals are
every node of a weighted graph only once. This combined to create new ones, which become part of the
problem is found in many real world applications new generation. After that the mutation happens. Some
therefore a good solution would be helpful. Many randomly selected individuals are mutated, which means
methods have been used in finding the best that a character of the vector is changed leading to the
solution for the TSP but we are going to use creation of new individuals (and therefore a new
genetic algorithms as such solution. In order to generation). This process goes on until a stopping
prove it we will simulate it in a test environment condition is achieved. At this point the individual who is
to watch from close the way it works and the closer to the final solution is decoded and the process
efficiency of this algorithm in resolving our ends.
problem.
2. Standard Genetic Algorithm
1 Presentation
We are given a problem with a well defined solution.
Genetic algorithms are an optimization technique based The preliminary process includes finding a way of
on natural evolution, which includes the concepts of presenting such a predicted by the encoding. In this
natural selection into a searching algorithm and offers an situation a genetic algorithm would work like below:
acceptable solution without the need of calculating all the 1. We start by generating a population of random
options. Genetic algorithms are based on the concept of solutions with n candidates of length 1 bit. (the genes)
natural selection [Fal98]. In nature, the most adopted 2. We calculate function f(x) of the natural selection
individuals have more survival chances and therefore even potential of each candidate (chromosome) of the
their children are more adopted and healthier than their population.
parents. 3. Repeat the steps until n descendant are created:
The same idea will be applied in problems supposing as a. Choose a pair of chromosomes from this
a start a group of solutions and later combining all most population, with a probability of selection as in ascending
suitable solutions to create a new generation of solutions order. Each chromosome can be selected more then once
getting closer and closer to the required one. Genetic as parent of the selected couple.
algorithm consists of the followings steps: b. With probability pc (crossover probability)
– Encoding couples are crossed with each other in the random selected
– Evaluation point in order to produce 2 descendants. If we don’t have
– Selection a successful crossover we can take a copy of the 2 parent
– Crossover and consider them as descendants.
– Mutation c. Mutate each descendant in the selected
– Decoding gene with probability pm (mutation probability)
and put the new descendants in the new
population. If n is odd one of the descendants – Encoding with real numbers
will be randomly removed. Used in problems that requires optimization of
4. Replace the old population with the new one. functions and classified as the most convenient
5. Restart from point2. [Wro96].
Each iteration of this process is called a
generation.
– Character Encoding [Rei94]. Best solution for
combinatory problems.
– Encoding with structure of data [Mic94]. Used in
real world problems
Let’s take into consideration the problem above. Our
possible solutions are clearly numbers, therefore we use
Figure 1: The evolution of a generic algorithm binary encoding. Therefore to represent numbers from
0 to 15 we need 4 bits which in genetic algorithms will
be called genes and the vectors formed by then will be
called chromosomes.
3. Basic Concepts
For example: 1 0001 . . . . . 15 1111
Genetic algorithms can vary from straightforward to
very difficult to understand. Before we proceed let us give Now we in a random way we generate a population
a simple example of how they work. We need to maximize from these chromosomes.
a function f = -2x2 + 4x - 5 from a vector of whole
numbers {0, 1 …15}. From straight calculation we can 3.2 Selection
find that max (f) is reached for x=1.
The main principle on which genetic algorithms is
essentially Darwinian natural selection. Selection provides
3.1 Encoding a driving force in genetic algorithms. Very strongly,
The encoding process is usually the hardest one in genetic research will be completed ahead of time, with
resolving a problem with genetic algorithms [Mit91]. little power, progress of evolution will be slower than
When applied in a specific problem it is usually hard to usual. Usually, a pressure lower selection suggested early
find a correct presentation of the solution. Taking into genetic research in favor of an exploration of wider space
consideration that we have to encode many possible research, while a high pressure selection is recommended
solutions to create a population the easiest way to at the end of genetic research to narrow the space
represent it is through a vector of 0’s and 1’s. Anyway research, also achieving convergence solution. Selecting
based on the kind of characters used for presentation drives genetic research towards a promising area of
encoding is divided in 4 groups: research in space [Psg91]. During the past two decades,
– Binary Encoding more selection methods are proposed, examined,
Usually used in problems with small complicity or compared listed below:
when the solution is expected to be a number. – Roulette wheel selection
– (µ + λ)- selection
– Tournament selection
– Steady- state reproduction
– Ranking and scaling By exchanging genes we would have:
– Sharing v1’ = 01|00 = 4
Roulette wheel selection, proposed by Holland is the v2’ = 11|11= 15
best type of selection known so far. The basic idea of this
method is to determine the probability of selection or Now we have 2 new chromosomes which will be
survival probability for each chromosome in proportion to moved to create the new population.
the value of adaptability. So a roulette wheel model can be
made to the appearance of these probabilities. Then the
selection process is done by turning the wheel as often as
population size, each time when a chromosome selected
only for the young population. Wheels present stochastic
method as a procedure sample. Baker proposed a
universal stochastic method which requires only one
rotation. Wheel is modeled like a roulette wheel, with an
equal number of areas with the population. The basic
strategy which is built on this approach is to maintain the
expected number of copies of chromosomes in the new
generation.
In contrast to proportional selection, selection (μ + λ)
and (μ, λ) of the proposed Back deterministic procedures
which are selecting the best chromosomes from parents
and offspring. We note that the two methods of selection
prevent duplicated chromosomes from the population, Figure 2: Crossover process with one point
many researchers prefer to use this method to work with
combinatorial optimization problems [Gol89]. Trunkan Not every junction chromosome used. We reiterated
selection and blocking it are also regarding the procedures that the function of assessment gives or any chromosomal
stochastic which classify individuals based on eligibility 'points' that are used to determine the probability that any
and select the best parents. Elite selection of commonly chromosome crosses, with the help of selection mentioned
used as supplementary selections chromosomes above, chromosomes are selected to be crossed by chance
proportional to preserve the best of the new generation, and the greatest opportunity is given to those with 'points'
though not selected during the process of selection higher. We use distribution collection created in the
proportional. evaluation process to select chromosomes by various
Distribution techniques, presented by Richardson for a selection methods. Generate random numbers between 0
Golberg and multimodal optimized functions, are used to and 1 and choose which chromosome corresponds to our
maintain the diversity of the population. A distribution distribution. We repeat to find the second and then the
function is a way to determine the degradation of the intersection of two young individuals become part of the
eligibility of an individual from a neighboring individual new generation. The process continues until a new
in a certain distance. Degradation, the probability of generation is filled. Not necessarily better than the first
reproducing individuals within a community falls while settler.
other individuals are encouraged to japing successor. There are many types’ intersection routines, some of
In our problem, simplicity and efficiency that will be which would later face. Sometimes we need us move the
used wheeling roulette, in which a group of individuals intersection routines to ensure that the chromosomes do
will choose randomly, but the appropriateness of assessing not conclude logically incorrect.
proportionality in the section above.
3.4 Mutation
3.3 Crossover
Mutation is the technique which enables us to process
Crossover may be eligible a straightforward procedure. not stalled local optimization. As a result of the process to
In our example, which used the simplest case crossover, chance, occasionally we have chromosomes from optimal
we randomly select two chromosomes to cross, I randomly local close but not that global. For this reason
select an intersection point, and then we exchange all the chromosomes from optimal local close to the junction will
genes that are after that point. In our case: be solved because they will have greater adaptability, but
v1 = 0111 then the chances will be smaller to achieve global from
v2 = 1100 optimal. So completely random mutation as a way remains
We can suppose that the crossover point is randomly the only option for finding a possible solution. Mutation is
selected after the 2nd gene. applied after the intersection in one of the new generation
v1 = 01|11 of chromosomes. Then randomly selected a point (gene)
on chromosome selected and change it. For
v2 = 11|00 demonstration, in our example we have:
v1 = 0111 cities done this method inefficient, and unable to find the
If we suppose that randomly has been selected as cost of each link in polynomial time.
mutation point the 3rd gene then v1 would become:
v1’ = 0101
Another inversion is a form of mutation. It is usually
used in special cases which will see later. Now we will
demonstrate inversion in the example we have taken.
Inversion consists of random selection of two points
Inverted in vector and then every bit For example:
v2 = 1100
We select 2 points:
v2 = 1|10|0 Figure 3: Example of a TSP problem
Invert the 2 genes:
v2’ = 1|01|0
If we had a bigger chromosome then we would have: 4.2 Why TSP? Applications
v3= 101101101001 The problem of itinerant vendors there are plenty of
v3= 101|101101|001 different applications in the real world, which makes it a
v3’= 101|010010|001 very common problem to be solved. Here we will explain
some of these applications. For example, some car router
3.5 Decoding problems can be addressed and resolved as TSP. Here the
Decoding is the last step to be followed in an algorithm problem lies in finding out who the client will be served
genetic, it's just the reverse process of coding, where the and by whom the car, and the minimum number of
final data or response algorithm to a problem, which come machines necessary to serve each customer. There are
in the form of selected coding return a response accessible many variations and problems involving minimum time to
to the user or process. In this case, it made the transition serve each customer. We can deal with such problems in
from binary to decimal conversion by the basic rules of the form of a TSP-art.
the way. Hardware problem connecting with "wireless" can be
modeled as a TSP. We have a set of modules, each with a
certain number of pin. We need to connect pins with
4. Traveling Salesman Problem several groups of conductors to each other, but each pin
apogee is not to have more than two connections and the
4.1 Entry length of the conductor is minimized.
Another found an application by Plate, Lowe and
The problem of vendors traveling (Traveling Salesman Chandrasekaran control in aircraft gas turbines. Consisting
Problem, TSP) addresses the problem of finding a way to of several wind sensor located in the perimeter and
visit a number of cities, with the proviso that each city is located on each level of the turbine to ensure a uniform
visited only once, the journey ends in the city of the left flow of gas. The positioning of wind indicators in order to
and this length be much smaller. The first example of TSP minimize the fuel consumption can be modeled as a
was given by Euler in 1759, whose problem was to symmetric TSP problem.
displace the horse in any chess position only once. Fame Turn the work of a single machine with the time given
took in a book written by a German seller BF Voigt in to each work and preparation for any work time is also a
1832 how to become a successful traveling salesman. He TSP. We can minimize the work of a total aligning things
cited TSP, not with the same name, but suggested that an in the right order.
important aspect was that every city to be visited only A robot must perform a set of operations to meet a
once. process. In this application, compared with sequences of a
Standard problem or called as itinerant vendor’s machine works, we have advantages and limitations which
symmetrical problem can be expressed mathematically as can be viewed as an asymmetric TSP [Jtr94].
follows: Problems related to the acceleration of the work of
Given a weighted graph G = (V, E) where weights CIJ drilling electronic circuits, which consists Opening of
crossing between nodes i and j is not a negative value, holes with different diameter for various electronic
find any connection node to have a minimum total cost. elements, changing the head of drill spends more time
Currently the only way to guarantee the optimal with it to a factory cost counties. Control of the work of
solution to this problem of any magnitude is calculated the drilling head can be treated as TSP.
every opportunity connection between them and finding it As these and many other applications give a particular
with lesser cost [Hgl92]. Any point of contact for a importance to this problem, as in aeronautics, robotics,
number of towns in particular need calculation of n! industry, transport, telecommunications etc.
Possibilities of connections, with a growing number of
5. Genetic Algorithms As Solution For TSP weight from node to node. Given that our main task is
based on achieving the problem of finding a shortest tour,
5.1 Adaptation the intention of solving this problem will tend to minimize
One of the methods for optimization is also tsp GA this assessment. Maintaining these distances or weights
(Genetic Algorithms). In the first chapter presented in between nodes can be calculated as distance Euclidian or
general terms how this method proceeds to the provision wasted searching algorithm can be stored in matrix form
of an optimal solution to a problem. In this part we will by eliminating their need occasional calculation.
focus on how helps an algorithm based on natural
evolution for solving a problem so large it is TSP-ja. Step 5.1.3 Adapted Selection
will adapt to any functional link genetic algorithms TSP-
in. As we mentioned, the selection is one of the most
important operators in genetic algorithms [Llk86]. Given
that the goal is minimizing the tour, we ask individuals,
5.1.1 Adapted Encoding
which in our case represent, with probability greater to be
We saw above basic ways of encoding a basic problem selected to be those with greater conformity, then the
using vectors to 0 and 1, who presented numbers in binary distance of the tour, the smallest defined by the evaluation
form. The question arises how to introduce so easily operator. All selection methods can be used, but as noted
malleable and efficient problem of itinerant vendors? In in the chapter of our inquiry the best selection of selector
the same way we can use vectors encoding numbers as wheel solves roulette. Assessment determines those
12345, letters ABCDE vectors, also any other form of individuals were part of the wheel which then 'rotate'
strings of symbols, enough to make sense of the problem.
Below we present the main ways of presenting the TSP's
so malleable by genetic algorithms [Che00].
Matrix
Because in itself a problem as TSP-ja is itself a graph.
We can create a matrix of connections, which consists of
one and zero, where 1 defines the connection node of the
j-in and 0 division. We can then treat this matrix in
unmodified form or working with extending linearly
according to the ranks.
Figure 4: Roulette wheel selection
5.1.4 Adapted Crossover
We will start with the first partial junction (partially
matched crossover PMX). Assume that we are using
vector encoding type numbers, also reuse the intersection
with two points mentioned in the first chapter.
Vectorial
Form the first to introduce the problem of itinerant
vectors symbols can be cyclic, in the form of vectors:
V = b1 b2 ... bn...
Where mug to the value implied by the position vector
in that position, which means the tour goes from city to
city bi. For example, the vector v1 = 3421 is meant as a
tour that starts from city 1 to city 3, then from 3 to City 2
city, then the city 2 to 4 and from city to city 4 City 1. It
should be noted that in presentation this way not every
possible combination of numbers in the vector sense, such
as those that create closed loops without going into any
city such as v2 = 3412.
Figure 5: Partial Crossover
5.1.2 Adapted Evaluation
The evaluation process of individuals to create, which If we would have 2 vectors:
in this case are the links of successive tour presented,
there will be nothing but the sum of each distance, cost or
V1 = 1234 | 567 | 8
V2 = 8521 | 364 | 7
Crossover would be like: 6. Simulations with Different Algorithms
Best
Nr of Optimal Average result
V1’ = 1234 | 364 | 8 approximate
nodes Result from GA
result
V2’ = 8521 | 567 | 7
Cyclic crossover CX works in a completely different Bay29 29 9074 9074 0.00 % 9075 0.01 %
way. First, this type of intersection can be used only with
the presentation in the order shown, namely that where the Eli51 51 426 434 1.87 % 441 3.52 %
numbers are placed in order of visits. Berlin
In this type of intersection point we do not choose at 52 7542 7544 0.02 % 7774 3.07 %
52
all. First choose one gene from their parents:
KroA
100 21282 21600 1.49 % 22445 5.46 %
V1 = 12345678 100
V2 = 85213647 KroA
200 29368 31864 8.49 % 32399 10.32 %
V2’ = 82315647 200
Conclusions
Genetic algorithms, their development, are playing a
very important role in resolving various problem-based
approach and anticipation. They have led an evolutionary
step forward calculation, and as term comprehensive
computerization. Genetic algorithms, through its junction
operators, mutation and selection enhanced algorithm so
create a more flexible and suitable for any application.
The problem of itinerant vendors, a conceptual basis of
a problem that arises in many real-life applications. Center
Figure 6: Cyclic Crossover of attention of many mathematicians studies because of its
importance, has expanded so much in terms of different
types of treatment, as well as the techniques and methods
5.1.4 Adapted Mutation needed to solve it [Aff09].
So that mutations committed to provide seed even more In our subject matter treated as the use of genetic
tailored, instead of leaving the process up to chance, as algorithms to find an approximation to the problem of
noted in chapter 1, the problem of vendors strolling us itinerant vendors and based on simulations performed,
come to the aid of algorithms servo controller for selecting genetic algorithms constitute a relatively good proxy tool
the 'gene' that will undergo change, presented in section to the problem of itinerant vendors. He responds ideally to
2.4.2 of regulators the tour. smaller nodes number 30 also gives a satisfactory
How early will revisit the 2-opt operators. Randomly approximation and faster even more problems with joints.
select two connections (a, b) and (b, c) from our tour and As we see in the summary table relative dependence
check if we can find another way to link these four joints calculated approximation does not exist only in relation to
in order to achieve a lower cost. To do this check if: the number of nodes, but also their position and weight. A
Cab + CCD> Cac + CDB look at the results given by the algorithm to Berlin 52
If the inequality completed Casualty replace Eli51 and draw the conclusion that genetic algorithm
connections (a, b) and (c, d) with the new links (a, c) and shows more efficiency in large instance. Problems where
(d, b). We note that it was assumed that a, b, c, d accuracy is the primary element, a greater number
displayed in the order of the tour though b to c are not generation need to get the best of him.
connected. We also have 3-opt operator who controls As in many other applications, genetic algorithms can
randomly selected 3 links instead of two. If we have be used effectively for obtaining a satisfactory
connections (a, b), (c, d) and (e, f), check whether: approximation to the problem of itinerant vendors
Cab + CCD + Cef > Cac + CBE + CDF [Hau04]. As a method which is based on more research in
If completed on like is replaced connections for these 6 the future, an even higher performance can be achieved by
nods. him.
References
[Fal98] Emanuel Falkenauer. Genetic Algorithms and [Llk86] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan,
Grouping Problems. John Wiley and Sons, 1998. and D.B. Shmoys. The Traveling Salesman. John
[Gol89] David E. Goldberg. Genetic Algorithms in Wiley and Sons, 1986.
Search, Optimization and Machine [Mic94] Zbigniew Michalewicz. Genetic Algorithms +
Learning.Addison-Wesley, 1989. Data Structures = Evolution Programs. Springer-
[Hgl92] Abdollah Homaifar, Shanguchuan Guan, and Verlag, 2nd edition, 1994.
Gunar E. Liepins. Schema analysis of the [Rei94] Gerard Reinelt. The Traveling Salesman:
traveling salesman problem using genetic Computational Solutions for TSP Applications.
algorithms. Complex Systems, 1992. Springer- Verlag, 1994.
[Psg91] Prasanna Jog, Jung Y. Suh, and Dirk Van Gucht. [Wro96] Jakub Wroblewski. Theoretical foundations of
Parallel genetic algorithms applied to the order-based genetic algorithms. Fundamenta
traveling salesman problem. SIAM Journal of Informaticae, 1996.
Optimization, 1991. [Che00] Genetic.Algorithms.and.EngineeringOptimization
[Jtr94] Michael Junger, Stefan Thienel, and Gerard M.Gen R.Cheng (Wiley_2000)
Reinelt. Provably good solutions for the traveling [Mit91] An.Introduction.to.Genetic.Algorithms 5ed
salesman problem. Mathematical Methods of M.Mitchell, 1991
Operations Research, 1994.
[Aff09] Genetic.Algorithms.and.Genetic.Programming ,
M.Affenzeller, 2009
[Hau04] Practical.Genetic.Algorithms 2ed, R.L.Haupt dhe
S.E.Haupt (Wiley_2004)