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

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

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

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

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

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

6、改了原算法的權(quán)重向量更新步驟。大量的實驗結(jié)果表明，與RMEAD算法相比，在所有的測試函數(shù)上，IRMEAD算法得到了在多樣性和收斂性上更好的結(jié)果。與最新提出的融合偏好的多目標(biāo)進化算法MOEA/D-PRE相比，IRMEAD算法在大部分測試函數(shù)上具有明顯優(yōu)勢。
　　③提出了基于分解的多目標(biāo)進化算法的多序列比對方法MOMSA(Multi-objectiveevolutionaryalgorithmbasedondecompositionf

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