基于模擬正態(tài)分布隨機(jī)數(shù)的NSGA- II 算法研究

呂 琳 石連栓

（天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津300222）

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

1 基本概念

多目標(biāo)優(yōu)化問題的一般描述：

日常生產(chǎn)生活中的多目標(biāo)問題可以抽象為數(shù)學(xué)形式。多目標(biāo)優(yōu)化問題由多個目標(biāo)函數(shù)及相關(guān)的等式和不等式約束組成：

其中：k 為目標(biāo)函數(shù)的個數(shù)，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 多目標(biāo)優(yōu)化算法的改進(jìn)

2.1 引入模擬正態(tài)分布交叉算子（SNDX）

2.1.1 模擬正態(tài)分布隨機(jī)數(shù)。正態(tài)分布、卡方分布等連續(xù)型隨機(jī)變量，一般使用逆變化法求得其隨機(jī)數(shù)[5]。因隨機(jī)數(shù)的求解難度大，可采用兼顧簡潔性和精確性的顯式初等函數(shù)來模擬函數(shù)關(guān)系，增強(qiáng)數(shù)據(jù)的可解釋性。標(biāo)準(zhǔn)正態(tài)分布的分布函數(shù)為：

其中λ（x）為七次多項(xiàng)式。

在[-3.2,3.2]區(qū)間內(nèi)的擬合正態(tài)分布的分布函數(shù)圖像如圖1 所示。從圖1 可知，通過模擬產(chǎn)生的正態(tài)分布函數(shù)值能夠均勻的分布在標(biāo)準(zhǔn)正態(tài)分布的分布函數(shù)曲線上, 可以根據(jù)牛頓近似法求u（x）的逆函數(shù)近似正態(tài)分布隨機(jī)數(shù)N。

模擬標(biāo)準(zhǔn)正態(tài)分布函數(shù)圖像

2.1.2 基于模擬正態(tài)分布隨機(jī)數(shù)的交叉算子（SNDX）。基于SNDX的交叉過程如下：

（A）產(chǎn)生一個（0，1]間均勻分布的隨機(jī)數(shù)α；（B）如果α燮0.5，則

（C）如果α>0.5，則其中N為通過擬合函數(shù)求逆得到的近似正態(tài)分布的隨機(jī)數(shù)。

2.2 自適應(yīng)的交叉概率和變異概率

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

（1）交叉概率。交叉的發(fā)生概率根據(jù)式（10）進(jìn)行自適應(yīng)調(diào)整：

其中n 表示當(dāng)前迭代次數(shù)，N為最大的迭代次數(shù)，pc 是給定的交叉概率值。

（2）變異概率。對變異概率的自適應(yīng)調(diào)整根據(jù)下列公式進(jìn)行：

其中n 表示當(dāng)前迭代次數(shù)，N為最大的迭代次數(shù)，pm是給定的變異概率值。

3 算法步驟

根據(jù)以上改進(jìn)，SNDX-NSGA-II 的算法基本步驟如下：

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

4 實(shí)驗(yàn)仿真

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

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

IGD 評價結(jié)果

5 結(jié)論

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