信息与控制
INFORMATION AND CONTROL
1999年 第28卷 第3期 Vol.28 No.3 1999



基于均匀设计的遗传算法及其应用
高齐圣　潘德惠
　　摘要：均匀设计属于Monte Carlo方法的范畴，基于该方法对遗传算法进行改进，并给出在橡胶产品设计中的应用实例．实验结果表明本文提出的遗传算法在求解大规模优化问题中是行之有效的．
　　关键词：优化设计,均匀设计,遗传算法,橡胶配方
　　中图分类号：TP13　　　　　　文献标识码：B
GENETIC ALGORITHMS BASED ON UNIFORM DESIGN
AND ITS APPLICATION
GAO Qisheng　PAN Dehui
(Institute of Information Science and Technology, Northeaster University, Shenyang 110006)
　　Abstract　Based on uniform design technique, a new genetic algorithm, UDGA, is proposed, and it is applied to solve a complicated optimization problem that appears in rubber prescription. Experiment results show its validity. 
　　Key words　optimal design, uniform design, genetic algorithms, rubber prescription
　　1　引言
　　遗传算法(Genetic algorithms: GA)是由美国Michigan大学的John Holland教授在60年代提出的[1,2]，它是一种自然适应优化方法，该算法是基于自然遗传和自然优选机理的寻优方法．所谓自然遗传和自然优选来自于达尔文的进化论学说，该学说认为在生物进化过程中，任一动植物经过若干代的遗传和变异，使之能够适应新的环境，是优胜劣汰的结果，这种自然遗传思想也适用于求解优化问题．
　　GA采用选择(selection)、交叉(crossover)和变异(mutation)运算来实现“物竞天择,适者生存”这一自然法则的模拟，近年来发展迅速．目前研究表明，传统的标准遗传算法(SGA)不能收敛到全局最优解，而对SGA的改进算法，如在选择运算后保留当前最佳个体的GA最终能够收敛到全局最优解，但同时指出，这种收敛到全局最优解所需要的时间可能很长，如何提高GA的搜索效率是目前急需解决的问题．
　　本文基于均匀设计方法，提出一种能够有效地提高搜索效率的遗传算法——UDGA(genetic algorithms based on uniform design)，并给出在橡胶产品设计中的一个应用实例．
　　2　均匀设计
　　“均匀设计”是80年代由中国科学院数学所王元和方开泰教授将数论和多元统计分析相结合创立的一种新颖的试验方法[3]，它是单纯从均匀性原则出发的试验设计．均匀性度量采用以下偏差(discrepancy)概念：
　　　　　　　　　　　　　　　　　　　　　　　(1)
其中，v(X)为矩形[0,X]的体积，mX为X1,X2,…,Xm中落入[0,x]的点数，Cn为定义的空间．
　　均匀设计与统计的试验方法——“正交设计”相比，其试验次数大大减少，因而受到工程人员的普遍欢迎．均匀设计的核心思想是用确定性方法寻找空间中均匀分布的点集来替代Monte Carlo中的随机数，因而属于Monte Carlo的范畴，可看成是统计抽样，这些都是我们引入GA并改进之的依据．
　　均匀设计的实施常用一个均匀表Um(mn)来完成， m为试验次数， n为所处理的因素 (变
量)，以好格子点法(good lattice point)为例说明其元素uij的生成过程．
　　第一步，给定试验次数(后面称群体规模)m,寻找比m小的整数h，且使(m,h)=1,符合这些条件的正整数组成一个生成向量H=(h1,h2,…,hn);
　　第二步，均匀表的第j列由下面方法产生
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(2)
这里，[mod m]表示同余运算．如m=9时，H(1,2,4,5,7,8),可生成均匀表格(表1)．
表1　U9(96)

　123456
1124578
2248157
3363636
4487215
5512784
6636363
7751842
8875421
9999999

　　3　改进的遗传算法——UDGA
　　3.1　初始群体的生成
　　给定群体规模m，即m=|A(0)|, A(t)表示第t代群体(母体)．初始群体A(0)可采用均匀设计Um(ms)来产生，这里，s为参数个数．
　　3.2　个体编码
　　第t代群体A(t)中第i个个体编码为
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(3)
这里， aij∈{1,2,…,m}(I=1,2,…,m; j=1,2,…,s).显然，此编码不是等长的，且参数实际值和编码间对应关系为
　　　　　　　　　　　　　　　　　　　　　　　　　(4)
这里，[xjmin, xjmax]为第t代参数xj的搜索范围，不妨记X(t)={xij}m×s．
　　3.3　遗传操作
　　1) 选择
　　记fi, 为群体中个体适应度和群体适应度平均值，选择群体中适应度的所有个体
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(5)
进入下一代，这里为取整运算．记A′(t)的实际参数表达为
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(6)
　　2) 交叉和变异
　　按照物种形式和小生境技术原理，交叉和变异是在适应度较强的环境中进行，具体就是基于X′(t)(或A′(t))形成的搜索空间内实现交叉和变异．记
　　　　　　　　　　　　　　　　　　　　　　(7)
选用均匀设计表Up(ps)产生p个个体，记为
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(8)
A″(t)即可认为是经交叉和变异后生成的新个体，记对应的实际参数表达为
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(9)
令
　　　　　　　　　　　　　　　　　　　　　　　　　　　(10)
则A(t+1), x(t+1)构成下一代群体的编码和实际参数表达．
　　3.4　搜索停止准则
　　　　　　　　　　　　　　　　　　　　(11)
这里，f*表示群体中最佳个体的适应度，ε1,ε2为预先给定的精度．
　　UDGA步骤如下：
　　第一步，置t=0，选择参数ε1,ε2,m,并由Um(ms)生成初始群体A(0);
　　第二步，评价第t代群体A(t)的适应度
　　第三步，依据(5)～(10)经过选择、交叉和变异运算生成下一代群体A(t+1);
　　第四步，依(11)进行终止条件判定，如果满足终止条件，则转向第五步，否则,tt+1,转向第二步；
　　第五步，输出最佳母体结果．
　　综上可见，基于均匀设计基础上的遗传算法(UDGA)，具有以下特点：
　　1)可降低遗传规模的选取；
　　2)每一代遗传都能保证当前最优个体以概率1转移到下一代去；
　　3)每一代群体形成的搜索区域不断收缩，因而可有效地提高GA收敛到全局最优解的速度．
　　4　应用实例
　　某橡胶厂在开展QC(Quality Control)活动中，选择丁基橡胶产品配方设计开展工作，目标是在保证产品质量要求的前提下降低产品的成本．考察的主要变化成分为半增强碳黑、硫磺s和促进剂TMTD三种，其用量分别为x1,x2,x3,工艺范围为x1∈[20, 40],x2∈[0.8, 2], x3∈[0.8, 2.2]．考察的产品性能指标有扯断强力y1,拉断伸长率y2,撕裂强度y3，老化系数y4,门尼焦烧(120℃)y5，300% 定伸y6，永久变形y7和正硫化T90(168℃)y8八项， 国际标准依次为y*1=12.00, y*2=600.00, y*3=40.00, y*4=0.80, y*5=37.00, y*6=30.00, y*7=33.00, y*8=11.00,且前6项性能类型为收益型，后两项性能类型为损益型．
　　　　　　　　　　　　　　　(12)
yi(x1,x2,x3)代表产品第i项性能与设计变量之间的近似函数关系，可通过安排试验和辨识模型得到，这里，yi(x1,x2,x3)结构如下，参数见表2．
表2　模型系数一览表

　b0b1b2b3b11b12b13b22b23b33
y11753.74-36.6-55.80.6764-0.10360.31644.5-0.878613.5
y260717.1-59.4-11.2-0.3071-0.27660.184629.96-0.1558-1.46
y355.41.91-11.1-20.6-0.05170.36890.36920.92-3.51441.69
y40.96-0.030.170.430.00030.00350.0012-0.120.0373-0.18
y530.2-1.132.5834.10.01320.15530.0773-4.490.4349-9.46
y641.2-1.2821.0-11.00.0215-0.33820.3428-6.526.5895-0.71
y727.00.43-0.42-10.70.00070.0307-0.1320.191.31795.24
y820.7-0.093.32-14.3-0.00110.03840.0725-0.65-0.113.10

　　　　　　　　　　　　　(13)
记

　　　　　　　　　　　　　　　　　　　　　　　　(14)
M为惩罚因子，在本文中，M=100, α=1，因此，(13)等价于如下形式
　　　　　　　　　　　　　　　　(15)
适应度定义为
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(16)
取m=30, ε1=0.005, ε2=0.005，经过10代UDGA搜索结束，得到结果为x*1=29.00, x*2=1.04, x*3=1.21.
　　5　结论
　　基于均匀试验设计技术，本文提出一种新型的遗传算法——UDGA，并将该方法应用到橡胶配方优化问题中，实验结果表明，该方法用于求解复杂的大规模优化问题时，可以有效地减少搜索次数，加快收敛速度，便于实际应用．
作者单位：东北大学信息科学与工程学院　沈阳　110006
作者简介：高齐圣，32岁，博士生，副教授．研究领域为优化设计及应用．
　　　　　潘德惠，70岁，教授，博士生导师．研究领域为应用数学、自动控制理论及其应用理论．
参考文献
　1　Holland J H. Adaption in Natural and Artificial Systems. Univ of Michigan Press, 1975
　2　Goldberg D E. Genetic Algorithms in Search. Optimization and Machine Learning, Addison-wesley, 1989
　3　王　元，方开泰. 关于均匀分布与试验设计(数论方法). 科学通报， 1981， 26: 65～70
　4　方开泰. 均匀设计与均匀设计表. 科学出版社，北京，1994
　5　高齐圣，潘德惠. 应用TQC方法进行某产品配方设计. 管理工程学报，(已录用，待发表) 
　6　王伟，高齐圣. 应用均匀网格法优化橡胶配方. 橡胶工业， 1997， 44(1)
　7　高齐圣. 改进的SA及其在橡胶配方优化设计中的应用. 合成橡胶工业，1998, 21(2)
1998-04-08收稿
