一種改進(jìn)的非支配排序遺傳算法

王青松，謝興生，周光臨

(中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥 230026)

0 引言

在實(shí)際生活以及工程應(yīng)用中，經(jīng)常要求在給定的資源下，同時(shí)滿足多個(gè)目標(biāo)最優(yōu)化，即多目標(biāo)優(yōu)化[1]。比如在部署虛擬機(jī)時(shí)，需要同時(shí)滿足高利用率、低延遲以及高吞吐量等[2]；在交通信號(hào)配時(shí)中，需同時(shí)使得延誤時(shí)間最小、通行能力最大以及停車次數(shù)最少[3]。對(duì)于多目標(biāo)優(yōu)化問題，傳統(tǒng)的處理方法大多是加權(quán)法，即通過對(duì)不同的優(yōu)化目標(biāo)分配不同的權(quán)重，把多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題來求解。加權(quán)法的缺點(diǎn)主要有兩點(diǎn)，一方面權(quán)重的設(shè)置具有主觀性，需要對(duì)優(yōu)化問題有充分的了解；另外一方面，優(yōu)化目標(biāo)之間通常不是線性相關(guān)的，因此求得的解通常來說不是全局最優(yōu)解。對(duì)于多目標(biāo)優(yōu)化問題，由于幾乎不存在單個(gè)全局最優(yōu)解，因此通常是求解一系列非支配解[4](Pareto解集)。

非支配排序遺傳算法[5](Non-dominated Sorting Genetic Algorithm II，NSGA-II)是DEB K等人提出的一種元啟發(fā)式算法，由于NSGA-II算法在低維優(yōu)化問題中表現(xiàn)優(yōu)良，并且算法實(shí)現(xiàn)相對(duì)容易，因此被廣泛使用。比如李曉青等人[6]針對(duì)發(fā)電功率，對(duì)風(fēng)力發(fā)電子系統(tǒng)和光伏發(fā)電子系統(tǒng)一起使用NSGA-II算法進(jìn)行協(xié)調(diào)控制，使得風(fēng)能和太陽(yáng)能更為合理地得到利用；AHMADI V等人[7]使用NSGA-II算法求解(Software Defined Network,SDN)體系結(jié)構(gòu)中的控制器的部署位置，顯著提高了網(wǎng)絡(luò)的負(fù)載均衡能力、可靠性和容錯(cuò)性。然而，NSGA-II算法在求解時(shí)更關(guān)注解集質(zhì)量，求出的解集在分布性方面相對(duì)較差。針對(duì)NSGA-II算法的不足，本文提出了一種改進(jìn)的非支配排序遺傳算法(INSGA-II)。

本文首先擴(kuò)大了NSGA-II算法初始化種群規(guī)模，其目的是提高收斂性，然后為了提高解集的分布性，引入了概率選擇算子。同時(shí)為了增大算法的搜索空間，提出了混合交叉算子。最后使用公開的多目標(biāo)測(cè)試函數(shù)，以世代距離(Generational Distance，GD)、分布性(Δ)和反世代距離(Inverted Generational Distance，IGD)作為性能指標(biāo)[8]，與NSGA-II算法和改進(jìn)的多目標(biāo)粒子群算法[9](Optimized Multi-Objective Particle Swarm Optimization，OMOPSO)算法進(jìn)行比較。

1 NSGA-II算法相關(guān)概念

NSGA-II算法主要有三大核心概念：快速非支配排序、擁擠距離以及精英策略。

1.1 快速非支配排序

快速非支配排序算法根據(jù)種群中個(gè)體的優(yōu)劣程度來對(duì)種群分層，目的是使得下一步搜索方向往Pareto最優(yōu)解集靠近。令nt為支配個(gè)體t的個(gè)體數(shù)目，st為被個(gè)體t支配的所有個(gè)體，則具體步驟如下：

(1)把種群中滿足nt=0的所有個(gè)體存入到當(dāng)前非支配集合F1中。

(2)被F1中的個(gè)體i支配的個(gè)體集合記為Si。遍歷集合Si，對(duì)于其中的每個(gè)個(gè)體l，將其支配數(shù)nl更新為nl-1，若nl=0，則把個(gè)體l保存到新的集合H中。

(3)此時(shí)，F(xiàn)1集合為第一級(jí)非支配個(gè)體集合，里面所有個(gè)體的非支配序均相同，而集合H重新作為當(dāng)前非支配集合，重復(fù)上述步驟，直到所有個(gè)體均被賦予了非支配序。

1.2 擁擠距離

擁擠距離刻畫了種群中個(gè)體的分散程度，令Ci為個(gè)體i的擁擠距離，則在邊緣上的個(gè)體的擁擠距離為∞，其余個(gè)體的擁擠距離計(jì)算公式如下：

(1)

i>cj?irankCj

(2)

式中，irank表示個(gè)體i的非支配序。式(2)含義為個(gè)體i優(yōu)于個(gè)體j，當(dāng)且僅當(dāng)個(gè)體i的非支配序小于個(gè)體j的非支配序或者個(gè)體i的非支配序等于個(gè)體j的非支配序且個(gè)體i的擁擠距離大于個(gè)體j的擁擠距離。

1.3 精英策略

精英策略的目的是避免優(yōu)秀的Pareto解集丟失。首先將父代種群Pt和子代種群Qt組合成大小為2N的新種群Rt，然后對(duì)集合Rt進(jìn)行快速非支配排序和擁擠距離計(jì)算，并按照非支配序從低到高排序，選擇個(gè)體進(jìn)入新種群Pt+1中，如果某個(gè)相同非支配序集合中的個(gè)體全部加入Pt+1超過了種群上限值N，則此時(shí)按照擁擠距離從該集合中進(jìn)行優(yōu)選，直到種群數(shù)量為N。

2 改進(jìn)的NSGA-II算法

為了提高NSGA-II算法的收斂性和分布性，以獲得更多和更好的解，提出以下三種改進(jìn)策略。

2.1 新的初始化種群

在NSGA-II算法中，初始化種群P0是隨機(jī)產(chǎn)生的，且種群的大小為N，而子代種群Q0則是基于種群P0經(jīng)過選擇、交叉和變異產(chǎn)生的。算法進(jìn)行第一次迭代時(shí)，可以視為隨機(jī)搜索。對(duì)于隨機(jī)搜索，顯然種群個(gè)體越多，找到最優(yōu)解的概率就越大，但是個(gè)體也不能無(wú)限增加，否則可能會(huì)影響算法的收斂時(shí)間。在不影響算法復(fù)雜度的前提下，若種群個(gè)體為N，初始化種群的個(gè)體數(shù)目可以設(shè)置為1.5N～2N之間，其目的是提高第一輪子代種群Q0的質(zhì)量，加速整個(gè)種群往最優(yōu)解靠近。

2.2 概率選擇算子

選擇算子是算法的核心算子之一，作用是從當(dāng)前種群中選擇出優(yōu)良的個(gè)體并用于后續(xù)交叉、變異以產(chǎn)生新的子代種群，它決定了當(dāng)前種群的下一步走向。NSGA-II算法選擇算子常采用的策略是二元錦標(biāo)賽選擇，即隨機(jī)從種群中選擇兩個(gè)個(gè)體，讓這兩個(gè)個(gè)體互相比較，選擇出最優(yōu)個(gè)體，比較的策略是基于個(gè)體的非支配序和擁擠距離。由于選擇算子對(duì)于算法的性能至關(guān)重要，因此選擇算子的好壞會(huì)影響到所求的解集的質(zhì)量。

NSGA-II的選擇算子更關(guān)注解的質(zhì)量，為了讓選擇算子在保證解的質(zhì)量前提下提高所求解集的分布性，在原有的選擇算子基礎(chǔ)之上引入了概率操作。在種群進(jìn)化初期，以較大的概率拒絕當(dāng)前選出的最優(yōu)個(gè)體，選擇另外的個(gè)體，保證了算法初期的種群多樣性，在進(jìn)化后期，由于種群趨向于收斂，因此以較小的概率拒絕當(dāng)前選出的最優(yōu)個(gè)體，但是仍然保留選擇另外個(gè)體的可能性。概率操作的計(jì)算公式為：

(3)

式中，w為概率選擇算子參數(shù)，g為進(jìn)化代數(shù)。

2.3 混合交叉算子

基本的NSGA-II算法中對(duì)實(shí)數(shù)編碼采用了模擬二進(jìn)制交叉(Simulated Binary Crossover，SBX)，SBX交叉算子實(shí)現(xiàn)起來比較簡(jiǎn)單，但是移動(dòng)空間的范圍比較小，因此搜索能力相對(duì)較弱，容易陷入局部最優(yōu)解。針對(duì)SBX交叉算子存在的缺點(diǎn)，提出了混合交叉算子，即在SBX交叉算子基礎(chǔ)上引入高斯分布交叉算子(Normal Distribution Crossover，NDX)，并自適應(yīng)地調(diào)整這兩種交叉算子權(quán)重。NDX交叉算子相對(duì)于SBX交叉算子的優(yōu)勢(shì)在于搜索空間更大，因此更容易跳出局部最優(yōu)[10]。在算法初期，由于種群中的個(gè)體不知道最優(yōu)解位于何處，因此應(yīng)該加大搜索空間范圍，讓NDX交叉算子的權(quán)重更大。在算法迭代的后期，由于整個(gè)種群已經(jīng)趨向于穩(wěn)定，大部分個(gè)體都在最優(yōu)Pareto解周圍，因此可以縮小搜索空間，此時(shí)讓SBX交叉算子權(quán)重變大，以加速算法收斂。令u為區(qū)間(0,1)上均勻分布所產(chǎn)生的隨機(jī)數(shù)，r=|N(0,1)|為高斯分布隨機(jī)變量的值，則當(dāng)u≤0.5時(shí)，個(gè)體在混合交叉算子下的更新公式為：

(4)

當(dāng)u>0.5時(shí)，個(gè)體在混合交叉算子下的更新公式為：

(5)

式(5)、(6)中，x1,i和x2,i為混合交叉算子產(chǎn)生子代個(gè)體第i個(gè)變量的值；M=p1,i+p2,i，N=p1,i-p2,i，p1,i和p2,i為父代個(gè)體第i個(gè)變量的值；g為當(dāng)前迭代次數(shù)，G為總的迭代次數(shù)，ηc為交叉算子參數(shù)。

2.4 INSGA-II算法步驟

INSGA-II算法步驟如下：

(1)設(shè)置算法參數(shù):種群規(guī)模N，初始化種群P0的規(guī)模N0=1.5N～2N，迭代次數(shù)G，概率選擇算子參數(shù)w以及混合交叉算子參數(shù)ηc。

(2)隨機(jī)產(chǎn)生N0個(gè)個(gè)體作為父代種群P0。

(3)當(dāng)前迭代次數(shù)g=0，對(duì)父代種群P0進(jìn)行概率選擇、混合交叉和變異操作，生成子代種群Q0。

(4)合并父子代種群Pt和Qt為新種群Rt，對(duì)新種群Rt進(jìn)行快速非支配排序。

(5)使用精英策略，從新種群Rt中選擇出N個(gè)優(yōu)良個(gè)體作為新的父代種群Pt+1。

(6)對(duì)新種群Pt+1進(jìn)行概率選擇、混合交叉和變異操作，生成新子代種群Qt+1。

(7)若當(dāng)前迭代次數(shù)g不小于最大迭代次數(shù)G，則算法結(jié)束，否則g=g+1，并進(jìn)入步驟(4)。

3 實(shí)驗(yàn)與分析

3.1 測(cè)試函數(shù)和參數(shù)設(shè)置

為了評(píng)估INSGA-II優(yōu)化算法的有效性，使用四個(gè)公開的標(biāo)準(zhǔn)多目標(biāo)測(cè)試函數(shù)來進(jìn)行測(cè)試，分別是ZDT1、ZDT2、ZDT3和ZDT4函數(shù)[11]，具體表達(dá)式如公式(6)～公式(9)所示。為了公平且合理比較不同的多目標(biāo)優(yōu)化算法，種群規(guī)模的大小均設(shè)置為100，最大迭代次數(shù)均設(shè)置為1 000；NSGA-II算法和INSGA-II算法的變異算子參數(shù)以及交叉算子參數(shù)均為20，INSGA-II概率選擇算子中的w參數(shù)設(shè)置為0.01；OMOPSO算法的變異概率為1/d，d為變量個(gè)數(shù)，存檔的大小為100，慣性量權(quán)重系數(shù)W的值為random(0.1,0.5)；真實(shí)Pareto前沿的采樣點(diǎn)個(gè)數(shù)為500。同時(shí)為了提高評(píng)價(jià)結(jié)果的穩(wěn)定性，對(duì)每個(gè)測(cè)試函數(shù)使用優(yōu)化算法重復(fù)求解50次，計(jì)算不同評(píng)價(jià)指標(biāo)的平均值。

(6)

(7)

(8)

(9)

對(duì)于三個(gè)評(píng)價(jià)指標(biāo)，收斂性評(píng)價(jià)指標(biāo)GD的計(jì)算公式如下：

(10)

式中，di表示算法求解得到的Pareto前沿PF中的個(gè)體i和真實(shí)Pareto前沿集合的最短距離，值越小，表明解集質(zhì)量越高。分布性評(píng)價(jià)指標(biāo)SP的計(jì)算公式為：

(11)

(12)

式中，d(x,y)表示點(diǎn)x與點(diǎn)y之間的距離，IGD值越小，表明所求的最優(yōu)解集組成的Pareto前沿PF越逼近真實(shí)的Pareto前沿PF*，算法的綜合性能越好。

3.2 結(jié)果和分析

三種優(yōu)化算法對(duì)四個(gè)測(cè)試函數(shù)求解得到的Pareto前沿的局部放大結(jié)果如圖1～圖4所示，其性能指標(biāo)結(jié)果如表1所示。由圖1到圖4可以看出，INSGA-II算法能比較接近真實(shí)的Pareto前沿。從表1中的數(shù)據(jù)可知，INSGA-II算法在大多數(shù)情況下收斂性和分布性比NSGA-II算法要好，在ZDT1和ZDT3測(cè)試函數(shù)上，INSGA-II算法的GD略低于OMOPSO算法，但是INSGA-II算法的分布性卻大大優(yōu)于OMOPSO算法。相比于OMOPSO算法，INSGA-II算法在保證Pareto解集質(zhì)量的前提下，同時(shí)保證了Pareto解集的分布性。這表明新的初始化種群、概率選擇算子以及混合交叉算子有效地改善了NSGA-II算法的分布性和收斂性。

圖1 ZDT1函數(shù)實(shí)驗(yàn)結(jié)果局部放大

圖2 ZDT2函數(shù)實(shí)驗(yàn)結(jié)果局部放大

圖3 ZDT3函數(shù)實(shí)驗(yàn)結(jié)果局部放大

圖4 ZDT4函數(shù)實(shí)驗(yàn)結(jié)果局部放大

測(cè)試函數(shù)性能指標(biāo)NSGA-IIINSGA-IIOMOPSOGD0.004 3620.001 4820.001 314ZDT1Δ0.555 3040.226 8270.604 015IGD0.048 6540.014 878 80.014 581GD0.006 2240.002 7280.005 436ZDT2Δ0.657 8260.422 9081.038 221IGD0.066 7810.026 2660.086 539GD0.001 4880.001 1510.001 135ZDT3Δ0.787 3830.804 6441.177 877IGD0.023 7010.021 0530.021 770GD0.000 9290.000 2460.000 291ZDT4Δ0.562 7740.231 5800.953 511IGD0.014 5740.003 8100.009 814

4 結(jié)論

本文提出了一種改進(jìn)的非支配排序遺傳算法，通過擴(kuò)大初始化種群規(guī)模，來加速算法收斂；對(duì)選擇算子引入概率操作，提高了種群的多樣性；同時(shí)為了擴(kuò)大算法的搜索空間，引入了混合交叉算子。最后，使用公開的多目標(biāo)基準(zhǔn)函數(shù)進(jìn)行測(cè)試，并和基本的NSGA-II算法以及OMOPSO算法進(jìn)行對(duì)比，驗(yàn)證了本文提出的INSGA-II算法能獲得分布性和收斂性更好的Pareto前沿。未來的工作將考慮使用更復(fù)雜的公開測(cè)試函數(shù)來對(duì)INSGA-II算法進(jìn)行測(cè)試，并在交通信號(hào)配時(shí)優(yōu)化等實(shí)際工程問題中檢驗(yàn)INSGA-II算法的性能。