基于網(wǎng)格支配的微型多目標遺傳算法

符純明　姜　潮　劉桂萍　鄧善良

湖南大學汽車車身先進設(shè)計制造國家重點實驗室，長沙，410082

基于網(wǎng)格支配的微型多目標遺傳算法

符純明姜潮劉桂萍鄧善良

湖南大學汽車車身先進設(shè)計制造國家重點實驗室，長沙，410082

提出了一種基于網(wǎng)格支配的微型多目標遺傳算法，該算法在求解較多目標函數(shù)的優(yōu)化問題時具有較好的收斂性和較高的計算效率。該算法引入網(wǎng)格支配概念并結(jié)合微型多目標遺傳算法，在每一代進化種群中計算各個個體的網(wǎng)格值、網(wǎng)格擁擠距離和網(wǎng)格坐標點距離，根據(jù)網(wǎng)格支配分級和網(wǎng)格選擇機制策略選取精英個體，并對其進行交叉和變異操作，使其朝前沿面收斂以獲得Pareto最優(yōu)解。4個測試函數(shù)和2個工程實例驗證了該算法的有效性。

多目標遺傳算法；網(wǎng)格支配；微型種群; Pareto最優(yōu)解；耐撞性

0　引言

在實際工程設(shè)計中，經(jīng)常遇到多目標優(yōu)化問題(multi-objective optimization problem，MOP)，如汽車正面碰撞的結(jié)構(gòu)優(yōu)化設(shè)計中，輕量化與最大吸能為兩目標優(yōu)化問題，兩者難以同時達到最優(yōu)，只能獲得一組無法進行簡單比較的Pareto解。多目標遺傳算法可在無需考慮目標函數(shù)和約束函數(shù)滿足連續(xù)性和可導(dǎo)性的條件下，對線性或者非線性目標函數(shù)進行有效求解，因而引起了眾多學者的關(guān)注，并被廣泛應(yīng)用于求解實際工程問題[1-3]。Schaffer[4]1985年提出了向量評估遺傳算法(vector evaluated genetic algorithm，VEGA)，用于解決機器學習的多目標問題。隨后，一系列的多目標遺傳算法被提出和發(fā)展，其中以Deb等[5]的NSGA-Ⅱ(non-dominated sorting GA-Ⅱ)算法和Zitzler等[6]的SPEA2(strength Pareto EA2)算法應(yīng)用最為廣泛。在汽車碰撞安全性設(shè)計中，謝然等[7]將NSGA-Ⅱ算法用于40%的偏置正面碰撞中，在滿足6σ可靠性、扭轉(zhuǎn)剛度和質(zhì)量要求的約束條件下，提高了整車的碰撞安全性能。為提高計算效率，劉桂萍等[8-10]將微型遺傳算法(micro genetic algorithm，μGA)[11]引入多目標優(yōu)化問題中，提出了微型多目標遺傳算法(micro multi-objective GA，μMOGA)，該算法在計算效率、解的均勻性和工程實用性等方面具有較好的綜合性能。Yang等[12]提出了基于網(wǎng)格支配的進化算法(grid-based evolutionary algorithm，GrEA)，利用網(wǎng)格能同時反映收斂性和多樣性的特點，使得個體朝著Pareto最優(yōu)解方向迭代。

本文在微型多目標遺傳算法μMOGA的基礎(chǔ)上結(jié)合網(wǎng)格支配的概念，提出了一種具有網(wǎng)格屬性的多目標遺傳算法Gr-μMOGA(μMOGA based on grid domination)，與現(xiàn)有方法相比，該算法在求解較多目標函數(shù)問題時具有較好的收斂性和均勻性，并提高了計算效率。

1　多目標優(yōu)化相關(guān)概念

多目標優(yōu)化廣泛存在于實際工程中，其優(yōu)化目標函數(shù)之間可能不一致甚至相互沖突，因此難以獲得一個類似于單目標的最優(yōu)解，而只能獲得一組無法進行簡單比較的Pareto最優(yōu)解。一般的MOP被定義為[13]

(1)

式中，fk(x)、gi(x)和hj(x)分別為目標函數(shù)、不等式約束函數(shù)和等式約束函數(shù)；m、p和q分別為目標函數(shù)、不等式約束和等式約束函數(shù)的個數(shù)；x、xL和xU分別為優(yōu)化變量、優(yōu)化變量的下界和上界。

?i∈(1,2,…,m):fi(x)≤fi(y)且

?j∈(1,2,…,m):fj(x)

2　Gr-μMOGA算法及構(gòu)造

現(xiàn)有的多目標優(yōu)化方法大都是針對二維目標函數(shù)問題，而對于較多目標函數(shù)問題通常難以獲得較好的Pareto解。為此，本文構(gòu)建一種新的基于網(wǎng)格支配的微型多目標遺傳算法Gr-μMOGA，用于求解較多目標函數(shù)的一類實際工程多目標設(shè)計問題。網(wǎng)格支配在文獻[12,14]被提出，通過該方法可保證較多目標函數(shù)下Pareto解集的計算精度；μMOGA算法由劉桂萍等[9]提出，通過小種群和重啟動策略可有效保證多目標優(yōu)化的計算效率。本文提出的Gr-μMOGA算法在求解較多目標函數(shù)問題時，將兼具精度和效率的雙重優(yōu)點。

2.1網(wǎng)格的概念及相關(guān)參數(shù)定義

第k個目標函數(shù)的網(wǎng)格間距dk為

則個體x在第k個目標函數(shù)空間的網(wǎng)格值Gk(x)為

(2)

其中，floor(·)表示最小取整函數(shù)，fk(x)為個體x在第k個目標函數(shù)的真實函數(shù)值。由式(2)知，圖1中5個個體在第k個目標函數(shù)下的網(wǎng)格值Gk(x)從左到右分別為0、1、3、3和4。

圖1　第k個目標函數(shù)賦予的網(wǎng)格屬性

個體x在m個目標函數(shù)下的網(wǎng)格值之和為

(3)

?i∈(1,2,…,m):Gi(x)≤Gi(y)且

?j∈(1,2,…,m):Gj(x)

個體x和y在m個目標函數(shù)下的網(wǎng)格值之差定義為網(wǎng)格差值，記為GD：

(4)

當個體y滿足N(x)={y|GD(x,y)

(5)

Gr值和dGC值能較好地度量解的收斂性和多樣性，但當兩者值相等時則無法區(qū)分個體，故引入網(wǎng)格坐標點距離，記為dGCP：

(6)

式中，dGCP為個體x在超方體中與理想點(超方體中所有目標函數(shù)值最小的點)的正則化歐拉距離。

通過Gr、dGC和dGCP值的比較與選擇獲得精英個體。以兩目標函數(shù)為例，6個個體在網(wǎng)格中的Gr值和dGC值分別如圖2所示。如個體C在網(wǎng)格中的Gr值和dGC值計算式為：Gr(C)=3+3=6，dGC(C)=(2-1)+(2-1)=2。

圖2　個體在網(wǎng)格中的Gr值和dGC值

2.2算法流程

以NSGA-Ⅱ算法和SPEA2算法為代表的多目標進化算法通常采用大種群計算，計算量大，效率較低。Gr-μMOGA算法采用小種群[9](5～8個個體)結(jié)合重啟動策略，并基于網(wǎng)格支配進行迭代進化，能提高效率并滿足解的收斂性要求，其計算流程如圖3所示。

圖3　Gr-μMOGA計算流程

(1)在可行域空間產(chǎn)生5～8個個體形成初始種群P1。設(shè)外部種群Pe大小為N，外部種群出現(xiàn)相同的連續(xù)代數(shù)的次數(shù)記為if lag。

(2)網(wǎng)格支配分級。將外部種群Pe和進化種群Pt合并成Rt，將Rt進行網(wǎng)格支配分級(R1,…,Rm)。若Pe=R1，則if lag+1。

(3)當if lag大于設(shè)定值M(一般取值為2～9)時，則采用重啟動策略。重新在可行域空間中產(chǎn)生進化種群Pt，并加入Rt中進行網(wǎng)格支配分級，否則進行網(wǎng)格選擇機制。

(4)網(wǎng)格選擇機制。當|Pt+1|+|Ri|

(5)當進化代數(shù)大于設(shè)定的n值時終止進化，并輸出外部種群個體，否則轉(zhuǎn)(6)繼續(xù)進化。

(6)遺傳操作。選擇外部種群的精英個體進行交叉、變異等操作，從而生成子代種群Pt+1，轉(zhuǎn)(2)進行迭代進化。

該算法采用小種群計算效率高的優(yōu)點并結(jié)合重啟動策略，避免了早熟收斂的特點，能有效地求解較多目標優(yōu)化問題。

3　測試函數(shù)及工程應(yīng)用

3.1兩目標測試函數(shù)

選擇文獻[15]中ZDT1函數(shù)和ZDT2函數(shù)作為測試函數(shù)進行分析：

ZDT1函數(shù)為

(7)

ZDT2函數(shù)為

(8)

變量個數(shù)n=30，變量xi∈[0,1]，i=1,2,…,30。在Gr-μMOGA算法中，其參數(shù)設(shè)置為：初始種群P1為8，外部種群Pe為100，交叉概率Pc為0.95，變異概率Pm為0.1，外部種群出現(xiàn)相同次數(shù)M為3，每個目標空間劃分成相等個數(shù)的子空間，取Dk為5。采用NSGA-Ⅱ算法作對比分析，其初始種群P1為50，其余參數(shù)設(shè)置與Gr-μMOGA相同，都采用單點交叉和位變異操作。

(a)NSGA-Ⅱ算法求解ZDT1函數(shù)的Pareto解(b)Gr-μMOGA算法求解ZDT1函數(shù)的Pareto解

(c)NSGA-Ⅱ算法求解ZDT2函數(shù)的Pareto解(d)Gr-μMOGA算法求解ZDT2函數(shù)的Pareto解圖4　ZDT1函數(shù)和ZDT2函數(shù)的優(yōu)化結(jié)果

3.2三目標測試函數(shù)

采用文獻[16]中的DTLZ1函數(shù)和DTLZ2函數(shù)進行分析，DTLZ1函數(shù)為

(9)

i=1,2,…,n

DTLZ2函數(shù)為

(10)

i=1,2,…,n

式(9)和式(10)中的g(xm)分別為

cos(20π(xi-0.5))]

xm=(xm,xm+1,…,xn)

3.3制動器多目標優(yōu)化設(shè)計

汽車盤式制動器相對鼓式制動器，具有散熱能力強、結(jié)構(gòu)簡單以及較高的方向穩(wěn)定性等優(yōu)點，被廣泛用于現(xiàn)代汽車制動系統(tǒng)中。制動器在汽車制動過程中起著關(guān)鍵性作用，制動器質(zhì)量、制動時間、制動圓盤半徑等設(shè)計參數(shù)直接決定制動器的制動性能。制動器的嚙合力越大，制動時間就越短，則需要更大的質(zhì)量承受較大的嚙合力，故制動器的嚙合力、制動時間和總質(zhì)量為多目標優(yōu)化問題。本文引入文獻[17]中的盤式制動器的優(yōu)化問題，設(shè)計變量為制動器圓盤內(nèi)徑、外徑、嚙合力、摩擦接觸面的個數(shù)，其多目標優(yōu)化模型為

f3(x)=x3

式中，f1(x)為制動器的質(zhì)量，kg；f2(x)為制動器的制動時間，s；f3(x)為制動器的嚙合力，N；x1為制動器圓盤的內(nèi)半徑，mm；x2為制動器圓盤的外半徑，mm；x3為制動器的嚙合力，N；x4為摩擦接觸面的個數(shù)。

(a)NSGA-Ⅱ算法求解DTLZ1函數(shù)的Pareto解

(b)Gr-μMOGA 算法求解DTLZ1函數(shù)的Pareto解

(c)NSGA-Ⅱ算法求解DTLZ2函數(shù)的Pareto解

(d)Gr-μMOGA算法求解DTLZ2函數(shù)的Pareto解圖5　DTLZ1函數(shù)和DTLZ2函數(shù)的優(yōu)化結(jié)果

其幾何約束g1(x)和g2(x)為

g1(x)=(x2-x1)-20≥0

g2(x)=30-2.5(x4+1)≥0

壓力約束g3(x)為

溫度約束g4(x)為

扭矩約束g5(x)為

邊界約束如下：55 mm≤x1≤80 mm，75 mm≤x2≤110 mm，1000 N≤x3≤3000 N，x4為[2,20]之間的整數(shù)。

將Gr-μMOGA算法用于求解制動器多目標優(yōu)化問題，其Pareto最優(yōu)解較好地分布于目標空間，如圖6所示。表1給出了圖6中的部分Pareto解。當設(shè)計者偏重于考慮制動器產(chǎn)生的制動力較小時可以選擇解1。解6的制動力為2988.4N，制動時間為2.1s，質(zhì)量為2.9kg，其制動時間最短，有利于汽車在緊急情況下快速制動。最終，設(shè)計者可以根據(jù)不同的設(shè)計需求選擇相應(yīng)的Pareto最優(yōu)解。

圖6　盤式制動器多目標優(yōu)化結(jié)果

序號質(zhì)量(kg)制動時間(s)制動力(N)設(shè)計變量(x1,x2,x3,x4)14.15.11365.556.6,108.1,1365.5,1121.63.62085.469.5,90.3,2085.4,1133.12.82265.775.3,109.9,2265.7,1143.72.62490.866.7,110,2490.8,1152.12.62821.965.4,93,2821.9,1162.92.12988.477.3,109.8,2988.4,11

3.4汽車高速和低速耐撞性多目標優(yōu)化設(shè)計

制動器具有較好的制動性，能有效地避免汽車發(fā)生碰撞。當碰撞無法避免時，其保險杠、防撞梁和吸能盒等相關(guān)部件應(yīng)能最大限度地保護乘員和汽車，降低損傷成本。采用文獻[18]中汽車高速和低速耐撞性多目標優(yōu)化設(shè)計模型，其中選取保險杠厚度x1、吸能盒內(nèi)板厚度x2、吸能盒外板厚度x3、前縱梁內(nèi)板厚度x4和前縱梁外板厚度x5為優(yōu)化設(shè)計變量，如圖7所示。高速碰撞模型為汽車以56 km/h的速度100%正面剛性壁障碰撞；低速碰撞模型為RCAR (Research Council for Automobile Repairs)中的正面偏置碰撞，如圖8所示。選取汽車保險杠和前縱梁等部件的輕量化設(shè)計與碰撞中座椅點的加速度積分均值為多目標優(yōu)化問題，其優(yōu)化模型為[18]

(11)

圖7　優(yōu)化設(shè)計變量

圖8　汽車偏置碰撞模型

圖9　汽車耐撞性多目標優(yōu)化結(jié)果

表2　耐撞性優(yōu)化部分Pareto最優(yōu)解

4　結(jié)語

本文提出了一種基于網(wǎng)格支配的微型多目標遺傳方法Gr-μMOGA，該算法可用于求解多目標函數(shù)的優(yōu)化問題。測試函數(shù)的結(jié)果表明，該算法具有較好的收斂性，在保證解的均勻性條件下可提高計算效率。采用本文提出的算法求解制動器和汽車高低速耐撞性多目標優(yōu)化設(shè)計問題，獲得了較好的非支配解集。在實際工程設(shè)計中，工程人員可以根據(jù)不同的設(shè)計方案選擇相應(yīng)的Pareto解以滿足設(shè)計要求。

[1]王炳剛, 饒運清, 邵新宇, 等. 基于多目標遺傳算法的混流加工/裝配系統(tǒng)排序問題研究[J]. 中國機械工程, 2009, 20(12): 1434-1438.

Wang Binggang, Rao Yunqing, Shao Xinyu, et al. A MOGA- based Algorithm for Sequencing a Mixed-model Fabrication/ Assembly System[J]. China Mechanical Engineering, 2009, 20(12): 1434-1438.

[2]張勇, 李光耀, 王建華. 多目標遺傳算法在整車輕量化優(yōu)化設(shè)計中的應(yīng)用研究[J]. 中國機械工程,2009,20(4): 500-503.

Zhang Yong, Li Guangyao, Wang Jianhua. Design Optimization on Lightweight of Full Vehicle Based on Multi- objective Genetic Algorithm[J]. China Mechanical Engineering, 2009,20(4): 500-503.

[3]陳建嶺, 孫杰, 李劍峰. 鈦合金銑削加工參數(shù)多目標優(yōu)化研究[J]. 中國機械工程, 2014, 25(2): 169-773.

Chen Jianling, Sun Jie, Li Jianfeng. Multi-objective Optimization of Cutting Parameters during Milling of Titanium Alloys[J]. China Mechanical Engineering, 2014, 25(2): 169-773.

[4]Schafer J D. Multiple Objective Optimization with Vector Evaluated Genetic Algorithms[C]//Proceedings of 1st International Conference on Genetic Algorithms and Their Applications. Pittsburgh, PA, USA, 1985: 93-100.

[5]Deb K, Pratap A, Agrwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.

[6]Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization[C]//Evolutionary Methods Design Optimization Control, Proceedings EUROGEN 2001.Athens,Greece,2001:95-100.

[7]謝然, 蘭鳳崇, 陳吉清, 等. 滿足可靠性要求的輕量化車身結(jié)構(gòu)多目標優(yōu)化方法[J]. 機械工程學報, 2011, 47(4): 117-124.

Xie Ran, Lan Fengchong, Chen Jiqing, et al. Multi-objective Optimization Method in Car-body Structure Light-weight Design with Reliability Requirement[J]. Chinese Journal of Mechanical Enineering, 2011, 47(4): 117-124.

[8]劉桂萍, 韓旭, 姜潮. 基于微型多目標遺傳算法的薄板沖壓成形變壓邊力優(yōu)化[J]. 中國機械工程, 2007, 18(21): 2614-2617.

Liu Guiping, Han Xu, Jiang Chao. Optimization of Variable Binder Force in Sheet Metal Forming Using the Micro Multi-objective Genetic Algorithm[J]. China Mechanical Engineering, 2007, 18(21): 2614-2617.

[9]Liu Guiping, Han Xu, Jiang Chao. A Novel Multi-objective Optimization Method Based on an Approximation Model Management Technique[J]. Computer Methods in Applied Mechanics and Engineering, 2008, 197(33): 2719-2731.

[10]劉桂萍, 韓旭, 官鳳嬌. 基于信賴域近似模型管理的多目標優(yōu)化方法及其應(yīng)用[J]. 中國機械工程, 2008, 19(10): 1140-1143.

Liu Guiping, Han Xu, Guan Fengjiao. A multi-objective optimization Method Based on the Trust Region Model Management Framework and Its Applicatio[J]. China Mechanical Engineering, 2008, 19(10): 1140-1143.

[11]Krishnakumar K. Micro-genetic Algorithms for Stationary and Non-stationary Function Optimization[C] //SPIE Proceedings: Intelligent Control and Adaptive Systems.Philadelphia, US, 1989: 289-296.

[12]Yang S X, Li M Q, Liu X H, et al. A Grid-Based Evolutionary Algorithm for Many-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(5): 721-736.

[13]Miettinen K. Nonlinear Multiobjective Optimization[M].New York: Kluwer Academic Publishers, 1999.

[14]Li M Q, Zheng J H, Shen R M, et al. A Grid-Based Fitness Strategy for Evolutionary Many-Objective Optimization[C]//Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation.New York, 2010:463-470.

[15]Zitzler E, Deb K, Thiele L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results[J]. IEEE Transactions on Evolutionary Computation, 2000, 8: 173 -195.

[16]Deb K, Thiele L, Laumanns M, et al. Scalable Multi-objective Optimization Test Problems[C]// Proceedings of the 2002 Congress on Evolutionary Computational.Honolulu, 2002:825-830.

[17]Osycaka A, Kundu S.A Modified Distance Method for Multicriteria Optimization Using Genetic Algorithms[J]. Computers & Industrial Engineering, 1996, 30:871-882.

[18]姜潮, 鄧善良. 考慮車輛高速和低速耐撞性的多目標優(yōu)化設(shè)計[J]. 計算力學學報, 2014,31(4): 474-479.Jiang Chao, Deng Shanliang. Multi-objective Optimization and Design Considering Automotive High-speed and Low-speed Crashworthiness[J].Chinese Journal of Computational Mechanics, 2014, 31(4): 474-479.

(編輯蘇衛(wèi)國)

Micro Multi-objective Genetic Algorithm Based on Grid Domination

Fu ChunmingJiang ChaoLiu GuipingDeng Shanliang

State Key Laboratory of Advanced Design and Manufacturing for Vehicle Body,Hunan University,Changsha,410082

A micro multi-objective genetic algorithm was proposed herein based on grid domination to solve multi-objective optimization problems and it had good convergence and high computational efficiency. The method combined with the concept of the grid dominance and micro multi-objective genetic algorithm. In each generation, the grid value, the grid crowding distance and grid coordinate point distance of every individual were calculated, respectively. Then elite individuals were selected to do crossover and mutation operators based on the grid domination sorting and grid selection strategies. The individuals were iterated toward the Pareto front and the Pareto optimal solutions were obtained. Finally, the proposed algorithm was verified effectively through four test functions and two practical engineering problems.

multi-objective genetic algorithm; grid domination; micro population; Pareto optimal solution; crashworthiness

2014-06-05

國家自然科學基金資助項目(11172096)；國家自然科學基金優(yōu)秀青年基金資助項目(51222502)；教育部新世紀優(yōu)秀人才支持計劃資助項目(NCET-11-0124)；湖南省杰出青年基金資助項目(14JJ1016)

TP18DOI：10.3969/j.issn.1004-132X.2015.16.014

符純明，男，1987年生。湖南大學汽車車身先進設(shè)計制造國家重點實驗室博士研究生。研究方向為差分進化算法、多目標優(yōu)化。姜潮(通信作者)，男，1978年生。湖南大學汽車車身先進設(shè)計制造國家重點實驗室教授、博士研究生導(dǎo)師。劉桂萍，女，1980年生。湖南大學汽車車身先進設(shè)計制造國家重點實驗室講師。鄧善良，男，1987年生。湖南大學汽車車身先進設(shè)計制造國家重點實驗室碩士研究生。