一種基于有限K近鄰的強(qiáng)度帕累托進(jìn)化算法

姜宏 楊孟飛 于廣良 魏夢(mèng)捷

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

(3 空間智能控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190)

一種基于有限K近鄰的強(qiáng)度帕累托進(jìn)化算法

姜宏1，3楊孟飛2,3于廣良1,3魏夢(mèng)捷1,3

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

(3 空間智能控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190)

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

軟硬件協(xié)同設(shè)計(jì)；多目標(biāo)優(yōu)化；帕累托最優(yōu)；強(qiáng)度帕累托進(jìn)化算法；星載計(jì)算機(jī)；航天器控制

1 引言

隨著我國(guó)航天技術(shù)的飛速發(fā)展，航天器控制計(jì)算機(jī)呈現(xiàn)出日益小型化、輕量化、集成化和低能耗的趨勢(shì)。為順應(yīng)這一趨勢(shì)，必須在滿足功能和性能的前提下，使系統(tǒng)的體積更小、質(zhì)量更輕、功耗更低。在這些指標(biāo)的嚴(yán)格約束下，將軟硬件分開設(shè)計(jì)的傳統(tǒng)方法將無(wú)法滿足要求，因此本文在計(jì)算機(jī)系統(tǒng)設(shè)計(jì)中采用了軟硬件協(xié)同設(shè)計(jì)[1]方法。

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

2 多目標(biāo)優(yōu)化和帕累托最優(yōu)

1896年，經(jīng)濟(jì)學(xué)家V.Pareto首先在經(jīng)濟(jì)平衡的研究中提出了多目標(biāo)優(yōu)化問(wèn)題，并引入了被稱為帕累托最優(yōu)的概念[7]。多目標(biāo)優(yōu)化包含最小化和最大化兩類問(wèn)題，這兩類問(wèn)題是可以相互轉(zhuǎn)化的，本文所涉及的最小化問(wèn)題的多目標(biāo)模型可表示為

(1)

式中X=(x1,x2,…,xn)為決策空間中所有滿足約束的可行解組成的集合，n為構(gòu)成可行解的決策變量的個(gè)數(shù)；F(X)=(f1(X),f2(X),…,fm(X))為對(duì)應(yīng)于X的多目標(biāo)函數(shù)向量，m為目標(biāo)數(shù)；p和q是兩類約束的個(gè)數(shù)?；谀Ｐ?1)可以得到帕累托支配的概念如下。

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

則稱X1支配X2，記作：X1PX2。不被其他解支配的解稱為非支配解或帕累托最優(yōu)，所有非支配解組成的集合稱為帕累托最優(yōu)集。與帕累托最優(yōu)集所對(duì)應(yīng)的多目標(biāo)值的集合稱為帕累托前沿[8]。

本文對(duì)優(yōu)化后獲得的近似帕累托前沿(ParetoFopt)進(jìn)行評(píng)價(jià)的指標(biāo)有兩個(gè)：收斂的距離指標(biāo)Υ和分布的多樣性指標(biāo)Δ[9](見圖1)。圖1是以雙目標(biāo)優(yōu)化為例，不同優(yōu)化問(wèn)題的帕累托前沿和優(yōu)化后獲得的近似帕累托前沿會(huì)與圖1存在差異。

圖1 距離指標(biāo)和多樣性指標(biāo)Fig.1 Distance metric and diversity metric

Υ的求解方法是從某個(gè)評(píng)測(cè)函數(shù)的帕累托前沿(ParetoFstd)上以大致相同的間隔取出C1=500個(gè)點(diǎn)，構(gòu)成標(biāo)準(zhǔn)集S=(S1,S2,…,SC1)，然后計(jì)算ParetoFopt上的每個(gè)點(diǎn)到達(dá)S的最短歐氏距離的平均值：

(2)

式中C2為ParetoFopt上的點(diǎn)個(gè)數(shù)；函數(shù)dist表示兩點(diǎn)間的歐氏距離。

指標(biāo)Δ的計(jì)算公式為

(3)

3 基于SPEA2的改進(jìn)算法

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

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

輸出：非支配集A。

步驟6：雜交和變異。對(duì)雜交池中的所有個(gè)體執(zhí)行雜交和變異操作，并將處理后的種群設(shè)定為Pt+1，對(duì)當(dāng)前迭代次數(shù)t加1后再回到步驟2。

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

3.1 原始K近鄰方法

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

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

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

3.2 有限K近鄰方法

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

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

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

3.3 時(shí)間復(fù)雜度分析

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

1)K近鄰策略迭代l次：由于每次近鄰計(jì)算最多要比較M2個(gè)距離值，則l次近鄰計(jì)算需要比較最多l(xiāng)M2個(gè)距離值，因此時(shí)間復(fù)雜度為O(lM2)。

將3個(gè)步驟的時(shí)間復(fù)雜度綜合起來(lái)，可知改進(jìn)后的環(huán)境選擇環(huán)節(jié)的時(shí)間復(fù)雜度為O(lM2)，與原方法相比優(yōu)勢(shì)明顯。

由于新算法在適應(yīng)度值分配環(huán)節(jié)的時(shí)間復(fù)雜度依然為O(M2logM)，因此整個(gè)算法的最差時(shí)間復(fù)雜度由原來(lái)的O(M3)下降到O(max(l,logM)M2)。

4 數(shù)值試驗(yàn)

4.1 收斂性和多樣性試驗(yàn)

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

表1 測(cè)試函數(shù)

續(xù)表1

這些測(cè)試函數(shù)是從事多目標(biāo)優(yōu)化算法研究的學(xué)者所公認(rèn)的試驗(yàn)基準(zhǔn)函數(shù)，能夠衡量一個(gè)算法的收斂性優(yōu)劣。接下來(lái)，對(duì)試驗(yàn)的參數(shù)進(jìn)行了設(shè)置。將染色體編碼方式規(guī)定為實(shí)數(shù)編碼，將雜交概率設(shè)置為0.9，變異概率設(shè)置為1/n(n是決策變量的個(gè)數(shù))，將雜交和變異算子的分布指數(shù)全都指定為20.0，設(shè)定種群大小為100，并限定進(jìn)化的子代數(shù)量為250代。

上述準(zhǔn)備工作完成之后，本文在VisualStudio2010環(huán)境下編寫C++程序?qū)崿F(xiàn)了SPEA2和改進(jìn)算法(令常數(shù)l=3，r=8)，并且將二者都重復(fù)運(yùn)行了25 000次，根據(jù)公式(2)和(3)求得 Υ和Δ，然后計(jì)算平均值和方差，最后將獲得的數(shù)據(jù)和NSGAII的結(jié)果(參考文獻(xiàn)[9]且參數(shù)設(shè)置和本文相同)放在一起進(jìn)行對(duì)比(見表2和表3)。

表2 收斂指標(biāo)Υ的均值和方差

表3 多樣性指標(biāo)Δ的均值和方差

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

4.2 計(jì)算時(shí)間試驗(yàn)

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

表4 計(jì)算時(shí)間比較

觀察表4可發(fā)現(xiàn)，兩種算法僅僅在ZDT4問(wèn)題上的運(yùn)行結(jié)果最為接近，而其他7項(xiàng)測(cè)試的運(yùn)行結(jié)果差距都比較大。表4中數(shù)據(jù)所呈現(xiàn)的變化規(guī)律是：SPEA2算法的計(jì)算時(shí)間隨著問(wèn)題規(guī)模的增長(zhǎng)比新算法要大很多，其中ZDT6的試驗(yàn)結(jié)果最能說(shuō)明這一點(diǎn)。

5 結(jié)束語(yǔ)

本文針對(duì)SPEA2算法在環(huán)境選擇環(huán)節(jié)的計(jì)算時(shí)間復(fù)雜度過(guò)大的問(wèn)題提出了一種改進(jìn)算法。新的算法采用有限K近鄰策略代替了原有的K近鄰策略，減少了總的比較次數(shù)，降低了時(shí)間復(fù)雜度。在收斂性和多樣性試驗(yàn)階段，選取8個(gè)測(cè)試函數(shù)對(duì)NSGAII、SPEA2和本文算法進(jìn)行了對(duì)比。在計(jì)算時(shí)間試驗(yàn)階段，按照種群大小分別統(tǒng)計(jì)新算法和原算法的運(yùn)行時(shí)間。試驗(yàn)結(jié)果表明：本文提出的SPEA2改進(jìn)算法不僅在收斂性和分布多樣性上優(yōu)于NSGAII和SPEA2，而且計(jì)算速度快于原始的SPEA2算法。本文算法的上述優(yōu)點(diǎn)將為航天器控制計(jì)算機(jī)的軟硬件協(xié)同設(shè)計(jì)工作創(chuàng)造非常有利的條件。

[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整定的衛(wèi)星姿態(tài)控制研究 [J]. 中國(guó)空間科學(xué)技術(shù), 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] 林銼云, 董加禮. 多目標(biāo)優(yōu)化的方法與理論 [M]. 長(zhǎng)春: 吉林教育出版社, 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年獲北京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)碩士學(xué)位，現(xiàn)為北京控制工程研究所計(jì)算機(jī)控制專業(yè)博士研究生。研究領(lǐng)域是航天器控制計(jì)算機(jī)的軟硬件協(xié)同設(shè)計(jì)。

(編輯：王曉宇)

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

國(guó)家自然科學(xué)基金(91118007)資助項(xiàng)目

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

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