遗传算法在工程优化中的几点改进

1、http:/ - 1 - 遗传算法在工程优化中的几点改进陈玲俐，姚宇琼，于洁上海大学土木系，上海（200072）E-mail：摘要：本文面对工程优化中的实际困难，对传统遗传算法进行了系统改进。在遗传算法中采用动态种群规模，消除了种群规模对优化效率和优化质量的影响；在选择操作中加入记忆功能， 避免了大量重复计算工作；针对实数编码导致的杂交操作并行机制丧失问题，提出了双重模糊编码方法；为了提高优化效率，提出用启发式优化准则减少变异操作中的盲目性。为避免早熟收敛，在优化进程中逐步增大变异率，减小杂交率。 改进的遗传算法在不破坏自适应并行运算机制的同时，规避了种群的无效解、消除了优化过程中的重复计算，

2、提高了优化效率。关键词 ：遗传算法，动态种群，双重模糊编码1. 引言遗传算法是1975 年美国密西根大学的Holand 教授借鉴生物进化原则，提出的一种自适应并行优化算法。在自然界中， 生物的染色体决定生物的形态。千差万别的染色体都是由相同数目的基因组成，一个基因只能是两种属性值（X，Y）中的一种 （也可以表示为0 或 1） ，不同属性值的基因的组合方式构成了千差万别的染色体。生物进化过程是染色体中的基因优化过程。 在工程和数学优化问题中，优化方案决定优化目标。千差万别的优化方案都是由相同数目的优化参数组成，一个优化参数只能取有限的几个值、或在有限区间L，U中取值，不同取值的优化参数的组合方式

3、构成了千差万别的设计方案。可见，优化问题与生物进化问题从表达方式到最终目标都非常相似。将优化问题表述成生物进化问题，在优化过程中采用生物进化原则，实现优化目的的一类算法，称为遗传算法。2. 传统遗传算法遗传算法在求解优化问题时一般包括以下几个步骤：1、 编码。 将优化参数表示为基因的过程称为编码。由于生物基因属性只有两种，对应0-1 二进制编码中的一个编码位。如果优化参数的值域也只包括两个值，则用一个编码位的基因就可以代表一个优化参数。如果优化参数的值域包括多个值、或者优化参数为一个连续变量，则多个编码位的基因才能表示一个优化参数。例如，优化参数的值域为（07）的8个整数，称值域空间为8，则需

4、要 3 个编码位才能表示一个优化参数。优化参数的值域空间大小决定了编码位数的大小。如果编码位数为n，则编码空间为2 n。一般编码空间不小于优化参数的值域空间。当编码空间大于优化参数的值域空间时，则基因值可能会对应无意义的或超界的优化参数值。对此，要进行修正、淘汰或加以惩罚。这种处理干扰了算法的自然进化过程。 为了避免编码空间与优化参数的值域空间不一致问题，又提出了自然数编码、序列编码和实数编码等编码形式。如值域空间为8 的优化参数， 可以用变化范围为18 的一个自然数编码位来表示。后三种编码方式大大降低了编码和译码的工作量，在工程优化中应用广泛，但是这些编码方式破坏了在生物杂交操作中隐含的并行

5、机制。2、 遗传操作。 遗传操作是通过种群性态的比较，使好的染色体遗传到下一代，差的染色体失去繁殖权利。染色体的好坏通过适应函数值的大小来评价，适应值不小于零。适应值http:/ - 2 - 函数要通过具体的目标函数值和约束情况综合考虑，构建。 适应值函数与目标函数值的关系通常有以下几种关系：线性关系、指数关系、对数关系、倒数关系等。当染色体对应的优化方案满足优化模型中的约束关系，约束对染色体的适应值不产生影响；当约束关系不满足时，要根据违约量的大小，对目标函数值得到的适应值附加一项惩罚。违约量越大， 惩罚量越大。如果一个优化方案违反严格约束，则此方案的适应值为零。这种处理方式相当于淘汰不满足

6、约束条件的解， 在窄界约束条件下，很少采用这种处理方式。在种群中挑选遗传的染色体有多种选择方法：赌盘选择、确定性原则、有退还和无退还随机选择、有退还和无退还剩余随机选择。 在后面我们将介绍一种新的遗传选择机制，有繁殖能力的染色体只能在子代中复制一个样本，有效避免降低种群的多样性。3、 杂交操作。杂交操作通过交换两对染色体中的部分等位基因，变成两个新的染色体。杂交操作分为一点杂交、多点杂交和分段杂交。对于二维编码，对应着二维杂交。在常规的杂交操作中一般用新解替代旧解。这种做法可能会破坏遗传下来的最优解。因此， 本文改进的遗传算法采用新解旧解同时保留策略。这里所说的旧解，已经是经过遗传操作筛选后的

7、最优种群，保留旧解不会降低算法优化效率，却可以扩大种群多样性。4、 变异操作。变异操作通过改变染色体中的一个和多个基因属性值，得到新的染色体。对于二进制编码，变异只需要对待变异基因的属性按位取反，0、1 互变即可。对于自然数编码，可以在取值空间随机选取与待变异基因原有属性不同的值即可。传统的变异操作与杂交操作一样，也是采用新解替代旧解策略。本文同时保留新、旧解，原因同上。如果杂交操作和变异操作产生的新解数量超过遗传操作中淘汰解的数量，则此时种群规模大于上一代的种群规模。虽然本文改进的遗传算法最大特点是在计算过程中采用动态的种群规模。但是如果种群规模一代代扩张，不加控制，则计算效率将很低下，遗传

8、算法等同于随机搜索。 因此在本文的遗传算法中对种群规模给定上下限。种群初始规模在种群规模的上下限之间。当种群规模大于上限值时，对种群进行多次选择，优中选优；当种群规模小于下限值时，在淘汰解中进行二次选择，次中选优。使种群规模满足上下限限制。5、 收敛判断。 遗传算法有多种收敛判断方法。方法一： 计算代数不超过指定的最大遗传代数；方法二：最优值与种群均值的差小于指定的小量；方法三：最优值连续多代保持稳定。为了保证全局搜索，在方法一中，最大遗传代数越大越好。用方法二得到的最优解如果不理想， 说明算法在应用时可能出现了早熟收敛问题（种群在没有搜索到最优解时已经丧失多样性，使优化停滞不前）。此时可以通

9、过扩大种群规模和加大变异率，重新计算。第三种判断方法不很可靠。遗传算法的计算效率与以下几个参数决定：种群规模、杂交率、变异率。种群规模大，计算时间长，能保证全局搜索。反之，计算时间短，但是可能会出现早熟收敛问题。在遗传算法应用中通常采用固定种群规模的做法。本文在计算中采用动态种群规模，避免了固定种群规模对遗传算法计算效率的影响。下面我们来详细介绍有记忆动态种群遗传算法的每个操作步骤。3. 有记忆动态种群遗传算法3.1 编码工程优化中优化参数多为实数，设优化参数xj的有效取值空间为（，） ，采用实数编码，http:/ - 3 - ( )()()code xrand =-（1）其中 rand()为

10、 01 的随机数。 采用（1）式得到的xj的编码 code(xj)取值区间为 ，。用 +， -替换（ 1）式中的和，为一接近零的小正数；则code(xj)的取值区间为开区间（，） ，xj= code( xj)。这种编码方式显然无需再译码，同时可以避免优化参数落入无效取值空间形成无意义解，即无效种群。但是，实数编码会导致杂交操作在很大程度上丧失并行运算机制。为了弥补这个缺陷，在进行杂交操作时可以对参与杂交操作的染色体采用双重编码，即同时采用实数编码和模糊二进制编码。取值空间为（，）的一个实型优化参数xk，如果采用二进制编码需要占用n 个编码位， 我们将这 n 个编码位分为前、中、后三组（记为 I

11、1I2I3） ；最前一组编码位非零时（100，110，111）表示xj取值接近；最前一组为零，而中间一组非零时（010，011）表示xj取值接近2 +；当前两组编码为均为零时（001，000）表示xj取值接近。我们将这种分组二进制编码称为模糊二进制编码。模糊二进制编码（I1I2I3）映射到实数编码为：123()2)7jxrandIII -+?+(4(2) 实数编码到模糊二进制编码的映射规则为：当23jx+时赋予其模糊二进制编码记为(100)；2233jx +；存活（4）Int 为取整函数。存活的染色体的数量记为pop1，pop1 1，在优化过程中pop1 是不定的。 当种群的适应值都接近max

12、fit() 时， 存活的染色体就多； 当种群的适应值都接近minfit()时，存活的染色体就少。存活的染色体相当于在子代中复制了一个样本，这部分样本的适应值显然已经知道，无需重复计算。3.4 杂交率和变异率杂交率和变异率取值目前只能采用试算法确定。一般的取值原则是如果种群规模较小，则杂交率和变异率取值要稍大，目的是增加种群的多样性。但是杂交率和变异率不能过大，避免杂交和变异产生的新解替换过多的遗传旧解，使算法的自适应特性不突出，变成随机搜索。由于本文改进的遗传算法不存在种群规模对种群多样性的制约。因此， 杂交率和变异率的取值不受种群规模大小的影响。另外在杂交和变异操作中采用的新、旧解不替换策略

13、，杂交率和变异率过高不会破坏算法自适应性质。因此， 在本文所采用的改进遗传算法中，杂交率和变异率初始取值原则是杂交率高于变异率；其次，初始杂交和变异操作产生的新解数目略大于遗传操作中淘汰解的数目。考虑到优化后期种群逐步趋同，杂交操作往往不能产生新解。为减少无效解，避免种群早熟收敛优化过程中通过公式（5） （ 6）逐步降低杂交率，提高变异率。杂交和变异产生的新解的数目分别为2pop2, pop3 。1,0iterpopNiter?-?cpop1pop2=min int2 (5) 1,0iterpopNiter?+?cpop3=min intpop1 (6) 杂交和变异产生的新解的数目分别为2po

14、p2, pop3 。 Niter, iter 分别为最大遗传代数和遗传代数；由于pop1 在优化过程中不定，所以在这里我们要规定最小新解数量pop0，避免优化过程无法进行下去。至此，新一代种群规模变为pop=pop1+2 pop2+pop3。由于记忆功能的加入，在新的种群中我们只需要计算杂交和变异得到的新解的适应值。随着优化过程的展开，由于我们没有用杂交和变异得到的新解替换父代旧解，种群规模可能一代代膨胀。由于计算机的存储和计算容量是有限的，当新一代种群规模在遗传操作后存活种群数量pop1 达到或超过指定的最大种群规模pop_max 时，令 pop=pop1，重新计算存活种群的相对适应值fit

15、，进行二次遗传操作。重复上面过程直到pop1pop_max。3.5 杂交操作杂交操作的实质是两个解xi，xj中一个或多个解构成信息的互换（如图1） 。采用二进制编码时多个编码位置的取值决定一个实数参数的取值大小，信息互换不仅可实现参数值的互换，而且可以产生新的数值。例如8（ 1000）和 3（0011）如果采用二进制单点杂交可以得到 0（0000） 、11（1011）和 10（1010） 、1（0001）及 9（1001） 、2（0001）三对新的数值。采用实数编码时， 一个编码位置对应一个优化参数，杂交操作通常只能实现优化参数的互换。上例中的8 和 3 杂交后仍然为8 和 3，只是在解向量中

16、发生了互换，二进制编码时杂交操作中所蕴含的并行运算机制不复存在。http:/ - 5 - 图 1 杂交操作Fig.1 Crossover operation 如果各优化参数的灵敏度相近，则所优化系统的性能主要表现为优化参数的组合效应，这种实数杂交操作仍然是有效的，无需采用双重编码。但是当各优化参数的灵敏度相差较大时，这种实数杂交操作是一种低效的优化手段，有时甚至比随机搜索还要差。基于模糊二进制编码的杂交操作能够部分恢复传统杂交操作所蕴含的并行运算机制，同时充分利用实数编码的优点。基于模糊二进制编码的杂交操作其编码长度变为3m，可以采用单点杂交、多点杂交等传统杂交操作方式。 （100） （ 01

17、1） （001）多点杂交后会新产生(111)(110)(101)(011)(000) 五种编码方式。与传统二进制编码杂交操作唯一不同的地方是译码，见公式（2） 。3.6 变异操作采用实数编码的变异操作可以采用单点变异或多点变异，变异方法见公式（1） 。由于多数工程优化问题有明确的物理意义。基于工程优化的物理意义或者已经积累的工程设计经验， 我们可以建立一些启发式优化准则。这些启发式优化准则在大型复杂工程系统优化中很难给出全局最优解；但是由于这些启发式优化准则能够直观反映工程优化中的部分优化规律，利用启发式优化准则给出的优化方向作为变异方向通常可以使变异操作更加有效。3.7 收敛判断收敛准则与传

18、统遗传算法相同，这里不再赘述。4工程优化实例一工程系统的组成结构如图2 所示，节点间路径可靠度r 与造价 c、路径长度l 之间的对应关系为：(10.7 )clr =-。在总造价约等于35 条件下，求系统各路径可靠度，要求使系统源点到汇点的连通可靠度最大。路径长度均为1。图 2 工程系统组成结构Fig.2 Topology structure of the engineering system 该优化问题的优化参数数量m17，优化参数的取值区间为0, 1) 。取初始种群规模为30， 初始杂交率和变异率取为0.4, 0.2； 最小新解数量pop06， 最大种群规模pop_max120。1(源点 )

19、 4 2 3568710(汇点 )9xi1 xi2 xikxi,(k+ 1)xi,(k+ 2) xi,(m-11)ximxj1 xj2 xjk xj,(k+1) x j,(k+2) xj,(m-11)xjmxi1 xi2 xjk xj,(k+1) x j,(k+2) xi,(m-11)ximxj1 xj2 xikxi,(k+ 1)xi,(k+ 2) xj,(m-11)xjm杂交http:/ - 6 - 需要指出的是由于优化过程中采用了动态种群规模，这些初始参数只在优化初期对优化进程有所影响。根据单元可靠度越大造价越高的变化规律，变异操作时采用的启发式优化准则为：()()(),( )35()()

20、(),( )35ikikikiikikimutute rrrandrc rmutute rrrandc r?=-+?=-+?采用本文的有记忆动态种群遗传算法得到的优化结果见表1。表 1 优化结果Tab.1 Optimization result 路径可靠度路径可靠度路径可靠度路径可靠度1-2 0 3-4 0.713735-8 0.248958-10 0.359271-3 0.89871 3-7 0.921056-8 0.379697-6 0.867501-4 0 4-7 0 6-9 0.178287-9 0.168422-5 0 5-6 0 6-10 0.893329-10 0.171943-

21、5 0.21449 系统可靠度：0.67115 系统总造价：35.189 5结语遗传算法经过三十多年的研究，借鉴和结合其它优化算法的优点，由一种算法发展为形式极其丰富的一类算法。各种改进的遗传算法或是弥补了算法在应用时存在的潜在缺点，如早熟收敛问题、欺骗解问题等；或者提高了算法的计算效率。在本文提出的动态种群规模的遗传算法中，我们加入了记忆功能。算法对旧解的目标函数值和约束函数值具有记忆，在子代计算时， 不需要再次计算从遗传操作得到的旧解的目标函数和约束函数值，只需对新解进行计算，避免了重复计算。对于小杂交率和变异率的遗传算法， 子代中的大部分解为遗传得来的旧解，记忆功能的引入，大大降低了子代

22、实际求解规模。在工程优化问题中，目标函数和约束函数的计算通常最为耗时。避免目标函数和约束函数的重复计算，意义很重大。参考文献1 米凯利维兹 Z. ， （2000） ，演化程序 遗传算法和数据编码的结合，科学出版社。2 陈玲俐 . 城市供水系统抗震功能分析与优化. 上海：同济大学博士学位论文，2002 年 7 月. 3 Li M, ,Sun X Y, Gong D W. Adaptive hierarchy genetic algorithm .Journal of China University of Mining & Technology, 2002, 31 (6) :622624

23、 . 4 LEE Heow Pueh,LIM Siak Piang,LEE Kwok Hong. Solving traveling salesman problems by genetic algorithmsJ. Progress in Natural Science , 2003,(02) . 5 沈洪远 ,彭小奇 ,王俊年 ,胡志坤 ,. 基于混沌序列的多峰函数微粒群寻优算法J. 计算机工程与应用 , 2006,(07) . http:/ - 7 - Some Improvements of Genetic Algorithm for Engineering Optimization

24、Ghen Lingli ，Yao Yuqiong，Yu Jie Department of Civil engineering ，Shanghai Uni.， Shanghai （ 200072）Abstract The classical genetic algorithms are improved to solved the engineering optimization problems. The changeable population is used in Gas in order to eliminate the disturbances of population to optimization efficient and quality. The memory fu