基于三角剖分鄰域關(guān)系的多目標(biāo)進(jìn)化算法研究.pdf

1、最優(yōu)化問題是一類最常遇到的問題，因為最優(yōu)化問題的解決通常是某個問題得到解決之前的最后也是最關(guān)鍵的步驟。近些年來，隨著科學(xué)技術(shù)的發(fā)展和工程應(yīng)用的不斷的增多，很多問題通過數(shù)學(xué)模型的建立最終都可以歸結(jié)于最優(yōu)化問題。最優(yōu)化問題可以根據(jù)同時需要優(yōu)化的問題數(shù)目的不同分為單目標(biāo)優(yōu)化問題和多目標(biāo)優(yōu)化問題。隨著在現(xiàn)實世界中遇到的問題越來越復(fù)雜，更多的問題被建模為多目標(biāo)優(yōu)化問題。這也促使多目標(biāo)優(yōu)化問題成為當(dāng)下得到研究比較多的一類問題，它的求解對于問題最終的

2、解決具有非常重要的意義。但是實際中遇到的多目標(biāo)優(yōu)化問題通常表現(xiàn)出一定的復(fù)雜性，并且不具有數(shù)學(xué)意義上求解的特性，而且通常是非線性的。多目標(biāo)優(yōu)化問題的這些特性決定了傳統(tǒng)的方法并不能很好的解決這一大類問題。目前解決這類問題最常使用的一類算法是多目標(biāo)進(jìn)化算法（MOEA）。衡量MOEA的性能的指標(biāo)通常包含兩個方面：1.算法求解得到的解集與真正的問題最優(yōu)解的解集的逼近程度；2.算法求解得到的解集相對于整個問題的解集的分布程度，包括分布廣度和分布的均

3、勻性。作為MOEA中優(yōu)秀的框架意義上被提出和使用較多的并且具有代表性的兩大類算法是NSGA-II和MOEA/D。前者代表了一類基于非支配排序的MOEA，而后者則代表了一類基于分解的MOEA。這兩種具有代表性的MOEA在算法迭代過程中對于維持解集的多樣性都使用到了密度度量這個指標(biāo)。其中，NSGA-II定義了自己的擁擠距離（crowding distance），而MOEA/D中則使用了傳統(tǒng)的歐氏距離（Euclidian distance）來

4、度量，這兩種距離度量在某種程度上都僅僅考慮了點之間單純的距離關(guān)系。但是在三維空間或者更高維度空間里，點與另一個點之間的關(guān)系還包括其相對位置關(guān)系，也就是方向的問題。所以，本文引入了三角剖分這個工具，綜合考慮距離與鄰域關(guān)系的基礎(chǔ)上來提高進(jìn)化算法解集的分布度。根據(jù)我們的實驗結(jié)果數(shù)據(jù)，可以說明在維持解集多樣性上本文中提出的改進(jìn)方法具有顯著的作用。本文的主要工作如下：
　　1.針對NSGA-II算法的具體改進(jìn)。我們知道NSGA-II算法是基

5、于非支配排序的，其中的核心思想在于進(jìn)化群體中一個偏序關(guān)系的構(gòu)造。對于進(jìn)化群體中的個體進(jìn)行邊界集的構(gòu)造和邊界集上個體擁擠距離的計算。擁有較小的邊界集號的個體會被算法優(yōu)先選擇進(jìn)入下一次迭代，而在最后一層邊界集的選擇時則選擇擁擠距離大的個體。從這種偏序關(guān)系上我們可以看出，非支配排序的目的在于使算法盡快收斂，而擁擠距離的計算在于選擇個體使解集的分布度更高。本文的具體工作就在于在計算擁擠距離的時候用三角剖分的方式更精確的確立個體的擁擠距離。

6、>　　2.針對MOEA/D算法的具體改進(jìn)。根據(jù)我們對MOEA/D中權(quán)向量和解集之間對應(yīng)關(guān)系的分析，我們可以根據(jù)目標(biāo)空間中個體的目標(biāo)值計算出其應(yīng)該對應(yīng)的權(quán)向量空間中具體的權(quán)向量值。這樣我們就可以在目標(biāo)空間中調(diào)整解集中的個體使其盡量均勻分布，并計算相應(yīng)的權(quán)向量加入到種群中，使該個體最終收斂到合適的位置。在衡量個體間的均勻性的時候，本文也是采用三角剖分的方式精確的確立種群中的稀疏區(qū)域與擁擠區(qū)域。從而向稀疏區(qū)域加入個體，從密集區(qū)域刪除個體，從而