多目標(biāo)遺傳算法探究及其工程案例應(yīng)用

宋偉 李志鵬

摘要：針對(duì)多目標(biāo)優(yōu)化問(wèn)題，本文提出一種多目標(biāo)遺傳算法（MOGA）。該算法引入重啟動(dòng)策略，從而來(lái)避免進(jìn)化種群過(guò)早的收斂到某一局部Pareto最優(yōu)解。一旦進(jìn)化種群早熟，則在設(shè)計(jì)變量空間中重新生成一個(gè)進(jìn)化種群，同時(shí)提出一種探測(cè)算子在非支配解的設(shè)計(jì)空間中進(jìn)行探測(cè)性的搜索，以提高收斂效率。采用非支配解排序，將每代中的非支配解集存入一外部種群中，同時(shí)為了保持外部非支配個(gè)體分布的均勻性，進(jìn)一步根據(jù)個(gè)體擁擠距離進(jìn)行同一非支配級(jí)個(gè)體的比較和選擇。最后將該算法用于求解汽車被動(dòng)懸架結(jié)構(gòu)的多目標(biāo)優(yōu)化設(shè)計(jì)案例，求解結(jié)果表明其具有較強(qiáng)的求解工程問(wèn)題的能力。

關(guān)鍵詞：MOGA；重啟動(dòng)策略；Pareto最優(yōu)解；探測(cè)算子；非支配解

中圖分類號(hào)：TB 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1672—3198（2014）16—0196—03

1引言

尋求非劣解是多目標(biāo)決策的基本手段，已有成熟的非劣解生成技術(shù)本質(zhì)上都是以標(biāo)量?jī)?yōu)化的手段通過(guò)多次計(jì)算得到非劣解。圍繞多目標(biāo)決策問(wèn)題，國(guó)內(nèi)外諸多學(xué)者進(jìn)行了探究。向量評(píng)價(jià)遺傳算法（VEGA）是由Schaffer開發(fā)的多目標(biāo)優(yōu)化程序，其中包括了多判據(jù)函數(shù)。VEGA系統(tǒng)的主要思想是將群體劃分為相等規(guī)模的子群體：每個(gè)子群體對(duì)于m個(gè)目標(biāo)中的某單個(gè)目標(biāo)是“合理的”，對(duì)每個(gè)目標(biāo)，選擇過(guò)程是獨(dú)立執(zhí)行的，但交叉是跨越子群體邊界的。進(jìn)化過(guò)程中的適應(yīng)度評(píng)價(jià)和選擇過(guò)程在每一代的進(jìn)化中都要執(zhí)行m次。VEGA歸根結(jié)底仍是一種基于單目標(biāo)的優(yōu)化選擇過(guò)程，難以收斂到非劣解集。Coello和Gregorio提出MicroGA-Moo以及他們?cè)?003年提出的改進(jìn)算法MicroGA2-Moo，算法中采取一些較復(fù)雜的處理方法，使種群多樣性和Pareto最優(yōu)解分布的均勻性較小地受到小規(guī)模群體的影響，如在MicroGA-Moo中融入較多敏感參數(shù)，并且事先設(shè)定各敏感參數(shù)值，而在其改進(jìn)算法中又融入并行進(jìn)化過(guò)程來(lái)選擇最優(yōu)遺傳交叉算子，實(shí)際上算法效率沒(méi)有很好地提高。Fonseca和Fleming提出了一種基于Pareto群體分級(jí)的多目標(biāo)遺傳算法（FFGA），建立了個(gè)體的級(jí)別與當(dāng)前群體中被該個(gè)體占優(yōu)的染色體數(shù)目的關(guān)系，同時(shí)Fonseca使用了一種基于共享機(jī)制小生境技術(shù)來(lái)使群體均勻分布在Pareto解集上，F(xiàn)FGA算法簡(jiǎn)單，易于實(shí)現(xiàn)，但它的效率依賴于共享因子的選擇，且對(duì)之非常敏感。

本文基于上述各算法優(yōu)缺點(diǎn)，提出基于Pareto排序分級(jí)的多目標(biāo)Pareto遺傳算法，主要針對(duì)算法過(guò)程中的Pareto排序問(wèn)題、適應(yīng)度值計(jì)算問(wèn)題、種群多樣性保持問(wèn)題、約束處理等。將改進(jìn)后的算法應(yīng)用于求解汽車被動(dòng)懸架結(jié)構(gòu)參數(shù)多目標(biāo)優(yōu)化設(shè)計(jì)案例，求解結(jié)果驗(yàn)證了改進(jìn)算法的有效性。

2多目標(biāo)遺傳算法（MOGA）實(shí)現(xiàn)流程

針對(duì)基本遺傳算法對(duì)于工程中的復(fù)雜非線性MOP求解的局限性，本文在基本遺傳算法的基礎(chǔ)上提出了多目標(biāo)遺傳算法（MOGA）。在MOGA中，不是簡(jiǎn)單地為各個(gè)體分配適應(yīng)度值，而是針對(duì)種群中各個(gè)體首先計(jì)算它的非支配級(jí)和個(gè)體擁擠距離，并根據(jù)這兩個(gè)值進(jìn)行個(gè)體間的比較和選擇操作。非支配級(jí)和個(gè)體擁擠距離分別是通過(guò)非支配分級(jí)操作及NSGA-ΙΙ的個(gè)體擁擠距離計(jì)算方法得到的。在兩個(gè)個(gè)體進(jìn)行比較時(shí)，首先比較它們的非支配級(jí)，非支配級(jí)數(shù)小的個(gè)體要優(yōu)于級(jí)數(shù)大的個(gè)體。若非支配級(jí)數(shù)相同，則比較它們的個(gè)體擁擠距離，個(gè)體擁擠距離大的個(gè)體要優(yōu)于該值小的個(gè)體。非支配數(shù)為1的個(gè)體即為當(dāng)前的非支配個(gè)體，它們將被保存到一個(gè)外部種群Pe中。以上的個(gè)體比較和選擇操作是針對(duì)無(wú)約束優(yōu)化問(wèn)題的，對(duì)于帶約束的多目標(biāo)優(yōu)化問(wèn)題，則采用Deb等人提出的約束處理方法來(lái)處理約束。該方法就是對(duì)每個(gè)個(gè)體計(jì)算一個(gè)約束違反值，當(dāng)兩個(gè)個(gè)體進(jìn)行比較時(shí)，首先比較其約束違反值，該值越小的個(gè)體越優(yōu)，約束違反值為零的個(gè)體為可行解，當(dāng)兩個(gè)個(gè)體均為可行解時(shí)，則采用無(wú)約束問(wèn)題的個(gè)體比較操作進(jìn)行比較。

在遺傳算法進(jìn)化過(guò)程中，當(dāng)連續(xù)M代的外部種群Pe都相同或者相近時(shí)，則種群收斂到解空間某一局部最優(yōu)區(qū)域，此時(shí)則采用重啟動(dòng)策略，即重新在自變量空間中隨機(jī)生成一同規(guī)模大小的新種群，同時(shí)采用探測(cè)算子法生成兩個(gè)新個(gè)體，然后將這兩個(gè)新個(gè)體與外部種群中的個(gè)體進(jìn)行非支配關(guān)系比較，若新個(gè)體沒(méi)有被外部種群中的任何一個(gè)個(gè)體支配，則把它加入外部種群中，并去掉其中被它所支配的個(gè)體。

3多目標(biāo)遺傳算法（MOGA）實(shí)現(xiàn)技術(shù)

3.1非支配分級(jí)

非支配分級(jí)就是根據(jù)基于Pareto思想進(jìn)行非支配排序分級(jí)，將個(gè)體按照級(jí)數(shù)從高到低的順序進(jìn)行排列。級(jí)數(shù)高的個(gè)體適應(yīng)度值優(yōu)于級(jí)數(shù)低的個(gè)體，其中級(jí)數(shù)為1的個(gè)體為當(dāng)前種群中的非支配個(gè)體。在MOGA中采用了一種快速高效的非支配排序方法，該方法的具體實(shí)現(xiàn)過(guò)程如下：

（1）初始化個(gè)體集Di和非支配個(gè)體集Fj，令j=1；

（2）對(duì)每個(gè)個(gè)體i計(jì)算種群中支配它的個(gè)體數(shù)目值ndi，同時(shí)將被它支配的個(gè)體放入個(gè)體集Di，并將種群中ndi=0的個(gè)體放入第1級(jí)非支配個(gè)體集Fj中；

（3）令第j+1級(jí)的非支配個(gè)體集Fj+1=，將Fj中的個(gè)體從種群中剔除，再把其中的每個(gè)個(gè)體的ndi均減去1，在這個(gè)過(guò)程中如果沒(méi)有某個(gè)個(gè)體的ndi=0，則將該個(gè)體放到Fj+1中；

（4）j=j+1，若各非支配個(gè)體集中的個(gè)體包含所有種群個(gè)體，則終止，否則轉(zhuǎn)到步驟3。

經(jīng)過(guò)上面的非支配排序分級(jí)后，種群中所有個(gè)體就都被分配到各個(gè)非支配個(gè)體集Fj，j=1，2，…。

3.2種群多樣性保持策略

針對(duì)MOGA多樣性保持問(wèn)題，本文提出采用兩個(gè)種群來(lái)確保種群多樣性：一個(gè)種群是用來(lái)保持進(jìn)化種群中個(gè)體遺傳基因多樣性的重啟動(dòng)策略；另一個(gè)種群則是用來(lái)保持外部非支配個(gè)體種群多樣性的個(gè)體擁擠距離比較方法。

3.2.1重啟動(dòng)策略

MOGA中所采用的重啟動(dòng)策略的基本思路與GA的大致相同，但MOGA是用于多目標(biāo)優(yōu)化問(wèn)題的求解，由于多目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解一般是一組無(wú)法相互比較的解，因此它所采用的重啟動(dòng)策略在具體實(shí)現(xiàn)時(shí)與用于單目標(biāo)問(wèn)題求解的GA不同主要體現(xiàn)在以下兩方面：

（1）重啟動(dòng)判斷條件不同：在MOGA中，若連續(xù)M代的外部非支配種群Pe相同或者相似，則認(rèn)為此時(shí)的種群收斂到解空間的局部最優(yōu)區(qū)域，因此重啟動(dòng)判斷條件參數(shù)為外部種群連續(xù)相同的代數(shù)M，在本文中，M也稱為重啟動(dòng)判斷參數(shù)，其值為事先設(shè)定值；

（2）重啟動(dòng)方式不同：MOGA中不僅在搜索空間內(nèi)隨機(jī)生成一規(guī)模數(shù)相同的新種群，還采用了一種探測(cè)算子在非支配解區(qū)域進(jìn)行探測(cè)性的搜索，即通過(guò)探測(cè)算子法得到兩個(gè)新個(gè)體，然后將生成的新種群和兩個(gè)新個(gè)體與外部種群合并進(jìn)行非支配排序分級(jí)。這樣既可以提高種群的多樣性，同時(shí)加強(qiáng)算法的局部搜索能力。

探測(cè)算子是一種用來(lái)在當(dāng)前非支配解區(qū)域?qū)崿F(xiàn)探測(cè)性搜索的算子。它生成以下兩個(gè)新個(gè)體E1和E2：

公式（3）、（4）中，n表示子目標(biāo)的個(gè)數(shù)，l表示當(dāng)前外部種群中非支配解的個(gè)數(shù)。

3.2.2個(gè)體擁擠距離比較方法

傳統(tǒng)上擁擠距離法中的共享參數(shù)需要事先設(shè)定預(yù)設(shè)值，本文提出的方法不需要預(yù)設(shè)參數(shù)值。具體操作步驟如下：首先分別計(jì)算各級(jí)Fj中各個(gè)體的擁擠距離，按照擁擠距離從大到小的原則對(duì)各級(jí)非支配個(gè)體集中的個(gè)體進(jìn)行排序，擁擠距離大的個(gè)體適應(yīng)度值優(yōu)于擁擠距離小的個(gè)體。個(gè)體的擁擠距離即計(jì)算該個(gè)體相鄰的兩個(gè)個(gè)體在各個(gè)目標(biāo)上的歐式距離之和來(lái)表示的。計(jì)算個(gè)體擁擠距離時(shí)，首先按照各子目標(biāo)將個(gè)體在該子目標(biāo)值下以從大到小的順序進(jìn)行排列，再根據(jù)公式（5）在每個(gè)子目標(biāo)上都進(jìn)行一次計(jì)算：

3.3最優(yōu)個(gè)體保持策略

在MOGA中，當(dāng)代種群中的非支配個(gè)體之間在不設(shè)置權(quán)值的情況下是無(wú)法比較優(yōu)劣的，因此執(zhí)行精英策略時(shí)一般將該代的所有非支配個(gè)體都保留到下一代的進(jìn)化種群中。

4性能測(cè)試及評(píng)價(jià)

本文將MOGA應(yīng)用于求解汽車被動(dòng)懸架結(jié)構(gòu)參數(shù)優(yōu)化的案例中。汽車懸架是把車架（車身）與車橋（車輪）彈性連接起來(lái)的所有裝置的總稱。作為連接車身與車輪的傳力部件，它的特性直接影響著汽車乘坐舒適性、操作穩(wěn)定性和行駛安全性等性能，并且這一特性對(duì)汽車各方面性能的影響是相互矛盾的，即優(yōu)化問(wèn)題的各子目標(biāo)間相互矛盾，故需要對(duì)懸架結(jié)構(gòu)參數(shù)進(jìn)行多目標(biāo)優(yōu)化設(shè)計(jì)。

4.1多目標(biāo)優(yōu)化問(wèn)題的建立

懸架按照其控制力的施加形式一般可分為被動(dòng)懸架、半主動(dòng)懸架和主動(dòng)懸架。其中被動(dòng)懸架由于結(jié)構(gòu)簡(jiǎn)單、性能可靠以及成本低等特點(diǎn)，是目前應(yīng)用的最為廣泛的類型。但是被動(dòng)懸架設(shè)計(jì)完成后，其剛度參數(shù)和阻尼系數(shù)參數(shù)是確定的，因此需建立數(shù)學(xué)優(yōu)化模型對(duì)其參數(shù)進(jìn)行優(yōu)化以盡可能獲得更優(yōu)的性能。一般情況下對(duì)于被動(dòng)懸架來(lái)說(shuō)，要獲最佳的乘坐性能，懸架應(yīng)該“軟”一些，但要獲得好的汽車操控性能，懸架又應(yīng)該“硬”一些。這兩者之間是相互矛盾的，但又都是汽車性能比較重要的方面，于是對(duì)被動(dòng)懸架參數(shù)進(jìn)行優(yōu)化設(shè)計(jì)時(shí)，這兩個(gè)方面都應(yīng)該考慮到。另外行駛安全性也是與懸架相關(guān)的汽車性能的重要方面，在優(yōu)化設(shè)計(jì)時(shí)也應(yīng)考慮。

鑒于汽車本身為復(fù)雜的振動(dòng)系統(tǒng)，為了便于數(shù)學(xué)分析，通常采用簡(jiǎn)化模型。圖1所示為一個(gè)二自由度1/4汽車振動(dòng)的簡(jiǎn)化模型。其中m1和m2為輪胎和車體的質(zhì)量，k1和k2分別為輪胎和懸架的剛度，r2為懸架的阻尼系數(shù)，ζ、x1和是評(píng)價(jià)乘坐舒適性的主要指標(biāo)，懸架動(dòng)行程x2-x1不僅會(huì)影響乘坐舒適性，而且還要受懸架工作空間的限制，輪胎位移x1-ζ主要與操縱穩(wěn)定性和行駛安全性相關(guān)。因此在優(yōu)化時(shí)選擇這三個(gè)響應(yīng)的均方值作為優(yōu)化目標(biāo)，而懸架參數(shù)m由圖2可知，本文提出的MOGA算法的種群進(jìn)化700代是得到的Pareto最優(yōu)解集的分布較均勻。由表1及表2可知，與初始設(shè)置參數(shù)下的被動(dòng)懸架相比，車身加速度的均方根值減少幅度較大，最多達(dá)到17%，懸架行程和輪胎位移則最多可分別達(dá)到9%和5%。因此上述優(yōu)化結(jié)果證明了MOGA對(duì)于多于三個(gè)子目標(biāo)的工程優(yōu)化問(wèn)題具有較強(qiáng)的求解能力，算法是可行的、有效的。

參考文獻(xiàn)

[1]Schaffer J D.Multiple objective optimization with vector evaluated genetic algorithms[C].In：Proc.Of 1st Int.Conf.On Genetic Algorithms and Their Application，Lawrence Erlbaum Associates，1985：93100.

[2]Gregorio T P and Carlos A.The micr0 genetic algorithm 2：towards online adaptation in evolutionary multiobjective optimization[C]. In： Evolutionary，MultiCriterion Optimization Second International Conference（EMO 2003）.Faro，Portugal，2003：252266.

[3]Fonseca C.M.，F(xiàn)leming P.J.，Genetic Algorithms for multiobjective optimization：formulation，discussion and generalization[C].In S.Forrest Ed.Proceedings of Fifth International Conference on Genetic Algorithms（San Mateo，California，1993），University of Illinois at UrbanaChampaign：Morgan Kaufman Publishers，1993：416423.

[4]Deb K，Pratap A，Agarwal S，et a1.A fast and elitist multiobjective genetic algorithm：NSGA II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182197.

[5]Deb K.An efficient constrainthanding method for genetic algorithms[J].Computer Methods Appl.Mech.Eng.，2000，186（24）：311338.

[6]Deb K，Pratap A，Agarwal S，et a1.A fast and elitist multiobjective genetic algorithm：NSGA II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182197.

[7]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，1999.

[8]余志生.汽車?yán)碚摚ǖ?版）[M].北京：機(jī)械工業(yè)出版社，1990.