基于三角剖分鄰域關系的多目標進化算法研究.pdf

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

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

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

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

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

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