基于多目標(biāo)演化的模糊認(rèn)知圖學(xué)習(xí)算法

方 偉, 張齡之

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院, 江蘇 無(wú)錫 214122)

0 引 言

認(rèn)知圖是計(jì)算智能領(lǐng)域的一個(gè)新興的研究熱點(diǎn),它提供了一個(gè)有效的軟計(jì)算工具來(lái)支持基于先驗(yàn)知識(shí)的自適應(yīng)行為[1]。文獻(xiàn)[2]在古典認(rèn)知圖的基礎(chǔ)之上,融合認(rèn)知圖論和模糊集理論,提出模糊認(rèn)知圖(fuzzy cognitive maps, FCMs)。由于模糊邏輯能夠比三值邏輯攜帶更多的信息,使得FCMs在定性推理中起著更大的作用,并成為目前認(rèn)知圖研究的主流,廣泛應(yīng)用于工業(yè)、軍事、科技、醫(yī)學(xué)、建筑等領(lǐng)域[3-7]。

FCMs用來(lái)解釋系統(tǒng)中的概念、實(shí)體或者數(shù)學(xué)變量之間因果關(guān)系,利用有向加權(quán)圖來(lái)建模,即由結(jié)點(diǎn)與結(jié)點(diǎn)之間的有向弧組成。結(jié)點(diǎn)間有向弧的權(quán)值反映了兩個(gè)結(jié)點(diǎn)間的連接強(qiáng)度和類型。因此對(duì)FCMs的學(xué)習(xí)是盡可能找到準(zhǔn)確的權(quán)值。FCMs的學(xué)習(xí)算法可大致分3類,分別是基于Hebbian的方法,基于進(jìn)化算法的方法以及基于Hebbian和進(jìn)化算法的混合方法。文獻(xiàn)[8]提出的非線性Hebbian學(xué)習(xí)(nonlinear hebbian learning,NHL)算法是基于Hebbian方法中的代表算法,該算法需要專家的介入,而且對(duì)專家的知識(shí)精確性要求較高,但是在一些復(fù)雜領(lǐng)域的專家知識(shí)很難得到,容易出現(xiàn)初始網(wǎng)絡(luò)無(wú)法重構(gòu)的現(xiàn)象。為了解決這一問(wèn)題,研究人員把進(jìn)化算法應(yīng)用于FCMs,使得FCMs可以自動(dòng)選擇數(shù)據(jù)。這種基于進(jìn)化算法的選擇策略,實(shí)質(zhì)上是將選擇問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題,通過(guò)設(shè)定合適目標(biāo)函數(shù)的方法找到問(wèn)題的最優(yōu)解。文獻(xiàn)[9]提出了用于學(xué)習(xí)FCMs的實(shí)數(shù)稀疏編碼遺傳算法(sparse real-coded genetic algorithms,SRCGA),該算法在實(shí)數(shù)編碼遺傳算法(real-coded genetic algorithms,RCGA)的基礎(chǔ)之上采用密度估計(jì)參數(shù),引導(dǎo)算法的學(xué)習(xí)過(guò)程。然而,預(yù)定義的密度參數(shù)在現(xiàn)實(shí)生活中很難求出,使得SRCGA在應(yīng)用范圍上存在一定局限性。由于系統(tǒng)的復(fù)雜性、概念間的相互作用及外部強(qiáng)迫函數(shù)的作用,概念間的關(guān)系可能會(huì)發(fā)生改變,甚至變?yōu)橄嗷ッ艿年P(guān)系,而FCMs不具有非單調(diào)推理的能力,這使得FCMs學(xué)習(xí)算法無(wú)法自適應(yīng)于外界的環(huán)境變化。為了解決該問(wèn)題,研究人員將多目標(biāo)演化算法(multi-objective optimization evolutionary algorithms, MOEA)[10]用于FCMs的學(xué)習(xí)。該類算法針對(duì)不同的優(yōu)先級(jí),對(duì)多個(gè)目標(biāo)函數(shù)進(jìn)行折中處理以盡可能使所有目標(biāo)同時(shí)達(dá)到最優(yōu),從而得到更為準(zhǔn)確的FCMs。文獻(xiàn)[11]設(shè)計(jì)了兩個(gè)目標(biāo),使得輸入的歷史數(shù)據(jù)在不同數(shù)據(jù)密度情況下依然可以獲得較優(yōu)秀的解,從而為決策者提供不同屬性的候選方案。多目標(biāo)演化算法以非支配占優(yōu)和精英保留機(jī)制為主要特點(diǎn),可以對(duì)不同目標(biāo)進(jìn)行折中處理,單次運(yùn)行后可以獲得一組具有代表性的帕累托(Pareto)最優(yōu)解集合,使各個(gè)目標(biāo)盡可能同時(shí)達(dá)到最優(yōu)?；谥笜?biāo)的多目標(biāo)演化算法(indicator-based evolutionary algorithm,IBEA)[12]利用二元性指標(biāo)直接計(jì)算適應(yīng)度,提高了算法的收斂性,但是在維護(hù)解的多樣性方面表現(xiàn)并不理想。文獻(xiàn)[13]通過(guò)聚合函數(shù)權(quán)重矢量將子問(wèn)題劃分到指定鄰域,通過(guò)子問(wèn)題間的優(yōu)化信息來(lái)優(yōu)化個(gè)體本身,提出了基于分解的多目標(biāo)演化算法(multi-objective evolutionary algorithm based on decomposition,MOEA/D),能夠很好地解決一定規(guī)模范圍內(nèi)相異的多目標(biāo)問(wèn)題;基于外部存儲(chǔ)引導(dǎo)的分解多目標(biāo)演化算法(external archive guided MOEA/D,EAG-MOEA/D)[14]利用分解策略和非支配排序策略分別對(duì)內(nèi)部種群和外部種群進(jìn)行維護(hù),使每一代的搜索區(qū)域更加明確,有效提高了多目標(biāo)優(yōu)化算法的搜索效率;基于排序和選擇方法的MOEA/D(MOEA/D with sorting and selection,MOEA/D-SAS)[15]通過(guò)分解排序策略(decomposition based sorting,DBS)和角度選擇策略(angle based selection,ABS),可以有效處理不規(guī)則的前沿,實(shí)現(xiàn)收斂性和多樣性之間的平衡。

上述研究中,通過(guò)將多目標(biāo)優(yōu)化算法應(yīng)用于模糊認(rèn)知圖,雖然能夠有效地獲得較為優(yōu)秀的解,但依然存在一些不足:

(1) 以多個(gè)目標(biāo)為優(yōu)化對(duì)象對(duì)FCM進(jìn)行學(xué)習(xí)的方法的出現(xiàn),很好地降低了FCM對(duì)專家經(jīng)驗(yàn)的依賴,但現(xiàn)有的算法在學(xué)習(xí)過(guò)程中僅對(duì)權(quán)值進(jìn)行單方面優(yōu)化,造成模型擬合準(zhǔn)確程度不足;

(2) 將現(xiàn)有的多目標(biāo)進(jìn)化算法應(yīng)用于FCM學(xué)習(xí),雖然可以找到較為精確的權(quán)值,但是隨著節(jié)點(diǎn)數(shù)目的增多,候選解的數(shù)目也會(huì)以指數(shù)級(jí)的速度增加,容易引起算法的收斂速度降低;同時(shí),現(xiàn)有的多目標(biāo)進(jìn)化算法無(wú)法保證所得的解集分布較為均勻,導(dǎo)致算法容易陷入局部最優(yōu),使得現(xiàn)有的多目標(biāo)進(jìn)化算法無(wú)法適用于規(guī)模較大的FCM學(xué)習(xí);

(3) 現(xiàn)有多目標(biāo)FCM學(xué)習(xí)算法中的目標(biāo)設(shè)計(jì)都偏重于對(duì)真實(shí)權(quán)重矩陣和學(xué)習(xí)權(quán)重矩陣之間的差異進(jìn)行優(yōu)化,忽略了響應(yīng)序列對(duì)真實(shí)權(quán)重矩陣的影響,容易造成單個(gè)目標(biāo)的解超出規(guī)定范圍。

本文針對(duì)FCMs學(xué)習(xí)過(guò)程中僅對(duì)權(quán)值進(jìn)行優(yōu)化而造成模型擬合準(zhǔn)確程度不足的缺陷,提出了一種基于多目標(biāo)演化的模糊認(rèn)知圖學(xué)習(xí)算法(multiobjective evolutionary algorithm based on coordinate transformation for FCM, MOEA/CT-FCM)。該學(xué)習(xí)算法首先設(shè)計(jì)了基于坐標(biāo)變換的MOEA(multi-objective optimization evolutionary algorithms based on coordinate transformation, MOEA/CT),該方法通過(guò)坐標(biāo)變換(coordinate transformation, CT)策略賦予目標(biāo)空間中個(gè)體新的適應(yīng)度,并將此適應(yīng)度值作為個(gè)體的收斂信息(convergence information, CI),完成個(gè)體CI的賦值,同時(shí),采用一種新的外部存檔策略,當(dāng)精英個(gè)體進(jìn)入存檔集后,根據(jù)上一步得到的CI,對(duì)存檔集中的個(gè)體進(jìn)行篩選,從而尋找到有效收斂個(gè)體,加速收斂過(guò)程,進(jìn)一步,引入一種基于Lp-norm的密度篩選方法,利用Fractional距離代替歐式距離,以準(zhǔn)確反映個(gè)體間的擁擠程度,能夠防止鄰近個(gè)體同時(shí)被選入存檔集,使所得解集分布更加均勻;接著,通過(guò)研究FCMs的固有特性,設(shè)計(jì)出結(jié)點(diǎn)間權(quán)值誤差與誤差權(quán)重2個(gè)求解目標(biāo),將FCMs的學(xué)習(xí)問(wèn)題抽象為兩目標(biāo)優(yōu)化問(wèn)題,以防止單個(gè)目標(biāo)的解集超出規(guī)定范圍的問(wèn)題;最后再將MOEA/CT算法應(yīng)用于FCMs的模型學(xué)習(xí)。本文采用實(shí)際工程中9結(jié)點(diǎn),12結(jié)點(diǎn)和24結(jié)點(diǎn)的FCMs進(jìn)行仿真實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明本文提出的 MOEA/CT-FCM算法,相比于MOEA-FCM、RCGA、分治實(shí)數(shù)編碼遺傳(devide and conquer RCGA, D&C RCGA)、基于數(shù)據(jù)控制NHL算法(data and controlling NHL,DD-NHL)、NHL等算法,能夠更準(zhǔn)確地表達(dá)結(jié)點(diǎn)間的因果關(guān)系,降低對(duì)專家經(jīng)驗(yàn)的依賴性。

1 模糊認(rèn)知圖

FCMs把知識(shí)蘊(yùn)含在概念結(jié)點(diǎn)及概念結(jié)點(diǎn)間的關(guān)系中,通過(guò)概念間的依賴與反饋來(lái)模擬系統(tǒng)的動(dòng)態(tài)行為,其數(shù)學(xué)模型包括概念結(jié)點(diǎn)C,權(quán)值w,狀態(tài)值A(chǔ),激活/閾值函數(shù)g(·)等組成部分[16]。

由Nn個(gè)概念結(jié)點(diǎn)所組成的結(jié)點(diǎn)矩陣可表示為

C=[C1,C2,…,CNn]

(1)

式中,Ci∈[0,1],i=1,2,…,Nn。這些結(jié)點(diǎn)之間的模糊因果關(guān)系可以用NN×NN維的鄰接權(quán)重矩陣表示為

(2)

(3)

(4)

式中,β是用來(lái)規(guī)定函數(shù)在0點(diǎn)附近步長(zhǎng)的參數(shù),β的取值一般設(shè)置為5[19]。

2 MOEA/CT-FCM

2.1 MOEA/CT

針對(duì)基于傳統(tǒng)占優(yōu)機(jī)制的經(jīng)典多目標(biāo)智能算法在迭代過(guò)程中對(duì)精英種群判斷力較弱,從而導(dǎo)致算法收斂緩慢和無(wú)法得到最優(yōu)解的問(wèn)題,本文在MOEA基礎(chǔ)上提出了一種基于坐標(biāo)變換的多目標(biāo)演化算法,進(jìn)行了3個(gè)部分改進(jìn):坐標(biāo)變換策略、外部存儲(chǔ)器更新策略和密度篩選策略。

2.1.1 坐標(biāo)變換策略

為了尋找更為有效的收斂個(gè)體,以加速完成收斂過(guò)程,并快速逼近完整的Pareto真實(shí)前沿,MOEA/CT算法設(shè)計(jì)了坐標(biāo)變換策略。首先以目標(biāo)空間中的每個(gè)個(gè)體i為原點(diǎn)依次建立坐標(biāo)系,將其余個(gè)體以目標(biāo)值為基準(zhǔn)投影至新坐標(biāo)系中,產(chǎn)生新的個(gè)體,并將個(gè)體i與新個(gè)體的歐氏距離和作為個(gè)體i的新適應(yīng)度Dpi表示為

(5)

以兩目標(biāo)優(yōu)化算法為例,來(lái)說(shuō)明坐標(biāo)變換模型的建立及個(gè)體適應(yīng)度調(diào)整方式,如圖1所示,點(diǎn)A(3,3),B(1,6),C(6,2),D(8,1)為目標(biāo)空間中的4個(gè)非支配解,現(xiàn)以點(diǎn)A為中心建立坐標(biāo)系,計(jì)算各個(gè)體在新坐標(biāo)系下距點(diǎn)A的歐式距離。點(diǎn)B(1,6)在目標(biāo)f1上優(yōu)于點(diǎn)A,則將點(diǎn)B沿f2方向平移到新坐標(biāo)系中,得到調(diào)整后的點(diǎn)B′(-2,0),同理可得C′(0,-1),D′(0,-2),可得個(gè)體A的新適應(yīng)度為DA=5。

圖1 CT策略示意圖Fig.1 Schematic diagram of CT strategy

2.1.2 改進(jìn)的外部存儲(chǔ)器更新策略

(6)

式中,g表示當(dāng)前迭代次數(shù);gmax表示迭代總次數(shù);dj(min)、dj(max)分別表示經(jīng)調(diào)整后其余個(gè)體距個(gè)體j的最小值與最大值;α值表示目標(biāo)函數(shù)個(gè)數(shù)。

最終通過(guò)對(duì)非支配解集進(jìn)行進(jìn)一步篩選,尋找到更為有效的收斂個(gè)體,加速收斂過(guò)程。

α的選取會(huì)對(duì)算法的收斂性造成一定的影響,本文以ZDT1(E.Zitzler，K.Deb and L.Thiele)函數(shù)為例,比較不同取值的α對(duì)算法性能的影響。如圖2所示,隨著迭代次數(shù)的增加,收斂性指標(biāo)γ都呈下降趨勢(shì),當(dāng)α=2時(shí),γ下降速率較α取其他值時(shí)更具優(yōu)勢(shì),說(shuō)明α取值為2時(shí),算法的收斂速率最快。圖2中各曲線在開始時(shí)都有一定的波動(dòng),這是由于MOEA/CT算法在初始化階段采用隨機(jī)選取個(gè)體的方式,導(dǎo)致算法的收斂過(guò)程需要經(jīng)過(guò)多次的迭代才能趨于穩(wěn)定,而從圖2中可以看出,當(dāng)α取值為2時(shí),波動(dòng)的次數(shù)較少,說(shuō)明其到達(dá)穩(wěn)定狀態(tài)所需的迭代次數(shù)較少。因此本文α取值為2。

圖2 不同α值對(duì)算法性能的影響Fig.2 Effects of different α values on the performance of the algorithm

2.1.3 改進(jìn)的密度選擇策略

在現(xiàn)有多目標(biāo)優(yōu)化算法中,經(jīng)常使用的擁擠密度估計(jì)方法如:Mahalanobis、Euclidean(L2-norm)平均距離算法等[20-22],在目標(biāo)函數(shù)個(gè)數(shù)增多的情況下并不能準(zhǔn)確反映個(gè)體間的擁擠程度[23]。文獻(xiàn)[23-24]指出,相比L2-norm距離,Fractional距離(Lp-norm)在處理高維空間問(wèn)題時(shí)效率更高。文獻(xiàn)[25]在上述結(jié)論基礎(chǔ)上,通過(guò)實(shí)驗(yàn)證明,通過(guò)減小p值可以使最遠(yuǎn)相鄰個(gè)體和最近相鄰個(gè)體的計(jì)算結(jié)果形成較大反差,因此MOEA/CT采用p=1/m時(shí)的Fractional距離代替歐式距離計(jì)算擁擠距離,以使非支配個(gè)體分布更均勻。

為了驗(yàn)證MOEA/CT算法所設(shè)計(jì)的3個(gè)策略的有效性,本文采用世代距離指標(biāo)(generational distance,GD)[26],均勻性指標(biāo)(spacing,SP)[27],收斂性指標(biāo)γ[28],在ZDT1和ZDT2函數(shù)上進(jìn)行實(shí)驗(yàn)。分別選取MOEA算法基礎(chǔ)上引入坐標(biāo)變換策略(transformation function,TF)、坐標(biāo)變換策略結(jié)合改進(jìn)的外部存儲(chǔ)器策略(TF evolutionary algorithm,TFEA)以及坐標(biāo)變換策略與改進(jìn)外部存儲(chǔ)器策略結(jié)合密度選擇3種情況,下文簡(jiǎn)稱MOEA/TF、MOEA/TFEA及MOEA/CT算法,與MOEA算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果如表1所示,表1中數(shù)據(jù)為各算法迭代100次,獨(dú)立運(yùn)行30次所取的平均值。從表1可以看出,采用了本文提出策略的3種算法,實(shí)驗(yàn)結(jié)果較MOEA更優(yōu)。MOEA/TF算法僅選取經(jīng)過(guò)坐標(biāo)變換后適應(yīng)度較大的個(gè)體加入外部存儲(chǔ)器,直至外部存儲(chǔ)器滿為止。表1中,MOEA/TF算法的GD和γ比MOEA算法更小,說(shuō)明采用坐標(biāo)轉(zhuǎn)換策略后,算法所選取的個(gè)體與真實(shí)前沿較為接近,但是隨著迭代次數(shù)的增多,非支配解數(shù)量成倍增加,僅依靠坐標(biāo)變換策略無(wú)法對(duì)大量非支配解進(jìn)行有效篩選,因此本文設(shè)計(jì)了更為有效的外部存儲(chǔ)器篩選策略。MOEA/TFEA算法所得結(jié)果的GD和γ值較MOEA/TF算法更小,說(shuō)明加入本文提出的外部存儲(chǔ)器策略之后,能夠使得算法所選擇的個(gè)體更加貼近真實(shí)前沿。由于算法未對(duì)所獲的解集進(jìn)行合適的密度篩選,導(dǎo)致MOEA/TF與MOEA/TFEA算法的SP值并不理想,因此本文加入了Lp-norm密度篩選策略,以使得所選解集的密度更加均勻。同樣從表1中可以看出,MOEA/CT算法的SP值較小,說(shuō)明密度篩選策略能夠使得所選解集的密度更加均勻。

表1 不同策略對(duì)算法的影響

為了充分檢驗(yàn)MOEA/CT算法的性能,本文還將所提算法與改進(jìn)的非支配排序遺傳算法(improved non-dominated sorting genetic algorithm,NSGA-Ⅱ)[29], 多目標(biāo)粒子群算法(multi-objective particle swarm optimization,MOPSO)[30], NSGA-Ⅲ[31], 改進(jìn)的兩階段存儲(chǔ)法(improved two-archive algorithm,Two_arch2)[25]這4種算法進(jìn)行對(duì)比。本文采用與文獻(xiàn)[9]一樣的模擬二進(jìn)制交叉(simulated binary crossover,SBX)交叉算子和多項(xiàng)式變異算子,所有對(duì)比算法的控制參數(shù)設(shè)置均采用相應(yīng)原文文獻(xiàn)中的推薦值,實(shí)驗(yàn)參數(shù)如表2所示。

實(shí)驗(yàn)結(jié)果均為各算法獨(dú)立運(yùn)行30次所對(duì)應(yīng)的各測(cè)試指標(biāo)平均值,統(tǒng)計(jì)結(jié)果如表3所示,各項(xiàng)對(duì)比實(shí)驗(yàn)中的最優(yōu)結(jié)果均用黑體加粗表示。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

表3 5種算法在ZDT1與ZDT2上的實(shí)驗(yàn)結(jié)果

ZDT1函數(shù)非劣解集在目標(biāo)函數(shù)空間是凸的,從表3可以看出,MOEA/CT、Two_arch2,NSGA-Ⅲ都可以很好逼近真實(shí)Pareto前沿,但是MOEA/CT算法具有更好的分布性。NSGA-Ⅲ沒有覆蓋整個(gè)Pareto前沿面,NSGA-Ⅱ和MOPSO算法雖然有收斂趨勢(shì),但并沒有完全收斂。MOEA/CT在ZDT1函數(shù)所得到的前沿如圖3所示。

圖3 MOEA/CT的ZDT1函數(shù)前沿Fig.3 MOEA/CT front of ZDT1 function

ZDT2函數(shù)的非劣解集在目標(biāo)函數(shù)空間是非凸的,本算法在各測(cè)試指標(biāo)上表現(xiàn)都很優(yōu)秀,分布均勻,貼近真實(shí)前沿且解集的分布寬廣度與真實(shí)前沿一致。NSGA-Ⅲ在求解ZDT2時(shí),分布性略優(yōu)于MOEA/CT算法。但是較大的GD值說(shuō)明其未能逼近整個(gè)真實(shí)前沿面。MOPSO算法的GD與γ值較小,但是SP值較大,說(shuō)明其陷入局部最優(yōu)無(wú)法跳出。MOEA/CT在ZDT2函數(shù)所得到的前沿如圖4所示。

圖4 MOEA/CT的ZDT2函數(shù)前沿Fig.4 MOEA/CT front of ZDT2 function

2.2 面向FCMs學(xué)習(xí)的兩目標(biāo)優(yōu)化模型設(shè)計(jì)

在多目標(biāo)優(yōu)化中,通過(guò)Pareto最優(yōu)解來(lái)評(píng)價(jià)所得解集的優(yōu)劣性,優(yōu)劣性就是指在目標(biāo)函數(shù)的解集中對(duì)其中一個(gè)或多個(gè)子目標(biāo)函數(shù)的進(jìn)一步優(yōu)化,而不會(huì)引起其他子目標(biāo)函數(shù)的解超出規(guī)定范圍,即多目標(biāo)優(yōu)化最終會(huì)得到一組互相支配的解的集合。

對(duì)FCMs學(xué)習(xí)的目的是通過(guò)優(yōu)化權(quán)值矩陣,盡可能確定每一對(duì)概念結(jié)點(diǎn)之間的真實(shí)關(guān)系。因此,算法將所求得的響應(yīng)序列和現(xiàn)有的響應(yīng)序列之間的最小差異設(shè)定為第一目標(biāo),表示為

(7)

第2個(gè)目標(biāo)是誤差比重,用來(lái)評(píng)估真實(shí)權(quán)重矩陣和學(xué)習(xí)權(quán)重矩陣的差異,并與全局?jǐn)?shù)據(jù)誤差進(jìn)行比較。結(jié)點(diǎn)i的誤差比重計(jì)算方式為

(8)

由FCM性質(zhì)可知,希望通過(guò)算法得到盡可能小的結(jié)點(diǎn)差異和權(quán)重差異,因此誤差比重越小,代表算法所得到的解集越接近真實(shí)解集。多目標(biāo)優(yōu)化是對(duì)多個(gè)相互矛盾、相互影響的目標(biāo)進(jìn)行優(yōu)化,以求得最優(yōu)解,能夠同時(shí)滿足多個(gè)矛盾的目標(biāo)函數(shù)。由式(7)、式(8)可推知,當(dāng)式(7)的值增加時(shí),式(8)的值會(huì)在一定程度上減小,而當(dāng)式(8)的值增加時(shí),式(7)的值不一定增加。實(shí)際運(yùn)行所得結(jié)果如圖5所示,其中權(quán)重值和結(jié)點(diǎn)值的取值范圍為[0,1],可以看出兩個(gè)目標(biāo)函數(shù)之間相互排斥。因此,本文所設(shè)計(jì)的兩個(gè)最小化目標(biāo)是相互矛盾且相互影響的,符合多目標(biāo)定義且適用于FCMs系統(tǒng)。

圖5 兩個(gè)目標(biāo)的關(guān)系Fig.5 Relationship between the two objectives

2.3 MOEA/CT-FCM

在MOEA/CT中,每一個(gè)候選解由一維向量組成,而在 MOEA/CT-FCM中每個(gè)候選解由一個(gè)權(quán)重矩陣組成。為了方便起見,把2維權(quán)重矩陣轉(zhuǎn)化為1維的向量,若權(quán)重矩陣如式(2)所示,則轉(zhuǎn)化后的Nn×Nn的權(quán)重可表示為

w=[w11,w12,…,w1Nn,w21,w22,…,

w2Nn,…,wNn1,…,wNnNn]

(9)

式中,w的取值范圍為[-1,1]。

MOEA/CT-FCM算法的具體實(shí)現(xiàn)過(guò)程如下:

步驟1生成初始種群,即初始權(quán)重矩陣;

步驟2進(jìn)行非支配排序后執(zhí)行進(jìn)化操作生成子代種群,合并種群后進(jìn)行非支配排序選擇;

步驟3判斷剩余的種群數(shù)量是否大于預(yù)設(shè)值,若小于預(yù)設(shè)值則繼續(xù)執(zhí)行步驟2直至數(shù)量大于預(yù)設(shè)值;

步驟4若數(shù)量大于預(yù)設(shè)值進(jìn)行坐標(biāo)變換找到收斂性較好的個(gè)體,通過(guò)函數(shù)篩選更新外部存儲(chǔ)器,之后進(jìn)行密度篩選,得到不大于種群數(shù)量的精英種群;

步驟5判斷是否達(dá)到總迭代次數(shù),若未達(dá)到則返回步驟2,反之,運(yùn)行結(jié)束。

MOEA/CT-FCM的具體過(guò)程如下:

算法1基于多目標(biāo)演化的模糊認(rèn)知圖學(xué)習(xí)算法

輸入初始種群Pt,迭代次數(shù)gmax,種群數(shù)目N,標(biāo)識(shí)目標(biāo)函數(shù)個(gè)數(shù)m

輸出新種群Pt+1

2 初始化迭代次數(shù):g=1;

3 對(duì)初始種群Pt進(jìn)行非支配選擇,選擇出其中互相不支配的個(gè)體,將結(jié)果存入種群Qt;

4 While |Qt|≤N{

7 }

9 Fori=1:|Qt| {

10 Forj=1:|Qt| {

11 Fork=1:m{

14 }

15 }

17 }

19 Fori=1:|Qt′| {

20 對(duì)個(gè)體進(jìn)行歸一化操作,得到歸一化后的新個(gè)體適應(yīng)度γi;

21 利用式(6)計(jì)算Oi;

22 將γi

23 }

24 利用密度選擇策略,對(duì)Qt中的個(gè)體進(jìn)行篩選,將結(jié)果存入新種群Pt+1

本文主要的運(yùn)算量是計(jì)算經(jīng)過(guò)坐標(biāo)變換策略調(diào)整及收斂距離、Pareto占優(yōu)過(guò)程和擁擠距離的計(jì)算。若有m個(gè)目標(biāo),種群數(shù)量為N,計(jì)算坐標(biāo)變換和收斂距離的復(fù)雜度為O((mN)2),非支配排序所需計(jì)算復(fù)雜度為O(NlogM-2N)[32],求解擁擠距離所需計(jì)算復(fù)雜度最大為O((mN)2)。綜上所述,本算法的時(shí)間復(fù)雜度為max(O(NlogM-2N),O((mN)2))。

3 實(shí)驗(yàn)結(jié)果

本文對(duì)3種不同規(guī)模的實(shí)際FCM進(jìn)行學(xué)習(xí),分別來(lái)源于9結(jié)點(diǎn)的工廠監(jiān)控系統(tǒng)[33],12結(jié)點(diǎn)的巴西亞馬遜森林砍伐模型[34]和24結(jié)點(diǎn)的某學(xué)校教育軟件模型[35]。9結(jié)點(diǎn)模型與12結(jié)點(diǎn)模型的概念結(jié)點(diǎn)為確定性結(jié)點(diǎn),24結(jié)點(diǎn)模型為隨機(jī)不確定性結(jié)點(diǎn)。

3.1 實(shí)驗(yàn)參數(shù)

MOEA/CT-FCM應(yīng)用于9結(jié)點(diǎn)模型初始參數(shù)設(shè)置與文獻(xiàn)[33]相同,12結(jié)點(diǎn)模型初始參數(shù)設(shè)置與文獻(xiàn)[34]相同,24結(jié)點(diǎn)模型初始參數(shù)為范圍在[0,1]之間的隨機(jī)設(shè)定值,具體參數(shù)設(shè)置如表4所示,其中，Nn表示結(jié)點(diǎn)個(gè)數(shù);Ns表示響應(yīng)序列個(gè)數(shù);Ns表示時(shí)間序列數(shù)目(設(shè)定方式詳見第3.2節(jié))。

表4 MOEA/CT-FCM實(shí)驗(yàn)參數(shù)設(shè)置

分別選取Data_error, Model_Error, Out_of_Sample_Error和SS_Mean作為算法的評(píng)價(jià)指標(biāo)。其中,Data_error是目標(biāo)函數(shù)f1(W)。模型誤差Model_Error用以評(píng)價(jià)算法獲得的權(quán)值與初始權(quán)值之間的差異,表示為

(10)

Out_of_Sample_Error用于評(píng)價(jià)算法的擬合能力,表示為

(11)

SS_Mean利用統(tǒng)計(jì)特性Specificity和Sensitivity來(lái)驗(yàn)證學(xué)習(xí)算法是否能夠準(zhǔn)確預(yù)測(cè)出2個(gè)結(jié)點(diǎn)之間存在的邊,并把模糊認(rèn)知圖學(xué)習(xí)問(wèn)題擴(kuò)展和轉(zhuǎn)換成了二分類問(wèn)題。當(dāng)權(quán)重的絕對(duì)值大于臨界值時(shí)被置為1,而小于臨界值時(shí)則置為0。為了進(jìn)行比較,本文將采用與文獻(xiàn)相同的臨界值以及正負(fù)結(jié)果的定義,此處設(shè)臨界值為0.05。另外,本算法中將權(quán)重的絕對(duì)值小于0.05的邊識(shí)別為正邊,否則該邊被識(shí)別為負(fù)邊。轉(zhuǎn)換過(guò)程中,T代表正確識(shí)別,F代表錯(cuò)誤識(shí)別,P代表正邊,N代表負(fù)邊。式(12)、式(13)中N表示滿足條件的邊的數(shù)目。SS_Mean值越接近1,表示算法預(yù)測(cè)權(quán)值的準(zhǔn)確性越強(qiáng),其參數(shù)設(shè)置如表5所示。

表5 SS_Mean參數(shù)設(shè)置

Specificity、Sensitivity、SS_Mean表示為

(12)

(13)

(14)

3.2 時(shí)間序列數(shù)目確定

為了能夠降低MOEA/CT-FCM的計(jì)算代價(jià),使FCM盡快達(dá)到較穩(wěn)定的學(xué)習(xí)狀態(tài),本文針對(duì)模糊認(rèn)知圖時(shí)間序列數(shù)目的確定進(jìn)行實(shí)驗(yàn)。為保證實(shí)驗(yàn)的客觀性,本文分別對(duì)9結(jié)點(diǎn),12結(jié)點(diǎn)和24結(jié)點(diǎn)的結(jié)點(diǎn)值進(jìn)行隨機(jī)初始化,圖6展示了9結(jié)點(diǎn)網(wǎng)絡(luò)模型時(shí)間序列長(zhǎng)度為10的響應(yīng)序列變化曲線,圖7展示了12結(jié)點(diǎn)網(wǎng)絡(luò)模型時(shí)間序列長(zhǎng)度為20的響應(yīng)序列變化曲線。

圖6 9結(jié)點(diǎn)時(shí)間序列長(zhǎng)度與結(jié)點(diǎn)狀態(tài)Fig.6 Time sequence and data statements of 9 nodes

圖7 12結(jié)點(diǎn)時(shí)間序列長(zhǎng)度與結(jié)點(diǎn)狀態(tài)Fig.7 Time sequence and data statements of 12 nodes

以Nt(9)表示9個(gè)結(jié)點(diǎn)的時(shí)間序列數(shù)目,Nt(12)表示12個(gè)結(jié)點(diǎn)的時(shí)間序列數(shù)目,從圖6可以看出,在Nt(9)=5之前,各結(jié)點(diǎn)的變化值均不穩(wěn)定,這是因?yàn)楦鱾€(gè)算法中下一個(gè)時(shí)間結(jié)點(diǎn)數(shù)值需要由當(dāng)前時(shí)間結(jié)點(diǎn)值和權(quán)值的共同作用決定,由于初始權(quán)值是隨機(jī)產(chǎn)生的,因此在學(xué)習(xí)過(guò)程中結(jié)點(diǎn)會(huì)產(chǎn)生波動(dòng)。從Nt(9)=5時(shí)刻開始,結(jié)點(diǎn)狀態(tài)變化幅度逐漸減小,說(shuō)明模糊認(rèn)知圖的動(dòng)力學(xué)系統(tǒng)開始變得穩(wěn)定。在確定Nt(12)時(shí),采用了文獻(xiàn)[34]的第一序列,由圖7可以看出，最終各結(jié)點(diǎn)值都穩(wěn)定在[0,1]，這是由FCM框架的性質(zhì)決定,由于初始結(jié)點(diǎn)C6=1.4,C7=-0.4,C8=-0.2,導(dǎo)致Nt(12)=4之前結(jié)點(diǎn)波動(dòng)極大,在Nt(12)=12 之后各結(jié)點(diǎn)狀態(tài)趨于穩(wěn)定,本文最終選取Nt(12)=20。24結(jié)點(diǎn)的時(shí)間序列數(shù)目的確定與12結(jié)點(diǎn)相同,在此不多做贅述。因此,在MOEA/CT-FCM中,我們選擇Nt(9)=10,Nt(12)=20,Nt(24)=20。

3.3 實(shí)驗(yàn)結(jié)果

為了比較MOEA/CT-FCM的優(yōu)化性能,將本文所提算法與MOEA-FCM[11]、RCGA、D&C RCGA[36]、DD-NHL[37]、NHL[8]等5種算法做對(duì)比。表6為9結(jié)點(diǎn)實(shí)驗(yàn)結(jié)果對(duì)比,實(shí)驗(yàn)結(jié)果均為各算法獨(dú)立運(yùn)行30次所對(duì)應(yīng)的各測(cè)試指標(biāo)的平均值和標(biāo)準(zhǔn)差,各項(xiàng)對(duì)比試驗(yàn)中的最優(yōu)結(jié)果均用黑體加粗表示。對(duì)比算法的實(shí)驗(yàn)結(jié)果來(lái)源于文獻(xiàn)[11],“/”表示在原文獻(xiàn)中未給出測(cè)量值。MOEA/CT-FCM算法在4個(gè)評(píng)價(jià)指標(biāo)上均明顯優(yōu)于其余5種算法。9結(jié)點(diǎn)工廠監(jiān)控模型中,MOEA/CT-FCM,MOEA-FCM,RCGA,D&C RCGA在Data_Error上都取得了0.00的結(jié)果,在結(jié)點(diǎn)還原方面比DD NHL和NHL要優(yōu)秀,其中MOEA/CT-FCM,MOEA-FCM在Out_of_Sample_Error上優(yōu)于其他算法,說(shuō)明在相同結(jié)點(diǎn)的情況下其擬合能力更強(qiáng)。由SS_Mean值可以看出,MOEA/CT-FCM能正確學(xué)習(xí)權(quán)值的大小。

表6 9結(jié)點(diǎn)實(shí)驗(yàn)結(jié)果對(duì)比

表7為12結(jié)點(diǎn)實(shí)驗(yàn)結(jié)果對(duì)比。結(jié)合表7中SS_Mean值和Model_Error值可以看出,MOEA/CT-FCM不僅可以正確識(shí)別概念結(jié)點(diǎn)狀態(tài)的變化,在計(jì)算概念結(jié)點(diǎn)間權(quán)值方面的誤差也很小。結(jié)合表7種Data_Error值和Model_Error值可以看出,MOEA/CT-FCM的值明顯小于其余5種算法,說(shuō)明在算法中所設(shè)計(jì)的f2(w)目標(biāo)在一定程度上起到了平衡概念結(jié)點(diǎn)狀態(tài)值和權(quán)值的作用。表8為24結(jié)點(diǎn)實(shí)驗(yàn)結(jié)果對(duì)比。表8反映了 MOEA/CT-FCM在處理不確定性多結(jié)點(diǎn)問(wèn)題的能力。雖然RCGA,D&C RCGA,DD NHL,NHL算法并沒有對(duì)Model_Error,SS_Mean進(jìn)行實(shí)驗(yàn),但并不影響對(duì)算法響應(yīng)序列穩(wěn)定程度的觀測(cè)。MOEA/CT-FCM,MOEA-FCM的Data_Error值明顯較其余對(duì)比算法小,說(shuō)明MOEA/CT-FCM與MODE-FCM能夠準(zhǔn)確地還原概念間權(quán)值。但MOEA-FCM的SS_Mean值較小,說(shuō)明在結(jié)點(diǎn)數(shù)量增多的情況下,該算法并不能很好的識(shí)別結(jié)點(diǎn)之間的關(guān)系。因此,雖然MOEA-FCM表現(xiàn)很出色,但是相比MOEA/CT-FCM來(lái)說(shuō)略顯遜色。

表7 12結(jié)點(diǎn)實(shí)驗(yàn)結(jié)果對(duì)比

表8 24結(jié)點(diǎn)實(shí)驗(yàn)結(jié)果對(duì)比

4 結(jié) 論

模糊認(rèn)知圖具有強(qiáng)大的推理能力,利用其來(lái)處理工程建模問(wèn)題具有較強(qiáng)的可行性,同時(shí)對(duì)數(shù)據(jù)的預(yù)測(cè)具有重要的實(shí)際意義。本文通過(guò)設(shè)計(jì)結(jié)點(diǎn)間有向弧權(quán)值誤差與誤差比重兩個(gè)目標(biāo),提出了模糊認(rèn)知圖學(xué)習(xí)的多目標(biāo)優(yōu)化模型,利用基于坐標(biāo)變換的多目標(biāo)演化算法對(duì)該模型進(jìn)行優(yōu)化求解,有效提高了模糊認(rèn)知圖的學(xué)習(xí)精度。通過(guò)實(shí)驗(yàn)結(jié)果可以看出,基于多目標(biāo)演化的模糊認(rèn)知圖學(xué)習(xí)算法可以有效降低結(jié)點(diǎn)數(shù)據(jù)誤差與模型誤差,能夠更準(zhǔn)確地得出概念結(jié)點(diǎn)間的因果關(guān)系,同時(shí)能夠適用于不同的實(shí)驗(yàn)數(shù)據(jù)集,說(shuō)明本文所提出的算法具有一定的應(yīng)用前景。

[1] 駱祥峰. 認(rèn)知圖理論及其在圖像分析與理解中的應(yīng)用[D]. 合肥: 合肥工業(yè)大學(xué), 2003.

LUO X F. Cognitive map theory and its applications in image analysis and understanding[D].Hefei:Hefei University of Technology, 2003.

[2] KOSKO B. Fuzzy cognitive maps[J]. International Journal of Man-Machine Studies, 1986, 24(1): 65-75.

[3] 陳軍, 高曉光, 丁琳. 模糊認(rèn)知圖在預(yù)警機(jī)燃油管理中的應(yīng)用[J]. 系統(tǒng)工程與電子技術(shù), 2008, 30(9): 1717-1720.

CHEN J, GAO X G,DING L. Application of fuzzy cognitive maps in fuel management of airborne warning and control systems[J]. Systems Engineering and Electronics, 2008, 30(9): 1717-1720.

[4] 李闖,端木京順,雷英杰,等.基于認(rèn)知圖和直覺模糊推理的態(tài)勢(shì)評(píng)估方法[J].系統(tǒng)工程與電子技術(shù),2012,34(10):2064-2068.

LI C, DUANMU J S, LEI Y J, et al. Situation assessment based on cognitive maps and intuitionistic fuzzy reasoning[J]. Systems Engineering and Electronics, 2012, 34(10): 2064-2068.

[5] MENDONCA M, ARRUDA L V R, ROSSATO CHRUN I, et al. Hybrid dynamic fuzzy cognitive maps evolution for autonomous navigation system[C]∥Proc.of the IEEE International Conference on Fuzzy Systems, 2015: 1-7.

[6] PAPAGEORGIOU E I. A new methodology for decisions in medical informatics using fuzzy cognitive maps based on fuzzy rule-extraction techniques[J]. Applied Soft Computing, 2011, 11(1): 500-513.

[7] SENNIAPPAN V, SUBRAMANIAN J, PAPAGEORGIOU E I, et al. Application of fuzzy cognitive maps for crack categorization in columns of reinforced concrete structures[J]. Neural Computing & Applications, 2016: 1-11.

[8] PAPAGEORGIOU E, STYLIOS C, GROUMPOS P. Fuzzy cognitive map learning based on nonlinear hebbian rule[C]∥Proc.of the Australian Conference on Artificial Intelligence, 2003:256-268.

[9] STACH W, PEDRYCZ W, KURGAN L A. Learning of fuzzy cognitive maps using density estimate[J]. IEEE Trans.on Systems Man & Cybernetics Part B Cybernetics, 2012, 42(3):900.

[10] DEB K. Multi-objective ptimization using evolutionary algrithms[M]. Chichester: Wiley, 2001.

[11] CHI Y, LIU J. Learning of fuzzy cognitive maps with varying densities using a multiobjective evolutionary algorithm[J]. IEEE Trans.on Fuzzy Systems, 2016, 24(1): 71-81.

[12] ZITZLER E, KüNZLI S. Indicator-based selection in multi-objective search[J].Lecture Notes in Computer Science,2004,3242: 832-842.

[13] ZHANG Q, Li H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans.on Evolutionary Computation, 2007,11(6): 712-731.

[14] CAI X, LI Y, FAN Z, et al. An external archive guided multi-objective evolutionary algorithm based on decomposition for combinatorial optimization[J]. IEEE Trans.on Evolutionary Computation, 2014, 19(4): 508-523.

[15] CAI X, YANG Z, FAN Z, et al. Decomposition-based-sorting and angle-based-selection for evolutionary multiobjective and many-objective optimization[J]. IEEE Trans.on Cybernetics, 2016, 47(9): 1-14.

[16] KOSKO B. Fuzzy cognitive maps[J]. International Journal of Man-machine Studies, 1986, 24(1): 65-75.

[17] TSADIRAS A K. Comparing the inference capabilities of binary, trivalent and sigmoid fuzzy cognitive maps[J]. Information Sciences, 2008, 178(20): 3880-3894.

[18] CHEN N, ZHANG J. Index-based genetic algorithm for continuous optimization problems[C]∥Proc.of the Genetic and Evolutionary Computation Conference, 2011: 1029-1036.

[19] STACH W J. Learning and aggregation of fuzzy cognitive maps-an evolutionary approach[D]. Canada: University of Alberta. 2010.

[20] PSYCHAS I D, DELIMPASI E, MARINAKIS Y. Hybrid evolutionary algorithms for the multiobjective traveling salesman problem[J]. Expert Systems with Applications, 2015, 42(22): 8956-8970.

[21] HUANG D Z, GONG R X, SHU N M. Constrained multi-objective optimization for microgrid based on nondominated immune algorithm[J]. IEEE Trans.on Electrical & Electronic Engineering, 2015, 10(4): 376-382.

[22] LI M, YANG S, ZHENG J, et al. ETEA: a euclidean minimum spanning tree-based evolutionary algorithm for multi-objective optimization[J].Evolutionary Computation, 2014, 22(2): 189-230.

[23] AGGARWAL C C, HINNEBURG A, KEIM D A. On the surprising behavior of distance metrics in high dimensional space[C]∥Proc.of the 8th International Conference on Database Theory, 2001: 420-434.

[24] MORGAN R, GALLAGHER M. Sampling techniques and distance metrics in high dimensional continuous landscape analysis: limitations and improvements[J]. IEEE Trans.on Evolutionary Computation, 2014, 18(3): 456-461.

[25] WANG H D, JIAO L C, YAO X. Two_arch2: an improved two-archive algorithm for many-objective optimization[J]. IEEE Trans.on Evolutionary Computation, 2015, 19(4): 524-541.

[26] VELDHUIZEN D V, LAMONT G B. On measuring multi-objective evolutionary algorithm performance[C]∥Proc.of the Evolutionary Computation, 2000: 204-211.

[27] SCHOTT J R. Fault tolerant design using single and multicriteria genetic algorithm optimization[J].Cellular Immunology,1995, 37(1): 1-13.

[28] DEB K, THIELE L, LAUMANNS M, et al. Scalable multi-objective optimization test problems[C]∥Proc.of the World on Congress on Computational Intelligence, 2002: 825-830.

[29] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Trans.on Evolutionary Computation, 2002, 6(2): 182-197.

[30] COELLO C C, PULIDO G T, LECHUGA M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Trans.on Evolutionary Computation, 2004, 8(3): 256-279.

[31] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE Trans.on Evolutionary Computation, 2014, 18(4): 577-601.

[32] KUNG H T, LUCCIO F, PREPARATA F P. On finding the maxima of a set of vectors[J]. Journal of the ACM, 1975, 22(4): 469-476.

[33] STYLIOS C D, GROUMPOS P P. Fuzzy cognitive maps: a model for intelligent supervisory control systems[J]. Compu-ters in Industry, 1999, 39(3): 229-238.

[34] KOK K. The potential of fuzzy cognitive maps for semi-quantitative scenario development, with an example from Brazil[J]. Global Environmental Change, 2009, 19(1): 122-133.

[35] HOSSAIN S, BROOKS L. Fuzzy cognitive map modelling educational software adoption[J]. Computers & Education, 2008, 51(4): 1569-1588.

[36] STACH W, KURGAN L, PEDRYCZ W, et al. Genetic learning of fuzzy cognitive maps[J].Fuzzy Sets & Systems,2005,153(3): 371-401.

[37] STACH W, KURGAN L, PEDRYCZ W. Data-driven nonlinear Hebbian learning method for fuzzy cognitive maps[C]∥Proc.of the IEEE International Conference on Fuzzy Systems, 2008: 1975-1981.