TELKOM
NIKA
, Vol.11, No
.1, Janua
ry 2013, pp. 123
~12
9
ISSN: 2302-4
046
123
Re
cei
v
ed Se
ptem
ber 28, 2012; Revi
se
d No
vem
ber
22, 2012; Accepted Novem
ber 30, 20
12
Estimation of Distribution Immune Genetic Algorithm
and Convergence Analysis
LIU Zhen*
1
, HU Yun
-
an
1
, SHI Jian-guo
2
1
Dept. of Control Eng
i
ne
eri
ng,
Naval Aer
ona
utic
al a
nd Astrona
utical U
n
iv
ersit
y
, Ya
ntai, Chin
a
2
Dept. of No.7, Naval Aer
ona
utical a
nd
Astrona
utical U
n
iv
ersit
y
, Ya
ntai, Chin
a
*corres
pon
di
ng
author, e-mai
l
: h
y
lz
10
08@
12
6.
com, h
y
a50
7
1
@sin
a.com, cherra
ppl
e@1
2
6.com
A
b
st
r
a
ct
In the traditio
n
a
l i
m
mu
ne g
e
netic al
gorit
h
m
, cr
ossover an
d mutation c
a
n disru
p
t the super
ior
chro
mos
o
me,
so make th
e
alg
o
rith
m took
a lo
ng ti
me t
o
conv
erge t
o
the best so
lu
tion. T
he w
a
y
of
crossover and
mutati
on bas
e
d
on margi
n
a
l
prod
uct
mod
e
l w
h
ich
can mak
e
the
a
l
g
o
rith
m
conver
ge quic
k
ly
w
a
s propos
ed
in or
der to
avo
i
d the
disru
p
tio
n
of t
he s
u
p
e
ri
or chro
moso
me. T
he ps
eud
o
para
lle
l ev
oluti
o
n
mec
h
a
n
is
m w
a
s also
brou
g
h
t into the pr
opos
ed a
l
gor
ithm
in or
der to enh
anc
e th
e divers
ity of th
e
pop
ulati
on. T
h
e conv
erg
ence
character
of t
he a
l
g
o
rith
m is
ana
ly
z
e
d. T
h
e
mode
l the
o
re
m
of esti
mati
o
n
o
f
distrib
u
tion i
m
mu
ne g
e
n
e
tic alg
o
rith
m w
a
s give
n and th
e conver
genc
e rule w
a
s also
give
n. Simulati
o
n
results of sev
e
ral be
nch
m
ark functio
n
s show
that the pro
pos
ed al
gor
ith
m
is
super
ior tha
n
g
enetic
alg
o
rith
m
immune
gen
eti
c
algor
ith
m
. So the propos
ed
alg
o
rith
m is cor
r
ect and feasi
b
l
e
.
Key
w
ords
: i
m
m
une ge
n
e
tic al
gorith
m
, estim
a
tio
n
of di
strib
u
tion, m
a
rgin
al pro
d
u
c
t m
odel,
ecten
ded co
m
pact
Copyrig
h
t
©
2013
Univer
sitas Ahmad
Dahlan. All rights res
e
rv
ed.
1. Introduc
tion
Artificial imm
une sy
stem
is a co
mput
ational intelli
gen
ce pa
radi
gm inspi
r
e
d
by the
biologi
cal im
mune sy
ste
m
, and has
been ap
plied
su
cce
s
sfully to a variety of optimization
probl
em
s. Immune g
eneti
c
algorith
m
(I
GA) is
a nov
el bio-i
mmun
e
evolution
a
ry algorithm,
whi
c
h
have gaine
d more an
d mo
re attention d
ue to t
heir excelle
nt adapt
ation and ro
b
u
stne
ss. In th
e
past
seve
ral
years,
som
e
pe
ople
ha
ve propo
se
d
many
kin
d
s of imp
r
ove
d
artifici
al im
mune
algorith
m
s.
In the widely
studie
d
imm
une alg
o
rith
ms, many
re
sults
are
abo
ut the clon
al
sele
ction,
Wu p
r
o
pose
s
an
ada
ptive qua
ntum i
mmune
cl
o
n
a
l
algo
rithm and
the co
n
v
ergen
ce of th
e
prop
osed al
gorithm i
s
proved the
o
r
etically
[1]. Liu introdu
ce
s the biol
ogic info
rma
t
ion
mech
ani
sm i
n
to the immu
ne algo
rithm
and the biol
o
g
ic informatio
n mechani
sm
is employed
to
improve
information inte
ra
ction
and
a
c
cele
rate
the
spe
ed
of ev
olution [2]. A
novel
ada
ptive
immune
algo
rithm, whi
c
h i
s
ba
se
d on
immune
dan
g
e
r the
o
ry, wa
s p
r
op
osed b
y
Xu to emul
ate
the entire im
mune m
e
cha
n
ism
s
a
nd t
o
enh
an
ce t
he pe
rforma
nce fo
r
com
p
lex multimo
dal
probl
em
s [3]. Che
n
devel
op a hyb
r
id i
mmune
multi-obje
c
tive opt
imization
alg
o
rithm b
a
sed
on
clon
al sele
ction pri
n
ci
ple,
a hybrid
m
u
tation op
era
t
or is
pro
p
o
s
ed with th
e
combi
nation
of
Gau
ssi
an an
d polynomial
mutations [4].
Ali pres
e
n
ts
a new hyb
r
id
optimizatio
n approa
ch ba
sed
on imm
une algorithm
and
hill cli
m
bing l
o
cal
sear
ch
algorithm in
order to enhance the running
effic
i
enc
y
[5].
IGA has be
en p
r
op
osed
and i
s
ch
ara
c
teri
ze
d
by rapi
d co
nverge
nce a
nd hig
h
conve
r
ge
nce
pre
c
isi
on.
Evolution pa
ramete
rs
an
d evolution
approa
ch
sh
ould b
e
sele
cted
prop
erly
so a
s
to contrib
u
te po
sitively to the
optimization pe
rform
a
nce
of IGA. Howeve
r, in m
o
st
of the existi
ng IGAs, th
e cro
s
sover and
muta
ti
on al
ways d
i
sru
p
t the
superi
o
r
patte
rn of
chromo
som
e
, then
ca
nno
t guarantee
the gl
obal
optimum.
So in o
r
d
e
r to p
r
omote
th
e
evolutiona
ry perfo
rma
n
ce of the I
G
A, ex
plora
t
ion and
e
x
ploitation can be
provided
simultan
eou
sl
y when the crossover a
nd
mutation ca
n be set corre
c
t.
Estimation of
distri
bution
algorith
m
s
(E
DA)
h
a
ve be
en p
r
opo
se
d
as a
n
exten
s
ion
of
geneti
c
alg
o
ri
thms. EDA
s
u
s
e
s
p
r
ob
ability distrib
u
tions derived
from
the fun
c
tion t
o
be o
p
timize
d
Evaluation Warning : The document was created with Spire.PDF for Python.
TEL
K
E
to g
e
both
esti
m
gene
repla
prob
a
solut
i
com
p
whi
c
h
the c
after
prop
o
idea
(EDI
G
intro
d
Sec
t
i
the c
o
2. E
s
2.1
.
P
the
c
solut
i
can
d
extre
conv
e
popu
2.2.
C
opti
m
muta
gro
w
the c
r
MP
M
cro
s
s
linka
g
pro
c
e
indivi
sha
p
e
MP
M
cro
s
s
K
OM
NIKA
E
stim
ation o
e
ne
rate sear
c
ca
se
s a
p
o
m
ate a
se
arc
h
ti
c al
gori
t
h
m
ce
s t
r
ad
it
io
n
a
bili
stic mod
i
on
s
.
The
E
C
p
one
nts,
(1
)
h
va
riabl
es
a
hr
o
m
os
ome
iteration
s
.
T
o
sed a n
e
w
q
of EDA
S
i
s
G
A) i
s
propo
The rem
d
uc
ed
in
s
e
c
on 4 p
r
e
s
en
o
nc
lus
i
on
s
.
s
tim
a
tio
n
of
P
opulation
I
Populati
o
c
onve
r
ge
nce
i
on is av
aila
b
idate sol
u
ti
o
mum, so
i
n
e
rge
n
c
e
sp
e
lation [8].
C
ross
o
v
e
r
a
The tra
d
m
um, an
d t
h
tion, the k
e
y
increa
si
ng i
r
oss
o
ver a
n
d
Definitio
n
M
s
can
b
e
v
i
s
ove
r
is
nam
e
The MP
M
g
e b
e
tween
e
du
re
can
b
e
dual
s ca
n e
x
A
s sh
ow
n
e
re
present
s
M
2, the al
lele
s
o
v
er
p
r
oc
es
f Distri
butio
n
c
h p
o
ints i
n
s
o
p
u
lation of
h
di
strib
u
tio
n
m
(E
CGA)
is
n
al variati
on
el of
pro
m
is
C
GA use
s
t
h
a partitio
n
o
a
re linked, a
n
can be
di
vi
d
T
an intro
d
u
c
q
ua
ntum-i
ns
s
bro
ught
in
t
sed.
ai
nd
er of t
h
c
tion 2, wh
ile
t
s
the sim
u
l
a
Distribu
tio
n
I
nitializ
ati
o
n
o
n ini
t
ializati
o
spee
d a
nd
b
le, then
ra
n
o
ns (initial
p
o
n
or
d
e
r
to
e
ed, the p
a
a
nd Mutatio
n
d
itional cros
s
h
e better pa
y
that th
e
e
v
n the next it
e
d
mutation b
a
n
1 The allel
e
i
e
w
ed
as a
e
d a
s
M
P
M
c
M
cross
o
ve
r
the allel
e
c
a
e
de
scr
ie
d a
s
x
cha
nge t
he
n
in
the Fig
s
the differen
5 an
d 6
ca
n
s
can b
e
s
h
o
I
S
n
I
m
m
une G
e
s
tead of c
r
o
s
point
s i
s
u
s
n
or to be
u
s
e
a
cl
as
s
of
E
op
erato
r
s
o
ing soluti
on
s
h
e m
a
rgi
n
al
o
ver the v
a
r
n
d (2) a
pro
d
ed into se
v
e
c
e
s
the qu
a
n
pi
red e
s
tim
a
t
o IGA, and
h
e pa
per i
s
se
ction 3
g
i
a
t
i
on
s re
sul
t
s
n
Immune
G
n
o
n
is
a c
r
uc
i
a
also the
q
u
n
dom
initiali
z
o
pul
ation
)
.
B
enh
an
ce t
h
a
p
e
r
ad
op
t
s
n
Base
d on
s
over and
m
ttern in the
v
olutiona
ry
a
e
rations
. So
a
se
d on M
P
M
e
in the chro
m
whole. Th
e
c
ro
ssover.
r
ca
n
guara
a
n n
o
t brea
k
s
: rand
omly
sel
e
ct
e
d
M
P
1, the
chro
m
t MPMs
, the
n
be
viewe
d
o
wn as
Figu
r
Figure 1. S
S
SN: 2302-4
0
e
ne
tic Algori
t
s
sover
and
m
s
ed
an
d
poi
n
e
d fo
r
cro
s
s
o
E
DAs whi
c
h
o
f genetic
a
s
and
sam
p
l
produ
ct m
o
d
r
iabl
es, defi
n
bability di
str
e
ral MPMs
a
n
tum-inspir
e
tion of distri
b
es
timation
o
r
g
ani
zed
a
i
ves
the con
v
s
for the be
n
G
enetic Ag
o
r
a
l t
a
sk i
n
ev
o
u
ality of the
z
ation is the
B
ut ran
dom
h
e dive
rsity
s
the opp
o
s
MPM
m
utation al
w
ch
rom
o
s
o
m
a
lgorithm ca
the better
p
M
is prop
os
e
m
o
s
om
e ca
n
cr
os
sover
c
ntee t
he b
e
k
in the pro
c
sele
ct
t
w
o
i
n
P
M th
r
o
u
gh t
m
o
s
om
e is
gene 1, 3 a
as MPM
3
.
W
r
e 1.
ketch map
o
0
46
t
hm
and Co
n
m
utation a
s
d
n
ts
with
go
o
o
ver an
d m
u
is p
r
op
ose
d
a
nd evolutio
n
ing the
mo
d
d
el (MPM),
w
n
ing whi
c
h
v
ibution over
a
nd the supe
e
d evolution
a
b
ution algo
ri
t
of distri
buti
o
a
s follows
.
v
ergen
ce p
r
o
n
chma
r
k
f
u
n
c
r
ithm
o
lutiona
ry al
g
final s
o
lutio
n
most
comm
o
initialization
of the po
p
s
itio
n-
b
a
s
ed
w
ays l
ead
t
m
e ca
n be
b
n converge
p
attern sh
oul
d
e
d.
n
b
e
divided
c
an
pe
rform
e
tter individ
u
c
ess
o
f
th
e
n
dividual
s fr
o
h
e cro
s
sov
e
and
r
nd 4 form th
e
W
he
n we ch
o
o
f MPM
cros
s
i
q
j
q
n
verg
ence A
n
d
one by ge
n
o
dne
ss are
u
t
a
tion. The
e
d
by Ha
rik [
6
n
ary alg
o
rit
h
d
el to g
ene
r
a
w
hi
ch can b
e
ariabl
es are
each p
a
rtiti
o
rior in
dividu
a
a
ry algorith
m
t
hm [7], in th
o
n immune
T
he basic
i
o
of of the p
r
c
tions
. Las
t
l
y
g
orithm
s be
c
n
. If no info
r
o
nly used m
can l
ead
p
p
ulation, an
learnin
g
t
o
t
he
alg
o
rith
m
b
rea
k
thr
o
u
g
is
that the
b
d
be res
e
rv
e
into sever
a
l
according
t
u
a
l
s
gr
ow i
n
MPM cross
o
o
m the po
pu
r ope
rator
.
r
e
s
pe
ctively,
e
MPM1, th
e
o
ose the M
P
s
ov
er
n
alysi
s
(LI
U
etic algo
rith
m
selec
t
ed eit
h
e
xtende
d co
m
6
]. The algo
r
h
ms by buil
d
a
te new can
d
e
divided in
t
i
ndep
ende
n
o
n
.
S
o
i
n
t
h
e
a
ls
c
a
n
b
e
r
e
m
in
to
ED
A
s
e pape
r,
the
geneti
c
alg
o
de
a of E
D
I
G
r
op
ose
d
alg
o
y
,
sect
ion 5
c
au
se it
ca
n
r
mation abo
ethod to
ge
n
p
opu
la
tio
n
t
o
d a
c
c
e
ler
a
t
o
generate
m
trap into
g
h cr
os
sov
e
b
etter patte
r
e
. So in the
p
MPMs, and
t
o the
MPM
n
crea
sing a
n
o
ver
.
The
d
e
la
tion and t
h
and the di
f
e
gene 2 for
m
P
M1 ra
ndom
124
Zhen
)
m
s.
I
n
h
er
to
m
pa
ct
r
ithms
d
in
g
a
d
i
date
t
o two
n
t and
e
IG
A
,
e
ser
v
e
s
, and
basic
o
rith
m
G
A is
o
rith
m.
dr
aws
affec
t
u
t
t
he
n
erate
o
lo
ca
l
e
t
he
initial
local
e
r and
r
n can
p
aper,
every
s, t
he
n
d the
e
t
a
iled
h
e t
w
o
f
ferent
m
s the
l
y,
the
Evaluation Warning : The document was created with Spire.PDF for Python.
125
ISSN: 2302-4
046
TELKOM
NIKA
Vol. 11, No
. 1, Janua
ry 2013 : 123 – 1
2
9
The po
pulatio
n evolves the
optimum sl
o
w
ly
and
can
often meet the local extre
m
e wh
en
the allele tha
t
choo
se
s to mutated ra
nd
omly,
so the pape
r propo
sed a ne
w kin
d
of mutation
based on MP
M.
Definition
2 Choo
se a
MPM from the
p
opulatio
n indi
viduals, a
nd t
he allel
e
in th
e ch
osen
MPM can be
mutated according to the m
u
tation probability
.
In the runnin
g
pro
c
ess of th
e ev
olutiona
ry algorithm, if the ev
olution
a
ry algo
rithm alway
s
adopt
s the same mutatio
n
prob
ability, the c
onverg
ence of the EA will slow and the bet
ter
individual
s
cannot
always re
se
rve in
the n
e
xt gen
eration,
so
if the mut
a
tion proba
bility ca
n
change adaptively acco
rdi
ng to the evolution
condition, so the m
u
tation probability of the
individual
s ca
n be set a
s
:
(1)
In the eq
uati
on (1),
and
is the
maxi
mum a
nd mi
nimum fitne
s
s at the
iteration
, and
is the predef
ined con
s
tant
.
2.3. Immune
Selection
In orde
r to p
r
omote th
e d
i
versity of the ev
olution p
opulatio
n, an
d make the
sele
ction
mech
ani
sm d
i
rect
t
he
cor
r
e
ct
se
ar
ch,
t
he f
i
t
nes
s sh
aring i
s
brou
ght into the EDIGA. Fitness
sha
r
ing
me
ch
anism
ca
n av
oid the lo
cal
conve
r
ge
nce
and hi
gh
sele
ction p
r
e
s
sure. For the t
w
o
antibody
and
, the sharing
function
can
be define
d
as:
(2)
In the equati
on (2
),
is th
e sha
r
in
g ra
d
i
us,
is the distan
ce bet
we
en the
and
the
. When th
e probl
em scale is
, and the individual
s
can b
e
define
d
as:
(3)
and
a
r
e the
fitness befo
r
e
and
after fitn
ess
sha
r
ing
mech
ani
sm. I
n
orde
r to
make
su
re th
at the popul
a
t
ion can
ke
ep
diversit
y, the
sele
ction p
r
o
bability for the
individual
c
an be s
e
t as [9]:
(4)
In the equation (4),
and
are the adju
s
tive param
eter and a
r
e al
l consta
nt, they
can b
e
set as 0.8 and 1.2 resp
ectively,
,
represents t
he numb
e
r of
individuals
whos
e fitnes
s is
between
,
.
2.4. The Indiv
i
duals Migration Stra
teg
y
In orde
r to promote the diversity of the popul
ation, the whole p
opu
lation can b
e
divided
into two
sub
popul
ation in
depe
ndently
[10], t
he two
sub
popul
ation can exch
ange in
dividu
als
m
p
th
i
ma
x
max
m
i
n
()
()
()
()
i
mm
f
tf
t
pp
f
tf
t
ma
x
()
f
t
min
()
f
t
t
m
p
()
i
at
()
j
at
2
1,
()
0,
ij
ij
s
ij
s
d
d
Sh
d
othe
rwise
s
ij
d
th
i
th
j
n
()
i
at
1
()
(
)
(
)
n
ii
i
j
j
f
tf
t
S
h
d
()
i
f
t
()
i
f
t
th
i
((
)
/
)
1
()
1
()
(
1
)
()
i
Ct
v
i
i
N
j
j
ft
pt
e
N
ft
v
()
()
i
i
ht
Ct
n
()
i
ht
[(
)
,
(
)
(
)
]
ii
f
tf
t
f
t
max
m
i
n
()
()
()
3
ft
f
t
f
t
()
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
126
Estim
a
tion of
Distri
bution I
m
m
une Gene
tic Algor
ithm
and Con
v
erg
ence Analysi
s
(LI
U
Zhen
)
betwe
en the
m
.
(5)
In the equ
ation (5),
,
and
are the
best fitne
ss of the two
sub
pop
ulatio
n. In every iteration, the mi
grat
ion m
e
tho
d
can b
e
dete
r
mine
d as foll
ows:
(1) if
, then t
he in
dividual
s ca
n mi
grate
from the
su
b
popul
ation to
the
sub
pop
ulatio
n, else the in
dividual
s will migr
ate to the
subpo
pulati
on, if
, do nothing;
(2) if
, then the scale of the
migrat
ion i
s
,
is the popul
ation scale.
2.5
.
The Pro
cess o
f
the
Proposed E
D
IGA
Above all, after the detaile
d
descri
p
tion
of the propo
sed alg
o
rithm
,
the proce
ss of the
prop
osed alg
o
rithm can be
summa
rized
as:
Step1 Initialize the p
a
ra
meter of the
algorithm
s,
su
ch a
s
the
probl
em scal
e
, the
chromo
som
e
length
et al,
then Initialize chromo
som
e
according to
se
ction 2.1;
Step 2 Perform the MP
M cro
s
sover and the MPM mutation operatio
n, cro
s
sove
r
prob
abltiy ca
n be set a
s
0.7 and the mut
a
tion pro
babil
i
ty can be set
accordi
ng to equatio
n (1
);
Step 3 Calcul
ate the ap
pet
ency b
e
twe
e
n
the antib
od
y and antig
e
n
, the fitness can
got
according to
equatio
n (3
), and the sele
ction pr
ob
abilit
y can be got
according to
equatio
n (4
);
Step 4 If the termin
ation
cri
t
erion i
s
satisfied, this p
r
o
c
edure e
n
d
s
; otherwise, se
t t = t +
1, and retu
rn
to Step 2.
3. Conv
ergence of the Pr
oposed
Algo
rithm
Theo
rem
1 In
the EDIGA, t
he p
r
op
osed
algorith
m
ad
o
p
ts
cro
s
sover and m
u
tation
based
on MPM,
the
n
mod
e
l d
e
fin
ed di
stan
ce
can n
o
t affe
ct
the expe
ctati
on of th
e p
a
ttern i
n
the
ne
xt
iteration. The
low ord
e
r m
odel individu
als wh
o
s
e fitness are bett
e
r t
han the a
v
erage p
opul
ation
fitness
will grow expo
nenti
a
lly.
Proof The propo
sed alg
o
ri
thm adopts th
e MPM cro
s
sover and MP
M mutation. Becau
s
e
MPM crossov
e
r a
nd mutati
on can n
o
t di
sru
p
t the
p
a
ttern. Sup
p
o
s
e
that the mod
e
l numb
e
r
of the
gene
ration i
s
, and the m
u
tation proba
bility is
, then the prob
abili
ty that all the
allele do not
mutated is
, in the most ca
se
, and
,
is the model
defined o
r
de
r. Then acco
rding to t
he m
odel theo
rem,
the model su
rvival prob
abi
lity
is:
(9)
In the equation (9
),
is the average
fitn
ess of
, and
is the avera
g
e
fitness of the
whol
e popul
a
t
ion. If
the fitn
ess of
the model is
times of the average
fitness, then
, and we can
get:
(10
)
Theo
rem 2 T
he pop
ulation
of the propo
sed EDIGA
is a finite Marko
v
proce
s
s.
Proof Be
ca
use the
state
space
of th
e
p
r
opo
se
d E
D
IGA is finite, suppo
se
the
e
n
co
ding
lenghtn of
chromo
som
e
is
, the individual
s can be
cha
nge from
to
. Then the whol
e state
spa
c
e is
, and
is the numbe
r of
sub
pop
ulatio
n,
i
s
the
le
nghtn
of chromosome.
T
hen th
e
state spa
c
e
ca
n
be
co
nst
r
u
c
ted
ma
x
1
,
ma
x
,
0
ij
fi
t
fi
t
fit
fit
fi
t
ij
f
it
fi
t
fit
i
f
it
j
f
it
0
fit
th
i
th
j
th
i
0
fi
t
0
n
n
n
m
th
t
(,
)
mn
m
p
()
(1
)
O
m
P
1
m
P
()
(1
)
(
)
O
mm
PP
O
()
O
()
(,
1
)
(,
)
[
1
(
)
(
)
]
va
m
n
f
mn
mn
pO
p
O
f
()
f
((
)
)
Xn
n
f
k
()
(
1
)
n
f
kf
(,
1
)
(,
0
)
(
1
)
[
1
(
)
(
)
]
n
va
m
mn
m
k
p
O
p
O
()
X
t
(
0
,
0
,
,
...,
0)
(
1
,
1
,
...,
1
)
NL
N
L
Evaluation Warning : The document was created with Spire.PDF for Python.
127
ISSN: 2302-4
046
TELKOM
NIKA
Vol. 11, No
. 1, Janua
ry 2013 : 123 – 1
2
9
throug
h
cho
o
sin
g
indi
viduals fo
rm
, the stat
e space i
s
finite. Also
be
cau
s
e
,
and
have no relation
with the iter
ation
numbe
r,
is the migration
operator,
is the gen
etic op
erato
r
, and
,
is the mutatio
n
operator,
is the
cro
s
sove
r op
erato
r
,
is the
immune
sel
e
ction
ope
rat
o
r. So the
has n
o
rel
a
tio
n
with
, then
is the finite Markov pro
c
e
ss.
Lemma 1 [11]
s
e
t
,
, if
,
s
a
tis
f
y (1)
, (2)
,
then
ca
n
proba
bility strong
co
nverge
nce t
o
the
sati
sfaction
set
, then
。
Theo
rem
3 T
he evol
ution
popul
ation of
the p
r
op
ose
d
EDIGA i
s
, then
is
prob
ability strong converge
nce
to the satisfactio
n
set
.
Proof From t
he evolutio
n
pro
c
e
s
s of
the
EDIGA,
whe
n
the p
o
pulation
co
ntains th
e
satisfa
c
tion
set in the
iteration, then the popul
at
ion will also
cont
ains the
satisfaction set in
the next gen
eration, the
n
, so
, and the co
ndition
(2)
can me
ets. Condition (1
) is the same
as
.
Bec
a
us
e ,
then
we can get
,
. It is prove
s
that
is least than 1 in no
more tha
n
o
ne co
ndition,
then at the gene
ration
,
so
,
and th
e
con
d
ition
can
al
so
meets,
th
en
ca
n p
r
o
bability stron
g
convergen
ce to
the
s
a
tis
f
ac
tion set.
4. Simulation Resul
t
s of
Benc
hmark
Function
s
In orde
r to e
v
aluate the
algorith
m
, the pro
p
o
s
ed
algorith
m
ha
s be
en ap
pli
ed to the
optimizatio
n
of well
-kno
wn be
nchma
r
k functio
n
s
an
d its
perfo
rm
ance i
s
comp
ared
with
tha
t
of
other
algo
rith
m. The
dime
nsio
n of
and
ca
n b
e
set a
s
2,
and
the
dimen
s
ion
of
and
can
be
set a
s
20, the opti
m
um of fun
c
tion
is -1.10
3
1628, a
nd th
e optimum
of
,
and
are all zero.
,
,
,
.
The scal
e of popul
ation scale is 10
0 an
d
,
. The maximal iteratio
n
can be set
a
s
10
0.
The propo
sed algo
ri
thm
ca
n
be compa
r
ed with
geneti
c
alg
o
r
ithm
(GA)
a
nd
immune g
ene
tic algorith
m
(IGA).
Table
2 i
s
th
e
statisti
cal
re
sults
com
pare
d
with
GA
an
d IGA. F
r
om t
he
simulatio
n
re
sult
s,
the conve
r
g
e
n
ce
spe
ed of
the prop
ose
d
algo
rith
m is faster tha
n
GA and IGA, and can al
so
get
N
(1
)
(
(
)
)
VG
X
tT
T
X
t
V
T
G
T
V
T
G
T
GM
C
S
TT
T
T
M
T
C
T
S
T
(1
)
Xt
()
X
t
()
X
t
((
1
)
/
(
)
)
B
cc
t
aP
X
t
B
X
t
B
((
1
)
/
(
)
)
B
cc
t
PX
t
B
X
t
B
B
t
a
B
t
1
B
t
t
(1
-
)
0
B
t
B
t
a
1-
{(
)
}
X
t
B
li
m
(
(
)
)
1
t
PX
t
B
()
X
t
()
X
t
B
th
t
((
1
)
/
(
)
)
0
cc
PX
t
B
X
t
B
0
B
t
a
sup(
)
1
B
t
((
1
)
/
(
)
)
((
1
)
/
(
)
)
1
cc
c
c
P
X
t
B
Xt
B
P
Xt
B
X
t
B
1(
(
1
)
/
(
)
)
B
cc
t
PX
t
B
X
t
B
((
1
)
/
(
)
)
0
cc
PX
t
B
X
t
B
((
)
)
P
Xt
B
1
t
((
1
)
)
1
PX
t
B
sup(
)
1
B
t
()
X
t
1
f
2
f
3
f
4
f
1
f
2
f
3
f
4
f
4
22
2
2
1
11
1
1
2
1
2
(
)
=
(
4
2
.
1
)
(
44)
,
[
3
,
3
]
3
i
x
fx
x
x
x
x
x
x
x
22
2
22
1
1
(
)
=
1
0
0
(
)
(
1
)
,
[
-
2
.
04
8,2
.
04
8]
i
fx
x
x
x
x
2
3
11
11
(
)
20
0.
02
e
x
p
c
o
s
(
2
)
2
0
[
30
,
30]
2
0
nn
ii
i
ii
fx
x
x
e
x
n
nn
，，
2
4
1
1
1
(
)
1
c
os
,
[
6
0
0
,
600
]
2
0
40
00
n
n
i
ii
i
i
x
fx
x
x
n
i
，
0.7
c
p
0.0
5
m
p
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
128
Estim
a
tion of
Distri
bution I
m
m
une Gene
tic Algor
ithm
and Con
v
erg
ence Analysi
s
(LI
U
Zhen
)
bet
t
e
r
re
sult
s.
Fro
m
t
h
e
st
a
t
ist
i
cal
re
sult
s
,
t
he
propo
se
d alg
o
rithm
can g
e
t better
results, a
nd t
h
e
simulatio
n
re
sults i
s
also stable.
Table 1. Simulation re
sult
s of the three
algorith
m
s
Function
GA
IGA
EDIG
A
Mean
Std
Mean
Std
Mean
Std
-1.02
3.25×10
-
2
-1.03
2.85×10
-
2
-1.03
2.89×10
-
2
7.01×10
-
1
4.19×10
-
1
6.67×10
-
2
4.08×10
-
2
6.10×10
-
2
3.65×10
-
2
1.03
8.01×10
-
1
2.18×10
-
2
1.64×10
-
2
4.31×10
-
3
2.10×10
-
3
6.54×10
-
1
3.56×10
-
2
9.42×10
-
2
2.17×10
-
2
5.17.×10
-
3
2.31×10
-
3
T
o
the fu
nctio
n
and
, the si
mulation
re
su
lts of EDIGA
i
s
only a little
better tha
n
th
e
simulatio
n
re
sults
of GA
a
nd IGA. It is becau
se
that
the MPM in the low-orde
r function
cont
ain
less allele, sometime
s the MPM only contain
s
on
e allele, so
it has small
ef
fect on the
conve
r
ge
nce of the proposed evol
ution algorith
m
. But to
the high-orde
r functio
n
and
, th
e
MPM can en
han
ce the pe
rforman
c
e of the pro
p
o
s
ed
algorith
m
obv
iously
.
The iteratio
n runni
ng resul
t
s of function
and
are
sh
own a
s
Fig
2
(a) an
d Fig2
(b
).
From the sim
u
lation re
sult
s, we can se
e that
the
pro
posed algo
rithm perfoem
well than GA
and
IGA.
T
o
the low-order fun
c
tion
, each of three
alg
o
rithms can re
a
c
h the glo
bal
optimum, bu
t
the propo
se
d
algorithm ha
ve faster con
v
ergen
ce
spe
ed, for the high-o
r
d
e
r function
, EDIGA
can g
e
t better result
s than t
he other two algorith
m
s.
(a)
s
i
mulation res
u
lt
s
of
(b) s
i
mulation res
u
lts
of
Figure 2. Co
mpari
s
o
n
of simulation results
5. Conclusio
n
The obje
c
tive of this work is to creat
an ef
ficient
and com
pete
n
t EA, capa
ble of
solving large scale dif
f
icult probl
em
s. Particula
r
ly
, we are intereste
d
in creating a
n
algorithm th
a
t
can de
al ef
ficiently with problem
sub-st
ructu
r
e
s
, solv
ing a broa
der
class of pro
b
lems tha
n
the
cla
ss th
e IGA
can h
andl
e.
The individ
u
a
l
s in
the
p
o
p
u
lation
can crossover and mutation
ba
sed
on MPM and every sub
pop
ulation in the prop
osed alg
o
rithm
s
can n
o
t only evolve
indepen
dentl
y
,
but also exch
ange i
n
form
a
t
ion with e
a
ch othe
r
.
Simu
lation re
sult
s
of ben
chma
rk function
s p
r
o
v
e
the corre
c
tne
ss of the p
r
op
ose
d
algo
rith
m.
Referen
ces
[1]
Wu QY, Jiao
LC, Li YY, et
al. Se
lf Ada
p
ti
ve Qua
n
tum-in
s
pire
d Immun
e
Cl
on
e Al
gor
i
t
hm an
d Its
Conv
erge
nce Anal
ys
is.
Pattern Reco
gniti
on
and Artifici
al In
tellig
enc
e
. 200
8; 21(5): 59
2-5
97.
1
f
2
f
3
f
4
f
1
f
2
f
3
f
4
f
2
f
3
f
2
f
3
f
2
f
3
f
Evaluation Warning : The document was created with Spire.PDF for Python.
129
ISSN: 2302-4
046
TELKOM
NIKA
Vol. 11, No
. 1, Janua
ry 2013 : 123 – 1
2
9
[2]
Liu SR, Z
han
g
BT
.
Quantum Immune Clon
a
l Alg
o
ri
thm Based o
n
Biol
o
g
ic Informatio
n
Mechan
ism.
Pattern Reco
g
n
itio
n an
d
Artificial Intelligence
, 2008; 2
1
(5): 592
–5
97.
[3]
Xu B, Z
h
u
ang
Y. Adaptive
Immune
Alg
o
ri
thm Based o
n
Dan
ger T
heor
y
.
Jo
urna
l o
f
Si Chua
n
Univers
i
ty (Eng
ine
e
rin
g
Scie
n
c
e Editio
n
. 201
1; 43(3): 12
3–1
32.
[4]
Chen JY, Lin
QZ, Ji Z
.
A Hy
brid Immune
M
u
lti-o
b
jectiv
e Optimizati
on Al
g
o
rithm Euro
pe
an.
Jour
nal of
Operatio
nal R
e
search
. 20
10;
204: 29
4–
30
2.
[5] Ali
RY.
A Nov
e
l Hybr
id I
m
mune A
l
gor
ith
m
for Global O
p
timi
z
a
ti
on i
n
Desig
n
a
nd M
anufactur
i
n
g
.
Rob
o
tics an
d Co
mp
uter-Inte
g
rated Ma
nufa
c
turing
. 20
09;
25: 261
–2
70.
[6]
GR Harik, F
G
Lobo, DE
Goldber
g.
T
he Com
pact Genetic Alg
o
ri
thm.
IEEE Tr
ansactions on
Evoluti
onary C
o
mputati
o
n
. 19
99; 3(4): 28
7-2
97.
[7]
T
an LX, Guo
L.
Quantu
m
-In
s
pire
d Estimati
on of Distri
but
ion Al
gorit
h
m
Based
on C
o
mpr
e
h
ensiv
e
Lear
nin
g
. Pattern Reco
gniti
on
and Artifici
al In
tellig
enc
e
. 201
0, 23(3): 31
4-3
19.
[8]
Shahr
ya
r R, Hamid
RT
, Magd
y MS. A
Novel P
o
p
u
lati
on Initi
a
liz
atio
n Metho
d
for Accelerati
n
g
Evoluti
onar
y Al
gorithms.
Co
mputers an
d Mat
h
e
m
atics w
i
th Appl
icatio
ns
. 2
007, 53(
10): 16
05–
16
14.
[9]
Che
ng LJ,
Din
g YS, Hao
KR.
An Ense
mbl
e
Kerne
l
Cl
assifi
er w
i
th Immu
n
e
Cl
ona
l Se
lec
t
ion Al
gorith
m
for Automatic Discri
m
i
nant of
Primary Ope
n
-
ang
le Gla
u
co
m
, Neurocom
puti
ng, 201
2, 83(1
5
): 1-11.
[10]
Z
hao F
Y
, Ma
Z
hen-
yu
e, W
ang
Y
i
-b
o. Identificati
on
of D
y
namic
Para
meters Base
d
on A
daptiv
e
Pseud
o-p
a
ral
l
e
l
Genetic Alg
o
ri
thms.
Journal
of Dali
an Un
ive
r
sity of T
e
chnol
ogy
. 200
7; 47(
2): 252-2
56.
[11]
Z
hang W
X
, Lia
ng Y.
T
he foun
datio
n of gen
etic alg
o
rith
m
. Xi
an: Xi an Jia
o
t
ong Pu
blis
her,
200
3.
Evaluation Warning : The document was created with Spire.PDF for Python.