IEEE Workshop on Nonlinear Circuit Networks
December 13-14, 2013

Combination of Immune Algorithm and Virus
Theory of Evolution for TSPs
Takuya Inoue, Yoko Uwate and Yoshifumi Nishio

Tokushima University
2-1 Minami-Josanjima, Tokushima 770-8506, JAPAN
Email: {t-inoue, uwate, nishio}ee.tokushima-u.a .jp

Abstra t We propose Evolutionary Algorithm with Immune
and Infe tion (EAII). EAII is using Virus Theory of Evolution
algorithm to be based on Immune Algorithm. Thus, EAII nds
a optimal solution in ombinatorial optimization problems byupdating antibodies and apart of the information of the antibody
hanging by Virus Theory of Evolution. We onrm that EAII
obtains more effe tive result than others method.
I. I NTRODUCTION
In daily life, there are many optimization problems. One ofthese optimization problems is Traveling Salesman Problem(TSP) [1]. TSP is known as one of ombinatorial optimization
problems. When salesman is given a set of number N ities,
TSP is the problem of nding minimum total between ea hity distan e. When the number of N in reases, the total routenumber explodes. Therefore, exploring total route number
needs amount of time in nding approximate solution. It isne essary to solve the TSP in other ways ex ept exploring
total routes. There is a variety of methods to nd approximate
solution by TSP [2]-[4].
Immune Algorithm (IA) [5], [6] is one of method to solve
the TSP, and modeling behavior of updating antibodies inorganism. In repeating these updating antibodies, antibodies
group hanges ef ient group for ghting antigen. IA nds
optimal solution by using these behavior.
However, IA onsiders only updating antibodies group.
Thus, we fo us attention on a quiring the Virus Theoryof Evolution (VTE) by antigen besides updating antibodies
group. We propose Evolutionary Algorithm with Immune andInfe tion (EAII ). EAII is using VTE algorithm to be based on
Immune Algorithm. We onrm that the proposed algorithma hieves better performan e than other methods.

ell, genes an evolve. Low tness individuals possibly evolve
into high tness individuals in just one generation by LGTin Virus infe tion. Algorithms of using VTE was proposedin the past [9]. We assume using VTE algorithm leads theapproximate solution in less time and VTE theory is ef ientin TSP.
III. E VOLUTIONARY A LGORITHM WITH I MMUNE AND
I NFECTION

1II. V IRUS T HEORY OF E VOLUTION
Organi evolution is theory based on natural sele tion.
In natural world, high tness individuals organism survive,
while low tness individuals organism be ome extin t. Overthe years, only higher tness individuals survive. We all itEvolution. Thus, evolution needs to overlay generations.
On the other hand, Virus Theory of Evolution (VTE) [7] hasproposed aside from organi evolution. This theory is basedon the evolution by Lateral Gene Transfer (LGT) [8] in Virusinfe tion. Without evolution inherited from parent ell to hild
1 We are submitting the same

ontent to IEEE International Symposium on

Cir uits and Systems (ISCAS'14).

- 72 -Fig. 1.

Flowhart of EAII.

In this se tion, we explain ow of Evolutionary Algorithmwith Immune and Infe tion (EAII). Flow hart of EAII isshown in Fig. 1. Flow of EAII shows Steps1-4. Step2 fromStep4 is repeated until the set number of updating antibodies(tmax ). t means the number of repeating times.
Step1 Initialization

We prepare a number of random route sele tion. We dene
the number of random routes as antibodies. The number ofrandom route sele tion is U .

Step2 Evaluation of antibodies

Where axi is level of afnity and is dened by the following
Eq. (1). caj indi ates the antigen, and N indi ates number ofity.
axi =NX(1)

axij

IV. S IMULATION R ESULTS
In order to ompare the performan e of EAII and otheralgorithms, we apply to nd approximate solutions in TSP.
In this study, the number of t is 2000 times, the number ofsimulation is 5 times, U is 1024, applying TSP are 4 kinds
and error rate is dened by the following Eq. (6).

j=1axij =

1(cij = caj )0(cij 6= caj )(2)

Where ci is on entration of spe i antibody. S indi ates
number of antibody.
Sci =1X
ayij
S j=1(obtain) − (optimum)× 100 (6)(optimum)where obtain shows obtained solution and optimum shows
Error rate[%] =(3)optimum solution.
Table I shows result of EAII, GA and ACO. GA is Geneti
Algorithm [10], ACO is Ant Colony Optimization [11]. GAand ACO are same the number of t and U for omparing
performan e of EAII. In Table I, result of EAII is the best of
three methods.
TABLE Iayij =

1(axi = axj )0(axi 6= axj )(4)

By using axi and ci , we al ulate ei . dtotal−i indi ates total
distan e of ea h route. α is oef ient. Where ei is evaluation
value, and is dened by the following Eq. (5).
ei =1(dtotal−i)α×axiciT(5)

Equation (5) means that high evaluation values organism
survive, while low evaluation values organism be ome extin t.
Step3 Produ tion of new antibodies

In surviving antibodies in Step2, new antibodies is produ edby Crossover and Mutation.

HE RESULT OF SIMULATIONS

att48

kroC100

eil101

gr120

GA

5.54

13.34

13.34

12.32

ACO

2.76

10.21

7.19

6.01

EAII

1.29

9.47

6.61

3.89

V. C ONCLUSION
We proposed EAII for TSP and ompared the performan eof EAII and other algorithms to lead approximate solutions.
From the result, the result of EAII was better than othermethods. Thus, it was ef ient to use VTE based on IAin TSP. Furthermore, we expe t that EAII has te hnologi alappli ation possibility.
In future work, we would like to study the me hanism ofInf ection in detail. We expe t to obtain a better solution bystudying me hanism of Inf ection.

Step4 Infe tion

R EFERENCES

We dene elements of ea h route as antigen, elements sele t
the minimum route in obtaining and part of ea h route isinfe ted by this antigen at random. Number of element sele tsis xed probability. Part of antibody hanges the information
held in this Virus like the Fig. 2. We all it Inf ection.

[1℄ E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy-Kan and D. B. Shmoys,editors. The Traveling Salesman Problem, Wiley, 1985.

[2℄ H. Kitano ed.,Identeki

Algorithm[Geneti Algorithm℄, 1st ed.Sangyo

Tosyo Kabushiki Kaisya, 1993.

hi,Optimization by simulated
annealing, S ien e, 220, pp.671-680, 1983.
[4℄ J. Kennedy and R. C. Eberhart, Parti le swarm optimization, Pro .
[3℄ S. Kirkpatri k, C.D. Gelatt Jr., M.P. Ve

IEEE. Int. Conf. Neural Netw, pp.1942-1948, 1995.

[5℄ S. Garrett, How Do We Evaluate Arti ial Immune Systems?, Evolutionary Computation, vol.13, no.2, pp.145-178, 2005.

[6℄ V. Cutello, G. Ni osia, M. Pavone, J. Timmis, An Immune Algorithm

for Protein Stru ture Predi tion on Latti e Models, IEEE Transa tions
on Evolutionary Computation, vol.11, no.1, pp.101-117, 2007.

[7℄ Hideomi N, Takashi S and Takashi F, Virus theory of evolution, Bulletinof Yamanashi Medi al University Vol.3, pp.14-18, 1986.

[8℄ Zhaxybayeva O, Doolittle W F, Lateral gene transfer, Curr. Biol. 21,
R242-246, 2011.

[9℄ N. Nakayama, A. Kanasugi and K. Kondo, An Evolutionary Algorithm

Based on the Virus Theory of Evolution, Transa tions of Information
Pro essing So iety of Japan, Vol.40, No.5 p2346-2355, 1999.

[10℄ Jean-Yves Potvin,Geneti
Fig. 2.

The me hanism ofalgorithms for the traveling salesman problem, Annals of Operations Resear h 63, pp.339-370, 1996.
[11℄ M. Dorigo, V. Maniezzo and A. Colorni, The ant system: optimization
by a olony of ooperating agents, IEEE Trans, IEEE Trans. Sys-

Inf ection.

tems Man Cybernet, B 26, p29-42, 1996.

- 73 -