基于模型的混合多目標(biāo)算法的研究

基于模型的混合多目標(biāo)算法的研究提綱研究背景及意義國內(nèi)外研究現(xiàn)狀模型多目標(biāo)算法（RM-MEDA，MMEA）基于模型的混合多目標(biāo)算法實(shí)驗(yàn)結(jié)果及分析總結(jié)與展望研究背景及意義傳統(tǒng)多目標(biāo)算法如NSGA-Ⅱ具有較好的全局搜索能力，而在算法后期由于采用交叉、變異算子使得較好解容易丟失，造成收斂速度過慢；模型多目標(biāo)具有較好的局部搜索能力，而如果在算法初期種群還未形成一定規(guī)則的時(shí)候就對種群進(jìn)行建模操作，可能會(huì)造成算法陷入局部最優(yōu)。因此，本文將兩種算法結(jié)合，充分發(fā)揮各自的優(yōu)勢，具有一定的研究意義。國內(nèi)外研究現(xiàn)狀1967年，Rosenberg在其博士論文中首次提出采用遺傳搜索的方法來求解多目標(biāo)的優(yōu)化問題。1984年以來，研究者們針對不同的實(shí)際問題，提出了各式各樣的多目標(biāo)進(jìn)化算法（MOEA）。比較突出的就是Deb等提出的NSGA-Ⅱ以及Zitzler等提出的SPEA2。雖然NSGA-Ⅱ、SPEA2已經(jīng)獲得了很大的成功，但是它們都是采用交叉、變異算子進(jìn)行子代繁殖，而忽略了這些算子對算法性能的影響。分布估計(jì)算法（EDA）采用統(tǒng)計(jì)學(xué)的方法對當(dāng)前種群進(jìn)行分析，建立一個(gè)概率模型，并從中取樣產(chǎn)生新的子代。國內(nèi)外研究現(xiàn)狀（續(xù)）2005年，周愛民等首次提出了模型多目標(biāo)優(yōu)化算法用于解決兩個(gè)目標(biāo)問題。。2007年張青富等提出RegularityModel-BasedMulti-objectiveEstimationofDistributionAlgorithm(RM-MEDA)。2008年周愛民等人又將多目標(biāo)優(yōu)化問題分為兩類,并且提出解決第二類問題的MMEA算法。模型多目標(biāo)算法—RM-MEDA多目標(biāo)相關(guān)概念：

一般MOP由n個(gè)決策變量參數(shù)，m個(gè)目標(biāo)以及約束條件組成，目標(biāo)函數(shù)、約束條件與決策變量之間是函數(shù)關(guān)系。最優(yōu)化目標(biāo)如下：

minst.多目標(biāo)優(yōu)化問題的解就是尋求一個(gè)，使得在滿足約束條件的情況下達(dá)到最優(yōu)。

若不存在一個(gè)使得，且至少一個(gè)是嚴(yán)格的不等式，則此時(shí)的就稱為多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解。將所有滿足Pareto最優(yōu)解定義的組成的集合稱為PS，而PS對應(yīng)的目標(biāo)空間的解集即為PF。

模型多目標(biāo)算法—RM-MEDA個(gè)體支配關(guān)系：設(shè)p和q是進(jìn)化群體Pop中的任意兩個(gè)不同的個(gè)體，稱p支配q，則必須滿足下列條件：1、對所有的子目標(biāo)，p不比q差，即fk(p)≤fk(q)(k=1,2,…m)。2、至少存在一個(gè)子目標(biāo)，使得p比q好，即嚴(yán)格的不等式成立。其中：m為子目標(biāo)的個(gè)數(shù)。RM-MEDA算法理論基礎(chǔ)：

在光滑的條件下根據(jù)Karush-Kuhn-Tucker條件可以得出，一個(gè)連續(xù)的m個(gè)目標(biāo)的多目標(biāo)優(yōu)化問題的Pareto解集（即ParetoSet，PS）在決策空間的分布是一個(gè)分段、連續(xù)的(m-1)維的流形。對于兩個(gè)目標(biāo)的優(yōu)化問題，它的解集分布是一維流形，即主曲線。對于三個(gè)目標(biāo)的優(yōu)化問題，它的解集分布是一個(gè)二維的主曲面。RM-MEDA（續(xù)）算法基本思想：其中：是在流形

上隨機(jī)產(chǎn)生的點(diǎn)，

，是恒等矩陣，RM-MEDA（續(xù)）算法基本流程：RM-MEDA（續(xù)）建模過程：

1、利用LocalPCA聚類算法將種群劃分為K個(gè)聚類

2、對每一個(gè)聚類，計(jì)算它的數(shù)據(jù)點(diǎn)的平均值，以及中樣本點(diǎn)的協(xié)方差矩陣，令為第個(gè)聚類第個(gè)主成分的方向（即聚類中所有個(gè)體解的協(xié)方差矩陣的第大特征值對應(yīng)的特征向量）3、計(jì)算個(gè)體在各主成分方向上的范圍：令4、計(jì)算：5、令為聚類

中樣本點(diǎn)的協(xié)方差矩陣的第i大特征值，則RM-MEDA（續(xù)）子代繁殖：

1、隨機(jī)產(chǎn)生一個(gè)整數(shù)

按照概率

2、隨機(jī)產(chǎn)生一個(gè)新解，按照公式

，其中

是個(gè)產(chǎn)生于

的數(shù)據(jù)點(diǎn)，為一個(gè)服從

的噪聲向量。

3、重復(fù)步驟1，步驟2直到產(chǎn)生N個(gè)新解。RM-MEDA（續(xù)）選擇：

1、利用快速非支配排序算法將種群

劃分為不同的前沿

，令Pop(t+1)=，k=0；2、執(zhí)行下列步驟直到種群Pop(t+1)中的個(gè)體數(shù)目超過N，,

3、種群Pop(t+1)中的個(gè)體數(shù)目超過N時(shí)，計(jì)算在種群

中所有個(gè)體的擁擠度距離，將擁擠度距離最小的個(gè)體從種群里面移除。模型多目標(biāo)算法—MMEAMMEA算法是針對第二類問題提出的，第二類問題指的是目標(biāo)空間的PF分布是一個(gè)(m-1)-D的流形，而決策空間的PS分布是一個(gè)高于(m-1)-D的流形,第二類問題較第一類問題更為復(fù)雜。MMEA算法是通過對目標(biāo)空間PF的逼近來同時(shí)對決策空間PS進(jìn)行逼近的。

MMEAMMEA算法基本流程：

設(shè)種群Pop的規(guī)模大小為N，演化代數(shù)為t，每個(gè)個(gè)體對應(yīng)的目標(biāo)函數(shù)值為

算法的流程如下：1、初始化：隨機(jī)產(chǎn)生一個(gè)初始種群P并計(jì)算P中個(gè)體的目標(biāo)函數(shù)值；2、建立模型：為當(dāng)前種群建立一個(gè)概率模型模擬種群中P中個(gè)體的分布；3、子代繁殖：從步驟2的模型中取樣產(chǎn)生新解的集合Q，并計(jì)算Q中個(gè)體

的目標(biāo)函數(shù)值；4、選擇：從子代種群Q和父代種群P中產(chǎn)生N個(gè)解代替P中的所有個(gè)體；5、結(jié)束條件：如果結(jié)束條件滿足，返回在種群P中的所有解和其對應(yīng)的目標(biāo)函數(shù)值，否則返回步驟2。MMEA（續(xù)）建模過程：1、建立一個(gè)理想的PF(UtopianPF，UPF)：基于當(dāng)前種群P的信息，在目標(biāo)空間建立一個(gè)(m-1)-D的單形作為UPF。1.1、從種群P的非支配解集中選取在第i個(gè)目標(biāo)函數(shù)

上有最大值的m個(gè)個(gè)體1.2、初始化單形S為目標(biāo)空間的頂點(diǎn)為

的m-1維流形，將S沿其垂直方向移動(dòng)到一個(gè)位置，使得：(a)S中沒有一個(gè)點(diǎn)被P中的個(gè)體支配；(b)移動(dòng)的距離盡可能的?。?.3、令為移動(dòng)后的單形S的頂點(diǎn)，計(jì)算S的中心：然后通過移動(dòng)S的頂點(diǎn)來擴(kuò)展S，MMEA（續(xù)）2、計(jì)算子種群K，3、在建立的UPF上，均勻的選取K個(gè)點(diǎn)

作為參考點(diǎn)，用來將種群劃分為K個(gè)聚類。4、主成分分析(PCA)及建模：

即保持80%的主成分，因?yàn)镻S是比m-1維更高的流形，但不知道它具體多少維，所以不能保持所有的主成分。

基于模型的混合多目標(biāo)算法算法提出的依據(jù)：基于模型的混合多目標(biāo)算法（續(xù)）1代50代100代150代200代250代基于模型的混合多目標(biāo)算法（續(xù)）基本流程：實(shí)驗(yàn)結(jié)果及分析度量準(zhǔn)則：收斂性度量：多樣性度量：IGD度量：第一類問題的實(shí)驗(yàn)結(jié)果及分析第一類問題的實(shí)驗(yàn)結(jié)果及分析第一類問題的實(shí)驗(yàn)結(jié)果及分析第一類問題的實(shí)驗(yàn)結(jié)果及分析第一類問題的實(shí)驗(yàn)結(jié)果及分析ZDT1實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析ZDT2實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析ZDT3實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析ZDT6實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析ZDT1.1實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析ZDT2.1實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析ZDT1.2實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析ZDT2.2實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析DTLZ2實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析DTLZ2.1實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA第一類問題的實(shí)驗(yàn)結(jié)果及分析DTLZ2.2實(shí)驗(yàn)結(jié)果圖示：NSGA-ⅡRM-MEDAMMEAN+RMMEDA針對標(biāo)準(zhǔn)的ZDT系列函數(shù)以及DTLZ2函數(shù)，NSGA-Ⅱ的效果要明顯優(yōu)于模型多目標(biāo)算法，由于它們決策空間的PS分布相對簡單，弱化了模型多目標(biāo)算法的優(yōu)勢，同時(shí)，如果從算法開始就對種群進(jìn)行建模操作，當(dāng)種群的分布還未呈現(xiàn)出一定的規(guī)則時(shí)就進(jìn)行建模，不利于子代的搜索，可能會(huì)造成收斂不到全局的最優(yōu)解，而陷入局部最優(yōu)。而將兩者結(jié)合后的算法雖略差于NSGA-Ⅱ，但是卻要明顯優(yōu)于兩種模型多目標(biāo)算法。

第一類問題的實(shí)驗(yàn)結(jié)果及分析針對改進(jìn)的ZDT函數(shù)以及DTLZ2函數(shù)，由于它們的PS分布相對復(fù)雜，這時(shí)NSGA-Ⅱ算法就顯得無能為力，而模型多目標(biāo)算法的優(yōu)勢也漸漸顯現(xiàn)出來。從實(shí)驗(yàn)數(shù)據(jù)中也可以看出，結(jié)合后的算法與模型多目標(biāo)算法相差不大，而且在某些方面要更優(yōu)于模型多目標(biāo)算法。

為什么結(jié)合后的算法沒有達(dá)到預(yù)期的效果呢？這主要是算法階段的劃分還不明確，何時(shí)采用建模的方式產(chǎn)生子代也有待進(jìn)一步研究。第一類問題的實(shí)驗(yàn)結(jié)果及分析第二類問題的實(shí)驗(yàn)結(jié)果及分析第二類問題的實(shí)驗(yàn)結(jié)果及分析F3實(shí)驗(yàn)結(jié)果圖示：

NSGA-ⅡMMEAN+MMEA