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



̬ϵͳݻģ
ܺ졡ɽع
ժҪԲôͳ̬ϵͳ΢ַ̽ģѺʹڵĲ㣬˽ŴŴ㷨Ƕ׵Ļݻģ㷨ŴŻģͽṹŴ㷨ŻģͲɹʵ˶̬ϵͳĳ΢ַ齨ģԶʵô㷨ںʱɼԶֶŵĳ΢ַģͣеĽģ(ɫϵͳ)ȽϣнģܻԶģͽṹԸ㡢ϺԤľȸߵŵ㣮
ؼʡ΢ַ飬ݻģŴƣŴ㷨ɫϵͳ
ͼšTP301.6
A HYBRID EVOLUTIONARY MODELING ALGORITHM FOR DYNAMIC SYSTEMS
CAO Hong-Qing, KANG Li-Shan, and CHEN Yu-Ping 
(State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072)
AbstractTo overcome the difficulties and drawbacks in modeling the dynamic systems by using traditional methods, a hybrid evolutionary modeling algorithm (HEMA) is proposed to model the dynamic system with a system of ordinary differential equations (ODEs) whose main idea is to embed genetic algorithm (GA) in genetic programming (GP) where GP is employed to optimize the structure of a model, and GA is employed to optimize the parameters of a model. It has succeeded in automating the modeling process of systems of ODEs for dynamic systems. The computational experiments indicate that, by running the HEMA, the computer can search out multiple superior ODEs models in a reasonable time. Compared with most available modeling methods, such as the grey systems method (GSM), this algorithm possesses the advantages of automation of the modeling process, more flexible and various model structures, wider range of applications, and higher precision of fitting and predicting data. 
Key wordssystem of ordinary differential equations, evolutionary modeling, genetic programming, genetic algorithm, grey systems
1
ڹ̼ùȻѧѧձʱ仯ĸϵͳͷ۵ĲƷı仯˿ڵȣͨҪݶ̬ϵͳĹ۲ݽ΢ַģ(ѧģ)Ϊϵͳƺδ״̬ԤṩݣͨһǳҪʮѵ飮ͳĽģƾֱȼٶһ΢̵ַʽȻһЩֵȷеδ֪13ݣԷ׷ӵݣѡʵ΢ַģͽṹͨǺѵģǵ΢ַеıʱ
ĿǰھáᡢũҵϵͳԤУڲý϶ǵ˾Ļɫϵͳģ4ݣ΢ַĵģͰGM(n,1)GM(1,h)ģַͣͬģ͵Ľṹѡ⣬ͬһݼѡȡͬnhֵõģͲͬϺԤЧҲͬģ͵ĽṹҲȽϵһ͹̶֮⣬㲻㣺١ڸӵĶ̬ݣģ͵ϺԤľȲߣҪӳڶĹ̻ͨвʶβвģ޸ģڡΪ״̬ģ͵GM(1,h)ģֻܷӳh-1ĳһһ׵Ӱ,ܷӳϵͳڸ֮໥ãȻձ໥Լ໥õϵͳ֮Ĺ;ϵ֮ľȣЩҪͨ΢ַ
Щ⣬ݻ㷨Ӧ֯ѧϰԣ˽ŴŴ㷨Ƕ׵Ļݻģ㷨ŴŻģͽṹŴ㷨ŻģͲɹʵ˶̬ϵͳĳ΢ַ齨ģԶȫɼԶشӶ̬ϵͳĹ۲зϵͳĳ΢ַ飮
2ѧ
ȶģΪ

һ̬ϵͳn໥ĺģѹ۲⵽ϵͳʱһϵΪ

t0Ϊʼʱ̣tΪʱʾxjtiʱ̵Ĺ۲ֵ


 ɳȺĸϺʾģຯɵĿռΪF
΢ַĽģ

ʹС

ɴԤϵͳδ״̬.
3ݻģ㷨
ݻ㷨ģȻݻ̣ȻѡȻŴƶչһĲԺͷü򵥵ı뼼ʾָӵĽṹͨһʾм򵥵Ŵʤ̭Ȼѡָѧϰȷķݻ㷨е֯ӦѧϰԼʵĲԺڲͨǿص㣬ĿǰѱɹӦڻѧϰģʽʶ𡢾Ԥ⡢ŻƼ䲢д5,6ݣݻ㷨3֧Ŵ㷨(GA)ݻ滮(EP)ݻ(ES) 90Ŵ㷨ĻַչŴһµķ֧79ݣṹʾͬļҶγն˼ͨ޲κмγɺͨһЩĳȺŴ㷨Ļ˼룬ͨʹһЩŴ(ӽŴ)̬ظıЩṹһݻȥֱҵҪĽ⣮
ôͳŴƷʵֳ΢ַݻģȻģ͵ĽṹϴͳиԣͬʱҲһ⣬ȺУһЩṹϺõģкܴʻĲʹӦֵͶ̭Ⱥʹģ;ȷȲߣݻٶ֡.Ϊ˱ŴݻģÿһǶģ͵ĲẒ̇ʹýԼӿ첢ģ͸.ڴͳһЩԲƵ㷨ֱHooke-JeevesNelder-Meadݶȷͱ߶ȷ10ݵȣֻͨĳһضЧҶģ͵ǿҪģ;ɵԣݻģ㷨ģ͸ӶҿɶɣҲάҲ̶Щ޷ƣΪǲʵŴ㷨ʵֶģ͵ĲŻ
ŴŻģͽṹŴ㷨ŻģͲݵԤģ͵ļ໯͹淶ϵͳԤȸϣ㹹˱ĵĻݻģ㷨㷨Ľṹ£
PROCEDUREݻģ㷨
begin 
ԭʼݾX(0)
ԤõX(1)
ʼ΢ַȺP(0)
P(0)иӦֵ
s= 0;
repeat
ģ͵ļ໯͹淶
optimized á= 
for i= 1 to popsize do 
begin
if(piĽṹoptimized)
begin
piи΢ַĲ
ʼȺQ(0)
Q(0)иӦֵ
t= 0
repeat
ӦֵСѡԴQ(t)ѡһĸQ(t+1)
ִӽQ(t+1)
Q(t+1)иӦֵ
t= t+1
untilֹ
Q(t)еø滻piи̵ĶӦ
optimized= optimized{ piĽṹ }
end
end
ӦֵСѡԴP(s)ѡһĸP(s+1)
ִӽP(s+1)
P(s+1)иӦֵ
s= s+1
untilֹ
P(s)еøϵͳԤ⣻
end
4㷨ϸ
4.1ݵԤ
öάɢҶ任ͨͨ˲ƵɷԭʼݵĲ
4.2Ӧݻģ
(1) ʾ
ڴͳŴеα뷽ʽǽĵʾչһɵʽnΪ΢ַķ̸磺3δ֪ĳ΢ַ飺

ɱʾͼ1һʽ޶ΪD, øÿĽ临Ӷȣ


ͼ1΢̵ַĶʾ
(2) ӦֵĶ
ṩ(2)ʽĹ۲ݣԤõ󣬸ɱʾΪµĳ΢ַʽ

Ӧֵ fit(pi) Ĺ£
PROCEDUREpiӦֵ
begin
X*ͦXΪmn׾󣬽X(1)ĵһԪظX*ĵһУ
for i= 2 to m do
begin
X(1)ĵi-1ԪΪʼֵֵ㷨(6)ʽһX*ĵiԪأ
end
X= X(1)- X*
fit(pi)=X
end
ȻӦֵԽСԽãͬʱڼӦֵĹ,һЩɵĳ΢ַĽܲȶҪʹڵлֵʱ䷵һϴӦֵΪͷӶʹڽѡʱܿ챻̭ȺӦֵǲõǹ̶Ϊ0.01ĸĽŷ
(3) ģ͵ļ໯͹淶
ģ͵ļ໯ģȺÿṹÿɼֵĳЩ֣ıӦֵÿһݻи壬һֱӰ쵽ģͱŻĲĸ
ģ͵Ĺ淶ģ͵ԡ+򡰡Ϊ㣬ΪһĽṹʹģ͵S-ʽгλڡ+ ұߣڶͬģͽṹʶ𣬲ģ͵ĲŻʱa+xx+aaxxaжϳɲͬģͽṹظŻ
(4) ѡԺŴӵ
ùģΪ4ĽѡԲŲԣϴø屣ڵǰµȺУ
ӽ,ӽɷֳУӽδѡһΪӽӽԸÿԷ²ѡӽ㣬ӽΪӦõDΪԭѡһĶΪӽ  
ڱʱӦֵͬȡӦض̬ڱʵķʽ11ݣʹöڽϺõĽֲֻڽϲĽڽϴķΧ壬Ϊ

fmin ΪǰøӦֵfiΪiӦֵбʱѡһٶ²ѡһ㣬ɾԱΪһɵµԭһ𹹳˱
4.3ģ͵ĲŻ
(1) ʾ
ȶģ͵ĽṹбŻĽṹŻģڽвŻǰҪȷÿTi(i1n)еĲli¼ӦλãȺQ(t)еÿɱʾnάֱΪliʽ

Ciеÿcijʵķʽ
(2) ӦֵĶ
nһһӦشԭģ͵ӦУú4.2(2)ͬĹ̼ӦֵĴС
(3) ѡԺŴӵ
ú4.2(4)ͬѡԣ
ӽ

ӽʱζÿ(i1n)²ѡȡһӽλk (1kli)ٲӽԷһ(0,1)Ϊ

ӶγɵӽΪ

Ӳö༶12,13ݣ壮бʱζÿCi(i1n)²ѡȡһk(1kli)ٶԷcik015һjcikĶΪminmax,ķΪ

ӶγɵıΪ
4.4ϵͳԤ
ݻģ̵õģͺó΢ַһЩֵⷨ,ŷ-ȣX(1) һΪʼõԤУ
5ʵ
5.1ʵ
Ϊ鱾㷨ЧԣǷֱѡȡһάʵһάʵʵ飬ÿʵô㷨40Σɫϵͳ˱Ƚϣʵڱ586΢(166MHz)ϽУʵĲΪ
(1) Ӧݻģ̣
ն˼(nΪ΢ַз̵ĸcΪ)ȺģΪ100Ϊ4㷨100ֹͣ
(2) ģ͵ĲẒ̇
ȺģΪ20ӽʷֱΪ0.60.30.1ȺøӦֵ3ޱ仯ʱֹͣŻ
5.2ʵ 1
(1) ʵ
ף2ݣ1еġʵݡһ(˿xiĵλΪ) Ҫ17901930˿ΪʵݽѧģͲԤ19401950˿ֵ
(2) ʵ
ûɫϵͳĻɫGM(1,1)ģΪ dx/dt = 8.951490+0.205366x
ݻ㷨40ΣõļϺģΪ
ģ͢: dx/dt = (1.384360-(xt))((x+1.548616)20.574356) 
ģ͢: dx/dt = x(30.912327-(x0.151000))
ʽ dx/dt = 30.912327x-0.151000x2
ģ͢: dx/dt = ((x21.926580)+111.811684)cos(xt)
ģ͵Ľģ1
1ʵ1(ɫϵͳģݻģȽϱ)

ʵݻɫģݻģ͢ݻģ͢ݻģ͢
ꡡ ixiiiii
1790 
1800
1810
1820
1830
1840
1850
1860
1870
1880
1890
1900
1910
1920
19301
2
3
4
5
6
7
8
9
10
11
12
13
14
153.9
5.3
7.2
9.6
12.9
17.1
23.2
31.4
38.6
50.2
62.9
76.0
92.0
106.5
123.23.9000000
10.826068
13.294112
16.324833
20.046478
24.616570
30.228523
37.119865
45.582245
55.973862
68.734436
84.404175
103.646179
127.274902
156.2903443.535357
5.156120
7.570995
9.915323
13.087546
17.293678
22.678036
30.352379
40.267639
49.184601
62.618629
76.934494
91.309525
107.662506
122.2022553.535357
4.768738
7.238487
9.632812
12.867659
17.148132
22.613745
30.378368
40.369537
49.320061
62.753670
77.020882
91.324280
107.611816
122.1573793.535357
5.634524
7.929233
10.166016
13.206610
17.261953
22.490780
30.010643
39.829693
48.743813
62.287102
76.814316
91.436218
108.040558
122.736099
1940
195016
17131.7
150.7191.920593
235.673523131.699997
150.699997137.396286
150.477142137.936386
151.287262
46.3847813.0694543.0915223.350870
Ԥ104.1490335.6461935.7006466.263979
ݻ㷨ͳƽ(ƽֵ)=4.165328Ԥ=12.368071=9.575ʱ=1336 s


ɱ1ɼݻ㷨ɵõŵ΢ַģͣģ͵Ľṹʽģ͵ԤҲȻɫģСö࣮
Ȥǣģ͢ļ򻯽ף2вþģ(Logisticģ)õĽһµģף2ݰLogisticģͼ裺ʵȷеĳr=0.31, xm=197õģ

ģ͵ʽʱtĵλѡȡйأʶͬһݼͬʱ䵥λģͿܲͬ㷨õʼʱΪ0Ϊ0.01ŷֵ֣ʱ䵥λtLogisticģ100΢ַҶҲ100ʵʽȫһµģģͬģ͢ȫɼԶشӶ̬ϵͳĹ۲зֵģģ(11)Ǹݾģͽģߵһ˵˱ĵݻģ㷨Ϊ̬ݿ͹۹ɵԶṩһĹߣ
5.3ʵ 2
(1) ʵ
ף14ݣ2еġʵݡһx1 x2ֱΪй19781983ֵܲũҵֵܲ(λΪԪ)Ҫǰ5ݽѧģͲԤ1983ֵܲ
(2) ʵ
ף14ݽĻɫGM(1,2)ģΪ dx1/dt + 4.0879x1 = 14.9226x2
ݻ㷨һ΢ַģͣ40εõļϺģΪ
ģ
ģ
ģ
ģ͵Ľģ2
2ʵ2(ɫϵͳģݻģȽϱ)

ʵݻɫģݻģ͢ݻģ͢ݻģ͢
ix1ix2i1i1i2i1i2i1i2i
1978
1979
1980
1981
19821
2
3
4
56.846
7.642
8.531
9.071
9.9631.567
1.896
2.180
2.460
2.7856.846
5.698
8.052
8.983
10.1676.841975
7.662210
8.499115
9.084071
9.9684371.563206
1.890477
2.186530
2.467112
2.7749666.841975
7.661316
8.498152
9.083347
9.9680461.563206
1.876022
2.196958
2.472951
2.7718246.841975
7.659248
8.508387
9.114331
9.9111771.563206
1.868178
2.200855
2.464535
2.769078
1983611.0523.12111.39310.9143243.15119410.9165093.08618411.0205423.084314
2.01440.0433050.0518520.082981
Ԥ0.34100.1409480.1398930.048327
ͳƽ(ƽֵ)=0.191258Ԥ=0.317860T1=8.9 T2=8.65 ʱ=2062 s

Уɫģͣ Ԥ 
ݻģͣ Ԥ. 
Աȱ2нɼ㷨õģͶx1ϺԤ⾫ȾȻɫģҪߵö࣮ͬʱڻɫϵͳǹx1һ΢ַ̣ܷӳx2Ķ̬仯޷x2ֵϺԤ⣬Ԥ 1983ֵܲʱ֪1983ũҵֵܲҪGM(1,1)ԻعģͱȻǺܲģݻĳ΢ַģͲͬʱӳx1x2ʱtı仯ϵģͻɶһԤ⣬ԤЧҲϻɫϵͳã 
6
Բôͳ̬ϵͳ΢ַ̽ģѺʹڵĲ㣬ݻ㷨Ӧ֯ѧϰԣ˽ŴŴ㷨Ƕ׵ݻģ㷨ŴŻģͽṹŴ㷨ŻģͲɹʵ˶̬ϵͳĳ΢ַ齨ģԶʵô㷨ںʱɼԶֶŵĳ΢ַģͣеĽģ(ɫϵͳ)ȽϣнģܻԶģͽṹԸ㡢ϺԤľȸߵŵ㣮㷨оΪʵֶ̬ݵ֪ʶֹԶṩһĹߣԤгԤ⡢̬Ԥʱʱ䳡صʵеõƹӦã

Ŀ:õȻѧĿ69635030͹ҡ߼ĿĿ863-306-ZT06-06-3
߼飺ܺ죬Ů19721ʿоҪоΪŴơݻģͲм.ɽУ1934ڣʿʦҪоΪѧۡݻͲм.عŮ1942ҪоΪͼѧ.
ߵλܺ졡ɽع人ѧ̹صʵҡ人430072
ο
1Lucas W F. Differential Equation Models. New YorkSpringer-Verlag, 1983
2Դѧģ, ڶ森ߵȽ, 1993
(Jiang Qiyuan. Mathematical Models(in Chinese), Edition . Beijing: Education Press, 1993)
3ؽѫϵͳģѧģͣţѧ磬1995
(He Jianxun. System Modelling and Mathematical Models(in Chinese). Xiamen: Fujian Science & Technology Press, 1995)
4˾ɫϵͳ人йѧԺ磬1985
(Deng Julong. Grey Control Systems(in Chinese). Wuhan: Huazhong University of Science and Technology Press, 1985)
5Goldberg D E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MAAddison Welsey, 1989
6Mitchell M. An introduction to genetic algorithms. Cambridge, MA: MIT Press, 1996
7Koza J R. Genetic Programmingon the Programming of Computers by Means of Natural Selection. Cambridge, MAMIT Press, 1992
8Koza J R. Genetic Programming IIAutomatic Discovery of Reusable Programs. Cambridge, MAMIT Press, 1994
9Banzhaf W, Nordin P, Keller R E, Francone F D. Genetic Programming: An Introduction on the Automatic Evolution of Computer Programs and Its Applications. San Mateo, CA: Morgan Kaufmann, 1997
10Nash J C, Walker-Smith M. Nonlinear Parameter Estimation. New York: Marcel Dekker Inc, 1987
11Hinterding Robert, Michalewicz Zbigniew, Eiben Agoston. Adaptation in evolutionary computation: A survey. In: Baeck Thomas, Michalewicz Zbigniew, Yao Xin eds. Proceedings of the 4th Int'l Conference on Evolutionary Computation. Piscataway, NJ: IEEE Press, 1997. 6569
12Mhlenbein H, Schomisch M, Born J. The parallel genetic algorithm as function optimizer. Parallel Computing, 1991, 17, 619632
13Mhlenbein H, Schlierkamp-rose D. Predictive models for the breeder genetic algorithm. Evolutionary Computation, 1993, 1(1): 2549
14ܺˣ֣ҫģ˽񣮻ɫϵͳǳ,1988
(Cao Hongxing, Zheng Yaowen, Gu Jin. A Brief Introduction to Grey System Theory(in Chinese). Beijing: Meteorology Press, 1988)
յڣ1998-10-15
޸ڣ1999-04-26
