改进的多目标遗传算法在结构优化设计中的应用

改进的多目标遗传算法在结构优化设计中的应用关志华1（天津大学管理学院9013信箱天津300072）万杰（河北工业大学管理学院天津300000）摘要本文探讨了多目标遗传算法（MOGA）存在的问题，并提出了相应的改进策略。这些策略包括：小生境技术、适应度共享策略、交叉限制、改进的终止准则等。通过采用这些策略对MOGA进行改进，使之可以克服在终止准则和小生境形成上的缺陷，从而使算法既可以对问题空间进行更广泛的搜索又可以可靠的、迅速的收敛于优化解，为最终决策提供了帮助。最后，给出了改进的MOGA在结构优化设计中的两个应用实例。关键词多目标优化问题，结构优化设计，遗传算法1引言带有m个目标函数的多目标优化问题(MOOP)的数学表达式如下：KkxhJjxgxDDxosubjecttxfxfxfMinimizekjmi,...1,0)(,,...,1,0)(::)(),...(),...(1由于在MOOP中，多个设计变量有时是相互矛盾的。所以，这里的最小化（Minimize）问题，从实际意义上来说，其实是指当综合考虑所有的目标函数时的优化解（Pareto解）。尽管也许全部的目标函数都不能优化到它们各自作为单目标函数时的最优解，但是，在多目标情况下，对其中任意一个单个的目标函数的优化都不能以降低其它函数的优化解为代价。这就是多目标优化不同于单目标函数优化的地方，也正是它的难点。这里，为了区别进化过程中的Pareto解集和MOOP最终得到的Pareto解集，我们把进化过程中的Pareto解集称为近优解集（non-inferior），而在其它文献中这两个名词通常表示同一概念。适用于多目标优化问题的遗传算法（MOGAs）是在经典遗传算法（GAs）的基础上修改得到的。多目标优化问题的遗传算法在适应度分配策略上不同于经典遗传算法。本文探讨了现有的MOGAs的主要缺点，并在此基础上提出了一些改进策略。在使用MOGA进行多目标问题优化时，为了得到最终的解集，MOGA必须对尽可能多的近优解集进行分析，而这些解是均匀的分布在解空间中的，这就会使MOGA的效率降低。但是，只有求得大量的解才可能得到一个连续的、平滑的Pareto曲面，从而使MOGA可以尽快地收敛于优化解。当然，收敛速度同时也依赖于终止准则的选取。在单目标优化问题中，终止准则可以定为：“在N代进化中适应度值没有改进”或直接定为“进化N代”，而在MOGA中却不能如此简单的定义，因此，需要有一种策略来检测MOGA是否已经得到了Pareto解集。目前,MOGA存在如下主要问题:(1)如何指导种群跳出相邻的小生境（niche）从而尽可能的搜索更多的Pareto集。要做到这一点，必须同时满足两个相互矛盾的条件，1）算法必须能够识别近优解集中的群体或个体簇是来源于哪个小生境。因为在进化初期会产生许多小生境，随着进化过程的进行，这些小生境将会扩张超出其边界，这有可能会导致MOGA难以收敛或导致进化过程更接近随机搜索过程，从而效率低下。通过在父代选择阶段采取一些改进策略可以避免这个问题。2）算法必须能阻止这些小生境中的群体过分地集中一些适应值较高的个体附近，而使得小生境过分收缩。从而可能会导致过早地收敛与近优解集。要避免这个问题，可以禁止同一个小生境中的父代交叉。这两个条件一个要尽量抑制小生境的扩张，另一个又要为保持小生境群体的多1作者简介：关志华（1971-），男，天津大学管理学院99秋季博士，主要研究方向为多目标进化算法及其应用。样性而使它在一定范围内扩张。也就是在一定范围内的多样化。(2)怎样加入一些特定的终止准则，这些特定的终止准则可以有效的检测出进化过程中是否产生了Pareto集，并且检测出这些Pareto集是否是均匀分布的。均匀分布的Pareto集中的解不应该在某些区域中解过于集中；而在另一些区域中过于分散。这些Pareto解过于集中和过于分散的区域往往是小生境正在形成的区域，如果这时终止算法的话，就可能使算法过早地收敛于局部优化解而得不到全局的优化解。(3)如何使设计者有一个相对自由地选择来对它感兴趣的特定区域进行放大，以便进一步对特定区域进行优化。这样做的好处是：设计者可以在某个特定的阶段选择特定的区域，从而可以人为地控制这个阶段的种群大小，以较小的种群获得较好的结果和较快的收敛效果，使算法运行效率较高。它的不足之处在于较小的种群规模可能无法覆盖整个可行域。2改进的MOGAs2.1改进的终止准则改进的终止准则可按如下步骤进行：a)从当前近优解集中指定一个佳点（或由设计者直接指定），计算每个个体与这个佳点的距离，形成一个距离矩阵；b)计算这个距离矩阵的均值和标准偏差；c)随着进化代数的增加，近优解集中的点逐渐聚拢，因此，距离矩阵中的元素值逐渐减小，这个过程可以由其均值反映出来；而个体的分布程度可以由标准偏差的增大反映出来。d)如果均值的减小到小于某一个给定值，则可以认为算法收敛并终止算法。否则，转向步骤a)。2.2基于拥挤（crowding）机制的小生境技术在每一个进化代中，当获得近优解集时，可以采取过滤机制人为地从小生境中删除一些个体，删除的个体数目取决于小生境的拥挤程度（小生境密度），被删除的个体由随机产生的个体补充。这样可以使设计者更清晰的理解问题本身并且确定问题的关键区域。具体做法为采用基于拥挤（crowding）机制的小生境技术。主要采用了群体间的代间覆盖方法，其实现方法为：a)初始化（建立初始种群，确定遗传算子。设定拥挤因子CF）；b)计算个体适应度；c)遗传操作；d)从当前群体中随机选出群体规模的1/CF个个体组成拥挤因子成员；e)比较新产生的个体与拥挤因子成员之间的相似性；f)用新产生的个体替换拥挤因子成员中最相似的个体，形成新的当前群体；g)如未满足终止准则，转b），否则终止算法。上述方法在进化的初始阶段，由于群体间个体的相似性相差不大，个体的更新呈随机性。随着进化的过程，群体中的个体逐渐被分成若干个小生境，这时，基于个体相似性的拥挤因子法可以在一定程度上维持群体的分布特性，并为进一步的分类和新的小生境的形成留出了空间。2.3过滤和交叉限制机制在选择父代进行交叉以前，先计算两个父本之间的目标函数空间内的距离，如果距离小于给定的值，则这两个父本不进行交叉；否则，允许交叉。这种对父本的过滤和限制交叉的机制依赖于小生境的密度和其中的种群分布情况。这样可以限制“近亲”交叉，保持种群的均匀分布和多样性。2.4目标函数约束的改进策略当得出整个空间中的近优解以后设计者可以通过给近优解加上约束条件来放大特定的区域。步骤如下：a)暂停进化过程；b)加入必要的约束条件；c)重新开始进化。这个策略可以在每代进化结束时进行，也可以由设计者自己选择时间进行。这样，可以避免那些不满足约束条件的个体的进一步复制。而灵活地选择加入约束的时间，可以加强设计者对进化过程的控制。2.5惩罚机制的改进由于我们只对近优解中的个体进行约束检查，当个体违反约束条件时，如果只是简单将它删除，就有可能丢失包含好的基因片段的个体，所以应该采取基于修改其适应度值的方法来处理。根据Pareto排序方法相应地减小它的适应度值。有如下三种方法可以选择：a)线性排序：rkqpk1参数r定义为10nqqrb)指数排序：11kkqqpc)另一种指数排序：1kkqp式中，kp为种群排在第k位的个体的选择概率；k为排序位置；q为最好个体的选择概率；0q为最差个体的选择概率；n为群体大小。对于违反约束的个体可以制定它的k=n即可以降低它的选择概率。2.6基于预选择(perselection)机制的小生境策略其主要内容为：只有在子个体的适应度值超过其父个体时，子个体才能代替父个体，进入下一代群体。由于这种方法趋向于替换与其本身相似的个体（父个体与子个体之间的性状遗传），因而能够较好地维持群体的分布性。2.7基于适应度共享（sharing）的小生境技术用共享度函数来确定群体中个体的共享度。一个个体的共享度等于该个体与群体内的各个其他个体之间的共享函数值的总和。共享函数是关于个体之间的密切程度的函数。当个体之间关系较密切时，共享函数值较大；反之，则较小。设ijd表示个体i和个体j之间的关系密切程度，s表示共享函数，is表示个体i在群体中的共享度，n表示种群大小，则：njijidss1计算出各个体的共享度后，个体的适应度if被重新指定为iisifif。这种基于适应度共享的小生境技术可以限制那些适应度值太大的“超级个体”的无限制增长。3结构优化实例[例1]两杆构架优化问题两个目标函数的两杆构架优化问题的数学描述如下：0,311000001000001.0:162011621122221xxyffftosubjectyxyfMinimizeyxyxfMinimizeBCACACstressstressvolumestressvolume最小化两个目标函数volumef和stressf，分别为对构架的体积和应力的优化。如下图（图一）所示，经过240代的进化改进的MOGA得到了近优解集。得到Paerto解集所进行的函数计算量为9523次，大大少于未改进的MOGA获得相同解集的计算量（27397次）。图一改进的MOGA在两杆构架问题中的应用[例2]振动试验台优化问题振动试验台优化问题是要设计一个带有固定电机的平台，它可以简化为两杆支撑的有负载的横梁的问题，这里的负载是指电机本身。振动由电机产生再传递到横梁上。横梁长为L宽为B，是由三层材料组成的复合结构，材料厚度分别由1d、2d、3d表示，材料的类型由iM表示，其中)3,2,1(i，表示材料密度，E表示材料的杨氏弹性模量，c表示单位体积材料的价格。组成试验平台的材料属性如下表所示：材料类型iM材料密度3/mkg杨氏弹性模量2/mNE材料单位价格volumec/$1277070109150021001.610950037780200109800表一振动试验台材料属性表问题的有两个目标函数，1f表示基础频率，2f表示试验台造价。振动试验台优化问题的具体数学描述如下：初始种群010000200003000040000500006000000.020.040.060.080.10.12体积（volume）应力（stress）进化240代后010000200003000040000500006000070000800009000000.020.040.060.080.10.12体积（volume）应力（stress）63g5.035.0g6.02.0g5.02.0g005.0g001.0g001.0g02800g:2,,,,2322,,,,,87362514233122123121321223121323331323123211321321321LBdddddddLtosubjectddcddcdcBMBdddfMinimizedddddBddEddEdEBEIEILMLBdddfMaximizeMMMiMMMMMMi目标是要设计夹层结构的梁的参数321321,,,,,,.,MMMdddBL的值，使得振动试验台的造价最小，同时，最小化由于电机的扰动而产生的梁的振动（即：最大化梁的基础频率）。改进的遗传算法MOGA在120代进化后得到了近优解集，而未改进的MOGA则需要进化150代以上。由于采用了适应度共享机制和交叉限制等策略，计算量大为减少，而最终的Pareto解集也优于未改进的算法的结果。结果如下图所示：图二改进的MOGA应用于振动试验台的计算结果4结论本文共探讨了7个MOGA的改进策略，包括：改进的终止准则、基于拥挤（crowding）机制的小生境技术、过滤和交叉限制机制、目标函数约束的改进策略、惩罚机制的改进、