基于改進離散差分進化算法的桁架優化

王 爍，谷正氣，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算法在保證最優解質量的同時，結構分析次數明顯少于其他算法。下一步將在尺寸和形狀優化的基礎上，使用本文算法對桁架進行拓撲優化，以實現更高層次且更全面的結構優化。