2014 International Symposium on Nonlinear Theory and its Applications
NOLTA2014, Luzern, Switzerland, September 14-18, 2014

E e tiveness of Combination of Arti ial Immune Systemand Virus Theory of Evolution for QAPs
Takuya Inoue, Yoko Uwate and Yoshifumi Nishio

Department of Ele tri al and Ele troni Engineering, Tokushima University
21 Minami-Josanjima, Tokushima 7708506, Japan
Email: ft-inoue, uwate, nishiogee.tokushima-u.a .jp
Abstra tThis paper presents the solving method ofQuadrati Assignment Problems (QAPs). This method
uses both Arti ial Immune System (AIS) and Virus Theory of Evolution (VTE), and we all it Evolutionary Algorithm with Immune and Infe tion (EAII). EAII has hara teristi s of both AIS and VTE. We onsider that EAII ise e tive method for QAPs. Thus, we apply EAII to theQAPs and onrm that EAII obtains more e e tive result
than IA. Furthermore, we analyze the reason for obtaining
better solution in EAII.

2. Quadrati

Assignment Problem

The Quadrati Assignment Problem (QAP) [4℄,[5℄ is demanded looking for the best allo ation of a tivities in lo ations. Task of the QAP is to assign all a tivities to di erent
lo ations with the minimum ost among all ombinations.
The QAP has two matri es (F and D) of the dimensionn  n (n indi ates the size of problems). The matrix of F indi ates ea h ow of a tivity, and the matrix of D indi ates
ea h distan e. In using F and D, total assignment ost E (P)is shown as Eq. (1).

E ( P) =1. Introdu tion

Optimization problem is the problem to analyze state ofmaximum or minimum value in the fun tion of a spe iset. Some optimization problems are diÆ ult to nd theoptimum solution. For example, these problems are Fun tion Optimization Problem [1℄, Traveling Salesman problem [2℄, Knapsa k Problem [3℄ and so on. Quadrati Assignment Problem (QAP) [4℄,[5℄ is known as one of diÆult problems to nd the optimum solution.
Arti ial Immune System (AIS) [6℄ is omputer system
based on immune system of living organisms. AIS is able
to apply to a variety of elds [7℄-[9℄; optimization problems, pattern re ognition, roboti s and so on. Immune Algorithm (IA) [10℄-[12℄ is based on AIS and is devised inimmune system of possessing organisms. IA nds optimal
solution by updating antibody group.
In this study, we fo us attention on infe tion algorithm.
The infe tion algorithm is based on Virus Theory of Evolution (VTE) [13℄-[15℄, Chara teristi of VTE seems to be
useful for nding the approximate solution qui kly. If wepropose the algorithm to use both infe tion algorithm andimmune system, we an make a predi tion that this algorithm obtains better result than IA. Thus, we propose Evolutionary Algorithm with Immune and Infe tion (EAII).
EAII is the hybrid method of infe tion algorithm and IA.
We arry out omputer simulations for various parametervalues and onrm that the proposed algorithm of EAII
a hieves better performan e than other methods.

n XnX
i=1 j=1

fi j d p i p j( ) ( )(1)where fi j and d p(i) p( j) are (i,j)-th elements of D and F ,p(i) p( j) is a alignment value.
For example, the matrix of F and D are dened byEqs. (2) and (3). Figures 2 and 3 an indi ate Eqs. (2)and (3). If f of ow allo ate P( f 2; f 1; f 4; f 3) to(d1; d2; d3; d4) like Fig. 1, al ulation result of E (P) isshown as Eq. (4).
2 0 5 10 2 37666666 5 0 6 3 77777(2)
F = 66666 10 6 0 4 77777
57462 3 4 02 0 21 11 44 37666666 21 0 12 30 77777
6
D = 6666 11 12 0 9 77777
7564
44 30 9 0E ( P) ===4 X4X

i=1 j=12 0666
666 5666666 10421524(3)fi j d p i p j( ) ( )32
5 10 2 377 66 0 21 30 12 777777 666
0 6 3 777 666 21 0 44 11 77777
6 0 4 77775 66664 30 44 0 9 77775
12 11 9 03 4 0(4)If the size of n in reases, the total ombination of alloation explodes. The task of QAP is to demand minimum
value of E (P).

- 160 -Figure 1: Example of QAP (n = 4).

Figure 2: Flow of a tivity.

Figure 3: Distan e.
Figure 4: Flow hart of EAII.

3. Virus Theory of Evolution

Organi evolution is theory based on natural sele tion.
In natural world, individuals of high tness survive, while
individuals of low tness 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)[13℄ has proposed aside from organi evolution. This theory is based on the evolution by Lateral Gene Transfer(LGT) [14℄ in Virus infe tion. LGT is uptake of the gene too ur between other individuals and among other spe ies.
Without evolution inherited from parent ell to hild ell,genes an evolve. Low tness individuals possibly evolve
into high tness individuals in just one generation by LGT
in Virus infe tion. Algorithms of using VTE was proposedin the past [15℄. We assume using VTE algorithm leads
the approximate solution in less time and VTE theory iseÆ ient for the QAP.

Step2 Evaluation of antibodies

Level of aÆnity
Level of aÆnity indi ates evaluation value, and is dened by the following Eq. (5).
v =1
E (v)

(5)

Degree of similarity
Degree of similarity of antibody v and w is dened by
the following Eq. (6).
vw

= 1 +1Hvw(6)

Hvw indi ates hamming distan e of v and w. Thus, when vand w are exa tly the same, Hvw equals 0.

4. Evolutionary Algorithm with Immune and Infe tion

Con entration

Evolutionary Algorithm with Immune and Infe tion
(EAII) is based on AIS [10℄,[11℄ and VTE. Flow hart ofEAII is shown in Fig. 4. Flow of EAII shows Steps1-5.
Step2 from Step5 is repeated until the set iteration (tmax ).

Con entration is dened by the following Eq. (7),(8).
(U : Number of antibodies)v = U1

Step1 Initialization

We prepare a number of random lo ation sele tion. Wedene the number of random lo ations as antibodies. The
number of random lo ations sele tion is U .

- 161 -vw =Whenvw

(UX
w=1

vw

1 ( vw ≧ T 1 )0 ( vw < T 1 )ross threshold of T 1 , vw ree ts v .

(7)
(8)

Step3 Di erentiation

Memory ellThis se tion is di erentiation of antibodies into memory
ell. If on entration v of ea h antibody v ross threshold of T 2 , v hanges andidate memory ell . When 
do not rea h a upper limit of number of memory ells, be omes di erentiated into memory ell. While  rea h aupper limit of number of memory ells, we al ulate degree of similarity m of  and m. When evaluation valueof  ross highest value of m ,  be omes di erentiatedinto memory ell.

Figure 6: The me hanism of In f e tion.

T ellThis se tions di erentiation of antibodies into T ell. v
be omes di erentiated into T ell t in des ending order ofon entration. We al ulate degree of similarity vt of v
and t. If vt ross threshold of T 3 , v be ome extin t. Thisbehavior indi ates inhibition of similar solution. Extin t
antibodies replenish new antibodies by random number.
Step4 Promotion and Inhibition of produ tion antibod-5. Simulation Results

In order to ompare the performan e of EAII and IA, weapply to nd approximate solutions in QAPs. In this study,
the number of tmax is 4000 times, the number of simulationis 10 times, U is 1024, applying QAP type are 5 kinds [5℄.
error rate is dened by the following Eq. (9).

ies

Error rate[%℄ =Extin tion and existen e
We al ulate level of aÆnity v by all antibodies v.
Number of N2 of v exist in des ending order of v . While,other N2 of v be ome extin t.

Produ tion new antibodies
In surviving antibodies v, new antibodies are produ ed

by Crossover. Crossover is to be mated the two lo ations
like Fig. 5.
Step5 Infe tion(9)where obtain denotes obtained solution and optimumshows optimum solution. When obtain value approa hes
optimum value, Error rate is low.
Tables 9 shows result of EAII and IA. IA is same thenumber of t and U for omparing performan e of EAII.
Infe tion rate in EAII is 20%. We use these parametersof the ea h best result by simulation results. In results ofTable 1, we onrm that EAII obtains the better solution
than IA.
Table 1: The result of Error rate[%℄QAP type Size
IAEAII
tai12a12
6.15
1.05
s r1212
2.58
0.00
nug2020
9.51
6.85
had20
20
2.62
1.07
nug3030
14.23 12.42

We sele t one memory ell. New antibodies are infe ted by a part of element of sele ted memory ell. Sele ted memory ell hanges ea h time, and the sele ted
number of element is de ided with xed probability. Partof antibody hanges the information held like Fig. 6. We
all it In f e tion. In this study, we dene In f e tion rate.
In f e tion rate indi ates a fra tion that antibodies group a quire the In f e tion.

Figure 5: The me hanism of Crossover.

(obtain) (optimum)
 100(optimum)

Se ond, we fo us on distribution of solutions. We investigate distribution of solutions by EAII and IA in nug30(tmax = 4000; U = 1024). Figure 7 shows sort solutions byhigh ost of E (P). Horizontal axis is the number of memory
ell, and verti al axis is the ost of E (P). Initialization ofEAII and IA are same onguration, and number of memory ells are 50. Distributions of solutions are almost samein memory ells by EAII and IA. However, the result ofEAII is better than IA. Thus, EAII keeps diverse solutionand obtains good result.

- 162 -2960

7100

EAII
IA

EAII

2940

7050

2920
2900

7000

2860

E(P)

E(P)

2880

6950

2840
2820

6900

2800

6850

2780
2760
0102030
Memory cells

4050

6800
02040

60

80100

Number of memory cell

Figure 7: Distribution of solutions in nug20.

Figure 9: Relationship between number of the memory elland evaluation value (nug30).

Third, we investigate al ulation time and evaluation
value by hanging the number of memory ell. The number of memory ell is hanged from 5 to 100, the numberof simulation is 5 times, ea h value uses average value by
5 times, and QAP type is nug30 (tmax = 4000; U = 1024).
Figure 8 shows relationship between the number of memory ell and al ulation time, and Fig. 9 shows relationshipbetween number of memory ell and evaluation value. If
number of the memory ell in reases, al ulation time also
in reases. While, if the number of memory ell in reases,
EAII does not obtain good solution. Thus, we need to set
the appropriate the number of memory ell.

like to study the me hanism of In f e tion in detail. We expe t to obtain a better solution by studying me hanism ofIn f e tion.
A knowledgment

This work was partly supported by JSPS Grant-in-Aidfor Challenging Exploratory Resear h 26540127.
Referen es[1℄560
EAII

Evolutionary Computation. The Third Conferen e on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.249-257, 1994.

555

550

545
time[s]M.A. Potter, K.A De Jong,  A Cooperative Coevolutionary Approa h toFun tion Optimization, Pro eedings of the International Conferen e on[2℄E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy-Kan and D. B. Shmoys, editors.

[3℄D. Pisinger, Algorithms for Knapsa k Problems, PhD thesis, University ofThe Traveling Salesman Problem, Wiley, 1985.

Copenhagen, Dept. of Computer S ien e, 1995.

540

[4℄

E. Lawler, The Quadrati

Assignment Problem, Management S ien e 9,pp.586 1963.

535[5℄530R.E. Burkard, S.E. Karis h, F. Rendl, QAPLIB -A Quadrati Assignment Problem Library, Journal of Global Optimization Volume 10, Issue4, pp.391-403, 1997.

525[6℄de Castro L., Von Zuben F., Arti ial Immune System: Part I - Basi

[7℄de Castro L., Von Zuben F., Arti ial Immune System: Part II - A Survey of[8℄S. Garrett, How Do We Evaluate Arti ial Immune Systems?, Evolutionary

520
02040

60

80

100

Number of memory cell

Figure 8: Relationship between number of the memory ell
and al ulation time (nug30).

and Appli ations, Te hni al Report, TR-DCA, 1999.

TheoryAppli ations, Te hni al Report, TR-DCA, 1999.
Computation, vol.13, no.2, pp.145-178, 2005.

[9℄D. Dasgupta, S. Yu, F. Nino, Re ent advan es in arti ial immune systems,
Applied Soft Computing, 11(2), pp.1574-1587, 2011.

[10℄

K. Mori and M. Tsukiyama, Immune algorithm with sear hing diversity

and its appli ation to resour e allo ation problem, Transa tions on JIEE
113-C (10), 1993.

[11℄

6. Con lusions

We proposed EAII for solving the QAP, and ompared
the performan e of EAII and IA to lead approximate solutions. From the result, the result of EAII was better result
than IA. EAII obtained all kinds of evaluation value, and it
is important to keep of diverse solution in solving solutionof the QAP. Thus, it was eÆ ient to use VTE based on IAin the QAP. We expe t that apply these results to te hnologi al appli ation possibility. In future work, we would

K. Mori , M. Tsukiyama and T Fukuda Appli ation of an immune algorithm

to multi-optimization problems, T. IEEE Japan, vol.117-C, no.5, pp.593 598 1997.

[12℄

V. Cutello, G. Ni osia, M. Pavone, J. Timmis, An Immune Algorithm forProtein Stru ture Predi tion on Latti e Models, IEEE Transa tions on Evolutionary Computation, vol.11, no.1, pp.101-117, 2007. 86.

[13℄[14℄Domingo E, Es armis C, Sevilla N, Moya A, Elena SF, et al, Basi

on epts
in RNA virus evolution., FASEBJ, 10: 859-64, 1996.
Zhaxybayeva O, Doolittle W F, Lateral gene transfer, Curr. Biol. 21,
R242-246, 2011.

[15℄- 163 -An Evolutionary Algorithm
Based on the Virus Theory of Evolution, Transa tions of Information ProN. Nakayama, A. Kanasugi and K. Kondo,

essing So iety of Japan, Vol.40, No.5 p2346-2355, 1999.