趙艷敏，霍 達(dá)

(1.北京京北職業(yè)技術(shù)學(xué)院，北京101400;2.北京工業(yè)大學(xué)建筑工程學(xué)院，北京100022)

0 引言

對(duì)于基礎(chǔ)研究和應(yīng)用研究，優(yōu)化問(wèn)題是一個(gè)普遍的問(wèn)題，有著廣泛的應(yīng)用背景.在工程實(shí)際中，許多優(yōu)化問(wèn)題的目標(biāo)函數(shù)是非凸的，而且受到材料加工和模數(shù)尺寸的限制，存在大量的離散變量?jī)?yōu)化問(wèn)題，如型鋼尺寸、板厚等均為離散變量.傳統(tǒng)的優(yōu)化設(shè)計(jì)方法很難解決這些問(wèn)題，因此必須尋求有效的優(yōu)化算法.

遺傳算法從概率意義上以隨機(jī)的方式收斂到最優(yōu)解，是一種全局優(yōu)化算法，在很多的領(lǐng)域中得到了成功的應(yīng)用.但局部搜索能力較差，需要較長(zhǎng)時(shí)間才能收斂到全局最優(yōu)解.模擬退火算法是一種簡(jiǎn)單的啟發(fā)式算法，局部搜索能力很強(qiáng)，容易收斂到局部最優(yōu)解，但全局搜索能力較差.將遺傳算法同模擬退火算法相結(jié)合而成的遺傳模擬退火算法是一種全局和局部搜索能力都很強(qiáng)的算法，是一種最近興起的智能優(yōu)化算法，研究遺傳模擬退火算法在結(jié)構(gòu)離散變量［1］優(yōu)化設(shè)計(jì)中的應(yīng)用具有重要的理論和現(xiàn)實(shí)意義.

1 遺傳模擬退火算法的原理

1.1 遺傳算法

遺傳算法［2］(Genetic Algorithms)，簡(jiǎn)稱(chēng) GA，60年代初期由美國(guó)的J.Holland教授提出.其特點(diǎn)是：只對(duì)決策變量的編碼進(jìn)行運(yùn)算;運(yùn)用群體搜索策略提高搜索的效率和速度;確定搜索的方向和范圍只需要目標(biāo)函數(shù);概率搜索技術(shù)增加搜索過(guò)程的靈活性;優(yōu)化計(jì)算時(shí)不依賴(lài)于梯度信息.遺傳算法廣泛應(yīng)用于傳統(tǒng)搜索方法難以解決的高度復(fù)雜的非線性領(lǐng)域［3］，并在信息處理、組合優(yōu)化［4］、機(jī)器學(xué)習(xí)和人工生命方面展示了良好的優(yōu)越性.

1.2 模擬退火算法

1953年，Metropolis等人提出了模擬退火算法(Simulated Annealing)，簡(jiǎn)稱(chēng) SA［5］.SA 源于對(duì)固體退火過(guò)程的模擬，采用Metropolis接受準(zhǔn)則，并用一組稱(chēng)為冷卻進(jìn)度表的參數(shù)控制算法進(jìn)程，使算法在多項(xiàng)式時(shí)間里給出一個(gè)近似最優(yōu)解.1982年，Kirkpatric意識(shí)到固體退火過(guò)程與組合優(yōu)化問(wèn)題之間的類(lèi)似，將退火思想引入組合優(yōu)化領(lǐng)域.算法流程圖見(jiàn)圖1.

1.3 遺傳模擬退火算法

遺傳模擬退火算法(Genetic Simulated Annealing Algorithm)，簡(jiǎn)稱(chēng) SAGA［6］，是一種將模擬退火算法同遺傳算法相結(jié)合的現(xiàn)代優(yōu)化計(jì)算方法.遺傳模擬退火算法綜合了遺傳算法和退火算法各自的優(yōu)點(diǎn)，是一種全局和局部搜索能力都較強(qiáng)的智能優(yōu)化算法.遺傳模擬退火算法從一組隨機(jī)產(chǎn)生的初始解(初始群體)開(kāi)始搜索全局最優(yōu)解，先通過(guò)選擇、交叉、變異等遺傳操作來(lái)產(chǎn)生一組新個(gè)體，然后再獨(dú)立對(duì)新產(chǎn)生的各個(gè)個(gè)體進(jìn)行模擬退火過(guò)程，以其結(jié)果作為下一代中的個(gè)體，這個(gè)運(yùn)行過(guò)程反復(fù)迭代地進(jìn)行，直到滿足某個(gè)終止條件為止.算法流程圖見(jiàn)圖2.

2 離散變量的遺傳模擬退火算法

2.1 優(yōu)化模型

設(shè)計(jì)變量取桁架結(jié)構(gòu)各桿的截面面積xi［7］，其取值范圍為離散變量的有限離散域.優(yōu)化的目標(biāo)函數(shù)為：

式中：ρ為材料密度;l為各桿件的長(zhǎng)度.目標(biāo)函數(shù)是使得桁架結(jié)構(gòu)重量最輕，應(yīng)滿足的約束條件如下：

式中：σi為各桿件的應(yīng)力;μi為各桿件的位移.

2.2 編碼、解碼和初始群體

遺傳模擬退火算法以設(shè)計(jì)變量的編碼為操作對(duì)象，一般采用的是簡(jiǎn)單、直觀的二進(jìn)制編碼.當(dāng)有n個(gè)變量時(shí)，將n個(gè)位串連接成一串形成個(gè)體.每個(gè)變量的串長(zhǎng)l應(yīng)滿足2l≥m，其中m為設(shè)計(jì)變量可取元素的個(gè)數(shù)，則總串長(zhǎng)為nl.例如：每個(gè)變量可取16(即 m)個(gè)離散值［1.25 1.45 1.65 1.85 2.10 2.25 2.35 2.54 2.62 3.24 3.50 3.65 3.78 3.84 4.00 4.40］.因?yàn)?4≥16，所以 l取 4，如果有3 個(gè)變量則總串長(zhǎng)為12，解碼的時(shí)候把碼串分成3部分分別進(jìn)行解碼.具體映射關(guān)系如表1所示.

表1 一個(gè)變量的編碼串與離散值的對(duì)應(yīng)關(guān)系Tab.1 Corresponding relations of encoded string and discrete values

2.3 適應(yīng)度函數(shù)

筆者采用罰函數(shù)的方法將帶約束的非線性?xún)?yōu)化問(wèn)題轉(zhuǎn)換成無(wú)約束優(yōu)化問(wèn)題.由于標(biāo)準(zhǔn)遺傳算法是求最大值問(wèn)題，并要求每個(gè)個(gè)體的適應(yīng)度為正數(shù)或零，所以遺傳算法部分的適應(yīng)度函數(shù)按照下式進(jìn)行處理.

式中：φ(x)為經(jīng)過(guò)約束處理后的目標(biāo)函數(shù);Cmax為給出的一個(gè)較大的常數(shù);F(x)為適應(yīng)度函數(shù).對(duì)于模擬退火部分是求最小值問(wèn)題，所以這部分的適應(yīng)度函數(shù)F(x)=φ(x).

2.4 遺傳算子

(1)選擇算子(Selection)采用2選1的聯(lián)賽選擇方法，即每一次隨機(jī)的從種群中選擇兩個(gè)個(gè)體，其適應(yīng)度較高的個(gè)體保存到下一代.這一過(guò)程反復(fù)進(jìn)行，直到保存到下一代的個(gè)體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)目為止.(2)交叉(Crossover)是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)重組生成新的個(gè)體.筆者采用單點(diǎn)交叉的方法，具體操作為：隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)，然后將這兩個(gè)個(gè)體在該點(diǎn)后的部分互換，生成兩個(gè)新的個(gè)體.(3)變異(Mutation)是為了維持群體的多樣性，筆者采用均勻變異.設(shè)定一個(gè)隨機(jī)產(chǎn)生器，如果產(chǎn)生的概率小于變異概率，則把這個(gè)串位上的基因值取反.

2.5 算法的實(shí)現(xiàn)

(1)初始化運(yùn)行參數(shù)，將進(jìn)化代數(shù)k設(shè)定為0，t=t0;(2)隨機(jī)產(chǎn)生初始群體p(0);(3)群體選擇操作，p1(k)=selection［p(k)］;(4)單點(diǎn)交叉算子進(jìn)行交叉，p2(k)=crossover［p1(k)］，交叉概率取為0.90;(5)均勻變異，p3(k)=mutation［p2(k)］，變異概率取0.001;(6)對(duì)群體進(jìn)行模擬退火，退火的冷卻進(jìn)度表為：t0=1.0，lk=10 ，t=t0×0.95k，p4(k)=annealing［p3(k)］;即在群體 P3(k)中每個(gè)染色體i∈p3(k)的鄰域中隨機(jī)地選取某一新個(gè)體j∈N(i)，然后計(jì)算模擬退火中的接受概率 prij(tk)=min{1，exp［(f(i)-f(j))/tk］}.如果 prij(tk)≥random［0，1］，則接受新解，否則拋棄.其中random［0，1］為隨機(jī)產(chǎn)生的一個(gè)0～1之間的隨機(jī)數(shù)，f(i)為狀態(tài)i的目標(biāo)函數(shù).(7)對(duì)約束采用懲罰的方法處理，然后評(píng)價(jià)加上懲罰項(xiàng)后的群體適應(yīng)度，并且保留最優(yōu)個(gè)體;(8)是否滿足終止條件，如果滿足，輸出當(dāng)前最優(yōu)個(gè)體，如果不滿足，則 k=k+1，t=t0×0.95k，轉(zhuǎn)到第 3 步進(jìn)行下一步進(jìn)化過(guò)程.

3 工程實(shí)例

算法采用Matlab語(yǔ)言編寫(xiě)，平面桁架應(yīng)力求解采用文獻(xiàn)［8］有限元程序.數(shù)據(jù)采集采用算法程序連續(xù)運(yùn)行20次為一組，進(jìn)行了5組實(shí)驗(yàn)，記錄搜索到最優(yōu)解所需要的進(jìn)化代數(shù).如果迭代100代沒(méi)有找到最優(yōu)解，則計(jì)為100;然后分別求出改進(jìn)的遺傳算法和遺傳模擬退火算法搜到最優(yōu)解的平均進(jìn)化代數(shù)和搜到最優(yōu)解的次數(shù)，并同文獻(xiàn)［4］進(jìn)行比較，作為算法性能評(píng)價(jià)的依據(jù).

3.1 十桿桁架問(wèn)題的描述

將SAGA用于十桿桁架結(jié)構(gòu)，如圖3所示，基本參數(shù)為：彈性模量E=2.0×105MPa，材料密度ρ=7.8×103kg/m3，最大的允許應(yīng)力 σmax= ±100 MPa，在節(jié)點(diǎn)2和4作用著垂直荷載P=10 kN，求十桿桁架的最優(yōu)斷面面積，使該桁架系統(tǒng)總重量最小.A 的取值范圍為 A=［1.132 1.432 1.459 1.749 1.859 2.109 2.276 2.359 2.659 2.756 3.086 3.382 3.486 3.791 4.292 5.076］.(單位：cm2)水平和豎向桿的長(zhǎng)度為1.0 m，斜桿的長(zhǎng)度為.罰因子取 100，Cmax=300，群體規(guī)模n=100.

3.2 SAGA優(yōu)化結(jié)果與其他優(yōu)化結(jié)果的比較

SAGA優(yōu)化算法中隨著進(jìn)化代數(shù)的增加，十桿桁架重量的優(yōu)化過(guò)程見(jiàn)圖4，十桿桁架適應(yīng)度的變化見(jiàn)圖5，優(yōu)化結(jié)果與其他優(yōu)化結(jié)果的比較見(jiàn)表2，最優(yōu)解處各桿件的截面面積和應(yīng)力見(jiàn)表3.

表2 十桿桁架優(yōu)化結(jié)果比較Tab.2 Comparison between SAGA and other optimization results

3.3 試驗(yàn)結(jié)果分析

為了便于比較分析，筆者分別用改進(jìn)的遺傳算法和遺傳模擬退火算法對(duì)十桿桁架進(jìn)行優(yōu)化計(jì)算，在遺傳算法部分采用相同的選擇方法和變異、交叉概率.從表2中可以看出：遺傳模擬退火算法的尋優(yōu)概率是100%，其穩(wěn)定性?xún)?yōu)于改進(jìn)的遺傳算法.平均進(jìn)化代數(shù)為35代，遠(yuǎn)遠(yuǎn)優(yōu)于文獻(xiàn)［4］，求解效率高于改進(jìn)的遺傳算法.圖4和圖5的優(yōu)化過(guò)程中可以看出遺傳模擬退火算法比改進(jìn)的遺傳算法較快的搜索到了最優(yōu)解，且尋優(yōu)結(jié)果優(yōu)于文獻(xiàn)［9］.

表3 最優(yōu)解處各桿件的截面面積和應(yīng)力Tab.3 Cross-section areas and stresses of every pole in optimal value

4 結(jié)論

(1)遺傳模擬退火算法具有良好的可操作性、穩(wěn)健型、魯棒性，能有效地解決桁架結(jié)構(gòu)離散變量的優(yōu)化問(wèn)題;

(2)遺傳模擬退火算法采用退火操作進(jìn)行局部搜索，使其局部搜索能力優(yōu)于改進(jìn)的遺傳算法，可以更快的收斂到全局最優(yōu)解，在很大程度上克服了遺傳算法迭代過(guò)程緩慢的缺點(diǎn)，提高了算法的搜索效率;

(3)遺傳模擬退火算法的尋優(yōu)穩(wěn)定性高于改進(jìn)的遺傳算法，是一種更可靠、有效地智能優(yōu)化算法;

(4)遺傳模擬退火算法具有遺傳算法和退火算法各自的優(yōu)點(diǎn)，是一種全局和局部搜索能力都較強(qiáng)的智能優(yōu)化算法，將其用于優(yōu)化設(shè)計(jì)領(lǐng)域是行之有效的.

［1］顧元憲，項(xiàng)寶衛(wèi)，趙國(guó)忠.桁架結(jié)構(gòu)截面優(yōu)化設(shè)計(jì)的改進(jìn)模擬退火算法［J］.計(jì)算力學(xué)學(xué)報(bào)，2006，23(5)：546-552.

［2］陳國(guó)良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用［M］.北京：人民郵電出版社，1996：80-81.

［3］孟凡旦，鹿曉陽(yáng).基于遺傳算法鋼框架抗震優(yōu)化設(shè)計(jì)［J］.山西建筑，2006，32(17)：7-8.

［4］郝進(jìn)鋒，劉艷暉，張文福，等.遺傳算法在網(wǎng)架結(jié)構(gòu)優(yōu)化中的應(yīng)用［J］.力學(xué)與實(shí)踐，2006，28(6)：42-45.

［5］康立山，謝云，尤矢勇，等.非數(shù)值并行算法-模擬退火算法［M］.北京：科學(xué)出版社，1994：12-38.

［6］劉敬宇，朱朝艷.遺傳模擬退火算法在結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用［J］.吉林建筑工程學(xué)院學(xué)報(bào)，2010，27(2)：5-8.

［7］黃冀卓，王湛，龔明袖.遺傳算法在鋼結(jié)構(gòu)截面優(yōu)化設(shè)計(jì)中的應(yīng)用［J］.四川建筑科學(xué)研究，2005，31(3)：26-31.

［8］匡文起.結(jié)構(gòu)矩陣分析和程序設(shè)計(jì)［M］.北京：高等教育出版社，1993：46-63.

［9］張思才，張方曉.遺傳算法在離散變量結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用［J］.西南交通大學(xué)學(xué)報(bào)，2003，38(2)：146-150.