本文關(guān)鍵詞：超多目標(biāo)演化算法及其應(yīng)用研究　出處：《中國科學(xué)技術(shù)大學(xué)》2017年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 元啟發(fā)式方法 演化算法 多目標(biāo)優(yōu)化 超多目標(biāo)優(yōu)化 隨機(jī)排序 推薦系統(tǒng)

【摘要】：在現(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 Opti-mization Problem)。作為一類重要的優(yōu)化問題,超多目標(biāo)優(yōu)化問題廣泛出現(xiàn)在各種現(xiàn)實世界的應(yīng)用中,如工程設(shè)計、空中交通控制、護(hù)士排班、汽車控制器優(yōu)化、供水組合規(guī)劃等等。演化算法(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ī)種群中的非支配解的比例急劇增加。這就導(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)演化方法分為以下幾類:基于松弛的支配定義的方法、基于多樣性的方法、基于聚集的方法、基于評價指標(biāo)的方法、基于參照點(diǎn)集的方法、基于偏好的方法和降維的方法。作為一種基于參照點(diǎn)集合的方法,兩檔案算法(Two Archive Algorithm,TAA)在環(huán)境選擇中使用了兩個檔案(解集合)來處理非支配解。具體來說,在每一代中,非支配解被分到兩個檔案中:收斂性檔案(Convergence Archive,CA)和多樣性檔案(Diversity Archive,DA)。這兩個檔案分別針對收斂性和多樣性。但是,隨著目標(biāo)個數(shù)的增加,收斂性檔案的大小會急劇增加,從而使得剩余給多樣性檔案的空間很小,嚴(yán)重影響了二者的平衡。同時,收斂性檔案的更新率很低,使得算法的收斂速度很慢。另外,多樣性檔案的更新策略導(dǎo)致算法偏向于遠(yuǎn)離收斂性檔案的收斂性很差的解,也會對算法的性能造成影響。在第二章中,作者針對兩檔案算法的主要缺陷,提出了改進(jìn)版的兩檔案算法(Improved Two Archive Algorithm,ITAA)。在改進(jìn)版算法中,基于懲罰的邊界交叉方法被用來作為CA的截斷選擇策略。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)函數(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ū)動,作者在第三章中提出了一個多指標(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)的平衡這一難點(diǎn)。實驗結(jié)果表明,提出的基于隨機(jī)排序的多指標(biāo)算法(Stochastic Ranking based multi-indicator Algorithm,SRA),在一系列的基準(zhǔn)測試問題上都顯示出很好的性能。最近幾年,爆炸式的數(shù)據(jù)已經(jīng)遠(yuǎn)遠(yuǎn)超出了用戶抽取有用信息的能力。電子商務(wù)平臺(如亞馬遜、阿里巴巴)以及內(nèi)容提供商(如Netflix,lastfm,和豆瓣)試圖推薦巨量的商品來滿足每個用戶的特定的興趣。為了處理這一問題,很多推薦系統(tǒng)應(yīng)運(yùn)而生,成為科研界的研究熱點(diǎn)。推薦系統(tǒng)可以被分為以下兩類:基于內(nèi)容的方法和基于協(xié)同過濾的方法�；趦�(nèi)容的方法利用自然信息建立用戶檔案或者物品檔案并進(jìn)行個性化推薦;協(xié)同過濾的方法則基于用戶的行為歷史進(jìn)行推薦。這里,一個用戶的行為可以是他的點(diǎ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項個性化推薦建模成了超多目標(biāo)優(yōu)化問題,并使用隨機(jī)排序多指標(biāo)算法來處理這一問題。在Movielens數(shù)據(jù)集上的實驗結(jié)果顯示,與其他三個超多目標(biāo)演化算法相比,提出的算法在收斂性和多樣性上都表現(xiàn)較好。
[Abstract]:In the real world , we often face optimization problems with multiple objectives called Multi - objective Optimization Problem . Among them , the multi - objective optimization problem with at least four objectives is often referred to informally as hypermultiple objective optimization problems . As a kind of important optimization problem , hyper - multi - objective optimization has been widely used in various real world applications , such as engineering design , air traffic control , nurse shift , car controller optimization , water supply combination planning , etc . However , with the increase of the number of objects , the size of the convergence file can be increased sharply , so that the space remaining to the diversity file is very small , which seriously affects the balance of the two . In the second chapter , the author proposes an improved Two Archive Algorithm ( ITAA ) for the main defects of the two - file algorithm . In the improved algorithm , the boundary crossing method based on penalty is used as a truncated selection strategy for CA . The PBI method provides ordering criteria for the solution in CA , so that the algorithm can intercept the CA more than a certain hour . In order to deal with this problem , the author puts forward a multi - index optimization algorithm to deal with the problem of multi - target optimization . In the fourth chapter , the author puts forward a multi - index optimization algorithm based on content - based method to deal with the problem of multi - target optimization .

【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 周育人,閔華清,許孝元,李元香;多目標(biāo)演化算法的收斂性研究[J];計算機(jī)學(xué)報;2004年10期

2 龔文引;謝丹;;針對本科生的演化算法教學(xué)探討[J];計算機(jī)時代;2012年07期

3 熊盛武,李元香,康立山,陳毓屏;用演化算法求解拋物型方程擴(kuò)散系數(shù)的識別問題[J];計算機(jī)學(xué)報;2000年03期

4 曾三友,康立山,丁立新;基于偏序關(guān)系的演化算法[J];計算機(jī)工程;2001年08期

5 周永華,毛宗源;基于混合雜交與間歇變異的演化算法[J];計算機(jī)工程與應(yīng)用;2003年06期

6 閆震宇,康立山,陳毓屏,付朋輝;一種新的多目標(biāo)演化算法——穩(wěn)態(tài)淘汰演化算法[J];武漢大學(xué)學(xué)報(理學(xué)版);2003年01期

7 王濤,李歧強(qiáng);基于空間收縮的并行演化算法[J];中國工程科學(xué);2003年03期

8 何國良,李元香;多個粒子參與交叉的一種動態(tài)演化算法[J];計算機(jī)工程與應(yīng)用;2004年08期

9 劉敏忠,鄒秀芬,康立山;一種基于偏序排名的高效的多目標(biāo)演化算法[J];小型微型計算機(jī)系統(tǒng);2004年12期

10 王龍奎,汪祖柱;關(guān)于多目標(biāo)演化算法的策略分析[J];安徽大學(xué)學(xué)報(自然科學(xué)版);2005年03期

相關(guān)會議論文 前3條

1 馮珊;李鋒;周凱波;;面向演化算法應(yīng)用的智能體系統(tǒng)建模與仿真研究[A];西部開發(fā)與系統(tǒng)工程——中國系統(tǒng)工程學(xué)會第12屆年會論文集[C];2002年

2 張文俊;謝曉鋒;馬君;;并行演化算法在半導(dǎo)體器件綜合中的應(yīng)用[A];2006年全國開放式分布與并行計算學(xué)術(shù)會議論文集（二）[C];2006年

3 謝柏橋;戴光明;鄭蔚;王劍文;;有指導(dǎo)的多目標(biāo)演化算法在區(qū)域星座設(shè)計中的應(yīng)用[A];中國宇航學(xué)會深空探測技術(shù)專業(yè)委員會第四屆學(xué)術(shù)年會論文集[C];2007年

相關(guān)博士學(xué)位論文 前10條

1 俞揚(yáng);演化計算理論分析與學(xué)習(xí)算法的研究[D];南京大學(xué);2011年

2 庫俊華;自適應(yīng)差分演化算法及其應(yīng)用研究[D];中國地質(zhì)大學(xué);2015年

3 彭雪;演化算法和蟻群算法的性能分析[D];華南理工大學(xué);2016年

4 李丙棟;超多目標(biāo)演化算法及其應(yīng)用研究[D];中國科學(xué)技術(shù)大學(xué);2017年

5 陸曉芬;基于代理模型的實值演化算法研究[D];中國科學(xué)技術(shù)大學(xué);2017年

6 彭晟;演化算法的靜電場論模型[D];武漢大學(xué);2011年

7 陳明;演化算法漸近行為的若干問題研究[D];武漢大學(xué);2012年

8 彭飛;實值演化算法投資組合研究[D];中國科學(xué)技術(shù)大學(xué);2011年

9 萬書振;動態(tài)環(huán)境下差分演化算法研究與應(yīng)用[D];武漢理工大學(xué);2012年

10 魏波;交互式與自適應(yīng)演化算法研究[D];武漢大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 楊穎;一種多差分向量的自適應(yīng)差分演化算法[D];浙江大學(xué);2015年

2 陳偉;隊伍演化算法及其在微波電路設(shè)計中的應(yīng)用[D];杭州電子科技大學(xué);2015年

3 吳昊;多群體并行演化算法的研究[D];南京郵電大學(xué);2015年

4 邢雪;基于Pi演算的關(guān)系演化算法的研究與實現(xiàn)[D];吉林大學(xué);2016年

5 黃星;遺傳遞增演化算法配筋優(yōu)化設(shè)計[D];湖南大學(xué);2016年

6 溫志超;基于演化算法及改進(jìn)詞袋模型的病蟲害分類識別技術(shù)研究[D];華南農(nóng)業(yè)大學(xué);2016年

7 左磊;改進(jìn)的差分演化算法研究及其應(yīng)用[D];華南農(nóng)業(yè)大學(xué);2016年

8 張盛鑫;基于新型變異與交叉算子的差分演化算法研究[D];暨南大學(xué);2016年

9 陳澤豐;多目標(biāo)演化算法的性能改進(jìn)研究[D];華南理工大學(xué);2016年

10 彭超;差分演化算法的評估、改進(jìn)與應(yīng)用研究[D];大連海事大學(xué);2016年

，

本文編號：1402136