白首華，郭廣頌，胡天彤

鄭州航空工業(yè)管理學(xué)院 智能工程學(xué)院，鄭州450046

在多目標(biāo)優(yōu)化（Multi-objective Optimization Problem，MOP）問(wèn)題中，優(yōu)化目標(biāo)通常含有不能用函數(shù)表達(dá)的隱式指標(biāo)，這類問(wèn)題稱為混合指標(biāo)優(yōu)化問(wèn)題（Hybrid Index Optimization Problem，HIOP），這是一類特殊的多目標(biāo)優(yōu)化問(wèn)題。由于存在隱式指標(biāo)，HIOP的很多約束條件很難用數(shù)學(xué)形式表達(dá)，這就需要得到盡可能多的多重Pareto最優(yōu)解用于可行解的考察。此時(shí)，這類問(wèn)題稱為多模態(tài)混合指標(biāo)優(yōu)化問(wèn)題（Multi-modal Hybrid Index Optimization Problem，MHIOP）。HIOP和MHIOP在生產(chǎn)調(diào)度[1]、鋼梁設(shè)計(jì)[2]、柴油機(jī)標(biāo)定[3]、地圖設(shè)計(jì)[4]等領(lǐng)域普遍存在。

交互式進(jìn)化計(jì)算（Interactive Evolutionary Computation，IEC）作為一種重要的人機(jī)交互技術(shù)取得了長(zhǎng)足進(jìn)步，業(yè)已衍生出交互式多目標(biāo)優(yōu)化[5]、多用戶協(xié)同進(jìn)化[6]、個(gè)性化推薦等分支。IEC求解HIOP也已經(jīng)取得了顯著進(jìn)展[7]。但對(duì)于MHIOP，現(xiàn)有IEC方法并不能有效獲得多模態(tài)優(yōu)化解。在交互式進(jìn)化過(guò)程中，受人的疲勞限制，人只能評(píng)價(jià)少量樣本及執(zhí)行少數(shù)進(jìn)化操作。為了提高搜索效率，機(jī)器運(yùn)算需要提取包括用戶偏好、遺傳操作、個(gè)體分布等大量進(jìn)化信息。為了合理利用進(jìn)化信息，提高優(yōu)化質(zhì)量，support vector machine[8]、neural networks[9]、Gaussian process等代理模型已被用于進(jìn)化操作。由于IEC受自身單層進(jìn)化結(jié)構(gòu)限制，文獻(xiàn)[8-9]能夠提取的進(jìn)化信息都比較單一。IEC難以同時(shí)整合種類較多的信息，這使得IEC求解MHIOP時(shí)面臨巨大困難。所以，知識(shí)獲取與利用是IEC求解MHIOP的核心問(wèn)題，目前這一研究還很少。

文化算法（Cultural Algorithm，CA）是一種源于文化進(jìn)化的雙層結(jié)構(gòu)進(jìn)化模型，該模型由種群空間和信度空間構(gòu)成，分別用于實(shí)現(xiàn)個(gè)體進(jìn)化和知識(shí)更新。文化算法已成功應(yīng)用于環(huán)境設(shè)計(jì)[10]、圖像匹配[11]等問(wèn)題。文化算法的突出特點(diǎn)是其雙層結(jié)構(gòu)為復(fù)雜自適應(yīng)系統(tǒng)設(shè)計(jì)提供了一種通用框架，并且適用于任何以種群為基礎(chǔ)的算法。基于此，本文針對(duì)MHIOP提出一種能同時(shí)提取隱含知識(shí)和進(jìn)化知識(shí)的交互式多目標(biāo)文化算法（Interactive Multi-objective Cultural Algorithm，IMCA）。該算法可以有效求解MHIOP。

本文的創(chuàng)新之處是：（1）提出了一種求解混合指標(biāo)優(yōu)化問(wèn)題的交互式文化算法框架；（2）提出了混合指標(biāo)特殊擁擠距離計(jì)算方法；（3）提出了混合指標(biāo)多模態(tài)最優(yōu)解選取方法；（4）提出了文化算法框架下的知識(shí)引導(dǎo)自適應(yīng)交叉和變異算子。

1 多模態(tài)混合指標(biāo)優(yōu)化問(wèn)題（MHIOP）

本文考慮如下一類混合性能指標(biāo)優(yōu)化問(wèn)題：

式中，x=(x1,x2,…,xn)是n維決策變量；S為x的可行域；f1(x),f2(x),…,fp(x)為顯式性能指標(biāo)對(duì)應(yīng)的目標(biāo)函數(shù)；為隱式性能指標(biāo)，是用戶對(duì)進(jìn)化個(gè)體滿足程度的定性評(píng)價(jià)值。當(dāng)p+q≥4時(shí)，該問(wèn)題稱為高維混合指標(biāo)優(yōu)化問(wèn)題，本文僅考慮p=q=1的情況。

多模態(tài)解是指在決策空間中至少有兩個(gè)Pareto解集對(duì)應(yīng)目標(biāo)空間上的同一個(gè)Pareto前沿，如圖1所示[12]。多模態(tài)解意味著這類解在決策空間不同，但在目標(biāo)空間具有相同品質(zhì)（目標(biāo)函數(shù)值），這可以為目標(biāo)優(yōu)化提供更多的選擇。此外，獲得多重Pareto最優(yōu)解還能夠幫助發(fā)現(xiàn)優(yōu)化問(wèn)題一些潛在的特性，比如Pareto最優(yōu)解集在決策空間的分布等。多目標(biāo)優(yōu)化問(wèn)題求解多模態(tài)解，稱為多模態(tài)多目標(biāo)優(yōu)化問(wèn)題（Multi-modal Multi-objective Optimization Problem，MMOP）[13]。對(duì)于問(wèn)題（1）而言，多個(gè)不同的多模態(tài)解，可能對(duì)應(yīng)著相同的成本和能源效率，這可以為設(shè)計(jì)者提供相同成本下更多的最優(yōu)方案。所以，在已有的優(yōu)化結(jié)果中，找到盡可能多的多模態(tài)解是求解MHIOP的關(guān)鍵。

圖1 多模態(tài)解Fig.1 Multi-modal solution

2 算法描述

IMCA的思想是，將混合指標(biāo)優(yōu)化中的決策空間-目標(biāo)空間映射為與文化算法中的種群空間-信度空間。在信度空間內(nèi)，提取目標(biāo)空間解的信息，該信息一部分用于求解多模態(tài)解，一部分用于種群空間進(jìn)化算法的引導(dǎo)，從而獲得最佳最優(yōu)解，提高算法優(yōu)化質(zhì)量。具體步驟如下：

步驟1隨機(jī)產(chǎn)生初始化種群P，將種群均勻分成Nc個(gè)子類，初始化信度空間。

步驟2每個(gè)子類中選擇1個(gè)代表個(gè)體，共Nc個(gè)個(gè)體推薦給用戶評(píng)價(jià)。

步驟3估計(jì)剩余個(gè)體隱式指標(biāo)，存入種群空間數(shù)據(jù)庫(kù)，樣本選取函數(shù)從數(shù)據(jù)庫(kù)中選取指標(biāo)均衡性個(gè)體和精英個(gè)體構(gòu)成信度空間樣本庫(kù)。

步驟4知識(shí)提取函數(shù)根據(jù)特殊擁擠距離，選取多模態(tài)解，同時(shí)，更新信度空間各類知識(shí)。

步驟5利用信度空間的形勢(shì)知識(shí)指導(dǎo)種群空間進(jìn)化，生成新一代種群。

步驟6用戶若對(duì)多模態(tài)解滿意，則終止程序，否則轉(zhuǎn)步驟2。

可以看出，交互式多目標(biāo)文化算法求解多模態(tài)混合指標(biāo)優(yōu)化問(wèn)題的核心在于：多模態(tài)解的選取和知識(shí)指導(dǎo)種群空間進(jìn)化。

2.1 信度空間內(nèi)知識(shí)表示及利用

2.1.1 歷史知識(shí)

歷史知識(shí)存儲(chǔ)每代的多模態(tài)解，并根據(jù)序值大小按降序排列，記為M1,M2,…,Ms。式中，s是多模態(tài)解數(shù)量；Mi={xi|R(xi)}為第i個(gè)多模態(tài)個(gè)體，R(xi)為xi的序值。降序排列滿足R(xi-1)>R(xi),i≤s。歷史知識(shí)在種群空間每代進(jìn)化后更新。設(shè)xMbest(t)是種群空間中第t代序值最小多模態(tài)個(gè)體，歷史知識(shí)更新過(guò)程為：

2.1.2 標(biāo)準(zhǔn)化知識(shí)

標(biāo)準(zhǔn)化知識(shí)存儲(chǔ)每代的進(jìn)化信息，包括個(gè)體序值R(t)、指標(biāo)均衡度Gi(t)、指標(biāo)均衡度均值Gˉ(t)、決策空間擁擠距離CDavg,x和目標(biāo)空間擁擠距離Davg,f，記為R(t),Gi(t),Gˉ(t),CDavg,x,Davg,f。

（1）個(gè)體序值

個(gè)體序值根據(jù)混合指標(biāo)分布，采用非被占優(yōu)排序。

（2）指標(biāo)均衡度

混合指標(biāo)優(yōu)化會(huì)出現(xiàn)難以調(diào)和的定性與定量指標(biāo)矛盾，為了獲得最優(yōu)Pareto解，本節(jié)基于Gini系數(shù)建立指標(biāo)均衡度[14]。設(shè)第t代種群個(gè)體xi(t),i=1,2,…,N的顯式適應(yīng)值為f1(xi(t)),f2(xi(t)),…,fp(xi(t))，隱式適應(yīng)值 為，可 以 獲 得 種 群無(wú)量綱指標(biāo)行矩陣B(xi(t))1×(p+q)。在B(xi(t))1×(p+q)中，1～p列元素b11(xi(t)),b12(xi(t)),…,b1p(xi(t))為顯式指標(biāo)，即成本型指標(biāo)，該指標(biāo)值越小越好；p+1～p+q列元素b1(p+1)(xi(t)),b1(P+2)(xi(t)),…,b1(p+q)(xi(t))為隱式指標(biāo)，即效益型指標(biāo)，該指標(biāo)值越大越好。設(shè)指標(biāo)效用系數(shù)為1，且每一代均能收集到相關(guān)數(shù)據(jù)對(duì)相應(yīng)指標(biāo)進(jìn)行評(píng)價(jià)，故直接將個(gè)體xi(t)的各項(xiàng)指標(biāo)b11(xi(t)),b12(xi(t)),…,b1(p+q)(xi(t))作升序排列，記為V11(xi(t)),V12(xi(t)),…,V1(p+q)(xi(t))，則個(gè)體xi(t),i=1,2,…,N的指標(biāo)均衡度為：

式中，Gi(t)值越大，反映該個(gè)體的指標(biāo)均衡性越好，Gi(t)∈[0,1]。Gi(t)的均值稱為種群指標(biāo)均衡度，記為

（3）決策空間擁擠距離

圖2給出決策空間5個(gè)個(gè)體，以及這些個(gè)體在目標(biāo)空間的分布情況。記圖2（a）中個(gè)體3的擁擠距離為CD3,x，邊界個(gè)體5的擁擠距離為CD5,x：

圖2 個(gè)體擁擠距離Fig.2 Ind ividual crowding distance

式中，xi,j代表第j個(gè)個(gè)體的第i維決策變量值。記CDavg,x為決策空間個(gè)體擁擠距離平均值。

（4）目標(biāo)空間擁擠距離

記圖2（b）中個(gè)體5的擁擠距離為D(x5)，邊界個(gè)體4的擁擠距離為D(x4)：

式中，d(?)是顯式指標(biāo)距離；是隱式指標(biāo)距離，f1,i、f2,i代表個(gè)體xi的顯式指標(biāo)和隱式指標(biāo)。記Davg,f為目標(biāo)空間個(gè)體擁擠距離平均值。

2.1.3 領(lǐng)域知識(shí)

領(lǐng)域知識(shí)存儲(chǔ)非用戶評(píng)價(jià)的隱式指標(biāo)機(jī)器評(píng)價(jià)策略。為了擴(kuò)大搜索空間，同時(shí)減少人的操作負(fù)擔(dān)，本文采用基于個(gè)體相似性的聚類估計(jì)策略[15]，該策略以多模態(tài)解為聚類中心，實(shí)現(xiàn)對(duì)非用戶評(píng)價(jià)個(gè)體的隱式指標(biāo)的估計(jì)。

2.2 接口函數(shù)和知識(shí)函數(shù)

接口函數(shù)包括樣本選取函數(shù)和進(jìn)化引導(dǎo)函數(shù)，知識(shí)函數(shù)包括知識(shí)提取函數(shù)和知識(shí)更新函數(shù)。

2.2.1 樣本選取函數(shù)

多模態(tài)個(gè)體的特點(diǎn)是具有良好的指標(biāo)均衡性和較小的序值。樣本選取函數(shù)從種群空間數(shù)據(jù)庫(kù)中分別選取指標(biāo)均衡性個(gè)體和精英個(gè)體，構(gòu)成信度空間樣本庫(kù)，具體步驟如下：

步驟1在目標(biāo)空間內(nèi)合并父代種群，構(gòu)成種群F，按式（3）指標(biāo)均衡度降序排序，保存前N個(gè)個(gè)體，構(gòu)成指標(biāo)均衡性保存集。

步驟2在NSGA-II框架下，對(duì)種群F按非支配排序，選擇前Nc個(gè)個(gè)體作為聚類中心，按個(gè)體基因型歐氏距離聚類，再按式（6）、（7）所示目標(biāo)空間擁擠距離確定各個(gè)體序值。

步驟3用戶設(shè)定小生境半徑σniche，將各子類中小于σniche的個(gè)體保存，按序值選擇前N個(gè)個(gè)體，構(gòu)成精英種群保存集。

2.2.2 知識(shí)提取函數(shù)

知識(shí)提取函數(shù)從信度空間樣本庫(kù)挑出多模態(tài)解，具體步驟如下：

步驟1將信度空間樣本庫(kù)內(nèi)的指標(biāo)均衡性保存集與精英種群保存集相交，這兩個(gè)集合的相同個(gè)體，構(gòu)成重組集合B。集合B個(gè)體同時(shí)具備收斂性和分布性，是挑選多模態(tài)個(gè)體的基礎(chǔ)。

步驟2在目標(biāo)空間內(nèi)計(jì)算集合B內(nèi)個(gè)體的特殊擁擠距離SCDi，即對(duì)于個(gè)體xi∈B，

根據(jù)多模態(tài)解特點(diǎn)，如果SCDi大于閾值，則可以認(rèn)為該個(gè)體為多模態(tài)解，否則為最優(yōu)解。

需要說(shuō)明的是，在步驟2中，由于隱式性能指標(biāo)的不確定性決定了個(gè)體在決策空間的距離大小不能反映目標(biāo)空間內(nèi)指標(biāo)距離，所以，采用式（13）判定多模態(tài)解時(shí)不用考慮決策空間個(gè)體間的擁擠距離，這也是混合指標(biāo)優(yōu)化與數(shù)值多目標(biāo)優(yōu)化的明顯區(qū)別。

2.2.3 知識(shí)更新函數(shù)

知識(shí)更新的核心問(wèn)題在于更新頻率，與有關(guān)。記相鄰兩次知識(shí)提取的間隔進(jìn)化代數(shù)為：

式中，a為調(diào)整系數(shù)，τ∈{1,2,3}。

2.2.4 進(jìn)化引導(dǎo)函數(shù)

（1）指導(dǎo)遺傳操作

進(jìn)化引導(dǎo)函數(shù)指導(dǎo)遺傳操作分為兩個(gè)部分，一部分是將標(biāo)準(zhǔn)化知識(shí)中個(gè)體序值R(t)和目標(biāo)空間擁擠距離Davg,f用于種群空間的NSGA-II算法；另一部分是考慮算法探索和開發(fā)功能，利用進(jìn)化知識(shí)設(shè)計(jì)自適應(yīng)交叉和變異算子[16-18]。設(shè)pc(t)、p'c(t)和pm(t)、p'm(t)分別為進(jìn)化引導(dǎo)前后的交叉和變異概率，則有：

上式均以種群指標(biāo)均衡度作為遺傳算子的引導(dǎo)知識(shí)，并以Sigmoid函數(shù)設(shè)計(jì)自適應(yīng)交叉和變異概率，其中，是關(guān)于的增函數(shù)，(t)是關(guān)于的減函數(shù)，且在（0.5，1）之間，在（0，0.5）之間。式（15）、（16）采用Sigmoid函數(shù)是因?yàn)樵摵瘮?shù)具有如下特點(diǎn)：①Sigmoid函數(shù)的導(dǎo)數(shù)和反函數(shù)均可以用其自身表示，而Sigmoid函數(shù)的單增以及反函數(shù)單減等性質(zhì)則能在線性和非線性行為之間顯現(xiàn)出較好的平衡；②從信息熵角度考察，Sigmoid函數(shù)對(duì)于呈倒置吊鐘型概率密度函數(shù)的輸入信號(hào)具有最優(yōu)變換特性；③Sigmoid函數(shù)的參數(shù)形式為閾值設(shè)置提供了豐富的設(shè)計(jì)空間。

以自適應(yīng)變異概率說(shuō)明進(jìn)化引導(dǎo)函數(shù)指導(dǎo)遺傳操作機(jī)理。式（16）對(duì)當(dāng)前進(jìn)化代種群指標(biāo)均衡度與前一代種群指標(biāo)均衡度進(jìn)行比較，將比較結(jié)果作為自適應(yīng)調(diào)整交叉和變異概率的條件。若小于，說(shuō)明當(dāng)前進(jìn)化代種群指標(biāo)均衡性變差，種群的多樣性也變壞。此時(shí)，需要增大變異概率，增強(qiáng)局部搜索能力，提升指標(biāo)均衡性和種群的多樣性。根據(jù)式（16）關(guān)于的Sigmoid減函數(shù)特性，變異概率將自適應(yīng)增加。若不小于，說(shuō)明種群指標(biāo)均衡性沒(méi)有變差，此時(shí)應(yīng)維持變異概率不變，減小優(yōu)良個(gè)體被破壞的可能性，保持全局搜索能力。一般來(lái)說(shuō)，在進(jìn)化中前期，由于混合指標(biāo)優(yōu)化不完善，指標(biāo)均衡性較差，小于次數(shù)較多；隨著進(jìn)化深入，指標(biāo)均衡性逐漸提高，變異概率會(huì)逐漸減小，并趨于穩(wěn)定。實(shí)施變異操作時(shí)，先考慮父代個(gè)體，按式（16）計(jì)算其變異概率，然后依該概率進(jìn)行變異操作。自適應(yīng)交叉概率運(yùn)算機(jī)理與此類似。

（2）指導(dǎo)評(píng)價(jià)過(guò)程

本文方法采用大規(guī)模種群進(jìn)化，用戶只評(píng)價(jià)少量個(gè)體。用戶評(píng)價(jià)個(gè)體由算法推薦，而多模態(tài)解可以提供用戶多種選擇，所以，由知識(shí)提取函數(shù)獲得的多模態(tài)解作為推薦個(gè)體，用于用戶評(píng)價(jià)。如果多模態(tài)解數(shù)量不足Nc個(gè)，則從其他最優(yōu)解中按非支配解序值選擇補(bǔ)充。

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

3.1 優(yōu)化系統(tǒng)與參數(shù)設(shè)置

采用室內(nèi)布局優(yōu)化問(wèn)題驗(yàn)證本文方法的性能[7]。該室內(nèi)布局由客廳、臥室等7個(gè)居室單元組成，布局開間W和進(jìn)深H分別為W=12.5 m，H=10 m。該優(yōu)化問(wèn)題包含1個(gè)顯式指標(biāo)（總造價(jià)）f1(x)和1個(gè)隱式指標(biāo)（審美需求）。其中，顯示指標(biāo)函數(shù)f1(x)由決策變量x=[x1,x2,x3,x4,x5,x6,x7]和參數(shù)c=[c1,c2,c3,c4,c5,c6,c7]組成，決策變量x1~x7代表各居室單元的邊長(zhǎng)，采用離散值，取值個(gè)數(shù)分別為5、12、5、5、5、5、5，參數(shù)c1～c7代表各居室單元的單位面積造價(jià)；是用戶對(duì)室內(nèi)布局方案的主觀評(píng)價(jià)值。優(yōu)化目標(biāo)是：合理設(shè)計(jì)各居室單元的劃分，在滿足總造價(jià)最低的同時(shí)，最大程度符合用戶對(duì)居室布局設(shè)計(jì)的審美需求。

優(yōu)化系統(tǒng)采用VB6.0開發(fā)。本文方法種群規(guī)模N=200，用戶評(píng)價(jià)個(gè)體數(shù)Nc=12，最大進(jìn)化代數(shù)T=10，用戶評(píng)價(jià)值為1~99整數(shù)。式（15）、（16）中k1=k2=0.5。優(yōu)化系統(tǒng)的人機(jī)交互界面如圖3所示。在人機(jī)交互過(guò)程中，優(yōu)化系統(tǒng)通過(guò)進(jìn)化逐漸生成用戶滿意的布局方案。

圖3 人機(jī)交互界面Fig.3 Human-computer interaction interface

3.2 實(shí)驗(yàn)結(jié)果分析

目前，尚沒(méi)有直接求解MHIOP的方法。為驗(yàn)證本文方法優(yōu)越性，將文獻(xiàn)[7]的優(yōu)化算法（記為方法1）和采用小種群(N=12)實(shí)現(xiàn)本文方法（記為方法2）等兩種方法作為比較算法，其中方法1已被證明優(yōu)于傳統(tǒng)交互式進(jìn)化計(jì)算。分別按上述3種方法開發(fā)相應(yīng)系統(tǒng)，選擇10名在校大學(xué)生作為體驗(yàn)用戶，將每種方法獨(dú)立運(yùn)行3次。按如下3項(xiàng)測(cè)試項(xiàng)目，驗(yàn)證本文方法在搜索效率、優(yōu)化質(zhì)量、可用性等方面的有效性。

（1）本文方法的優(yōu)化效果

本文方法優(yōu)化解指標(biāo)如表1所示?？梢钥吹?，采用本文方法，10位用戶每次進(jìn)化都能獲得較多多模態(tài)解，且多模態(tài)解數(shù)目與評(píng)價(jià)互異個(gè)體數(shù)目大致相同，這體現(xiàn)出多模態(tài)解已經(jīng)成為種群聚類中心，種群獲得了良好的多樣性。另外，每位用戶的知識(shí)更新次數(shù)不少于2次，Gˉ(t)均值不低于0.7。并且Gˉ(t)越大，多模態(tài)解越多，兩者呈現(xiàn)正向性。這反映出指標(biāo)均衡性作為引導(dǎo)知識(shí)可以有效求解多模態(tài)解。相應(yīng)地，作為歷史知識(shí)，將多模態(tài)解用于聚類中心實(shí)現(xiàn)大規(guī)模種群進(jìn)化，種群個(gè)體的混合指標(biāo)會(huì)表現(xiàn)出良好的均衡性。這表明，采用雙層進(jìn)化結(jié)構(gòu)及知識(shí)引導(dǎo)策略，種群空間得到更高的進(jìn)化效率，可以準(zhǔn)確搜索到多模態(tài)解。實(shí)現(xiàn)了決策空間-目標(biāo)空間與種群空間-信度空間的映射。

表1 本文方法優(yōu)化解Table 1 IMCA optimal solution

抽取用戶5的第1次實(shí)驗(yàn)結(jié)果，分析自適應(yīng)遺傳算子在進(jìn)化過(guò)程對(duì)種群的影響程度，如圖4所示?？梢钥吹剑S著進(jìn)化深入，變異概率逐漸減小，交叉概率逐漸增加，其對(duì)種群作用比例相應(yīng)變化。通過(guò)對(duì)式（15）、（16）求導(dǎo)可得，即在相同的變化下，交叉概率與變異概率變化呈反向。這種變化趨勢(shì)也表現(xiàn)為遺傳操作對(duì)種群的作用程度上，圖4曲線印證了這種變化趨勢(shì)，也表明了進(jìn)化過(guò)程中知識(shí)引導(dǎo)的準(zhǔn)確性。

圖4 遺傳算子影響Fig.4 Influence of genetic operators

選取第1、3、5、7、9及10代兩類遺傳算子作用下產(chǎn)生的多模態(tài)個(gè)體進(jìn)化情況如圖5、圖6所示?？梢钥吹?，進(jìn)化初期，自適應(yīng)變異算子產(chǎn)生的多模態(tài)個(gè)體較多，算法的局部探索能力較強(qiáng)。隨著進(jìn)化深入，自適應(yīng)交叉作用比例逐漸增加，產(chǎn)生的多模態(tài)個(gè)體增加，算法全局搜索能力得到加強(qiáng)，加快算法收斂。圖5、圖6所示多模態(tài)解進(jìn)化趨勢(shì)與圖4所示曲線趨勢(shì)一致，同樣驗(yàn)證了本文方法搜索多模態(tài)解的準(zhǔn)確性。另外，從圖4可知，變異算子的作用比例有時(shí)會(huì)增加，這可以幫助算法從局部收斂點(diǎn)跳出，從而保證算法全局尋優(yōu)能力。

圖5 自適應(yīng)變異概率產(chǎn)生多模態(tài)個(gè)體Fig.5 Adaptive mutation probability generating multimodal individuals

圖6 自適應(yīng)交叉概率產(chǎn)生多模態(tài)個(gè)體Fig.6 Adaptive crossover probability generating multimodal individuals

（2）不同方法性能比較

①算法效率分析

算法效率通過(guò)與對(duì)比方法比較獲得，統(tǒng)計(jì)結(jié)果如表2所示，其中指標(biāo)SR是算法獲得的多模態(tài)解與最優(yōu)解比例，SR越大，算法性能越好?？梢钥闯觯疚姆椒ǖ挠脩艉臅r(shí)最少，進(jìn)化代數(shù)最短，用戶評(píng)價(jià)個(gè)體數(shù)目最少，最優(yōu)解數(shù)目最多，SR最大。這說(shuō)明，本文方法可以在最少的操作負(fù)擔(dān)內(nèi)，獲得最多最優(yōu)解，算法體現(xiàn)出最高的搜索效率。原因在于，本文方法采用文化算法的雙層進(jìn)化結(jié)構(gòu)，在信度空間內(nèi)對(duì)多目標(biāo)優(yōu)化知識(shí)的提取與利用更充分，能夠獲得更多的多模態(tài)解，同時(shí)采用知識(shí)引導(dǎo)自適應(yīng)交叉和變異概率策略，擴(kuò)大了種群搜索范圍，減少了進(jìn)化代數(shù)，減輕了人的疲勞。方法1未采用雙層進(jìn)化結(jié)構(gòu)，SR最小，多模態(tài)解最少；方法2由于采用小種群，算法效率最低。

表2 算法效率Table 2 Efficiency of algorithm

②算法收斂性分析

圖7給出了3種算法的混合指標(biāo)統(tǒng)計(jì)結(jié)果?？梢钥吹?，3種方法的混合指標(biāo)均能成功收斂，但本文方法的顯式指標(biāo)居中，隱式指標(biāo)則高于對(duì)比方法。這表明，本文方法的收斂效果最好，布局方案用戶最滿意，優(yōu)化結(jié)果質(zhì)量最高。表2給出了本文方法的平均進(jìn)化代數(shù)為8.2，說(shuō)明本文方法收斂速度最快。表2中指標(biāo) ||SR是算法獲得的多模態(tài)解與最優(yōu)解的平均歐氏距離，反映收斂精度。本文方法的 ||SR值最小，說(shuō)明收斂精度最高。

圖7 性能指標(biāo)Fig.7 Performance index

事實(shí)上，本文涉及的3種算法收斂性均與傳統(tǒng)遺傳算法相同，即以馬爾科夫鏈概率收斂到全局最優(yōu)解。在算法收斂前提下，本文方法和方法2的計(jì)算復(fù)雜度為Q(((T/τ)-1)?2N(Ng+1))，Ng為個(gè)體表現(xiàn)型屬性數(shù)目，方法1的計(jì)算復(fù)雜性為Q((T-1)?2N(Ng+1))。由于本文方法采用大規(guī)模種群進(jìn)化，知識(shí)更新次數(shù)τ多于方法2，所以算法計(jì)算復(fù)雜度最低，這從理論上保證了本文方法收斂效果最好。

③Pareto最優(yōu)解集

抽取3種方法在第8代獲得的Pareto前沿，如圖8所示。可以看到，本文方法得到的Pareto最優(yōu)解多于對(duì)比方法，且Pareto前沿分布也更均勻。說(shuō)明本文方法在解的多樣性方面表現(xiàn)更好。采用bH測(cè)度、I測(cè)度和D測(cè)度衡量Pareto最優(yōu)解集質(zhì)量，如表3所示?？梢钥吹剑疚姆椒╞H測(cè)度值最大，表明本文方法得到的pareto前沿更接近真實(shí)Pareto前沿；本文方法I測(cè)度值和D測(cè)度值最小，說(shuō)明本文方法得到的Pareto最優(yōu)解集不確定性最小且分布更均勻。可以看到，本文方法整體前沿分布性優(yōu)于對(duì)比算法。原因在于，本文提出的知識(shí)引導(dǎo)自適應(yīng)交叉變異算子結(jié)合了文化算法和傳統(tǒng)遺傳算法在微觀、宏觀兩個(gè)層面的進(jìn)化優(yōu)勢(shì)，顯著改善了收斂性和多樣性。

表3 Pareto最優(yōu)解集測(cè)度Table 3 Measure of Pareto optimal solution set

圖8 第8代Pareto前沿Fig.8 Pareto front of 8th generation

④算法可用性

在算法可用性方面，統(tǒng)計(jì)用戶的迷失度L和滿意度。迷失度用于度量用戶對(duì)操作對(duì)象的迷茫程度，反映用戶的疲勞性感受[19]：

式中，No'是用戶在一次進(jìn)化任務(wù)中評(píng)價(jià)的互異個(gè)體數(shù)目，No''是用戶在一次進(jìn)化任務(wù)中獲得的最優(yōu)評(píng)價(jià)的個(gè)體數(shù)目，T'是算法運(yùn)行終止進(jìn)化代數(shù)。用戶迷失度箱圖如圖9所示。

圖9 用戶迷失度Fig.9 User lostness

將本文方法和對(duì)比方法進(jìn)行用戶滿意度量化可用性測(cè)試（System Usability Scale，SUS）問(wèn)卷調(diào)查，所得SUS分?jǐn)?shù)即為滿意度分值。用戶滿意度箱圖如圖10所示。

圖10 用戶滿意度Fig.10 User satisfaction

迷失度小于0.4時(shí)，用戶不會(huì)對(duì)操作對(duì)象顯示出任何可觀察到的迷失特征，當(dāng)迷失度大于0.5時(shí)，用戶就會(huì)出現(xiàn)迷失特征，同時(shí)疲勞會(huì)快速增加。從圖9可以看到，本文方法的迷失度最小，這表明用戶使用本文方法沒(méi)有產(chǎn)生迷失特征，有效預(yù)防了疲勞發(fā)生。從圖10可以看到，本文方法的滿意度SUS分值最高，表明用戶體驗(yàn)最佳。

（3）在更大搜索空間的性能

為考察本文方法對(duì)更復(fù)雜混合指標(biāo)優(yōu)化問(wèn)題的求解能力，將2.1節(jié)室內(nèi)布局優(yōu)化問(wèn)題的決策變量x1~x7的取值個(gè)數(shù)擴(kuò)大為13、12、13、17、9、13、7，則總的布局方案由原有的12×56=187 500擴(kuò)大為133×12×17×9×7=28 235 844。表3列出了這種情況下，本文方法與對(duì)比方法的Pareto最優(yōu)解集測(cè)度?？梢钥吹?，和未擴(kuò)大優(yōu)化問(wèn)題搜索空間相比，3種方法的bH測(cè)度值均有所下降，I測(cè)度值和D測(cè)度值則均提高，這是由優(yōu)化問(wèn)題變復(fù)雜導(dǎo)致的Pareto最優(yōu)解質(zhì)量下降。但本文方法bH測(cè)度值明顯大于對(duì)比方法；本文方法I測(cè)度值和D測(cè)度值明顯小于對(duì)比方。這說(shuō)明本文方法得到的Pareto最優(yōu)解集仍優(yōu)于對(duì)比方法，即對(duì)于更大搜索空間的復(fù)雜混合指標(biāo)優(yōu)化問(wèn)題，采用本文方法仍能獲得更好的求解。原因在于，本文方法通過(guò)標(biāo)準(zhǔn)化知識(shí)-領(lǐng)域知識(shí)-歷史知識(shí)的知識(shí)轉(zhuǎn)化過(guò)程，由知識(shí)提取函數(shù)獲得的多模態(tài)解增強(qiáng)了偏好引導(dǎo)性，增強(qiáng)了算法尋優(yōu)能力，引導(dǎo)種群空間的高效搜索，讓算法在更大搜索空間的優(yōu)化能力仍優(yōu)于對(duì)比方法。

綜上所述，與對(duì)比方法比較，本文方法搜索效率最高、求解能力更強(qiáng)、可用性更好。對(duì)于求解多模態(tài)混合指標(biāo)優(yōu)化問(wèn)題，采用文化算法框架、大規(guī)模進(jìn)化種群、自適應(yīng)遺傳算子，有利于求解該問(wèn)題。

4 結(jié)語(yǔ)

在文化算法框架下，采用交互式進(jìn)化優(yōu)化求解多模態(tài)混合指標(biāo)優(yōu)化問(wèn)題。該方法在信度空間內(nèi)，從樣本庫(kù)中選取多模態(tài)個(gè)體，推薦給用戶評(píng)價(jià)。同時(shí)，針對(duì)大規(guī)模種群聚類進(jìn)化，知識(shí)引導(dǎo)遺傳操作，擴(kuò)大種群多樣性。仿真結(jié)果表明，采用雙層進(jìn)化結(jié)構(gòu)，知識(shí)引導(dǎo)進(jìn)化，有助于獲得更多多模態(tài)優(yōu)化解。本文方法為解決多模態(tài)多目標(biāo)優(yōu)化問(wèn)題提供了一種新思路。本文僅研究2維混合指標(biāo)優(yōu)化問(wèn)題，探尋交互式文化算法求解高維多模態(tài)混合指標(biāo)優(yōu)化問(wèn)題是下一步研究的內(nèi)容。