可计算一般均衡CGE模型的遗传算法研究

文章编号:1000-6788(2000)06-0001-07

系统工程理论与实践第6期　

可计算一般均衡CGE模型的遗传算法研究

李　彤,冯　珊,陈树衡

1

1

2

(1.华中理工大学控制工程系,湖北武汉430074;2.国立政治大学经济系,台北11623)

摘要:　简单讨论了求解CGE模型的早期Scarf算法和牛顿算法、以及新近流行的CGE模型求解工

具软件GAMS和GEMPACK中的典型算法,并且分别指出它们的优缺点;最后给出了一个基于模拟进化思想体系的CGE模型竞争求解算法,并给出了算例.

关键词:　可计算一般均衡模型;Scarf算法;牛顿算法;遗传算法中图分类号:　TP18　　a

AStudyonGeneticAlgorithmforComputableGeneralEquilibriumModel

112

LITong,FENGShan,CHENShu-heng

(1.DepartmentofAutomaticControlEngineering,HuazhongUniversityofScienceandTechnology,Wuhan430074;NationalChengchiUniversity,DepartmentofEconomics,Taipei,Taiwan,11623)

Abstract:　Inthispaper,theearlierScarfandNewtonAlgorithmforCGEadntypicalalgorithmincurrentmodelsolutionsoftwaretoolsasGAMSandGEMPACKaredis-cussed.Thestrongandweakpointsofthesealgorithmsasindicatedseparately.Also,Asimulationcasestudybasedonevolutionarytheoreticalsystemandcompetitivelysolvingapproachhasbeengivenattheendofthepaper.

Keywords:　computablegeneralequilibriummodel;Scarfalgorithm;Newtonalgo-rithm;geneticalgorithm

1　引言

自Walrasian一般均衡结构由一个抽象的经济描述转变为一个实用的经济分析工具以来,由于其方程的非线性和方程组规模较大,模型求解算法一直是研究者们所努力加以解决和改善的问题.早期,将一般均衡理论实际化的工作在很大程度上得益于Scarf的工作,他首先发明了一种保证收敛的计算一般均衡的方法,即不动点算法,这一工作使人们可以运用一般均衡方法分析实际问题并计算出数值解.此后,人们在其基础上提出了一些对不动点算法的修正,或者是提高其计算速度或者是使其更加简便灵活.另外,人们也大量采用一些虽然不能保证一定收敛,但实用效果比较好的算法,如牛顿法.近年来,求解CGE模型主要以GAMS和GEMPACK这两个软件包为代表,主要采用的是改进的牛顿法和逐段线性化的方法来求解模型.

随着计算机技术的飞速发展,虽然模型的求解已不是阻碍CGE模型应用的主要困难,但人们一直没有放弃寻找更简便有效的新算法.用计算机模拟生物界的进化过程的演化算法就是一个典型的代表.

在生物学研究中,进化论有着巨大的影响.生物界的自然进化过程实际上是基于生物种群的优化过程.“进化”这个优化思想并不仅仅局限于生命科学中,还可以更为广泛地在工程领域.社会经济领域中发

a

收稿日期:1998-10-24

资助项目:国家自然科学基金(NSF69674041)2

系统工程理论与实践2000年6月

现它的踪迹.用计算机来模拟进化过程导致了一些随机优化技术的出现.这些随机优化技术通常比传统的优化方法更能解决现实世界中的许多问题.因此,本文在讨论了传统的算法后,试图用模拟进化的方法给CGE模型一个竞争求解算法.

2　流行求解算法

2.1　早期的Scarf算法和和牛顿算法

Scarf不动点算法的主要步骤是对初始单纯形进行三角分割,然后运用“标记”原则和“替换”原则对单纯形顶点进行标记,所有的顶点都已标记后,即获得一近似的竞争均衡.在已完全标记的单纯形中选择任一点计算超额需求.当超额需求充分小时,即获得模型解.如果超过误差范围,可从新选择初始单纯形进行更细的三角分割,直至获得模型解.

不动点算法虽然能够保证模型的收敛,但是当超额需求方程数目较多时,不动点算法实现起来非常困难.因此,多数用不动点算法求解的CGE模型都是计算要素方面的超额需求,因为模型中的要素种类一般来说较少.但这样一来,算法不适用那种假设部门要素固定的CGE模型.而且,严格地说,不动点算法必须满足不动点定理的假设,也就是说那些存在着固定价格的模型同样不能适用于不动点算法.

牛顿法用对非线性方程组逐次线性近似的方法来求解模型.它可以表示为一个使下N个超额需求函数为零的问题;即找到价格P=(p1,…,pn)使得超额需求:

Gi(P)=0,i=1,…,n因子K对于CGE模型的求解是非常重要的.2.2　GAMS和GEMPACK中典型算法

GAMS和GEMPACK是目前流行的CGE模型求解工具软件,分别由世界银行和澳大利亚组织开发和应用.

1)GAMS/MINOS

GAMS中有多个求解工具,如MINOS用于求解非线性规划问题,ZOOM求解混合整数规划问题,以及PATH和MILLS求解混合补偿问题等.由于CGE模型中有大量的非线性方程,通常选用MINOS作为模型的求解工具.对CGE模型而言,GAMS/MINOS求解如下形式的问题:

minF(x)+cTx+dTy

x,y

(1)

　　这一方法并不能保证解的收敛,但在实际运用中却较为有效.经验表明,初始价格向量的选择和调整

(2)(3)(4)(5)

s.t.f(x)+A1y=b1A2x+A3y=b2lF

xyFu

其中c,d,b1,b2,l,u为常向量,A1,A2,A3是常系数矩阵,F(x)为一光滑的纯量函数,f(x)为一光滑的函数向量,它反映模型中的非线性部分的方程.x为非线性部分变量,y为线性部分变量.相应地称(3)式为非线性约束(4)式为线性约束,(5)式是变量的上下界.

设m,n分别表示整个约束和变量数目,m1和n1分别表示非线性约束和非线性部分变量数目,则A3具有m-m1行和n-n1列.

GAMS/MINOS用投影拉格朗日(projectedLagrange)算法[AnthonyBroodeetal.1992]解这一规划问题.这一算法通过循环求解线性约束的子问题来逼近非线性约束问题的解.其子问题的约束包括原问题的线性约束(4)式和非线性约束(3)式的线性化形式.

2)GEMPACK中的线性多步法

GEMPACK软件包采用多阶段线性模拟的方法来近似逼近模型的实际解.它将模型的外生变量的变化分解成多个小的变化,使模型计算结果接近实际值.

第6期

可计算一般均衡CGE模型的遗传算法研究3

3　CGE模型的遗传算法研究

3.1　CGE模型的解与进化

遗传算法是模拟进化算法的一种,它是从所求解的问题的一些相互竞争的试探解(trialsolutions)开始,通过随机地对现有的解产生变异来得到新的解,并用性能的一个目标测度来对每个试探解进行评价,得到每个试探解的“符合度”(fitness),然后再由某种选择机制来确定哪些解被保留下来作为后续子代(subsequentgeneration)的“父代”(parents)与其它模拟进化方法相比,遗传算法强调了染色体在进化中的变化及其所起的作用.

CGE模型中,均衡价格得到的过程实际上也是一个“适者生存”的过程,用模拟进化算法求解CGE模型不但可以得到均衡解,而且可以观察均衡解得到的过程,笔者相信对其“价格进化”过程的了解有助于说明实际经济领域中一些不易解释的现象.3.2　CGE模型的遗传算法(GA)研究

这节中将讨论怎样用遗传算法求解CGE模型,为方便讨论,考虑一个较为简单的CGE模型,设模型M个消费者、N种商品和两种生产要素(资本和劳动力),记Xmi为第m(m=1,…,M)个消费者对商品i(i=1,…,N)的需求,Lm,Km为消费者m对劳动力和资本生产两要素的贡献;pi,w,r(i=1,…,N)分别为商品和要素价格;Um(・)为消费者m的效用函数,并假设它是一个严格的凸函数;从消费方面来看应满足效用最大化条件:

m

maxUm(Xm1,…,XN)

N

s.t.

6

piX=wL+rK

m

t

mm

(6)

i=1

mm

　　由此可得到满足问题1)的一阶条件Xmi=Xi(p1,…,pN,r,w);由于U(・)为一严格凸函数,这意味

者问题(1)的解对价格而言是零次齐次函数.

从生产方面来看,N个厂商的生产函数为线性齐次函数:

Qj=Qj(Lj,Kj),j=1,…,N

求解其最小化成本问题即得要素的需求:

Lj=Lj(r,w,Qj)　Kj=Kj(r,w,Qj),j=1,…,N

它们对要素价格而言是零次齐次函数.

在这个简单的模型中,对于给定的价格使商品和要素的超额需求小于等于0即达到均衡状态.即

M

j

Xmj(p1,…,pN,r,w)-QF0,　j=1,…,N

M

(7)(8)

666

m=1N

L(r,w,Q)-K(r,w,Q)-j

j

jj

j=1N

6

LmF0,KkF0,

(9)

m=1

j=1

6

M

m=1

　　另外,若厂商的产出为正,则一般有利润为零的条件,对厂商j而言即满足:

pjQj=wLj(r,w,Qj)+rKj(r,w,Qj)

　　此时,Walras定理可以写为:

N

M

N

M

(10)

6

pjQ-

j

j=1

6

Xm

j+w

m=1

6

K-

j

j=1

6

K

m

=0(11)

m=1

并且,由于需求函数的齐次性,我们可以确定一个规范化价格,其它价格是该规范价格的相对价.

由以上分析可知,该模型的解空间可以归结为确定某几个商品的价格或生产要素的价格,用GA的语言描述即为给出初始商品价格或生产要素价格,在CGE模型世界中,价格通过竞争,优胜劣汰,最后得到最有“生命力”的价格,模型即达到均衡状态.下面我们以生产要素价格为例,归纳其计算步骤如下:

1)种群的构造4

系统工程理论与实践2000年6月

设种群数为G,根据实际情况,将G个备选初始解中的每一个编码为一个向量x,这个向量被称为染色体(chromosome),向量的各个分量被称为基因.

由于需求函数的零次齐次性,r和w都可以取相对价格,令r+w=1,则对r进行编码即可.

在这里我们可以选择十进制或二进制进行编码.如我们可以将模型的备选初始解编码为一个十进制n位数;也可以编码为二进制n位数,如n=30:100101000001111001000011110111,然后进行解码和规范化使02)目标函数的确定和解的适合度

集结的生产要素超额需求为我们目标函数,即求解问题minûQ+ûQK(r,w)ûL(r,w)û;为方便,记

Q(r,w)=ûQQ(12)K(r,w)û+ûL(r,w)û其中QK(r,w)=

6

K

K(r,w)-

j

j=1

6

M

K,QL(r,w)=

m

m=1

6

K

L(r,w)-

j

j=1

6

M

Lm;该优化问题即为

(13)

m=1

Q(r,w)=0

为使Q(r,w)较小的r,w具有较大的适合度,定义

f(r,w)=

1

1+Q(r,w)

(14)

　　我们称Q(r,w)为原始适合度(rawfitness),f(r,w)为选择适合度.

3)种群中的每一个染色体xk,k=1,2,…,G都被解码为一种适宜于进行评价的形式rk和wk,然后根据目标计算出适合度值f(rk,wk).

4)对每一个染色体都分配一个再生的概率pk,k=1,2,…,G,这个概率的取值使得某个染色体相对于种群中的其他染色体来说,它被选择的可能性正比于它的符合度.如果每个染色体的符合度都严格地是要极大化的正数,那么再生的概率可以用转轮选择(roulettewheelselection)机制来确定.由适合度值可以得出每一染色体的再生概率.

pk=

f(rk,wk)

6

G

　k=1,…,G(15)

f(rk,wk)

k=1

其中G为种群的总数,f(rk,wk)为第k个染色体的选择适合度.

5)根据已经分配了再生概率pk,k=1,2,…,G,通过在现有的染色体种群的随机地选择编码串来产生出一个新的染色体种群.被选择的染色体采用一定的遗传算子来产生子代,这样的遗传算子有交换(crossover)和位变异(bitmutation).交换是由两个父代染色体所进行的运算,在编码串上随机地选择一个位置,将第一个串在此位置前的部分与第二个串在此位置之后的部分拼接在一起,第一个串在此位置之后的部分与第二个串在此位置之前的部分拼接在一起,这样就得到了两个子代染色体.位变异为编码中每一位取值随机翻转提供了机会.交换和位变异的概率的典型取值范围分别为[0.6,0.95]和[0.001,0.01].6)如果一个满意的解被找到了即找到xB使Q(rB,wB)FD(D一般取0.001),或者达到了预定的循环计算次数,那么进化过程就终止进行.否则的话,返回步骤3),产生新的染色体并重进行计算循环.

在上述步骤中求解目标函数Q(r,w)的过程如下:

1)对于给定的r,w,计算厂商每单位产出的最小化要素需求,

LjjKj

=kj(r,w,1),j=1,2,…,Njl(r,w,1),　QQj

　　2)利用零利润条件,计算商品价格,

pj(r,w)=wlj(r,w,1)+rkj(r,w,1)

　　3)确定N个商品价格后,即可以计算商品需求,

m

Xmj(r,w)=Xj(p1(r,w),…,pN(r,w),r,w)　j=1,…,N;m=1,…,M　　4)计算满足市场需求的产出和要素需求,

Q(r,w)=(17)(18)(16)

6M

Xmj(r,w)　j=1,…,N(19)m=1

第6期

可计算一般均衡CGE模型的遗传算法研究

Lj(r,w)=lj(r,w,1)õQj(r,w),Kj(r,w)=kj(r,w,1)õQj(r,w)　j=1,…,N

5

(20)

　　5)计算要素超额需求

QK(r,w)=

再由(12)式即得Q(r,w).

3.3　CGE模型的遗传算法计算示例

为便于描述和具有比较性,用Shoven和Whalley(1984)求解过程的例子进行计算比较.模型结构和参数如表1所示.

表1　两个部门的CGE模型(ShovenandWhalley,1984)

A:需求

效用函数

Um=

(6i=1

2

m1/Lm(Lm-1)/Lm

A(xmi)i)

mm

L/(L-1)

6

N

K(r,w)-

j

j-1

6

M

K,QL(r,w)=

m

m=1

6

N

L(r,w)-

j

j=1

6

M

Lm

(21)

m=1

　　　　参数值

R,AR)=(0.5,0.5)(A12

需求函数

xmi=

-m-m(wLA+rKm)iPLi

m

(P,A1P)A2=(0.3,0.7)

(m=R,P)

(LR,LR)=(1.5,0.75)--(KR,KP)=(25,0.0)--(LR,LP)=(0.0,60)B:生产参数值

(51,52)=(1.5,2.0)(D1,D2)=(0.6,0.7)(R1,R2)=(2.0,0.5)

1L=jQj

5j

6

2mP(1-LAii

m

i=1

(m=R,P,　i=1,2)

生产函数

Q=5j[DjLj

j

(Rj-1)/Rj

要素需求函数

Dj+

(1-Dj)

Djr(1-Dj)w

(1-Rj)

(1-Rj)

Rj/(1-Rj)

]R/(R-j

j

1)

j)Kj　　+(1+D

jj

(R-1)/R

j=1,2

Kj=

1jQ5j

j

j(1-D)wDj(Dr)

Rj/(1-Rj)

+(1-Dj)

该模型只有两个最终产品、两种生产要素(资本K和劳动力L)和两类家庭消费群体(富人Rich和穷

人Poor).每种产品根据CES生产函数产生,每类消费群体需求来自满足财政预算的条件下极大化CES

-为具有的资产.5为生产规模参数,D为生产要效用函数.表中A为消费份额参数,L为消费替代弹性,-K,L素权重因素,R为要素替代弹性.

表2为利用其它方法(如牛顿算法、Scarf不动点算法等)求得的均衡数字解.

表2　Scarf不动点算法求得的均衡解(r+w=1)

r=0.5778;Qk(・)=0.0582;Ql(・)=-0.0797

r=0.5786;Qk(・)=0.0049;Ql(・)=-0.0068

　　在CGE模型的GA的算法中,设每代种群数G=30,染色体长度lchrom=30,经过6代就基本上

达到均衡解,下表是第0代、第6代、第15代的数据.

6

系统工程理论与实践

表3　CGE模型的GA算法:第0代

染色体

　　　r

适合度2000年6月

表4　CGE模型的GA算法:第6代

染色体

　　　r

适合度0.6936

1111100001010110100111001001010.9700720.00173500011110010111100101001100111110.2372540.01338830010001101100110001010011111110.1382780.00698631001110001011010011101110001010.6107550.1655871010101101100011011110101101110.6694870.06141771101110110101111001011100110110.8659540.01046110100000111000001010101111101110.2568560.01497060111000100101110010111111000110.4421140.0452661011010110111111111100111101010.709961100101001100010110011001100110.79057

0.04042240.0204249

0011101100101011110010100111110.2311370.01292120000110001001101000100110010000.04805110.00252510101111110100101101001110010110.3736210.02879771101110011011101000000110110000.9627470.01080231010101000011010001101011110000.620.06523310111011010101000011101110000110.4625080.0537990011001100000110011100011010010.1993170.01066611100110111010001011110000101000.8039780.01828340101001111011000011001000000100.3275210.02213340111101010010101110100001001010.4788470.061811010111110110001001011101101010.6862970.05099591001010001011100010100110100000.5795340.8835690100111101001010000110000111110.3097240.02006011110101001100101010110111011000.9156090.00579490001011111000111111111001111100.092530.004260011010001101010001110111110000.2047460.01103181011010011101010011011010010010.7067020.04167260011001110000110110110001111100.2012760.01079720001100010111111011110111011000.09667180.00482821011101010010011101110001010000.7288170.034127max.fitness=0.883569,r=0.579534

1001010011011101110100110100010.58151

1011110001011100010100110100000.7357840.03213441001010001011010011000110110110.5795040.8871311000011001001000010100110100000.5245410.10841000010011011101010001110100010.5190010.09990241001110001011100010100110100010.5910080.3438530001010000011100010100110100010.6107840.1654611001010001011101010100110100100.07855720.00395071011011001001001110110101100010.5795490.8817431001010011011100010001110100010.6107830.1654661011011001001001110110101100010.71200.039341001010011011100010001110100010.5814860.6982051001010101001100010100110100010.5831960.571001011001111101010110010000010.58785

0.413799

1001010001011100010000110100010.5795330.8836861001011001001100010100110100000.5871020.4346881001010011001100010100010110110.5812430.7169871001010001011100010100011110000.5795340.8835771001010001011100011110110110110.5795360.8832821001011001011010011101110000100.5873180.4284511011010001011100010100110100000.7045340.04253591001010001011100010001110100000.5795330.8836511001010001011100010100110100010.5795340.8835691001010000011100010100110100000.5785570.9820631001010001011110010100110100010.57950.8799241001010001011100011100110110110.5795360.883341001010001011000010100110100100.5794730.09551001010001011101010100110100010.5795490.8817431001010101111100001100110110010.5839260.5528631001010101011101010110010000010.5834560.576024max.fitness=0.982063,r=0.578557

表5　CGE模型的GA算法:第15代

染色体　　　r适合度0001010000001110010110001011000.07834390.00394051001010100001100100101111110000.582220.68791001010001011110010000111101010.5795630.8800291001010000111100010000000101110.579040.94671001010001011101010010010001010.5795480.8818111001010000011100010000000100100.578550.98121001011001011001001001010010000.5872980.4290251001010001001100101101111110000.579290.9131011000010001011001000011101100010.5169840.09695551001010000111000000110111101110.5780.9552451001010000111100011001010010000.5790570.9461681001010000011110010000111101110.578580.98661001010001001100010001001100010.5793040.9119941001010100001100000001001100100.582210.74471001010001001100010001001100010.57920.9139751001010000011101010001001100100.578570.9842051001010001001111110001101100000.5793420.9071611001010000011101110101000100100.578580.9854741000010001010101010001101100010.5169260.09687371101010000111100010000000101110.829040.0147684第6期

可计算一般均衡CGE模型的遗传算法研究续表5　CGE模型的GA算法:第15代

染色体

　　　r

适合度7

1001010001001100010100001011100.57920.9138871001010100001100010001001100100.582210.72011000010000111110010000111101110.5165750.0963791001010001001100010100001011000.579280.9138871001010001101010000001100101110.5797430.8591730001010001001100010100001011000.079280.00398561001010001001110100101111110000.5793240.9094451011010001101010000100001011000.704740.04245131001010001001100000001001100100.5792850.9144661001010001001110010001100101110.579310.910067

max.fitness=0.9866,r=0.578587

从表中可以看出,随着一代一代的进化,种群中适合度接近1的个体增多,并且很快能找到均衡解r=0.5786.

4　结语

CGE模型中,获得均衡价格的过程实际上可以视为是一个“适者生存”的过程,价格内生互动,最后得到的均衡价格是最适应模型所设定条件和规则的解.本文首先讨论了求解CGE模型的早期Scarf算法和牛顿算法、以及新近流行的CGE模型求解工具软件GAMS和GEMPACK中的典型算法,分别指出这些算法的优劣;提出了一个基于模拟进化思想体系的CGE模型竞争求解算法.给出了算法步骤.用模拟进化算法求解CGE模型是一个新的尝试,求解过程中不但可以得到均衡解,而且可以观察到均衡解得到的全过程.这种对其“价格进化”过程的了解有助于说明实际经济领域中一引进不易解释的现象,如均衡状态的“转化成本”等.参考文献

[1]　AdelmanI,RobinsonS.IncomeDistributionPolicyinDevelopingCountries[M].StanfordUniversi-tyPress,Stanford,CA,1978.

[2]　AnthonyBrooke,DavidKendrick,AlexanderMeeraus.GAMS:AUser'sGuide,Release2.25

[M].TheScientificPress,1992.[3]　ArrowKJandDebreuG.ExistenceofanEquilibriumforaCompetitiveEconomy[J].Econometrica1954,22:265～290.

[4]　CaiJun,FengShan,LiTong.AGA-BasedTrainingApproachforAppliedNeuralNetworks[A].

TheInternationalConferenceofGeneralSystemMethodologyandApplicationc[C].HUST,

Wuhan,1996.

[5]　ChenShuheng,FengShan,LiTong.SimulatingEnergyPoliciesviaComputableGeneralEquilibri-umModels[A].TheISCAInternationalConferenceonComputersandTheirApplications(CATA-97)[C].Tempe,Arizona,USAMarch13～15,1997.[6]　CosiG,PearsonKR.GEMPACK:General-purposeSoftwareforAppliedGeneralEquilibriumand

OtherEconomicModelers[J].ComputerScienceinEconomicsandManagement,1:1～207.[7]　FogelDB.AnIntroductiontoSimulatedEvolutionaryOptimization[J].IEEETransactionsonNeu-ralNetworks,1994,5(1):3～12.[8]　JohnBShoven,JohnWhalley.ApplyingGeneralEquilibrium[M].CambridgeUniversityPress,

1984.