基于適應(yīng)度指導(dǎo)交配限制策略的重組算子與多目標(biāo)優(yōu)化研究

汪禹宏，張屹

1 引言

目前，大多數(shù)多目標(biāo)進(jìn)化算法仍是直接采用為單目標(biāo)進(jìn)化算法而設(shè)計(jì)的重組算子［1］. 事實(shí)上，單目標(biāo)優(yōu)化問題存在一個或多個全局最優(yōu)解，而多目標(biāo)優(yōu)化問題則是呈現(xiàn)出良好規(guī)則流形結(jié)構(gòu)的Pareto 解集（Pareto optimal set，PS），即連續(xù)多目標(biāo)優(yōu)化問題的PS 在變量空間上呈現(xiàn)連續(xù)分段的（m-1）維流形結(jié)構(gòu). 由于單目標(biāo)優(yōu)化與多目標(biāo)優(yōu)化最優(yōu)解的拓?fù)浣Y(jié)構(gòu)存在本質(zhì)區(qū)別，所以直接將單目標(biāo)進(jìn)化算法的重組算子應(yīng)用于多目標(biāo)進(jìn)化算法，并不能保證達(dá)到最理想的求解效果［2，3］.

有研究表明，在多目標(biāo)優(yōu)化算法中，與相似個體進(jìn)行交配可以提高新解的質(zhì)量，加速算法的收斂［4，6］. 這種做法實(shí)際上增強(qiáng)了算法的局部搜索，局部搜索機(jī)制的成功在于它隱含地利用了PS 的連通性和正則性［7］.聚類算法［8］是一類將未知標(biāo)簽的數(shù)據(jù)對象集進(jìn)行分組的無監(jiān)督學(xué)習(xí)方法，它將數(shù)據(jù)樣本劃分為多個類，同一類中的個體具有較大的相似性，可以被當(dāng)作是彼此的鄰居個體，而不同類中的個體相似度較差. 因此，我們可以在優(yōu)化算法進(jìn)化的過程中利用聚類算法發(fā)掘所求解問題Pareto 解集的結(jié)構(gòu)，利用此結(jié)構(gòu)信息引導(dǎo)個體重組，從而加速算法收斂.

近年來，圍繞多目標(biāo)優(yōu)化問題特性的利用，一些基于聚類算法的交配限制策略便成為研究熱點(diǎn)［1，9］. 張虎等［10］為了平衡開采與勘探，用一個預(yù)定義的交配限制概率δ從同一類中挑選父代，并以1-δ的概率從所有解中挑選父代. 文獻(xiàn)［11］中，在利用預(yù)定義交配限制概率構(gòu)建交配池的基礎(chǔ)上加入了自適應(yīng)的更新策略，即根據(jù)兩種父代來源在過去進(jìn)化代數(shù)中的重組效用，自適應(yīng)調(diào)整該參數(shù)δ的數(shù)值. 李欣［12］提出分別以β和1-β的概率從同一類個體和整個種群中挑選交配父代，每代演化之后又根據(jù)類的整體質(zhì)量自適應(yīng)地更新該交配限制概率. 此外，還有許多基于聚類的交配限制策略［13，14］被提出. 目前此類算法大多是采用不確定性的交配限制策略，即利用概率值去確定新解進(jìn)行全局勘探或近鄰重組，這種做法缺少對個體質(zhì)量信息的關(guān)注. 在實(shí)際的演化過程中，每一個體在收斂性和多樣性上表現(xiàn)不同，質(zhì)量較好的個體需要更多的開采；而質(zhì)量較差的個體需要更多的勘探［9，12］. 可以認(rèn)為每一代所產(chǎn)生的非支配解擁有較高的質(zhì)量，而每一代所產(chǎn)生的支配解的質(zhì)量較差. 因此我們可以將種群結(jié)構(gòu)化信息與個體質(zhì)量信息相融合以提升算法性能，即引入聚類算法從全局角度發(fā)掘種群結(jié)構(gòu)化信息，設(shè)置以個體質(zhì)量信息為主導(dǎo)的交配限制策略去完成兩類信息的融合.

基于以上分析，本文利用K-means聚類算法對種群進(jìn)行聚類，以此來優(yōu)化種群分布結(jié)構(gòu). 基于以上種群結(jié)構(gòu)化信息，設(shè)計(jì)了一種適應(yīng)度指導(dǎo)的交配限制策略（Fitness Guided Mating Restriction Strategy，F(xiàn)GMS）. 該策略根據(jù)適應(yīng)度值這一確定性信息來判斷解的支配關(guān)系，對非支配解進(jìn)行近鄰重組，對支配解做全局勘探. 將其集成至改進(jìn)的Pareto強(qiáng)度進(jìn)化算法（Improving the Strength Pareto Evolu?tionary Algorithm，SPEA2）框架中，最終提出了基于Kmeans聚類適應(yīng)度指導(dǎo)交配限制策略的多目標(biāo)進(jìn)化算法KFGEA（K-means clustering-based Fitness Guided mating re?striction multi-objective Evolutionary Algorithm）. 與傳統(tǒng)單目標(biāo)重組算子相比，KFGEA利用K-means聚類算法發(fā)掘種群規(guī)則特性來引導(dǎo)算法搜索，彌補(bǔ)了其只利用個體的質(zhì)量信息引導(dǎo)算法搜索的不足. 與現(xiàn)有的交配限制策略相比，本文首次提出利用確定性信息（適應(yīng)度值）去指導(dǎo)后續(xù)的交配限制，充分考慮到了對個體質(zhì)量信息的利用.

2 基于適應(yīng)度指導(dǎo)交配限制策略的多目標(biāo)進(jìn)化算法

2.1 KFGEA算法框架描述

算法1 給出了KFGEA 的算法框架. 在初始化階段，首先獲得初始種群P，計(jì)算初始種群的適應(yīng)度值fiti，設(shè)置初始交配限制概率β（第1 行）. 在迭代過程中，對種群P執(zhí)行K-means 聚類獲得若干子種群，其中類內(nèi)個體具有極高的相似度，而類與類之間存在較大差異（第3 行）. 對于非支配解，以概率β設(shè)置同一類中的鄰居個體構(gòu)成交配池，否則以概率1-β設(shè)置全局子種群（由相互差異較大的個體構(gòu)成）作為交配池；對于支配解，設(shè)置全局子種群構(gòu)成交配池. 基于交配池Qi，利用差分進(jìn)化算子（Differential Evolution，DE）生成當(dāng)前解xi的新解yi（第5、6 行）. 新解產(chǎn)生過程結(jié)束以后，執(zhí)行環(huán)境選擇過程對種群個體進(jìn)行更新（第8 行）.

2.2 K-means聚類算法

K-means 聚類算法是應(yīng)用最為廣泛的聚類算法之一，它是一種基于劃分的聚類方法. 所謂基于劃分的聚類算法，就是根據(jù)數(shù)據(jù)對象間的相似性將數(shù)據(jù)對象集劃分到各個獨(dú)立的子集中［8］. K-means 聚類算法將數(shù)據(jù)對象間的相似性具體化為每個對象與預(yù)先選取的各聚類中心之間的距離［15］. 該算法把每個對象分配到與之距離最近的聚類中心，以此來形成一個聚類，并通過迭代去優(yōu)化平方誤差準(zhǔn)則進(jìn)而改善各聚類質(zhì)量.

在FGMS 中，K-means 算法用來發(fā)掘種群中解的分布結(jié)構(gòu)（鄰居關(guān)系）［16］. 然后基于發(fā)掘的結(jié)構(gòu)，對于種群中的每個個體，根據(jù)適應(yīng)度這一確定性信息去判斷每個解的支配關(guān)系，進(jìn)而去決定從相同類或整個種群中挑選父個體進(jìn)行交配.

2.3 新解產(chǎn)生

算法1中SolGen操作的作用是產(chǎn)生新解.本文將MOEA/D-DE（Multi-Objective Evolutionary Algorithm based on De?composition with Differential Evolution operator）算法 中新解生成方法直接應(yīng)用于KFGEA，具體細(xì)節(jié)見算法2. 生成新解的過程由DE 算子生成初始解，然后對新生成的解應(yīng)用多項(xiàng)式變異算子進(jìn)行變異操作. 為了使新的解可行，根據(jù)變異操作前后的情況對新解進(jìn)行修復(fù).

2.4 環(huán)境選擇

SPEA2 的適應(yīng)度值由粗糙適應(yīng)度值和密度估計(jì)值共同構(gòu)成. 密度估算機(jī)制的引入使得SPEA2 的適應(yīng)度值得以精確地反映解的支配關(guān)系，這也使其成為了一種優(yōu)秀的確定性信息去指導(dǎo)交配池的構(gòu)建.

因此，KFGEA 使用SPEA2 算法［17］中提出的強(qiáng)度Pareto 環(huán)境選擇方法用來對種群進(jìn)行更新. 算法3給出了其具體步驟，其要點(diǎn)如下. 將所有P中的個體復(fù)制到P'，如果種群個數(shù)超過N，采用截?cái)嗖僮?；如果合并后的種群個數(shù)少于N則用P中的支配解填充P'. 截?cái)嗖僮鳎旱^程中，與其它個體具有最小距離的個體被移除，如果多個個體同時擁有最小的距離，則通過比較第二最小距離打破這個平局.

算法4 描述了適應(yīng)度分配的步驟. 其中，一個小的適應(yīng)度fiti意味著較少的個體支配與之對應(yīng)的xi，并且xi與其它個體之間存在著較大的距離. 當(dāng)fiti＜1 時，則表示rfi=0，即其與之對應(yīng)的xi是一個非支配解.

3 實(shí)驗(yàn)設(shè)置

3.1 測試函數(shù)與性能指標(biāo)

本文選取了GLT1~GLT6 和LZ1~LZ9，15 個目標(biāo)測試函數(shù)測試KFGEA 算法的性能. 其中，GLT 測試集有著復(fù)雜PF（Pareto Front）前沿，而LZ 測試集有著復(fù)雜PS 結(jié)構(gòu). 性能測度指標(biāo)選用反轉(zhuǎn)世代距離IGD（Inverted Generation Distance）［2］和超體積HV（Hyper?volume）［18］.

（1） 反世代距離評價指標(biāo)

反世代距離評價指標(biāo)是一個綜合性能評價指標(biāo)，它主要通過計(jì)算Pareto 面上均勻點(diǎn)到非支配解集上最小距離的平均值，來評價算法的收斂性能和分布性能［19］. 其定義如下：

其中d(x*,P)是指點(diǎn)x*與算法獲取的個體種群P之間的最短歐氏距離，|P*|是指P*中點(diǎn)的個數(shù)［20］.IGD 值越小，則代表算法的綜合性能（收斂性和多樣性）越好.

（2） 超體積指標(biāo)

超體積表示獲得的Pareto 解集與參考點(diǎn)所圍成的超立方體的體積，以實(shí)現(xiàn)對算法綜合性能的評價［21］. 其定義如下：

其中r=(r1,…,rm)表示目標(biāo)空間中Pareto 最優(yōu)解的參考點(diǎn)，[f(x),r],(x?P)表示參考點(diǎn)和非支配個體所構(gòu)成的超體積，VOL(·)表示Lebesgue 測度［20］，文獻(xiàn)［22］指出了Lebesgue 測度的具體計(jì)算方法. HV 值越大，算法的性能越好.

3.2 參數(shù)設(shè)置

為了驗(yàn)證KFGEA的性能，本文選擇多目標(biāo)差分進(jìn)化算法MOEA/D-DE［18］、改進(jìn)的Pareto強(qiáng)度進(jìn)化算法（Improv?ing the Strength Pareto Evolutionary Algorithm，SPEA2）［17］、快速非支配排序遺傳算法（Nondominated Sorting Genet?ic Algorithm II，NSGA-II）［23］、自組織多目標(biāo)進(jìn)化算法（Self-Organizing Multiobjective Evolutionary Algorithm，SMEA）［10］以及基于規(guī)則模型的多目標(biāo)分布估計(jì)算法（Regularity Model-based Multiobjective Estimation of Dis?tribution Algorithm，RM-MEDA［2］作為對照算法. 所有對照算法使用原始文獻(xiàn)中的最佳參數(shù). 公共參數(shù)以及每種算法的具體參數(shù)設(shè)置如下：

公共參數(shù)設(shè)置：種群大小N=100；最大進(jìn)化代數(shù)T=300；DE 參數(shù)F=0.5，CR=1；變異參數(shù)

MOEA/D-DE 參數(shù)設(shè)置：近鄰規(guī)模大小NS=5；近鄰搜索概率β=0.9；最大替換數(shù)目nr=2.

RM-MEDA 參數(shù)設(shè)置：Local PCA 聚類數(shù)目K=5；采樣擴(kuò)展率?=0.25.

SMEA 參數(shù)設(shè)置：初始學(xué)習(xí)率τ=0.7；近鄰池近鄰數(shù)目H=5；交配限制概率β=0.9.

KFGEA 參數(shù)設(shè)置：聚類數(shù)目K=8；交配限制概率β=0.4.

其中SPEA2 和NSGA-II 除公共參數(shù)外不需要設(shè)置特殊參數(shù). 所有算法均在Matlab 中編程實(shí)現(xiàn).

4 對比結(jié)果

為了驗(yàn)證KFGEA 的性能，我們在本節(jié)分別從性能指標(biāo)值統(tǒng)計(jì)結(jié)果、搜索效率和可視化對比三個方面分析了KFGEA 和對比算法的結(jié)果. 在搜索效率和可視化對比方面，我們選擇了GLT1~GLT6 測試套件進(jìn)行代表性分析.

4.1 性能指標(biāo)值統(tǒng)計(jì)分析

表1、表2為MOEA/D-DE、SPEA2、NSGA-II、SMEA、RM-MEDA 以及KFGEA 算法分別獨(dú)立計(jì)算GLT 測試集和LZ 測試集30次獲得的IGD 和HV 指標(biāo)值的平均值和標(biāo)準(zhǔn)差. 對于5%顯著水平下Wilcoxon 秩和檢驗(yàn)的結(jié)果，分別標(biāo)記“+”，“-”和“=”，表示在相應(yīng)測試題上，對照算法優(yōu)于、劣于或相似于KFGEA. 上述測試問題的最優(yōu)統(tǒng)計(jì)結(jié)果被突出顯示.

表1 顯示了IGD 指標(biāo)的分析結(jié)果，其中MOEA/DDE、SPEA2、NSGA-II、SMEA、RM-MEDA 和KFGEA 分別取得2、0、0、2、1 和10 個最佳指標(biāo)值；表2 顯示了HV指標(biāo)的分析結(jié)果，上述每個算法分別獲得2、0、1、2、2和8 個最佳指標(biāo)值. 在所有其他對照算法的30 個比較結(jié)果中，對于5%顯著水平下Wilcoxon 秩和檢驗(yàn)的表現(xiàn)，KFGEA 算法獲得了18、24、25、22 和19 個顯著優(yōu)勢IGD 和HV 指標(biāo).

總體來說，與對照算法相比，KFGEA 在具有復(fù)雜PF 的GLT 測試集以及具有復(fù)雜PS 的LZ 測試集上具有一定優(yōu)勢.

4.2 搜索效率分析

為了分析KFGEA算法的搜索效率，圖1給出了所有算法對GLT 測試題進(jìn)行30次獨(dú)立運(yùn)算后的最優(yōu)IGD 指標(biāo)值的演化曲線. 從圖1中可以看出，對于GLT2、GLT3、GLT4、GLT5、GLT6，KFGEA均能夠以最快的速度獲得最小的IGD 指標(biāo)值；對于GLT1，KFGEA 雖然未表現(xiàn)出最快的收斂速度，但是最終會獲得最小的IGD 指標(biāo)值. 圖中對比結(jié)果顯示，對于GLT 系列問題KFGEA 算法總體上具有不俗的收斂速度和最高的搜索效率.

4.3 可視化對比分析

為了進(jìn)一步求證KFGEA 的性能，圖2 繪制了當(dāng)MOEA/D-DE、SMEA、RM-MEDA 和KFGEA 求解GLT3和GLT5時獲得的平均IGD 值的代表性帕累托前沿. 圖2 顯示對于GLT3 測試問題，相較于對照算法KFGEA 表現(xiàn)出了優(yōu)異的收斂性與多樣性. 對于GLT5 測試問題，MOEA/D-DE 雖然收斂到了該問題真實(shí)的帕累托前沿，但其多樣性較差；SMEA 沒有很好地貼合真實(shí)的帕累托前沿；RM-MEDA 和KFGEA 在該問題上有著不錯的表現(xiàn)，但顯然是KFGEA具有更出色的收斂性和一致性.

秦虹路現(xiàn)狀東西向下穿寧蕪鐵路，涵洞車道規(guī)模（雙向兩車道）與限高（僅3m）均收到較大制約，極易造成擁堵。優(yōu)化后，將鐵路走廊改造為城市支路和綠道，同時對該節(jié)點(diǎn)豎向進(jìn)行優(yōu)化，消除凈空不足的安全隱患，也與周邊地塊豎向?qū)崿F(xiàn)良好銜接。同時對新平面交叉口進(jìn)行渠化設(shè)計(jì)，合理分配機(jī)動車與慢行空間路權(quán)。

表1 MOEA/D?DE、SPEA2、NSGA?II、SMEA、RM?MEDA和KFGEA求解GLT和LZ測試集30次的IGD的平均值（標(biāo)準(zhǔn)差）

表2 MOEA/D?DE、SPEA2、NSGA?II、SMEA、RM?MEDA和KFGEA求解GLT和LZ測試集30次的HV的平均值（標(biāo)準(zhǔn)差）

綜上所述，通過性能指標(biāo)值的統(tǒng)計(jì)比較、收斂速度和可視化比較，可以得出結(jié)論：相較于MOEA/D-DE、SPEA2、NSGA-II、SMEA 和RM-MEDA，KFGEA 對于PS或PF 形狀復(fù)雜的MOPs具有最佳的解性能.

圖1 MOEA/D-DE,SPEA2,NSGA-II,SMEA,RM-MEDA和KFGEA求解GLT測試集30次獲得最優(yōu)IGD 指標(biāo)值得變化曲線

圖2 MOEA/D-DE,SMEA,RM-MEDA和KFGEA 獲得的代表性分布前沿(Approximation Fronts,AF)

5 算法控制參數(shù)靈敏度分析

在KFGEA 算法性能參數(shù)靈敏度的分析中，選用GLT 測試集對每個具有不同參數(shù)的KFGEA 算法進(jìn)行20 次運(yùn)算，并分析性能指標(biāo)值的統(tǒng)計(jì)結(jié)果.

由圖3 可見，在β值均為0.4；不同聚類數(shù)目的條件下，KFGEA 的IGD 指標(biāo)值在GLT3、GLT4 和GLT6 測試問題中產(chǎn)生了輕微波動，對于其余測試問題聚類數(shù)目對算法的性能指標(biāo)影響很小. 這表明聚類數(shù)目對算法整體性能的影響不大.

從圖4 中可以看出，在聚類數(shù)目K=8；不同β值的條件下，除了在GLT6 和GLT3 測試問題中IGD 值出現(xiàn)了一些浮動，其余測試問題中KFGEA 性能指標(biāo)的波動很小. 這表明交配限制概率β值對算法整體性能的影響不大.

綜上所述，KFGEA 對控制參數(shù)值不是特別敏感，該算法具有良好的魯棒性.

圖3 KFGEA 算法在不同K值下GLT 系列套件獨(dú)立運(yùn)行20 次的IGD指標(biāo)值的平均值和標(biāo)準(zhǔn)差

圖4 KFGEA 算法在不同β值下GLT 系列套件獨(dú)立運(yùn)行20 次的IGD指標(biāo)值的平均值和標(biāo)準(zhǔn)差

6 結(jié)束語

本文選擇了帶有復(fù)雜PF 結(jié)構(gòu)的GLT 測試集和具有復(fù)雜PF 結(jié)構(gòu)的LZ 測試集作為求解問題；選取五種經(jīng)典多目標(biāo)優(yōu)化算法與KFGEA 算法進(jìn)行對比測試. 實(shí)驗(yàn)結(jié)果表明KFGEA 算法在IGD 和HV 指標(biāo)、搜索效率和可視化對比三個方面均具有明顯的優(yōu)勢. 這說明Kmeans 聚類算法的引進(jìn)可以充分利用多目標(biāo)優(yōu)化問題的規(guī)則特性，進(jìn)而去提高進(jìn)化算法的性能；FGMS 能提高搜索效率，利用適應(yīng)度這一確定性信息去維持算法收斂性與多樣性的平衡. 后續(xù)工作將圍繞KFGEA 算法的實(shí)際應(yīng)用而展開.