基于模擬正態分布隨機數的NSGA- II 算法研究

呂 琳 石連栓

（天津職業技術師范大學信息技術工程學院，天津300222）

NSGA-II 算法是由Deb.K[1]等提出的一種解決多目標優化問題的經典算法，文獻[2]-[4]提出了將正態分布交叉算子應用到多目標優化中，擴大了解集的搜索空間，且非支配解集的精度更高，穩定性更強。基于上述文獻的啟發，本文引入模擬正態分布隨機數交叉算子，并探究其在解空間的搜索性能。并通過自適應的變異和交叉概率來避免算法早熟。

1 基本概念

多目標優化問題的一般描述：

日常生產生活中的多目標問題可以抽象為數學形式。多目標優化問題由多個目標函數及相關的等式和不等式約束組成：

其中：k 為目標函數的個數，fk，gi，hj：Rn→R，∈Rn為決策變量，X={x|x∈Rn，gi（x）燮0，hj（x）=0，i=1，2，…，p；j=1，2，…，p}稱為式（1）的可行域。g（x）定義了q 個不等式約束，h（x）定義了p 個等式約束。

2 多目標優化算法的改進

2.1 引入模擬正態分布交叉算子（SNDX）

2.1.1 模擬正態分布隨機數。正態分布、卡方分布等連續型隨機變量，一般使用逆變化法求得其隨機數[5]。因隨機數的求解難度大，可采用兼顧簡潔性和精確性的顯式初等函數來模擬函數關系，增強數據的可解釋性。標準正態分布的分布函數為：

其中λ（x）為七次多項式。

在[-3.2,3.2]區間內的擬合正態分布的分布函數圖像如圖1 所示。從圖1 可知，通過模擬產生的正態分布函數值能夠均勻的分布在標準正態分布的分布函數曲線上, 可以根據牛頓近似法求u（x）的逆函數近似正態分布隨機數N。

模擬標準正態分布函數圖像

2.1.2 基于模擬正態分布隨機數的交叉算子（SNDX）。基于SNDX的交叉過程如下：

（A）產生一個（0，1]間均勻分布的隨機數α；（B）如果α燮0.5，則

（C）如果α>0.5，則其中N為通過擬合函數求逆得到的近似正態分布的隨機數。

2.2 自適應的交叉概率和變異概率

交叉概率和變異概率的值是影響算法性能及收斂的兩個關鍵控制參數，但在NSGA-II 算法中通常被定義為常量，在解決多目標問題時會導致搜索能力不足，易陷入局部最優。因此本文基于NSGA-II 算法設計了自適應調整的交叉概率和變異概率。

（1）交叉概率。交叉的發生概率根據式（10）進行自適應調整：

其中n 表示當前迭代次數，N為最大的迭代次數，pc 是給定的交叉概率值。

（2）變異概率。對變異概率的自適應調整根據下列公式進行：

其中n 表示當前迭代次數，N為最大的迭代次數，pm是給定的變異概率值。

3 算法步驟

根據以上改進，SNDX-NSGA-II 的算法基本步驟如下：

Step1 設置算法的起始參數，包括種群規模popSize，最大迭代次數N，染色體大小chromoSize，優化目標數量等常量，給定交叉概率pc 和變異概率pm。Step2 初始化種群，隨機產生popSize 個個體作為父代種群，并對種群中的所有個體的支配等級進行初始化。Step3 當前迭代次數n=1，對父代種群進行二進制錦標賽選擇，將給定的交叉概率和變異概率帶入式（9）和式（10）中生成自適應的交叉概率PC和交叉概率PM，使用模擬正態分布交叉算子和SBX 多項式變異算子進行交叉和變異操作，產生子代種群。Step4 將父代種群和子代種群合并后，對產生的新種群進行快速非支配排序。Step5 計算擁擠度和擁擠距離，利用精英選擇策略選擇出最佳的popSize 個個體，形成新一代種群。Step6 當前迭代次數n=n+1。重復執行步驟Step3 至步驟Step6，直到滿足循環終止條件。Step7 得到最終的Pareto最優解集。

4 實驗仿真

為了測試基于SNDX-NSGA-II 算法的有效性和可行性，本文使用3 個多目標優化測試函數ZDT1、ZDT2、ZDT3 對其進行測試。實驗參數設置如下：種群大小popSize=300，染色體大小chromoSize=30， 固 定 交 叉 概 率 pc=1； 固 定 變 異 概 率pm=1/chromoSize，設置最大代數為250 代。每個測試實驗均執行30 次。

評價函數：本文使用了反轉世代距離（IGD） 函數對SNDX-NSGA-II 算法進行評估。IGD函數是一個綜合性能評價指標，主要通過計算每個真實Pareto前沿面上的點到算法獲取的個體集合之間的最小距離和，來評價算法的收斂性能和分布性。下表是每種實驗分別運行30 次的得到的平均結果。通過評價函數的結果可知，在ZDT1, ZDT2, ZDT3 測試函數中本文的算法IGD 指標的結果均小于NSGA-II。因此，SNDX- NSGA-II 算法提高了解的收斂性和分布性，能更好的求解多目標優化問題。

IGD 評價結果

5 結論

本文利用模擬正態分布隨機數交叉算子結合自適應調整的交叉概率和變異概率對NSGA-II 算法進行了改進，使用通用的多目標測試函數對本文提出的算法進行測試，結果顯示改進后的算法得到了更好的分布性和收斂性Pareto 解的前沿。今后將SNDX-NSGA-II 算法運用到維度更高更加復雜的公開測試函數對其進行性能測試，并考慮將本文的算法應用到實際的工程問題中，提高處理實際問題的能力。