ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



ӳɢ綯̬ľо 
ɽɡ

ժҪӳɢ״̬תƷ󲻵ʽĵȼоĶѧ.ھȨ,¸Ϊ12ļ޻ڵһЩ.ͬʱ,Ϊ1,24һЩ⼫޻˴ڵ,õ粻κβĳ,ֻм޻ĳ.ģʵȷ.
ؼʡ,ȶ,ӳ,޻.
ͼšTP183
Matrix Criterion for Dynamic Analysis in Discrete Neural Networks with Delay
QIU Shen-shan1 XU Xiao-fei1 LI Chun-sheng2 LIU Ming-zhu3
1(Department of Computer Science and Engineering Harbin Institute of Technology Harbin 150001)
2(Department of Computer Science Daqing Petroleum Institute Anda 151400)
3(Department of Mathematics Harbin Institute of Technology Harbin 150001)
Abstract The dynamics of discrete neural network with delay are studied in this paper using a matrix inequality which is shown to be equivalent to the state transition equation of the network. For the network with arbitrary weight matrix, the conditions for the existence of cycle of length 1 and 2 are presented. Also, the conditions for the existence of special cycle of length 1, 2 and 4, for having no any stable states are achieved. Computer simulations demonstrate that the theoretical analysis is correct.
Key words Neural network, stability, delay, cycle.

Hopfield˹ģӰ졢Ӧɹģ֮һ,ȶѾõ˱Ƚϳֵо[17],ΪʵӦõ춨ۻ.ķΪNP-ȫһЧ㷨(㸲(vertex cover problem)[6](maximal independent set problem)(maximum clique problem)[6]).ɢѧĹ۵,粻֮,ѧ,缫޻,ԿΪƵһֿз,ɢHopfieldļ޻˼[7].ɢѧĹ۵㿼ɢHopfield-,[4]˽4ڼ޻繹췽,[5]и˴2nڼ޻,ѧоȽ,ҪԭǸΪơŻڶѧϵ׷Ŀǲ.[8]ɢӳ첽йµȫȶ,ʵ,ӳмḻĶѧΪ.Ϊ,ֻжݻĶѧ˽,ַܳǱڵ,ƺӦ.Ĵӳɢ״̬תƷ󲻵ʽĵȼԳо䶯ѧ.
1ӳɢHopfield-
һӳɢHopfield-nȫԪ[8],ÿԪiʱtӵִ洢״̬:vi(t),vi(t-1)vi(t-1)ʾʷ״̬ļ,Ҳ˵ʱṹ.nn׾w0,w1һnάֵ=(12n)TΨһȷ,ΪN=(w0W1,).w0ijʾǰ״̬ԪjԪiȨֵ,w0ijʾӳ״̬ԪjiȨֵ,t+1ΪiԪֵ.Ԫit+1ʱ̵״̬ݻ.
 (1)
,fiΪֵ.
ӳɢHopfield-N=(w0w1,)ӳȨw1=Onnʱ,ΪɢHopfield-N=wȣ.w0iiӳɢHopfield-(ʽ(1))ΪԷ[16]
֤[5],ʽ(1)ֵfi,һһֵgi,x0x1Bn{v:v=(v1,v2,vn)T,vi{-1,1}} ,x0=(x01,x02,x0n)T,x0=(x11,x12,x1n)T,fi=gi,жgi:
 (2)
ǳgiΪϸֵ.ܼfiΪϸֵ.
һӳɢN=(w0w1,)ʽݻ̻:
 (3)
.Ϊ
V(t+1)=f(w0v(t)+w1v(t-1)-). v(0),v(1)Bn,t=1,2, (4)
fĵiΪ.ΪΪfi(i=1,2,,n)ɵļΪһ޼,ʽ(4)v(k)(K=0,1,)һΪ(൱N=(w0w1,)ݻ),Ϊ޻.Ϊ1ļ޻Ϊ,ϸ.
. һӳɢHopfield-N=(w0w1,)һ״̬v*BΪȶ״̬(Ʋ),i,1in,
 (5)
,v*=(v*1,v*2,v*n)T.
v(t)Ϊtʱ̵״̬,ʽ(4)Ϊ綯̬Ե״̬תƷ.v(t),v(t- 1)ֱt,t- 1ʱ̵״̬.״̬ռ2n.|A|AԪصľֵɵľʽ,|A|=(|ij|)nn.
2뼫޻Ĵ
2.1 󲻵ʽ
״̬תƷʽ(4)󲻵ʽĵȼ.
. N=(w0w1,),v(0),v(1)Bn,Dkһnn׶ԽԪΪ1ĶԽǾ,༴
Dkʡ{D|D=diag(d1,d2dn),di=}1,
vk=DkJ,ô
Dk+1w0DkJ+Dk+1w1Dk-1J-Dk+1>0,k=1,2,.... (6)
,Dkʽ(6),ôv(k)=DkJһN=(w0w1,)״̬,J=(1.1,...,1)T.
ʵ,һӳɢHopfield-N=(w0w1,)״̬תƷʽ(4)v(k),k=0,1,...תΪʽ(6),˶ֵfiĴ.
֤:V(K)=DkJ,k=0,1,...,ôDk+1J=F(W0DkJ+w1Dk-1J-),k=1,2,...,J=(Dk+1)-1FV(W0DkJ+) w1Dk-1J-=Dk+1f(w0DkJ+w1Dk-1J-).ΪDkÿһԪؾΪ1,Dk+1ĵiԽԪ+1(-1),ôw0DkJ+w1Dk-1-ĵiԪһ0(С0),Ӷó
Dk+1w0DkJ+Dk+1w1Dk-1J-Dk+1>0.
֮,ʽ(6)Dkʳ,ôW0DkJ+w1Dk-1J-ĵiԪһDk-1ĵiԽԪͬ,ӶDk+1w0DkJ+w1Dk-1J->0,༴
Dk+1J=f(w0DkJ+w1Dk-1J-)
Ӷ,N=(w0w1,)״̬v(K)=DkJ,k=1,2,.... 
2.2 Ϊ1ļ޻()
1. N=(w0w1,)Ϊ1ļ޻(v=D)ĳҪDw0DJ+Dw1DJ-D0 .,v=D,Dһnn׶ԽԪΪ1ĶԽǾ.
֤:.Dw0DJ+Dw1DJ-D0,֪v(k-1)=Dk-1J=DJ,v(k+1)=Dk+1J=DJ,v(k-1)=v(k),v=DΪ.
Ҫ.N=(w0w1,)Ϊ1ļ޻,ôһһk0,k> k0,ʹv(k-1)=v(k)=v(k+1),֪,k> k0,Dk+1=Dk=Dk-1,Dk=D֪, Dw0DJ+Dw1DJ-D0 . 
Ӧע,е綼в,епֻм޻,ǽں.
ǽйزĸϸĽ.
2. N=(w0w1,),ҼD½.
(1) һD,:
|w0|J+|w1|J+D<0(|w0|J+|w1|J-D<0)(7)
ôҽһv=DJ(v=- DJ).
(2) һD,
Dw0DJ+Dw1DJ-||, (8)
ôv1=DJ,v2=-DJ
(3) 
 (9)
ô2n,Dj=DjJ,Dj,j=1,2,...,2n,2nnάֵȫĲ.
֤:(1) D0D1,,ɼ֪
. (10)
v(0)=D0J,v(1)=D1J,V(2)=DJ,ĳʼv(0),v(1),ʽ(7)(10)֪,綼v(2),Ψһ,ȡD0=D1=D,óDw0Dj+Dw1Dj-D,Ӷf(v(2),v(2))=v(2)v(2)ΪN=(w0w1,)Ĳ.֤ͬ,Dw0DJ+Dw1Dj-||>0ʱ,Ȼ.
(2) Dʽ(8),Ϊ||D,֪
Dw0DJ+Dw1DJ-DDw0DJ+Dw1DJ-||>0, (11)
Dw0DJ+Dw1DJ+DDw0DJ+Dw1DJ-||>0. (12)
Ӷv1=DJ,v2=-DJ,ʽ(11)ʱõv1=f(w0v1+v1v1-);ʽ(12)ʱõv2=f(w0v2+v1v2-),Ϊʽ(11)(12)ͬʱ,v1=DJ,v2=-DJͬʱ,v1,v2.
(3) di=1,i=1,2,...,nôdi,dj,²ʽ.
 
Ӷ

ʽ˵ľʽΪDw0DJ+Dw1DJ-D>0,D=diag(d1d2,...dn),ɶ1֪,һΪ1ļ޻v=DJ,Ϊǡ2nͬľD,Ӷ۳. 
N=(w0w1,)㶨2еʽ(9),ôֻв,Ϊ״̬ռ2n,ÿһΪ,[5]Ӧƹ㵽ӳ.
1. N=(w0w1,)Ȩw0w1ӦԪͬ,ô2nĳҪǶ2(3)е,ʽ(9).
֤:֤ͬ2,÷֤֤Ҫ,. 
2.3 Ϊ2ļ޻
ĶΪ2ļ޻.
3. N=(w0w1,)һΪ2ļ޻v1v2ҽ
(a) D2w0D1J+D2w1D2J-D2>0;
(b) D1w0D1J+D1w1D2J-D1iD2w0D2J+D2w1D2J-D2ĵiͬ,vj=DjJ,Dj,J=1,2.
֤:,һΪ2ļ޻v1,v2ҽ
D2W0D1J+D2w1D2J-D2>0,D1w0D2J+D1w1D1J-D1>0
ΪD1D2=D1D2=I(λ)D1,D2ɻ,ʽд
D1D2D1w0D1J+D1w1D2J-D1>0,D1D2(D2w2D2J+D2w1D2J-D1)>0
֪. 
2.4⼫޻Ĵ
ǿ¼:
(1) , (2) ,
(3) , (4) ,
(5) , (6) ,
i,j=1,2.
2. Dͬʱ(1),(2),N=(w0w1,)м޻.
3. (3),(4)ͬʱ,4Ϊ2ļ޻.(5),(6)ͬʱ,Ϊ4ļ޻.
ۿ֪,N=(w0w1,)ŷǳḻĶѧ,ⲢһҪʹΪĲ,ԽΪ޻,ԽǿĴ뵽һ޻.оN=(w0w1,)ļ޻ڼֲǷǳо.
2.5 ڲ
ǰۿ֪,D,|w0|J+|w1|JD,ûв.ǽֱӴ籾Ĳ.
4. i0ʹ,N=(w0w1,)ûв
.
ע,4еֻǳ,ǱҪ.ͬʱҲ˵ڸ,ֻڴ1ļ޻,ƹ[5]Ľ.һҪעķ,۵ݻȫе,ݻ(紮Сֲе)µӦ,ǽ.
3ʵ
Զ4Ϊ,ѡȨֵֵʵ,ȷ.ͬʱӳ.ͼ1ԲȦеֵʾԪ״̬Ϊʮֵ,(-1 -1 -1 -1)0 (-1 -1 1 -1)2,(-1 -1 1 1)3,(1 1 1 1)15,A ʾ̬ΪA,ͷָķΪݻֹ״̬; , , ䷽෴ͷָ״ֵ̬ɼ޻.
ͼ1ʾӳN=(w0w1,)ݻ,
.

ͼ1
Ϊ,N=(w0w1,)㶨4,ó16ֳֵݻĽ,ͼ1ʾ,ûȶ̬,Ϊ2ļ޻.ʵ˵4.ʵл㶨13Ȩ,֪۳..
4 
Ҫɢӳй,õ½:
(1) Ľ[2,5]Ĳֽƹ㵽ɢӳ;
(2) ھȨ,õΪ12ļ޻ĴԵһЩ;
(3) ĸΪ1,24һЩļ޻Ĵ;
(4) Ļ粻κβ,ֻм޻ĳ;
(5) ģʵ,ĵõĶȷ.
עͣоõȻѧ
߼飺ɽ1962,ʿ,ʦ,ҪоΪ˹,С,缰Ӧ
Ӧ,ѧϰ
ɣ1962,ʿ,,ʿʦ,ҪоΪ˹CIMS.
1960,,ҪоΪģʽʶ,˹,缰Ӧ
,POSC
飺1941,ʿ,,ʿʦ,ҪоΪ΢ֵַ,
,С
ߵλɽɣҵѧѧ빤ϵ  150001
ʯѧԺѧϵ  151400
飺ҵѧѧϵ  150001
ο
1Hopfield J J. Neural networks and physical systems with emergent collective 
computational abilities. Proceedings of National Academy of Science USA, 1982,
(79):25542558
2Brown D P. Matrix test for period 1 and 2 limit cycles in discrete threshold 
networks. IEEE Transactions on Systems Man Cybernation, 1992,22(3):552554
3Bruck J. On the convergence properties of the Hopfield model. Proceedings of 
IEEE, 1990,78(10):15791585
4Bruck J, Goodman J W. A generalized convergence theorem for neural networks.IEEE
Transactions on Information Theory, 1988,34(5):10891092
5ѧ,.Hopfieldļ.ѧ,1996,24(4):2133
(Liang Xue-bin, Wu Li-de. Memory capacity of binary Hopfield type neural network. 
Acta Electronica Sinica, 1996,24(4):2133)
6Arun J. Approximating maximum clique with a Hopfield network. IEEE Transactions 
on Neural Networks, 1995,6(3):724735
7,Ϊ.Hopfieldһ㷽.Զѧ,1996,22(3):301307
(Liu Xiao-hong, Dai Ru-wei. General methods of construction of Hopfield neural 
networks. Acta Automatica Sinica, 1996,22(3):301307)
8ɽ,,.ӳɢHopfieldԷ.廪ѧѧ,1998,28
(s2):131134
(Qiu Shen-shan, Xu Xiao-fei, Ma Rui-min. Convergent analysis of discrete 
Hopfield type neural networks with delay. Journal of Tsinghua University, 1998,
28(s2):131134)
ո:19998-09-03޸:1998-12-03
