平成25年度電気関係学会四国支部連合大会 講演論文集 （2013 徳島大学）
2013 SHIKOKU-SECTION JOINT CONVENTION RECORD OF THE INSTITUTES OF ELECTRICAL AND RELATED ENGINEERS (TOKUSHIMA)

1-28
Evolutionary Algorithm with Immune and Infection
for Traveling Salesman Problems
Takuya INOUE, Yoko UWATE and Yoshifumi NISHIO(Tokushima University)

1. Introduction

Step4 (Inf ection)

In this paper, we propose Evolutionary Algorithm withImmune and Infection (EAII). Immune Algorithm[1] wasproposed in the past and finds a optimal solution by updating antibodies. On the other hand, EAII is using
infection algorithm to be based on Immune Algorithm.
Thus, EAII finds a optimal solution in combinatorial optimization problems by updating antibodies and apart ofthe information of the antibody changing by infection. In
this study, we apply proposing method of EAII to Traveling Salesman problems (TSP) and confirm that EAIIobtains more eﬀective result than others method.

We define elements of each route as antigen, elements
select the minimum route in obtaining and part of eachroute is infected by this antigen at random. Number ofelement selects is fixed probability.

3. Experimental Results
In order to compare the performance of EAII and others method. In this study, the number of updating antibodies is 2000 times, the number of simulation is 5 times,
number of antibody is 1024 and error rate is defined by
the following formula.

2. Flow of EAIIIn this section, we explain flow of Evolutionary Algorithm with Immune and Infection (EAII). Flow of EAII
shows Step1-4. Step2 from Step4 is repeated until theset number of updating antibodies.

Step1 (Initialization)
Initialization is random route selection. We define random routes as antibodies.

Step2 (Evaluation of antibodies)
Where axi is level of aﬃnity and is defined by the following formula. caj indicates the antigen, and N indicates
number of city.
axi =N∑axij =1(cij = caj )0(cij ̸= caj )

(1)

(2)

Where ci is concentration of specific antibody. S indicates number of antibody.

∑Sci ={
ayij =

j=1

ayij

S
1(axi = axj )0(axi ̸= axj )

(3)

(6)

where obtain is minimum solution and optimum is optimum solution. When obtain value approaches optimum
value, Error rate is low. For example, when obtainvalue is equally optimum value, Error rate is 0[%]. IfError rate is 0[%], we would obtain optimum solution.
However, obtain is bad solution, error rate is high.
Table 1 shows result of EAII and others method. GAis Genetic Algorithm, AS is Ant System and GIACO[2]is Ant Colony Optimization Using Genetic Information.
Using TSP types are 5 types. att48 is 48 cities, kroC100
is 100 cities, eil101 is 101 cities, gr120 is 120 cities andgr202 is 202 cities.

1axi×(dtotal−i )αciAlgorithm
typeGAASGIACO
EAII

att48
5.54
2.76
2.41
2.03

Error rate[%]kroC100 eil101 gr120
13.34
13.34
12.32
10.21
7.19
6.01
9.50
2.11
4.64
9.47
6.61
3.89

gr202
10.01
1.31
0.00
9.08

In Table 1, EAII does not obtain the best solution inall TSP type, however EAII can obtain basically goodsolution.

4. Conclusion(4)

In using axi and ci , we calculate ei . dtotal−i indicates
total distance of each route. α is coeﬃcient. Where ei isevaluation value, and is defined by the following formula.
ei =(obtain) − (optimum)× 100(optimum)

Table 1: result
axij

j=1

{Error rate[%] =(5)High evaluation values organism survive, while low
evaluation values organism become extinct.

Step3 (P roduction of new antibodies)
In surviving antibodies, this Step3 acts production of new
antibodies by Crossover and Mutation. Crossover is to
be mated the two routes, and Mutation is to change theroute with a certain probability.

28

We proposed EAII for TSP and applied it to lead approximate solutions. From the result, EAII was valuable
to obtain of the good solution. In the future work, wewould like to study the mechanism of Inf ection in detail.
It is also our future work to investigate leading approximate solution for large number of cities in TSP.

References[1] K. Mori and M. Tsukiyama, “Immune algorithm withsearching diversity and its application to resource allocation problem,” Transactions on JIEE 113-C (10), 1993.
[2] S. Shimomura, H. Matsushita and Y. Nishio, “Ant Colony
Optimization Using Genetic Information for TSP,” Proceedings of International Symposium on Nonlinear Theoryand its Applications (NOLTA’11), pp. 48-51, 2011.