о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 5 Vol.36 No.5 1999



ӳɢHopfield첽
ɽɡ顡Ƕ
ժҪɢHopfieldһҪ첽зʽȶ̬ͬзʽڲ2ļ޻ǸģͿơŻۻиӳɢHopfieldԶ첽зʽ£֤˶ԳȨԶƹеɢHopfieldԽ, ֵӳɢHopfieldȶ̬Ĺϵȶ̬ݻ, õ첽ʱﵽȶЭϵ.
ؼʡɢHopfield磬ӳ٣ԣȶ̬
ͼšTP18TP311
CONVERGENCE OF DISCRETE HOPFIELD-TYPE NEURAL 
NETWORKS WITH TIME-DELAY IN A SERIAL MODE
QIU Shen-Shan, XU Xiao-Fei, and WANG Ya-Dong
(Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin150001) 
LIU Ming-Zhu
(Department of Mathematics, Harbin Institute of Technology, Harbin150001)
AbstractIt is known that an important property of the discrete Hopfield-type neural network is that it always converges to a stable state when operating in a serial mode and to a cycle of length at most 2 when operating in a full parallel model.These properties are the basis for the potential applications of this model,such as associative memory devices and combinatorial optimization.Convergence theorems of discrete Hopfield-type neural networks with delay are obtained in the paper.Under a proper assumption,it is proved that any discrete Hopfield-type neural network with delay will converge to a stable state when operating in the serial mode,and one of the weight matrices is a symmetric one and can generalize convergence theorem in earlier works.The authors also relate maximum of modified energy function to stable state of neural network with delay and obtain evolution features in neighborhood of stable state.In other words,this network can converge to a stable state after one time interval.Accordant relations between convergence of the energy function and stabilization correspondent network are presented in the serial mode as well.
Key wordsdiscrete Hopfield-type neural network, delay, convergence, stable state
1
ɢHopfieldһܹģԾֲܵĴģд磬ͼģʽʶ𡢷Թ滮TSPѵõ˳ɹӦ. ΪĹ㷺Ӧԣѧ߽ۺӦõооɹ16ݣȻӳɢHopfieldհף
˹ӳ٣McCulloh-Pittsģ֮漰ӳٵ˹ĳΣHerzHebѧϰӳٶӰ7ݣʵϣӳʹ״̬ʷ״̬лϵʹݻ뵱ǰ״̬йػʷ״̬Լȿѧϰռ-ʱģʽֿԪνһݻԣоӳ˹ϵͳ۲壬ҪӦüֵ.
֪ɢHopfield֮䡢ŻΪԣ첽зʽȶ̬46ݣͬзʽڲ2ļ޻8ݣ첽зʽ£֤ӳɢHopfieldȶ̬.ļֵȶ̬Ĺϵõ첽ʱNﵽȶЭϵ.
2ӳɢHopfield
nӳɢHopfieldnȫԪɣÿԪiʱtӵִ洢״̬xi(t),xi(t-1)xi(t-1)ʾʷ״̬ļ䣬Ҳ˵ʱṹnn׾w0,w1һnάֵ=(1,2,n)TΨһȷN=(w0w1,).w0ijʾڵǰ״̬ԪjԪiȨֵw1ijʾӳ״̬ԪjiȨֵiΪiԪֵ.Ԫ¹һʱ̵״ֵ̬
(1)
У
ν첽зʽ2ʱt2NһԪi(1)ʽݻn-1Ԫ״ֲ̬.ӳɢHopfieldN=(w0w1,)ӳȨw1=OnnΪɢHopfield46ݣ
3ظ
Ϊ㣬·ţBnʾÿȡ1nάȫ壬Bn={v.v=(v1,v2,vn)T,vi{-1,1}},u,vʾu,vBnڻʾuvHamming.ȻСu,v=n-2dH(u,v)BH(v,r)ʾBnvHamming벻rȫ壬BH(v,r)={u:dH(u,v)r,u,vBn}
1. nӳɢHopfieldN=(w0w1,)һ״̬vBnΪȶ״̬Ʋ㣩.i,1inУ
(2)
.:v=(v1,v2,vn)T.
2. N=(w0w1,)ѡv(0)=v(1)BnΪֵʱt2,ѡ״̬vi(t)vi(t-1)ͬԪi(1)ʽзʽݻ;ȫͬv(t)=v(t-1)ѡһԪ(1)ʽзʽݻƴݻʽΪ첽зʽ
3. Bn϶ԪE(u,v)=uTw0u+2uTw1v-2uTΪN=(w0w1,)u=v(t)u=v(t-1),E(t)E(v(t),v(t-1))
4. u,vBH(v*,r)E(u*,v)E(u,v)v*ΪE(u,v)HammingΪrļֵ;r=nv*ΪE(u,v)ֵ.ƿԶHammingΪrļСֵСֵ.
5. æ(E,r)ʾE(t)=E(v(t),v(t-1))HammingΪrļֵļ,(N)ʾN=(w0w1,)ȶ̬ļϣ(E,r)(N)E(t)Ϊr(E,r)(N)E(t)Ϊr(E,r)=(N)E(t)Ϊr걸رr=1ʱֱΪ桢걸6.
4ӳɢHopfield
ӳɢHopfieldΪ䡢Ż㣬ǾŻɿԵĹؼأҲŻ۸ݣȻΪעӳʲôӳкã¶شЩ⣮
1. nӳɢHopfieldN=(w0w1,),w0nn׶Գƾw1nn׾ҶԽԪ㣺
(3)
ĳʼ״̬x(0)=x(1)Bn첽ʽУһȶ̬
֤. ɶ3E(u,v)

u=x(t),v=x(t-1),Ϊֵ=(1,2,n)TȻE(t)E(x(t),x(t-1))Ͻ磬
|E(t)|ܪni=1nj=1(|w0ij|+2|w1ij|)+2ni=1|i|.

E(t)E(t+1)-E(t),xi(t)xi(t+1)-xi(t),

E(t)=xT(t+1)w0x(t+1)+2xT(t+1)w1x(t)-2xT(t+1)
-xT(t)w0x(t)-2xTw1x(t-1)+2x(t)T.
ʱt2첽зʽ½ݻУ
E(t)=2xi(t)Hi(x(t))+w0ii(xi(t))2+2xi(t-1)xi(t+1)w1ii
(4)
2첽зʽ,֤ڦxi(t)xi(t-1)0.ʧһԣ
(1) xi(1)=-2,xi(2)=2,
x(0)=x(1),xi(0)=xi(1)=1,xi(2)=-1,xi(3)=1֪xi(2)=2,xi(1)=-2
(2) xi(1)=2,xi(2)=-2.
x(0)=x(1),xi(0)=xi(1)=-1,xi(2)=1,xi(3)=-1֪xi(1)=2,xi(2)=-2
(1)xi(2)=-1,У
(5)
2֪һȻݻiԪxi(3)=-1,
(6)
ע⵱jiʱxj(0)=xj(1)=xj(2).(6)ʽ-1(5)ʽӵã
2w0ii<0.(7)
֪(7)ʽ(3)ʽì.֤ͬ(2)xi(1)=2,xi(2)=-2ʱҲƳ(3)ʽì.
xi(t)=0,xi(t-1)=2ʱ
(8)
(3)ʽ֪E(t)0.
xi(t)=0,xj(t-1)=-2ʱ
(9)
֪E(t)0.
xi(t)=2,xi(t-1)=0ʱ
E(t)4(w0iiHi(x(t))).(10)
(3)ʽ֪E(t)0.֪xi(t)0xi(t-1)0ʱЦE(t)=E(t+1)-E(t)0,ɵнԭ֪E(t).
½һ֤E(t)ʱN=(w0w1,)սĳһȶ̬.
E(t)t0,tt0ʱ
E(t)=E(t0).(11)
x(t0)=x(t0+1)ҶÿһԪݻ䣬x*=x(t0)ΪNȶ̬x(t0)x(t0+1)һԪixi(t0)xi(t0+1)ԪiݻУ89ֿʹE(t0+1)=0.һǡΪx(t0+1)=x(t0+2)ѡһԪݻܸıԪi,xi(t0+1)=xi(t0+2)=-1ͦE(t0+1)=0֪w0ii=0w0ii>0Ԫiܸı״̬Ϊtt0ʱE(t+1)=4(w0ii+Hi(x(t)))0루11ʽì.Ϊ֤㣬w0ĴԽԪظΪl½˵E(t)Nͬȡl.
ɣ11ʽ֪tt0ݻܸıԪߢxi(t0)xi(t0+1),ߢxi(t0+1)=xi(t0+2)=-1w0ii=0,Hi(x(t0))=0ڢݻ1Σڢݻ(l-2)+1ظڵݻ(l-3)+1,(l-4)+1,,1ݻﵽNĳһȶ̬Ȼw0ԽԪؾʱE(t)ʱNĳһȶ̬һxi(t0)=-1,xi(t0+1)=1,xi(t0+2)=1ﵽȶ̬xi(t0)=1,xi(t0+1)=-1,xi(t0+2)=-1,ﵽȶ̬
1. nӳɢHopfieldN=(w0w1,),w0nn׶Գƾw1nn׾ҶԽԪ㣺

ĳʼ״̬x(0)=x(1)Bn첽ʽУE(t) Nݻһ.
Ӷ1֤󲿷ֿɵõ1
2. 1w1˻ΪOnnʱw0ij0(i=1,2,,n). ʱ2Ϊ[5]еҪ1ƹ[5]еҪ
2. nӳɢHopfieldN=(w0w1,)w0nn׶Գƾw1nn׾ҶԽԪ㣺
(12)
ĳʼ״̬x(0)=x(1)Bn첽ʽУһȶ̬ĳֱҪӦͬʱﵽ.
֤. ʹõķ붨1֤ʹõķͬڴȥ˵ʱt2첽зʽ½ݻУ
E(t)=2xi(t)Hi(x(t))+i(t).
У

ֽE(t)iԪt-1tt+1ʱ̵Ŀ״̬б£
1

Ŧxi(t)xi(t-1)xi(t+1)xi(t)xi(t-1)E(t)=2xi(t)Hi(x(t))+i(t)
10211-1
20-2-1-11
3201-1-14(w0ii+Hi(x(t)))
4-20-1114(w0ii-Hi(x(t)))
5001110
600-1-1-10

: 
x(t0)=x(t0-1)x(t0-2),x(t)(1)ʽ첽ʽݻ}
E(t0)>E(t0-1),E(t)x(t)ݻ·}
֤T0=T1һ棬T0Ķ弰1еt=t0-1ʱx(t0-1)x(t0+2)ȼNеĳԪiڱ1н12xi(t0-1)xi(t0-2),Ӧ

E(t0)>E(t0-1)tT0ʱx(t)=x(t0).ԦE(t)=E(t0)=0,T0T1; һ棬T1Ķ֪E(T0)>E(T1-1)ʱڱ1нܳ12. 34첽й֪һ12(12)ʽ֪E(T1+1)>E(T1)ʽT1Ķ妤E(T1)=E(T1+1)-E(T1)=0ìܣʴӱ112֪x(T1-1)x(T1-2)ɵtT1,E(t)=0(12)ʽ֪tT1ʱE(t)=0ҽ156Ľ֣xi(t)=xi(T1),tT1,֪T1T0, T0=T1T0T1Ķ֪T0Nݻ(1)ﵽȶ̬ʱ̣T1ǡNݻ·ﵽ״̬ʱ̣T0=T1,ͬʱﵽ
3 nӳɢHopfieldN=(w0w1,),w0nn׶Գƾw1nn׾ҶԽԪ㣺
(13)
vNȶ̬ĳֱҪvΪE(u,v)HammingΪ1ļֵ㣮
3֤˼[6]ж2(iii)֤ƣ.
3 ֪3ļ,N걸
3֪ӳNΪŻģͣȻϣr걸.
4. nӳɢHopfieldN=(w0w1,),w0,w1nn׾ҶԽԪطǸ첽ʽУܵu,vBH(v*,1)(1)ʽݻһݻv*vһNȶ̬
ע4ܵu,vBH(v*,1)ζuv*,vv*,uv֣ܳΪ첽ʽʱv(t),v(t-1)ͬķΪ1
֤. (1)ʽݻͶ2ܵu,vBH(v*,1)д:u=v*+u,v=v*+v,Уu=(0,0,-2v*k,0)T,v=(0,0,-2v*l,0)T,,¡{0,1}.
4
 ==1,1k=ln;
 =0,=1,1ln;
 =1,=0,1kn;
 =0,=0.
֪

һݻv:
skv*k=sgn(v*kHk(v*k)-2(w0kk+w1kk))>0
ȼ
v*kHk(v*k)-2(w1kk+w0kk)0.(14)
(2)(3)(4)֪ͬ
v*lHl(v*l)2w1ll,(15)
v*kHk(v*k)2w1kk,(16)
ѡĳi
v*kHk(v*k)0.(17)
u,vԼklȡ1nԴ(14),(15),(16)(17)ʽκһʽӾɵõvNȶ̬
4. nӳɢHopfieldN=(w0w1,),w0nn׶Գƾw1nn׾ҶԽԪطǸ첽зʽ֮һ
1 u=vv*u,vBH(v*,1)һv,
2 uv*,v=v*,u,vBH(v*,1)һv,
3 u=v*,vv*,u,vBH(v*,1)һv.
vһNȶ̬
֤ɶ4֤е(14),(15)(16)ʽֱӵõ
Ӷ44֪첽зʽ,v*ǷΪNȶ̬BH(v*,1)еĵһݻȷҲɽ϶12Ľʶ44ݻ·ƣBH(v*,1)пܹɵE(u,v)ֵ첽зʽ¾һݻE(v*,v*)v*Nȶ̬Ȼľֲֵ.
5ᡡ
(1) ĸW0ΪԳƵ첽еԶ,ƹHopfield5ݵĽ
(2) ӳɢHopfieldӦĶԪΪӳɢHopfieldΪơŻ춨ۻ
(3) ļֵNȶ̬ĶӦϵNȶ̬ݻһݻȶ̬
(4) õN첽ʱȶ̬Эϵ, ͬĳֱҪ
õȻѧ(Ŀ A01030202).
߼飺ɽУ19621ʿʦҪо缰ӦáѧϰС.ɣУ196211ڣʿʦо졢ֲʽݿ.飬У19416ڣʿʦҪӳ΢ֵַ⣬񾭼С.ǶУ19648ڣҪоΪרϵͳѧϰ֪ʶ.
ߵλɽɡǶҵѧѧ빤ϵ150001
顡ҵѧѧϵ150001
ο
1壬࣬⸣. Էѧϰ㷨.ѧ,1994,17(9):676681
(Zhang Ling, Zhang Bo, Wu Fuchao. Ellipsoid learning algorithm of neural networks with self-feedback connections.Chinese Journal of Computers(in Chinese),1994,17(9): 676681)
2žӢ. HopfieldĹط.Զѧ1997,23(4):447453
(Zhang JunyingXu JinBao Zheng. Connected analysis for Hopfield networks. Acta Automatic Sinica(in Chinese),1997, 23(4): 447453)
3Zhang Xiangsun, Li Hongfeng, Wang XiaodongA straightforward mathematical analysis for the Hopfield neural networkActa Electronica Sinica,1992,20(10):1017
4Bruck J, Goodman J WA generalized convergence theorem for neural networksIEEE Trans on information theory1988,34(5):10891092
5Hopfield J J. Neural networks and physical systems with emergent collective computational abilities. Proc Nat Acad Sci USA ,1982,79:25542558
6Zongbin Xu, Guoqing Hu, Chungping Kwong. Asymmetric Hopfield-type networks: Theory and applications. Neural Networks,1996,9(3):483501
7Herz A V M, Li Z, van Hemmen J LStatistical mechanics of temporal association in neural networks with transmission delaysPhys Rev Lett,1991,66:13701373
8Goles EFogelman F,Pellegrin DDecreasing energy function as a tool for studying threshold networksDiscrete Appl Math,1985,12:261277
ԭյڣ1998-07-03
޸ĸյڣ1998-11-06
