超多目標(biāo)演化算法及其應(yīng)用研究.pdf

1、在現(xiàn)實世界中，我們經(jīng)常面對具有多個目標(biāo)的優(yōu)化問題，這類問題被稱為多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem)。其中，至少有四個目標(biāo)的多目標(biāo)優(yōu)化問題通常被非正式地稱為超多目標(biāo)優(yōu)化問題(Many-objective Optimization Problem)。作為一類重要的優(yōu)化問題，超多目標(biāo)優(yōu)化問題廣泛出現(xiàn)在各種現(xiàn)實世界的應(yīng)用中，如工程設(shè)計、空中交通控制、護(hù)士排班、汽車控制器優(yōu)化、供水組合規(guī)劃等

2、等。演化算法(Evolutionary Algorithm)作為一類基于種群的黑盒搜索/優(yōu)化方法，不需要對問題的連續(xù)性和可微性做假設(shè)。這類算法非常適合處理具有多個目標(biāo)的復(fù)雜優(yōu)化問題。在過去的幾十年里，研究人員提出一系列的多目標(biāo)演化算法。但是，有研究表明，基于傳統(tǒng)的帕累托支配的方法在超多目標(biāo)優(yōu)化問題（目標(biāo)數(shù)大于3的多目標(biāo)優(yōu)化問題）上會發(fā)生比較嚴(yán)重的性能退化。發(fā)生這種現(xiàn)象的主要原因在于隨著目標(biāo)空間維度的增加，隨機(jī)種群中的非支配解的比例急劇增

3、加。這就導(dǎo)致基于支配定義的主要的選擇標(biāo)準(zhǔn)失去效果，而基于多樣性的次要選擇標(biāo)準(zhǔn)在環(huán)境選擇階段起主導(dǎo)作用。次要選擇標(biāo)準(zhǔn)會導(dǎo)致種群發(fā)散地分布在目標(biāo)空間，并遠(yuǎn)離帕累托前沿。因此這類算法在處理超多目標(biāo)優(yōu)化問題時，收斂性會急劇降低，整個種群與帕累托最優(yōu)前沿相去甚遠(yuǎn)。
　　為了處理超多目標(biāo)優(yōu)化問題，研究者們提出了一系列的超多目標(biāo)演化算法?；谒惴ǖ暮诵乃枷?，我們將超多目標(biāo)演化方法分為以下幾類:基于松弛的支配定義的方法、基于多樣性的方法、基于聚集

4、的方法、基于評價指標(biāo)的方法、基于參照點集的方法、基于偏好的方法和降維的方法。作為一種基于參照點集合的方法，兩檔案算法(Two Archive Algorithm，TAA)在環(huán)境選擇中使用了兩個檔案（解集合）來處理非支配解。具體來說，在每一代中，非支配解被分到兩個檔案中:收斂性檔案(Convergence Archive，CA)和多樣性檔案(Diversity Archive，DA)。這兩個檔案分別針對收斂性和多樣性。但是，隨著目標(biāo)個數(shù)的

5、增加，收斂性檔案的大小會急劇增加，從而使得剩余給多樣性檔案的空間很小，嚴(yán)重影響了二者的平衡。同時，收斂性檔案的更新率很低，使得算法的收斂速度很慢。另外，多樣性檔案的更新策略導(dǎo)致算法偏向于遠(yuǎn)離收斂性檔案的收斂性很差的解，也會對算法的性能造成影響。在第二章中，作者針對兩檔案算法的主要缺陷，提出了改進(jìn)版的兩檔案算法(Improved Two Archive Algorithm，ITAA)。在改進(jìn)版算法中，基于懲罰的邊界交叉方法被用來作為CA的

6、截斷選擇策略。PBI方法為CA中的解提供了排序標(biāo)準(zhǔn)，使得算法可以在CA超過一定大小時對CA進(jìn)行截斷。此外，改進(jìn)版算法使用基于平移的密度估計對DA進(jìn)行排序，以避免多樣性檔案嚴(yán)重滯后于整個種群的收斂。在基準(zhǔn)測試集上的實驗結(jié)果顯示，在大部分測試樣例上，改進(jìn)版的算法在收斂性和多樣性上都優(yōu)于原版算法。
　　由于最終的解集合是根據(jù)評估指標(biāo)進(jìn)行評價的，所以一個處理超多目標(biāo)優(yōu)化問題的很直觀的方法是利用解集合的指標(biāo)值來引導(dǎo)搜索方向。但是，單個指標(biāo)函

7、數(shù)很有可能具有偏向性，將搜索方向引導(dǎo)至帕累托前沿的某個子區(qū)域。以一個基于I∈+指標(biāo)的算法IBEA為例，在處理超多目標(biāo)優(yōu)化問題時，它很難保持種群的多樣性。這種現(xiàn)象說明，I∈+指標(biāo)相對多樣性而言更加偏好收斂性。其他指標(biāo)（如擁塞距離、平移密度估計等等.）很可能偏好多樣性更好的解。由于不同的指標(biāo)可能具有不同的偏向性并且可能相互補(bǔ)充，因此，在環(huán)境選擇階段使用多個指標(biāo)而非單個指標(biāo)可能會得到一個更好的算法。由這一思想驅(qū)動，作者在第三章中提出了一個多指

8、標(biāo)優(yōu)化算法來處理超多目標(biāo)優(yōu)化問題。特別地，設(shè)計這樣一個算法的關(guān)鍵問題在于如何基于很有可能并不一致的多個指標(biāo)來進(jìn)行環(huán)境選擇。有研究表明，隨機(jī)排序在處理約束優(yōu)化中的適應(yīng)度和約束違反量之間的沖突方面表現(xiàn)突出。因此，作者采用了隨機(jī)排序技術(shù)來處理多指標(biāo)的平衡這一難點。實驗結(jié)果表明，提出的基于隨機(jī)排序的多指標(biāo)算法(Stochastic Rankingbased multi-indicator Algorithm，SRA)，在一系列的基準(zhǔn)測試問題上都

9、顯示出很好的性能。
　　最近幾年，爆炸式的數(shù)據(jù)已經(jīng)遠(yuǎn)遠(yuǎn)超出了用戶抽取有用信息的能力。電子商務(wù)平臺（如亞馬遜、阿里巴巴）以及內(nèi)容提供商（如Netflix，lastfm，和豆瓣）試圖推薦巨量的商品來滿足每個用戶的特定的興趣。為了處理這一問題，很多推薦系統(tǒng)應(yīng)運(yùn)而生，成為科研界的研究熱點。推薦系統(tǒng)可以被分為以下兩類:基于內(nèi)容的方法和基于協(xié)同過濾的方法?；趦?nèi)容的方法利用自然信息建立用戶檔案或者物品檔案并進(jìn)行個性化推薦;協(xié)同過濾的方法則基于

10、用戶的行為歷史進(jìn)行推薦。這里，一個用戶的行為可以是他的點擊、評分、購買記錄以及對于商品或者服務(wù)的評論。顯然，僅僅考慮推薦系統(tǒng)的準(zhǔn)確性對于推薦系統(tǒng)的評價是不夠全面的。其他性能指標(biāo)，例如多樣性、新穎性、覆蓋率、偶然性也應(yīng)該被考慮在內(nèi)。這些看起來沖突的不同的性能指標(biāo)使得推薦任務(wù)變?yōu)橐粋€多目標(biāo)優(yōu)化問題。盡管在多目標(biāo)推薦系統(tǒng)中已經(jīng)有很多研究工作，但是，尚無工作考慮基于超多目標(biāo)優(yōu)化的個性化推薦（超多三個目標(biāo)的）。在本文的第四章中，作者將前N項個性化