子集選擇問題旨在從全集中挑選一個子集,使預(yù)先給定的評價指標(biāo)達(dá)到最優(yōu)。其在機(jī)器學(xué)習(xí)等領(lǐng)域有廣泛應(yīng)用,例如模型選擇、特征選擇、樣本選擇等任務(wù)都可歸結(jié)為子集選擇問題。子集選擇是經(jīng)典的NP難問題,因此研究者不斷地在尋找適合該類問題的高效近似算法,例如貪心算法被證明在子模函數(shù)子集選擇問題上具有常數(shù)近似率,也成為最為常用的子集選擇近似算法。最近,研究者提出一種基于雙目標(biāo)優(yōu)化的帕累托優(yōu)化算法,并用于子集選擇問題,形成子集選擇算法POSS。POSS被證明具有優(yōu)于貪心算法的逼近能力,受到了關(guān)注。然而,POSS算法存在求解效率不高、求解約束單一、求解環(huán)境無噪的限制。為了更好的求解實(shí)際問題中面臨的子集選擇問題,本文基于POSS逼近能力的優(yōu)勢,從求解效率、約束類型、環(huán)境噪音三方面進(jìn)行拓展研究,取得了如下結(jié)果:1.在求解效率方面,針對雙目標(biāo)優(yōu)化過程不區(qū)分階段性導(dǎo)致優(yōu)化過程缺乏著重點(diǎn),提出了貫序分解方法,將其優(yōu)化過程分解為多個階段,在不同的時間著重優(yōu)化其中一個階段,并在多個問題上進(jìn)行了時間復(fù)雜度分析,發(fā)現(xiàn)該方法可獲得O（n）的加速;針對POSS算法順序執(zhí)行而難以利用現(xiàn)有多核計算設(shè)備加速的不足,提出了異步并行化方法... 

【文章來源】：南京大學(xué)江蘇省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：71 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖３－３：?ｗ５ａ數(shù)據(jù)集（７０００樣本，５０００個特征）??（算法成果已經(jīng)發(fā)表在ＩＪＣＡＩ－１６上，如需更詳細(xì)的結(jié)果，可以參考已經(jīng)發(fā)表的??論文［３Ｇ］）

圖４－２：傳感器放置（ｅｎｔｒｏｐｙ：越大越好）??近似

圖４－３：影響力傳播（ｓｐｒｅａｄ：越大越好）??

【參考文獻(xiàn)】：
期刊論文
[1]Variable solution structure can be helpful in evolutionary optimization[J]. QIAN Chao,YU Yang,ZHOU Zhi-Hua.  Science China（Information Sciences）. 2015(11)



本文編號：3404286