艾青松 許 強 劉 泉

武漢理工大學，武漢，430070

1 多目標優(yōu)化進化算法概述

現(xiàn)代制造企業(yè)要高效率、低成本地設計和生產(chǎn)令客戶滿意的產(chǎn)品，就必須能夠快速準確地獲取客戶的個性化需求，以最快的速度加以滿足。然而，滿足客戶的需求并不是唯一的目標，還要考慮企業(yè)的生產(chǎn)設備、技術實力、制造能力、人員力量以及生產(chǎn)成本、生產(chǎn)周期和企業(yè)管理等其他因素，只有在滿足客戶需求且自身條件具備的前提下，才能在最短的時間內生產(chǎn)出讓客戶滿意的商品，達到生產(chǎn)企業(yè)和客戶之間的雙贏。因此，基于客戶需求信息的產(chǎn)品設計優(yōu)化是一個多目標優(yōu)化問題［1］。

近年來，有學者提出了多目標優(yōu)化進化算法（evolutionary multi－objective optimization，EMO）［2］，該算法作為一種簡單有效的全局搜索算法，具有較強的全局收斂能力和較強的魯棒性，且不需要借助問題的特征信息（如導數(shù)等梯度信息）就可以有效求解大量非線性、不可微和多峰值的復雜優(yōu)化問題。

進化算法是以達爾文的進化論思想為基礎，通過模擬自然界生物進化準則逼近問題最優(yōu)解的一類群體搜索算法［3］。生物進化是通過繁殖、變異、競爭和選擇來實現(xiàn)的，而進化算法則主要通過選擇 （selection）、重 組 （recombination）和 變 異（mutation）這三種操作來實現(xiàn)優(yōu)化問題的求解或近似求解。進化算法的基本步驟一般為［3］：①初始化進化算法的停止條件，t＝1；②初始化種群大小，給每個個體賦予坐標值；③計算出每個個體的目標值并存入一個矩陣中；④進行⑤～⑥的循環(huán)進化，每輪進化后，t自動加1；⑤對種群進行選擇操作，主要選擇局部達到優(yōu)化的個體作為優(yōu)良個體，保存在外部種群中；⑥重組外部種群和內部種群，讓它們進行交配和變異，并選擇出優(yōu)良個體保存在外部種群中；⑦當達到進化停止條件即t達到一定數(shù)值后，停止進化算法，取外部種群中的個體作為本次進化算法最終得到的優(yōu)化個體。

簡單地說，進化算法就是通過不斷地選擇、交配和變異，最終得到一系列優(yōu)化個體，完成對多目標優(yōu)化問題的優(yōu)化工作。進化算法的具體實現(xiàn)方式多樣，本文以粒子群優(yōu)化算法（PSO）［4］為例進行深入研究。

粒子群優(yōu)化算法將決策空間內的變量看成一個粒子，粒子以一定的速度和方向飛行。在飛行過程中，粒子追尋兩個極值來更新自己的位置，即局部最優(yōu)位置pbest和全局最優(yōu)位置gbest。其進化方程如下［4］：

式中，i表示第i個粒子；j表示維數(shù)，也就是目標數(shù)；c1為調節(jié)粒子飛向局部最優(yōu)位置的步長；c2為調節(jié)粒子飛向全局最優(yōu)位置的步長，通常在［0，2］中取值；r1和r2為兩個獨立的隨機數(shù)，在［0，1］中隨機取值；t為停止條件，即粒子飛行次數(shù)，t越大，粒子飛行位置越密集，得到的pbest和gbest將越精確。

由式（1）可以看出，粒子群算法將進化算法的進化思路具體化為粒子的位置和速度變化，通過不斷比較和更新pbest和gbest來實現(xiàn)全局優(yōu)化。

然而，到目前為止多目標優(yōu)化進化算法尚缺乏系統(tǒng)性研究，一些理論性問題有待進一步探討。例如，算法只適合于低維目標優(yōu)化，對高維優(yōu)化效果很差；有些算法有優(yōu)越的優(yōu)化方法，但難以用于工程實際。基于客戶需求信息的產(chǎn)品設計與優(yōu)化也有其自身的特點，它一方面要求在客戶給出需求信息后，企業(yè)能盡快作出反應，提出合適的方案供客戶選擇，縮短產(chǎn)品設計時間，提高整個項目效率。另一方面要求我們的算法得出的目標優(yōu)化值均勻分布，在可行性空間里找到更多的優(yōu)化解并保證每個解的有效性，避免重復解的出現(xiàn)，方便用戶對目標優(yōu)化值進行比較，最終選擇出合適的產(chǎn)品設計方案。而目前的多目標優(yōu)化進化算法未能很好地解決這些問題。所以，我們還需要對多目標優(yōu)化進化算法進行研究，提出合適的、高效的優(yōu)化算法。

基于此，本文對多目標優(yōu)化進化算法進行研究，針對產(chǎn)品設計與優(yōu)化過程中所要解決的問題，在現(xiàn)有多目標優(yōu)化進化算法基礎上，從優(yōu)化算法的執(zhí)行效率和優(yōu)化結果的分布兩方面進行了必要的改進，并分別進行實驗仿真，通過與其他優(yōu)化算法的對比分析，驗證了改進算法的可行性、可靠性和優(yōu)越性。

2 多目標優(yōu)化進化算法的效率改進

進化算法通過不斷選擇和淘汰局部最優(yōu)解而得到的全局最優(yōu)解集所對應的最優(yōu)前沿曲面應該包含所有目標的極值，它對任何一個目標都是公平的。如式（1）所示，粒子的飛行位置xij和速度vij在更新過程中沒有偏向任何目標，只是盲目地朝著全局最優(yōu)解收斂而已。而在實際的生產(chǎn)設計過程中，按照客戶和企業(yè)的不同要求，目標之間往往是不公平的。假設某個目標對客戶很重要，需要著重考慮該目標的優(yōu)化值，即可以在一定范圍內，通過犧牲其他目標來滿足該目標的需求，那么，我們得到的“公平”最優(yōu)前沿曲面就顯得資源浪費，從產(chǎn)品開發(fā)的實際效率來講，降低了算法的執(zhí)行效率。

另外，本文的主要工作是設計一種多目標優(yōu)化算法，并將其運用在基于客戶需求的產(chǎn)品設計中，得出最優(yōu)化解集，讓客戶選擇其中一個解作為定制產(chǎn)品開發(fā)方案。如果得出的最優(yōu)化解集過大，優(yōu)化解過多，則一方面加大了客戶的選擇壓力，不利于客戶找出最適合的那個解；另一方面，客戶還需要大量時間對優(yōu)化解進行比較，選擇出最合適的解，從產(chǎn)品開發(fā)效率來看，這也會降低項目設計階段的效率。

基于以上兩個問題，本文提出了側重度系數(shù)概念，根據(jù)客戶的選擇，將每個目標的重要程度分等級，在進化算法運行過程中，通過重要度的比較，優(yōu)先淘汰一些重要度很低的局部優(yōu)化解。這樣，一方面實現(xiàn)了最優(yōu)前沿曲面按照客戶的需求收斂，提高了算法執(zhí)行效率；另一方面，也減少了最終得到的優(yōu)化解個數(shù)，提高了客戶定制產(chǎn)品設計階段的效率。

定義1 側重度系數(shù)λ。由目標之間相互重要程度信息轉化而來的重要度參數(shù)稱為側重度系數(shù)。

本文定義的目標側重度系數(shù)如表1所示。

表1 重要度信息衡量標準表

多目標優(yōu)化問題目前在學術界已經(jīng)統(tǒng)一成目標函數(shù)值極小問題［3-4］，所以，加入目標側重度系數(shù)后，粒子的有效運動范圍應該是讓側重度高的目標取值更小、更靠近目標極小值的范圍，將該范圍取名為側重范圍。如果把整個坐標系分成10等份，分別定義目標A對目標B的側重度系數(shù)為0.90、0.75、0.60和0.50，則它們的側重范圍如圖1所示。

圖1 4種側重度系數(shù)下的側重范圍

從圖1中可以觀察到側重范圍的大小，為了對粒子的位置是否合格做相應判斷，我們需要計算出側重范圍的邊界曲線函數(shù)。因為把坐標系等分成10份，每一份就是9°，所以圖1中4個側重范圍的夾角分別為18°、45°、72°和90°。通過三角函數(shù)計算，得出4種側重范圍的邊界曲線函數(shù)如表2所示。其中，側重度系數(shù)為0.5即目標之間同等重要時，沒有側重范圍，因而也就沒有邊界曲線。下面闡述加入側重度系數(shù)的進化算法運行思路。

表2 4種側重范圍的邊界曲線函數(shù)

在進化算法運行步驟⑤后面加入優(yōu)良個體的再次選擇環(huán)節(jié)，判斷每個優(yōu)良個體的位置是否在側重范圍內。如果在側重范圍內則進入下一步驟；否則淘汰該個體。其他步驟不變，依此循環(huán)進化，達到停止條件后即得到最優(yōu)解。

設側重區(qū)域為Ω，加入側重度系數(shù)λ后的粒子群的優(yōu)化方程變?yōu)?/p>

式（2）中，速度vij中有兩個隨機變量r1和r2存在，所以能讓粒子在朝全局最優(yōu)解收斂時，沿著不同的路徑找到更多的pbest，而位置xij則必須限定在側重范圍內，這樣收斂區(qū)域將變小，收斂效率變高。

我們運用改進算法對ZDT［5］問題進行優(yōu)化，ZDT問題的數(shù)學方程如下：

查閱相關文獻得知，ZDT問題的理想最優(yōu)化曲面如圖2所示。

定義目標f1對目標f2的側重度系數(shù)為0.90，設定停止條件為t＝10 000，取c1＝c2＝1，則改進算法的優(yōu)化仿真圖見圖3。

圖2 測試問題ZDT的理想最優(yōu)化曲面

圖3 λ＝0.90的優(yōu)化仿真圖

為了方便對比分析，本文運用進化算法NSGA－2［1］對ZDT問題進行優(yōu)化。設定停止條件為t＝10 000，交叉系數(shù)Pc為0.8，變異系數(shù)Pm為1／30，優(yōu)化仿真圖見圖4。

從圖3和圖4中可以看出，加入側重度系數(shù)后的進化算法能夠讓粒子有選擇地收斂，減少了最優(yōu)解的個數(shù)，提高了客戶的選擇效率。觀察圖形可知，改進算法達到了預期目標。

多目標優(yōu)化領域中一般采用Deb等［5］提出的收斂性指標（convergence metric）對多目標優(yōu)化算法的優(yōu)化效果進行評判。為此，本文做了2組對比實驗，在目標側重度系數(shù)為0.9的條件下，將改進算法和目前流行的兩種進化算法（NSGA－2算法［1］和 SPEA－2算法［6］）進行比較，得到數(shù)據(jù)如表3所示。

圖4 NSGA－2算法對ZDT問題的優(yōu)化仿真圖

表3 不同停止條件下的多目標優(yōu)化算法運行時間和收斂性指標值

從表3可以看出，當側重度系數(shù)為0.9時，改進算法的運行時間明顯短于NSGA－2算法和SPEA－2算法的算法時間，說明改進算法的優(yōu)化效率更高。并且改進算法的收斂性指標值也小于NSGA－2算法和SPEA－2算法的收斂性指標值，而該指標值越小，說明算法得到的最優(yōu)化曲面與圖2中的理想最優(yōu)化曲面的距離越近，算法更優(yōu)越。

以上對多目標優(yōu)化進化算法優(yōu)化效率的改進研究表明，通過加入目標側重度系數(shù)，縮小了最優(yōu)解集，方便客戶快速選擇出適合項目的最優(yōu)解。同時，采用改進算法對多目標優(yōu)化問題進行優(yōu)化后，得出的最優(yōu)化粒子與理想的最優(yōu)化曲面更接近，即優(yōu)化效果更明顯。

3 多目標優(yōu)化進化算法的解分布改進

采用進化算法對多目標優(yōu)化問題進行優(yōu)化的過程中，很容易產(chǎn)生局部優(yōu)化解過于集中的現(xiàn)象。這些高度集中的局部最優(yōu)解占據(jù)了最優(yōu)解集中的大量位置，排擠掉了一些偏僻和孤立的優(yōu)化解，導致最優(yōu)解多樣性缺失，使進化算法陷入局部最優(yōu)，學術界通常稱該現(xiàn)象為早熟。如式（1）中，由于r1和r2兩個獨立隨機數(shù)的存在，導致粒子的收斂方向不固定。如果在某一次收斂中得到的局部最優(yōu)解大量集中，即xij變化不大，那么粒子將陷入局部最優(yōu)的包圍中，很難脫離出來，最終將局部收斂。

采用進化算法對多目標優(yōu)化問題進行優(yōu)化后，我們將得到一些接近于理想優(yōu)化曲面的離散優(yōu)化點，稱它們?yōu)槟繕藘?yōu)化值?？蛻魪谋姸嗄繕藘?yōu)化值中選擇出一個滿意的優(yōu)化值作為產(chǎn)品設計的最優(yōu)目標值。如果兩個目標優(yōu)化值相隔過近，則它們沒有比較的價值，稱之為重復目標優(yōu)化值，必須拋棄其中一個。所以，如何合理選擇目標優(yōu)化值，使它們相互之間有一定的距離，避免重復值的出現(xiàn)，是本文對進化算法改進的另一個出發(fā)點。即對于客戶來說，要做到大部分目標優(yōu)化值對他們的選擇都有意義。

基于以上兩個問題，本文提出了目標間距矩陣概念，根據(jù)客戶自己的選擇，確定每個目標的最小距離。在選擇局部最優(yōu)解和目標優(yōu)化值時，檢驗它們之間的間距是否大于或等于最小距離。如果滿足條件，則被選中，進行下一步操作；否則，淘汰該值。

定義2 目標間距矩陣。假設一個多目標優(yōu)化問題中有m個目標需要優(yōu)化，而這m個目標都有各自的最小距離，即要求第i個目標的目標值之間最小間隔Li個單位。那么，由這m個最小距離組成的矩陣L＝［L1L2L3… Lm］稱為目標間距矩陣。

下面詳細說明改進算法的執(zhí)行過程。

假設在進化算法進行優(yōu)良個體選擇時有n個個體a1，a2，a3，…，an比較優(yōu)秀，可以進入下一代進行交配。此時，我們將這n個個體進行排序，排序的規(guī)則是：先比較這n個個體的第一個目標值大小，按照從小到大的順序排序；然后比較這n個個體的第二個目標值大小，按照從小到大的順序排列；再比較這n個個體的第三個目標值大小，也按照從小到大的順序排列。依照這個方法，對這n個個體總共進行m次排序，可以得到一個m行的排序隊列，如圖5所示。

圖5 優(yōu)良個體的排序序列

然后讀取目標間距矩陣中每個目標的最小間距，對上述隊列進行檢查，如果相鄰兩個個體之間不滿足該排序標準的目標的間距指標，則淘汰兩個個體中的后一個個體。通過目標間距矩陣對這m個排序序列進行排查，淘汰一些間距過小的個體。然后再次考察這個序列，如果某個個體出現(xiàn)的次數(shù)等于m，則表示該個體勝出，作為優(yōu)良個體進入下一代種群中；如果某個個體出現(xiàn)的次數(shù)小于m，則表示該個體被淘汰，不能作為優(yōu)良個體進入下一代種群。

在進化算法的執(zhí)行過程中，每次選擇出種群優(yōu)良個體后，都按照上述方法對優(yōu)良個體進行再一次的選擇，勝出者才能進入下一代種群中進行交配和變異。這樣，通過往進化算法中加入目標間距矩陣，并對優(yōu)良個體反復進行間距排查，能夠避免局部最優(yōu)解的高度集中，保證了最優(yōu)解的多樣性，防止算法早熟。同時，能夠讓最終得到的最優(yōu)解集中的解趨于均勻分布，方便客戶做對比分析，快速選擇出定制產(chǎn)品的開發(fā)方案。

在粒子群優(yōu)化算法中加入目標間距矩陣后的進化方程如下：

在式（4）中，每次粒子更新位置時都加上該目標的最小間距，即將該粒子沿著目標坐標軸平移最小間距的距離，這樣來防止粒子位置的高度集中，以免陷入局部最優(yōu)。

下面采用改進算法對現(xiàn)今流行的測試問題DTLZ［5］進行優(yōu)化仿真實驗，DTLZ數(shù)學表達式如下：

定義DTLZ問題的目標間距矩陣為L＝［0.05 0.05 0.05］，k＝3，｜xk｜＝5，停止條件為t＝10 000，取c1＝c2＝1，得到的優(yōu)化仿真圖見圖6。

同樣，運用進化算法SPEA－2對DTLZ問題進行優(yōu)化，設定停止條件為t＝10 000，k＝3，｜xk｜＝5，交叉系數(shù)Pc為0.6，變異系數(shù)Pm為1／30，優(yōu)化仿真圖見圖7。

從圖6和圖7對比來看，改進算法保證了每個粒子之間的距離，淘汰了很多重復解和近似解，使最優(yōu)化解集中的粒子基本達到了均勻分布。觀察圖形得出，改進算法達到了預期目標，具有可行性。

圖6 改進算法對DTLZ問題的優(yōu)化仿真圖

圖7 SPEA－2算法對DTLZ問題的優(yōu)化仿真圖

為了評估多目標優(yōu)化算法得到的最優(yōu)解的均勻分布性能，優(yōu)化領域中一般采用Schott提出的間距指標（Spacing Metric）［7］進行衡量。該指標值越小，代表解分布越均勻。通過改進算法、NSGA－2算法和SPEA－2算法的對比實驗，得到的間距指標值如表4所示。

表4 多目標優(yōu)化算法的間距指標

從表4中的數(shù)值來看，改進算法的間距指標值最小，基本接近于0，即解近似于均勻分布，而NSGA－2算法和SPEA－2算法的間距指標值略大，所以，改進算法具有一定的優(yōu)越性。

通過仿真實驗可以看出，改進算法可對最優(yōu)解集映射到目標空間中粒子的解分布進行調控，即淘汰重疊粒子和近似粒子，使最終得到的粒子均勻分布，提升每個粒子在實際產(chǎn)品開發(fā)中的參考價值，從而減小了客戶的選擇壓力，縮短了產(chǎn)品的開發(fā)周期，提高了客戶的滿意度。

4 多目標優(yōu)化算法流程設計

本研究是針對客戶定制產(chǎn)品設計與優(yōu)化過程中的多目標優(yōu)化算法展開的，在產(chǎn)品的設計階段，需要考慮客戶的需求信息，將這些信息加以分類、整理和轉化，變成直觀的數(shù)學表達式。同時，還需要考慮企業(yè)的實際生產(chǎn)條件，如生產(chǎn)設備、技術能力、人員分配和生產(chǎn)資源等，在進行產(chǎn)品生產(chǎn)時，需要兼顧自身的生產(chǎn)實際和經(jīng)濟效益。圖8為所設計的多目標優(yōu)化算法的流程圖。

圖8 改進多目標優(yōu)化算法流程圖

仿真實驗結果說明了上述改進思路的可行性、可靠性和優(yōu)越性，這里運用改進算法對ZDT問題進行仿真實驗。

定義目標f1對目標f2的側重度系數(shù)為0.75，設定停止條件為t＝10 000，取c1＝c2＝1，設定目標間距矩陣為L＝［0.02 0.02］，改進算法對ZDT問題的優(yōu)化仿真圖見圖9。

從圖9中可以看出，粒子在側重度系數(shù)作用下進行了局部收斂，提高了優(yōu)化效率，同時保持了相互之間的間距，保證了最優(yōu)解的多樣性。

定義NSGA－2算法和SPEA－2算法的停止條件為t＝10 000，交叉系數(shù)Pc為0.8，變異系數(shù)Pm為1／30。將它們分別對ZDT問題進行優(yōu)化仿真，并計算出相關指標值與改進算法作對比分析，結果如表5所示。

圖9 改進算法對ZDT問題的優(yōu)化仿真圖

表5 多目標優(yōu)化算法對比實驗結果

從表5中可以看出，改進算法在優(yōu)化效率、收斂性和解的分布性方面均優(yōu)于NSGA－2算法和SPEA－2算法，正好符合本文的研究目標。

5 結語

本文對客戶定制產(chǎn)品設計與優(yōu)化項目中需要用到的多目標優(yōu)化算法進行了研究，在深入研究多目標優(yōu)化進化算法的基礎上，從優(yōu)化算法的優(yōu)化效率和最優(yōu)解的目標空間分布兩個方面對進化算法進行了改進，提高了多目標優(yōu)化進化算法的運行效率，精簡了最優(yōu)解的數(shù)量，降低了客戶的選擇壓力，同時，提高了每個最優(yōu)解的實際價值，方便客戶快速找到滿足自身需求的產(chǎn)品設計方案。研究結果對整個產(chǎn)品設計與優(yōu)化過程具有重要的意義。

［1］Deb K，Pratap A，Agarwal S，et al.A Fast and Elitist Multiobjective Genetic Algorithm：NSGA－II［J］.IEEE Trans.on Evolutionary Computation，2002，6（2）：182－197.

［2］王介生，王金城，王偉.基于粒子群算法的PID參數(shù)自整定［J］.控制與決策，2005，20（1）：73－76.

［3］方偉，孫俊，須文波.基于微分進化算子的量子粒子群優(yōu)化算法及應用［J］.系統(tǒng)仿真學報，2008，20（24）：6740－6744.

［4］許昆，李智勇.改進的量子粒子群多目標優(yōu)化算法［J］.計算機工程與設計，2009，30（1）：164－167.

［5］Deb K，Jain S.Running Performance Metrics for Evolutionary Multi－objective Optimization.Technical Report，No.2002004［R］.Kanpur：Indian Institute of Technology Kanpur，2002.

［6］Zitzler E，Laumanns M，Thiele L.SPEA2：Improving the Strength Pareto Evolutionary Algorithm［C］／／Giannakoglou K，Tsahalis D T，Papailiou K D，et al，eds.Evolutionary Methods for Design，Optimization and Control with Applications to Industrial Problems.Berlin：Springer－Verlag，2002：95－100.

［7］Sun Jun，F(xiàn)eng Bin，Xu Wenbo.A Global Search Strategy of Quantum－behaved Particle Swarm Optimization［C］／／IEEE Conference on Cybernetics and Intelligent Systems.Piscataway，NJ：IEEE Press，2004：111－116.