2013 International Workshop on Nonlinear Circuits,Communications and Signal Processing
NCSP'13, Isrand of Hawaii, Hawaii, USA. March 4-7, 2013

Consideration of Genetic Algorithm with Virus Infection
solving Traveling Salesman Problem
Takuya Inoue, Yudai Shirasaki, Yoko Uwate and Yoshifumi Nishio
Tokushima University
2-1 Minami-Josanjima, Tokushima 770-8506, JAPAN
Email: {t-ionue, shirasaki, uwate, nishio}@ee.tokushima-u.ac.jp

Abstract

Infection (GAVI). GAVI is using Virus Infection algorithm
based on GA. One of the characteristics of the Virus Infection [4]-[6] is infection other same generations at once. This
characteristic seems to be useful for finding the approximate
solution quickly. Therefore, we consider that the virus will
help to solve the TSP. We carry out computer simulations forvarious parameter values and confirm that the proposed algorithm achieves better performance than the conventional GA.

Genetic Algorithm (GA) is known as method to solve Traveling Salesman Problem (TSP). However, GA needs amountof time for finding approximate solution. Thus, this study
proposes Genetic Algorithm with Virus Infection (GAVI).
GAVI algorithm is using Virus Theory of Evolution (VTE)
to be based on Genetic Algorithm (GA). GA can evolve bynatural selection, while VTE can evolve by virus infection.
GA characteristic convey informations to next generation bycrossover. On the other hand, VTE characteristic has sharing 2. Virus Theory of Evolutionof information among same generation. GAVI is using boththese characteristics of GA and VTE. We apply GAVI to TSP
Organic evolution is theory based on natural selection.
and confirm that GAVI obtains more effective result than GA. In natural world, high fitness individuals organism survive,while low fitness individuals organism become extinct. Overthe years, only higher fitness individuals survive. We call it
1. Introduction
Evolution. Thus, evolution need to overlay generations.
On the other hand, there is theory that Virus Theory of EvoTraveling Salesman Problem (TSP) [1] is known as one of
the combinatorial optimization problems. When Salesman lution (VTE) [7]. This theory is based on the evolution bytours all cities at once, TSP is the problem of finding min- Lateral Gene Transfer（LGT) [8] in Virus infection. LGT isimum total between each city distance in route. Then n is uptake of the gene that occur between other individuals andthe number of cities in TSP, total route number increase at among other species. Without evolution inherited from parent
rate proportional to many of the factorial of n. Therefore, ex- cell to child cell, genes can evolve. Low fitness individuals
ploring total route number needs amount of time for finding possibly evolve into high fitness individuals in just one genapproximate solution, however we would like to obtain the eration by LGT in Virus infection. In other words, we assume
approximate solution in TSP quickly. It is necessary to solve that each individual become a better evaluation value quickly.
the TSP in other ways except exploring total routes. Finding Thus, we assume using VTE algorithm leads the approximate
solution in less time and VTE theory is efficient in TSP.
approximate solution method of TSP is a variety of ways.
Genetic Algorithm (GA) [2], [3] is one of the popularmethod in variety of ways to solve the TSP and is studied
by many researchers all over the world. GA is modeling be- 3. Genetic Algorithm with Virus Infection
havior of evolution in organic. Thus, GA is to explore thesolution for repeating crossover on the basis of organic evoSelection, Crossover and Mutation are the main functions
lution. Organic evolution is to survive individuals with high of the GA. GAVI is a method of VTE algorithm in Virus
evaluation in alternation of generations. Thus, GA can ob- infection to be based on GA. Flow chart of GAVI showstain the approximate solution by overlaying the generation. Fig. 1. tmax is number of repeating times. GAVI algorithm
However, evolution needs large number of alternation of gen- is indicated the following Step1-7. Step2-7 is repeated untilerations. Thus, GA needs amount of time and convergence the set number of Crossover times. After the set number ofspeed is slow.
Crossover times, GAVI output the best solution in all getting
In this study, we propose Genetic Algorithm with Virus solutions.

- 289 -step1 (Initialization)
Initialization is random route selection. Number of randomroute selection is U .

route. The route replace to 3, 5 1, 4. We call it Inf ection.
Inf ection is incorporating partial optimum solution.
step7 (One route reset in random)

step2 (Evaluation)
Evaluation is defined by the following formula.
fi =1
di(1)

where di is total distance of each route and fi is evaluation
value. If di is low, fi is high by this formula.

If a obtained solution is same among number of s, one routein all routes is initialization in random. O(t) is the obtained
solution in number of t times, while O(t−s) is obtain solution
previous number of s. Thus, O(t) = O(t − s) shows that theobtained solution is same among number of s. We assume
that this is efficient to escape local minimum.

STARTt=0
step3 (Selection)
Route is selected with a probability of pi . pi is defined by thefollowing formula.
fipi = ∑ni=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 individuals organism become extinct.

Selection

Fulfill crossover condition

step4 (Fulfill crossover condition)

NOThis section evaluates crossover condition. If parents is not
fulfill crossover condition, crossover is not action. whencrossover condition is fulfill, crossover is action.
step5 (Crossover)

YES
Crossover
t=t+1

Crossover is to be mated the two routes. In this study, weapply sub tour exchange crossover. This way makes a searchfor sub tour of Both Parent A and Parent B in common. If
it does not find sub tour in common, crossover is not action.
For example, between 1, 2, 5, 6 and 5, 1, 6, 2 are sub tour inFig. 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
and 6, 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 inFig. 3. Thus, after crossover, four child exist.

Infection

O(t)=O(t-s)

NOYES
One route resetin random

YESt<tmax
step6 (Infection)NO
We define elements of each route as Virus, elements select thebest route in obtain and part of each route is infected by thisVirus at random. Number of element selects is fixed probability.
For example, 3, 5 is a virus and has infected the route of6, 1, 3, 5, 2, 4 in Fig. 4. Inf ection part determines 1, 4 in the- 290 -END
Figure 1: Flow chart of GAVI.

Parent A

3 7 1 2 5 6 8 4Parent B

8 7 4 5 1 6 2 3Child A

4. Experimental Results
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, tmax = 5000 , thenumber of simulation is 10 times, U = 1000, and error rateis defined by the following formula.

3 7 5 1 6 2 8 4Error rate[%] =Child B

3 7 2 6 1 5 8 4Child C

8 7 4 1 2 5 6 3Child D8 7 4 6 5 2 1 3
Figure 2: The mechanism of Inf ection.

Figure 3: The mechanism of Inf ection.
Virus(obtain) − (optimum)× 100(optimum)(3)

where obtain is minimum solution and optimum is optimum solution. When obtain value approaches optimum
value, Error rate is low. For example, when obtain value isequally optimum value, Error rate is 0[%]. If Error rate
is 0[%], we would obtain optimum solution. However, ifobtain is bad solution, error rate is high. In Table 1-3, Ave
is the average, Max is the maximum value and Min is theminimum value.
Table 1 shows the result of GA and Tables 2-3 show theresult of GAVI. M utation is to change the route with a certain probability and less likely to fall into local minimum.
M utation rate shows performing the M utation probability. Table 2 uses value of s = 100, while Table 3 uses valueof s = 50. GAVI can find a good solution by Inf ection fromresult of Tables 1-3. The best result of GA in Ave uses valueof M utation rate = 0.05, while the best result of GAVI uses
value of Inf ection rate = 0.30 and s = 100.
Figure 5 shows error curves in each the best result of GAand GAVI. In Fig. 5, convergence speed of GAVI is fasterthan GA. During t = 0 − 5000, the result of GA and GAVI
are most of the same. However, during t = 1000 − 5000, theresult of GA is almost unchanged, while GAVI changes goodsolution by gradation. Thus, result of GAVI is better than GA.
Figure 6 shows relationship between inf ection rate anderror rate. In Fig. 6, when inf ection rate is high and low,
result is bad. In inf ection rate = 0.20, 0.30, 0.40, theresult of GAVI is relatively good solution in both s = 100
and s = 50.
All results of GAVI are not better than GA in Tables 1-3.
However, we assume that the result of GAVI is good by using
appropriate inf ection rate in Fig. 6.

3 5Choose a place
to infectTable 1: The result of GA for 48 cities

Algorithmtype

6 3 1 4 2 5InfectionGA

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

- 291 -

Mutation
rate
0.02
0.05
0.100.20

Error rate[%]MinAveMax
6.486 0.597 2.878
3.618 0.559 2.266
4.520 0.691 2.329
13.938 0.250 2.708

1000

Table 2: The result of GAVI for 48 cities (s = 100)GAVIInfection
rate
0.02
0.05
0.10
0.20
0.30
0.40
0.50

Error rate[%]MinAveMax
11.048 1.542 5.109
8.484 1.478 3.497
6.861 0.250 2.389
2.447 0.000 1.122
2.432 0.000 0.871
3.867 0.250 1.652
6.822 0.250 2.639

100error rate [%]Algorithm
type10GA
GAVI

10.101000

Table 3: The result of GAVI for at 48 cities (s = 50)

GAVI

Infection
rate
0.02
0.05
0.10
0.20
0.30
0.40
0.50

Error rate[%]MinAveMax
16.038 2.193 5.548
3.328 0.250 1.700
7.846 0.000 1.839
4.036 0.000 1.656
3.443 0.798 1.372
2.921 0.530 1.183
4.979 0.530 2.130

4000

5000

Figure 5: Error curves of GA and GAVI.
65error rate [%]Algorithm
type

2000
3000
t[times]43s=5025. Conclusions
1s=100We proposed GAVI for TSP and compared the performance of GAVI and GA to lead approximate solutions. From0the simulations, the result of GAVI was better than GA by us0
0.1
0.2
0.3
0.4
0.5ing appropriate inf ection rate. It was efficient that not only
Infection rate
GA but also Inf ection applied in TSP. GAVI was valuable
in convergence of the solution. We confirmed that VTE isFigure 6: Relationship between inf ection rate andefficient in TSP.
error rate.
In future work, we would like to study the mechanism ofInf ection in detail. In this study, all number of elementin Inf ection is depended on fixed probability. However,changing fixed probability each number of element would ex- [2] Jean-Yves Potvin,“Genetic algorithms for the traveling salesman problem,” Annals of Operations Research 63, pp.339-370, 1996.
pect efficient. Moreover, it is necessary that consideration of[3] Kitano H ed.,“Identeki Algorithm[Genetic Algorithm],” 1st ed.Sangyo
diversity of genetics. We would expect to consideration of diTosyo Kabushiki Kaisya, 1993.
versity of genetics in using Virus Infection algorithm obtains [4] Fang G, Hongwei L, Qiang Z, Gang C, “A Genetic Algorithm with aMixed Region Search for the Asymmetric Traveling Salesman Problem,”good solution in other TSP.
Acknowledgment
This work was partly supported by JSPS Grant-in-Aid forYoung Scientists 23700269.
References[1] Little J, Murty K, Sweeney D, Karel C, “An algorithm for the travelingsalesman problem,” Operations Research 11:972-89, 1963.

Computers and Operations Research 30(5), 773-786, 2003.
[5] Naoshi N, Akinori K and Kunio K, “An Evolutionary Algorithm Basedon the Virus Theory of Evolution,” Information Processing Society ofJapan 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,” Bulletin of Yamanashi Medical University Vol.3, pp.14-18, 1986.
[8] Zhaxybayeva O, Doolittle W F, “Lateral gene transfer,” Curr. Biol. 21,
R242-246 2011

- 292 -