MOEA-D算法及其在多序列比對(duì)中的應(yīng)用研究.pdf

1、多目標(biāo)優(yōu)化問(wèn)題是現(xiàn)實(shí)生活和生產(chǎn)實(shí)踐中常見(jiàn)的一類優(yōu)化問(wèn)題。對(duì)求解多目標(biāo)優(yōu)化問(wèn)題的算法研究一直是學(xué)者們熱衷的領(lǐng)域。傳統(tǒng)的多目標(biāo)優(yōu)化算法對(duì)于目標(biāo)函數(shù)具有嚴(yán)格的限制，如連續(xù)，可導(dǎo)等。這大大地限制了傳統(tǒng)多目標(biāo)優(yōu)化算法的應(yīng)用范圍。隨著上世紀(jì)90年代進(jìn)化算法的興起，該研究領(lǐng)域取得了重要的進(jìn)展。多目標(biāo)進(jìn)化算法具有對(duì)目標(biāo)函數(shù)要求低，智能性，隱并行性以及自適應(yīng)性的特點(diǎn)，并且運(yùn)行一次就可以同時(shí)獲得一組Pareto最優(yōu)解。MOEA/D（Multi-object

2、iveEvolutionaryAlgorithmbasedonDecomposition）算法是近年提出的一類基于分解技術(shù)的多目標(biāo)進(jìn)化算法。由于其簡(jiǎn)單并且優(yōu)越的性能，在眾多的多目標(biāo)進(jìn)化算法中脫穎而出。與其他的多目標(biāo)進(jìn)化算法相比，MOEA/D算法在連續(xù)的多目標(biāo)優(yōu)化問(wèn)題上具有優(yōu)勢(shì)，但是面對(duì)較難的和目標(biāo)個(gè)數(shù)較多的多目標(biāo)優(yōu)化問(wèn)題仍然存在很大的挑戰(zhàn)，如容易陷入局部最優(yōu)，收斂速度慢等。
　　本文著重圍繞MOEA/D算法的改進(jìn)以及應(yīng)用兩方面進(jìn)行

3、了深入的研究，主要的創(chuàng)新性研究成果如下：
　?、籴槍?duì)MOEA/D-DRA(MOEA/DwithDynamicResourceAllocation)算法在解決較難的多目標(biāo)優(yōu)化問(wèn)題時(shí)，該算法的效用函數(shù)無(wú)法合理地分配計(jì)算資源的缺點(diǎn)，提出了一種基于新效用函數(shù)的MOEA/D-DRA（MOEA/D-DRA-NU,MOEA/D-DRAwithNewUtilityfunction）算法。在MOEA/D-DRA-NU算法的效用函數(shù)中，將個(gè)體到該個(gè)體

4、的方向向量的垂直距離或者該個(gè)體沿方向向量到理想點(diǎn)的距離的相對(duì)減少量作為度量子問(wèn)題難易程度的標(biāo)準(zhǔn)。在UF測(cè)試函數(shù)集上進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明，MOEA/D-DRA-NU算法比原MOEA/D-DRA算法和經(jīng)典的MOEA/D-DE算法的性能都要優(yōu)越。與最新提出的多目標(biāo)進(jìn)化算法MOEA/D-IR,ED/DPP-DRA和MOEA/D-FRRMAB相比較，MOEA/D-DRA-NU算法的耗費(fèi)時(shí)間最短，而且優(yōu)化效果較好。
　?、诂F(xiàn)實(shí)生活中，決策者

5、可能并不需要整個(gè)Pareto前沿的數(shù)據(jù)，而是僅僅需要其中一部分的數(shù)據(jù)。為了得到便于決策者選擇的部分Pareto前沿，本文提出了一種改進(jìn)的RMEAD（ReferencepointbasedMulti-objectiveEvolutionaryAlgorithmbyDecomposition）算法，(記為IRMEAD，ImprovedRMEAD)。該算法從如下兩方面修改了RMEAD算法。其一，提出了一種簡(jiǎn)單的尋找基權(quán)重向量的新方法；其二，修

6、改了原算法的權(quán)重向量更新步驟。大量的實(shí)驗(yàn)結(jié)果表明，與RMEAD算法相比，在所有的測(cè)試函數(shù)上，IRMEAD算法得到了在多樣性和收斂性上更好的結(jié)果。與最新提出的融合偏好的多目標(biāo)進(jìn)化算法MOEA/D-PRE相比，IRMEAD算法在大部分測(cè)試函數(shù)上具有明顯優(yōu)勢(shì)。
　?、厶岢隽嘶诜纸獾亩嗄繕?biāo)進(jìn)化算法的多序列比對(duì)方法MOMSA(Multi-objectiveevolutionaryalgorithmbasedondecompositionf

7、orMultipleSequenceAlignment)。首先，對(duì)多序列比對(duì)問(wèn)題進(jìn)行建模，將多序列比對(duì)問(wèn)題轉(zhuǎn)化為一個(gè)多目標(biāo)優(yōu)化問(wèn)題，然后將MOEA/D算法應(yīng)用于求解該多目標(biāo)優(yōu)化問(wèn)題。在該方法中，本文發(fā)展了一種新的種群初始化方法和一種新的變異操作。與經(jīng)典的以及最先進(jìn)的多序列比對(duì)方法比較，大量的實(shí)驗(yàn)結(jié)果表明，在測(cè)試集BAliBASE2.0和3.0上，MOMSA得到的比對(duì)精度高于最近提出的基于單目標(biāo)進(jìn)化算法的多序列比對(duì)方法VDGA，GAPAM