一種基于有限K近鄰的強度帕累托進化算法

姜宏 楊孟飛 于廣良 魏夢捷

(1 北京控制工程研究所，北京 100190) (2 中國空間技術研究院，北京 100094)

(3 空間智能控制技術重點實驗室，北京 100190)

一種基于有限K近鄰的強度帕累托進化算法

姜宏1，3楊孟飛2,3于廣良1,3魏夢捷1,3

(1 北京控制工程研究所，北京 100190) (2 中國空間技術研究院，北京 100094)

(3 空間智能控制技術重點實驗室，北京 100190)

在航天器控制計算機的軟硬件協同設計過程中，需要解決多目標優化問題。當前的強度帕累托進化算法在求解高維多目標優化問題時具有優勢，但是在環境選擇階段的計算時間復雜度仍然較大。文章針對這一問題，提出了一種改進算法。新的算法采用有限K近鄰方法，減少了原算法中K近鄰策略的比較次數，使時間復雜度由O(M3)下降為O(max(l,logM)M2)。試驗結果表明文中算法的計算速度更快，并且具有更優的收斂性和分布多樣性特征。

軟硬件協同設計；多目標優化；帕累托最優；強度帕累托進化算法；星載計算機；航天器控制

1 引言

隨著我國航天技術的飛速發展，航天器控制計算機呈現出日益小型化、輕量化、集成化和低能耗的趨勢。為順應這一趨勢，必須在滿足功能和性能的前提下，使系統的體積更小、質量更輕、功耗更低。在這些指標的嚴格約束下，將軟硬件分開設計的傳統方法將無法滿足要求，因此本文在計算機系統設計中采用了軟硬件協同設計[1]方法。

在協同設計的軟硬件劃分過程中,多目標優化是必須要解決的關鍵問題。對于規模較小的多目標優化問題，可以采用確定性算法求出精確解[2]，而對于規模較大的情形則只能采用隨機算法得到近似解。軟硬件協同設計中用到的隨機算法主要是多目標優化進化算法，與其他進化算法[3]相比，區別在于適應度值分配和環境選擇的方法不同。根據適應度值分配和環境選擇的差異，多目標進化算法又進一步分化為快速精英非支配排序遺傳算法(NSGA II[4])、改進的強度帕累托進化算法(SPEA2[5])等。由于SPEA2在應對多維目標時更有優勢，因此本文基于SPEA2算法展開研究。

2 多目標優化和帕累托最優

1896年，經濟學家V.Pareto首先在經濟平衡的研究中提出了多目標優化問題，并引入了被稱為帕累托最優的概念[7]。多目標優化包含最小化和最大化兩類問題，這兩類問題是可以相互轉化的，本文所涉及的最小化問題的多目標模型可表示為

(1)

式中X=(x1,x2,…,xn)為決策空間中所有滿足約束的可行解組成的集合，n為構成可行解的決策變量的個數；F(X)=(f1(X),f2(X),…,fm(X))為對應于X的多目標函數向量，m為目標數；p和q是兩類約束的個數。基于模型(1)可以得到帕累托支配的概念如下。

定義1：在X中任取兩個解X1和X2，若：

則稱X1支配X2，記作：X1PX2。不被其他解支配的解稱為非支配解或帕累托最優，所有非支配解組成的集合稱為帕累托最優集。與帕累托最優集所對應的多目標值的集合稱為帕累托前沿[8]。

本文對優化后獲得的近似帕累托前沿(ParetoFopt)進行評價的指標有兩個：收斂的距離指標Υ和分布的多樣性指標Δ[9](見圖1)。圖1是以雙目標優化為例，不同優化問題的帕累托前沿和優化后獲得的近似帕累托前沿會與圖1存在差異。

圖1 距離指標和多樣性指標Fig.1 Distance metric and diversity metric

Υ的求解方法是從某個評測函數的帕累托前沿(ParetoFstd)上以大致相同的間隔取出C1=500個點，構成標準集S=(S1,S2,…,SC1)，然后計算ParetoFopt上的每個點到達S的最短歐氏距離的平均值：

(2)

式中C2為ParetoFopt上的點個數；函數dist表示兩點間的歐氏距離。

指標Δ的計算公式為

(3)

3 基于SPEA2的改進算法

由Eckart Zitzler等人提出的SPEA2算法為：

輸入：種群大小N、檔案大小N、迭代的最大次數T。

輸出：非支配集A。

步驟6：雜交和變異。對雜交池中的所有個體執行雜交和變異操作，并將處理后的種群設定為Pt+1，對當前迭代次數t加1后再回到步驟2。

在上述步驟中，適應度值分配和環境選擇的時間復雜度分別為O(M2logM)和O(M3)，因此環境選擇環節是降低算法計算時間的關鍵所在。SPEA2在環境選擇階段采用的是K近鄰方法。該方法雖然降低了邊界點被錯誤刪除的可能性，提高了結果的收斂性和分布多樣性，但是時間開銷也相應增大。為了彌補SPEA2算法的這一不足，本文算法重點對步驟3加以改進，具體做法是在原始K近鄰策略的基礎上提出了有限K近鄰方法。

3.1 原始K近鄰方法

在SPEA2的環境選擇過程中，需要對雜交、變異后的種群個體和檔案種群中的個體進行篩選，以控制個體總數不超過規定的上限值。當種群中的個體數量超出上限時，則應對多余的個體執行刪減操作。若多余的個體是支配解，則只需挑選出與最近鄰距離最小的個體予以剔除，若多余的個體是非支配解，則在原算法的步驟3中按照如下策略選擇待刪除個體。

事實上，在算法迭代過程中，圖2(a)中的極端情況是很常見的，圖2(b)中的情況雖然很難遇到但接近于此的情形很多，正是這兩個原因使得K近鄰方法在實現時的時間復雜度較高。

圖2 K近鄰搜索中的兩種極端情況Fig.2 Two extreme cases of K-nearest neighbor method

3.2 有限K近鄰方法

為減少K近鄰方法的計算時間，本文提出了如下的有限K近鄰策略：

步驟1：按照前文所述的K近鄰方法迭代l次(即最多搜索到第l個近鄰，l為預設的常數)，若找到的是惟一的個體，則可直接將該個體刪除，否則將剩余的個體組成集合SKNN，然后轉到步驟2。

步驟4：若W值最小的個體有多個，則從其中隨機挑選一個予以刪除，若只存在惟一的個體，則直接將其刪除即可。

3.3 時間復雜度分析

由前文可知，受制于SPEA2算法的K近鄰環境選擇策略，算法的最差計算時間復雜度只能達到O(M3)。當用有限K近鄰策略對原策略進行替換后，新算法在環境選擇環節的時間復雜度按如下3部分進行分析：

1)K近鄰策略迭代l次：由于每次近鄰計算最多要比較M2個距離值，則l次近鄰計算需要比較最多lM2個距離值，因此時間復雜度為O(lM2)。

將3個步驟的時間復雜度綜合起來，可知改進后的環境選擇環節的時間復雜度為O(lM2)，與原方法相比優勢明顯。

由于新算法在適應度值分配環節的時間復雜度依然為O(M2logM)，因此整個算法的最差時間復雜度由原來的O(M3)下降到O(max(l,logM)M2)。

4 數值試驗

4.1 收斂性和多樣性試驗

根據前文所述，本文算法的時間復雜度相比SPEA2算法有了明顯的改善，但是收斂的距離指標和分布的多樣性指標卻無法直接由分析得到結論，必須通過試驗加以驗證。在試驗之前，首先選定了8個測試函數[9]：Schaffer研究的測試函數(SCH)、Fonseca和Fleming設計的測試函數(FON)、Kursawe的測試函數(KUR)以及Zitzler提出的5個測試函數(ZDT1、ZDT2、ZDT3、ZDT4和ZDT6)如表1所示。

表1 測試函數

續表1

這些測試函數是從事多目標優化算法研究的學者所公認的試驗基準函數，能夠衡量一個算法的收斂性優劣。接下來，對試驗的參數進行了設置。將染色體編碼方式規定為實數編碼，將雜交概率設置為0.9，變異概率設置為1/n(n是決策變量的個數)，將雜交和變異算子的分布指數全都指定為20.0，設定種群大小為100，并限定進化的子代數量為250代。

上述準備工作完成之后，本文在VisualStudio2010環境下編寫C++程序實現了SPEA2和改進算法(令常數l=3，r=8)，并且將二者都重復運行了25 000次，根據公式(2)和(3)求得 Υ和Δ，然后計算平均值和方差，最后將獲得的數據和NSGAII的結果(參考文獻[9]且參數設置和本文相同)放在一起進行對比(見表2和表3)。

表2 收斂指標Υ的均值和方差

表3 多樣性指標Δ的均值和方差

觀察表2可以發現，改進后的SPEA2算法在收斂性方面，不論是均值和方差都普遍好于NSGAII算法；與SPEA2算法相比，僅僅在ZDT2和ZDT3這兩個問題的收斂均值上稍遜，在其他6個問題上的均值和方差全都占優，因此總體上優于SPEA2算法。再通過表3可知，改進后的SPEA2算法在ZDT4問題的多樣性均值和方差略輸于NSGAII算法，而在其他7個問題的表現都強于NSGAII，因而總體上比NSGAII的分布多樣性更好；再與SPEA2算法相比，新算法只是在ZDT6問題上的均值較差，其他問題的均值都較好，因此在分布多樣性上也優于SPEA2，但是由于方差較大，波動更大一些。

4.2 計算時間試驗

計算時間試驗所挑選的測試函數與第一部分試驗完全一樣。在參數設置上，為了突顯改進后SPEA2和SPEA2算法在計算時間方面的差異，將種群大小分別設定為100、200、300,400和500，其他參數保持不變。算法運行的環境是：2.66GHz主頻的雙核CPU、2GB內存，以及WIN7操作系統，最后按種群大小得到的數據如表4所示。

表4 計算時間比較

觀察表4可發現，兩種算法僅僅在ZDT4問題上的運行結果最為接近，而其他7項測試的運行結果差距都比較大。表4中數據所呈現的變化規律是：SPEA2算法的計算時間隨著問題規模的增長比新算法要大很多，其中ZDT6的試驗結果最能說明這一點。

5 結束語

本文針對SPEA2算法在環境選擇環節的計算時間復雜度過大的問題提出了一種改進算法。新的算法采用有限K近鄰策略代替了原有的K近鄰策略，減少了總的比較次數，降低了時間復雜度。在收斂性和多樣性試驗階段，選取8個測試函數對NSGAII、SPEA2和本文算法進行了對比。在計算時間試驗階段，按照種群大小分別統計新算法和原算法的運行時間。試驗結果表明：本文提出的SPEA2改進算法不僅在收斂性和分布多樣性上優于NSGAII和SPEA2，而且計算速度快于原始的SPEA2算法。本文算法的上述優點將為航天器控制計算機的軟硬件協同設計工作創造非常有利的條件。

[1] FRANK D W, PURVIS M K. Hardware/software co-design: a perspective [C]. IEEE 13thInternational Conference on Software Engineering, C.A.,USA, IEEE, 1991: 344-352.

[2] JIANG HONG, YANG MENGFEI, ZHANG SHAOLIN, et al. A new method for multi-objective optimization problem [C]. 2013 IEEE 4thInternational Conference on Electronics Information and Emergency Communication, Beijing,IEEE, 2013: 209-212.

[3] 李源, 吳宏悅, 吳杰. 基于遺傳算法PID整定的衛星姿態控制研究 [J]. 中國空間科學技術, 2007, 27(4): 66-71.

LI YUAN, WU HONGYUE, WU JIE. Genetic algorithm PID self-tuning based on the satellite attitude control [J]. Chinese Space Science and Technology, 2007, 27(4): 66-71.

[4] COELLO CAC, PULIDO GT. Multiobjective structural optimization using a microgenetic algorithm [J]. Structural and Multidisciplinary Optimization, 2005,30(5): 388-403.

[5] ECKART ZITZLER, MARCO LAUMANNS, LOTHAR THIELE. SPEA2: improving the strength Pareto evolutionary algorithm TIK-Report 103[R].Zurich:Swiss Federal Institute of Technology, 2001: 1-21.

[6] ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach [J]. IEEE Transactions on Evolutionary Computing,1999, 3(4): 257-271.

[7] 林銼云, 董加禮. 多目標優化的方法與理論 [M]. 長春: 吉林教育出版社, 1992:8-9.

[8] VIDA KIANZAD, SHUVRA S, BHATTACHARYYA. CHARMED: a multi-objective co-synthesis framework for multi-mode embedded systems [C]. 15thIEEE International Conference on Applications-Specific Systems, Architecture and Processors, Texas,IEEE, 2004: 28-40.

[9] KALYANMOY DEB, AMRIT PRATAP, SAMEER AGARWAL,et al. A fast and elitist multiobjective genetic algorithm: NSGA-II [J]. IEEE Transaction on Evolutionary Computing,2002,6(2): 182-197.

[10] DEB K.Multiobjective optimization using evolutionary algorithms [M].New York: Wiley, 2001: 338-375.

姜 宏 1975年生，2011年獲北京航空航天大學計算機科學與技術專業碩士學位，現為北京控制工程研究所計算機控制專業博士研究生。研究領域是航天器控制計算機的軟硬件協同設計。

(編輯：王曉宇)

An Improved Strength Pareto Evolutionary Algorithm Based on the Limited K-Nearest Neighbor Method

JIANG Hong1,3YANG Mengfei2,3YU Guangliang1,3WEI Mengjie1,3

(1 Beijing Institute of Control Engineering, Beijing 100190)

(2 China Academy of Space Technology, Beijing 100094)

(3 Science and Technology on Space Intelligent Control Laboratory, Beijing 100190)

In the process of Hardware/software co-design of spacecraft control computers, the multi-objective optimization is a key problem. The current strength Pareto evolutionary algorithm has some advantages in solving high-dimensional multi-objective optimization problems, but the computing time-complexity during the step of environmental selection is still very large. Aiming at this point, an improved algorithm was proposed. With the finite K-nearest neighbor method, new algorithm reduces the number of comparisons to lower the time-complexity fromO(M3) down toO(max(l, logM)M2). The experimental results show that the proposed algorithm not only improves the running speed, but also acquires better convergence and distribution diversity than the original one.

Hardware/software co-design; Multi-objective optimization; Pareto optimization;Strength Pareto evolutionary algorithm;On-board computer;Spacecraft control

國家自然科學基金(91118007)資助項目

2014-11-15。收修改稿日期：2015-01-08

10.3780/j.issn.1000-758X.2015.02.007