基于啟發(fā)式變異的改進演化規(guī)劃算法*

胡廉民 黃翰 蔡昭權(quán)

(1.華南理工大學(xué) 計算機科學(xué)與工程學(xué)院，廣東 廣州 510006;2.華南理工大學(xué) 軟件學(xué)院，廣東 廣州 510006;3.惠州學(xué)院 科技處，廣東 惠州 516007)

在演化計算領(lǐng)域，經(jīng)典的演化算法包括了三類:遺傳算法(GA)、演化規(guī)劃(EP)和演化策略(ES)［1］.GA 主要針對組合優(yōu)化問題，EP 和ES 多用于求解連續(xù)優(yōu)化問題.演化規(guī)劃最初是以有限狀態(tài)機技術(shù)出現(xiàn)，后來推廣應(yīng)用到連續(xù)優(yōu)化問題、組合優(yōu)化問題和實際的工程優(yōu)化問題［1］.在20 世紀90 年代，EP的研究主要在于參數(shù)對求解效果的影響和自適應(yīng)策略的設(shè)計.研究學(xué)者又提出了多種EP 的版本，主要是將不同的分布函數(shù)融入變異算子的設(shè)計.

簡單的EP 算法來源于GA 的一個簡化變型，主要是采用基于均勻分布的變異算子.比較成功的第一種演化規(guī)劃算法是基于Gauss 變異的EP(CEP)算法，其求解結(jié)果比非自適應(yīng)高斯變異EP 算法更好.Yao 等［2］曾指出Gauss 變異EP 比較適用于單峰優(yōu)化函數(shù)的求解，或者峰值分布較密的多峰函數(shù)，具有較強的局部搜索能力.他的一項重要研究成果是將Cauchy 分布引入到演化規(guī)劃中［2］，設(shè)計了Cauchy 變異EP 算法(FEP)，得到了比Gauss 變異EP 更高效率的優(yōu)化結(jié)果.Lee 等［3］將Lévy 分布引入到演化規(guī)劃的變異算子設(shè)計，設(shè)計了Lévy 變異演化規(guī)劃(LEP).Gauss 變異EP 適用于峰值分布較密的優(yōu)化問題，Cauchy 變異EP 則適用于峰值分布較疏的優(yōu)化問題.

除了EP 的設(shè)計研究以外，EP 的理論研究也有一定的進展，主要是集中在收斂性的分析研究上.劉峰等［4］基于Markov 過程也給出了Gauss 變異EP 算法的收斂性分析.Rudolph 和劉峰等［4-5］的主要研究成果是針對連續(xù)狀態(tài)空間，比Fogel［6］的研究更有普遍性意義.高永超等［7］將模擬退火策略引入了EP，并分析了其收斂性.王向軍等［8-9］設(shè)計了雙種群和多種群的演化規(guī)劃算法.杜海峰等［10］設(shè)計了自適應(yīng)混沌克隆演化規(guī)劃算法，并證明了該算法的收斂性.郝志峰等［11-12］分析了Gauss 變異和Cauchy 變異演化規(guī)劃算法的計算時間，為EP 算法的改進提供了理論依據(jù);蔡昭權(quán)等［13］分析了Lévy 變異進化規(guī)劃算法的計算時間.黃翰和蔡昭權(quán)等［11，13-14］總結(jié)了這些工作，提出了分析進化算法收斂性對比的模型與分析框架.張宇山等［15］發(fā)展了這一理論并分析二元演化策略的計算時間，強調(diào)了啟發(fā)式策略對算法的重要作用.上述工作為研究演化規(guī)劃算法的改進提供了重要的理論依據(jù).

變異擾動的設(shè)置和更新是演化規(guī)劃算法改進設(shè)計的關(guān)鍵點［16-17］.現(xiàn)有的EP 算法的變異擾動與優(yōu)化變量無關(guān)，所以很難有效地引導(dǎo)算法求解.本研究將重新設(shè)計變異步長向量，使得EP 算法的變異擾動可以隨著優(yōu)化變量的狀態(tài)動態(tài)更新，實現(xiàn)算法的啟發(fā)式迭代.

1 演化規(guī)劃算法基本介紹

演化規(guī)劃算法主要是用于求解連續(xù)優(yōu)化問題.

可以假設(shè)f 滿足:f 是有界函數(shù);整體的極小(極大)值點集arg f*非空;f 是定義在S 上的;對于ε ＞0，集合}滿足:Mε的Lebesgue測度m(Mε)＞0.其中，f*=min{f(x )x∈S}(以極小化問題為例).

演化規(guī)劃算法主要包含以下步驟:

(1)任意生成K 個初始個體，每個個體是一對實值向量(xi，σi)，i =1，2，…，K.其中，xi是待優(yōu)化的目標向量，σi是xi的變異步長向量.設(shè)置t=1.

(2)據(jù)目標函數(shù)f(xi)評估每一個個體(xi，σi)的適應(yīng)值.

(3)對于每個個體(xi，σi)，執(zhí)行相應(yīng)的分布函數(shù)生成子代個體(x'i，σ'i).

(4)將父代個體和子代個體合并一起，用錦標賽法［3］選擇出K 個獲勝次數(shù)最多的個體作為下一次迭代的父代.

(5)若滿足停機條件，則輸出當前最優(yōu)解并退出算法;否則，迭代次數(shù)t=t+1，返回步驟(3).

在步驟(2)中，不同的EP 算法用不同的分布函數(shù)產(chǎn)生變異擾動，體現(xiàn)在式(2)的Fj.

式中:N(0，1)為一個標準正態(tài)分布的隨機變量，對于每個i 產(chǎn)生一次;Nj(0，1)為對于每個j 產(chǎn)生一次的標準正態(tài)分布隨機變量，j =1，2，…，n;參數(shù) =Fj為服從某個分布的隨機數(shù)，對應(yīng)第j 個分量.

2 非啟發(fā)式變異EP 算法的不足

定義2 假設(shè)P{x'i∈Mε}是EP 算法中的個體xi經(jīng)過式(1)和(2)變異后進入最優(yōu)鄰域Mε的概率.

由于Mε中的ε 可以是任意小，在連續(xù)優(yōu)化問題中，個體到達最優(yōu)鄰域相當于達到問題的最優(yōu)解.定義2 中的P{x'i∈Mε}相當于EP 算法基于該個體求得最優(yōu)解的概率.

從文獻［11-13］的分析可以看出，P{x'i∈Mε}是分析的關(guān)鍵，因為它可以決定算法的期望收斂時間.根據(jù)式(2)，有

式中:ψ 為隨機向量;v 為集合的元素向量;pF(y)是隨機變量的密度函數(shù)，在CEP 算法［3］中是Gauss 密度函數(shù)，在FEP 算法［4］中是Cauchy 密度函數(shù)，而在LEP［5］中是Lévy 密度函數(shù).當參數(shù)固定時，密度函數(shù)pF(y)是固定的，即不會隨著迭代時間t 變化.因此，式(3)主要是由M'ε所決定，而根據(jù)式(4)，M'ε主要由Mε和變異擾動σi所決定.Mε求解的目標問題由EP 算法所決定，問題和算法確定后Mε就固定了.根據(jù)前一段分析，∫M'εpF(y)dy 值主要由迭代中的σ、目標問題(Mε)和密度函數(shù)pF(y)所決定［18］.

因此，對于相同的問題和σ 初值，CEP、FEP 和LEP 算法的∫M'εpF(y)dy 由密度函數(shù)pF(y)所決定，3 種算法求解相同問題時會因為密度函數(shù)不同會出現(xiàn)性能差別.文獻［7］已說明CEP、FEP 和LEP 算法分別適合求解不同的函數(shù)優(yōu)化問題:CEP 算法比較適用于單峰優(yōu)化函數(shù)的求解，或者峰值分布較密的多峰函數(shù);FEP 算法適合求解多峰函數(shù)，特別是峰值分布較疏的多峰函數(shù)［19］;而LEP 算法在求解峰值分布非常稀疏的函數(shù)時有明顯優(yōu)勢.

為了進一步研究，需要再分析變異擾動向量σi，因為CEP、FEP 和LEP 算法都是采用式(1)和(2)更新σi，所以σ'i(j)以較大的概率在σ'i(j)=σi(j)exp{-1.96('+ )}和σ'i(j)=σi(j)exp{1.96·('+)}之間變動.考慮參數(shù)和 ' =即σ'i(j)在σi(j)基礎(chǔ)上作小范圍波動.因此，隨σ 變化而變化，而且σ 是迭代過程中唯一可能引起變化的因素.然而，σ 在迭代過程中的變化是完全隨機波動，并非啟發(fā)式地變化.

因此，σ 的設(shè)置和更新是演化規(guī)劃算法改進設(shè)計的關(guān)鍵點.原有EP 算法中σ 的變化與變量x 的狀態(tài)無關(guān)，所以無法有效地引導(dǎo)算法求解.本研究將重新設(shè)計變異步長向量σ，使得σ 可以根據(jù)x 動態(tài)地更新，使得:即使σ 初值令值較小時，迭代過程中σ 的動態(tài)更新仍可以令以較大概率增大，從而提高算法的性能.

3 啟發(fā)式變異EP 算法的設(shè)計與分析

3.1 啟發(fā)式變異算子

文中提出了一種啟發(fā)式變異的EP(HMEP)算法.HMEP 算法沿用EP 算法的框架(見第2 節(jié))，主要修改的內(nèi)容集中在σ 和x 的更新.

變異步長向量改為下式，每個個體(xi，σi)，執(zhí)行下面公式生成子代個體的變異步長σ'i:

r1和r2是{1，2，…，K}中的均勻隨機整數(shù)，滿足r1、r2和i 互不相同.式(6)的設(shè)計主要是以隨機抽取的兩個個體差異來更新變異步長.在生成σ'之后，按照式(6)產(chǎn)生新的變異個體.

其中，當t=0 時，i取(0，1］中的均勻隨機數(shù);當t ＞0 時，i以0.1 的概率取(0，1］中的均勻隨機數(shù)作更新，以0.9 的概率保持不變.對于i=1，2，…，K，j=1，2，…，n，α(j)是［0，1］之間的均勻隨機數(shù)，Ci為變異控制系數(shù)，當α(j)≤Ci時，個體在第j 維發(fā)生變異.O(i)則是{1，2，…，n}中的均勻隨機整數(shù)，為保證個體至少有一維發(fā)生變異.當α(j)＞Ci且j≠O(i)時，個體在第j 維不發(fā)生變異，即第j 維值保持原狀.Ci以0.1 的概率取(0，1］中的均勻隨機數(shù)作更新，以0.9 的概率保持不變.

式(6)與式(2)最大的不同是允許個體有機會在某些維數(shù)保持原狀，只是進行部分維數(shù)上的變異，使得優(yōu)秀的個體片段可以保留，這是HMEP 算法與CEP、FEP 和LEP 算法的一個根本區(qū)別.當然，式(6)也可能如式(2)一樣使個體在所有的維數(shù)上發(fā)生變異.為避免固定控制系數(shù)Ci影響變異效果，對于每個i 執(zhí)行式(6)進行更新時，都用較小的概率重新取值.

3.2 算法性能分析

HMEP 算法的其他處理過程與CEP、FEP 和LEP 算法一樣.從式(5)和式(6)可得，HMEP 算法雖然比3 種常用EP 算法增加了 i 和Ci更新步驟，但是卻省略了生成Gauss、Cauchy 或者Lévy 分布隨機數(shù)的生成步驟.因此，HMEP 算法并沒有比CEP、FEP 和LEP 算法明顯地增加計算量.

啟發(fā)式變異EP(HMEP)算法是針對CEP、FEP和LEP 算法不足而改進的EP 算法，第4 節(jié)用實驗結(jié)果說明了HMEP 的性能優(yōu)勢，本節(jié)將從理論上給出HMEP 算法的期望收斂時間分析.HMEP 采用如式(5)和(6)的變異算子，x'i(j)等價于在區(qū)間［li(j)，hi(j)］取服從均勻分布的隨機值.其中，li(j)=min(xi(j)，σi(j))，hi(j)=max(xi(j)，σi(j)).

當r1和r2確定時，x'i(j)服從均勻分布對應(yīng)的概率密度函數(shù):

其中，

因此，

其中，i=1，2，…，K 和U0.CEP、FEP 和LEP 算法中σ 的變化與變量x 的狀態(tài)無關(guān)，σ 在迭代過程中的變化是完全隨機波動，且非啟發(fā)式地變化，所以無法有效地引導(dǎo)算法求解.HMEP 算法設(shè)計了變異步長向量σ，使σ 可以根據(jù)x 動態(tài)地更新，使得:即使σ初值令值較小時，迭代過程中σ 的動態(tài)更新仍可以令以較大概率增大.因此，HMEP 算法可以適應(yīng)更多種類的優(yōu)化問題［2］，比CEP、FEP 和LEP 算法有更好的收斂速度和魯棒性.第4 節(jié)的實驗結(jié)果也證明了本節(jié)理論分析的結(jié)論.

4 實驗結(jié)果與分析

在實驗中，對HMEP、CEP、FEP、LEP 和ALEP算法設(shè)置相同的種群規(guī)模K=100，相同的最大迭代次數(shù).5 種算法的50 次獨立運行的均值和標準差見表1 和表2，測試問題見文獻［2］.

表1 中的結(jié)果表明，HMEP 算法比FEP 和CEP算法在大多數(shù)的測試問題上求解更優(yōu);HMEP 算法在多個單峰和多峰問題求得的平均最優(yōu)解明顯優(yōu)于FEP 和CEP 算法，而且HMEP 算法在標準差上也明顯小于另外兩種算法.

由表2 可知，對于單峰函數(shù)問題f1、f 3 和f5，HMEP 算法比LEP 和ALEP 算法更優(yōu).對于帶多個局部最優(yōu)的多峰函數(shù)問題，除了f 8 以外，HMEP 算法在f9—f13 問題求解上明顯優(yōu)于LEP 和ALEP 算法，且穩(wěn)定性更強.對帶少量局部最優(yōu)的多峰函數(shù)問題f14 和f16，3 種算法則旗鼓相當.ALEP 算法被證明是目前最優(yōu)的演化規(guī)劃算法之一，HMEP 算法從整體上比ALEP 算法更優(yōu)更穩(wěn)定，可以認為是一種改進的EP 算法.

筆者還將提出的HMEP 算法與最近學(xué)者們提出的IMEP 算法［20］和LSEP 算法［21］進行了總體性能對比.結(jié)果見表3，HMEP 算法在16 個標準測試函數(shù)問題的求解上有著絕對優(yōu)勢，改進效果非常顯著.

表1 HMEP、CEP 和FEP 算法求解性能的總體對比Table 1 Performance comparison among HMEP，CEP and FEP algorithms

表2 HMEP、LEP 和ALEP 三算法求解性能的總體對比Table 2 Performance comparison among HMEP，LEP and ALEP algorithms

表3 HMEP、IMEP 和LSEP 算法求解性能的總體對比Table 3 Performance comparison among HMEP，IMEP and LSEP algorithms

5 結(jié)語

文中基于演化規(guī)劃算法計算時間分析的一般理論，分析了CEP、FEP 和LEP 等非啟發(fā)式變異算法的不足，設(shè)計了一種基于個體差異的進化規(guī)劃算法HMEP，從實驗和理論上都證明了HMEP 算法比CEP、FEP、LEP、IMEP 和LSEP 等算法有更高的收斂速度和更好的魯棒性.未來的工作將分析差異進化算法、免疫算法和粒子群算法等其他連續(xù)優(yōu)化算法的改進，并且對算法的參數(shù)選擇作進一步研究.

［1］Yao X，Xu Y.Recent advances in evolutionary computation［J］.Journal of Computer Science and Technology，2006，21(1):1-18.

［2］Yao X，Liu Y，Lin G.Evolutionary programming made faster［J］.IEEE Transactions on Evolutionary Computation，1999，3(2):82-102.

［3］Lee C Y，Yao X.Evolutionary programming using mutations based on the Lévy probability distribution［J］.IEEE Transactions on Evolutionary Computation，2004，8(1):1-13.

［4］劉峰，劉貴忠，張茁生.進化規(guī)劃的Markov 過程分析及其收斂性［J］.電子學(xué)報，1998，26(8):76-79.Liu Feng，Liu Gui-Zhong，Zhang Zhuo-sheng.Markovian process analyses and convergences of evolutionary programming［J］.Acta Electronica Sinica，1998，26(8):76-79.

［5］Rudolph G.Self-adaptation and global convergence:A counter-example［C］∥Proceedings of the Congress on Evolutionary Computation.Piscataway:IEEE，1999:646-651.

［6］Fogel D B.An introduction to simulated evolutionary optimization ［J］.IEEE Transactions on Neural Networks，1994，5(1):3-14.

［7］高永超，李歧強.退火進化規(guī)劃算法及其收斂性［J］.系統(tǒng)仿真學(xué)報，2006，18(3):577-580.Gao Yong-chao，Li Qi-qiang.Annealing evolutionary programming algorithm and its convergence ［J］.Journal of System Simulation，2006，18(3):577-580.

［8］王向軍，嵇斗，張民.一種多群競爭進化規(guī)劃算法［J］.電子學(xué)報，2004，32(11):1824-1828.Wang Xiang-jun，Ji Dou，Zhang Min.A multi-subgroup competition evolutionary programming algorithm［J］.Acta Electronica Sinica，2004，32(11):1824-1828.

［9］王向軍，向東，蔣濤，等.一種雙種群進化規(guī)劃算法［J］.計算機學(xué)報，2006，29(5):835-840.Wang Xiang-jun，Xiang Dong，Jiang Tao，et al.A novel bigroup evolutionary programming［J］.Chinese Journal of Computers，2006，29(5):835-840.

［10］杜海峰，公茂果，劉若辰，等.自適應(yīng)混沌克隆進化規(guī)劃算法［J］.中國科學(xué)E 輯信息科學(xué)，2005，35(8):817-829.Du Hai-feng，Gong Mao-guo，Liu Ruo-chen，et al.Adaptive chaotic clone evolutionary programming algorithm［J］.Sciences in Chinese Ser.E Information Sciences，2005，35(8):817-829.

［11］黃翰，郝志峰，秦勇，進化規(guī)劃算法的時間復(fù)雜性分析［J］.計算機研究與發(fā)展，2008，45(11):1850-1857.Huang Han，Hao Zhi-feng，Qin Yong.Time complexity of evolutionary programming［J］.Journal of Computer Research and Development，2008，45(11):1850-1857.

［12］Hao Z F，Huang H，Li H Z，et al.A relation-based model for convergence analysis of evolutionary algorithm［C］∥Swarm，Evolutionary，and Memetic Computing.Berlin，Heidelberg:Springer，2010:190-197.

［13］蔡昭權(quán)，羅偉，張宇山，等.Lévy 變異進化規(guī)劃算法的計算時間分析［J］.計算機科學(xué)，2011，38(9):197-200.Cai Zhao-quan，Luo Wei，Zhang Yu-shan，et al.Runningtime analysis of evolutionary programming based on Lévy mutation［J］.Computer Science，2011，38(9):197-200.

［14］黃翰，林智勇，郝志峰，等.基于關(guān)系模型的進化算法收斂性分析與對比［J］.計算機學(xué)報，2011，34(5):801-811.Huang Han，Lin Zhi-yong，Hao Zhi-feng，et al.Convergence analysis and comparison of evolutionary algorithms based on relation model ［J］.Chinese Journal of Computers，2011，34(5):801-811.

［15］張宇山，郝志峰，黃翰.二元進化策略的收斂性分析［J］.計算機科學(xué)，2011，38(7):231-234.Zhang Yu-shan，Hao Zhi-feng，Huang Han.Convergence analysis of two-membered evolution strategy［J］.Computer Science，2011，38(7):231-234.

［16］Lu T C，Juang J C.A region-based quantum evolutionary algorithm(RQEA)for global numerical optimization［J］.Journal of Computational and Applied Mathematics，2013，239:1-11.

［17］Zhao L，Wang L，Cui D W.Hoeffding bound based evolutionary algorithm for symbolic regression［J］.Engineering Applications of Artificial Intelligence，2012，25(5):945-957.

［18］郝志峰，蔡瑞初.并行多任務(wù)環(huán)境下Agent 聯(lián)盟的快速生成算法［J］.華南理工大學(xué)學(xué)報:自然科學(xué)版，2008，36(9):11-14，30.Hao Zhi-feng，Cai Rui-chu.Fast generation algorithm of Agent coalition in parallel multi-task environment［J］.Journal of South China University of Technology:Natural Science Edition，2008，36(9):11-14，30.

［19］李學(xué)強，郝志峰，黃翰.基于分方向選擇搜索的多目標進化算法［J］.華南理工大學(xué)學(xué)報:自然科學(xué)版，2011，39(2):130-135.Li Xue-qiang，Hao Zhi-feng，Huang Han.Multi-objective evolutionary algorithm based on direction selection search［J］.Journal of South China University of Technology:Natural Science Edition，2011，39(2):130-135.

［20］Shen L，He J.Evolutionary programming using a mixed strategy with incomplete information.［C］∥2010 UK Workshop on Computational Intelligence(UKCI).Colchester:IEEE，2010:1-6.

［21］Shen L，He J.A mixed strategy for evolutionary programming based on local fitness landscape［C］∥Proceedings of 2010 IEEE World Congress on Computational Intelligence.Barcelona:IEEE，2010:350-357.