面向客戶定制產品開發的多目標優化算法設計

艾青松 許 強 劉 泉

武漢理工大學，武漢，430070

1 多目標優化進化算法概述

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

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

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

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

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

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

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

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

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

2 多目標優化進化算法的效率改進

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

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

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

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

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

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

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

圖1 4種側重度系數下的側重范圍

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

表2 4種側重范圍的邊界曲線函數

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

設側重區域為Ω，加入側重度系數λ后的粒子群的優化方程變為

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

我們運用改進算法對ZDT［5］問題進行優化，ZDT問題的數學方程如下：

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

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

圖2 測試問題ZDT的理想最優化曲面

圖3 λ＝0.90的優化仿真圖

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

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

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

圖4 NSGA－2算法對ZDT問題的優化仿真圖

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

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

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

3 多目標優化進化算法的解分布改進

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

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

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

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

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

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

圖5 優良個體的排序序列

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

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

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

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

下面采用改進算法對現今流行的測試問題DTLZ［5］進行優化仿真實驗，DTLZ數學表達式如下：

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

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

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

圖6 改進算法對DTLZ問題的優化仿真圖

圖7 SPEA－2算法對DTLZ問題的優化仿真圖

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

表4 多目標優化算法的間距指標

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

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

4 多目標優化算法流程設計

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

圖8 改進多目標優化算法流程圖

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

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

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

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

圖9 改進算法對ZDT問題的優化仿真圖

表5 多目標優化算法對比實驗結果

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

5 結語

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

［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參數自整定［J］.控制與決策，2005，20（1）：73－76.

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

［4］許昆，李智勇.改進的量子粒子群多目標優化算法［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，Feng 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.