2013 International Symposium on Nonlinear Theory and its Applications
NOLTA2013, Santa Fe, USA, September 8-11, 2013

Consideration of Diverse Solutions Geneti Algorithm with Virus Infe tionfor Traveling Salesman Problem
Takuya Inoue, Yoko Uwate and Yoshifumi Nishio

Tokushima University
2-1 Minami-Josanjima, Tokushima 770-8506, JAPAN
Email: ft-ionue, uwate, nishiogee.tokushima-u.a .jp
Abstra tGeneti Algorithm (GA) is known as one ofmethod to solve Traveling Salesman Problem (TSP). However, GA needs amount of time for nding approximate solution. In our previous study, we have proposed Geneti
Algorithm with Virus Infe tion (GAVI). GAVI algorithm
is used Virus Theory of Evolution (VTE) to be based on
GA. Chara teristi of VTE is e e tive for nding approximate solution. Thus, GAVI obtains more e e tive result
than GA. However, GAVI does not make onsideration ofdiverse solutions. In this study, we propose new algorithm
to make onsideration of diverse solutions. This proposedalgorithm is named Consideration of Diverse Solutions Geneti Algorithm with Virus Infe tion (DS-GAVI). We apply
DS-GAVI to TSP and onrm that DS-GAVI obtains e e tive solutions for leading approximate solution.
1. Introdu tion
Traveling Salesman Problem (TSP) [1℄ is known as oneof the ombinatorial optimization problems. When Salesman tours all ities at on e, TSP is the problem of nding
minimum total between ea h ity distan e in route. Then nis the number of ities in TSP, total route number in reaseat rate proportional to many of the fa torial of n. Therefore,
exploring total route number needs amount of time for nding approximate solution. It is ne essary to solve the TSP
in other ways ex ept exploring total routes.
Geneti Algorithm (GA) [2℄, [3℄ is one of the popularmethod in variety of ways to solve the TSP and is studied
by many resear hers all over the world. GA is modelingbehavior of evolution in organi , and is to explore the solution for repeating rossover on the basis of organi evolution. Thus, GA needs overlaying the generation for obtaining approximate solution. Whereat, in our previous study,
we have proposed Geneti Algorithm with Virus Infe tion(GAVI) [4℄. GAVI is used Virus Infe tion algorithm basedon GA. One of the hara teristi s of the Virus Infe tion
[5℄-[7℄ is infe tion other same generations at on e. This
hara teristi seemed to be useful for nding the approximate solution qui kly. Therefore, we onrmed that VTEis eÆ ient in TSP.
However, GAVI does not make onsideration of diverse
solutions. Moreover, in using the Virus Infe tion algorithm, gene group are easy to have similar nature. Be ause

hara teristi s of the Virus Infe tion is to onvey part ofgene information to other genes. In this study, we propose new algorithm to make onsideration of diverse solutions. This proposed algorithm is named Considerationof Diverse Solutions Geneti Algorithm with Virus Infe tion (DS-GAVI). If algorithm does not make onsiderationof diverse solutions, gene group would tend to have similar
nature. Thus, algorithm is diÆ ult to es ape lo al minimum, and needs onsideration diverse solutions for obtaining better solution. We arry out omputer simulations
for various parameter values and onrm that DS-GAVI
a hieves better performan e than GAVI.
2. Virus Theory of Evolution
Organi evolution is theory based on natural sele tion.
In the natural world, high tness individuals organism survive, while low tness individuals organism be ome extin t. Over the years, only higher tness individuals survive. We all it evolution. Thus, evolution need to overlay
generations.
On the other hand, there is theory named by Virus Theory of Evolution (VTE) [8℄. This theory is based on theevolution by Lateral Gene Transfer (LGT) [9℄ in Virus infe tion. LGT is uptake of the gene that o ur between
other individuals and among other spe ies. Without evolution inherited from parent ell to hild ell, genes anevolve. Low tness individuals possibly evolve into hightness individuals in just one generation by LGT in Virusinfe tion. In other words, we assume that ea h individualbe ome a better evaluation value qui kly. Thus, we assume
using VTE algorithm leads the approximate solution in lesstime and VTE theory is eÆ ient in TSP.
3. Diverse Solutions Geneti Algorithm with Virus Infe tion (DS-GAVI)GAVI is a method of VTE algorithm in Virus infe tion
to be based on GA. DS-GAVI is used both Good Sele tion and Bad Sele tion in ombination to keep diverse solutions. Good Sele tion tends to be hosen high evaluationroute. While, Bad Sele tion tends to be hosen low evaluation route. Figure 1 shows the ow hart of DS-GAVI.
tmax is number of repeating times. DS-GAVI algorithm is- 102 -indi ated the following Step1-7. Step2-7 is repeated until
the set number of rossover times. After the set number ofrossover times, DS-GAVI output the best solution in all
getting solutions.
step1 (Initialization)
Initialization is random route sele tion. Number of random route sele tion is U .
step2 (Evaluation)

step6 (Infe tion)
Infe tion is in orporating partial optimum solution. The
best individual, whi h gives the shortest tour in ea h generation, is dened as a Virus. The infe tion to other individuals is de ided with a xed probability. The infe tion
is made as opying some elements of the Virus, where theposition and the size are sele ted at random. For example,
3; 5 is a virus and has infe ted the route of 6; 1; 3; 5; 2; 4 inFig. 4. Infe tion part determines 1; 4 in the route. The route
repla e to 3; 5 1; 4. We all it Infe tion.

Evaluation is dened by the following formula.

fi =1

(1)

diwhere di is total distan e of ea h route and fi is evaluation value. If di is low, fi is high by this formula.
step3 (Sele tion)
In this study, we apply two sele tion method. The rst
method tends to be hosen high evaluation route. We allthis method Good Sele tion. In Good Sele tion, route issele ted with a probability of pgi . pgi is dened by thefollowing formula. Where n is the number of ities.

fpgi = Pn i

i=1 fi

step7 (One route reset in random)
If a obtained solution is same among number of s, one
route in all routes is initialization at random. O(t) is theobtained 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 the obtained solution is same among number ofs. We assume that this is eÆ ient to es ape lo al minimum.




(2)? ? 

While, the se ond method tends to be hosen low evaluation route. We all this method Bad Sele tion. In BadSele tion, route is sele ted with a probability of pbi .

dpbi = Pn ii=1di? #?  (3)     '(We use the both Good Sele tion and Bad Sele tion inombination.
step4 (Fulll rossover ondition)
This se tion evaluates rossover ondition. If parents
is not fulll rossover ondition, rossover is not a tion.
when rossover ondition is fulll, rossover is a tion.

$%&>    

step5 (Crossover) '($%&Crossover is to be mated the two routes. In this study,
we apply sub tour ex hange rossover. This way makes asear h for sub tour of Both Parent A and Parent B in ommon. If it does not nd sub tour in ommon, rossover is
not a tion. For example, between 1; 2; 5; 6 and 5; 1; 6; 2 are
sub tour in Fig. 2. 1; 2; 5; 6 and 5; 1; 6; 2 are di er in line,
however these are same lass. Sub tour in 1; 2; 5; 6 an express 1; 2; 5; 6 and 6; 5; 2; 1, 5; 1; 6; 2 an express 5; 1; 6; 2and 2; 6; 1; 5. Be ause two expressing are same about totalroute distan e in Fig. 3. Thus, after rossover, four hild
exist.

- 103 -   ? $%& '(!"Figure 1: Flow hart of DS-GAVI.

4. Experimental Results In order to onrm the performan e of onsideration ofdiverse solutions, we apply DS-GAVI to nd approximate
solutions in TSP su h as att48 , eil51 and berlin52. In thisstudy, tmax = 5000 , s = 5, the number of simulation is 30times, U = 1000, and error rate is dened by the followingformula.

 





Error rate[%℄ =(obtain) (optimum)
 100(optimum)(4)

where obtain is minimum solution and optimum is optimum solution. When obtain value approa hes optimumvalue, Error rate is low. For example, when obtain value
is equally optimum value, Error rate is 0[%℄. If Error rate
is 0[%℄, we would obtain optimum solution. However, if
obtain is bad solution, error rate is high.

Figure 2: The me hanism of rossover.
Table 1: The result of hanging Sele tion rate in DS-GAVI
sele tion rate
Error rate[%℄Good Bad att48
eil51 berlin52
1.0
0.0 1.222 4.148
0.209
0.8
0.2 1.140 2.026
0.179
0.7
0.3 1.649 1.918
0.277
0.6
0.4 0.794 1.984
0.308
0.5
0.5 1.536 2.461
0.955
0.4
0.6 1.485 2.142
2.915
0.3
0.7 1.649 6.746
7.587
0.2
0.8 3.498 39.896 17.259

Figure 3: Relationship between sub tour and touring number
!"   :#:

Figure 4: The me hanism of Infe tion.

Table 1 shows the result of average value and hanging the both Good S ele tion rate and Bad S ele tion rate.
Good S ele tion rate = 1:0 indi ates only using Good Sele tion. We need to use properly parameter by ea h TSP
type. However, we obtain better solutions than only using
Good S ele tion rate = 1:0.
Whereat, Figs. 5-7 show the relationship between evaluation value in att48. Using parameters in DS-GAVI are
Good S ele tion rate = 0:6 and Bad S ele tion rate = 0:4
in one simulation. In Figs. 5-7, we sort sele ted routes indes ending order for fa ilitating visualization. Figures 5-7
show the results at t = 0, t = 1000 and t = 4000, respe tively. In Fig. 5, the results of the both GAVI and DS-GAVI
are almost same. While, in Figs. 6 and 7, the results of
GAVI and DS-GAVI are di erent. Thus DS-GAVI is sele ted various evaluation value by the both Good Sele tion
and Bad Sele tion in ombination.
Table 2 shows the best result of ea h algorithm. In DSGAVI, we use the best parameter in S ele tion rate by Table 1. For that reason it is eÆ ient for es aping lo al minimum to keep diverse solutions. Thus, DS-GAVI an obtain
the best result.

- 104 -Table 2: The best result of ea h algorithm for TSP
TSP
Error rate[%℄typeGA GAVI DS-GAVI
att48
2.400 1.222
0.794
eil51
4.148 2.665
1.918
berlin52 0.787 0.209
0.179




#$%&
 "'()#$%&


!

 5. Con lusions    Figure 5: Relationship between evaluation value and sele ted routes at t = 0.

3+*,/*.

LMNO2+.,/*.

A knowledgment

KFE

This work was partly supported by JSPS Grant-in-Aidfor Young S ientists 23700269.

2+*,/*.
DCJI1+.,/*.
H
GWe proposed DS-GAVI for TSP and ompared the performan e of GA, GAVI and DS-GAVI to lead approximate
solutions. From the simulations, the result of DS-GAVI
needs to use properly parameter by Good S ele tion andBad S ele tion rate. In using the both Good Sele tion andBad Sele tion in ombination, DS-GAVI was able to keep
diverse solutions. DS-GAVI was easier es aping lo al minimum than GAVI. Thus, DS-GAVI obtained better solutions than GAVI.

DFPQRLMNO
EDC

1+*,/*.

Referen es.+*,/*0[1℄ Little J, Murty K, Sweeney D, Karel C, An algorithm for the trav-B

eling salesman problem, Operations Resear*+*,-***

2**

4**

0**

[2℄ Jean-Yves Potvin,Geneti

5**

h 11:972-89, 1963.

algorithms for the traveling salesman

problem, Annals of Operations Resear

h 63, pp.339-370, 1996.

6789:; <= >?:@:A[3℄ Kitano

Figure 6: Relationship between evaluation value and sele ted routes at t = 1000.

Hed.,Identeki

Algorithm[GenetiAlgorithm℄,

1st ed.Sangyo Tosyo Kabushiki Kaisya, 1993.
[4℄ Takuya I, Yudai S, Yoko U and Yoshifumi N, Consideration
GenetiofAlgorithm with Virus Infe tion Solving Traveling Salesman

Problem Pro

eedings of RISP International Workshop on Nonlin-ear Cir uits, Communi ations and Signal Pro essing (NCSP'13), pp
289-292, 2013.

\TSUXSWuvwx[5℄ Fang G, Hongwei L, Qiang Z, Gang C, A Geneti[TWUXSWtonAlgorithm with aMixed Region Sear h for the Asymmetri

Traveling Salesman Prob-lem, Computers and Operations Researh 30(5), 773-786, 2003.

[TSUXSWmls[6℄ Naoshi N, Akinori K and Kunio K, An EvolutionaryAlgorithm

Based on the Virus Theory of Evolution, Information Pro

essing So-yz{uvwxr

ZTWUXSWqp

iety of Japan Vol.40, No.5, 1999.
mon

ZTSUXSWml[7℄ Gao F, Liu H, Zhao Q, Cui G, Virus-evolutionary parti le swarm

koptimization algorithm,vol 4222. Springer, Berlin, pp 156-165,2006.

WTSUXSY[8℄ Hideomi N, Takashi S and Takashi F, Virus theory of evolution,

STSUVSS

Bulletin of Yamanashi Medi al University Vol.3, pp.14-18, 1986.
S[SS]SSYSS^SS[9℄ Zhaxybayeva O, Doolittle W F, Lateral gene transfer, Curr. Biol.

_`abcd ef ghcicj

21, R242-246 2011.

Figure 7: Relationship between evaluation value and sele ted routes at t = 4000.

- 105 -