自適應(yīng)模擬退火遺傳算法的改進與應(yīng)用

鄔 峰，黃麗亞

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

遺傳算法GA(Genetic Algorithm)是一種隨機搜索算法，1975年由 Holland[1]提出并發(fā)展起來，它具有隱含并行性和全局搜索性兩大特點。其核心內(nèi)容是參數(shù)編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)計、遺傳算子設(shè)計、控制參數(shù)設(shè)定。GA以一個種群中的所有個體為對象，利用隨機化技術(shù)指導(dǎo)，對一個被編碼的參數(shù)空間進行高效搜索。GA具有很強的計算能力，但是求解過程卻很簡單，因此成為現(xiàn)代有關(guān)智能計算中的主要算法之一。

模擬退火算法SAA(Simulated AnnealingAlgorithm)是1982年由Kirkpatrick[2]將固體退火思想引入組合優(yōu)化領(lǐng)域，提出了一種求解大規(guī)模組合優(yōu)化問題，特別是NP完全組合優(yōu)化的有效近似算法。算法的核心在于模仿熱力學(xué)中液體的凍結(jié)與結(jié)晶或金屬熔液的冷卻與退火過程。在搜索最優(yōu)解的過程中，SAA除了可以接受最優(yōu)解外，還有一個隨機接受準(zhǔn)則(Metropolis準(zhǔn)則)，可以有限度地接受惡化解，并且接受惡化解的概率慢慢趨向于零，使得算法有可能從局部最優(yōu)中跳出，盡可能找到全局最優(yōu)解，保證了算法的收斂。

本文在分析這兩種算法的長處與不足的基礎(chǔ)上，將SAA引入到GA中，同時結(jié)合自適應(yīng)調(diào)整遺傳算法控制參數(shù)的思想對交叉變異算子進行自適應(yīng)處理，提出了一種改進的自適應(yīng)模擬退火遺傳算法ASAGA(Adpative Simulated Annealing Genetic Algorithm)。仿真實驗結(jié)果表明，該算法不僅可以提高解的精度，同時亦可獲得較快的收斂速度。

1 遺傳算法概述

遺傳算法(GA)模擬了自然選擇和遺傳中發(fā)生的復(fù)制、交叉、變異等現(xiàn)象，從任一初始種群(Population)出發(fā)，通過隨機選擇、交叉、變異操作，產(chǎn)生一群更適應(yīng)環(huán)境的個體，使群體進化到搜索空間中越來越好的區(qū)域，這樣一代一代地不斷繁衍進化，經(jīng)過若干代之后，算法收斂于最好的個體(Individual)，很可能就是問題的最優(yōu)解或次優(yōu)解。

1.1 基本遺傳算法

基本遺傳算法SGA(Simple Genetic Algorithm)可定義為一個8元組：

其中，C為個體的編碼方法；E為個體的適應(yīng)度評價函數(shù)；P0為初始種群；M為群體大小；Ps為選擇算子；Pc為交叉算子；Pm為變異算子；T為算法終止條件[3]。

SGA具體步驟描述如下：

(1)隨機產(chǎn)生初始種群，個體數(shù)目一定，每個個體表示為染色體基因編碼；

(2)計算個體適應(yīng)度，判斷是否符合優(yōu)化準(zhǔn)則。若符合，輸出最佳個體或最佳解，并結(jié)束計算；否則轉(zhuǎn)向第(3)步；

(3)采取比例選擇法選擇個體：根據(jù)適應(yīng)度選擇再生個體，適應(yīng)度高的個體被選中概率高，適應(yīng)度低的個體可能被淘汰；

(4)按照一定的交叉概率和交叉方法，生成新的個體；

(5)按照一定的變異概率和變異方法，生成新的個體；

(6)由交叉和變異產(chǎn)生新一代的種群，返回第(2)步。

SGA流程圖如圖1所示。

SGA一般在開始隨機產(chǎn)生初始群體，然后不斷地改進個體，以得到越來越好的結(jié)果。但由于收斂速度和尋找最優(yōu)解往往是一對矛盾，SGA常表現(xiàn)為收斂速度慢、容易早熟、陷入局部最優(yōu)解。

1.2 自適應(yīng)遺傳算法

利用遺傳算法求解問題的關(guān)鍵是對問題的解進行編碼，構(gòu)造出適應(yīng)度函數(shù)，并選取遺傳算法參數(shù)：群體規(guī)模M、交叉概率 Pc以及變異概率Pm。其中，Pc和 Pm在遺傳算法中的重要性已經(jīng)得到研究者的公認(rèn)。GA在搜索全局最優(yōu)解時必須具備確定搜索最優(yōu)解區(qū)域并收斂到最優(yōu)解的能力及在搜索全局最優(yōu)解時，開辟新的解空間的能力，這些特點是由Pc和Pm控制的。Pc取值越大，新個體產(chǎn)生的速度就越快，即開辟新的解空間的能力越強。然而Pc過大時遺傳模式被破壞的可能性也越大，使得有高適應(yīng)度的個體結(jié)構(gòu)很快就會被破壞；但若Pc過小，會使搜索過程緩慢，以至停滯不前。對于變異概率Pm，如果取值過小，就不易產(chǎn)生新的個體結(jié)構(gòu)；若 Pm取值過大，則GA就變成了純粹的隨機搜索算法。

針對GA所存在的問題，Srinivas[4]提出了自適應(yīng)遺傳算法，其思想是當(dāng)種群適應(yīng)度比較集中時，使交叉概率Pc和變異概率Pm增大；當(dāng)種群適應(yīng)度比較分散時，使Pc和Pm減小。Pc和Pm按如下公式進行自適應(yīng)調(diào)整：

式中：favg為種群的平均適應(yīng)度值，fmax為種群的最大適應(yīng)度值，f′為交叉雙方適應(yīng)度較大者的適應(yīng)度值，f為要變異個體的適應(yīng)度值，0＜k1，k2，k3，k4≤1。

由上式可以看出，當(dāng)適應(yīng)度值越接近最大適應(yīng)度值時，交叉率和變異率就越小；當(dāng)?shù)扔谧畲筮m應(yīng)度值時，交叉率和變異率為零。這種調(diào)整方法在群體進化后期比較合適，但對于進化初期不利。因為進化初期較優(yōu)個體幾乎處于一種不發(fā)生變化的狀態(tài)，而此時優(yōu)良個體未必是全局最優(yōu)解，這容易使進化走向局部最優(yōu)解的可能性增加。

為克服這些問題，保存群體中性能較好的個體，本文對參考文獻[4]中自適應(yīng)算子加以改進，新的交叉和變異概率計算表達(dá)式如下：

式 中 ：Pc1＞Pc2＞Pc3，Pm1＞Pm2＞Pm3， 它 們 的 取 值 在(0，1)之 間并在優(yōu)化中調(diào)整。

2 模擬退火算法概述

模擬退火算法(SAA)是根據(jù)液態(tài)或固態(tài)材料中粒子的統(tǒng)計力學(xué)與復(fù)雜組合最優(yōu)化問題的求解過程的相似之處而提出來的。統(tǒng)計力學(xué)論述了材料中相互作用的粒子的特性:不同的材料中粒子結(jié)構(gòu)對應(yīng)于不同的能量水平。如果用粒子結(jié)構(gòu)或其相應(yīng)能量來定義材料的狀態(tài)，一個簡單的數(shù)學(xué)模型可描述材料在溫度T下從具有能量E(i)的狀態(tài)i進入具有能量E(j)的狀態(tài)j的機制：

若 E(i)≥E(j)，狀態(tài)轉(zhuǎn)換被接受；

若 E(i)＜E(j)，則狀態(tài)轉(zhuǎn)換以概率 p=exp{(E(i)-E(j))/KT}被接受，其中K為物理學(xué)中的波爾茲曼(Boltzmann)常數(shù)，T為材料溫度。以上過程稱為波爾茲曼接收策略。

SAA具體步驟描述如下：

(1)隨機產(chǎn)生一個初始最優(yōu)點，以它作為當(dāng)前最優(yōu)點，并計算目標(biāo)函數(shù)值；

(2)設(shè)置初始溫度：θ←T0；

(3)設(shè)置循環(huán)計數(shù)器初值：k←1；

(4)對當(dāng)前最優(yōu)點作隨機變動，產(chǎn)生一個新的最優(yōu)點，計算新的目標(biāo)函數(shù)值，并計算目標(biāo)函數(shù)值的增量Δ；

(5)如果 Δ＜0，則接受該新產(chǎn)生的最優(yōu)點作為當(dāng)前最優(yōu)點；

如果 Δ≥0，則以概率 p=exp(-Δ/θ)接受該新產(chǎn)生的最優(yōu)點為當(dāng)前最優(yōu)點；

(6)如果 k＜終止步數(shù)，則 k←k+1，轉(zhuǎn)向第(4)步；

(7)如果未到達(dá)冷卻狀態(tài)，則：θ←T(k)，轉(zhuǎn)向第(3)步；如果已經(jīng)到達(dá)冷卻狀態(tài)，則輸出當(dāng)前最優(yōu)點，計算結(jié)束。

以上步驟稱為Metropolis過程。控制溫度下降的函數(shù)的選取是SAA難以處理的問題。實際應(yīng)用中，由于必須考慮計算復(fù)雜度的切實可行性等問題，常采用如下所示的降溫方式:T(k+1)=λ×T(k)，式中 λ 為 正、略小于1.00的常數(shù)，k為降溫的次數(shù)[5]。

按照一定的退火方案逐步降低溫度，重復(fù)Metropolis過程，就構(gòu)成了SA算法。當(dāng)系統(tǒng)溫度足夠低時，可認(rèn)為達(dá)到了全局最優(yōu)狀態(tài)。使用Meteopolis準(zhǔn)則的優(yōu)點是：當(dāng)新解更優(yōu)時，完全接受新解為新的當(dāng)前解；而當(dāng)新解為惡化解時，以概率p接受惡化解為新當(dāng)前解。這就使得SAA能夠保證局部尋優(yōu)的精度，且還能夠避免陷入局部最優(yōu)[6]。

3 自適應(yīng)遺傳模擬退火算法

GA的局部搜索能力較差，但把握搜索過程總體的能力較強；而SAA具有較強的局部搜索能力，并能使搜索過程避免陷入局部最優(yōu)解，但SAA對整個搜索空間的狀況了解不多，不便于使搜索過程進入最有希望的搜索區(qū)域，從而使得SAA的運算效率不高[7]。但如果將上述兩種算法相結(jié)合構(gòu)成一種優(yōu)化算法，則可互相取長補短，形成性能優(yōu)良的全局搜索算法。在上述分析的基礎(chǔ)上，本文提出了自適應(yīng)模擬退火遺傳算法(ASAGA)，不但使群體中的最優(yōu)解得到了保留，同時避免了算法的早熟收斂問題，可以達(dá)到很好的全局尋優(yōu)效果。

ASAGA設(shè)計的基本思想是：將SAA引入到GA中，構(gòu)成一種混合算法，先是從一組隨機產(chǎn)生的初始種群開始全局最優(yōu)解的搜索，通過選擇、自適應(yīng)交叉及變異等遺傳操作產(chǎn)生新一代種群，并對交叉和變異后產(chǎn)生的新個體實施波爾茲曼接收策略，然后再獨立地對所產(chǎn)生出的個體進行精英選擇操作[8]，以其結(jié)果作為下一代種群中的個體。這個運算過程反復(fù)迭代地進行，直到滿足終止條件為止。在改進后的算法中，GA側(cè)重于全局搜索，SAA側(cè)重于局部搜索，兩者的結(jié)合將使算法的效率大大提高。

ASAGA算法步驟可描述如下：

(1)設(shè)置初始參數(shù)，包括種群規(guī)模M，最大迭代次數(shù)Tmax，交叉概率 Pc和變異概率 Pm，以及退火初始溫度 T0，溫度冷卻參數(shù)λ；

(2)初始化種群，按隨機方法產(chǎn)生初始群體中的每個個體，得到初始種群；

(3)計算種群中個體的適應(yīng)度值，評價是否滿足終止條件。若滿足，則輸出最優(yōu)解，終止算法；否則進入步驟(4)；

(4)采取比例選擇方法選擇個體，對被選中染色體進行交叉操作，其中的交叉概率通過式(3)計算得出。計算交叉產(chǎn)生的子個體所對應(yīng)適應(yīng)函數(shù)值 f(x′)，僅在min{1，exp((f(x)-f(x′))/Tk)}＞random 條件下接收新解，其中f(x)為父代個體適應(yīng)度值，Tk為當(dāng)前溫度，random是(0，1)之間的隨機數(shù)；

(5)對交叉后的染色體進行變異操作，其中變異概率通過式(4)計算得出；同理，按步驟(4)中的方法決定是否接收變異后的解；

(6)進行世代和退火降溫的迭代，溫度變化按照公式：Tk+1=λ×Tk，k←k+1，λ∈(0，1)，同時進行精英選擇：把進化過程中出現(xiàn)的最優(yōu)個體直接復(fù)制到下一代中，替換下一代中適應(yīng)度差的個體，并令被復(fù)制個體不參加任何遺傳操作。計算后，轉(zhuǎn)向步驟(3)。

自適應(yīng)SAGA基本流程如圖2所示。

4 實驗仿真

為測試本文提出的ASAGA的全局尋優(yōu)性能，選取一個典型的多峰值函數(shù)作為測試函數(shù)，用MATLAB語言進行仿真，尋找其全局最優(yōu)解，并與SGA求解此函數(shù)全局最優(yōu)解的結(jié)果相比較。設(shè)：

該函數(shù)在 x∈(0，9)區(qū)間中的最大值為 24.855 4，全局最優(yōu)點在x=7.856 9左右。

SGA采用的遺傳操作及相應(yīng)參數(shù)為比例選擇、單點交叉(Pc=0.85)及基本位變異(Pm=0.05)，種群規(guī)模 M=20，最大迭代次數(shù)Tmax=40。

SGA仿真結(jié)果如圖3所示。

ASAGA 相 應(yīng) 參 數(shù) 設(shè) 置 如 下 ：Pc1=0.4，Pc2=0.3，Pc3=0.2；Pm1=0.2，Pm2=0.1，Pm3=0.05；T0=100，λ=0.95；種群規(guī)模M=20，最大迭代次數(shù) Tmax=40。

ASAGA仿真結(jié)果如圖4所示。

通過對比圖3、圖4的仿真結(jié)果，可以看出：由于SGA的交叉變異概率在進化過程中沒有變化，導(dǎo)致不同個體的交叉變異操作是相同的，算法在第12代就陷入局部最優(yōu)點，直至最大迭代數(shù)也沒有跳出來。而ASAGA在全局尋優(yōu)能力、收斂概率和收斂速度等方面明顯優(yōu)于SGA。ASAGA確定的自適應(yīng)交叉、變異概率具有很強的指導(dǎo)搜索方向的能力，算法在第7代就迅速尋到了全局最優(yōu)點，達(dá)到了既快又好的效果。表1給出了兩種算法運算結(jié)果中關(guān)鍵參數(shù)的對比。

表1 SGA和ASAGA運算結(jié)果比較

本文在分析了遺傳算法的優(yōu)缺點的基礎(chǔ)上，提出了一種融入了模擬退火算法的混合遺傳算法——自適應(yīng)模擬退火遺傳算法。將模擬退火算法和遺傳算法有效地結(jié)合，同時改進自適應(yīng)遺傳算子，實現(xiàn)了兩者的優(yōu)勢互補。仿真結(jié)果表明，改進后的自適應(yīng)模擬退火遺傳算法可以顯著提高遺傳算法的尋優(yōu)性能和運行效率，較為有效地克服了基本遺傳算法易早熟和容易陷入局部最優(yōu)解的缺點。

[1]HOLLANG J H.Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan press，1975.

[2]KIRKPATRICK S， GELATT C D， VECCHIM P.Optimization by simulated annealing[J].Science， 1983，220:671-680.

[3]陳國良，王煦法.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.

[4]SRINIVAS M，PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Trans System， Man and Cybernetics， 1994，24(4):656-667.

[5]王小平，曹立明.遺傳算法—理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

[6]康立山，謝云，尤矢勇，等.非數(shù)值并行算法(第一冊)—模擬退火算法[M].北京：科學(xué)出版社，1995.

[7]王凌，鄭大鐘.一種GASA混合優(yōu)化策略[J].控制理論與應(yīng)用，2001，18(4):552-554.

[8]李敏強，寇紀(jì)淞，林丹，等.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.