基于網格支配的微型多目標遺傳算法

符純明　姜　潮　劉桂萍　鄧善良

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

基于網格支配的微型多目標遺傳算法

符純明姜潮劉桂萍鄧善良

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

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

多目標遺傳算法；網格支配；微型種群; Pareto最優解；耐撞性

0　引言

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

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

1　多目標優化相關概念

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

(1)

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

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

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

2　Gr-μMOGA算法及構造

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

2.1網格的概念及相關參數定義

第k個目標函數的網格間距dk為

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

(2)

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

圖1　第k個目標函數賦予的網格屬性

個體x在m個目標函數下的網格值之和為

(3)

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

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

個體x和y在m個目標函數下的網格值之差定義為網格差值，記為GD：

(4)

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

(5)

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

(6)

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

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

圖2　個體在網格中的Gr值和dGC值

2.2算法流程

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

圖3　Gr-μMOGA計算流程

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

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

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

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

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

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

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

3　測試函數及工程應用

3.1兩目標測試函數

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

ZDT1函數為

(7)

ZDT2函數為

(8)

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

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

(c)NSGA-Ⅱ算法求解ZDT2函數的Pareto解(d)Gr-μMOGA算法求解ZDT2函數的Pareto解圖4　ZDT1函數和ZDT2函數的優化結果

3.2三目標測試函數

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

(9)

i=1,2,…,n

DTLZ2函數為

(10)

i=1,2,…,n

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

cos(20π(xi-0.5))]

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

3.3制動器多目標優化設計

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

f3(x)=x3

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

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

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

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

(d)Gr-μMOGA算法求解DTLZ2函數的Pareto解圖5　DTLZ1函數和DTLZ2函數的優化結果

其幾何約束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]之間的整數。

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

圖6　盤式制動器多目標優化結果

序號質量(kg)制動時間(s)制動力(N)設計變量(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汽車高速和低速耐撞性多目標優化設計

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

(11)

圖7　優化設計變量

圖8　汽車偏置碰撞模型

圖9　汽車耐撞性多目標優化結果

表2　耐撞性優化部分Pareto最優解

4　結語

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

[1]王炳剛, 饒運清, 邵新宇, 等. 基于多目標遺傳算法的混流加工/裝配系統排序問題研究[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]張勇, 李光耀, 王建華. 多目標遺傳算法在整車輕量化優化設計中的應用研究[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]陳建嶺, 孫杰, 李劍峰. 鈦合金銑削加工參數多目標優化研究[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]謝然, 蘭鳳崇, 陳吉清, 等. 滿足可靠性要求的輕量化車身結構多目標優化方法[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]劉桂萍, 韓旭, 姜潮. 基于微型多目標遺傳算法的薄板沖壓成形變壓邊力優化[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]劉桂萍, 韓旭, 官鳳嬌. 基于信賴域近似模型管理的多目標優化方法及其應用[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]姜潮, 鄧善良. 考慮車輛高速和低速耐撞性的多目標優化設計[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.

(編輯蘇衛國)

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)；國家自然科學基金優秀青年基金資助項目(51222502)；教育部新世紀優秀人才支持計劃資助項目(NCET-11-0124)；湖南省杰出青年基金資助項目(14JJ1016)

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

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