Զѧ
ACTA AUTOMATICA SINICA
2000Vol.26No.3P.401-404



Թ滮ĻʽŴ㷨
ƼӸΰ
ժҪԹ滮,ͨ׼з׼зĿжȵ¸Ͷǿе(Ⱦɫ)·;ͨǶǿȾɫϢۺ,ͻƴͳĸǿȾɫԴĳͷ˼, µ۷ǿȾɫķ.ݶȷµ۷, һµȨݶȷĻʽŴ㷨(HGA).Բķ㷨Ч.
ؼʡԹ滮, ʽŴ㷨, Ȩݶȷ, ׼з.
HYBRID GENETIC ALGORITHM FOR SOLVING NON-LINEAR 
PROGRAMMING PROBLEM
TANG JiafuWANG DingweiGAO ZhenWANG Jin
(Institute of Information Science and Engineering,Northeastern University,Shenyang110006)
AbstractBased on the introduction of the new concepts of semi-feasible direction,feasible degree of semi-feasible direction,feasible degree of illegal points belonging to' feasible domain,etc.this paper proposes a new method for formulating and evaluating illegal points and three new kinds of evaluation functions,and develops a special hybrid genetic algorithm(HGA) with penalty function and weighted gradient direction search for non-linear programming problems.Simulation shows that this method is effective.
Key wordsNon-linear programming,hybrid genetic algorithm,weighted gradient direction,semi-feasible direction.
1
ͳĽԹ滮ķж֣1,ͷз򷨵,ҸӦӦΧ;.ΪһܻŻ, Ŵ㷨(GA)23Խܹ㷺Ӧ⡢0-1滮.GA͵ķԹ滮, ֻڴͳķ. GAڷԹ滮ʱ,ϵͳԼĴҪ,ΪŴӲȾɫ峣ͻƸԼ, ǳֹؼ4. ַǿԵĴͳ, ǸЩǿеȾɫԴĳͷǿȾɫ.䱾ڽ̭ǿнСռ. ѡҵȫֺõĺѡ,ŴʧȥЧ.Ϊ˿˷, ͶǿȾɫ¸,ͨѷǿȾɫϢǶ뵽ӦԺ, ԶǿȾɫĳ̶, ۷ǿȾɫ·.ݶȷµۺ,һµĻʽŴ㷨͵ķԹ滮.
2Թ滮ĻʽŴ㷨HGA
ĿǵķԹ滮һʽ(NLP)
max f(x)=f(x1,x2,,xn),
st.xQ=xEngi(x)0,i=1,2,,m.
f(x),gi(x)Enһ׵.ĻݶȷµۺĻʽŴ㷨Ļ˼ǣʼȺ(ȺСΪpopsize).ÿε,ÿxQ,ǿȾɫϢǶ뵽ӦԺйµۺ,ʹ֮нСӦֵ,;ÿڵаֲԱѡȡȨݶȷ57,Ӹ.xQ,ϽӲӴ.ŵ,нСӦֵӸ𽥱̭,ӦֵϴĿ꺯ֵϴӸ.Ŵ֤ӿͷǿŽ.
2.1Ȩݶȷ
ڸx,xQ,Ŀ꺯ݶȷ򡡦f(x) ,ʹĿ꺯õĽ.xQ,˵xڿ,I+=igi(x)0,xEn.iI+,xظݶȷ-gi(x),ʹӸgi(x)0,ȨԽ,gi(x)0ٶԽ. Ȩݶȷw0,wi(i=1,2,,m)ݶȷȨ.w0=1,

ЦڵĺС.x(k)iȨݶȷd(x(k)i)Ӹx(k+1)iΪx(k+1)i=x(k)i+(k)d(x(k)i)(k)Ǿֵ˥Erlangֲ.
2.2ǿе
GAԼŻʱ, ԼĴ⼫ΪҪ,Ͷǿе, ÷ǿеĹϵϢѡ.
gmax(x)=max{gi(x),i=1,2,,m}.
1.xQ֮ġ롱d(x,Q)ΪxͻԼֵd(x,Q)=max{0,gmax(x)}, k0=arg{ihi(x)=hmax(x),i=1,2,,m}.
2. -gk0(x)Ϊx׼з.
3. zڵxQָ򡱿,zT(-gk0(x))0.
4. zڵxQԶ롱,zT(-gk0(x))0.
5. zڵxQ׼з,zڵxQָ򡱿.
Ȼ, ׼з׼з.Ȩݶȷ¶.
1. ׼з.
֤.xQ׼зz׼з;,ͨ·ʽϵġ/2, ֱõ׼з.ΪԽС,֤gk0(x)Ȩؽκgi(x)ȨԽ,-zԽƫgk0(x),ȷõ׼з.
2. xQ,Ȩݶȷd(x)׼з(֤ͬ).
6.ǿеxQ׼зĿжfd1=-d(x)Tgk0(x).
ΪǿеĹϵ,ǿе㡰ڡĿжȸ.
7. ǿе(Ⱦɫ)xQڡĿжfd2Ϊ

ЦiʾxiԼĳ̶.ǿежfd2ĴСӳ˵㡰ڡĳ̶;жԽ, ʾͻԼԽ,ڡϣԽ, fd2=1ȫڿ;֮,0fd21ܴӾȷ()ѧ˵,xQ,ģĹ۵, ʾxڿĳ̶().һصͶǿе. Ϸ,ǿе(Ⱦɫ)µۺ: 
1)Ƕǿе׼зĿжȣۺ

2)Ƕǿе㡰ڡĿжȣۺ

3)Ƕǿе㡰Զ롱ľ룬ۺ

2.3GAҪصѡȡ
1)ʽ.þ߱nάʵʾӸ.
2)ʼȺ. Ϊٶ,ݾ,ѡȡÿ޺;þȷֲȾɫĳʼȺ.
3). Ҫڵĺ.ʱ󲿷Ⱦɫ嶼ڿ,ҶŽ.xQһȾɫ, ԺСĸʰϽӽн.
4).HGAҪ,ҲǱʽŴ㷨ɫ;ȨݶȷHGAӱ֮. ʽx(k+1)i=x(k)i+(k)d(x(k)i)б.
5)Ⱦɫѡ.µۺùֲѡ.
6)ֹͣ׼. ݼ㾫ȵҪ,ȷĵ.
3ᡡ
ʽŴ㷨(HGA)ݶȷµۺǶ뵽Ŵ㷨УһȨݶȷӱʽŴ㷨ص:1)HGAһµȨݶȷΪҪ,ֻڵԺСĽ,Ϊӣ2)״ǿе׼з,׼з򼰿жȡǿеڿĿжȵ¸;ͶǿȾɫ·3)ǶǿȾɫϢۺ,ͻƴͳĸǿȾɫԴĳͷ˼,µ۷ǿȾɫķ4)ȡȫλʽ,ֲ;ѡȡ,Ҿֵ˥.
Բʵͷ,ͬͳGAͳͷ˱Ƚо67,ȽϽHGA㷨Ч.
Ȼѧ(69684005)ʡѧ(26249)Ͷѧ.
ƼӸ1965.ʿ.Ϊѧڡ۳дѧ߼оԱ.ȤоģŻ뷽ܻŻ.ڹҪڿѧϷ25ƪ.
ΰ1948.1993ڶѧѧʿѧλ.1994ѧʿо.ζѧԶϵڡʿʦ.ȤоCIMS洢ĽģŻơģŻ뷽ܻŻ.ڹҪڿ80ƪר32.
ƼӸѧϢѧ빤ѧԺ110006E-mail:jftang@mail.neu.edu.cn
ΰѧϢѧ빤ѧԺ110006
񣨶ѧϢѧ빤ѧԺ110006
誣ѧϢѧ빤ѧԺ110006
ο
1ݡBazaraa M S, Shetty L M. Non-Linear Programming: Theory and Algorithms,New York:John.Wiley & Sons, 1985
2ݡHolland J H. Adaptation in Natural and Artificial Systems.New York:The University of Michigan Press,1975
3ݡTakao Y, Mitsuo G et al. A method for interval 0-1 number non-linear programming problems using genetic algorithm. Computers & Industrial Engineering,1995,29:531535
4ݡMichalewicz Z. A survey of constraint handling techniques in evolutionary computation methods. In: Evolutionary programming IV, MIT Press,1995.135155
5ݡƼӸ,ΰ.һԹ滮ĸĽŴ㷨.ѧѧ,1997,8(5):490493
6ݡTang J, Wang D, Ip A, Fung R Y K. A hybrid genetic algorithm for a type of nonlinear programming problems. Computers & Mathematics with Applications,1998,36(5):1121
7ݡƼӸ.Ŵ㷨ģŻ۷Ӧо.۲ʿѧλģ.ѧϢѧ빤ѧԺ1999
ոڡ1998-06-02
޸ڡ1999-04-12
