改進(jìn)的多目標(biāo)遺傳算法在結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用

1、改進(jìn)的多目標(biāo)遺傳算法在結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用關(guān)志華 作者簡(jiǎn)介：關(guān)志華（1971-），男，天津大學(xué)管理學(xué)院99秋季博士，主要研究方向?yàn)槎嗄繕?biāo)進(jìn)化算法及其應(yīng)用。 （天津大學(xué)管理學(xué)院9013信箱 天津 300072）萬(wàn)杰（河北工業(yè)大學(xué)管理學(xué)院 天津 300000）摘要 本文探討了多目標(biāo)遺傳算法（MOGA）存在的問(wèn)題，并提出了相應(yīng)的改進(jìn)策略。這些策略包括：小生境技術(shù)、適應(yīng)度共享策略、交叉限制、改進(jìn)的終止準(zhǔn)則等。通過(guò)采用這些策略對(duì)MOGA進(jìn)行改進(jìn)，使之可以克服在終止準(zhǔn)則和小生境形成上的缺陷，從而使算法既可以對(duì)問(wèn)題空間進(jìn)行更廣泛的搜索又可以可靠的、迅速的收斂于優(yōu)化解，為最終決策提供了幫助。最后，給出了改進(jìn)的

2、MOGA在結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的兩個(gè)應(yīng)用實(shí)例。關(guān)鍵詞 多目標(biāo)優(yōu)化問(wèn)題，結(jié)構(gòu)優(yōu)化設(shè)計(jì)，遺傳算法1 引言 帶有m個(gè)目標(biāo)函數(shù)的多目標(biāo)優(yōu)化問(wèn)題(MOOP)的數(shù)學(xué)表達(dá)式如下：由于在MOOP中，多個(gè)設(shè)計(jì)變量有時(shí)是相互矛盾的。所以，這里的最小化（Minimize）問(wèn)題，從實(shí)際意義上來(lái)說(shuō)，其實(shí)是指當(dāng)綜合考慮所有的目標(biāo)函數(shù)時(shí)的優(yōu)化解（Pareto 解）。盡管也許全部的目標(biāo)函數(shù)都不能優(yōu)化到它們各自作為單目標(biāo)函數(shù)時(shí)的最優(yōu)解，但是，在多目標(biāo)情況下，對(duì)其中任意一個(gè)單個(gè)的目標(biāo)函數(shù)的優(yōu)化都不能以降低其它函數(shù)的優(yōu)化解為代價(jià)。這就是多目標(biāo)優(yōu)化不同于單目標(biāo)函數(shù)優(yōu)化的地方，也正是它的難點(diǎn)。這里，為了區(qū)別進(jìn)化過(guò)程中的Pareto 解集和M

3、OOP最終得到的Pareto解集，我們把進(jìn)化過(guò)程中的Pareto 解集稱為近優(yōu)解集（non-inferior），而在其它文獻(xiàn)中這兩個(gè)名詞通常表示同一概念。適用于多目標(biāo)優(yōu)化問(wèn)題的遺傳算法（MOGAs）是在經(jīng)典遺傳算法（GAs）的基礎(chǔ)上修改得到的。多目標(biāo)優(yōu)化問(wèn)題的遺傳算法在適應(yīng)度分配策略上不同于經(jīng)典遺傳算法。本文探討了現(xiàn)有的MOGAs的主要缺點(diǎn)，并在此基礎(chǔ)上提出了一些改進(jìn)策略。在使用MOGA進(jìn)行多目標(biāo)問(wèn)題優(yōu)化時(shí)，為了得到最終的解集，MOGA必須對(duì)盡可能多的近優(yōu)解集進(jìn)行分析，而這些解是均勻的分布在解空間中的，這就會(huì)使MOGA的效率降低。但是，只有求得大量的解才可能得到一個(gè)連續(xù)的、平滑的Pareto曲

4、面，從而使MOGA可以盡快地收斂于優(yōu)化解。當(dāng)然，收斂速度同時(shí)也依賴于終止準(zhǔn)則的選取。在單目標(biāo)優(yōu)化問(wèn)題中，終止準(zhǔn)則可以定為：“在N代進(jìn)化中適應(yīng)度值沒(méi)有改進(jìn)”或直接定為“進(jìn)化N代”，而在MOGA中卻不能如此簡(jiǎn)單的定義，因此，需要有一種策略來(lái)檢測(cè)MOGA是否已經(jīng)得到了Pareto解集。 目前, MOGA存在如下主要問(wèn)題:(1) 如何指導(dǎo)種群跳出相鄰的小生境（niche）從而盡可能的搜索更多的Pareto集。要做到這一點(diǎn)，必須同時(shí)滿足兩個(gè)相互矛盾的條件，1）算法必須能夠識(shí)別近優(yōu)解集中的群體或個(gè)體簇是來(lái)源于哪個(gè)小生境。因?yàn)樵谶M(jìn)化初期會(huì)產(chǎn)生許多小生境，隨著進(jìn)化過(guò)程的進(jìn)行，這些小生境將會(huì)擴(kuò)張超出其邊界，這有

5、可能會(huì)導(dǎo)致MOGA難以收斂或?qū)е逻M(jìn)化過(guò)程更接近隨機(jī)搜索過(guò)程，從而效率低下。通過(guò)在父代選擇階段采取一些改進(jìn)策略可以避免這個(gè)問(wèn)題。2）算法必須能阻止這些小生境中的群體過(guò)分地集中一些適應(yīng)值較高的個(gè)體附近，而使得小生境過(guò)分收縮。從而可能會(huì)導(dǎo)致過(guò)早地收斂與近優(yōu)解集。要避免這個(gè)問(wèn)題，可以禁止同一個(gè)小生境中的父代交叉。這兩個(gè)條件一個(gè)要盡量抑制小生境的擴(kuò)張，另一個(gè)又要為保持小生境群體的多樣性而使它在一定范圍內(nèi)擴(kuò)張。也就是在一定范圍內(nèi)的多樣化。(2) 怎樣加入一些特定的終止準(zhǔn)則，這些特定的終止準(zhǔn)則可以有效的檢測(cè)出進(jìn)化過(guò)程中是否產(chǎn)生了Pareto集，并且檢測(cè)出這些Pareto集是否是均勻分布的。均勻分布的Pare

6、to集中的解不應(yīng)該在某些區(qū)域中解過(guò)于集中；而在另一些區(qū)域中過(guò)于分散。這些Pareto解過(guò)于集中和過(guò)于分散的區(qū)域往往是小生境正在形成的區(qū)域，如果這時(shí)終止算法的話，就可能使算法過(guò)早地收斂于局部?jī)?yōu)化解而得不到全局的優(yōu)化解。(3) 如何使設(shè)計(jì)者有一個(gè)相對(duì)自由地選擇來(lái)對(duì)它感興趣的特定區(qū)域進(jìn)行放大，以便進(jìn)一步對(duì)特定區(qū)域進(jìn)行優(yōu)化。這樣做的好處是：設(shè)計(jì)者可以在某個(gè)特定的階段選擇特定的區(qū)域，從而可以人為地控制這個(gè)階段的種群大小，以較小的種群獲得較好的結(jié)果和較快的收斂效果，使算法運(yùn)行效率較高。它的不足之處在于較小的種群規(guī)?？赡軣o(wú)法覆蓋整個(gè)可行域。2 改進(jìn)的MOGAs2.1改進(jìn)的終止準(zhǔn)則改進(jìn)的終止準(zhǔn)則可按如下步驟進(jìn)

7、行：a) 從當(dāng)前近優(yōu)解集中指定一個(gè)佳點(diǎn)（或由設(shè)計(jì)者直接指定），計(jì)算每個(gè)個(gè)體與這個(gè)佳點(diǎn)的距離，形成一個(gè)距離矩陣；b) 計(jì)算這個(gè)距離矩陣的均值和標(biāo)準(zhǔn)偏差；c) 隨著進(jìn)化代數(shù)的增加，近優(yōu)解集中的點(diǎn)逐漸聚攏，因此，距離矩陣中的元素值逐漸減小，這個(gè)過(guò)程可以由其均值反映出來(lái)；而個(gè)體的分布程度可以由標(biāo)準(zhǔn)偏差的增大反映出來(lái)。d) 如果均值的減小到小于某一個(gè)給定值，則可以認(rèn)為算法收斂并終止算法。否則，轉(zhuǎn)向步驟a)。2.2基于擁擠（crowding）機(jī)制的小生境技術(shù)在每一個(gè)進(jìn)化代中，當(dāng)獲得近優(yōu)解集時(shí)，可以采取過(guò)濾機(jī)制人為地從小生境中刪除一些個(gè)體，刪除的個(gè)體數(shù)目取決于小生境的擁擠程度（小生境密度），被刪除的個(gè)體由隨

8、機(jī)產(chǎn)生的個(gè)體補(bǔ)充。這樣可以使設(shè)計(jì)者更清晰的理解問(wèn)題本身并且確定問(wèn)題的關(guān)鍵區(qū)域。具體做法為采用基于擁擠（crowding）機(jī)制的小生境技術(shù)。主要采用了群體間的代間覆蓋方法，其實(shí)現(xiàn)方法為：a) 初始化（建立初始種群，確定遺傳算子。設(shè)定擁擠因子CF）；b) 計(jì)算個(gè)體適應(yīng)度；c) 遺傳操作；d) 從當(dāng)前群體中隨機(jī)選出群體規(guī)模的1/CF個(gè)個(gè)體組成擁擠因子成員；e) 比較新產(chǎn)生的個(gè)體與擁擠因子成員之間的相似性；f) 用新產(chǎn)生的個(gè)體替換擁擠因子成員中最相似的個(gè)體，形成新的當(dāng)前群體；g) 如未滿足終止準(zhǔn)則，轉(zhuǎn)b），否則終止算法。上述方法在進(jìn)化的初始階段，由于群體間個(gè)體的相似性相差不大，個(gè)體的更新呈隨機(jī)性。隨著

9、進(jìn)化的過(guò)程，群體中的個(gè)體逐漸被分成若干個(gè)小生境，這時(shí)，基于個(gè)體相似性的擁擠因子法可以在一定程度上維持群體的分布特性，并為進(jìn)一步的分類和新的小生境的形成留出了空間。2.3過(guò)濾和交叉限制機(jī)制在選擇父代進(jìn)行交叉以前，先計(jì)算兩個(gè)父本之間的目標(biāo)函數(shù)空間內(nèi)的距離，如果距離小于給定的值，則這兩個(gè)父本不進(jìn)行交叉；否則，允許交叉。這種對(duì)父本的過(guò)濾和限制交叉的機(jī)制依賴于小生境的密度和其中的種群分布情況。這樣可以限制“近親”交叉，保持種群的均勻分布和多樣性。2.4目標(biāo)函數(shù)約束的改進(jìn)策略當(dāng)?shù)贸稣麄€(gè)空間中的近優(yōu)解以后設(shè)計(jì)者可以通過(guò)給近優(yōu)解加上約束條件來(lái)放大特定的區(qū)域。步驟如下：a) 暫停進(jìn)化過(guò)程；b) 加入必要的約束條

10、件；c) 重新開(kāi)始進(jìn)化。這個(gè)策略可以在每代進(jìn)化結(jié)束時(shí)進(jìn)行，也可以由設(shè)計(jì)者自己選擇時(shí)間進(jìn)行。這樣，可以避免那些不滿足約束條件的個(gè)體的進(jìn)一步復(fù)制。而靈活地選擇加入約束的時(shí)間，可以加強(qiáng)設(shè)計(jì)者對(duì)進(jìn)化過(guò)程的控制。2.5懲罰機(jī)制的改進(jìn)由于我們只對(duì)近優(yōu)解中的個(gè)體進(jìn)行約束檢查，當(dāng)個(gè)體違反約束條件時(shí)，如果只是簡(jiǎn)單將它刪除，就有可能丟失包含好的基因片段的個(gè)體，所以應(yīng)該采取基于修改其適應(yīng)度值的方法來(lái)處理。根據(jù)Pareto排序方法相應(yīng)地減小它的適應(yīng)度值。有如下三種方法可以選擇：a) 線性排序： 參數(shù)定義為b) 指數(shù)排序：c) 另一種指數(shù)排序：式中，為種群排在第位的個(gè)體的選擇概率；為排序位置；為最好個(gè)體的選擇概率；為最

11、差個(gè)體的選擇概率；為群體大小。對(duì)于違反約束的個(gè)體可以制定它的=即可以降低它的選擇概率。2.6基于預(yù)選擇(perselection)機(jī)制的小生境策略其主要內(nèi)容為：只有在子個(gè)體的適應(yīng)度值超過(guò)其父?jìng)€(gè)體時(shí)，子個(gè)體才能代替父?jìng)€(gè)體，進(jìn)入下一代群體。由于這種方法趨向于替換與其本身相似的個(gè)體（父?jìng)€(gè)體與子個(gè)體之間的性狀遺傳），因而能夠較好地維持群體的分布性。2.7基于適應(yīng)度共享（sharing）的小生境技術(shù)用共享度函數(shù)來(lái)確定群體中個(gè)體的共享度。一個(gè)個(gè)體的共享度等于該個(gè)體與群體內(nèi)的各個(gè)其他個(gè)體之間的共享函數(shù)值的總和。共享函數(shù)是關(guān)于個(gè)體之間的密切程度的函數(shù)。當(dāng)個(gè)體之間關(guān)系較密切時(shí)，共享函數(shù)值較大；反之，則較小。設(shè)表

12、示個(gè)體和個(gè)體之間的關(guān)系密切程度，表示共享函數(shù)，表示個(gè)體在群體中的共享度，表示種群大小，則：計(jì)算出各個(gè)體的共享度后，個(gè)體的適應(yīng)度被重新指定為。這種基于適應(yīng)度共享的小生境技術(shù)可以限制那些適應(yīng)度值太大的“超級(jí)個(gè)體”的無(wú)限制增長(zhǎng)。3結(jié)構(gòu)優(yōu)化實(shí)例例1 兩桿構(gòu)架優(yōu)化問(wèn)題兩個(gè)目標(biāo)函數(shù)的兩桿構(gòu)架優(yōu)化問(wèn)題的數(shù)學(xué)描述如下：最小化兩個(gè)目標(biāo)函數(shù)和，分別為對(duì)構(gòu)架的體積和應(yīng)力的優(yōu)化。如下圖（圖一）所示，經(jīng)過(guò)240代的進(jìn)化改進(jìn)的MOGA得到了近優(yōu)解集。得到Paerto解集所進(jìn)行的函數(shù)計(jì)算量為9523次，大大少于未改進(jìn)的MOGA獲得相同解集的計(jì)算量（27397次）。圖一 改進(jìn)的MOGA在兩桿構(gòu)架問(wèn)題中的應(yīng)用例2 振動(dòng)試驗(yàn)臺(tái)優(yōu)

13、化問(wèn)題振動(dòng)試驗(yàn)臺(tái)優(yōu)化問(wèn)題是要設(shè)計(jì)一個(gè)帶有固定電機(jī)的平臺(tái)，它可以簡(jiǎn)化為兩桿支撐的有負(fù)載的橫梁的問(wèn)題，這里的負(fù)載是指電機(jī)本身。振動(dòng)由電機(jī)產(chǎn)生再傳遞到橫梁上。橫梁長(zhǎng)為寬為，是由三層材料組成的復(fù)合結(jié)構(gòu)，材料厚度分別由、表示，材料的類型由表示，其中，表示材料密度，表示材料的楊氏彈性模量，表示單位體積材料的價(jià)格。組成試驗(yàn)平臺(tái)的材料屬性如下表所示：材料類型材料密度楊氏彈性模量材料單位價(jià)格1277070109150021001.610950037780200109800表一 振動(dòng)試驗(yàn)臺(tái)材料屬性表問(wèn)題的有兩個(gè)目標(biāo)函數(shù)，表示基礎(chǔ)頻率，表示試驗(yàn)臺(tái)造價(jià)。振動(dòng)試驗(yàn)臺(tái)優(yōu)化問(wèn)題的具體數(shù)學(xué)描述如下：目標(biāo)是要設(shè)計(jì)夾層結(jié)構(gòu)的梁的

14、參數(shù)的值，使得振動(dòng)試驗(yàn)臺(tái)的造價(jià)最小，同時(shí)，最小化由于電機(jī)的擾動(dòng)而產(chǎn)生的梁的振動(dòng)（即：最大化梁的基礎(chǔ)頻率）。改進(jìn)的遺傳算法MOGA在120代進(jìn)化后得到了近優(yōu)解集，而未改進(jìn)的MOGA則需要進(jìn)化150代以上。由于采用了適應(yīng)度共享機(jī)制和交叉限制等策略，計(jì)算量大為減少，而最終的Pareto解集也優(yōu)于未改進(jìn)的算法的結(jié)果。結(jié)果如下圖所示：圖二 改進(jìn)的MOGA應(yīng)用于振動(dòng)試驗(yàn)臺(tái)的計(jì)算結(jié)果4 結(jié)論本文共探討了7個(gè)MOGA的改進(jìn)策略，包括：改進(jìn)的終止準(zhǔn)則、基于擁擠（crowding）機(jī)制的小生境技術(shù)、過(guò)濾和交叉限制機(jī)制、目標(biāo)函數(shù)約束的改進(jìn)策略、懲罰機(jī)制的改進(jìn)、基于預(yù)選擇(perselection)機(jī)制的小生境策略、

15、基于適應(yīng)度共享（sharing）的小生境技術(shù)。這些技術(shù)的采用可以保證MOGA可以可靠的、迅速的收斂于Pareto解集，并且可以對(duì)目標(biāo)函數(shù)空間進(jìn)行更為廣泛的搜索，對(duì)多目標(biāo)函數(shù)進(jìn)行更多的采樣，從而可以得出更接近全局最優(yōu)解的近優(yōu)解集，這個(gè)近優(yōu)解集中也會(huì)包含更多的優(yōu)化可行點(diǎn)，給決策提供了可靠的依據(jù)。從實(shí)例中可以看出，由于振動(dòng)試驗(yàn)臺(tái)問(wèn)題是一個(gè)離散化的問(wèn)題， Pareto點(diǎn)和小生境難以形成，所以延遲了全局優(yōu)化的速度。對(duì)于兩桿構(gòu)架問(wèn)題，Pareto解集基本上是一條連續(xù)的曲線，因此，采用改進(jìn)的MOGA就可以選擇相鄰的兩個(gè)Pareto點(diǎn)作為父本，在他們的鄰域內(nèi)產(chǎn)生新的Pareto點(diǎn)。這樣可以保證父代的優(yōu)異特性大

16、部分能傳到子代中，從而使整個(gè)算法最終收斂于Pareto解集。終止準(zhǔn)則的采用可以從很大程度上減少函數(shù)值的計(jì)算量，它的最重要的作用是評(píng)價(jià)Pareto集。盡管采用了許多改進(jìn)機(jī)制，對(duì)于不同的問(wèn)題仍然沒(méi)有一個(gè)通用的、魯棒性強(qiáng)的算法來(lái)求解多目標(biāo)優(yōu)化問(wèn)題，本文的算法也依賴于問(wèn)題本身的特性。我們只是在這一復(fù)雜問(wèn)題領(lǐng)域做了一些有意義的嘗試而已，對(duì)于多目標(biāo)進(jìn)化算法的研究還有待于進(jìn)一步的深化。參考文獻(xiàn)1 陳國(guó)良 等.遺傳算法及其應(yīng)用. 人民郵電出版社2 劉勇 等.非數(shù)值并行算法-遺傳算法. 科學(xué)出版社3 日玄光南.遺傳算法與工程設(shè)計(jì). 科學(xué)出版社4 Kirsch,U. Optimal structural desi

17、gn.NewYork:McGraw-hill,19815 Eschenaure,H,Koski,J and Osycka,A. Multi-criteria Design Optimization. New York Springer-Verlag, 19906 David A.Van Veldhuizen and Gray B. Lamont. Multi-objective Evolutionary Algorithm Research: A History and Analysis. October 14,19987 Colors M. Fonseca and Peter J. Flem

18、ing. A Overview of Evolutionary Algorithms in Multi-objective Optimization. May 19,19958 Eckart Zitzler. Evolutionary Algorithm for Multi-objective Optimization,Methods and Applications. November 11,19999 Shigeru Obayashi,Daisuke Sasaki,Yukihiro Takeguchi,and Naoki Hirose. Multi-objective Evolutiona

19、ry Computation for Supersonic Wing-shape Optimization10 David Todd and Pratyush Sen. Distributed Task Scheduling And Allocation Using Genetic Algorithms. October, 199811 D.J.Doorly,J.Peirt. Supervised parallel genetic algorithms in Aerodynamic optimization, in 13th AIAA CFD Conference,AIAA paper9718

20、52, American Institute of Aeronautics and Astronautics (AIAA). Snowmass Co., U.S.A., June 1997. 12 D. Quagliarella, A. Vicini. Coupling Genetic Algorithms and Gradient Based Optimization Techniques, in Quagliarella D. et al., editors, Genetic Algorithms and Evolution Strategies in Engineering and Computer Science. John Wiley & Sons Ltd., England, Nov. 1997, pp. 289-309. 13 A. Vicini, D. Quagliarella. Inverse and Direct Airfoil Design Using a Multiobjective Genetic Algorithm. AIAA Journal, Vol. 35, No. 9, Sep. 1997, pp. 1499-1505. AN IMPROVING MULTIOBJECTIVE GEN