一種求解復(fù)雜優(yōu)化問題的快速遺傳算法算子

裴 瑩, 蘇 山, 付加勝, 韓霄松

(1. 長春財(cái)經(jīng)學(xué)院 信息工程學(xué)院, 長春 130122； 2. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 符號計(jì)算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室, 長春 130012； 3. 中國石油集團(tuán)工程技術(shù)研究院有限公司 鉆井工藝研究所, 北京102206)

遺傳算法(genetic algorithm, GA)是一種啟發(fā)式的搜索策略, 通過模擬生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理搜索最優(yōu)解[1]. Holland[1]提出的模式定理和積木塊假說為GA提供了理論依據(jù). GA源于一組候選解決方案的種群, 其中每個(gè)候選解決方案是該種群的個(gè)體或染色體, 染色體通過基因進(jìn)行編碼得到. 根據(jù)優(yōu)勝劣汰原則, 將種群中的染色體通過交叉、 選擇和變異等操作, 產(chǎn)生含有更好解決方案的新群體. 產(chǎn)生的新種群每一代都不弱于前一代, 直到滿足進(jìn)化終止條件, 最優(yōu)個(gè)體被解碼并被用于問題的最佳解決方案. GA由于結(jié)構(gòu)簡單并具有強(qiáng)大的全局搜索能力, 廣泛應(yīng)用于機(jī)器人與自動控制[2]、 交通調(diào)度[3]、 車間調(diào)度[4]和神經(jīng)網(wǎng)絡(luò)訓(xùn)練[5]等領(lǐng)域.

分析表明, GA的運(yùn)行依賴于大規(guī)模的個(gè)體適應(yīng)度計(jì)算, 當(dāng)適應(yīng)度計(jì)算較復(fù)雜時(shí), GA尋優(yōu)過程十分耗時(shí). 很多優(yōu)化問題(尤其在工業(yè)領(lǐng)域)需要優(yōu)化的參數(shù)維度通常較高(high-dimensional), 適應(yīng)度計(jì)算復(fù)雜(expensive-computationally), 且有些優(yōu)化問題無法得到數(shù)學(xué)解析式, 解決方案的優(yōu)劣依賴于其他工具(black-box), 這類優(yōu)化問題的優(yōu)化較困難, 被稱為HEB問題[6]. 針對HEB問題, 目前已有很多研究成果： Branke等[7]利用鄰近個(gè)體的適應(yīng)度值通過插值和回歸估計(jì)個(gè)體的適應(yīng)度, 取得了較好的實(shí)驗(yàn)結(jié)果； Regis[8-11]將代理模型融合到粒子群等算法中, 得到了良好的實(shí)驗(yàn)結(jié)果, 并將其應(yīng)用到地下水除污等實(shí)際問題中[12-13]; 劉全等[14]提出了一種雙精英聯(lián)合遺傳算法避免了GA的早熟問題, 提高了收斂速度； Yoel[15-16]利用分類器預(yù)測能導(dǎo)致適應(yīng)度計(jì)算失敗的參數(shù)組合, 通過篩選參數(shù)組合達(dá)到提升算法效率的目的； Han等[17]提出的EGA算法(efficient GA)中構(gòu)建了聚類算法和模式理論的適應(yīng)度估計(jì)策略, 通過減少適應(yīng)度計(jì)算次數(shù)有效加速GA, 實(shí)驗(yàn)結(jié)果表明, EGA算法在保證速度的同時(shí)具有與經(jīng)典GA相似的優(yōu)化精度, 并將該算法擴(kuò)展到粒子群算法中, 取得了較好的效果[18].

上述研究大多數(shù)采用代理模型策略替代適應(yīng)度函數(shù), 從而通過減少調(diào)用真實(shí)適應(yīng)度函數(shù)方法加快尋優(yōu)速度. 通過提高算法收斂速度是解決HEB問題的另一種思路, 文獻(xiàn)[19]提出的基于全局最優(yōu)預(yù)測的自適應(yīng)變異粒子群優(yōu)化算法(global prediction-based adaptive mutation PSO, GPAM-PSO), 利用主成分分析(PCA)算法對群體進(jìn)行降維, 并在低維空間擬合曲面尋找更優(yōu)粒子引導(dǎo)群體進(jìn)化, 算法引入了自適應(yīng)的變異策略避免陷入局部極值, 實(shí)驗(yàn)結(jié)果表明, GPAM-PSO算法相比于經(jīng)典粒子群算法可以更快地收斂. 本文將GPAM-PSO的核心思想擴(kuò)展到GA, 提出通過聚集算子(aggregation operator)在GA進(jìn)化中發(fā)現(xiàn)更優(yōu)的個(gè)體引導(dǎo)種群進(jìn)化, 從而使GA可以快速收斂.

1 聚集算子

對GA的算法流程分析表明, 種群中新個(gè)體的產(chǎn)生全部來源于交叉和變異操作, 其中絕大多數(shù)來源于交叉操作, 但兩兩交叉不是每次都產(chǎn)生更好的個(gè)體, 因而會使算法收斂速度緩慢, 且具有隨機(jī)性, 易產(chǎn)生早熟現(xiàn)象. 為解決該問題, 本文在GA中引入聚集算子, 該算子首先采用聚類方法對群體進(jìn)行劃分, 然后對聚類后的每一簇個(gè)體用PCA算法進(jìn)行降維, 再采用最小二乘法對降維后的種群個(gè)體分布進(jìn)行擬合, 并求出低維空間下的優(yōu)勢個(gè)體, 最后將該個(gè)體還原到初始空間保存到下一代種群. 聚集算子流程如圖1所示.

圖1 聚集算子流程

圖2對聚集算子的有效性進(jìn)行了解釋, 其中紅色五角星位置為最優(yōu)位置, 藍(lán)色三角星為每一代聚集算子產(chǎn)生的優(yōu)勢染色體位置, 優(yōu)勢染色體將引導(dǎo)種群向最優(yōu)值靠近, 從而加速了搜索方法. 聚集算子主要包括GA種群劃分、 種群降維、 低維空間下種群分布擬合、 優(yōu)勢染色體發(fā)現(xiàn)和優(yōu)勢染色體返回五部分.

圖2 聚集算子特征

1.1 基于AP聚類的GA種群劃分

GPAM-PSO算法中每次迭代僅生成一個(gè)優(yōu)勢個(gè)體, PSO算法的特點(diǎn)為保證所有粒子都會向優(yōu)勢個(gè)體聚集. 但GA中如果每次進(jìn)化僅產(chǎn)生一個(gè)優(yōu)勢個(gè)體, 由于GA選擇操作的隨機(jī)性, 該個(gè)體不一定發(fā)揮作用, 為更大程度地利用優(yōu)勢個(gè)體, 在GA中提出的聚集算子每次迭代將產(chǎn)生多個(gè)優(yōu)勢個(gè)體. 方法是對GA臨時(shí)種群進(jìn)行聚類, 每個(gè)聚簇產(chǎn)生一個(gè)優(yōu)勢個(gè)體. 本文采用AP(affinity propagation)聚類對GA種群進(jìn)行劃分, 基于數(shù)據(jù)點(diǎn)間的“信息傳遞”進(jìn)行聚簇, 每次迭代計(jì)算并傳播每個(gè)數(shù)據(jù)點(diǎn)的吸引度和歸屬度[20], 計(jì)算公式為

(1)

(2)

(3)

吸引度r(i,j)由數(shù)據(jù)點(diǎn)i傳向候選聚類中心j, 表示點(diǎn)j作為點(diǎn)i聚類中心的累積證據(jù)； 歸屬度a(i,j)由候選聚類中心j傳向數(shù)據(jù)點(diǎn)i, 表示以點(diǎn)j作為聚類中心的聚類包含點(diǎn)i的累積證據(jù)；s表示兩個(gè)數(shù)據(jù)點(diǎn)的相似性, 一般采用負(fù)的歐氏距離. 對上述步驟進(jìn)行迭代, 若歸屬度和吸引度保持不變或者在一個(gè)小范圍內(nèi)振蕩, 或者算法執(zhí)行超過設(shè)定的迭代次數(shù)則算法結(jié)束. 為避免振蕩, AP聚類更新信息時(shí)引入了衰減系數(shù)λ, 則吸引度和歸屬度公式更新為

rt+1(i,k)←(1-λ)rt+1(i,k)+λrt(i,k),

(4)

at+1(i,k)←(1-λ)at+1(i,k)+λat(i,k).

(5)

相比于傳統(tǒng)聚類算法, AP聚類可根據(jù)數(shù)據(jù)分布自動確定聚類數(shù)目, 聚類中心是真實(shí)存在的點(diǎn), 結(jié)果穩(wěn)定且誤差小. 這些特征十分適合對沒有先驗(yàn)信息的GA種群進(jìn)行聚類, 可根據(jù)當(dāng)前種群結(jié)構(gòu)自適應(yīng)地聚類從而達(dá)到有效劃分的目的. 在GA迭代過程中, 為保持聚簇內(nèi)元素?cái)?shù)量, 當(dāng)元素?cái)?shù)小于6時(shí), 合并除主要聚簇外的聚簇. 這種處理方法的優(yōu)點(diǎn)是: 在大型聚簇中進(jìn)行了開發(fā)操作, 在多個(gè)小型聚簇上進(jìn)行探索操作, 提高收斂速度的同時(shí)避免了早熟.

1.2 基于PCA的GA種群降維

主成分分析(principal component analysis, PCA)是經(jīng)典的無監(jiān)督降維算法, 通過正交變換將數(shù)據(jù)特征轉(zhuǎn)換為一組線性不相關(guān)的新特征, 選擇新特征在更小維度下展示數(shù)據(jù)的特征. 方法是對數(shù)據(jù)進(jìn)行中心化后的協(xié)方差矩陣進(jìn)行奇異值(SVD)分解, 原始數(shù)據(jù)通過SVD分解的旋轉(zhuǎn)矩陣得到新特征, 然后根據(jù)特征值大小選擇主成分進(jìn)行降維, 利用旋轉(zhuǎn)矩陣的轉(zhuǎn)置可從新特征返回到原始數(shù)據(jù). PCA是最簡單有效的降維方法之一, 且實(shí)現(xiàn)簡單、 算法復(fù)雜度低, 用在聚集算子中不會給算法帶來額外的開銷. 本文提出的聚集算子采用PCA可快速對種群進(jìn)行降維, 在低維空間中可采用簡單的回歸算法擬合種群結(jié)構(gòu), 利用擬合曲面快速發(fā)現(xiàn)優(yōu)勢個(gè)體, 并利用PCA將優(yōu)勢染色體返回到原始空間.

1.3 基于WLS的GA種群結(jié)構(gòu)擬合及優(yōu)勢個(gè)體發(fā)現(xiàn)

最小二乘法(ordinary least squares, OLS)是一種解決數(shù)學(xué)優(yōu)化問題的有效方法, 其計(jì)算方式是利用最小誤差平方和找到最符合所有數(shù)據(jù)的曲線或曲面. 為能在本文提出的聚集算子中快速發(fā)現(xiàn)優(yōu)勢個(gè)體, 本文利用OLS在低維空間擬合一個(gè)二次曲面, 從而利用二次函數(shù)的求解公式得到曲面極值位置的數(shù)學(xué)解析解. 為提高OLS泛化能力, 本文采用加權(quán)最小二乘法(weighted OLS, WLS), WLS給每個(gè)觀測值分配一個(gè)反映測量不確定度的權(quán)重wi, 其最小二乘準(zhǔn)則為

(6)

其中ε表示誤差, 即要最小化的量, {Xi,Yi}為觀測量,a和b分別為回歸線的截距和斜率.

算法1融合聚集算子的遺傳算法(genetic algorithm with aggregation operator, aGA).

步驟1) 初始化： 指定AP聚類P值, 設(shè)置PCA特征選擇數(shù)目n或特征累計(jì)占比閾值θ, 進(jìn)化代數(shù)計(jì)數(shù)器t=0, 設(shè)置最大進(jìn)化代數(shù)T及適應(yīng)度評價(jià)函數(shù)f, 函數(shù)隨機(jī)生成M個(gè)染色體作為初始種群P(0)；

步驟2) 個(gè)體評價(jià)： 利用適應(yīng)度函數(shù)f計(jì)算種群P(t)中每個(gè)染色體的適應(yīng)度；

步驟3) 傳統(tǒng)算子作用在種群上；

① 選擇運(yùn)算： 將選擇算子作用于種群；

② 交叉運(yùn)算： 將交叉算子作用于種群；

③ 變異運(yùn)算： 將變異算子作用于種群；

步驟4) 種群P(t)經(jīng)過選擇、 交叉、 變異運(yùn)算后得到臨時(shí)種群P(t0)；

步驟5) 聚集算子作用在臨時(shí)種群P(t0), 合并較小聚簇；

① AP聚類算法將種群P(t0)劃分成N簇；

② PCA算法對每簇進(jìn)行降維, 保存n個(gè)最大成分, 或者累加占比超過θ的n個(gè)主成分；

③ WLS算法將每簇?cái)M合成二次曲面并求得極值, 發(fā)現(xiàn)優(yōu)勢染色體；

④ 將N個(gè)優(yōu)勢染色體利用PCA旋轉(zhuǎn)矩陣返回原始空間加入臨時(shí)種群P(t0)；

步驟6) 選擇算子從臨時(shí)種群P(t0)選擇個(gè)體產(chǎn)生新種群P(t+1)；

步驟7) 終止條件判斷： 若t=T, 則以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出, 終止計(jì)算.

2 數(shù)值實(shí)驗(yàn)

2.1 實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證算法聚集算子的效率, 本文選取10個(gè)Benchmark函數(shù)和經(jīng)典GA對比, 包括3個(gè)單峰函數(shù)和7個(gè)多峰函數(shù), 測試函數(shù)信息列于表1. 算法實(shí)驗(yàn)的種群大小為100, 最大迭代次數(shù)為50次, 優(yōu)化參數(shù)采用30維. 為對比方便, 將適應(yīng)度規(guī)約為0～100.

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

針對表1中的每個(gè)測試函數(shù), aGA和GA分別運(yùn)行10次, 每種算法的平均迭代曲線如圖3所示, 平均最優(yōu)適應(yīng)度和收斂位置列于表2.

表1 測試函數(shù)

表2 測試函數(shù)結(jié)果

圖3 測試函數(shù)迭代曲線

由圖3和表2可見: 在單峰函數(shù)實(shí)驗(yàn)中, aGA都快速達(dá)到近似最優(yōu)解, GA緩慢達(dá)到最優(yōu)解； 在多峰函數(shù)中, 3個(gè)函數(shù)Weierstrass,Ackley,Rastrigin在aGA中不僅快速收斂, 而且最優(yōu)值優(yōu)于GA, 其他函數(shù)雖然最終收斂值未超過GA, 但優(yōu)化精度接近, 除Schwfel函數(shù)外收斂速度明顯提升. 盡管由于引入聚集算子使每次迭代比較耗時(shí), 但聚集算子可使GA迭代幾次后快速收斂. 實(shí)驗(yàn)結(jié)果表明, 當(dāng)適應(yīng)度計(jì)算十分耗時(shí)時(shí), 如當(dāng)適應(yīng)度計(jì)算超過10 ms時(shí)或?qū)⑺惴ńK止條件設(shè)為連續(xù)5代適應(yīng)度不發(fā)生改變時(shí), aGA的優(yōu)勢明顯.

綜上所述, 本文在遺傳算法中引入了聚集算子, 該算子利用AP聚類對群體進(jìn)行劃分后, 通過PCA對每一聚簇進(jìn)行降維, 在低維空間利用加權(quán)最小二乘法將聚簇分布擬合成二次曲面, 并將求得的極值作為優(yōu)勢染色體返回到原始群體, 從而引導(dǎo)遺傳算法快速收斂. 10個(gè)標(biāo)準(zhǔn)測試函數(shù)的測試結(jié)果證明了該算法的有效性.