自动化学报
ACTA AUTOMATICA SINICA
1997年　第23卷　第6期　Vol.23　No.6　1997




变焦遗传算法及其并行实现研究
覃祖旭　张洪钺　陈一虹
　　摘要　遗传算法(Genetic Alogrithm, GA)以其简洁及适应性而获得广泛应用. 通常遗传算法由于串格式及串长的限制，搜索空间及分辨率是有限的， 因而往往收敛于局部最优. 文中提出了适宜串、并行计算的变焦(Zooming)遗传算法及多任务并行策略， 采用了解码因子、搜索中心、快速变异等策略来解决搜索空间与分辨率的矛盾，并在工作站及transputer上分别以串行、并行方式实现了变焦遗传算法. 
　　关键词　变焦遗传算法(ZGA)， 解码因子，搜索中心，并行. 
ON ZOOMING GENETIC ALGORITHM AND
ITS PARALLEL REALIZATION
QIN ZUXU　　ZHANG HONGYUE　　CHEN YIHONG
(Department of Automatic Control, Beijing University of Aeronautics and Astronautics,Beijing 100083)
Abstract　Genetic algorithm (GA) is widely applied to many fields due to its simplicity and adaptability. Generally, the search space and resolution of GA are limited by the string of GA, therefore, the solutions given by GA are usually local results. This paper analyzes the problems in GA and proposes the zooming GA(ZGA), which is suited to sequential and parallel computation. Strategies such as decoded factor, search center, fast mutation, etc. are adopted and the ZGA is realized on a wokrstation and transputers in sequential and parallel manners, respectively.
Key words　Zooming genetic algorithm(ZGA), decoded factor, search center, parallel.
1　引言
　　GA是建立在自然遗传学机理基础上的优化算法. 它的思想来自达尔文“适者生存”以及遗传、变异的基本思想［1，2］. GA以其很强的解决问题的能力和广泛的适应性渗透到各个领域，并取得了很好的效果. 它具有很多良好的特性， 如只采用目标函数，而不需要其他辅助条件(如梯度等)，因而几乎适用于各种场合；同时搜索解空间的许多点，具有并行特性、能搜索复杂的有噪声的多峰值解空间等. 在基本遗传算法及粗-精搜索思想［3，4］的基础上，本文提出了变焦遗传算法，它除了具有GA的优点外，还具有易并行处理、适宜约束优化、收敛速度快等优点. 通常， 基本遗传算法用于求解如下问题
max or minJ(θ),θ∈D, DRn.　　　　　　　　　　　　　(1)
其中θ为参数向量， D为约束所限参数集. 该算法［1，2］的求解过程如下：
　　(1) 确定需要优化的各种参数，将参数按顺序排列形成向量θ∈Rn, θ=[θ1,…,θn]T并设计合适的串S；由参数θ到串S的过程称为编码， 由串计算出参数值的过程称为解码，可用下式表示
　　　　　　　　　　　　(2)
其中t为编码规则，p为解码规则；
　　(2) 根据求解问题，选择适当形式的目标函数或适应函数，记为J(θ)或J(S)；
　　(3) 随机初始化m(＞l)个解(串)Si(i=1,2,…,m)，即选定一组初始解(一个群)；
　　(4) 对每个串进行解码， 再计算每个解的目标函数值(适应值)J(θi)(i=1,…,m);
　　(5) 从群中挑出l个适应值较大的串Si(i=1,2,…,l);
　　(6) 对l个串(构成匹配集)进行遗传进化，即用遗传算子对匹配集内的串进行运算， 主要的两个算子是交叉(crossover)及变异(mutation)； 有时也采用另外一些遗传算子［1，2］；
　　(7) 对产生的新串解码并计算相应的适应值；
　　(8) 判断适应值(或遗传代数)是否满足要求，否则转(5)继续优化. 
2　变焦遗传算法
　　基本遗传算法在无约束优化中，求解空间为Rn. 由于串格式及串长的限制，基本遗传算法搜索空间及分辨率是有限的，只能覆盖部分解空间，而且解的精度也有限，因而往往是局部收敛.由基本GA可以看出，首先要设计合适的串S及相应的解码规则.设问题的全局最优解θ*∈DRn， 所设计的串S解码后所覆盖的区域为DS， 因而用GA求得全局最小的必要条件是
θ*∈DS.　　　　　　　　　　　　　　　　　　(3)
事实上一旦S的格式确定下来，DS也就确定了.在求解某些问题时，由于问题的特殊性、串长及解码格式的限制，往往不能保证条件(3)，因而所得的解可能是局部最优. 从理论上讲，如果完全不知道最优解的位置，则设计的串应能覆盖Rn， 因此要求串是无限长的，这不可能. 在实际中，最优解或近似最优解往往都应是可以物理实现的(数值不可能很大)，因此可根据实际问题，合理地选取串格式及串长. 此外，在基本的GA中往往采用大概率交叉，小概率变异，这种策略在接近最优解时搜索非常缓慢，即所谓成熟前收敛的问题. 针对以上存在的问题，这里提出了变焦遗传算法. 主要思想如下：
　　① 变焦GA引进了解码因子α的概念，主要是为了解决有限串长时覆盖区域与分辨率之间的矛盾， 在大范围内搜索时采用较大的解码因子(分辨率较低)，小范围内采用较小的解码因子(分辨率较高). 因此，为保证求得全局最优，初始串应覆盖较大的区域，即初始解码因子α0应选择大一些. 这类似于“粗-精”搜索策略. 
　　② 采用了搜索中心及最优增量. 如果串S经解码后对应解的最大范数为‖θ‖，则GA搜索的区域DS为欧氏空间以θ0为搜索中心(它可以根据实际情况给定，也可以设在原点θ0=0)，搜索半径为α‖θ‖=R的超椭球体. 对于固定的串长及串格式，遗传算法是在这个区域内寻优， 如果这个区域较大，获得全局最优解的可能性就较大. 在变焦遗传算法中，遗传优化求得的是某一解码因子αi对应的搜索中心θi-1的增量， 增量最大变化范围为αiRi，最优增量记为Δθ*i，问题的最优解为θ0+∑Δθ*i. 这一点是与基本遗传算法相区别的. 解码因子、搜索中心、最优解形成下面系列
　　解码因子：α0,α1,α2,α3,α4,…,αi,…;
　　搜索中心：θ0,θ1,θ2,θ3,…,θi…;
　　最优解：θ1=θ0+Δθ*1; θ2=θ1+Δθ*2=θ0+Δθ*j,…;θi=θi-1+Δθ*2=θ0+Δθ*j,….
　　③ 采用了“快速变异”策略. 基本思想是在较小的解码因子(接近最优解)时，采用较大概率变异，使各个体迅速变化并覆盖整个搜索区域，加速收敛速度. 由于变焦算法搜索的是最优增量
，快速变异不会丢失最优解. 这种算法是在小的搜索范围内，将GA向随机搜索方向转化.变焦算法还用了“强迫变异”策略，对那些不适应环境(适应值较小)的个体进行强迫变异；如果仍然较差， 则淘汰掉并以新的个体取代(移民策略). 
　　本文将采用以上改进的遗传算法称为变焦遗传算法.不难看出，基本遗传算法是变焦遗传算法的一种特殊情形，相当于搜索中心在原点，搜索半径、解码因子固定的情形. 因此，ZGA完全具有GA的优点，同时它还具有如下优点：容易进行任务并行计算；非常适宜约束优化计算，特别是区域约束的情形；易于同其他算法(如梯度算法)结合使用. 
3　变焦遗传算法的并行实现
　　采用并行处理技术， 可突破传统串行计算机的“瓶颈”问题，使处理速度成倍加快，同时也有助于提高系统的可靠性. 在并行处理硬件方面，国内外大多采用由英国INMOS生产公司Transputer(晶片机)构成的或美国Texas仪器公司生产的TMS系列芯片构成的并行计算机，它们为并行处理提供良好的硬件基础. 
　　利用并行处理来扩大遗传算法的搜索区域、加快搜索速度是非常有效的手段. Transputer是目前广泛采用的一种并行硬件. 由Transputer可能构成大规模的并行阵列以提高计算速度，但晶片机的频繁通讯也会影响其效率，因此晶片机适用于通信量较少的任务并行计算. 本文采用的是INMOS T800晶片机系统，该系统是以Sun4为宿主机，在以太网上由晶片机构成的并行加速度器. 
　　利用变焦遗传算法搜索中心的概念，可以按区域搜索进行任务分割，因此变焦遗传算法可以完全做到不进行中间通讯，只在计算结束时与主机通讯，传送计算结果，由主机进行最优解的选择. 我们在Transputer上成功地应用变焦遗传算法并行计算了以下函数极小值，同时也在SGI工作站上利用变焦遗传算法计算了其极小值 
　　f(x)=3.591189×10-6x8-3.1094004×10-4x7+1.11345455×10-2x6-2.128811726×10-1x5+
2.33974988x4-14.81638047x3+51.2109248x2-84.16690736x+49.51052631.
　　计算中采用十进制串格式，串长为5，在此串长及串格式下的搜索区域为±α×104.为了使搜索区域尽量大，在工作站上串行计算时，共选取了16个搜索中心x0=0,x1,x2,…,x15，并顺序搜索完成优化计算. 在16片Transputer上，每个晶片机选取上面一个搜索中心进行搜索，所需时间大致为串行计算的1/16.在x0=0的搜索中心处，经过三次改变解码因子及采用快速变异策略，共90代遗传优化，求得最小点为x*=1.738, f(x*)=-1.6008, 其他搜索中心的局部最小值均大于x*处最小值.为了便于比较，还采用了基本遗传算法，在x0=0附近的区域进行寻优，经过3000次搜索求得上述函数最小点为x*=1.74, f(x*)=-1.60079. 由此可见，ZGA比GA搜索速度大大提高，搜索区域也增大了，在最优点附近，能较好地解决成熟前收敛的问题. 
4　应用
　　这里将变焦遗传算法应用于两相伺服电动机CAD系统中的约束优化［5］， 取得了较好的效果. 两相伺服电机参数的选择是一个的约束优化问题，要求电机体积尽量小(体积约束)，而性能达到要求的技术指标(指标约束)，力求在额定状态下获得最高效率. 目标函数为,V为电机体积，为电机效率. 优化的变量X主要选为结构尺寸X=[x1 x2 x3 x4 x5]T，其中x1为定子铁芯长l1,x2为定子槽底宽bcd1,x3为定子齿宽bz1,x4为转子槽高hc2, x5为转子槽宽bz2. 约束条件是由电机的性能要求决定的，可根据电机设计的技术性能指标推导出来，共有18个约束条件，包括体积约束及指标约束. 表1给出了45SL-4D型电机尺寸的几组约束条件，均为区域约束，因此采用变焦遗传算法是比较便利的. 优化计算中搜索中心可取为约束区域的中心，X0=[15　4.75　1.55　1.2　0.6]. 表2所示为将ZGA与外点SUMT法+模式搜索分别用于优化计算的结果. 
表1　六组约束条件
参数123456
x1［10,30］［10,35］［10,40］［10,30］［5,30］［12,30］
x2［1.2,1.7］［1.2,1.8］［1.2,1.9］［1.2,1.6］［1.1,1.7］［1.1,1.7］
x3［4.0,6.5］［4.0,7.0］［4.0,7.5］［4.0,7.0］［3.5,6.5］［4.3,6.5］
x4［0.6,1.4］［0.6,1.5］［0.6,1.2］［0.6,1.4］［0.5,1.4］［0.4,1.4］
x5［0.5,0.8］［0.5,0.9］［0.5,1.0］［0.5,0.8］［0.4,0.8］［0.5,0.8］

表2　不同约束条件下的优化结果
方法约束123456
外点SUMT法
+模式搜索目标函数值8.7838.9828.7018.823/8.924
计算时间(秒)3333/3
变焦遗传算法目标函数值7.8318.3927.5567.8638.1448.367
计算时间(秒)8614976

　　从表2可以看出， 变焦遗传算法计算时间稍长， 但其搜索结果要明显优于外点SUMT+模式搜索方法；对于第五组约束， 外点SUMT+模式搜索未能给出满足约束的结果.
5　结语
　　本文所提出的变焦遗传算法既适于串行计算更适合于并行处理，在Transputer上实现起来十分容易. 变焦遗传算法还被应用于其他约束优化问题，具有很好的特性；在神经网络的优化中同BP算法相结合可大大加快收敛速度. 
　　致谢　本文得到清华大学计算机系统与应用实验室的支持，在此表示感谢.
1) 得到国家自然科学基金及航空科学基金的资助. 
作者单位：北京航空航天大学301教研室　北京　100083
参考文献
[1]　David B Forgel. An introduction to simulated evolutionary optimization. IEEE Trans.Neural Networks,1994,5(1):3-14.
[2]　陈根社，陈新海.遗传算法的研究与进展.信息与控制，1994, 23(4):215-222.
[3]　Nicol N Schroudolph. Dynamic parameter encoding for genetic algorithms. Machine Learning,1992,9(1):9-21.
[4]　Shaleler C G .The ARGOT Strategy:Adaptive representation genetic optimizer technique. In:Proceeding of the second international conference on Genetic algorithms, 1987, Beijing, 50-58.
[5]　何　期.两相伺服电动机CAD系统研究与开发［学位论文］.北京：航空航天大学，1995.
收稿日期 1995-05-18
