<CK? E;>JD 32

35J

THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERSTECHNICAL REPORT OF IEICE.

:LB$1%%
 †OA90 M†@H †† F !"#"I & 770–8506 F 8F '()* + 2-1
E-mail: †{t-inoue, uwate, nishio}@ee.tokushima-u.ac.jp,-./ 467=GNPQRSTUVWXYZS[\]6^_`abcdRSTUVW (EAII) ^edXfghij
klXfgmnopiPQRSTUVWGqrs^tehiuv=w^xyhiRSTUVW=zij{|NYZS[\]6vGq}~qrXhiuv=qr{~ ]hiuvXow^xyhiuv~=
i6=zij467=GN_`abc] 1 =zi 2 o (QAP) XpoNfg
^ ¡¢£¤ ¢¥^¦pNEAII ~§¨©ª§^«iuv^¬­®dj¯°±°² PQRSTUVWNYZS[\]6N2 o

Combination of Immune Algorithm and Virus Theory of Evolution forOptimization Problems
Takuya INOUE† , Yoko UWATE† , and Yoshifumi NISHIO†† Department of Electrical and Electronic Engineering, Tokushima University
2-1 Minami-Josanjima, Tokushimashi, Tokushima, 770-8506, Japan
E-mail: †{t-inoue, uwate, nishio}@ee.tokushima-u.ac.jp
Abstract This paper presents the solving method of Quadratic Assignment Problems (QAPs). This method uses
both Artificial Immune System (AIS) and Virus Theory of Evolution (VTE), and we call it Evolutionary Algorithmwith Immune and Infection (EAII). EAII has characteristics of both AIS and VTE. We consider that EAII is effective method for QAPs. Thus, we apply EAII to the QAPs and confirm that EAII obtains more effective result thanIA. Furthermore, we analyze the reason for obtaining better solution in EAII.
Key words Immune Algorithm, Virus Theory of Evolution, Quadratic Assignment Problem

1.

³´µ¶$Ù$çIA Ä½ÝÐÑÒÓÝÀEÚº»ßÔÓÈÒç?È <KÐD0 ÓßÔÓ¼!½åÈÕÞÄç!½"#ìí&¹O (Virus Theory of Evolution:VTE)[13]-[15] ÚØÖÜ'($ÈÕ"#ìí&¹Oß;Ø¾)½·¸¹º»ÚÛ*ÓÝÀF=ÐÎÆ×$çÝÀEÐ
N× Ó2+ßÔÓÕ Ç,ç!½ AIS ¼ VTE À-#.
ñ/<KÄÔÓ Evolutionary Algorithm with Immune andInfection (EAII) Ð?ÈÚD0 ÓÕEAII À+Ð QAP ÚÛ*Óïë%6>ë%AïÐHÖçPQ<K¼À+RSÐHTÈÕ
2. 2 UVWXYZ[·¸¹º»¼½¾¿ÀÁÂÃÄ¿ÅÆÇÈÁÂÉÀÊËÀ·ÌÍÈ½·ÎÏÐÑÒÓº»ÄÔÓÕÖ×ØÙÀ·¸¹º»ÚÛÖÜ½·¸ÝÐÑÒÓÞ¼ßàáÄÔÓ¼âãÇÜÖÓÕä
åæçÊËÀ·¸¹º» [1]çèéêëìíîïº» [2]çðñ
òóñôº» [3]ç2 õö÷øÜº» (Quadratic AssignmentProblem: QAP) [4],[5] ùßúûãÇÓÕüýþÿ%í  (Artificial Immune System: AIS) [6] ¼½@Jß;Øþÿ%í Ð4Ú$Èïë%í ÄÔÓÕAIS ½·¸¹º»çëïGâçñ ý3 À
½ Ò¼ ÓM! L [7]-[9] Ä1ß2ÄÔÓÕAIS Ðì¹$Èþÿì (Immune Algorithm: IA)
2 õ ö ÷ ø Ü º » (Quadratic Assignment Problem:½9B7Ð? ÓÞ¼ÄÝÐC: ÓìÄÔ÷ç QAP)[4],[5] ¼½ (\ ÊËß 2 õ ] ¼ Óö÷øÜº»ÄÔ·¸¹º»ÐÝ×<K¼$ÜI×85ÆÇÜÖÓ [10]-[12]Õ ÓÕQAP À¿Å½ n ^_Ð;Ø 2 ØÀH` (H` F ¼H`—1—D) ßMåãÇÈ¼$ç] (1) ÚÛ*Ó E(P ) À·ÎÏÐÑÒÓº»ÄÔÓÕE(P ) =4 X
4X

fij dp(i)p(j)i=1 j=1E(P ) =n XnX

fij dp(i)p(j)(1)

i=1 j=1

0 5= 

 10

5

1006

0


3 
  21
4   30

2



2130

12044


11 


9 44 06 0
H` F À i Ùã j ÍÄÀ_çd½H` D À i Ù
12 11 90
2 3 4 0
ã j ÍÄÀ_Ð< Õ= 1524(4)QAP ½M! º»Ú1Ä$ÓÕ0ä¼$Üçn ^À;@Ð À ÚGC ÓÀÙÐ7ÒÓ>ÂÚÛÖÜçF Ð Ç? (1) À   Ö_Ë n À>ÂÄ½çAÂËßÇÀ;@ÀJNçD Ð ÇÇ¼;@À5¼$ÜçG  ÖÀÄÚ·¸ÝÐÑÒÓÞ¼ß2ÄÔÓÕ$Ù$ç
Cí ÄÔÓ E(P ) À·ÎÏÐÑÒÓº»¼$Ü QAP Ðä _Ë n ß2 ÓÚ=ÖçAÂËßH\Ú2
åÓÞ¼ßÄ$ÓÕÞÞÄç? (1) À  4 ØÀ;@Ð 4 Ø ÓÕ Ç,ç·¸ÝÐÑÒÓÞ¼ßá$× ÓÕ_Ë n ÀÏÀ6ÚGC Ó¼$ÀGCí ÐåÓÕ ÇÇÀ;@ ßÌ$Ö>ÂÚÛÖÜçÜÀAÂÐÑÒÜ·¸ÝÐÑÀJN¼5ß? (2) ¼? (3) À¼$çF ¼ D ½ ÇÇ ÒÓÞ¼½8\ÚI2ÄÔÓÀÄçK85Ä½7âì] (2),(3) ¼ ÓÕP (f 2, f 1, f 4, f 3) Ð (d1, d2, d3, d4) ¼ À0ÄÔÓ Evolutionary Algorithm with Immune
GC Ó¼$ÀGCí E(P ) ½] (4) Ú< ÚÄ and Infection (EAII) ÐÖÜ QAP ÀÝÀF=ÐHTÈÕ
$ÓÕ
3. % !"#O&'(3ÚÛÖÜç@JÀ&¹½)*Ú+$Ü¸1Eß9Ö
, -×@$.÷ç¸1EßDÖ, õ(/Ú.÷Ú×× ÓÕ$Üç¸1Eß9Ö1E:, FG ÓPQÚRÍÇÓÀÄçõ(/Ú½ ÷¸1Eß9Ö1E:ßS@ÆÇÓTUß9×ÓÕ ÀÈÒç(/F/ÐV÷W Þ¼Ä1E:½ ÷)*Ú
¸1$ÜÖ$ç@J½&¹ ÓÕ$Ù$ ßãç&¹Ú½Ë×À(/F/ß¼ ÓÀÄç-×Àß¼ ÓÕ0Xç"#ìí&¹O [13] ¼½"#ìíßYZ ÓÞ¼Ä&
1 4
LB.
¹ Ó[OÄÔÓÕ"#ìíßYZ ÓÞ¼Ä1E\]ßÌ$×^¹ ÓÞ¼¼ ÓÀÄçË Ö(/F/ÄÌI 1E:
À^¹ß2ÄÔÓÕ=TÜçYZÆÓ"#ìíß)*Ú+
0 5 10 2$Ü¸1EÀ9Ö\]Ð;TÜÖÓÀ ãæç_`À&¹ ÷ 5 0 6 3 abcÚd×¸1EÀ9Ö1E:e¼&¹Ä$ÓÞ¼ßfgÄ
F =
(2)

 10 6 0 4 $ÓÕ
2 3 4 0fij ½p(i)p(j)211144 21D= 1101212030

930 
9 442



04 J.

4. Evolutionary Algorithm with Immune
and Infection (EAII)(3)0

3D0<KÄÔÓ EAII ÀNÇÐ Step Ähi ÓÕStep2 Ùã@¿$È9BÀ?éË t j*V÷W$ÜçÝÀC:ÐHÕÍÈç? 4 Ú EAII Àkëlmë Ð< Õ
Step1 nopqrf@¿¼$ÜsïtÚuv$ÈwxÐ U ^y ÓÕÞÇã ÇÇÀwxÐ9B¼¿Å ÓÕ
Step2 z{|}~
9B7 ÇÇÀRSÏ½] (5) Ä¿Å ÓÕ
Step5 ÍÄ½

4 .

max

φv =

1E(v)

(5)

ÇÇÀ9B v Ú+ Óí ÄÔ÷çφv ½íßDÖ, 9ÖÏ¼ ÓÕ
9BÀE9BÀE½9BÚÛ*Ó+Ðy ÓÕ] (6) ½E(v) ½—2— 4 EAII % !!.
9B vçw ÚÛ*Ó9BÀEÐI$ÜÖÓÕ1
Ψvw =1 + HvwStep3J2

¹Ä½ Step2 ÄRS$È9BÐ5:K¼ T :K
Ú¹ÆÓ6ÐHÕ
Step3 À(6)5:K
9B vçw ÚÛ*Ó9Bß;Ø\]À+ÐI Ï
Step2 ÄÑÒÈ9BÀGE Θ ÀÏß$$ÖÏ T Ð1åÈÄÔÓÕa$açH = 0 ÄÔÇæ9B vçw ½×F \]¼$Ú5:K8 µ e¼¹ ÓÕa$aç@¿$È5:Ð;$çH ÀÏßÌ$× Ó¼9B vçw ½ ÷0 TÈ\]Ð;ØÕ Ç,çΨ ÀÏßÌ$Ö, 9B vçw À;Ø\ KËÀÃ ÚC$ÜÖ Ö>Âç5:K8 µ ½5:Km e¼¹ ÓÕ$Ù$ç@¿$È5:KËÀÃ ÚC$Ü]½$ÜÖÓ¼ÖåÓÕ
ÖÓ>Âç5:K8 µ ¼5:K m ¼À9BÀGE Ψ9BÀGE9BÀGE½] (7)ç(8) Ä¿Å ÓÕ(U ½9BÀ^ËÐy Ð ÓÕ·a9BÀGE Ψ ßÌ$ÖÏÀRSÏ φ¼5:K8 µ ÀRSÏ µ Ð Üç5:K8 µ ÀR ÓÕ)SÏ µ ÀÌ$*Çæç5:K8 µ ¼·a9BÀGE ΨßÌ$ÖÏÀ5:K m Ð Ç åÓÕ9BÀGE¼RSÏ
1 X
Θ =π(7)UÐÖÜ5:KeÀ¹ÐHÞ¼Äç5:KÀ-M+Ð<TÜÖÓÕ(>Hvw ½2v

vw

vw

vw

µm

µm

mmax

µm

Uv

vw

w=1πvw =1 (Ψvw = T1 )
0 (Ψvw < T1 )(8)ÇÇÀ9BÀE Ψvw ß$$ÖÏ T1 Ð1å
È¼$ÚÀH ÓÕ Ç,ç9BÀGE Θv ½&3À9B¼À+Ðy ÓÕ=TÜçΘv ÀÏßÌ$× Ó¼
BÀ9B¼$ÜÓÞ¼ÐI ÕK85Ä½$$ÖÏ T1 Ð@¿ ÓÞ¼ÄçÎÆ +½$ÜÖ Ö¼ $ÜÖ
ÓÕ9BÀGEßÎÆ +Ð;ØÞ¼ÄÏÚH$ ÖÚ@¿$ÜÖÓÕ
Ψvw ½

: K
5:KeÀ¹ß=Nç9B v Ð T :K t Ú¹ÆÓ6ÚØÖÜHÕ9B v ¼ T :K t ¼ÀE Ψ ÐÓÕE Ψ ÀÏß$$ÖÏ T Ð1åÈ¼$ç9B v Ð T:K t Ú¹ÆÚ>LÆÓÕÞÀ6ß;Øy½ ×È9BÐ>LÆÜç9B7À+ßÌ$× ÓÀÐößÔÓÕa$a9Bß>L$È>ÂçsïtÚ@@$È
9BÐ@$çT :K t Ú¹ÆÜç?$Ö9BÐ ÓÕTvtvt3—3—

Step4z{|};@}B?$M

I 1 Ú EAII ¼ IA À Error rate ¼1À%6>ë

@Q¼>L%Aï72Ð< ÕÖÈ QAP ½ 5  [5]çÏ½ 10 éÀ
T :K t Ú¹$È9B7Ú+$Üç ÇÇÀ9BÀRSÏçYZTU½ 20% ¼$ÈÕIA À t ¼ U ÀÏ½ EAII
Ï φ Ð ÓÕÃ0HRSÏÐ;Ø T :K t ½@Q$ç ¼ù$ÖÏÐÖÈÕ? 1 À Error rate À72ÚÛÖÜ½çÇ3À T :K t ½>LÆÓÕEAII ½ IA ÷aNÖ72ßFãÇÓÞ¼ÐTG$ÈÕ$Ù
?È 9B7ÀS@$ç1ÚÛÖÜ½$a EAII ÀXßÇÜÖÓ¼@Q$È T :K t Ú+$ÜçF:ÐÖÜç?È 9BÐ@ å ÖÕ¾Ú had20 ÚÛÖÜ½ EAII ÀXß1ÀÏßÌ@ ÓÕF:¼½ 2 ØÀ9BÀ\]ÐAÂÜç?È 9 IÚÌ$× TÜ$ÍTÈÕQAP ÀÚ TÜ½YZìBÐ@@ Ó6ÄÔÓÕF:ÚØÖÜ½? 5 Ú< ÕF:Ú ÐA ÓÞ¼ÄÌ$×1ß2$Ü$Í2
TÜ@@ÆÇÈ9BÐ>L$È9BÀËj* ÓÕ+ßÔÓÀÄç1ÀÌÐåÓÞ¼ßÄÔÓ¼
Step5 4åÓÕ5:KÙãsïtÚuç98¼ ÓÕ À98Ð9B
 1 EAII  IA  "!#&'(7Ú? 6 À Ú98\]À0IÐYZÆÓÕ98\]À0QAP Size Error rate[%] )*+, [s]IÐYZÆÓÞ¼Ä9B7À\]À0I½^¹ ÓÕÞÀ0typen
IAEAII IA EAIIOÀNÇÐYZì¼ÕK85Ä½98ÀËÐ^
tai12a 12
6.15
1.05 217204¹ÆÜ%6>ë%AïÐHTÈÕÍÈçYZEÂÖÐ^
scr12122.58
0.00 201200ÆÓÈÒÚYZTUÐ¿Å$ÈÕ
nug20 20
9.51
6.85 327 340
max

t

had20

20

2.62

1.07

338

456

nug30

30

14.23 12.42

563

522

õÚçnug30 ÚÛ*Ó5:KËÐ^¹ÆÈ¼$À1¼í E(P ) À^¹À%6>ë%AïHTÈÕ? 7 ½5
:KË¼1ÀÊ-ç? 8 ½5:KË¼í E(P )ÀÊ-Ð< Õ5:KËÐ^¹ÆÓÞ¼ÄçYZìÄÖÓ98ÀËa^¹ ÓÕ? 7 ÷ç5:KËÐ2ÆÓÞ¼Ä1½2 ÓÕ0Xç? 8 ÷5:KËÐ2ÆÓÞ¼Äí E(P ) ÀÏßÎÆ× ã ÙTÈÕE(P ) ÀÏÚæãØ$ß.ãÇÈßç5:KËß 15 /Ä·aNÖ72¼ TÈÕ? 7ç8 À72Ùã1¼ E(P ) ÀÏ ÷ç5:KËÐ2ÆÜa$aNÖ72ßFãÇÓ*Ä½ ÖÕ5:KËÐ¸5 ÏÚ@¿ ÓÞ¼ß
ÄÔÓ¼åÓÕ 5  .

560
EAII5556  %

 .

550

!
D0<KÄÔÓ EAII ¼PQ<KÄÔÓ IA ¼À+Ð 3ÓÈÒÚçJËÀ QAP Ú+$Üïë%6>ë%AïÐHTÈÕ9BË U Ð 1024ç9BÀ?éË t Ð 4000ç
%6>ë%AïéËÐ 10 éç5:KË½ 20 ¼$ÈÕÍÈç
·¸Ý¼ÀUÄÔÓ Error rate Ð] (9) Ä¿Å$ÈÕ
5.

max

Error rate[%] =Error rate ½(FãÇÈÝ) − (·¸Ý) × 100(·¸Ý)

time[s]545

540535530525

520
020406080100

Number of memory cell 7 nug30 9<=>CDEKGLNP4 QR.

(9)FãÇÈÝß·¸ÝÚ6Ö, ÎÆ Ï¼ ÓÕ
ãæç·¸ÝÐFÈÞ¼Ðy ÓÕError rate ß 0%—4—

[12] V. Cutello, G. Nicosia, M. Pavone, J. Timmis, “An Immune Algorithm for Protein Structure Prediction on Lattice
Models,” IEEE Transactions on Evolutionary Computation,
vol.11, no.1, pp.101-117, 2007. 86.
[13] N. Nakayama, A. Kanasugi and K. Kondo, “An Evolutionary Algorithm Based on the Virus Theory of Evolution,”Transactions of Information Processing Society of Japan,
Vol.40, No.5 p2346-2355, 1999.

7100
EAII7050

E(P)

7000

6950

6900

6850

6800
020406080100

Number of memory cell

 8 nug30 9<=>CDEKG%  E(P ) QR.
6.

³ $ K85Ä½çAIS ¼ VTE À-#.ñ/<KÄÔÓ EAIIÐÐ?ÈÚD0$ÈÕ·¸¹º»À 1 ØÄÔÓ QAP ÚÛ*Óïë%6>ë%AïÚÛÖÜçD0<KÄÔÓ EAII
ÀM8+ßTGÄ$ÈÕ:À2»¼$Ü½çFãÇÓ72ÀsëÀ0Q+
NÖ72ßFãÇÈÀÙÀ>:DÐHTÜÖ$ÈÖÕÍ
ÈçK85ÄÖÈ QAP ÷a ÷ó#ÀÌ$Ö QAP Ú+$ÜçNÖ72ßFãÇÓ ÚìÀN$ÜÖ$ÈÖÕJ[1] M.A. Potter, K.A De Jong, “ A Cooperative Coevolutionary
Approach to Function Optimization,” Proceedings of the International Conference on Evolutionary Computation. The
Third Conference on Parallel Problem Solving from Nature:Parallel Problem Solving from Nature, p.249-257, 1994.
[2] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy-Kan and
D. B. Shmoys, editors. “The Traveling Salesman Problem,”Wiley, 1985.
[3] D. Pisinger, “Algorithms for Knapsack Problems,” PhD
thesis, University of Copenhagen, Dept. of Computer Science, 1995.
[4] E. Lawler, “The Quadratic Assignment Problem,” Management Science 9, pp.586 1963.
[5] R.E. Burkard, S.E. Karisch, F. Rendl, “QAPLIB - A
Quadratic Assignment Problem Library,” Journal of GlobalOptimization Volume 10, Issue 4, pp.391-403, 1997.
[6] de Castro L., Von Zuben F., “Artificial Immune System:
Part I - Basic Theory and Applications,” Technical Report,TR-DCA, 1999.
[7] de Castro L., Von Zuben F., “Artificial Immune System:
Part II - A Survey of Applications,” Technical Report, TRDCA, 1999.
[8] S. Garrett, “How Do We Evaluate Artificial Immune Systems?,” Evolutionary Computation, vol.13, no.2, pp.145178, 2005.
[9] D. Dasgupta, S. Yu, F. Nino, “Recent advances in artificial immune systems,” Applied Soft Computing, 11(2),pp.1574-1587, 2011.
[10] K. Mori and M. Tsukiyama, “Immune algorithm withsearching diversity and its application to resource allocation problem,” Transactions on JIEE 113-C (10), 1993.
[11] K. Mori , M. Tsukiyama and T Fukuda “Application ofan immune algorithm to multi-optimization problems,” T.
IEEE Japan, vol.117-C, no.5, pp.593 -598 1997.

—5—