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

鄔 峰，黃麗亞

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

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

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

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

1 遺傳算法概述

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

1.1 基本遺傳算法

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

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

SGA具體步驟描述如下：

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

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

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

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

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

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

SGA流程圖如圖1所示。

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

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

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

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

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

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

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

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

2 模擬退火算法概述

模擬退火算法(SAA)是根據(jù)液態(tài)或固態(tài)材料中粒子的統(tǒng)計(jì)力學(xué)與復(fù)雜組合最優(yōu)化問(wèn)題的求解過(guò)程的相似之處而提出來(lái)的。統(tǒng)計(jì)力學(xué)論述了材料中相互作用的粒子的特性:不同的材料中粒子結(jié)構(gòu)對(duì)應(yīng)于不同的能量水平。如果用粒子結(jié)構(gòu)或其相應(yīng)能量來(lái)定義材料的狀態(tài)，一個(gè)簡(jiǎn)單的數(shù)學(xué)模型可描述材料在溫度T下從具有能量E(i)的狀態(tài)i進(jìn)入具有能量E(j)的狀態(tài)j的機(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為材料溫度。以上過(guò)程稱為波爾茲曼接收策略。

SAA具體步驟描述如下：

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

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

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

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

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

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

(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)點(diǎn)，計(jì)算結(jié)束。

以上步驟稱為Metropolis過(guò)程?？刂茰囟认陆档暮瘮?shù)的選取是SAA難以處理的問(wèn)題。實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問(wèn)題，常采用如下所示的降溫方式:T(k+1)=λ×T(k)，式中 λ 為 正、略小于1.00的常數(shù)，k為降溫的次數(shù)[5]。

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

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

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

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

ASAGA算法步驟可描述如下：

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

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

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

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

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

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

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

4 實(shí)驗(yàn)仿真

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

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

SGA采用的遺傳操作及相應(yīng)參數(shù)為比例選擇、單點(diǎn)交叉(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所示。

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

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

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

[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]陳國(guó)良，王煦法.遺傳算法及其應(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)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

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

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

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