Genetic Algorithm with Virus Infection
for Finding Approximate Solution
Takuya Inoue, Yoko Uwate and Yoshifumi Nishio
Tokushima University
2-1 Minami-Josanjima, Tokushima 770-8506, JAPAN
Email: {t-ionue, uwate, nishio}@ee.tokushima-u.ac.jp

Abstract— Genetic Algorithm (GA) is modeling behavior ofevolution in organic and known as one of method to solve Traveling Salesman Problem (TSP). However, GA obtains solution
by overlaying generations because of being based on evolution
in organic. Thus, it takes a long time to find approximatesolution. While, Virus Theory of Evolution (VTE) can evolve byvirus infection. VTE characteristic has sharing of information
among same generation. If new algorithm is using both thesecharacteristics of GA and VTE, convergence speed would befaster than GA. Thus, this study proposes Genetic Algorithmwith Virus Infection (GAVI). GAVI algorithm is Virus Theoryof Evolution (VTE) to be based on Genetic Algorithm (GA). We
apply GAVI to TSP and confirm that GAVI obtains more effective
result than GA.

that the proposed algorithm achieves better performance thanthe conventional GA.
TABLE IT HE NUMBER OF CITIES AND THE TOTAL ROUTE NUMBER
number of cities
348163264
128

total route number13
2.52 ∗ 103
6.54 ∗ 1011
8.22 ∗ 1033
9.91 ∗ 1086
1.51 ∗ 10213

I. I NTRODUCTION
Traveling Salesman Problem (TSP) [1] is known as oneof the combinatorial optimization problems. When Salesman
tours all cities at once, TSP is the problem of finding minimum
total between each city distance in route. Then n is thenumber of cities in TSP, total route number increase at rate
proportional to many of the factorial of n. For example, when
the number of n increases, the total route number explode in
Table I. Therefore, exploring total route number needs amountof time in finding approximate solution. However we would
like to obtain the approximate solution in TSP quickly. It isnecessary to solve the TSP in other ways except exploring
total routes. Finding approximate solution method of TSP isa variety of ways.
Genetic Algorithm (GA) [2], [3] is one of the popularmethod in variety of ways to solve the TSP and is studied bymany researchers all over the world. GA is modeling behaviorof evolution in organic. In genetic group, individuals with highevaluation tend to be many crossover. Thus, genetic groupobtains high evaluation in average for repeating crossover.
However, this method needs amount of time and convergence
speed is slow. We would like to obtain approximate solution
quickly. Thus, we need to propose the other method.
In this study, we propose Genetic Algorithm with Virus
Infection (GAVI). One of the characteristics of the virus infection [4]-[6] conveys gene information among same generation
at once. This characteristic seems to be useful for findingthe approximate solution quickly. Therefore, we consider thatthe virus infection will help to solve the TSP. We carry out
computer simulations for various parameter values and confirm

978-1-4673-5762-3/13/$31.00 ©2013 IEEE

II. V IRUS T HEORY OF E VOLUTION
Organic evolution is theory based on natural selection.
In natural world, high fitness individuals organism survive,
while low fitness individuals organism become extinct. Overthe years, only higher fitness individuals survive. We call itEvolution. Thus, evolution need to overlay generations.
On the other hand, there is theory that Virus Theory ofEvolution (VTE) [7]. This theory is based on the evolution
by Lateral Gene TransferiLGT) [8] in Virus infection. LGT isuptake of the gene that occur between other individuals andamong other species. Without evolution inherited from parent
cell to child cell, genes can evolve. Low fitness individuals
possibly evolve into high fitness individuals in just one generation by LGT in Virus infection. Thus, we assume using VTE
algorithm leads the approximate solution in less time and VTE
theory is efficient in TSP.
III. G ENETIC A LGORITHM WITH V IRUS I NFECTION
Selection, Crossover and Mutation are the main functionsof the GA. GAVI is a method of VTE algorithm in Virus
infection to be based on GA. Flow chart of GAVI is shown inFig. 1. New algorithm is Infection in Fig. 1. t is the numberof repeating times.
Initialization
Initialization is random route selection. Number of randomroute selection is U .

1604

Evaluation
Evaluation is defined by the following formula.
1(1)diwhere di is total distance of each route and fi is evaluation
value. If di is low, fi is high by this formula.
fi =START
t=0

Selection
Route is selected with a probability of pi . pi is defined by
the following formula.
fi
pi =  n

i=1 fi

Initialization(2)

Evaluation

where n is the number of cities. Selection is the methodof tends to be chosen high evaluation route. Low evaluationroute is chosen a few. Selection works that high fitness
individuals organism survive, while low fitness individualsorganism become extinct.

Selection

Fulfill crossover condition
This section evaluates crossover condition. If parents is
not fulfill crossover condition, crossover is not acted. Whencrossover condition is fulfill, crossover is acted.

Fulfill crossover condition

Crossover
Crossover is to be mated the two routes. In this study, weapply sub tour exchange crossover. This way makes a searchfor sub tour of the both Parent A and Parent B in common. If
it does not find sub tour in common, crossover algorithm is notacted. For example, between 1, 2, 5, 6 and 5, 1, 6, 2 are sub tourin Fig. 2. 1, 2, 5, 6 and 5, 1, 6, 2 are differ in line, however theseare same class. Sub tour in 1, 2, 5, 6 can express 1, 2, 5, 6 and6, 5, 2, 1, 5, 1, 6, 2 can express 5, 1, 6, 2 and 2, 6, 1, 5. Because
two expressing are same about total route distance in Fig. 3.
Thus, after crossover, four child exist.

YES
Crossovert=t+1

Mutation
Infection
O(t)=O(t-s)

Mutation
M utation is to change the route with a certain probabilityin Fig. 5 and less likely to fall into local minimum.
Infection
We define elements of each route as Virus, elements selectthe best route in the obtained solution and part of each routeis infected by this Virus at random. Number of element selects
is fixed probability. For example, 3, 5 is a virus and has
infected the route of 6, 1, 3, 5, 2, 4 in Fig. 4. Inf ection part
determines 1, 4 in the route. The route replace to 3, 5 1, 4. We
call it Inf ection. Inf ection is incorporating partial optimum
solution.
One route reset in random
If the obtained solution is same among number of s, one
route in all routes is initialization in random. O(t) is theobtained solution in number of t times, while O(t − s) is theobtained solution previous number of s. Thus, O(t) = O(t−s)
shows that the obtained solution is same among number of s.
We assume that this is efficient to escape local minimum.

1605

YES
One route resetin random

YESt<tmaxNOENDFig. 1.

Flow chart of GAVI.

NONOVirusParent A

3 53 7 1 2 5 6 8 4

Choose a place
to infect

Parent B

8 7 4 5 1 6 2 3

6 3 1 4 2 5Child A

Infection

3 7 5 1 6 2 8 4

6 1 3 5 2 4Child B

3 7 2 6 1 5 8 4Fig. 4.

Child CThe mechanism of Inf ection.

6 3 1 4 2 58 7 4 1 2 5 6 3Child DMutation

8 7 4 6 5 2 1 3Fig. 2.

6 2 1 4 3 5The mechanism of Inf ection.

Fig. 5.

The mechanism of Mutation.

IV. E XPERIMENTAL R ESULTS
In order to compare the performance of GAVI and GA, weapply GAVI and GA to find approximate solutions in TSP
such as att48 (48 cities). In this study, the number of t is
5000 times, the number of simulation is 10 times, U is 1000,
number of route in and error rate is defined by the following
formula.
Error rate[%] =Fig. 3.

The mechanism of Inf ection.

(obtain) − (optimum)× 100(optimum)(3)

where obtain shows obtained solution and optimum shows
optimum solution. When obtain value approaches optimumvalue, Error rate is low. For example, when obtain value
is equally optimum value, Error rate value is 0[%]. IfError rate value is 0[%], we would obtain optimum solution.
However, obtain is bad solution, error rate value is high. In
Table II, III, Ave is the average, Max is the maximum valueand Min is the minimum value in the results of simulation 10times.
Table II shows result of GA and Table III shows result ofGAVI. In GAVI, s is fixed with 100 and M utation rate
is fixed with 0.02. GAVI can find a good solution by1606

Inf ection from result of both Table II and Table III. WhenInf ection rate is 0.01, result of GAVI is the best. We assume
that if Inf ection rate is high, escaping local minimum
is difficult and diversity solution is loss. Thus, result ofInf ection rate = 0.1 is the better than Inf ection rate =0.2.
Figure 6 shows the error curve of GA and Fig. 7 showsthe error curve of GAVI. The number of simulation is 1time, M utation rate is fixed with 0.02 about GA and GAVI,Inf ection rate is fixed with 0.10 about GAVI. In Figure 6and 7, Convergence speed of GAVI is faster than GA. Thus,
we assume that Inf ection algorithm is efficient at first.
TABLE II
T HE RESULT FOR GA IN ATT 48

Algorithm
typeGA

Mutation
rate
0.02
0.05
0.10
0.20

Error rate[%]MaxMinAve
6.486
0.597
2.878
5.610
2.439
3.430
4.621
1.280
2.096
3.936
0.958
2.324

Fig. 7.

result, the result of GAVI was better than GA. It was efficientthat not only GA but also Inf ection applied in TSP. GAVI
was valuable in convergence of the solution. We confirmedthat VTE is efficient in TSP.
In future work, we would like to study the mechanism ofInf ection in detail. In this study, all number of element inInf ection is depended on fixed probability. However changing fixed probability is to expected efficient. For example, large
number of element is chosen frequent at first, while small
number of element is chosen frequent latter. Convergence
speed is fast at first, obtain solution prevent local minimum
latter. Thus, we are expected to obtain a better solution inGAVI.

TABLE IIIT HE RESULT FOR GAVI IN ATT 48

Algorithm
type
GAVI

Infection
rate
0.05
0.10
0.20

Max
4.437
2.835
2.096

error curve of GAVI.

Error ate[%]MinAve
0.926
1.912
0.530
1.195
0.798
1.628

ACKNOWLEDGMENT
This work was partly supported by JSPS Grant-in-Aid forYoung Scientists 23700269.
R EFERENCES

Fig. 6.

[1] Little J, Murty K, Sweeney D, Karel C, “An algorithm for the traveling salesman problem,” Operations Research 11:972-89, 1963.
[2] Jean-Yves Potvin,“Genetic algorithms for the traveling salesman problem,” Annals of Operations Research 63, pp.339-370, 1996.
[3] Kitano H ed.,“Identeki Algorithm[Genetic Algorithm],” 1st ed. Sangyo
Tosyo Kabushiki Kaisya, 1993.
[4] Fang G, Hongwei L, Qiang Z, Gang C, “A Genetic Algorithm with a Mixed Region Search for the Asymmetric Traveling Salesman Problem,” Computers and Operations Research 30(5), 773-786,
2003.
[5] Naoshi N, Akinori K and Kunio K, “An Evolutionary Algorithm Based on the Virus Theory of Evolution,” Information Processing
Society of Japan Vol.40, No.5, 1999.
[6] Gao F, Liu H, Zhao Q, Cui G, “Virus-evolutionary particle swarm optimization algorithm,” vol 4222. Springer, Berlin, pp 156-165, 2006.
[7] Hideomi N, Takashi S and Takashi F, “Virus theory of evolution,” Bulletinof Yamanashi Medical University Vol.3, pp.14-18, 1986.
[8] Zhaxybayeva O, Doolittle W F, “Lateral gene transfer,” Curr. Biol. 21,
R242-246 2011.

error curve of GA.

V. C ONCLUSION
We proposed GAVI for TSP and compared the performanceof GAVI and GA to lead approximate solutions. From the1607