基于改进离散差分进化算法的桁架优化

王 烁，谷正气，2，韩征彤，马晓骙

（1.湖南大学 汽车车身先进设计制造国家重点实验室，长沙 410082；2.湖南文理学院洞庭湖生态经济区建设与发展协同创新中心，湖南常德 415000）

0 概述

桁架优化的目的通常为在满足指定性能要求的同时实现重量最小化。由于在实际工程问题中往往存在离散变量，序列线性规划［1］、准则法［2］等成熟的优化方法并不适用，因此研究者通常采用遗传（GA）算法［3］、粒子群优化（PSO）算法［4］、萤火虫（FA）算法［5］等智能算法来解决此类问题。

STORN 等人［6］于1997 年提出的差分进化（DE）算法是较为高效的算法之一。DE 是一种基于种群的全局搜索方法，通过变异、交叉和选择等步骤将种群进化至最优解，具有控制参数少、收敛速度快、算法稳健性强等优点［7］。近十年来，已有很多研究人员［8-9］对DE 算法进行了改进，并应用于工程问题中［10-11］。

然而，这些改进多是集中在实验个体的生成和选择机制上，对种群规模NP 的讨论则相对较少。NP 对算法性能有显著的影响，如小规模种群收敛较快，但容易导致进化早熟收敛或停滞，大规模种群全局搜索能力较强，但收敛速度慢［12］。文献［6］给出NP 的参考范围是5D～10D，其中D为问题的维数。文献［13］提出使NP 每隔一定代数自动减半。文献［14］提出NP 随着进化线性减少，其固定参数无法根据进化过程自适应调整。关于NP 的自适应研究相对较少，主要基于以下两种方法：一种方法［15］是通过比较种群多样性的实际值与理论值的大小自适应地调整NP，但其认为种群多样性理论值应随着进化过程线性降低至0，与实际情况不符；另一种方法［16-18］是以上一代或几代最优解是否得到了更新为依据，自适应地调整NP，文献［16-17］认为当最优解更新时，NP 应减小，而文献［18］则认为应增大。由于两者并未互相比较，且各自均包含对DE 算法的其他改进，此种NP 自适应方法的合理性和有效性尚需进一步讨论。

此外，在使用智能算法处理桁架优化问题时，结构分析往往占据大部分的计算量。因此，结构分析次数很大程度上决定算法效率。目前的技术大多通过提高算法自身性能来减少结构分析次数，而结合桁架优化问题的特点，合理规避结构分析的工作则较少。文献［9］使用已知的最接近的目标个体的适应度预估实验个体的适应度，但该方法在种群规模不够大时正确率较低。文献［19］使用局部代理模型代替部分结构分析，但准确度难以保证。文献［20］在对粒子群优化（PSO）算法的研究中指出，PSO 更新粒子位置只需最佳个体位置，因此无需对目标函数已经大于最佳个体适应度的实验个体进行结构分析，从而大幅减少结构分析次数。但由于算法基本原理不同，该方法目前未能应用于差分进化算法中。

本文对基本DE 算法进行改进，提出一种自适应调整变异策略和种群规模的改进离散差分进化算法。通过自适应变异策略和种群缩减策略提高算法效率，在选择阶段前舍弃较大的实验个体以规避结构分析次数，采用将数值间的距离转化为概率的离散化技术来处理离散变量并保持种群多样性。

1 离散桁架优化问题

1.1 优化问题描述

桁架优化问题旨在使结构重量最小化的同时满足位移、应力、屈曲等约束，通常包含尺寸优化和形状优化。其中，尺寸优化的设计变量为离散的杆件横截面积，形状优化的设计变量为连续的节点坐标。因此，优化问题可以描述如下：

其中，f（x）是表示结构重量的目标函数，x是包含桁架n个尺寸变量和m个形状变量的D维向量，ρi和li分别是第i根杆的密度和长度，Δ（x）、σ（x）和λ（x）分别是节点位移、杆件应力和屈曲应力，应分别在各自的许用范围［Δ］、［σ］和［λ］内，xi是第i个尺寸变量，从许用离散集Xopt中选择，xj是第j个形状变量，介于其上下界之间。

1.2 约束处理方法

为处理式（1）中的约束，本文使用Oracle 罚函数法［21］，将有约束问题转化为无约束问题：

其中，p（x）是约束罚函数，其表达式为：

其中，Ω、res（x）和α分别是问题的当前已知最优解、约束违反总和以及控制参数，分别由式（4）～式（6）得出：

其中，a=｜f（x）-Ω｜，b=res（x），Ω初值取109，之后根据求解过程不断更新，q是优化问题的约束个数，g（xi）是第i个约束函数，λ是控制约束严格程度的常数，在本文中取10，α根据情况有4 种取值，目的是使罚函数过渡平滑且区分度高。

Oracle 罚函数法特别适用于智能算法，其优点在于控制参数Ω唯一且简单、全局搜索能力和稳健性强。更加详细的信息可以参考文献［21］。

2 差分进化算法

差分进化（DE）算法是最有效的全局搜索方法之一，被广泛用于解决工程优化问题。该算法包括4 个主要阶段。

1）初始化

通过从搜索空间中随机抽样来创建初始种群。例如，第i个个体xi初始化为：

2）变异

执行变异操作，利用每个目标个体xi生成一个变异个体vi。DE 通常使用如下4 种常用的变异操作：

其中，整数r1、r2、r3、r4、r5从区间［1，NP］中随机选择，并且使得i≠r1≠r2≠r3≠r4≠r5，变异算子F在区间［0，1］中随机选择，xbest是当前种群的最佳个体。如果变量超出边界，则执行下述边界处理方法：

3）交叉

通过交叉操作替换变异个体的部分元素，创建实验个体ui。最常见的交叉方法是二项式交叉：

其中，i∈｛1，2，…，NP｝，j∈｛1，2，…，D｝，整数irand从区间［1，D］中随机选择，交叉算子CR 在区间［0，1］中随机选择。

4）选择

将实验个体ui与目标个体xi进行比较，以选择具有较低目标函数值f的下一代：

3 改进的离散差分进化算法

本文提出一种改进的离散差分进化（AMPDDE）算法，通过4 项改进处理离散桁架优化问题，大幅减少了结构分析次数。

3.1 自适应变异策略

本节基于种群多样性自适应地选择变异策略。首先参考文献［22］种群多样性的方法：

其中，fbest和fmean分别是种群内个体目标函数的最小值与平均值。与其他种群多样性的表示方法［15，23-24］相比，该方法计算简单，且无需额外增加计算量。

本文采用如下变异策略：

其中，Pf是变异比例算子，计算公式为：

rand/1 具有很强的全局搜索能力，但收敛速度较慢，而current-to-best/1 具有较快的收敛速度，但容易陷入局部最优［25］，Pf以概率的形式控制上述两种方法的占比，利用delta 在求解过程中总体下降这一趋势，实现了从注重全局搜索能力到注重收敛速度的平滑过渡。

3.2 自适应种群规模缩减策略

本节以减少结构分析次数为目标，提出一种基于种群多样性自适应缩减种群规模的策略，通过三重判定，确保种群在恰当的时机舍弃恰当的个体以缩减群规模，旨在减少计算量的同时维持种群多样性：

其中，diffmin为当前种群内个体差异度最小值的估计值，其计算方法为先将种群个体按照适应度排序，然后按照下式计算：

其中，cos为两个个体作为向量夹角的余弦值，该方法避免了计算两两个体之间差异度所需的较大计算量，外部存档H为diffmin的10 个历史最低值的集合，当进化代数不足10 时，取全部历史值，其长度设为10 是为了在及时更新的同时，中和个别极端值的影响，mean（H）为H中所有元素的算术平均值。当3 个判定全部为真时，舍弃当前种群内差异度最小的一对个体中较差的个体xk，并使NP 减1。以上3 个判定具有以下的作用：

1）judge1用于设置NP 下限，以免进化停滞。

2）judge2中Pf与种群多样性delta 成反比，且随着进化代数的增加呈上升趋势，从而以概率的形式控制求解过程中NP 减小的时机，使得进化前中期NP几乎不变以保持较高的全局搜索能力，而在后期及时减小以加快收敛并减少结构分析次数。

3）judge3用于判断当前种群内是否存在高度相似的个体，结合前面两重判定，使得每次种群缩减时舍弃的都是高度相似的一对个体中较差的个体，以维持种群多样性。

选择舍弃相似个体中的一个而非最差个体的原因在于，进化的前提是存在差分向量，由式（13）可知，变异时所有目标个体均可用于提供符号和数值随机的差分向量，与个体是最优还是最差无关，但与个体之间是否相似有关。因此，最差个体的价值大于相似个体，舍弃相似个体能减少某些局部最优个体及其相似变体迅速控制整个种群，从而使算法具有早熟收敛的可能。

通过上述自适应种群缩减策略，确保种群在恰当的时机舍弃恰当的个体，从而在减少结构分析次数的同时，削弱种群缩减对种群多样性的影响。

3.3 结构分析次数减少策略

本节提出一种适用于差分进化算法的减少结构分析次数的策略：在计算个体适应度前首先计算其目标函数，并直接舍弃目标函数大于阈值的个体，从而规避不必要的结构分析。显然，阈值越大，误判率越低，本策略减少结构分析次数的效果就越弱；当阈值取目标个体适应度的最大值max（fit）时，误判率减至0。阈值越小，误判率越大，较小的阈值能够显著减少结构分析次数，但过低的阈值可能导致进化停滞。经过实验，本节中的阈值取目标个体适应度的中位数median（fit）与最大值max（fit）这两者的平均数。

此外，上述操作导致存留下来的实验个体的数量可能少于目标个体，基本DE 的选择方式不可行，因此本文引入文献［26］提出的精英选择技术以适配算法的选择阶段。精英选择技术的过程如下：首先将实验个体组成的种群P与目标个体组成的C合并，得到组合种群Q；然后从Q中选择NP 个最优秀的个体进入下一代。精英选择技术保证优秀个体全部进入下一代，能够加快算法的收敛速度，并且与全局搜索能力强的rand/1 策略配合良好。

3.4 离散变量处理方法

本节提出一种简便的连续变量离散化方法，以将差分进化算法应用于离散变量问题：

其中，xlow和xhigh分别是许用离散集Xopt中与xi，j上下相邻的元素。与直接离散至最接近的许用离散值的方法［8］相比，本文方法通过将数值之间的距离转化为概率，尽可能地保留了连续值xi，j所传递的信息，从而有利于保持种群多样性。

3.5 AMPDDE 算法

本文将上述4 种改进方法集成到DE 算法中，并提出AMPDDE 算法，算法流程如图1 所示。

图1 AMPDDE 算法流程Fig.1 Procedure of AMPDDE algorithm

在图1 中，Itermax是最大迭代次数，tolerance 是容差，本文取10-6，当种群多样性delta 低于容差时进化结束，以避免无用计算。

4 算例分析

本节将AMPDDE 算法用于求解3 个含有离散变量的桁架优化问题，包括10 杆平面桁架尺寸优化问题、39 杆空间桁架尺寸和形状优化问题以及200 杆平面桁架尺寸优化问题。3 个问题的NP 分别取30、25和40，其余参数相同，分别为：F=rand［0.4，1］，CR=rand［0.7，1］，Itermax=300。其中，F和CR 的取值范围均采用广泛认可的推荐值，NP 初值经过测试选取。所有问题均使用Python 3.6.7 实现，其中有限元分析过程调用了文献［27］编写的Feon 框架。每个问题均运行20 次，所得结果与其他文献中的研究结果进行了对比验证。

4.1 10 杆平面桁架

以10 杆平面桁架尺寸优化问题为例，分析NP初值对算法性能的影响，测试算法搜寻全局最优解的能力。桁架结构如图2所示，材料密度为2 768 kg/m3，弹性模量为68.948 GPa，结构受应力和位移约束，所有杆件的许用应力均为±172.369 MPa，所有节点在x和y方向的许用位移为±5.08 cm，位于节点2 和节点4 的竖直向下载荷P大小均为444.822 kN，变量为全部10 根杆的横截面积，许用离散集为｛10.452，11.613，12.839，13.742，15.355，16.903，16.968，18.581，18.903，19.935，20.194，21.806，22.387，22.903，23.419，24.774，24.968，25.032，26.968，27.226，28.968，29.613，30.968，32.064，33.032，37.032，46.581，51.419，74.193，87.097，89.677，91.613，100.000，103.226，109.032，121.290，128.387，141.935，147.742，170.967，193.548，216.129｝，单位为cm2。该问题已有多种算法研究，如文献［22］提出的自适应精英差分进化算法（aeDE）、文献［28］提出的电磁学萤火虫算法（EFA）等。

图2 10 杆平面桁架结构Fig.2 Structure of 10-bar plane truss

为分析NP 初值对算法性能的影响，取NP 从10 到40各运行20次，结果如表1和图3所示。可见，随着NP的增加，平均结构分析次数基本呈线性上升，最小重量在NP=25 时达到最低值，而平均重量在NP 达到30 后基本不再变化，且几乎与最小重量重合。因此，本文取NP=30，以获得最优解和计算效率的平衡。

表1 NP 初值对算法性能的影响Table 1 Impact of NP initial value on algorithm performance

图3 NP 对算法性能的影响Fig.3 Effect of NP on algorithm performance

AMPDDE 算法在20 次运行后与其他算法的对比结果如表2 所示，其中适应度的平均值和最小值曲线如图4 所示，可见平均值和最小值在中后期高度重叠，说明算法具有较好的稳健性。最小重量为2 492.795 kg，与DE［22］、aeDE［22］、EFA［22］等算法相同，均为全局最优解；最少结构分析次数、平均结构分析次数和标准差分别为1 664、1 754 和7.73，均低于其余算法，说明AMPDDE 算法具有较高的效率和稳健性。

表2 10 杆平面桁架尺寸优化结果Table 2 Optimization results of 10-bar plane truss size

图4 10 杆平面桁架20 次优化适应度曲线Fig.4 20 times optimized fitness curve of 10-bar plane truss

4.2 39 杆空间桁架

本文以39 杆空间桁架尺寸和形状优化问题为例，测试算法的收敛速度以及同时处理连续和离散变量的能力，39 杆空间桁架结构如图5 所示。桁架结构如图5（a）所示，节点坐标如表3 所示，材料密度为7 800 kg/m3，弹性模量为210 GPa，杆件受应力和位移约束，许用应力均为±240 MPa，所有节点在x、y和z方向的位移均不能超过±4 mm，位于节点13、14、15 的竖直向下的载荷均为10 kN。该问题共有11 个变量，其中5 个离散变量为杆件1、4、7、10、13 的横截面积，许用离散集为｛0.1，0.2，…，13｝，单位为cm2；6 个连续变量为节点4、7、10 在y轴和z轴的坐标，其上下限分别为：y4，y7，y10∈［0.28，1］，z4∈［0，2］，z7∈［1，3］，z10∈［2，4］，单位为m。杆件横截面积的对称性表示为Ai=Ai+1=Ai+2，i=1，4，7，10；Aj=Aj+1，j=13，14，…，38。该问题由文献［29］提出的改进离散粒子群算法（IDPSO）、文献［8］提出的改进（μ+λ）-约束离散差分进化算法（D-ICDE）和文献［30］提出的梯度估计多种群粒子群算法（GEMPSO）等进行分析。

图5 39 杆空间桁架结构Fig.5 Structure of 39-bar space truss

表3 39 杆空间桁架节点位置数据Table 3 Node position data of 39-bar space truss

AMPDDE 算法在20 次运行后与各算法的对比结果如表4 所示，其中适应度的平均值和最小值曲线如图6 所示。20 次运行得到的最小重量为133.131 1 kg，对应结构分析次数为1 827 次，该次运行的适应度曲线如图7 所示，最优解结构与原始结构的对比见图5（b）。可见，算法在1 000 次结构分析时重量已经低于135 kg，而在约1 400 次结构分析后几乎完全收敛，收敛性良好。显然，其结果明显优于最小重量为176.834 kg 的IDPSO［29］；与D-ICDE［8］在1 140 次结构分析后得到140.35 kg 的最优解相比，本文算法在相同结构分析次数时最优解更轻，且尚有下探能力，完全收敛后得到的最优解轻了5.14%，体现出AMPDDE 算法良好的开发性；与GEMPSO［30］在8 336 次结构分析后得到133.166 kg 的最优解相比，本文算法最优解轻了0.034 9 kg，且结构分析次数远低于前者，体现出AMPDDE 算法较高的效率。

表4 39 杆空间桁架尺寸和形状优化结果Table 4 Optimization results of 39-bar space truss size and shape

图6 39 杆空间桁架20 次优化适应度曲线Fig.6 20 times optimized fitness curve of 39-bar space truss

图7 39 杆空间桁架最优解适应度曲线Fig.7 Optimal solation fitness curve of 39-bar space truss

4.3 200 杆平面桁架

本节讨论200 杆平面桁架的尺寸优化问题，验证算法处理大中型多工况问题时的性能。桁架结构如图8 所示，材料密度为7 833 kg/m3，弹性模量为206.843 GPa，杆件受应力约束，许用应力均为±68.948 MPa。

图8 200 杆平面桁架结构Fig.8 Structure of 200-bar plane truss

施加载荷分为3 种工况：1）在下列节点施加大小4.448 kN 方向为x轴正方向的力：1，6，15，20，29，34，43，48，57，62 和71；2）在下列节点施加大小44.482 kN 方向为y轴负方向的力：1，2，3，4，5，6，8，10，12，14，15，16，17，18，19，20，22，24，26，28，29，30，31，32，33，34，36，38，40，42，43，44，45，46，47，48，50，52，54，56，57，58，59，60，61，62，64，66，68，70，71，72，73，74 和75；3）工况1 和工况2 的叠加。所有杆件被分为29 组，组内杆件具有相同的截面积，因此共有29 个离散的尺寸变量。杆件截面积的许用离散集为｛0.645，2.239，2.839，3.477，6.155，6.974，7.574，8.600，9.600，11.381，13.819，17.400，18.064，20.200，23.000，24.600，31.000，38.400，42.400，46.400，55.000，60.000，70.000，86.000，92.193，110.774，123.742，152.774，181.161，217.419｝，单位为cm2。该问题已由文献［31］提出的改进遗传算法（IGA）、文献［22］提出的自适应精英差分进化算法（aeDE）以及文献［28］提出的电磁学萤火虫算法（EFA）等进行分析。

AMPDDE 算法在20 次运行后与上述算法的对比结果如表5 所示，其中适应度的平均值和最小值曲线如图9 所示。AMPDDE 算法在5 536 次结构分析后得到重量为12 483.447 kg 的最优解，明显优于IGA［31］、DE［22］和aeDE［22］等算法。与EFA算法［28］在6 110 次结构分析后得到12 449.563 kg 的最优解相比，本文算法最优解重了0.27%，但结构分析次数少了9.39%；平均结构分析次数稍有增多，但最大重量、平均重量和标准差更低，体现了本文算法具有较好的稳健性。

表5 200 杆平面桁架尺寸优化结果Table 5 Optimization results of 200-bar plane truss size

续表

图9 200 杆平面桁架20 次优化适应度曲线Fig.9 20 times optimized fitness curve of 200-bar plane truss

5 结束语

为提高离散桁架优化问题的计算效率，本文提出一种改进的离散差分进化（AMPDDE）算法来大幅减少结构分析次数。对基本差分进化算法进行改进，基于种群多样性自适应地选择变异策略，根据个体差异度缩减种群规模，在结构分析前计算其目标函数，舍弃目标函数过大的个体以减少计算量，引入精英选择技术以适配算法选择阶段，并提出一种将连续值与邻近离散值之间的距离转化为概率的离散化方法。通过3 个经典桁架优化算例对比本文算法与6种传统算法的性能，数值分析结果表明，AMPDDE算法在保证最优解质量的同时，结构分析次数明显少于其他算法。下一步将在尺寸和形状优化的基础上，使用本文算法对桁架进行拓扑优化，以实现更高层次且更全面的结构优化。