第33卷 第1期2005年1月西北农林科技大学学报(自然科学版)
Jo ur. of N or thw est Sci-T ech U niv. o f A gr i. and Fo r. (N at. Sci. Ed. ) V ol. 33N o. 1
Jan. 2005
约束优化问题的遗传算法求解
宋松柏, 蔡焕杰, 康 艳
(西北农林科技大学水利与建筑工程学院, 陕西杨凌712100)
X
[摘 要] 应用遗传算法基本原理, 采用锦标赛选择、算术交叉、均匀交叉、均匀变异和非均匀变异算子, 设计了一般非线性规划和整数规划问题的通用求解算法, 应用M atlab 6. 0编制了相应的求解软件。实例测试结果表明, 该算法可以应用于一般的非线性规划和整数规划问题。
[关键词] 非线性规划; 整数规划; 约束优化; 遗传算法[中图分类号] O 224 [文献标识码] A
[文章编号] 1671-9387(2005) 01-0150-05
目前, 应用遗传算法(Genetic Alg orithm , GA) 处理有约束优化问题尚无统一的方法。常用的处理约束方法有修复不可行解法、改变遗传算子法和惩罚函数法[1～6]。修复不可行解法的主要缺点是不同类的求解问题有不同的修复算法, 修复算法依赖于所求问题; 改变遗传算子法在求解复杂的非线性优化问题及设计相应的遗传算子时是非常困难的; 惩罚函数法针对不可行解的个体, 在计算个体适应度时, 施加某种惩罚, 降低该个体的适应度, 使其被遗传到下一代群体的机会减少, 经过若干次迭代计算, 种群最后逐渐收敛于可行解。
因此, 实际中应用GA 求解约束优化问题时, 往
目标函数约束条件
往是根据具体优化模型中约束条件的特征, 选择适合的遗传算子或设计相应的遗传算子, 选用上述方法进行优化问题的求解。本研究基于Fernando Jim nez
[7]
的研究, 对一般非线性规划(Nonlinear
Prog ramming Problem , NPP ) 和整数规划(Integ ral Prog ramming Problem , IPP) 约束优化问题的GA 求解进行探讨, 应用M atlab 6. 0编制了相应的求解软件。以期为非线性规划和整数规划问题求解提供参考。
1 N PP 和IPP 问题求解的标准形式
NPP 和IPP 问题求解的标准形式可以表示为:
Min f (x 1, …, x j , …, x n )
i =1, 2, …, m j =1, 2, …, n
(1)
l j ≤x j ≤u j ,
g i (x 1, …, x j , …, x n ) ≤0,
式中, m , n 分别为约束数和决策变量数; x 1, …, x j , …, x n 为决策变量, 对于整数规划, 取值为介于[l j , u j ]的整数值, 其中[l j , u j ]为变量的取值范围; g i (x 1, …, x j , …, x n ) 为不等式约束左边项, 左边项可以是线性, 也可以是非线性。
采用以下方法将一般模型转换为标准形式。
(1) 目标函数最大化
对于目标函数最大化问题, 可用其负值的最小化问题替代, 求解后, 将结果再反号, 则为原目标函数的最大化值。即Max f (x 1, …, x j , …, x n ) =-{Min f (x 1, …, x j , …, x n ) }。
(2) 约束为“≥0”的形式
X [收稿日期] 2003-12-08
若约束为g i (x 1, …, x j , …, x n ) ≥0的形式, 两边
同乘以-1, 则可转换为-g i (x 1, …, x j , …, x n ) ≤0的形式。
(3) 约束为“=0”的形式
若约束为g i (x 1, …, x j , …, x n ) =0的形式, 可用替代, 对于
g i (x 1, …, …, x j , …, x n ) ≥0
g i (x 1, …, x j , …, x n ) ≥0, 可用方法(2) 转换为-g i (x 1, …, x j , …, x n ) ≤0, 因此, g i (x 1, …, x j , …, x n ) =0g i (x 1, …, x j , …, x n ) ≤0。
-g i (x 1, …, x j , …, x n ) ≤0
2个约束
g i (x 1, …, x j , …, x n ) ≤0
[基金项目] 国家自然科学基金资助项目(50179031) ; 高等学校全国优秀博士学位论文作者专项基金(200052); 西北农林科技大学2004
([) , , ,
第1期宋松柏等:约束优化问题的遗传算法求解
151
2 N PP 和IPP 问题的GA 求解
NPP 和IPP 问题的GA 算法步骤如下所述。2. 1 NPP 问题的GA 算法
2. 1. 1 初始化群体 在满足式(1) 约束条件的解空间, 选择一个初始解x 0=(x 1, x 2, …, x j , …, x n ) 作为初始群体个体Star t -population (i ) , i =1, 2, …, Po psize 。初始群体为演化计算, 可提供初始的“良种”。2. 1. 2 评价群体适应度 将初始群体代入式(1) 目标函数中, 计算相应的适应度Start -population(i ). Fitness , 按照可行性判别条件, 判别个体可行状态Star t -population (i ). Feasible , i =1, 2, …, Popsize 。以Feasible =1表示个体为可行解, Peasible =0表示个体为不可行解。
2. 1. 3 置当前遗传代数 置Current -gen=1。2. 1. 4 选择最优个体 由于式(1) 为目标函数最小化问题, 因此, 在群体大小为Popsize 的初始群体Star t -population(i ) , i =1, 2, …, Popsize, 选择适应度Start -population (i ). Fitness 最小, 且满足Start -po pulatio n (i ). Feasible =1的个体作为最优个体Best -individual, 并把该个体的适应度和解的可行状态赋给Best -individual. Fitness 和Best -individual. Feasible 。
2. 1. 5 最优个体遗传到新一代群体 置当前个体序号s =1, 将最优个体Best -individual 赋给新一代群体的第1个个体New -po pulation (1) , 其中s =
s +1。
2. 1. 6 选 择 采用锦标赛选择(T ournament Selection) , 首先在[1, Popsize]内随机产生tourn 个个体序号{k 1, k 2, …k tourn }, 按照最优保存策略(Elitism Strateg y ) 选取个体m ate 1和m ate 2。本文约定最优保存策略的原则为:¹2个可行解个体, 其评价适应度值小的个体优于评价适应度值大的个体; º不可行解个体在遗传过程中被淘汰。按照上述选择, 使群体在遗传过程中, 始终保持“良种”。因此, 对于tour n 个可行解个体, 则适应度值最小的个体将被最后选择遗传到下一代群体。
2. 1. 7 交 叉 交叉算子采用算术交叉(Arithmetic Cro ssover ) , 个体m ate 1和mate 2算术交叉, 产生2个个体child1和child2为:
child1=r õmate2+(1-r ) õmate1
(2)
child2=r õmate1+(1-r ) õmate2式中, r 为界于[0, 1]的随机数。
2. 1. 8 变 异 变异采用非均匀变异(Non uniform Mutation ) , 对于个体child 1和child 2分别进行非均匀变异, 则变异后分别产生2个个体o ffspring 1和o ffspring2。假定个体child1进行非均匀变异, 产生个体o ffspring1。
设child 1=x 1x 2, …x k , …, x n , 非均匀变异后产生的个体为offspring 1=x 1x 2, …, x ′k , …, x n , 若变异点x k 处的基因值取值范围为[l k , u k ], 则新的基因值
′
x k 由下式确定:
(3) b
x k -(x k -l k ) r 1-if random(0, 1) =1T
式中, r 为界于[0, 1]的随机数; T 为最大遗传代数; g en +1 重复执行步骤(4) ～(11) , 直至终止代数t 为当前遗传代数; b 为非均匀度参数; rando m (0, 1) M ax gen 。当输出最优个体Best -indiv idual 时, 停止表示产生0或1的随机数。
2. 1. 9 将o ffspr ing 1和o ffspr ing2分别赋给新一代群体的New -population (s ) New -po pulatio n (s ) =offspring 1, s =s +1, New -population (s ) =offspring 2, 至此, 步骤(6) ～(9) 完成产生2个新一代群体个体的过程。重复步骤(6) ～(9) , 直至产生Po psize 个个体。
2. 1. 10 评价群体适应度 将新一代群体的N ew -po pulatio n(s ) 赋给Start -population(s ) , s =1, 2, …, Po psize 。适应度计算同步骤(2) 。
2. 遗传计算。
2. 2 IPP 问题的GA 求解
IPP 和N PP 问题求解的差别在于某些遗传算子的选择。
2. 2. 1 选 择 选择算子同NPP 问题, 采用锦标赛选择。
2. 2. 2 交 叉 交叉算子采用均匀交叉(Unifor m Cro ssover) 。均匀交叉是指2个配对个体的每一个基因座上的基因都以相同的交叉概率进行交换, 从而形成2个新的个体[1]。对于个体m ate1和mate2进行2,
x =
′
k
x k +(u k -x k ) r 1-T
b
if random(0, 1) =0
152
[1]
西北农林科技大学学报(自然科学版) 第33卷
其交叉的主要过程为:
¹随机产生与个体编码长度等长的屏蔽字W =w 1w 2…w j …w n 。
º个体mate 1和mate 2按下述规则产生2个新的个体child1和child2。
若w j =0, 则child1在j 个基因座的基因值继承mate 1上对应的基因值; child 2在j 个基因座的基因值继承mate2上对应的基因值。
若w j =1, 则child1在j 个基因座的基因值继承mate2上对应的基因值; child2在j 个基因座的基因值继承mate 1上对应的基因值。
2. 2. 3 变 异 变异算子采用均匀变异(U niform M utatio n) 。均匀变异是指分别用符合某一范围内均匀分布的随机数, 用某一较小的概率来替换个体编码串中各个基因座上原有的基因值[1]。假定个体child1=x 1x 2…x k …x n 进行均匀变异, 产生的个体为offspring 1=x 1x 2…x k …x n , 若变异点x k 处的基因值取值范围为[l k , u k ], 则新的基因值x k 可由下式确定:
x k =int(l k +r (u k -l k ) )
(4)
式中, r 为介于[0, 1]的随机数; int 为取整函数。
′
′
(2)
M in f (x 1, x 2) =-x 1-x 2
432
x 2≤2x 1-8x 1+8x 1+2
32
x 2≤4x 41-32x 1+88x 1-96x 1+360≤x 1≤30≤x 2≤4 问题(3)
M ax f (x 1, x 2, x 3) =3x 1+x 2-2x 3+0. 8
+
2x 1-2x 2+x 31237x 1+3x 2-x 3x 1+x 2-x 3≤1
-x 1+x 2-x 3≤-112x 1+5x 2+12x 3≤34. 8
12x 1+12x 2+7x 3≤29. 1 -6x 1+x 2+x 3≤-4. 1x 1, x 2, x 3≥0 问题(4)
4i =1
4
2i
i =1
9
M in f (x , y ) =5∑x i -5∑x -∑y
i =1
i
3 实例应用
按前文所述的计算流程, 应用M atlab 6. 0编制了相应的求解程序。以下就几个实例应用说明本文算法的适用性。
3. 1 NPP 优化问题实例应用
问题(1)
M in f (x 1, x 2) =(x 1-10) +(x 2-20) (x 1-5) 2+(x 2-5) 2-100≥0
-(x 1-6) 2-(x 2-5) 2+82. 81≥013≤x 1≤1000≤x 2≤100
3
3
2x 1+2x 2+y 6+y 7≤102x 1+2x 3+y 6+y 8≤102x 2+2x 3+y 7+y 8≤10-8x 1+y 6≤10-8x 2+y 7≤0-8x 3+y 8≤0
-2x 4-y 1+y 6≤0-2y 2-y 3+y 7≤0-2y 4-y 5+y 8≤00≤x i ≤1 i =1, 2, 3, 4
0≤y i ≤1 i =1, 2, 3, 4, 5, 9y i ≥0 i =6, 7, 8
选取群体大小Popsize=100, 锦标赛选择个体数tour n =20, 交叉概率p c =0. 4, 变异概率p m =0. 2, 遗传终止代数M ax gen =1000, E =0. 00001。上述优化问题(1) ～(4) 的求解结果如表1所示。
表1 N PP 优化问题求解实例对比结果
T able 1 T he compar ativ e solut ion o f NP P betw een optimizat ion v alues and G A p s m ethods
优化问题
Optim um problems 问题1Problem 1问题2Problem 2问题3Problem 3
准确解Analys is res ults
x 1=14. 1; x 2=0. 8; f =-6962. 5x 1=2. 3295; x 2=3. 1783; f =-5. 5079x 1=1; x 2=0; x 3=0; f =-2. 471428x 1=0; x 2=1; x 3=1; x 4=4
问题4Problem 4
y 1=1; y 2=1; y 3=1; y 4=1; y 5=1y 6=3; y 7=3; y 8=3; y 9=1; f =-15
GA 求解结果GA p s res ults
x 1=14. 098; x 2=0. 801; f =-6962. 498x 1=2. 3297; x 2=3. 1788; f =-5. 5085
x 1=0. 9995; x 2=0. 0003; x 3=0. 0000; f =-2. 4721x 1=0. 0000; x 2=1. 0000; x 3=1. 0000; x 4=4. 0000
y
1=1. 0000; y 2=1. 0000; y 3=1. 0000; y 4=1. 0000; y 5=1. 0000; y 6=3. 0001; y 7=3. 0004; y 8=3. 0002; y 9=1. 0000; f =
-15. 0002
第1期宋松柏等:约束优化问题的遗传算法求解
k ) (T 1i ≤-i ≤T M ax 9
M 1≤k ≤9
i ≠k
153
3. 2 IPP 优化问题实例应用
问题(1)
M in
f (x 1, x 2, x 3) =3x 1-2x 2+5x 3
x 1+2x 2-x 3≤2x 1+4x 2+x 3≤4
x 1+x 3≤34x 2+x 3≤6x 1, x 2, x 3={0, 1}
问题(2)
M ax
f (x 1, x 2) =60x 1+30x 2
35x 1+8x 2≤4001. 5x 1+3. 5x 2≤604x 1+5x 2≤90x 1≥0, x 2≥0x 1, x 2取整数
问题(3) 为灌溉渠道轮灌配水优化模型[8], 如下所示, 共有9×26=234个决策变量, 9+2×26=61个约束变量。
表2 I PP 优化问题求解实例对比结果
-26
∑t x
j j =1
9
ij
-336≤0i =1, 2, …, 9
∑x
i =1
9i =1
ij
-1≤0j =1, 2, …, 26
∑x
ij
+1≤0j =1, 2, …, 26
i =1, 2, …, 9; j =1, 2, …, 26
x ij ={0, 1}
式中, x ij 为轮灌组出水口的开关状态, 为决策变量, 其中x ij ={0, 1}, x ij =0表示出水口关闭, x ij =1表示出水口开启; 26为出水口(配水渠道) 数; 9为轮灌组划分数; t j 为出水口引取水量所需的时间(h) 。选取群体大小Popsize=100, 锦标赛选择个体数tour n =20, 交叉概率p c =0. 3, 变异概率p m =0. 2, 遗传终止代数M axg en =1000, E =0. 001。上述优化问题(1) ～(2) 的求解结果如表2所示。
T able 2 T he compar ativ e so lution of L I PP betw een optimiza tio n v alues and G A p s methods
优化问题
Optimum problems 问题1Pr ob lem 1问题2Pr ob lem 2
准确解Analysis results x 1=1; x 2=0; x 3=1; f =8x 1=9; x 2=10; f =840
GA 求解结果GA p s r esu lts x 1=1; x 2=0; x 3=1; f =8x 1=9; x 2=10; f =840
优化问题(3) 中各轮灌组引水时间和目标函数值与文献[8]结果对比列于表3。
表3 文献[8]模型与文中模型求解结果对比
T able 3 T he co mpa rative o pt imization results betw een the models in lit eratur e [8]and in this paper
文献[8]模型优化结果Results of literature p model[8]
轮灌组引水时间/h Irr igation tim e of rotation irrigation group
[***********][1**********]
轮灌组引水流量/(m 3・s -1) Flow of of rotation irrigation g roup
0. 20. 20. 20. 20. 20. 20. 20. 20. 2
本文模型优化结果Results of this pap er model
轮灌组引水时间/h Irrigation time of rotation irrigation g roup
[***********]3293293297
轮灌组引水流量/(m3・s -1) Flow of of rotation irr igation group
0. 20. 20. 20. 20. 20. 20. 20. 20. 2
轮灌组Rotation irrigation gr ou p 轮灌组斗口组合Lateral canal combination 轮灌组Rotation irr igation group 轮灌组斗口组合Lateral canal combination
123456789
新10, 9, 新7, 311, 10, 4, 217, 1419, 723, 22, 16退水, 12, 821, 15, 13, 52018, 6, 1目标函数Target function
123456789
202, 145, 16, 239, 15, 18, 21, 22
3, 4, 17, 新206, 11, 137, 198, 12, 退水1, 新7, 10, 目标函数T ar get function
对比表1, 表2和表3可以看出, 本文GA 优化结果与其准确解参考值完全一致, IPP 问题(3) 的优化
154
西北农林科技大学学报(自然科学版) 第33卷
解NPP 、IPP 问题的算法是稳定的。
4 结 论
GA 求解约束优化问题是GA 研究中的热门问题之一。本文采用锦标赛选择、算术交叉、均匀交叉、均匀变异和非均匀变异算子, 应用M atlab 6. 0编制
了相应的求解程序。通过几个实例的数值试验, 计算
结果表明, 文中GA 优化结果与准确解一致, 具有较强的通用性、精确性和稳健性。由于遗传算法目前是一个正在探索研究的算法, 因此如何提高本文算法的性能及更好地进行运行参数选择等, 有待于进一步研究。
[参考文献]
[1] 周 明, 孙树栋. 遗传算法原理及应用[M ]. 北京:国防工业出版社, 1999. 33-64.
[2] 孙艳丰, 郑家齐, 王德兴, 等. 基于遗传算法的约束优化方法评述[J ]. 北方交通大学学报, 2000, 24(6) :14-19.
[3] M ichalew icz Z A. Survey of constraint handling techniques in evolutionary com putation methods[A]. M cDon nell J R, Reynolds R G, Fogel
D B. Processin g 4th an nual conference evolutionary p rog ramm ing[C]. Cambridge, M A:M IT Press , 1995. 135-155.
[4] M ichalew icz Z, Schoen auer M. Evolution ary algorithm s for constrained paprameter optimization problems [J]. Evolutionary Compution,
1996, 4(1) :1-32.
[5] M ichalew icz Z , Deb K , Sch midt M , et al . Evolu tionary alg orith ms for eng ineering application [A ]. M iettinen K , Neittaan m k i P , M kel M
M , et al. Evolutionary algorith ms in engin eering and com puter science[C]. Ch ichester, England:J oh n W iley and Sons , 1999. 73-94. [6] Zbigniew M ichalew icz, M artin Schmidt. TCG-2:A tes t-case generator for non-lin ear param eter optimisation techniques [A ]. I Ashis h
Ghosh, S higeyos hi Ts utsui. Advances in evolu tionary compu tin g, th eory an d applications [C]. Heidelberg, Germ any :S pringer, 2003. 193-212.
[7] Fernando Jim nez , J os L Ver degay . Evolution ary techn iques for cons trained optimization problem [A ]. Hans -J rgen Zimm ermann . 7th
eur op ean congress on intelligen t techniques an d s oft computing (EU FIT p 99) [C]. Aachen, Germ any:S pringer, 1999. [8] 吕宏兴, 熊运章, 汪志农. 灌溉渠道支斗渠轮灌配水与引水时间优化模型[J]. 农业工程学报, 2000, 16(6) :43-46.
Genetic algorithm solution for co nstrained optimization
SONG Song -bai , CAI Huan -jie , KANG Yan
(College of Water Resources and A rchi tectural Engineering , N orthwest A &F Univ ersity , Yangling , Shaanx i 712100, China )
Abstract :Based on the principles of g enetic alg orithm , the g eneral GA methods for No n Linear Pro gram ming and Integral Prog ramm ing w er e desig ned by using operators such as To urnament Selection, Arithm etic Crossover , U niform Crossov er , Uniform M utation and No n Uniform M utation. Using M atlab 6. 0, the co mputatio n prog ram o f GA has been developed. Finally , T he GA for Non Linear Progr am ming and Integ ral Prog ramm ing is tested by som e ex am ples and the results show that the alg orithm in this paper is feasible and stable.
Key words :non linear progr amming; integral prog ramming; co nstrained optim izatio n problem ; genetic algo rithm
第33卷 第1期2005年1月西北农林科技大学学报(自然科学版)
Jo ur. of N or thw est Sci-T ech U niv. o f A gr i. and Fo r. (N at. Sci. Ed. ) V ol. 33N o. 1
Jan. 2005
约束优化问题的遗传算法求解
宋松柏, 蔡焕杰, 康 艳
(西北农林科技大学水利与建筑工程学院, 陕西杨凌712100)
X
[摘 要] 应用遗传算法基本原理, 采用锦标赛选择、算术交叉、均匀交叉、均匀变异和非均匀变异算子, 设计了一般非线性规划和整数规划问题的通用求解算法, 应用M atlab 6. 0编制了相应的求解软件。实例测试结果表明, 该算法可以应用于一般的非线性规划和整数规划问题。
[关键词] 非线性规划; 整数规划; 约束优化; 遗传算法[中图分类号] O 224 [文献标识码] A
[文章编号] 1671-9387(2005) 01-0150-05
目前, 应用遗传算法(Genetic Alg orithm , GA) 处理有约束优化问题尚无统一的方法。常用的处理约束方法有修复不可行解法、改变遗传算子法和惩罚函数法[1～6]。修复不可行解法的主要缺点是不同类的求解问题有不同的修复算法, 修复算法依赖于所求问题; 改变遗传算子法在求解复杂的非线性优化问题及设计相应的遗传算子时是非常困难的; 惩罚函数法针对不可行解的个体, 在计算个体适应度时, 施加某种惩罚, 降低该个体的适应度, 使其被遗传到下一代群体的机会减少, 经过若干次迭代计算, 种群最后逐渐收敛于可行解。
因此, 实际中应用GA 求解约束优化问题时, 往
目标函数约束条件
往是根据具体优化模型中约束条件的特征, 选择适合的遗传算子或设计相应的遗传算子, 选用上述方法进行优化问题的求解。本研究基于Fernando Jim nez
[7]
的研究, 对一般非线性规划(Nonlinear
Prog ramming Problem , NPP ) 和整数规划(Integ ral Prog ramming Problem , IPP) 约束优化问题的GA 求解进行探讨, 应用M atlab 6. 0编制了相应的求解软件。以期为非线性规划和整数规划问题求解提供参考。
1 N PP 和IPP 问题求解的标准形式
NPP 和IPP 问题求解的标准形式可以表示为:
Min f (x 1, …, x j , …, x n )
i =1, 2, …, m j =1, 2, …, n
(1)
l j ≤x j ≤u j ,
g i (x 1, …, x j , …, x n ) ≤0,
式中, m , n 分别为约束数和决策变量数; x 1, …, x j , …, x n 为决策变量, 对于整数规划, 取值为介于[l j , u j ]的整数值, 其中[l j , u j ]为变量的取值范围; g i (x 1, …, x j , …, x n ) 为不等式约束左边项, 左边项可以是线性, 也可以是非线性。
采用以下方法将一般模型转换为标准形式。
(1) 目标函数最大化
对于目标函数最大化问题, 可用其负值的最小化问题替代, 求解后, 将结果再反号, 则为原目标函数的最大化值。即Max f (x 1, …, x j , …, x n ) =-{Min f (x 1, …, x j , …, x n ) }。
(2) 约束为“≥0”的形式
X [收稿日期] 2003-12-08
若约束为g i (x 1, …, x j , …, x n ) ≥0的形式, 两边
同乘以-1, 则可转换为-g i (x 1, …, x j , …, x n ) ≤0的形式。
(3) 约束为“=0”的形式
若约束为g i (x 1, …, x j , …, x n ) =0的形式, 可用替代, 对于
g i (x 1, …, …, x j , …, x n ) ≥0
g i (x 1, …, x j , …, x n ) ≥0, 可用方法(2) 转换为-g i (x 1, …, x j , …, x n ) ≤0, 因此, g i (x 1, …, x j , …, x n ) =0g i (x 1, …, x j , …, x n ) ≤0。
-g i (x 1, …, x j , …, x n ) ≤0
2个约束
g i (x 1, …, x j , …, x n ) ≤0
[基金项目] 国家自然科学基金资助项目(50179031) ; 高等学校全国优秀博士学位论文作者专项基金(200052); 西北农林科技大学2004
([) , , ,
第1期宋松柏等:约束优化问题的遗传算法求解
151
2 N PP 和IPP 问题的GA 求解
NPP 和IPP 问题的GA 算法步骤如下所述。2. 1 NPP 问题的GA 算法
2. 1. 1 初始化群体 在满足式(1) 约束条件的解空间, 选择一个初始解x 0=(x 1, x 2, …, x j , …, x n ) 作为初始群体个体Star t -population (i ) , i =1, 2, …, Po psize 。初始群体为演化计算, 可提供初始的“良种”。2. 1. 2 评价群体适应度 将初始群体代入式(1) 目标函数中, 计算相应的适应度Start -population(i ). Fitness , 按照可行性判别条件, 判别个体可行状态Star t -population (i ). Feasible , i =1, 2, …, Popsize 。以Feasible =1表示个体为可行解, Peasible =0表示个体为不可行解。
2. 1. 3 置当前遗传代数 置Current -gen=1。2. 1. 4 选择最优个体 由于式(1) 为目标函数最小化问题, 因此, 在群体大小为Popsize 的初始群体Star t -population(i ) , i =1, 2, …, Popsize, 选择适应度Start -population (i ). Fitness 最小, 且满足Start -po pulatio n (i ). Feasible =1的个体作为最优个体Best -individual, 并把该个体的适应度和解的可行状态赋给Best -individual. Fitness 和Best -individual. Feasible 。
2. 1. 5 最优个体遗传到新一代群体 置当前个体序号s =1, 将最优个体Best -individual 赋给新一代群体的第1个个体New -po pulation (1) , 其中s =
s +1。
2. 1. 6 选 择 采用锦标赛选择(T ournament Selection) , 首先在[1, Popsize]内随机产生tourn 个个体序号{k 1, k 2, …k tourn }, 按照最优保存策略(Elitism Strateg y ) 选取个体m ate 1和m ate 2。本文约定最优保存策略的原则为:¹2个可行解个体, 其评价适应度值小的个体优于评价适应度值大的个体; º不可行解个体在遗传过程中被淘汰。按照上述选择, 使群体在遗传过程中, 始终保持“良种”。因此, 对于tour n 个可行解个体, 则适应度值最小的个体将被最后选择遗传到下一代群体。
2. 1. 7 交 叉 交叉算子采用算术交叉(Arithmetic Cro ssover ) , 个体m ate 1和mate 2算术交叉, 产生2个个体child1和child2为:
child1=r õmate2+(1-r ) õmate1
(2)
child2=r õmate1+(1-r ) õmate2式中, r 为界于[0, 1]的随机数。
2. 1. 8 变 异 变异采用非均匀变异(Non uniform Mutation ) , 对于个体child 1和child 2分别进行非均匀变异, 则变异后分别产生2个个体o ffspring 1和o ffspring2。假定个体child1进行非均匀变异, 产生个体o ffspring1。
设child 1=x 1x 2, …x k , …, x n , 非均匀变异后产生的个体为offspring 1=x 1x 2, …, x ′k , …, x n , 若变异点x k 处的基因值取值范围为[l k , u k ], 则新的基因值
′
x k 由下式确定:
(3) b
x k -(x k -l k ) r 1-if random(0, 1) =1T
式中, r 为界于[0, 1]的随机数; T 为最大遗传代数; g en +1 重复执行步骤(4) ～(11) , 直至终止代数t 为当前遗传代数; b 为非均匀度参数; rando m (0, 1) M ax gen 。当输出最优个体Best -indiv idual 时, 停止表示产生0或1的随机数。
2. 1. 9 将o ffspr ing 1和o ffspr ing2分别赋给新一代群体的New -population (s ) New -po pulatio n (s ) =offspring 1, s =s +1, New -population (s ) =offspring 2, 至此, 步骤(6) ～(9) 完成产生2个新一代群体个体的过程。重复步骤(6) ～(9) , 直至产生Po psize 个个体。
2. 1. 10 评价群体适应度 将新一代群体的N ew -po pulatio n(s ) 赋给Start -population(s ) , s =1, 2, …, Po psize 。适应度计算同步骤(2) 。
2. 遗传计算。
2. 2 IPP 问题的GA 求解
IPP 和N PP 问题求解的差别在于某些遗传算子的选择。
2. 2. 1 选 择 选择算子同NPP 问题, 采用锦标赛选择。
2. 2. 2 交 叉 交叉算子采用均匀交叉(Unifor m Cro ssover) 。均匀交叉是指2个配对个体的每一个基因座上的基因都以相同的交叉概率进行交换, 从而形成2个新的个体[1]。对于个体m ate1和mate2进行2,
x =
′
k
x k +(u k -x k ) r 1-T
b
if random(0, 1) =0
152
[1]
西北农林科技大学学报(自然科学版) 第33卷
其交叉的主要过程为:
¹随机产生与个体编码长度等长的屏蔽字W =w 1w 2…w j …w n 。
º个体mate 1和mate 2按下述规则产生2个新的个体child1和child2。
若w j =0, 则child1在j 个基因座的基因值继承mate 1上对应的基因值; child 2在j 个基因座的基因值继承mate2上对应的基因值。
若w j =1, 则child1在j 个基因座的基因值继承mate2上对应的基因值; child2在j 个基因座的基因值继承mate 1上对应的基因值。
2. 2. 3 变 异 变异算子采用均匀变异(U niform M utatio n) 。均匀变异是指分别用符合某一范围内均匀分布的随机数, 用某一较小的概率来替换个体编码串中各个基因座上原有的基因值[1]。假定个体child1=x 1x 2…x k …x n 进行均匀变异, 产生的个体为offspring 1=x 1x 2…x k …x n , 若变异点x k 处的基因值取值范围为[l k , u k ], 则新的基因值x k 可由下式确定:
x k =int(l k +r (u k -l k ) )
(4)
式中, r 为介于[0, 1]的随机数; int 为取整函数。
′
′
(2)
M in f (x 1, x 2) =-x 1-x 2
432
x 2≤2x 1-8x 1+8x 1+2
32
x 2≤4x 41-32x 1+88x 1-96x 1+360≤x 1≤30≤x 2≤4 问题(3)
M ax f (x 1, x 2, x 3) =3x 1+x 2-2x 3+0. 8
+
2x 1-2x 2+x 31237x 1+3x 2-x 3x 1+x 2-x 3≤1
-x 1+x 2-x 3≤-112x 1+5x 2+12x 3≤34. 8
12x 1+12x 2+7x 3≤29. 1 -6x 1+x 2+x 3≤-4. 1x 1, x 2, x 3≥0 问题(4)
4i =1
4
2i
i =1
9
M in f (x , y ) =5∑x i -5∑x -∑y
i =1
i
3 实例应用
按前文所述的计算流程, 应用M atlab 6. 0编制了相应的求解程序。以下就几个实例应用说明本文算法的适用性。
3. 1 NPP 优化问题实例应用
问题(1)
M in f (x 1, x 2) =(x 1-10) +(x 2-20) (x 1-5) 2+(x 2-5) 2-100≥0
-(x 1-6) 2-(x 2-5) 2+82. 81≥013≤x 1≤1000≤x 2≤100
3
3
2x 1+2x 2+y 6+y 7≤102x 1+2x 3+y 6+y 8≤102x 2+2x 3+y 7+y 8≤10-8x 1+y 6≤10-8x 2+y 7≤0-8x 3+y 8≤0
-2x 4-y 1+y 6≤0-2y 2-y 3+y 7≤0-2y 4-y 5+y 8≤00≤x i ≤1 i =1, 2, 3, 4
0≤y i ≤1 i =1, 2, 3, 4, 5, 9y i ≥0 i =6, 7, 8
选取群体大小Popsize=100, 锦标赛选择个体数tour n =20, 交叉概率p c =0. 4, 变异概率p m =0. 2, 遗传终止代数M ax gen =1000, E =0. 00001。上述优化问题(1) ～(4) 的求解结果如表1所示。
表1 N PP 优化问题求解实例对比结果
T able 1 T he compar ativ e solut ion o f NP P betw een optimizat ion v alues and G A p s m ethods
优化问题
Optim um problems 问题1Problem 1问题2Problem 2问题3Problem 3
准确解Analys is res ults
x 1=14. 1; x 2=0. 8; f =-6962. 5x 1=2. 3295; x 2=3. 1783; f =-5. 5079x 1=1; x 2=0; x 3=0; f =-2. 471428x 1=0; x 2=1; x 3=1; x 4=4
问题4Problem 4
y 1=1; y 2=1; y 3=1; y 4=1; y 5=1y 6=3; y 7=3; y 8=3; y 9=1; f =-15
GA 求解结果GA p s res ults
x 1=14. 098; x 2=0. 801; f =-6962. 498x 1=2. 3297; x 2=3. 1788; f =-5. 5085
x 1=0. 9995; x 2=0. 0003; x 3=0. 0000; f =-2. 4721x 1=0. 0000; x 2=1. 0000; x 3=1. 0000; x 4=4. 0000
y
1=1. 0000; y 2=1. 0000; y 3=1. 0000; y 4=1. 0000; y 5=1. 0000; y 6=3. 0001; y 7=3. 0004; y 8=3. 0002; y 9=1. 0000; f =
-15. 0002
第1期宋松柏等:约束优化问题的遗传算法求解
k ) (T 1i ≤-i ≤T M ax 9
M 1≤k ≤9
i ≠k
153
3. 2 IPP 优化问题实例应用
问题(1)
M in
f (x 1, x 2, x 3) =3x 1-2x 2+5x 3
x 1+2x 2-x 3≤2x 1+4x 2+x 3≤4
x 1+x 3≤34x 2+x 3≤6x 1, x 2, x 3={0, 1}
问题(2)
M ax
f (x 1, x 2) =60x 1+30x 2
35x 1+8x 2≤4001. 5x 1+3. 5x 2≤604x 1+5x 2≤90x 1≥0, x 2≥0x 1, x 2取整数
问题(3) 为灌溉渠道轮灌配水优化模型[8], 如下所示, 共有9×26=234个决策变量, 9+2×26=61个约束变量。
表2 I PP 优化问题求解实例对比结果
-26
∑t x
j j =1
9
ij
-336≤0i =1, 2, …, 9
∑x
i =1
9i =1
ij
-1≤0j =1, 2, …, 26
∑x
ij
+1≤0j =1, 2, …, 26
i =1, 2, …, 9; j =1, 2, …, 26
x ij ={0, 1}
式中, x ij 为轮灌组出水口的开关状态, 为决策变量, 其中x ij ={0, 1}, x ij =0表示出水口关闭, x ij =1表示出水口开启; 26为出水口(配水渠道) 数; 9为轮灌组划分数; t j 为出水口引取水量所需的时间(h) 。选取群体大小Popsize=100, 锦标赛选择个体数tour n =20, 交叉概率p c =0. 3, 变异概率p m =0. 2, 遗传终止代数M axg en =1000, E =0. 001。上述优化问题(1) ～(2) 的求解结果如表2所示。
T able 2 T he compar ativ e so lution of L I PP betw een optimiza tio n v alues and G A p s methods
优化问题
Optimum problems 问题1Pr ob lem 1问题2Pr ob lem 2
准确解Analysis results x 1=1; x 2=0; x 3=1; f =8x 1=9; x 2=10; f =840
GA 求解结果GA p s r esu lts x 1=1; x 2=0; x 3=1; f =8x 1=9; x 2=10; f =840
优化问题(3) 中各轮灌组引水时间和目标函数值与文献[8]结果对比列于表3。
表3 文献[8]模型与文中模型求解结果对比
T able 3 T he co mpa rative o pt imization results betw een the models in lit eratur e [8]and in this paper
文献[8]模型优化结果Results of literature p model[8]
轮灌组引水时间/h Irr igation tim e of rotation irrigation group
[***********][1**********]
轮灌组引水流量/(m 3・s -1) Flow of of rotation irrigation g roup
0. 20. 20. 20. 20. 20. 20. 20. 20. 2
本文模型优化结果Results of this pap er model
轮灌组引水时间/h Irrigation time of rotation irrigation g roup
[***********]3293293297
轮灌组引水流量/(m3・s -1) Flow of of rotation irr igation group
0. 20. 20. 20. 20. 20. 20. 20. 20. 2
轮灌组Rotation irrigation gr ou p 轮灌组斗口组合Lateral canal combination 轮灌组Rotation irr igation group 轮灌组斗口组合Lateral canal combination
123456789
新10, 9, 新7, 311, 10, 4, 217, 1419, 723, 22, 16退水, 12, 821, 15, 13, 52018, 6, 1目标函数Target function
123456789
202, 145, 16, 239, 15, 18, 21, 22
3, 4, 17, 新206, 11, 137, 198, 12, 退水1, 新7, 10, 目标函数T ar get function
对比表1, 表2和表3可以看出, 本文GA 优化结果与其准确解参考值完全一致, IPP 问题(3) 的优化
154
西北农林科技大学学报(自然科学版) 第33卷
解NPP 、IPP 问题的算法是稳定的。
4 结 论
GA 求解约束优化问题是GA 研究中的热门问题之一。本文采用锦标赛选择、算术交叉、均匀交叉、均匀变异和非均匀变异算子, 应用M atlab 6. 0编制
了相应的求解程序。通过几个实例的数值试验, 计算
结果表明, 文中GA 优化结果与准确解一致, 具有较强的通用性、精确性和稳健性。由于遗传算法目前是一个正在探索研究的算法, 因此如何提高本文算法的性能及更好地进行运行参数选择等, 有待于进一步研究。
[参考文献]
[1] 周 明, 孙树栋. 遗传算法原理及应用[M ]. 北京:国防工业出版社, 1999. 33-64.
[2] 孙艳丰, 郑家齐, 王德兴, 等. 基于遗传算法的约束优化方法评述[J ]. 北方交通大学学报, 2000, 24(6) :14-19.
[3] M ichalew icz Z A. Survey of constraint handling techniques in evolutionary com putation methods[A]. M cDon nell J R, Reynolds R G, Fogel
D B. Processin g 4th an nual conference evolutionary p rog ramm ing[C]. Cambridge, M A:M IT Press , 1995. 135-155.
[4] M ichalew icz Z, Schoen auer M. Evolution ary algorithm s for constrained paprameter optimization problems [J]. Evolutionary Compution,
1996, 4(1) :1-32.
[5] M ichalew icz Z , Deb K , Sch midt M , et al . Evolu tionary alg orith ms for eng ineering application [A ]. M iettinen K , Neittaan m k i P , M kel M
M , et al. Evolutionary algorith ms in engin eering and com puter science[C]. Ch ichester, England:J oh n W iley and Sons , 1999. 73-94. [6] Zbigniew M ichalew icz, M artin Schmidt. TCG-2:A tes t-case generator for non-lin ear param eter optimisation techniques [A ]. I Ashis h
Ghosh, S higeyos hi Ts utsui. Advances in evolu tionary compu tin g, th eory an d applications [C]. Heidelberg, Germ any :S pringer, 2003. 193-212.
[7] Fernando Jim nez , J os L Ver degay . Evolution ary techn iques for cons trained optimization problem [A ]. Hans -J rgen Zimm ermann . 7th
eur op ean congress on intelligen t techniques an d s oft computing (EU FIT p 99) [C]. Aachen, Germ any:S pringer, 1999. [8] 吕宏兴, 熊运章, 汪志农. 灌溉渠道支斗渠轮灌配水与引水时间优化模型[J]. 农业工程学报, 2000, 16(6) :43-46.
Genetic algorithm solution for co nstrained optimization
SONG Song -bai , CAI Huan -jie , KANG Yan
(College of Water Resources and A rchi tectural Engineering , N orthwest A &F Univ ersity , Yangling , Shaanx i 712100, China )
Abstract :Based on the principles of g enetic alg orithm , the g eneral GA methods for No n Linear Pro gram ming and Integral Prog ramm ing w er e desig ned by using operators such as To urnament Selection, Arithm etic Crossover , U niform Crossov er , Uniform M utation and No n Uniform M utation. Using M atlab 6. 0, the co mputatio n prog ram o f GA has been developed. Finally , T he GA for Non Linear Progr am ming and Integ ral Prog ramm ing is tested by som e ex am ples and the results show that the alg orithm in this paper is feasible and stable.
Key words :non linear progr amming; integral prog ramming; co nstrained optim izatio n problem ; genetic algo rithm