張 勇 楊 康 郝國生 鞏敦衛(wèi)

進(jìn)化優(yōu)化是模擬生物進(jìn)化行為和機(jī)制產(chǎn)生的一類迭代搜索算法，目前已廣泛應(yīng)用于模式識(shí)別、經(jīng)濟(jì)管理、電氣工程和生物學(xué)等眾多領(lǐng)域[1].典型進(jìn)化優(yōu)化技術(shù)包含遺傳算法(Genetic algorithm，GA)、進(jìn)化策略(Evolution strategy，ES) 和進(jìn)化規(guī)劃(Evolutionary programming，EP) 等.由于同樣啟發(fā)于生物進(jìn)化行為，部分學(xué)者也將粒子群優(yōu)化和蟻群優(yōu)化等群體智能優(yōu)化算法歸為進(jìn)化優(yōu)化技術(shù).該類算法都是從選定的初始種群出發(fā)，通過不斷迭代更新種群中個(gè)體位置，直至搜索到最適合問題或任務(wù)的解.通常，這些算法所依賴的初始種群都是在問題可行域中生成的隨機(jī)位置.換句話說，現(xiàn)有進(jìn)化優(yōu)化算法，如文獻(xiàn)[2-8]，都是從問題的零初始信息開始搜索，并沒有考慮是否以前優(yōu)化過類似問題，是否可以從歷史信息中獲得解決當(dāng)前相似問題的能力.例如，在車間調(diào)度問題中，當(dāng)前月份的生成任務(wù)可能與往年某一月份的任務(wù)相同或相似.在利用進(jìn)化優(yōu)化尋找當(dāng)前月份最佳調(diào)度序列時(shí)，如果能夠充分利用相似任務(wù)的歷史信息，勢必可以提高其搜索能力.

遷移學(xué)習(xí)(Transfer learning) 是一種人性化的機(jī)器學(xué)習(xí)方法，其目的是把一個(gè)領(lǐng)域(即源領(lǐng)域) 的知識(shí)遷移到另外一個(gè)領(lǐng)域(即目標(biāo)領(lǐng)域)，使得目標(biāo)領(lǐng)域能夠取得更好的學(xué)習(xí)效果，即使用以前解決相似任務(wù)時(shí)獲得的信息來幫助解決新問題[9].目前遷移學(xué)習(xí)已廣泛應(yīng)用于圖形識(shí)別、文本分類、網(wǎng)頁分類等諸多問題[10-15].但是，將遷移學(xué)習(xí)應(yīng)用于進(jìn)化優(yōu)化中，相關(guān)研究仍然很少.Dinh 等[16]和Ko?cer等[17]在使用遺傳算法處理源域任務(wù)時(shí)，保存得到的最優(yōu)、中等和最差等個(gè)體;當(dāng)處理新的目標(biāo)任務(wù)時(shí)，遷移這些個(gè)體并隨機(jī)代替初始種群中的部分個(gè)體;Feng 等[18]將遷移學(xué)習(xí)融合到進(jìn)化優(yōu)化中，提出了一種新的文化基因進(jìn)化框架;最近，Jiang 等[19]成功地將遷移學(xué)習(xí)用于解決動(dòng)態(tài)多目標(biāo)優(yōu)化問題，顯著提高了進(jìn)化優(yōu)化算法對(duì)環(huán)境變化的響應(yīng)速度.

上述方法的成功應(yīng)用充分說明了利用遷移學(xué)習(xí)提高進(jìn)化算法性能的可行性.然而，相關(guān)研究起步較晚，仍然存在如下不足或可改進(jìn)之處:1) 在構(gòu)造遷移學(xué)習(xí)的源域樣本時(shí)，已有工作僅保存種群中最優(yōu)、中等或者最差的個(gè)體，沒有考慮所保存?zhèn)€體的多樣性.受益于進(jìn)化優(yōu)化的優(yōu)勝劣汰機(jī)制，種群中的所有個(gè)體往往會(huì)收斂到搜索空間中的一個(gè)點(diǎn)或一個(gè)很小的區(qū)域.此時(shí)，種群中的最優(yōu)、中等和最差可能十分相似.在源域中保存諸多相似的個(gè)體，不免造成樣本空間分布的過擬合現(xiàn)象.2) 現(xiàn)有工作大都假設(shè)源域和目標(biāo)域已經(jīng)相似或匹配，并未給出源域和目標(biāo)域相似性或匹配程度的判斷標(biāo)準(zhǔn).通常決策者可以獲得的相似歷史問題或任務(wù)往往較多，如何從眾多的歷史問題或任務(wù)中選出最為相似的一個(gè)，將直接影響到遷移學(xué)習(xí)的效果;相反，當(dāng)源域問題和目標(biāo)域問題完全不同時(shí)，強(qiáng)制遷移可能會(huì)污染目標(biāo)域，產(chǎn)生負(fù)面的影響[20].3) 由源域到目標(biāo)域的知識(shí)遷移方法研究不夠.文獻(xiàn)[16-17]將源域中保存的個(gè)體樣本直接替代目標(biāo)問題的初始種群，沒有考慮源問題與目標(biāo)問題之間的差異性.盡管文獻(xiàn)[18-19]所設(shè)計(jì)的知識(shí)遷移方法考慮了歷史問題與目標(biāo)問題之間的差異性(或映射關(guān)系)，但其所得成果皆立足于車輛路徑規(guī)劃和動(dòng)態(tài)多目標(biāo)優(yōu)化問題的自身特點(diǎn)，難以用于本文考慮的靜態(tài)全局優(yōu)化問題.

鑒于此，本文研究一種基于歷史相似信息遷移學(xué)習(xí)的進(jìn)化優(yōu)化框架，用以解決復(fù)雜優(yōu)化問題.針對(duì)某一待處理的新問題，該方法首先從模型庫中找到與其最為匹配的歷史模型;接著，從歷史模型對(duì)應(yīng)的源域知識(shí)中提取有用信息，構(gòu)建源域到目標(biāo)域的映射關(guān)系，并基于該映射關(guān)系產(chǎn)生新問題下進(jìn)化算法的初始種群.本文主要工作如下:1) 提出一種基于多分布估計(jì)的最大均值差異指標(biāo)，用來評(píng)價(jià)新問題與歷史問題之間的相似程度;2) 基于模型的相似程度，給出一種(歷史問題對(duì)應(yīng)的) 源域到(待優(yōu)化問題對(duì)應(yīng)的) 目標(biāo)域的自適應(yīng)知識(shí)遷移策略，初始化當(dāng)前進(jìn)化種群中的部分個(gè)體，加快進(jìn)化算法的搜索速度;3)為不斷更新和豐富歷史模型庫，給出一種基于迭代聚類的代表個(gè)體保存策略，形成源域的樣本集合，同時(shí)保證個(gè)體樣本的多樣性和質(zhì)量;4) 將自適應(yīng)骨干粒子群優(yōu)化算法嵌入到所提框架，給出一種基于相似歷史信息遷移學(xué)習(xí)的骨干粒子群優(yōu)化算法.

本文結(jié)構(gòu)如下:第1 節(jié)介紹相關(guān)工作，包括遷移學(xué)習(xí)和粒子群優(yōu)化的基本理論;第2 節(jié)給出所提基于歷史相似信息遷移學(xué)習(xí)的進(jìn)化優(yōu)化框架，以及基于遷移學(xué)習(xí)的改進(jìn)粒子群優(yōu)化算法;第3 節(jié)給出相應(yīng)的對(duì)比實(shí)驗(yàn)，驗(yàn)證算法的有效性;第4 節(jié)對(duì)本文工作進(jìn)行總結(jié).

1 相關(guān)工作

1.1 粒子群優(yōu)化算法

粒子群優(yōu)化(Particle swarm optimization，PSO)[21]算法是一種仿生物群體覓食行為的全局隨機(jī)搜索算法.在求解優(yōu)化問題時(shí)，每個(gè)粒子通過記憶和追隨兩個(gè)最優(yōu)位置，來不斷更新自身的位置[22].一個(gè)是該粒子到目前為止自己發(fā)現(xiàn)的最好位置Pbest=(pbesti，1，pbesti，2，···，pbesti，N)，即通常所說的粒子個(gè)體最優(yōu)點(diǎn)或局部引導(dǎo)者;另一個(gè)是目前為止鄰域粒子發(fā)現(xiàn)的最好位置Gbesti=(gbesti，1，gbesti，2，···，gbesti，N)，即通常所說的粒子的全局最優(yōu)點(diǎn)或全局引導(dǎo)者.設(shè)粒子i在N維空間的位置為矢量XXXi=(xi，1，xi，2，···，xi，N)，飛行速度為矢量VVV i=(vi，1，vi，2，···，vi，N)，該粒子位置更新式為

其中，k為算法迭代次數(shù)，ω為慣性權(quán)重，c1和c2為學(xué)習(xí)因子，r1和r2為服從均勻分布U(0，1) 的隨機(jī)數(shù).

1.2 遷移學(xué)習(xí)

遷移學(xué)習(xí)主要包含域和任務(wù)兩個(gè)概念[23-24].通常，域可以表示為D={Z，Pob(Z)}，即特征空間Z和特征空間的邊緣分布Pob(Z).在給定一個(gè)域D={Z，Pob(Z)}的情況下，一個(gè)任務(wù)可以表示為T={Y，f(·)}，即標(biāo)簽空間Y和一個(gè)目標(biāo)預(yù)測函數(shù)f(·).考慮存在一個(gè)源域Ds和一個(gè)目標(biāo)域Dt的情況，不妨設(shè)源域Ds={(zs，1，ys，1)，(zs，2，ys，2)，···，(zs，ns，ys，ns)}，zs，j ∈Zs表示源域樣本，ys，j ∈Ys表示源域樣本zs，j對(duì)應(yīng)的標(biāo)簽.目標(biāo)域Dt={(zt，1，yt，1)，(zt，2，yt，2)，···，(zt，ns，yt，nt)}，zt，j ∈Zt表示目標(biāo)域樣本，yt，j ∈Yt表示目標(biāo)域樣本zt，j對(duì)應(yīng)的輸出.基于以上的符號(hào)定義，遷移學(xué)習(xí)的目的是:在給定源域Ds和源域?qū)W習(xí)任務(wù)Ts、目標(biāo)域Dt和目標(biāo)域任務(wù)Tt，且滿足DtDs和Tt Ts的情況下，通過遷移學(xué)習(xí)使用源域Ds和Ts中的知識(shí)，提升或優(yōu)化目標(biāo)域Dt中目標(biāo)預(yù)測函數(shù)f(·) 的學(xué)習(xí)效果[9].史數(shù)據(jù)的利用和模型庫的更新.針對(duì)上述三個(gè)關(guān)鍵算子，下面分別給出詳細(xì)解決方案.

2 基于歷史相似信息遷移學(xué)習(xí)的進(jìn)化優(yōu)化框架

現(xiàn)有進(jìn)化優(yōu)化算法大都從給定問題的零初始信息開始，隨機(jī)產(chǎn)生初始種群，并通過迭代搜索找到問題的最優(yōu)解.為充分利用相似問題的歷史信息，本節(jié)提出一種基于遷移學(xué)習(xí)的進(jìn)化優(yōu)化框架，如圖1 所示.在圖1 中，模型庫(Model library，ML) 保存著進(jìn)化優(yōu)化算法所解決過的相似歷史問題信息.該模型庫保存的信息單元是mli=(fi，)，其中，fi和分別為所保存的第i個(gè)歷史問題及其最優(yōu)解集信息.由于需要利用歷史問題的解信息來指導(dǎo)新問題的求解，因此，模型庫中保存的歷史問題應(yīng)該與待求解問題屬于同一種(類) 問題，兩者應(yīng)該具有相似的編解碼策略和問題特征.

當(dāng)決策者獲得一個(gè)新的優(yōu)化問題時(shí)，首先，對(duì)模型庫進(jìn)行預(yù)處理，分析并判斷每個(gè)歷史問題是否與新問題具有相似的編解碼策略和特征，并刪除不相似和相似程度低的歷史問題;接著，利用模型匹配方法匹配模型庫中的信息，計(jì)算新問題與模型庫中已有歷史問題的相似度;找到匹配程度最高的歷史優(yōu)化問題，獲取其歷史數(shù)據(jù)，并將歷史問題的高質(zhì)量解遷移到新問題的進(jìn)化過程中，用來初始化新問題進(jìn)化種群中的部分個(gè)體;若沒有與之匹配的歷史優(yōu)化問題，則直接使用進(jìn)化算法求解優(yōu)化問題.在優(yōu)化當(dāng)前新問題時(shí)，將問題求解過程中得到的代表信息存儲(chǔ)到模型庫中，如此循環(huán)，隨著所解決問題數(shù)目的不斷加入，模型庫不斷增大，進(jìn)而有助于解決更多的優(yōu)化問題.分析上述進(jìn)化優(yōu)化框架可知，該框架存在如下三部分直接影響其最終性能，即模型匹配、相似歷

圖1 所提基于遷移學(xué)習(xí)的進(jìn)化算法框架Fig.1 Evolutionary algorithm framework based on transfer learning

2.1 基于多分布估計(jì)的模型匹配策略

將模型庫中保存的歷史問題信息作為源域知識(shí)，待解決的新問題看作目標(biāo)域任務(wù)，本文旨在利用已知源域知識(shí)去求解目標(biāo)域中的新問題.通常源域模型庫中存有的歷史問題或任務(wù)較多，如果歷史問題模型和目標(biāo)域中新問題的相似度較低或完全不同時(shí)，強(qiáng)制遷移可能會(huì)污染目標(biāo)域，產(chǎn)生負(fù)遷移現(xiàn)象.因此，如何準(zhǔn)確判斷源域和目標(biāo)域中問題的相似程度，從眾多的歷史問題或任務(wù)中選出最為相似的一個(gè)，將直接影響到目標(biāo)域優(yōu)化問題的求解效率.

最大均值差異(Maximum mean discrepancy，MMD) 是一種用來判斷兩個(gè)數(shù)據(jù)分布是否相同的指標(biāo)，最初主要用于雙樣本的檢測問題.近些年，學(xué)者們開始將其用于遷移學(xué)習(xí)中，利用源域數(shù)據(jù)集和目標(biāo)域數(shù)據(jù)集的均值差來表示源域和目標(biāo)域樣本之間的分布差異[25].MMD 的基本原理如下:假設(shè)有一個(gè)滿足Q1分布的源域數(shù)據(jù)集和一個(gè)滿足Q2分布的目標(biāo)域數(shù)據(jù)集Xt=令H為再生希爾伯特空間(Reproducing kernel Hilbert space，RKHS)，并且存在一個(gè)從原始空間到希爾伯特空間的映射函數(shù)F(·) :X →H，那么，當(dāng)n和m趨于無窮時(shí)，Xs和Xt在RKHS 上的最大均值差異可以表示為

然而，不同于傳統(tǒng)意義上的采樣數(shù)據(jù)(如傳感器數(shù)據(jù)、圖像數(shù)據(jù)等)，對(duì)于進(jìn)化種群產(chǎn)生的源域或目標(biāo)域樣本而言，由于所優(yōu)化問題通常包含若干個(gè)峰值，此時(shí)將源域或目標(biāo)域中所有樣本看成服從同一分布的整體，并采用MMD 判斷源域和目標(biāo)域問題的相似性，將很難準(zhǔn)確評(píng)價(jià)出它們的相似程度.

鑒于此，本文提出一種基于多分布估計(jì)的最大均值差異指標(biāo)，用來評(píng)價(jià)新問題與歷史問題之間的匹配程度，思想如下:首先，采用K-means 算法對(duì)源域和目標(biāo)域中樣本分別進(jìn)行聚類，并假設(shè)聚類后每一類中的樣本服從同一分布(注:傳統(tǒng)方法假設(shè)源域(目標(biāo)域) 中所有樣本服從同一分布);隨后，針對(duì)目標(biāo)域中的每一類，從源域中找到與其最為匹配的類，即MMD 值最小的類;最后，利用目標(biāo)域中所有樣本類的MMD 值的平均值，作為源域和目標(biāo)域樣本的整體相似性程度.

算法1.模型匹配策略

步驟4.2 利用目標(biāo)域中所有樣本類的最大均值差異的平均值，表示源域和目標(biāo)域的整體相似性程度.該平均值越小，源域和目標(biāo)域中樣本的分布越相似，進(jìn)而歷史問題和新問題越相似.循環(huán)執(zhí)行步驟2～4，直到計(jì)算出新問題與所有歷史問題相似程度值.最后，步驟5 選擇相似程度值最高(即最大均值差異的平均值最小) 的歷史問題，作為最終匹配結(jié)果.注意:當(dāng)源域和目標(biāo)域樣本數(shù)據(jù)具有不同的量綱時(shí)，需要對(duì)這些樣本進(jìn)行歸一化.式(4) 中映射函數(shù)選擇最為簡單的單位映射.

本文通過運(yùn)行一定迭代次數(shù)(Tlow) 的智能優(yōu)化算法產(chǎn)生目標(biāo)樣本.一方面，對(duì)于不同規(guī)模、不同操作流程的算法來說，它們通常具有不同的求解速度;另一方面，求解問題的復(fù)雜程度也對(duì)算法的迭代效率產(chǎn)生較大影響.因此，很難準(zhǔn)確估計(jì)出可以產(chǎn)生高質(zhì)量樣本(即可以高精度刻畫出問題解分布特性的個(gè)體) 的迭代次數(shù).算法1 利用少量迭代后的種群進(jìn)化結(jié)果作為目標(biāo)域樣本，具有如下特點(diǎn):1) 執(zhí)行少量迭代次數(shù)后，種群中的部分個(gè)體會(huì)接近多個(gè)最優(yōu)區(qū)域，而不會(huì)集中收斂到某個(gè)最優(yōu)區(qū)域，此時(shí)的種群樣本不僅具有較好的適應(yīng)值，而且多樣性相對(duì)較高;相反，如果迭代次數(shù)設(shè)置過大，在很大程度上種群中的大部分個(gè)體會(huì)集中收斂到某個(gè)最優(yōu)區(qū)域，此時(shí)的種群樣本雖然具有較好的適應(yīng)值，但其多樣性相對(duì)較差.2) 盡管通過加大種群的迭代次數(shù)，可以找到更為接近問題最優(yōu)解的樣本，但是，需要付出的計(jì)算代價(jià)也會(huì)隨之增加.更重要的是，在很多情況下，只需要找到較為接近問題最優(yōu)解的樣本，即可判斷出兩個(gè)問題的相似性.因此，在滿足樣本基本需要的基礎(chǔ)上，所提目標(biāo)域樣本產(chǎn)生方法還可以顯著減少樣本的產(chǎn)生代價(jià).

關(guān)于算法1 中迭代次數(shù)Tlow，一方面，由于無法事先判斷不同智能算法處理不同問題時(shí)的迭代速度與精度，很難給出適合所有算法的固定Tlow值;另一方面，如前所述，在很多情況下只需要找到較為接近問題最優(yōu)解的樣本，即可估計(jì)出兩個(gè)問題的相似性.因此，在一定程度上，可以放松對(duì)迭代次數(shù)Tlow取值的要求，本文建議Tlow取值為最大迭代次數(shù)的[1%，5%].具體而言，對(duì)于收斂速度較快的智能算法，可以取值為上述區(qū)間的下限值;相反，針對(duì)收斂速度較慢的智能算法，可以取值為上述區(qū)間的上限值.

2.2 源域匹配信息的利用

為加快進(jìn)化算法的搜索速度，給出一種基于源域匹配信息的種群初始化策略.當(dāng)從源域中找到與目標(biāo)域問題相匹配的歷史問題后，遷移源域中相似歷史問題的信息(解集信息)，用其生成新個(gè)體，并利用這些新個(gè)體替換目標(biāo)域中進(jìn)化種群的部分個(gè)體;為了增加種群多樣性、防止出現(xiàn)過遷移和欠遷移現(xiàn)象，根據(jù)歷史問題與新問題的相似度自動(dòng)設(shè)置替換初始種群的比例，即種群中被初始化個(gè)體的比例，具體計(jì)算式為

算法2.基于源域匹配信息的種群初始化策略

2.3 歷史模型庫的更新

對(duì)于已經(jīng)解決的歷史問題，保留求解問題過程中產(chǎn)生的歷史解信息，用于模型庫的更新.由于種群的進(jìn)化過程通常產(chǎn)生大量個(gè)體信息，保存所有個(gè)體信息代價(jià)較大.更為重要的是，這些個(gè)體信息中可能存在大量低價(jià)值甚至冗余的信息.

為此，本文給出一種基于迭代聚類的代表個(gè)體保存策略.該策略采用一種簡化的迭代K-means 算法，選擇種群迭代過程中產(chǎn)生的適應(yīng)值高且多樣性好的代表解集.進(jìn)一步，為減少模型庫更新的計(jì)算代價(jià)，設(shè)定一個(gè)更新頻率0≤μ ≤1，每間隔「μ ×Tmax代采樣一次種群進(jìn)化信息，用來更新所保存的代表個(gè)體.針對(duì)當(dāng)前優(yōu)化問題，基于迭代聚類的代表個(gè)體保存策略的步驟如下.

步驟1.初始化代表個(gè)體保存集合，以及初始類半徑.對(duì)第Tlow次迭代產(chǎn)生的種群，使用K-means算法(在決策變量空間中) 對(duì)其個(gè)體進(jìn)行聚類，將其劃分到ck個(gè)不同類中;從每一個(gè)類中選出適應(yīng)值最好的個(gè)體(即目標(biāo)函數(shù)值最小的個(gè)體)，保存到代表個(gè)體保存集合.計(jì)算集合中個(gè)體之間的兩兩距離，取距離最小值為初始類半徑.

步驟2.每間隔max代采樣一次種群進(jìn)化信息，更新代表個(gè)體保存集合中的元素(解) 及類半徑，直到算法結(jié)束.以某次更新為例，設(shè)現(xiàn)有代表個(gè)體集合為A={a1，a2，···，ack}，類半徑為r′，當(dāng)前種群為P={p1，p2，···，pN}，從P中第1 個(gè)個(gè)體起，依次檢查它與集合A中元素的位置和優(yōu)劣關(guān)系，由下述策略更新A中元素，直到檢查完種群中所有N個(gè)個(gè)體.以P中第i個(gè)個(gè)體pi為例，更新策略如下:先計(jì)算個(gè)體pi與集合A中每個(gè)元素之間的距離，從A中找到距離pi最近的元素，不妨設(shè)為amin，記兩者距離為d(pi，amin);接著，判斷兩者之間的位置和優(yōu)劣關(guān)系:1) 如果d(pi，amin)≤r′且pi的適應(yīng)值優(yōu)于amin的適應(yīng)值(即pi的目標(biāo)函數(shù)值小于amin的目標(biāo)函數(shù)值)，那么利用pi代替A中元素amin;2)d(pi，amin)≤r′，但pi的適應(yīng)值劣于amin的適應(yīng)值(即pi的目標(biāo)函數(shù)值大于amin的目標(biāo)函數(shù)值)，保持A中元素amin;3) 如果d(pi，amin)＞r′，且pi的適應(yīng)值優(yōu)于A中最差元素的適應(yīng)值(即pi的目標(biāo)函數(shù)值小于A中最差元素的目標(biāo)函數(shù)值)，那么，利用pi替換A中最差元素;4) 否則，刪除pi，保持A中元素不變.最后，計(jì)算集合A中個(gè)體之間的兩兩距離，取距離最小值為新的類半徑.

一方面，上述方法采用K-means 思想來更新代表解集，可以保持所選代表個(gè)體的多樣性;另一方面，當(dāng)新個(gè)體與A中某個(gè)元素同屬一個(gè)類時(shí)，只保留適應(yīng)值大的個(gè)體或元素，這樣可以保證所選代表個(gè)體具有高的適應(yīng)值.另外，除在開始階段采用傳統(tǒng)K-means 算法來產(chǎn)生初始化代表個(gè)體外，在后續(xù)更新A中元素時(shí)，上述方法采用簡化的K-means 算法，無需反復(fù)更新類中心，可以有效減少模型庫更新的計(jì)算復(fù)雜度.

2.4 基于相似歷史信息遷移的骨干粒子群優(yōu)化算法

為了進(jìn)一步說明所提進(jìn)化優(yōu)化框架的有效性，將一種改進(jìn)的骨干粒子群優(yōu)化算法(Bare-bone PSO，BBPSO)[26]嵌入到所提框架，給出一種基于相似歷史信息遷移的骨干粒子群優(yōu)化算法(Adaptive bare-bone particle swarm optimization based on transfer learning，TL-ABPSO).骨干粒子群優(yōu)化算法(BBPSO) 是一種改進(jìn)版本的粒子群優(yōu)化算法[27].與采用更新式(1) 和式(2) 的傳統(tǒng)粒子群優(yōu)化算法相比，BBPSO 刪除了粒子速度項(xiàng)、加速系數(shù)、慣性權(quán)值等控制參數(shù)，是一種少控制參數(shù)的新型粒子群優(yōu)化算法，算法結(jié)構(gòu)更為簡單，更加易于操作.然而，由于刪除了粒子速度項(xiàng)，BBPSO 算法存在易于陷入局部收斂的不足[27-28].為此，在先前工作中作者提出了一種改進(jìn)BBPSO 算法，即自適應(yīng)骨干粒子群算法(Adaptive bare-bone PSO，ABPSO)[26].該算法利用當(dāng)前粒子Xi與最佳粒子Gbest之間適應(yīng)值的差值，自適應(yīng)擾動(dòng)新生粒子位置，顯著提高了算法的全局搜索能力.以粒子Xi=(xi，1，xi，2，···，xi，N) 為例，ABPSO 所提粒子位置更新式為

其中，rand為[0，1]之間的隨機(jī)數(shù)，Pbestn1(t) 和Pbestn2(t) 為隨機(jī)選擇的兩個(gè)粒子的局部引導(dǎo)者;同上，Pbesti(t) 和Gbest(t) 分別為當(dāng)前粒子的局部和全局引導(dǎo)者，ft為目標(biāo)域中被優(yōu)化的新問題.

鑒于ABPSO 具有控制參數(shù)少、全局搜索能力強(qiáng)的優(yōu)點(diǎn)，本文將其嵌入到上述所提進(jìn)化框架，算法3 給出了基于相似歷史信息遷移的改進(jìn)骨干粒子群優(yōu)化算法的執(zhí)行步驟.對(duì)于一個(gè)新的優(yōu)化問題，首先隨機(jī)初始化粒子群，運(yùn)行Tlow代ABPSO，產(chǎn)生一個(gè)目標(biāo)域樣本;接著，利用第2.1 節(jié)方法從模型庫中尋找相匹配的歷史問題.如果發(fā)現(xiàn)匹配模型，利用第2.2 節(jié)方法遷移源域中相似歷史問題的信息，初始化第Tlow代粒子群中部分粒子的位置，繼續(xù)執(zhí)行ABPSO 相關(guān)算子，更新粒子位置;否則，直接執(zhí)行ABPSO 相關(guān)算子.在算法迭代過程中，每間隔「μ×Tmax代運(yùn)行一次第2.3 節(jié)方法，產(chǎn)生問題的代表個(gè)體集合.所提算法結(jié)束后，將被優(yōu)化問題及算法輸出的最終代表個(gè)體集合保存到模型庫中.

算法3.基于相似歷史信息遷移的骨干粒子群優(yōu)化算法

輸入.模型庫ML，粒子群規(guī)模N，代表個(gè)體集合的更新頻率μ，進(jìn)化代數(shù)Tlow，算法終止代數(shù)Tmax，聚類數(shù)目ck.

輸出.問題最優(yōu)解，模型庫.

步驟1.初始化.隨機(jī)初始化規(guī)模N的粒子群，初始化每個(gè)粒子的局部引導(dǎo)者為其自身;評(píng)價(jià)每個(gè)粒子的適應(yīng)值，設(shè)置所有粒子的全局引導(dǎo)者為種群最優(yōu)粒子的位置;初始化迭代次數(shù)為k=1.

步驟2.產(chǎn)生目標(biāo)域樣本.運(yùn)行Tlow代ABPSO，得到粒子群P(Tlow)，利用P(Tlow) 中粒子產(chǎn)生目標(biāo)域樣本.

步驟3.利用第2.1 節(jié)方法從模型庫ML中尋找相匹配的歷史問題.如果發(fā)現(xiàn)相匹配的歷史問題，執(zhí)行步驟4;否則，執(zhí)行步驟5.

步驟4.執(zhí)行第2.2 節(jié)方法，初始化P(Tlow) 中個(gè)隨機(jī)粒子的位置.

步驟5.k=Tlow，循環(huán)執(zhí)行ABPSO 中相關(guān)粒子更新算子，不斷更新粒子群，方法如下:

步驟5.1.評(píng)價(jià)粒子群P(k) 中所有粒子的適應(yīng)值;

步驟5.2.判斷Tmax/「μ×Tmax是否為整數(shù).如果是，利用第2.3 節(jié)方法更新代表個(gè)體保存集合;否則，執(zhí)行步驟5.3;

步驟5.3.采用常規(guī)方法更新粒子的局部引導(dǎo)者和全局引導(dǎo)者，具體更新方法可參加文獻(xiàn)[29];

步驟5.4.利用式(8) 更新粒子的位置;

步驟5.5.判斷算法是否得到終止代數(shù)Tmax.如果是，終止算法;否則，k=k+1，返回步驟5.2.

步驟6.輸出問題的最優(yōu)解，以及代表個(gè)體保存集合.

2.5 進(jìn)一步分析

將遷移學(xué)習(xí)的思想融入到進(jìn)化優(yōu)化框架，從已解決的相似歷史問題中提取有價(jià)值的歷史信息，用來指導(dǎo)新問題的進(jìn)化求解，上述進(jìn)化框架可以加速種群的進(jìn)化過程，提高算法的搜索效率.具體地，1)在利用相似歷史問題的遷移信息來初始化種群個(gè)體時(shí)，本文根據(jù)歷史問題與新問題的相似程度，自適應(yīng)確定遷移信息的使用程度，即種群中被遷移信息初始化的個(gè)體比例，可以有效防止出現(xiàn)負(fù)遷移或過遷移的現(xiàn)象，避免算法性能的退化;2)在更新和豐富歷史模型庫時(shí)，所給出的基于迭代聚類的代表樣本保存策略，在保證歷史樣本質(zhì)量的同時(shí)，還可以增強(qiáng)它們的多樣性，進(jìn)而能夠提高歷史遷移信息的多樣性，防止對(duì)單一歷史信息的過度學(xué)習(xí);3) 由于歷史遷移信息僅用來初始化種群中的部分個(gè)體，且初始化比例受新舊問題相似程度的嚴(yán)格限制，因此，在第3.4節(jié)中自適應(yīng)變異因子Δ，以及粒子全局引導(dǎo)者更新策略的作用下，本文所提TL-ABPSO 算法仍然能夠以概率1 收斂.具體收斂性證明，可參考我們先前的工作[26].

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

3.1 實(shí)驗(yàn)環(huán)境及測試函數(shù)

本節(jié)將所提TL-ABPSO 算法用于10 個(gè)改進(jìn)的標(biāo)準(zhǔn)測試函數(shù)，與包括ABPSO 在內(nèi)的4 種代表算法進(jìn)行比較，驗(yàn)證其性能.所用對(duì)比算法包括:標(biāo)準(zhǔn)的PSO 算法(Standard particle swarm optimization，SPSO)、基于突變和交叉的改進(jìn)骨干PSO 算法(Bare-bone particle swarm optimization with mutation and crossover，BBPSO-MC)[30]、基于跳躍策略的骨干PSO 算法(Bare-bone particle swarm optimization with jump，BBJ)[31]以及自適應(yīng)骨干PSO 算法(ABPSO)[26].所用實(shí)驗(yàn)采用相同環(huán)境，即Intel Core(TM)2 Duo、2.80 GHz 的CPU、2.00 GB RAM 存儲(chǔ).

采用MATLAB 2014b 實(shí)現(xiàn)所提算法，并構(gòu)建模型庫.表1 展示了模型庫中存儲(chǔ)的5 個(gè)經(jīng)典歷史測試函數(shù).首先，針對(duì)表1 給出的基本測試函數(shù)，運(yùn)行文獻(xiàn)[31]所提BBJ 算法，并采用第2.3 節(jié)方法保存迭代過程中適應(yīng)值高且多樣性好的代表解，產(chǎn)生初始模型庫信息.表2 給出了需要求解的10 個(gè)新的問題.這些新問題皆是表1 中函數(shù)的變形，在處理這些新優(yōu)化問題時(shí)，同樣采用第2.3 節(jié)方法將新問題的求解信息保存到模型庫中.表2 中測試函數(shù)可分為兩組，其中，F(xiàn)1～F5 為第1 組函數(shù)，該組函數(shù)在不改變測試函數(shù)的特點(diǎn)基礎(chǔ)上，對(duì)函數(shù)的參數(shù)進(jìn)行調(diào)整，使其全局最優(yōu)值發(fā)生變化.F6～F10 為第2 組函數(shù)，該組函數(shù)直接選自CEC2005 測試集合[32]，在整個(gè)搜索空間內(nèi)，其全局最優(yōu)值被任意移動(dòng)，具有旋轉(zhuǎn)、漂移和多模態(tài)等特點(diǎn).

表1 源域中保存的歷史優(yōu)化函數(shù)Table 1 Historical optimization functions saved in the source domain

表2 目標(biāo)域中新的優(yōu)化函數(shù)Table 2 New optimization functions in the target domain

3.2 評(píng)價(jià)標(biāo)準(zhǔn)及參數(shù)設(shè)置

本文采用三種不同的評(píng)價(jià)指標(biāo)，分別從成功率、收斂速度和精度方面來評(píng)價(jià)算法的有效性.

1) 成功率(SR).即算法找到全局最優(yōu)解的次數(shù)與實(shí)驗(yàn)總次數(shù)的比值.當(dāng)算法所得最優(yōu)解與真實(shí)最優(yōu)解誤差達(dá)到ε時(shí)，即認(rèn)為算法成功找到全局最優(yōu)解，其具體計(jì)算式為

其中，Sn′為算法找到全局最優(yōu)解的次數(shù)，Sn為實(shí)驗(yàn)總次數(shù)，本文取30 次.

2) 收斂速度(Time).算法的收斂速度由兩部分組成:a) 算法找到問題全局最優(yōu)解時(shí)所需要的平均評(píng)價(jià)次數(shù)Fave;b) 算法找到問題全局最優(yōu)解時(shí)所需要的平均時(shí)間(算法達(dá)到最大迭代次數(shù)時(shí)的平均運(yùn)行時(shí)間)Time.

算法找到問題全局最優(yōu)解時(shí)所需要的平均評(píng)價(jià)次數(shù)，計(jì)算式為

其中，Sn為實(shí)驗(yàn)總次數(shù)，ki為第i次運(yùn)行算法時(shí)找到全局最優(yōu)解的代數(shù).

3) 精度(AC).算法所得全局最優(yōu)解與函數(shù)真實(shí)最優(yōu)解之間的誤差，計(jì)算式為

其中，Xbest為算法找到的全局最優(yōu)解，opt為優(yōu)化函數(shù)的真實(shí)最優(yōu)解.當(dāng)兩者差值的絕對(duì)值小于誤差值ε時(shí)，表示算法已經(jīng)找到函數(shù)的真實(shí)最優(yōu)值.

本文的參數(shù)設(shè)置如下:實(shí)驗(yàn)中的所有算法，其種群或粒子群的規(guī)模為30，算法的最大評(píng)價(jià)次數(shù)為30 000 次.其他對(duì)比算法的參數(shù)設(shè)置參照相應(yīng)文獻(xiàn)，其中，SPSO 算法的慣性權(quán)重從0.9 線性遞減0.4;BBJ 算法采用全局鄰域，其尺度參數(shù)設(shè)為α=0.75;BBPSO-MC 算法中，其鄰域大小為2;ABPSO 算法中，突變概率為0.7;本文算法TL-ABPSO 中，聚類數(shù)目ck取為5.為便于比較算法的收斂速度，對(duì)于函數(shù)F8 和F9，設(shè)置成功誤差ε分別為100和10-3，其他函數(shù)皆設(shè)置誤差ε為10-8.

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

3.3.1 第1 組測試函數(shù)的實(shí)驗(yàn)結(jié)果分析

1)對(duì)于比較簡單的單模態(tài)優(yōu)化問題F1，SPSO、ABPSO 和TL-ABPSO 算法均能以100% 的成功率找到其全局最優(yōu)解，BBPSO-MC 和BBJ 算法的誤差精度也在很小的范圍之內(nèi).但是，通過比較Fave指標(biāo)可以看出，得益于所遷移相似歷史問題信息的幫助，本文算法TL-ABPSO 的收斂速度更快，其平均收斂代數(shù)為1.574×103，其他四種比較算法的最小迭代次數(shù)為2.635×103.

2) F2～F4 函數(shù)是多模態(tài)問題，隨著決策變量維數(shù)的增加，函數(shù)局部最優(yōu)解的數(shù)量呈指數(shù)增加.由表3 可知，對(duì)于函數(shù)F2，只有本文算法TL-ABPSO以100% 的成功率收斂到全局最優(yōu)點(diǎn);對(duì)于函數(shù)F3和F4，只有ABPSO 和TL-ABPSO 算法的成功率是100%;與其他四種比較算法的Fave指標(biāo)相比，TL-ABPSO 算法明顯優(yōu)于其他四種算法.

3) F5 函數(shù)是一個(gè)單峰函數(shù)，決策變量之間具有很強(qiáng)的相關(guān)性，且梯度信息經(jīng)常誤導(dǎo)算法的搜索方向.如表3 所示，所有算法均沒有成功找到全局最優(yōu)解，但是，比較算法的精度誤差指標(biāo)AC可知，ABPSO 和TL-ABPSO 算法明顯好于其他三種算法.這其中得益于本文采用的歷史問題遷移學(xué)習(xí)策略，TL-ABPSO 算法精度又好于ABPSO 算法.

4) 在算法運(yùn)行時(shí)間方面，由于增加了模型匹配等測試，在相同迭代次數(shù)下，本文算法TL-ABPSO的運(yùn)算時(shí)間要高于其他四種比較算法，如函數(shù)F5;然而，通過剩余4 個(gè)函數(shù)的運(yùn)行結(jié)果可以看出，由于顯著縮短了種群找到最優(yōu)解的迭代次數(shù)，TLABPSO 找到最優(yōu)解的時(shí)間花費(fèi)并不比其他算法高;對(duì)于函數(shù)F3 和F4，TL-ABPSO 甚至取得了最小的時(shí)間花費(fèi)值.好于其他三種算法，其中得益于本文所采用歷史遷移學(xué)習(xí)策略，TL-ABPSO 算法的精度又好于ABPSO 算法.

3.3.2 第2 組測試函數(shù)實(shí)驗(yàn)結(jié)果分析

針對(duì)表2 中F6～F10 等5 個(gè)復(fù)雜測試函數(shù)，分別運(yùn)行每種比較算法30 次，表4 給出了本文算法TL-ABPSO、SPSO、ABPSO、BBPSO-MC 和BBJ 等所得評(píng)價(jià)指標(biāo)的平均結(jié)果.可以看出:

1) 對(duì)于相對(duì)簡單的函數(shù)F6，SPSO、ABPSO、TL-ABPSO 算法都能以100% 的成功率找到它們的全局最優(yōu)解;但是，通過比較Fave指標(biāo)可以看出，得益于所遷移相似歷史問題信息的幫助，本文算法TL-ABPSO 的收斂速度更快，其平均收斂代數(shù)為1.421×102，其他四種比較算法的最小迭代次數(shù)為1.065×102.

2) 對(duì)于函數(shù)F7，ABPSO 和TL-ABPSO 的成功率分別為72% 和100%，高于BBPSO-MC 和BBJ 的成功率(33.33% 和50%);進(jìn)一步，得益于本文所采用的歷史問題遷移學(xué)習(xí)策略，TL-ABPSO算法的收斂速度明顯好于ABPSO 的收斂速度，TLABPSO 算法找到問題全局最優(yōu)解時(shí)所需要的平均評(píng)價(jià)次數(shù)(即Fave指標(biāo)) 為7.467×103.

3) 對(duì)于函數(shù)F8 而言，五種算法均沒有100%地找到其全局最優(yōu)解，其中，TL-ABPSO 算法的成功率最高，為63.33%;進(jìn)一步，比較ABPSO 和TLABPSO 算法的結(jié)果，類似于函數(shù)F7，TL-ABPSO算法的收斂速度好于ABPSO 的收斂速度，且TLABPSO 算法的誤差指標(biāo)AC高于ABPSO 算法.

4) 對(duì)于具有多模、旋轉(zhuǎn)和不可分離等特點(diǎn)的復(fù)雜函數(shù)F9 和F10，五種算法均沒有成功地找到其全局最優(yōu)解;五種算法的成功率都是0;但是，比較其精度誤差指標(biāo)AC可知，ABPSO 和TL-ABPSO算法明顯好于其他三種算法，其中，得益于本文所采用歷史遷移學(xué)習(xí)策略，TL-ABPSO 算法的精度又好于ABPSO 算法.

5) 對(duì)于復(fù)雜函數(shù)F8～F10，在相同迭代次數(shù)下，盡管本文算法TL-ABPSO 的運(yùn)算時(shí)間要高于其他四種比較算法，但是，其結(jié)果的精度皆優(yōu)于其他四種比較算法;SPSO 算法的運(yùn)算時(shí)間最短，但其運(yùn)行結(jié)果的精度較差.對(duì)于函數(shù)F6 和F7，由于顯著縮短了種群找到最優(yōu)解的迭代次數(shù)，本文算法TL-ABPSO找到最優(yōu)解的時(shí)間花費(fèi)要小于其他四種比較算法.

表3 比較算法優(yōu)化第1 組測試函數(shù)所得實(shí)驗(yàn)結(jié)果Table 3 Experimental results obtained by comparison algorithm for the first set of test functions

3.3.3 ABPSO 和TL-ABPSO 算法比較

本小節(jié)單獨(dú)比較ABPSO 和TL-ABPSO 的收斂效果.如前所述，本文所提TL-ABPSO 是ABPSO 算法和歷史問題遷移學(xué)習(xí)策略的結(jié)合體.通過比較兩種算法的收斂效果，可以反映出所提歷史問題遷移學(xué)習(xí)策略的有效性.圖2 展示了優(yōu)化第1 組測試函數(shù)時(shí)兩種算法的收斂曲線.可以看出，TL-ABPSO 算法的進(jìn)化趨勢和ABPSO 算法大致相同，加入遷移策略后并沒有影響算法本身的搜索機(jī)理;但是，得益于所遷移歷史問題最優(yōu)解信息的幫助，TL-ABPSO 算法的收斂速度始終明顯好于ABPSO 算法.

3.4 實(shí)驗(yàn)拓展及補(bǔ)充

3.4.1 遷移學(xué)習(xí)策略在差分進(jìn)化算法中的應(yīng)用

上述工作成功地將遷移學(xué)習(xí)策略加入到了骨干粒子群優(yōu)化算法中，實(shí)驗(yàn)結(jié)果也說明了遷移學(xué)習(xí)策略的有效性.本小節(jié)嘗試將所提遷移學(xué)習(xí)策略加入到另一種典型的優(yōu)化算法，即自適應(yīng)差分進(jìn)化算法[33]中，以驗(yàn)證遷移學(xué)習(xí)策略在不同進(jìn)化算法中的效果.由此，給出一種基于相似歷史信息遷移學(xué)習(xí)的自適應(yīng)差分進(jìn)化算法，簡稱TL-DE 算法.

為了驗(yàn)證TL-DE 算法的有效性，選擇在第1 組測試函數(shù)上進(jìn)行實(shí)驗(yàn)，算法參數(shù)設(shè)置為種群規(guī)模50，使用“DE/rand/1”變異策略，縮放因子為0.5，交叉概率為0.9，最大進(jìn)化代數(shù)為3 000.圖3 展示了優(yōu)化第1 組測試函數(shù)時(shí)兩種算法的收斂曲線.可以看出，在進(jìn)化初期，TL-DE 算法的收斂速度明顯好于DE算法;在進(jìn)化后期，對(duì)于大部分函數(shù)，TL-DE 算法所得結(jié)果也明顯好于DE 算法.這進(jìn)一步說明，加入遷移學(xué)習(xí)的進(jìn)化算法不僅可以節(jié)省進(jìn)化成本，加速種群的進(jìn)化過程，而且可以提高算法的求解精度.因此，本文所提于歷史信息遷移的進(jìn)化優(yōu)化框架同樣適用于差分進(jìn)化算法.

表4 比較算法優(yōu)化第2 組測試函數(shù)所得實(shí)驗(yàn)結(jié)果Table 4 Experimental results obtained by comparison algorithm for the second set of test functions

3.4.2 聚類數(shù)目ccckkk 的敏感性分析

由于影響歷史問題與新問題的匹配精度，聚類數(shù)目ck的取值非常關(guān)鍵.聚類數(shù)目ck設(shè)置過小，聚類結(jié)果不能有效反映解分布的多樣性;而聚類數(shù)目過大，每一類中保存的樣本較少，利用少量樣本學(xué)習(xí)得到的解分布模型通常不精確.基于優(yōu)化問題的復(fù)雜程度和解分布特點(diǎn)，可以設(shè)置合理的ck值，但是準(zhǔn)確獲取這些信息往往需要決策者具有一定的問題先驗(yàn)知識(shí)，這在很多實(shí)際情況下是不可能或者需要花費(fèi)太多代價(jià)的.本節(jié)通過實(shí)驗(yàn)分析聚類數(shù)目ck值對(duì)算法性能的影響，旨在給決策者提供一個(gè)較為合理的ck取值范圍.

鑒于此，選擇第1 組測試函數(shù)為例，參數(shù)ck分別取值為3，5，7，10，運(yùn)行TL-ABPSO 算法30 次，圖4 給出了在不同參數(shù)ck取值下，TL-ABPSO 找到問題最優(yōu)解所需平均迭代次數(shù).可以看出，聚類數(shù)目ck取3 或者10 時(shí)，TL-ABPSO 算法可以找到問題的全局最優(yōu)解，但其所需迭代次數(shù)要大于ck取5 和7 的情況;當(dāng)聚類數(shù)目ck取5 或者7 時(shí)，TL-ABPSO 算法能夠以較快的速度找到問題的全局最優(yōu)解.這在一定程度上歸功于由聚類數(shù)目ck間接決定的種群初始化比例ratio，合適的種群初始化比例明顯提高了算法的搜索速度.

4 結(jié)論

圖2 優(yōu)化第1 組測試函數(shù)時(shí)ABPSO 和TL-ABPSO 算法的收斂曲線Fig.2 Convergence curves of ABPSO and TL-ABPSO algorithms for the first set of test functions

圖3 優(yōu)化第1 組測試函數(shù)時(shí)DE 和TL-DE 算法的收斂曲線Fig.3 Convergence curves of DE and TL-DE algorithms for the first set of test functions

本文研究了一種基于相似歷史信息遷移學(xué)習(xí)的進(jìn)化優(yōu)化框架.針對(duì)框架中歷史模型匹配、歷史信息的遷移學(xué)習(xí)和模型庫更新等關(guān)鍵算子，分別提出了基于多分布估計(jì)最大均值差異的歷史模型匹配策略、基于模型匹配程度的進(jìn)化種群初始化策略，以及于基于迭代聚類的模型庫更新策略.通過從模型庫中找到與新問題匹配的歷史問題，并將其知識(shí)遷移到新問題的進(jìn)化優(yōu)化過程中，該框架明顯提高了算法的搜索效率.將已有的粒子群優(yōu)化算法和差分進(jìn)化算法分別嵌入到所提進(jìn)化優(yōu)化框架，給出了基于相似歷史信息遷移學(xué)習(xí)的骨干粒子群優(yōu)化算法和基于相似歷史信息遷移學(xué)習(xí)的自適應(yīng)差分進(jìn)化算法.兩種算法在10 個(gè)典型測試問題上的應(yīng)用表明，本文所提基于相似歷史問題的遷移學(xué)習(xí)機(jī)制，不僅可以明顯加速種群進(jìn)化過程，而且能夠提高算法的求解質(zhì)量.

然而，不可否認(rèn)，本文所提策略需要?dú)v史和新問題同屬一種問題，而且它們應(yīng)該具有相似的編解碼策略和特性，這限制了所提進(jìn)化框架的應(yīng)用范圍.是否可以在兩種不同問題(如背包問題和設(shè)施布局問題等) 之間進(jìn)行求解信息或求解規(guī)則的遷移，將是我們今后研究的重點(diǎn);此外，如何降低模型匹配等策略帶來的計(jì)算復(fù)雜度問題，也是今后需要研究的內(nèi)容.

圖4 在不同參數(shù)ck 取值下，TL-ABPSO 找到問題最優(yōu)解所需平均迭代次數(shù)Fig.4 The average iteration time required by TL-ABPSO to find the optimal solution under different ck value