鄔 峰，黃麗亞

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

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

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

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

1 遺傳算法概述

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

1.1 基本遺傳算法

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

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

SGA具體步驟描述如下：

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

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

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

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

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

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

SGA流程圖如圖1所示。

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

1.2 自適應遺傳算法

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

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

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

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

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

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

2 模擬退火算法概述

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

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

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

SAA具體步驟描述如下：

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

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

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

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

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

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

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

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

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

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

3 自適應遺傳模擬退火算法

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

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

ASAGA算法步驟可描述如下：

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

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

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

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

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

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

自適應SAGA基本流程如圖2所示。

4 實驗仿真

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

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

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

SGA仿真結果如圖3所示。

ASAGA 相 應 參 數(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仿真結果如圖4所示。

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

表1 SGA和ASAGA運算結果比較

本文在分析了遺傳算法的優(yōu)缺點的基礎上，提出了一種融入了模擬退火算法的混合遺傳算法——自適應模擬退火遺傳算法。將模擬退火算法和遺傳算法有效地結合，同時改進自適應遺傳算子，實現(xiàn)了兩者的優(yōu)勢互補。仿真結果表明，改進后的自適應模擬退火遺傳算法可以顯著提高遺傳算法的尋優(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]陳國良，王煦法.遺傳算法及其應用[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]王小平，曹立明.遺傳算法—理論、應用與軟件實現(xiàn)[M].西安：西安交通大學出版社，2002.

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

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

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