離散變量結構優化方法研究現狀及趨勢

李彥蒼，趙麗娜

(河北工程大學土木工程學院，河北邯鄲056038)

在實際結構設計中，有時出現某些或全部設計變量只能取限定離散值的情況［1]。例如，鋼筋混凝土結構構件的截面尺寸需要模數制的原則，鋼結構構件的截面需要考慮型鋼表或截面要求和特定組的離散值。采用平常的優化設計方法，必須通過處理所得解以滿足工程設計規范和各項技術標準，但這種經過連續變量優化方法處理后得到的離散結果不一定可行或最優［2]。因此，建立適合離散變量結構優化設計的方法是很有工程實用價值的［3]。

本文介紹了離散變量結構優化設計理論及設計方法的新成果，并對其發展及研究方向做出展望，指出了各離散變量結構優化方法在使用過程中的優缺點，并提出蟻群算法是一個有發展前途的離散變量結構優化方法。

1 離散變量結構優化設計特點

由于設計變量具有離散性，所以離散變量結構優化設計數學模型中目標函數和約束函數具有不連續的特點，這樣就使得連續變量優化模型轉化為不可微的、非凸規劃模型，可行域變成可行集，連續變量優化中的許多有效的解析數學算法和優化條件對此也無效，如各種梯度算法中的敏度分析法，K－T條件，各對偶算法等。

離散變量結構優化設計的難點在于［5]:

(1)解析數學對此無能為力。在數學上，離散變量優化問題屬于組合優化問題，即從所有可能的組合中尋找最優解。此問題隨設計變量個數的增加，組合數隨其呈指數增加，遂出現“組合爆炸”的現象。若在尋找最優解過程中搜索的組合個數不能用明確的多項式表示，稱這種問題為NP困難問題。NP困難問題的難度在于隨著設計變量個數的增加，組合個數迅速增加［6－7]。對于大規模問題指數時間算法所花的時間是巨大的，甚至難以解決。

(2)在形狀優化中主要包括截面變量的優化，另外還有形狀(坐標)變量優化。同時處理性質不同的兩類變量優化不光工作量大，難度也較大。

(3)拓撲優化與形狀優化近似，除截面變量優化外，還有拓撲(結點間有、無桿件連接)變量的優化。在處理不同性質的兩類變量優化困難下，還有桿件刪除，尤其是桿件恢復策略，若只有桿件的刪除而無桿件的恢復策略，通常情況得不到最優拓撲解。

(4)布局優化包括截面、形狀和拓撲三類性質的變量優化，很明顯同時處理三類不同性質的變量困難更大，計算工作量也增大較多。

(5)結構類型優化，這是最高層次的優化，難度也最大，迄今未見有關文獻。

2 離散變量結構優化方法

離散變量結構優化設計方法可分為三種:精確算法、近似算法、啟發式算法［8]。文獻［8－9]對傳統的優化設計方法如枚舉法、分支定界法、圓整法、割平面法、隱枚舉法、罰函數法、巴拉斯法、離散復合形法、整數梯度法等方法做了介紹和評價。這里主要介紹最近幾年新興起來的算法。

2.1 遺傳算法

遺傳算法是根據生物進化理論抽象出來的一種隨機、并行和自適應的優化算法，包括選擇、交叉和變異等過程［10]。其基本思想是，將設計變量編碼表示成染色體，染色體群通過復制、雜交和變異等過程，不斷進化并收斂到求解問題的最優解。對全局信息有效利用和隱含并行性是該法的兩大特點，特別是對目標函數、設計變量及可行域無特殊要求的特點，使得該方法的適用范圍較廣，天然適用于傳統尋優方法解決不了的復雜和非線性問題，對于離散變量的優化較有效［11]。張明輝等［12]采用遺傳算法對結構進行形狀優化，并給出了適應度函數的確定方法及對應力約束和幾何約束的處理方法。

遺傳算法在離散變量結構優化設計中表現了其獨特的優勢外，在結構優化設計中該算法最大的劣勢在于結構重分析次數過大，搜索效率偏低，還容易出現過早收斂等問題。對此，許多專家學者通過深入研究提出了各種改進的遺傳算法。如分層遺傳算法，跨世代異物種重組大變異(CHC)算法，自適應遺傳算法，Messy遺傳算法，并行遺傳算法，基于小生境技術的遺傳算法等，還出現遺傳算法與其他算法(如相對差商法、混沌算法、梯度算法等)相復合，形成混合遺傳算法［3，13]。這些改進的遺傳算法已在離散變量結構優化研究中得到大量應用，并取得了一定的成效［14－15]。相信在今后遺傳算法會得到更大的發展。

2.2 模擬退火法

模擬退火法是基于固體物質退火過程原理及蒙特卡羅迭代求解策略的一種隨即尋優算法，其思想來源于統計力學。在模擬固體退火過程中，由一組參數控制算法的進程，這組參數被命名為冷卻速度進度表，在此進程中算法通過Metropolis接受準則不斷選擇可行點。并且概率突跳法使得算法避免陷入局部最優解，所以得到全局最優解的機會增大。其中重要的參數有溫度衰減參數和尋優步長，兩者都作用于尋優的速度和精確度［16]。因為用不著任何梯度信息和 Hessian矩陣，所以該算法對解決離散變量優化設計問題較有效［17]。

為進一步提高經典模擬退火算法的性能，相關學者提出一些改進方法。都志輝等［18]提出一種混合SPMD模擬退火算法，使得算法的求解速度明顯加快;高齊圣等［19]提出一種改進的模擬退火算法;高占遠［20]將單純形法與模擬退火算法結合并提出改進措施，都具有較好的求解效率和全局優化能力。

2.3 人工神經網絡

人工神經網絡屬于一種較新的啟發式搜索方法，它主要是通過Hopfield［21]神經網絡對結構進行優化設計。非靜定三桿結構的優化和焊接結構的優化問題就是Dhingra通過Hopfield神經網絡來解決的;陸今桂［22]利用Hopfield神經網絡模型對離散變量結構優化問題進行研究。李興旺［23]等人通過深入研究人工神經網絡在工程結構優化設計中的應用，提出適用于工程結構優化的人工神經網絡模型，并用數值仿真證明該方法優于其他方法。此外還有人提出了混沌神經網絡模型，模糊神經網絡模型等，發展到今天已存在上百種神經網絡模型。

2.4 禁忌搜索法

禁忌搜索算法是針對在優化過程中局部搜索容易陷入局部最優解而無法得到全局最優解的問題而提出的。其主要思想是在搜索過程中標記搜索到的局部最優解對象，并在進一步的搜索過程中盡量避開它們，從而保證有不同的有效搜索路徑 ［5，24] 。

算法的搜索過程分為三步［25]:產生設計點的局部范圍，接受容許的設計，對Tabu表更新。Glover對該算法作了詳細介紹［26]，Bland作了補充并應用于桁架的優化設計［27]。禁忌搜索法常與其他方法結合使用，例如，遺傳算法、神經網絡等，目的是克服某種單純算法的弱點［28]。

2.5 蟻群算法

生物學家發現生物界中的螞蟻群在尋找食物的路徑上會釋放一種螞蟻特有的分泌物－信息素，一定范圍內的螞蟻能夠感受到這種物質，并且傾向于朝著濃度較高的路徑方向移動，螞蟻的這種行為被相關學者稱為是一種信息正反饋現象。由于此種生物現象的啟發，意大利學者 Marco Dorigo于1992年在他的博士論文中提出蟻群優化(Ant Colony Optimization，ACO)［29－30]，該算法最早成功地用于解決著名的旅行商問題［31]。

ACO算法的主要特點概括為［32]:采用分布式控制，不存在中心控制;個體的交互作用表現為群體的復雜行為;每個個體只能感知局部信息，無法直接獲得整體信息;個體可以改變環境并進行間接通訊;采用改進全局搜索方法求解全局最優解;求解時不需要問題具有嚴格數學性質;個體通過相互交換信息來提高適應環境的能力;具有潛在并行性，能同時搜索多個點。

經過十幾年的發展，螞蟻算法有諸多改進［33－42]，經過各種數值仿真結果的檢驗表明，該算法在組合優化方面具有諸多優越性，可以作為求解組合最優化問題的新型通用啟發式方法，但也有相關文獻資料表明該算法還存在有待改進的地方［43－48]。

總結以上，蟻群算法是近幾年逐漸發展起來的一種隨機優化方法，該算法優化的優點主要表現在:①可行解選擇機制;②信息素更新機制;③群體協作機制，這樣的操作過程使蟻群算法具有很強的發現較優解的能力。因此，該算法不僅可用于求解單目標優化問題，還可用于求解多目標優化問題。在組合優化中已展現出其獨特的優點，并且蟻群算法還具有易于操作、便于與其他方法相復合的特點，由此可見，蟻群算法是一很有發展前途的啟發式算法。

2.6 其他方法

目前，進行離散變量結構優化設計研究工作的人很多，如郭鵬飛等人提出了基于離散變量結構優化的斐波那契遺傳算法、擬滿應力設計法［1，49];董錦坤等人提出的單向搜索算法［50];李永梅等人把近似滿應力設計方法和相對差商法結合起來形成離散變量結構優化兩級算法［51]。另外還有基于生物免疫系統的免疫算法，它由免疫學理論和觀察到的免疫功能、原理和模型啟發而設計;2004年李泉永、龔雨兵把基于社會性動物(蟻群、蜂群、鳥群等)的自組織行為(覓食、遷徙、筑巢等)的群搜索算法應用于離散變量結構優化中［52]。2006年王希云、劉瑞芳研究了粒子群算法在離散變量結構優化中的應用［53]。2007年張梅鳳、邵誠、甘勇等探討了人工魚群優化算法在離散變量結構優化中的應用［54]。很多學者都在嘗試將這些智能算法運用到結構優化設計中來，但由于它們的應用探索還處于起步階段，還有許多方面沒考慮到。因此，這些新興算法的設計也有許多有待改進之處。

3 離散變量結構優化設計發展展望

從離散變量結構優化的發展方向，我們認為還有以下幾個方面:

(1)針對具體問題時:我們現在所考慮的模型可能和實際問題的模型有差異，怎樣把現有的研究成果應用到具體問題中，結合工程實際問題進行離散變量結構優化設計的研究，是優化研究人員應該關注的一個方向。

(2)多目標問題:在現實中，有的優化問題具有多個優化目標，由于這些目標之間相互矛盾、相互約束，難以同時得到最優結果，這就出現了多目標優化問題。因此，從尋求協調各項指標關系的方向進行多目標離散變量結構優化的研究，以求得更加符合實際的結構是非常有意義的研究課題。

(3)可靠性方面:結構的可靠性逐步成為判斷現代結構優化設計的重要因素，基于結構可靠性的離散變量結構優化設計的研究應該是未來的一個重要研究方向。

(4)發展高層次的結構優化設計方法:在形狀(幾何)、拓撲、布局優化方面應加大研究的力度。

(5)將研究理論較成熟的啟發式算法(如遺傳算法、人工神經網絡等)與計算機科學中運用的優化方法相復合，目的是尋求精確度高、收斂效果較快速平穩的啟發式算法，以應用到離散變量結構優化設計中。

(6)在發展結構優化設計軟件方面加大研究力度，以便于優化設計應用技術范圍的擴大。

4 結語

由于設計變量離散的特點，使得離散變量結構優化設計問題研究起來有一定的困難，而其在實際工程中又具有深遠的應用前景，因此，對離散變量結構優化設計的研究是一個內容廣泛、值得深入進行的方向，離散變量結構截面優化設計是研究離散變量結構優化設計問題的基礎。離散變量優化設計屬于NP困難問題，加之需要迭代運算，使得結構重分析次數巨大，所以優化算法的計算效率、收斂速度成為選用優化算法首先考慮的方面。由于到目前為止還沒有一種精確的數學算法能夠解決NP困難問題，因此，解決離散變量結構截面優化設計問題首先要尋找精度高、收斂速度快的啟發式算法，新興的蟻群算法在這方面逐步顯示其優勢。考慮到實際工程應用的需要，離散變量結構優化設計還應滿足結構設計規范要求的各種條件以及工程規范中的各種約束限制。雖然目前對離散變量結構優化設計的研究已經取得了不少的研究成果，但仍然需要進行更深入的研究。

［1] 郭鵬飛，韓英仕，魏英姿.離散變量結構優化設計的擬滿應力設計方法［J] .工程力學，2000，17(1):94－98.

［2] 郭鵬飛，韓英仕.離散變量結構優化設計的擬滿應力遺傳算法［J] .工程力學，2003，20(2):95－99.

［3] 張延年，劉斌，郭鵬飛.基于混合遺傳算法的建筑結構優化設計［J] .東北大學學報，2003，24(10):985－988.

［4] HAN Y S，GUO P F.A Hybrid genetic algorithm for structural optimization with discrete variables［C] //Proceedings of the First China－Japan－Korea Joint Symposium on Optimization of Structural and Mechanical System.Xi’an:Xidian University Press，1999，157 －164.

［5] 孫煥純，柴山，王躍方.離散變量結構優化設計發展、現狀及展望［J] .力學與實踐，1997，19(4):7－11.

［6] 周書敬，薄濤，史三元.混合算法在輕鋼結構優化中的應用［J] .河北工程大學學報:自然科學版，2011，28(2):71－74.

［7] PAPADIMITRIOU C H.組合最優化－算法和復雜性［M] .北京:清華大學出版社，1988.

［8] 孫煥純，柴 山，王躍方.離散變量結構優化設計［M] .大連:大連理工大學出版社，2002.

［9] 李京濤，何麗麗，高瑞貞，等.改進遺傳算法在桁架拓撲優化中的應用［J] .河北工程大學學報:自然科學版，2009，26(3):19－21.

［10] 王小平，曹立明.遺傳算法―理論、應用與軟件實現［M] .西安:西安交通大學出版社，2002.

［11] RYOO J，HAJELA P.Handling variable string lengths in GA －based structural topology optimization［J] .Structural and Multidisciplinary Optimization，2004，26(5):318－325.

［12] 張明輝，王尚錦.遺傳算法在結構形狀優化中的應用［J] .機械科學與技術，2001，20(6):824－826.

［13] 譚 虓，劉自山，李凌宇.基于模擬退火遺傳算法的IIR數字濾波器參數優化設計［J] .四川理工學院學報:自然科學版，2011，24(4):426－430.

［14] 劉立民，潘 偉，龐彥軍，等.多階段復合型遺傳算法的結構及性能研究［J] .河北工程大學學報:自然科學版，2010，27(2):107－112.

［15] 王紅霞，高瑞貞，張京軍.基于不動點理論的改進遺傳算法［J] .河北工程大學學報:自然科學版，2010，27(3):100－103.

［16] 康立山，謝 云，尤矢勇，等.非數值并行算法――模擬退火算法［M] .北京:科學出版社，1997.

［17] 鐘太勇，彭先萌.模擬退火算法在藥物動力學參數反演中的應用［J] .四川理工學院學報:自然科學版，2011，24(2):175－177.

［18] 都志輝，李三立，吳夢月，等.混合SPMD模擬退火算法及其應用［J] .計算機學報，2001，24(1):256－265.

［19] 高齊圣，張嗣癲，潘德惠，等.參數設計的模擬退火并行計算法［J] .系統工程理論與實踐，2002，5(8)，41－44.

［20] 高占遠.改進的單純形模擬退火算法［J] .南陽師范學院學報，2007，6(3):30－32.

［21] HOPFIELD J.Neural networks and physical systems with emergent collective computer abilities［J] .Proc Natl Acad Sci，1982，79(6):2554 －2558.

［22] 陸金桂.基于人工神經網絡及多級技術的結構優化與實踐［D] .武漢:華中理工大學，1997

［23] 李興旺，滿廣生.神經網絡方法在結構優化計算中的應用［J] .人民長江，2002，33(9):33－35.

［24] 劉清海，趙文清，丁予展.禁忌搜索離散化技術［J] .起重運輸機械，2001，12(5):11－13.

［25] 王凌.智能優化算法及其應用［M] .北京:清華大學出版社，2002.

［26] GLOVER F.Tabu search，part II［J] .ORSA J Comp，1990(2):4－32.

［27] BLAND J A.Discrete variable optimal structural design using Tabu search［J] .Structural Optimum，1995，10:87－93.

［28] 羅海林，霍達.離散變量桁架結構拓撲優化的遺傳禁忌搜索算法［J] .河南科學，2005，23(6):909－911

［29] BLUM C.Ant colony optimization:introduction and recent tends［J] .Physics of Life Reviews，2005，2(4):353－373.

［30] DORIGO M，VITTORIO M，ALBERTO C.The ant system:optimization by a colony of cooperating agents［J] .IEEE Transactions on Systems，1996，26(1):29－41.

［31] 勞眷.蟻群算法求解TSP問題若干改進策略的研究［J] .科學技術與工程，2009，9(9):2 459－2 462.

［32] COLORNI A，DORIGO M，MANIEZZO V，et al.Ant system for job － shop scheduling.Belgian［J] .Oper Res Statist Comput Sci，1994，34:39 －53.

［33] 楊潔，楊勝，曾慶光.基于信息素強度的蟻群算法［J] .計算機應用，2009，29(3):865－869.

［34] 段海濱，王道波，朱家強.蟻群算法理論及應用研究的進展［J] .控制與決策，2004，19(12):1 322－1 340.

［35] 楊中秋，張延華，鄭志麗.基于改進蟻群算法對最短路徑問題的分析與仿真［J] .沈陽化工學院學報，2009，23(2):150－153.

［36] 李士勇.蟻群算法及其應用［M] .哈爾濱:哈爾濱工業大學出版社，2004.

［37] 孫燾，王秀坤，劉業欣.一種簡單螞蟻算法及其收斂性分析［J] .小型微型計算機系統，2003，21(8):1524－1526.

［38] 吳慶洪，張紀會，徐心和.具有變異特征的蟻群算法［J] .計算機研究與發展，1999，36(10):1240－1245

［39] 丁建立，陳增強，袁著祉.基于自適應螞蟻算法的動態最優路由選擇［J] .控制與決策，2003，18(6):751－753.

［40] MARCO D，CHRISTIAN B.Ant colony optimization theory:A survey［J] .Theoretical Computer Science，2005，344:243 －278.

［41] GAMBARDEILA L M，DORIGO M，MIDDENDORF M.Guest editorial:special section on ant colony optimization［J] .IEEE Transactions on Evolutionary Computation，2002，6(4):317－319.

［42] 曾黃麟，黃 艷.基于信息最大覆蓋率蟻群算法的Rough集屬性優化約簡［J] .四川理工學院學報:自然科學版，2011，24(4):452－456.

［43] 胡祥培，丁秋雷，李永先.蟻群算法研究評述［J] .管理工程學報，2008，22(2):74－79.

［44] 楊劍鋒.蟻群算法及其應用研究［D] .浙江:浙江大學，2007.

［45] 陳吳.蟻群優化算法的原理及其應用［J] .湖北大學學報:自然科學版，2006，28(4):350－352.

［46] STUTZLE T，HOOS H.Max－min ant system［J] .Future Generation Computer Systems Journal，2000，16(8):889－914.

［47] HUANG K L，LIAO C J.Ant colony optimization combined with taboo search for the job shop scheduling problem［J] .Computers＆Operations Research，2008，35:1030－1046.

［48] DONATI A V，MONTEMANNI R，CASAGRANDE N，et a1.Time dependent vehicle routing problem with a multi ant colony system［J] .European Journal of Operational Research，2008，185:1174－1191.

［49] 郭鵬飛.離散變量結構優化的斐波那契遺傳算法［J] .遼寧工學院學報，2003，23(4):1－4.

［50] 張延年，劉劍平，劉 斌，等.改進單向搜索遺傳算法的工程結構優化設計［J] .力學季刊，2005，26(2):293－298.

［51] 李永梅，張毅剛.考慮結構整體穩定性的單層網殼優化設計［J] .建筑結構，2006，36(4):77－80.

［52] 李泉永，龔雨兵.離散變量結構優化中的一種有效仿生算法［J] .現代制造工程，2004(5):32－34.

［53] 王希云，劉瑞芳.混沌粒子群算法及其在桁架結構優化設計中的應用［J] .太原科技大學學報，2006，27(6):478－480，485.

［54] 張梅鳳，邵誠，甘勇，等.基于變異算子與模擬退火混合的人工魚群優化算法［J] .電子學報，2007，34(8):1381－1385.