朱大林，張燈皇，鄭曉東，王進學

（三峽大學機械與動力學院，湖北宜昌 443002）

基于多目標元胞遺傳算法的桁架結(jié)構(gòu)優(yōu)化設(shè)計

朱大林，張燈皇，鄭曉東，王進學

（三峽大學機械與動力學院，湖北宜昌 443002）

為了使桁架結(jié)構(gòu)的設(shè)計更符合工程實際惰況，建立了同時最小化結(jié)構(gòu)總質(zhì)量和節(jié)點位移的多目標優(yōu)化模型。采用離散實數(shù)編碼方式，使多目標元胞遺傳算法適用于優(yōu)化模型的求解，同時改進了算法的交叉變異算子，使算法保持較好的全局探索和局部尋優(yōu)能力。運用該算法對經(jīng)典空間桁架優(yōu)化問題進行求解，并與NSGA-II的優(yōu)化結(jié)果進行對比分析，結(jié)果表明該算法獲得的Pareto前端更加均勻，解的精度更高，極端點值域更廣，是解決此類離散優(yōu)化問題的有效算法。

桁架結(jié)構(gòu)；多目標優(yōu)化；離散實數(shù)編碼；元胞遺傳算法

0 引言

桁架結(jié)構(gòu)因其桿件主要承受軸向拉力或壓力，從而可以充分發(fā)揮材料的強度，并且結(jié)構(gòu)自重輕、造價低以及施工簡單，因此被廣泛的應(yīng)用于建筑結(jié)構(gòu)、橋梁設(shè)計、輸電網(wǎng)架、施工支護等諸多方面［1］。在給定的工況和約束條件下，合理的分配桁架結(jié)構(gòu)中各桿件的橫截面積，使設(shè)計目標盡可能的優(yōu)化，將具有重要的工程意義。

目前，大多數(shù)學者［2-4］對桁架結(jié)構(gòu)的優(yōu)化研究主要集中在以減輕結(jié)構(gòu)總質(zhì)量為目的的單目標優(yōu)化方面。然而，在許多實際工程結(jié)構(gòu)中需要對桁架進行多目標優(yōu)化，比如同時最小化結(jié)構(gòu)總質(zhì)量和指定節(jié)點最大位移。事實上，當結(jié)構(gòu)的總質(zhì)量減輕時，往往會使某些節(jié)點的位移增大，給結(jié)構(gòu)的使用造成限制。因此，需要統(tǒng)籌兼顧這兩個相互矛盾的指標，建立多目標優(yōu)化模型，以提供更加科學合理的方案。針對桁架結(jié)構(gòu)多目標優(yōu)化問題的研究，一些國內(nèi)外學者利用多目標進化算法進行了求解。C.A.Coello等［5］提出了一種基于minmax優(yōu)化的遺傳算法，并將該方法成功應(yīng)用于25桿空間桁架和200桿平面桁架的多目標優(yōu)化設(shè)計。Luh和Chueh［6］提出了利用細胞因子處理約束的免疫算法，通過數(shù)值實驗表明該方法可以作為求解結(jié)構(gòu)優(yōu)化的一種手段。任鳳鳴等［7］使用群搜索算法對桁架結(jié)構(gòu)進行多目標優(yōu)化，該方法具有較快的收斂速度。雖然這些優(yōu)化研究已經(jīng)取得了一定的成果，但是設(shè)計出編碼方式簡單、全局探索和局部尋優(yōu)能力較強的算法仍然是此類問題研究的熱點之一。

多目標元胞遺傳算法［8］（Cellular Genetic Algorithm for Multi-objective Optimization，MOCell）是一種將元胞自動機模型和多目標優(yōu)化理論引入遺傳算法而發(fā)展起來的進化算法，該算法在多樣性和收斂性方面均表現(xiàn)出良好的性能，并在工程中得到了很好的應(yīng)用［9-11］。由于桁架結(jié)構(gòu)的設(shè)計變量通常為一些離散的實數(shù)，本文采用離散實數(shù)編碼方式，使MOCell適用于優(yōu)化模型的求解，并提出了改進的遺傳操作算子，使算法在求解該問題時保持較好的性能。為了驗證MOCell求解該問題的有效性，分別運用MOCell和NSGAII［12］對經(jīng)典空間桁架優(yōu)化問題進行求解，并將優(yōu)化結(jié)果進行比較分析。

1 桁架結(jié)構(gòu)多目標優(yōu)化模型

在工業(yè)生產(chǎn)中，桁架結(jié)構(gòu)的桿件橫截面積一般都已經(jīng)標準化，即從給定的離散實數(shù)集合中選取橫截面積。由于應(yīng)用工況不同，要求也不同，結(jié)構(gòu)的優(yōu)化設(shè)計可以有多個優(yōu)化目標，如結(jié)構(gòu)總質(zhì)量最小、指定節(jié)點位移最小、自振頻率最大等等。本文研究的是在滿足桿件應(yīng)力約束條件的情況下，尋找出最優(yōu)的桿件橫截面積組合，使得桁架結(jié)構(gòu)的總質(zhì)量最小以及指定節(jié)點位移最小。以n桿桁架為研究對象，基本參數(shù)（結(jié)構(gòu)尺寸、材料密度、彈性模量、最大允許應(yīng)力、最大允許位移等）已知，其多目標優(yōu)化設(shè)計數(shù)學模型可表示為：

式中：A=［A1，A2，…，Am］T為設(shè)計變量，m為桿件的組數(shù)；W為桁架結(jié)構(gòu)的總質(zhì)量，Li，Ai，ρi分別為第i組桿件的長度、橫截面積以及密度；ujl為各工況下節(jié)點j在給定方向l上的位移；（A）≥0為第i組桿件的應(yīng)力約束條件；［σi］，σi分別為第i組桿件的應(yīng)力允許值和各工況下的最不利應(yīng)力值；｛a1，a2，…，aq｝為可選的桿件橫截面積，一般為離散實數(shù)集合；f1，f2為子目標函數(shù)。

2 桁架結(jié)構(gòu)優(yōu)化的多目標元胞遺傳算法

2.1 多目標元胞遺傳算法框架

元胞遺傳算法（Celluar Genetic Algorithms）［13］是一種將遺傳算法基本理論和元胞自動機模型相互結(jié)合而發(fā)展起來的進化算法，該算法不僅繼承了遺傳算法的優(yōu)良品質(zhì)，而且擁有元胞自動機的部分特性。同一般遺傳算法不同的是，元胞遺傳算法將種群中的每個個體分布在一個環(huán)形聯(lián)通的網(wǎng)狀空間拓撲結(jié)構(gòu)中，圖1a、圖1b分別顯示了一般遺傳算法中隨機分布的種群和元胞遺傳算法中具有元胞拓撲結(jié)構(gòu)的種群。元胞遺傳算法中每個個體具有相同的鄰居結(jié)構(gòu)，并且每個個體只能與其鄰近個體進行遺傳操作。如圖2所示，為元胞遺傳算法中個體的進化循環(huán)過程，相對于個體間隨機遺傳操作的一般遺傳算法而言，元胞遺傳算法能夠使不同范圍的個體快速收斂到搜索空間的不同區(qū)域，形成多個小生鏡，每個小生境的最優(yōu)解又能夠在整個種群中緩慢擴散，保持種群多樣性，從而使算法在具有較快收斂速度的同時，又具有較好的空間探索能力。多目標元胞遺傳算法是在元胞遺傳算法的基礎(chǔ)上，將多目標優(yōu)化理論融合到元胞遺傳算法中發(fā)展形成的多目標優(yōu)化算法。

圖1 種群結(jié)構(gòu)示意圖

圖2 元胞遺傳算法中個體的進化循環(huán)過程

2.2 染色體編碼方式

染色體的編碼方式在很大程度上取決于優(yōu)化問題的類型，同時，編碼方式的好壞也決定了遺傳算子能否被很好的應(yīng)用。由于桁架結(jié)構(gòu)多目標優(yōu)化模型中的設(shè)計變量從給定的離散實數(shù)集合中取值，為了使MOCell適用于對優(yōu)化模型的求解，本文采用離散實數(shù)編碼方式，該編碼方式簡單易實現(xiàn)，并對該類優(yōu)化問題具有通用性。采用離散實數(shù)編碼的染色體結(jié)構(gòu)如圖3所示。

圖3 采用離散實數(shù)編碼的染色體結(jié)構(gòu)

其中，api為給定的離散實數(shù)集合 ｛a1，a2，…，aq｝中的任一元素；n為染色體的長度；p1p2…pi…pn為自然數(shù)1，2，3，…，n的任一組合。

2.3 交叉算子

在遺傳進化過程中，交叉算子是產(chǎn)生新個體的主要方法。目前，模擬二進制交叉算子［14］（Simulated Binary Crossover，SBX）是實數(shù)編碼的多目標進化算法中最常用的交叉算子，其模擬的是二進制串單點交叉算子的工作原理，具有良好的全局探索能力。為了將SBX算子應(yīng)用到桁架結(jié)構(gòu)的優(yōu)化求解中，同時考慮到染色體的編碼方式，本文提出了一種改進的SBX算子：

其中，β為隨機變量，在每一維上都需要重新生成，生成方式如下：

其中，u為均勻分布于（0，1）區(qū)間上的隨機數(shù)；η為任意非負實數(shù)。

然后，將給定離散實數(shù)集合中的實數(shù)按照大小進行排序，相鄰的兩個數(shù)形成閉區(qū)間，對于SBX交叉操作獲得的子代個體，判別其每一個基因ci的值位于哪一個區(qū)間，選取該區(qū)間左端點值作為基因ci的修正值，如果基因ci的值小于給定離散實數(shù)集合中的最小值則選取該最小值作為修正值，如果基因ci的值大于給定離散實數(shù)集合中的最大值則選取該最大值作為修正值。

2.4 變異算子

多項式變異算子（Polynomial Mutation）是多目標進化算法中廣泛使用的變異算子，該算子能較好地改善算法的局部尋優(yōu)能力，維持種群的多樣性，防止出現(xiàn)早熟現(xiàn)象。鑒于此，針對本文的編碼方式，對多項式變異算子進行改進，具體運算步驟如下：

首先，對SBX算子所得個體c=（c1，c2，…，cn）中的任一基因ci，按照以下方式產(chǎn)生新的基因：

其中，u為均勻分布于（0，1）區(qū)間上的隨機數(shù)；ηm是分布指數(shù)，為任意非負實數(shù)。

然后，判別基因c＇i的值位于給定離散實數(shù)集合的哪一個區(qū)間，取該區(qū)間左端點值作為其修正值，如果基因c＇i的值小于集合中的最小值則取該最小值作為修正值，如果大于集合中的最大值則取該最大值作為修正值。

2.5 約束處理方法

在多目標優(yōu)化中，對約束條件的處理方式一般采用罰函數(shù)法和多目標法［15］。本文采用Deb［16］提出的多目標法處理約束，具體如下：

（1）當在兩個比較的個體中，一個個體為可行解，另外一個個體為不可行解時，選擇可行解；

（2）當兩個比較的個體均為可行解時，先比較二者的支配關(guān)系，選擇非支配的個體，如果均為非支配解，選擇擁擠距離大的個體；

（3）當兩個比較的個體均為不可行解時，選擇違反約束條件程度小的個體；

2.6 算法流程與步驟

綜合2.1～2.5節(jié)，本文采用的MOCell算法其基本流程與步驟如下：

Step1：對MOCell中的相關(guān)參數(shù)進行設(shè)置。包括個體更新策略和鄰居結(jié)構(gòu)類型（本文采用異步更新策略和Moore型鄰居結(jié)構(gòu)）、種群大小、最大評價次數(shù)、交叉概率和變異概率等。

Step2：初始化種群。按照2.2節(jié)中提出的離散實數(shù)編碼方式，隨機生成初始種群并將種群中的每個個體放置于環(huán)形聯(lián)通的網(wǎng)狀空間拓撲結(jié)構(gòu)中。

Step3：選擇操作。根據(jù)給定的更新策略和鄰居結(jié)構(gòu)，選取中心個體及其鄰居，采用二進制錦標賽選擇算子從鄰居中選出父代個體。

Step4：交叉變異操作。利用2.3節(jié)和2.4節(jié)中改進的SBX交叉和多項式變異算子，對父代個體進行運算得到子代個體。

Step5：個體更新。根據(jù)2.5節(jié)中對約束條件的處理方式，比較子代個體和父代個體的優(yōu)劣，如果子代優(yōu)于父代，則用子代替換父代，否則不替換。

Step6：判斷是否滿足終止條件。若評價次數(shù)未達到設(shè)定值，則轉(zhuǎn)至Step3，否則退出迭代，得到經(jīng)過優(yōu)化后的種群。

3 實例求解及結(jié)果分析

圖4 25桿空間桁架

如圖4所示25桿空間桁架，已知材料的彈性模量E=68950MPa，密度ρ=2768kg/m3，桿件尺寸如圖所示，其中L=635mm，可選桿件橫截面積集合D=｛0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1.0，1.1，1.2，1.3，1.4，1.5，1.6，1.7，1.8，1.9，2.0，2.1，2.2，2.3，2.4，2.5，2.6，2.8，3.0，3.2，3.3，3.4｝× 645.16mm2，桿件分組見表1，每組桿件的應(yīng)力約束均為［-275.8，275.8］MPa，節(jié)點載荷見表2。以桿件橫截面積為設(shè)計變量，同時最小化桁架結(jié)構(gòu)的總質(zhì)量和①～⑥節(jié)點在x-y-z三個方向的最大位移。

為了驗證MOCell求解桁架結(jié)構(gòu)多目標優(yōu)化模型的有效性，分別運用MOCell和NSGA-II對上述桁架進行優(yōu)化計算，并將優(yōu)化結(jié)果進行對比分析。兩種算法的參數(shù)設(shè)置為：均采用離散實數(shù)編碼，改進的SBX算子和多項式變異算子；種群大小為100，最大評價次數(shù)為25000，交叉概率為0.9，變異概率為1/len，len為變量維數(shù)。這兩種算法分別對優(yōu)化模型進行30次獨立運行計算。

表1 25桿空間桁架桿件分組

表2 25桿空間桁架節(jié)點載荷

圖5 25桿空間桁架優(yōu)化MOCell和NSGA-II獲得的Pareto前端比較

圖6 25桿空間桁架優(yōu)化MOCell和NSGA-II獲得的Pareto前端豎向極端點分布比較

圖7 25桿空間桁架優(yōu)化MOCell和NSGA-II獲得的Pareto前端水平極端點分布比較

為了能直觀地了解算法的性能，繪制出MOCell和NSGA-II各自所得最優(yōu)Pareto前端對比圖，如圖5所示。從圖5可以看出，在參數(shù)一致的情況下，MOCell所得Pareto前端分布得更加均勻有致，并且更加趨于最優(yōu)，大部分的解都支配NSGA-II所得解，表明MOCell在求解該優(yōu)化問題時具有更好的收斂性和均勻性。為了比較兩種算法的擴展性，統(tǒng)計它們30次獨立運行所得Pareto前端的極端點，并利用箱形圖分別展示豎向極端點和水平極端點的分布情況，如圖6、圖7所示。箱形圖中的矩形條代表極端點值的四分位差，數(shù)學意義為極端點值的分布區(qū)域，矩形條越短意味著數(shù)據(jù)越集中，算法穩(wěn)定性越好，由圖可知，MOCell的矩形條較短，表明其穩(wěn)定性更好。矩形條中的線條代表數(shù)據(jù)的中位數(shù)，對于極端點，中位數(shù)越大表明極端點值域越廣，圖中MOCell所得兩類極端點的中位數(shù)都更大，表明其值域更廣，即擴展性更好。

圖8 25桿空間桁架優(yōu)化MOCell獲得的Pareto前端與單目標優(yōu)化結(jié)果比較

表3 不同方法的桿件橫截面積比較mm2

對于上述25桿空間桁架結(jié)構(gòu)，在應(yīng)力約束保持不變，①～⑥節(jié)點在x-y-z三個方向的最大位移不超過8.889mm的情況下，最小化結(jié)構(gòu)總質(zhì)量。文獻［2-4］針對這一單目標優(yōu)化問題進行了求解，獲得的最優(yōu)解結(jié)果如表3和圖8所示，圖8中圓圈代表MOCell在30次獨立運行中得到的最優(yōu)Pareto前端。由圖表可知，在滿足約束的情況下，MOCell得到的Pareto前端中存在點A（總質(zhì)量為220.4920kg，位移為8.8660mm）支配文獻［2］和文獻［3］的最優(yōu)解，文獻［4］的最優(yōu)解則被Pareto前端中的其他解支配。由此可以證明單目標優(yōu)化得到的解并不一定是最優(yōu)的，MOCell的Pareto前端包含更多的可行解，能為結(jié)構(gòu)設(shè)計提供更多的方案。

4 結(jié)論

為了使桁架結(jié)構(gòu)的設(shè)計更接近工程實際，建立了同時考慮結(jié)構(gòu)總質(zhì)量和節(jié)點位移的多目標優(yōu)化模型。采用離散實數(shù)編碼，將MOCell引入對桁架結(jié)構(gòu)的優(yōu)化求解，并提出了改進的遺傳算子，使算法保持較好的全局搜索和局部尋優(yōu)能力。運用MOCell對25桿經(jīng)典空間桁結(jié)構(gòu)架優(yōu)化問題進行求解，并與NSGA-II的優(yōu)化結(jié)果進行比較，結(jié)果表明MOCell所得Pareto前端分布更加均勻、精度更高、極端點值域更廣。與單目標優(yōu)化進行對比，MOCell可以提供更多可行的設(shè)計方案。由此說明，MOCell能夠作為桁架結(jié)構(gòu)多目標優(yōu)化設(shè)計的有效方法。

［1］哈爾濱工業(yè)大學理論力學教研室.理論力學［M］.北京：高等教育出版社，2002.

［2］Shyue Jian，Pei Tse Chow.Steady-state genetic algorithms for discrete optimization of trusses［J］.Computers and Structures，1995，56（6）：979-991.

［3］Fuat Erbatur，Oguzhan Hasancebi，et al.Optimal design of planar and space structures with genetic algorithms［J］. Computers and Structures，2000，75：209-224.

［4］Rajeev S，Krishnamoorthy C.S.Discrete optimization of structures using genetic algorithms［J］.Journal of Structural Engineering，1992，118（5）：1233-1250.

［5］C.A.Coello，A.D.Christiansen.Multiobjective optimization of trusses using genetic algorithms［J］.Computers and Structures，2000，75（6）：647-660.

［6］Guan-Chun Luh，Chung-Huei Chueh.Multi-objective optimal design of truss structure with immune algorithm［J］. Computers and Structures，2004，82（11-12）：829-844.

［7］任鳳鳴，王春，李麗娟.多目標群搜索優(yōu)化算法及其在結(jié)構(gòu)設(shè)計中的應(yīng)用［J］.廣西大學學報（自然科學版），2010，35（2）：216-221.

［8］NEBRO A J，DURILLO J J，LUNA F，et al.MOCell：a cellular genetic algorithm for multiobjective optimization［J］.International Journal of Intelligent Systems，2009，24（7）：726-746.

［9］BRUDARU O，POPOVICID，COPACEANU C.Cellular genetic algorithm with communicating grids for assembly line balancing problems［J］.Advances in Electrical and Computer Engineering，2010，10（2）：87-93.

［10］LIXunbo，WANG Zhenlin.Cellular genetic algorithms for optimizing the area covering ofwireless sensor network［J］. Chinese Journal of Electronics，2011，20（2）：352-356.

［11］朱大林，詹騰.基于元胞多目標遺傳算法的蝸桿優(yōu)化設(shè)計［J］.計算機工程與應(yīng)用，doi：10.3778/j.issn.1002-8331.1307-0206.

［12］DEB K，PRATAP A，MEYARIVAN T.A fast and elitist multi-objective genetic algorithm：NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

［13］Bernab＇e Dorronsoro，Enrique Alba.A Simple Cellular Genetic Algorithm for Continuous Optimization，2006 IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Centre Hotel，Vancouver，BC，Canada，2006（7）：16-21.

［14］Deb K，Karthik S，Okabe.T.Self-Adaptive Simulated Binary Crossover for Real-Parameter Optimization［J］.Proceedings of GECCO：Genetic and Evolutionary Computation Conference，2007：118-119.

［15］王勇，蔡自興，周育人，肖赤心.約束優(yōu)化進化算法［J］.軟件學報，2009，20（1）：11-29.

［16］Deb K.An efficient constraint handling method for genetic algorithms［J］.Computation Methods in Applied Mechanics and Engineering，2000，86（2-4）：311338.

（編輯 李秀敏）

Optimal Design of Truss Structure Based on Cellular Genetic Algorithm for Multi-objective Optimization

ZHU Da-lin，ZHANG Deng-huang，ZHENG Xiao-dong，WANG Jin-xue
（College of Mechanical&Power Engineering，China Three Gorges University，Yichang Hubei443002，China）

In order to make the design of truss structure more accord with the actual engineering，an optimization model was established with the goals of the minimum structural mass and the nodal displacement. Based on discrete real number coding，improved simulated binary crossover and polynomial mutation，cellular genetic algorithm for multi-objective optimization（MOCell）was successfully applied to the optimal model，integrating excellent ability of global exploration and local exploitation.To evaluate the algorithm，a comparison with NSGA-II on the optimization problem of the well-known space truss was conducted.The results indicated that the pareto front of MOCell had more uniform distribution，higher accuracy and wider range of the extreme points.It could solve this kind of discrete optimization problems effectively.

truss structure；multi-objective optimization；discrete real number coding；cellular genetic algorithm

TH122；TG659

A

1001-2265（2015）03-0016-05 DOI：10.13462/j.cnki.mmtamt.2015.03.005

2014-07-01；

2014-09-26

朱大林（1957—），男，湖北宜昌人，三峽大學教授，研究方向為智能制造、結(jié)構(gòu)優(yōu)化設(shè)計，（E-mail）dlzhu@ctgu.edu.cn。