IEEE Workshop on Nonlinear Circuit Networks
December 12-13, 2014

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

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 bothArti ial Immune System (AIS) and Virus Theory of Evolution(VTE), and we all it Evolutionary Algorithm with Immune andInfe tion (EAII). EAII has hara teristi s of both AIS and VTE.
We onsider that EAII is e e tive method for QAPs. Thus, weapply EAII to the QAPs and onrm that EAII obtains moree e tive result than IA. Furthermore, we analyze the reason for
obtaining better solution in EAII.
I. Introdu tion
Optimization problem is the problem to analyze state ofmaximum or minimum value in the fun tion of a spe i set.
Some optimization problems are diÆ ult to nd the optimumsolution. For example, these problems are Fun tion Optimization Problem, Traveling Salesman problem, Knapsa k Problem
and so on. Quadrati Assignment Problem (QAP) [1℄,[2℄ isknown as one of diÆ ult problems to nd the optimumsolution.
Arti ial Immune System (AIS) [3℄ is omputer system
based on immune system of living organisms. AIS is able
to apply to a variety of elds [4℄-[6℄; optimization problems,pattern re ognition, roboti s and so on. Immune Algorithm(IA) [7℄-[9℄ is based on AIS and is devised in immune systemof possessing organisms. IA nds optimal solution by updating
antibody group.
In this study, we fo us attention on infe tion algorithm. Theinfe tion algorithm is based on Virus Theory of Evolution(VTE) [10℄-[12℄, Chara teristi of VTE seems to be usefulfor nding the approximate solution qui kly. If we propose thealgorithm to use both infe tion algorithm and immune 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 methodof infe tion algorithm and IA. We onrmed e e tivenessof EAII in [13℄. In this paper, we investigate more detailede e tiveness of EAII.
II. Quadrati Assignment Problem
The Quadrati Assignment Problem (QAP) [1℄,[2℄ 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 dimension n  n (nindi ates the size of problems). The matrix of F indi ates ea h- 77 -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 Pn XnX
i=1 j=1fi 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 by Eqs. (2)and (3). Figures 1 and 2 an indi ate Eqs. (2) and (3). If
f of ow allo ate P( f 2; f 1; f 4; f 3) to (d 1; d 2; d 3; d 4),
al ulation result of E (P) is shown as Eq. (4).
2 0 5 10 2 37666666 5 0 6 3 77777
6(2)F =6666 10 6 0 4 77777
75
64
2 3 4 02 0 21 11 44 37666666 21 0 12 30 77777
766(3)
D = 6666 11 12 0 9 77777
5444 30 9 0Fig. 1: Flow of a tivity.

( )

E P

===4 X4X

i=1 j=1

2 0666666 5666
666 10421524

Fig. 2: Distan e.

fi j d p(i) p( j)5 10 2 377 266 0 21 30 12 377
76
70 6 3 77777 66666 21 0 44 11 77777
6 0 4 77775 66664 30 44 0 9 77775
3 4 0
12 11 9 0(4)If the size of n in reases, the total ombination of allo ation
explodes. The task of QAP is to demand minimum value ofE ( P).

III. 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. 6 On
the other hand, Virus Theory of Evolution (VTE) [10℄ has
proposed aside from organi evolution. This theory is basedon the evolution by Lateral Gene Transfer (LGT) [11℄ inVirus infe tion. LGT is uptake of the gene to o 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. Algorithmsof using VTE was proposed in the past [12℄. We assume usingVTE algorithm leads the approximate solution in less time andVTE theory is eÆ ient for the QAP.
IV. Evolutionary Algorithm with Immune and Infe tion
Evolutionary Algorithm with Immune and Infe tion (EAII)
is based on AIS [7℄,[8℄ and VTE. Flow hart of EAII is shownin Fig. 3. Flow of EAII shows Steps1-5. Step2 from Step5 isrepeated until the set iteration (tmax ).

Degree of similarity of antibody v andis dened by the following Eq. (6).

Degree of similarity:
wvw =1

1 + Hvw(6)

indi ates hamming distan e of v and w. Thus, when v andare exa tly the same, Hvw equals 0.
Con entration: Con entration is dened by the following
Eq. (7),(8). (U : Number of antibodies)
Hvww

v = U1
vw =(UX
w=1

vw

1 ( vw ≧ T 1 )0 ( vw < T 1 )

(7)

(8)

When vw ross threshold of T 1 , vw ree ts v .
Step3 Di erentiation
Memory ell: This se tion is di erentiation of antibodies
into memory ell. If on entration v of ea h antibody v rossthreshold 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 ofsimilarity m of  and m. When evaluation value of  rosshighest value of m ,  be omes di erentiated into memoryell.
T ell: This se tions di erentiation of antibodies into T
ell. v be omes di erentiated into T ell t in des endingorder of on entration. We al ulate degree of similarity vtof v and t. If vt ross threshold of T 3 , v be ome extin t.
This behavior indi ates inhibition of similar solution. Extin t
antibodies replenish new antibodies by random number.

Step4 Promotion and Inhibition of produ tion antibodies
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 endingorder of v . While, other N2 of v be ome extin t.
Produ tion new antibodies: In surviving antibodies v, newantibodies are produ ed by Crossover. Crossover is to bemated the two lo ations like Fig. 4.

Fig. 3: Flow hart of EAII.
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 .
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)

- 78 -

Step5 Infe tion

We sele t one memory ell. New antibodies are infe ted bya 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. Part of antibody hanges theinformation held like Fig. 5. 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 tionthat antibodies group a quire the In f e tion.

verti al axis is the ost of E (P). Initialization of EAII andIA are same onguration. EAII obtains wider range of E (P)than IA in Figs. 6-8. Namely, we onsider that EAII obtains
more diverse solution than IA. Be ause, it is ne essity to keep
diverse solutions for es aping lo al minimum. Thus, the resultof EAII is better than IA.
Fig. 4: The me hanism of Crossover.

3800
EAII
IA
3700
3600
3500

E(P)

3400
3300
3200
3100
3000
2900
2800
0Fig. 5: The me hanism of In f e tion.

200400600

800

1000 1200 1400 1600 1800 2000

Antibodies

Fig. 6: Distribution of solution in nug20.

V. 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 5000 times, the number of simulation
is 100 times, U is 2048, applying QAP type are 5 kinds [2℄.
error rate is dened by the following Eq. (9).

8400
EAII
IA
8200

8000

7800
E(P)

(obtain) (o ptimum)
Error rate[%℄ = 100(9)(o ptimum)
where obtain denotes obtained solution and o ptimum shows
optimum solution. When obtain value approa hes o ptimum
value, Error rate is low.
Tables I shows result of EAII and IA. IA is same the numberof t and U for omparing performan e of EAII. Infe tion rate
in EAII is 20%. We use these parameters of the ea h best
result by simulation results and average value in 100 times.
In results of Table I, we onrm that EAII obtains the better
solution than IA.

7600

7400

7200

7000
0200

400

600

800

1000 1200 1400 1600 1800 2000

Antibodies

Fig. 7: Distribution of solution in had20.

TABLE I: The result of Error rate[%℄QAP typeSize

IAEAII

tai12a12

3.17

0.86

s r1212

2.35

0.06

nug20

20

8.26

3.59

had20

20

2.62

1.07

nug30

30

14.69

9.28

Next, we investigate distribution of solutions by nug20,
had20 and nug30 (tmax = 5000; U = 2000). Figures 6-8 show
sort solutions by low ost of E (P) in antibodies. Horizontal
axis is sort solutions by low ost of E (P) in antibodies, and- 79 -Finally, we investigate evaluation value by hanging thenumber of memory ell in EAII. The number of memory ell
is hanged from 1 to 40, the number of simulation is 30 times,
ea h value uses average value by 30 times. (tmax = 5000; U =2048). Figures 9-11 show relationship between the numberof memory ell and evaluation value. Horizontal axis is thenumber of memory ell, and verti al axis is the ost of E (P).
The number of memory ell in reases, EAII does not obtain
good solution. Thus, we need to set the appropriate the numberof memory ell.

7800

7045
EAII
IA

7400

7035

7200

7030

7000

7025
E(P)

7040

E(P)

7600

6800

7020

6600

7015

6400

7010

6200

7005

6000

7000
0200

400

600

800

1000 1200 1400 1600 1800 2000

05

10

Antibodies

15202530

35

40

Number of memory cellFig. 10: Changing memory ell in had20.

2775

6950

2770

6940

2765

6930

2760

6920
E(P)

E(P)

Fig. 8: Distribution of solution in nug30.

2755

6910

2750

6900

2745

6890

2740

6880
051015202530

3540

0510

Number of memory cellFig. 9: Changing memory ell in nug20.

9, pp.586 1963.

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

Re ent advan es in arti ial immunesystems, Applied Soft Computing, 11(2), pp.1574-1587, 2011.
[7℄ K. Mori and M. Tsukiyama, Immune algorithm with sear hing diversity
and its appli ation to resour e allo ation problem, Transa tions on[6℄ D. Dasgupta, S. Yu, F. Nino,JIEE 113-C (10), 1993.

Appli ation of an immune
algorithm to multi-optimization problems, T. IEEE Japan, vol.117-C,[8℄ K. Mori , M. Tsukiyama and T Fukuda
no.5, pp.593 -598 1997.

[9℄ 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. 86.

[10℄ 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.

[11℄ Zhaxybayeva O, Doolittle W F, Lateral gene transfer, Curr. Biol. 21,Referen es

R242-246, 2011.

Assignment Problem, Management S ien e[2℄ R.E. Burkard, S.E. Karis h, F. Rendl, QAPLIB - A Quadrati

20Fig. 11: Changing memory ell in nug30.

VI. Con lusions
We proposed EAII for solving the QAP, and ompared theperforman e of EAII and IA to lead approximate solutions.
From the result, the result of EAII was better result thanIA. EAII obtained all kinds of evaluation value, and it isimportant to keep of diverse solution in solving solution of
the QAP. Thus, it was eÆ ient to use VTE based on IA in
the QAP. We expe t that apply these results to te hnologi alappli ation possibility. In future work, we would like to study
the me hanism of In f e tion in detail. We expe t to obtain abetter solution by studying me hanism of In f e tion.
[1℄ E. Lawler, The Quadrati

15

Number of memory cell

Assign-ment Problem Library, Journal of Global Optimization Volume 10,
Issue 4, pp.391-403, 1997.

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

Theory and Appli ations, Te hni al Report, TR-DCA, 1999.
[4℄ de Castro L., Von Zuben F., Arti ial Immune System: Part II - A
Survey of Appli ations, Te hni al Report, TR-DCA, 1999.

- 80 -[12℄ 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.

[13℄ T. Inoue, Y. Uwate and Y. Nishio Ee tiveness of Combination ofArti ial Immune System and Virus Theory of Evolution for QAPs,
Pro eedings of International Symposium on Nonlinear Theory and its
Appli ations (NOLTA'14), pp.160-163, 2014.