一種改進(jìn)的遺傳退火算法以及收斂性分析*

高發(fā)玲

(青島理工大學(xué)琴島學(xué)院，山東 青島 266100)

一種改進(jìn)的遺傳退火算法以及收斂性分析*

高發(fā)玲

(青島理工大學(xué)琴島學(xué)院，山東 青島 266100)

針對一種約束條件既有0－1變量又有整數(shù)變量的非線性混合整數(shù)規(guī)劃模型，給出一種改進(jìn)的遺傳退火算法求解，并建立對應(yīng)的Markov鏈且理論證明其收斂性．

遺傳退火;Markov鏈;遍歷;收斂性

0 引 言

針對一種約束條件既有0－1變量又有整數(shù)變量的非線性混合整數(shù)規(guī)劃模型，數(shù)學(xué)模型

提出一種改進(jìn)的遺傳退火算法并對其算法對應(yīng)Markov鏈進(jìn)行收斂性分析．

1 算法設(shè)計

改進(jìn)的遺傳退火算法分為5步:編碼方案的設(shè)計、解除約束與適應(yīng)度函數(shù)的選定、交叉操作設(shè)計、變異操作設(shè)計以及終止條件的確定．

1．1 編碼方案的設(shè)計

對于0－1決策變量的Y，采用二進(jìn)制編碼;對于整數(shù)變量X，采用浮點編碼．

1．2 解除約束與適應(yīng)函數(shù)的選定

(1)約束優(yōu)化問題處理．采用懲罰策略技術(shù)將有約束的優(yōu)化模型轉(zhuǎn)化為無約束優(yōu)化問題，

此時采用的可變懲罰因子a=tk，其中tk為第k代退火溫度．

(2)適應(yīng)度函數(shù)的選定．

1．3 交叉操作設(shè)計

由于編碼方法采用的是上述混合并行方案，因此在交叉操作中也采用相應(yīng)的方式，對0－1決策變量的Y進(jìn)行單點交叉，對整數(shù)變量X進(jìn)行混合交叉．

1．4 變異操作設(shè)計

對模型中的兩種決策變量采用不同的變異方式，對0－1決策變量的Y采用基本位變異，對整數(shù)變量X采用均勻變異．

1．5 終止條件的確定

計算在每一溫度下每一代群體染色體的最大適應(yīng)值和最小適應(yīng)值，當(dāng)最大適應(yīng)值與最小適應(yīng)值之間的差小于ε(ε為參數(shù))時，停止此溫度下的種群迭代;設(shè)退火溫度為tk，若滿足tk≤η(η為很小的參數(shù))時(計算迭代到規(guī)定的退火溫度)，則停止計算．

2 算法收斂性分析

2．1 算法對應(yīng)Markov鏈的建立

離散組合優(yōu)化問題minf(bi)，其中bi為所有變量對應(yīng)的一個狀態(tài)，設(shè)狀態(tài)集

設(shè)變量的個數(shù)為k(其中有l(wèi)個0－1變量;有k－l個整數(shù)變量)，稱為一個個體或染色體，這里的為整數(shù)．

引理1［2］若C和M分別是以交叉概率Pc∈[0，1]進(jìn)行交叉和以變異概率Pm∈(0，1)進(jìn)行變異對應(yīng)的一步轉(zhuǎn)移概率矩陣，則C和M均為隨機(jī)陣．

定義2 若種群B(i)和B(j)中僅有某一個個體不同，設(shè)bi∈B(i)≠bj∈B(j)且滿足bj∈N(bi)，則稱種群B(i)屬于種群B(j)的鄰域N(B(j))．

定義3 SA狀態(tài)產(chǎn)生函數(shù)使種群B(i)轉(zhuǎn)移到B(j)的一步轉(zhuǎn)移概率為

其中

定義4 對種群中個體作模擬退火操作所引起的種群的一步轉(zhuǎn)移概率:

則在溫度T下對所有個體均作模擬退火操作得到的種群轉(zhuǎn)移概率為

此時A(T)陣是隨機(jī)陣．

因此，此種改進(jìn)的遺傳退火算法在每一溫度下的狀態(tài)轉(zhuǎn)移矩陣為

從而得到所建立的遺傳退火算法對應(yīng)的Markov鏈可表示如下:

2．2 收斂性分析

定義5［2］給定隨機(jī)陣，其遍歷系數(shù)定義為

定義6 給定圖G的中心Ic，若Q中任意節(jié)點到達(dá)Ic最多經(jīng)過步，則稱r為圖G的半徑．其中d(i，j)為種群B(i)到達(dá)B(j)的最短路徑

引理2 若算法對應(yīng)的有限非齊次Markov鏈在每一溫度Ti下存在平穩(wěn)分布，則在每一溫度Ti下狀態(tài)轉(zhuǎn)移矩陣P(Ti)存在特征值為1的左特征向量．其中

證明

(1)若在每一溫度Ti下Markov鏈存在平穩(wěn)分布π(Ti)，則由平穩(wěn)分布定義知

(2)由引理1及式(7)知算法中每一溫度Ti下的轉(zhuǎn)移矩陣P(Ti)均是隨機(jī)矩陣，必得它的平穩(wěn)分布π(Ti)的每一分量均為正數(shù)，從而知等價于，再由范數(shù)定義［3］知

由(1)、(2)可得證引理2成立．

證明 由定理2知Markov鏈強(qiáng)遍歷的充分必要條件是Markov鏈弱遍歷且在每一溫度下狀態(tài)轉(zhuǎn)移矩陣存在特征值為1的左特征向量且

所以分為3步來證明定理:第一步，證明Markov鏈的弱遍歷性;第二步，證明每一溫度下狀態(tài)轉(zhuǎn)移矩陣存在特征值為1的左特征向量;第三步，證明

第一步:證明Markov鏈的弱遍歷性．

當(dāng)B(i)∈(Q－Qm)時，若B(j)∈N(B(i))，則

由式(11)知當(dāng) B(i)∈ (Q －Qm)時，f(B(i)) ＜ f(B(j))，從而此時的 gB(i)B(j)是隨著 h的增大而增大，而是隨著h的增大而減小，進(jìn)而得aB(i)B(j)(Th)隨h的增大而減小;若且 B(j)≠ B(i)，則從而得當(dāng) B(i)∈ (Q － Qm) 時，隨h的增大而增大;即存在整數(shù)k0，k0＜∞，對所有的B(i)∈(Q－Qm)，都有

所以，?B(i)∈Q，h≥k0r

C，M，A(T)均為隨機(jī)陣，得每一溫度下的狀態(tài)轉(zhuǎn)移陣P(T)=CMA(T)也是隨機(jī)陣，且τ(P)≤τ(A)，從而

即

第二步:證明每一溫度下狀態(tài)轉(zhuǎn)移矩陣存在特征值為1的左特征向量由引理2知只要有限非齊次Markov鏈在每一溫度Ti下存在平穩(wěn)分布，即平穩(wěn)分布就是所要找的π(Ti)，所以問題就轉(zhuǎn)變?yōu)槠椒€(wěn)分布的證明，而不可約非周期Markov鏈存在平穩(wěn)分布［4］，下面分為兩步來分別證明Markov鏈不可約非周期性．現(xiàn)證明Markov鏈的不可約性及非周期性．

(1)由設(shè)計的算法中的交叉和變異方式知?B(i)，B(j)∈Q，cB(i)B(j)，mB(i)B(j)均大于0，由式(4)和(6)知?B(i)，B(j)∈Q，存在z≥1使得B(i)，B(k)，B(k+1)B(z)，B(j)∈Q，滿足:

所以當(dāng)溫度T＞0給定時，?B(i)，B(j)∈Q，算法對應(yīng)的有限狀態(tài)的非齊Markov鏈有

因此，B(i)?B(j)，進(jìn)而由狀態(tài)B(i)和B(j)的任意性知B(i)?B(j)．從而，由不可約的充分條件可得到算法對應(yīng)的Markov鏈?zhǔn)遣豢杉s的．

(2)由式(4)知?B(j)≠B(i)∈Q，且B(j)∈N(B(i))，使得

而且又滿足

由式(6)得

則狀態(tài)?B(i)∈Q到自身的轉(zhuǎn)移概率

由(1)(2)知算法對應(yīng)的Markov鏈存在平穩(wěn)分布，進(jìn)而由引理2得出在每一溫度下狀態(tài)轉(zhuǎn)移矩陣存在特征值為1的左特征向量

由式(5)及第一步證明過程知當(dāng)j∈Q－Qm且k∈N(j)時，aj，k(Th)隨著的增大而減小，所以當(dāng)j∈Q－Qm且k∈N(j)時，存在N∈Z+，使的n＞N時有

所以，取n0=max{M，N}，由式(26)、(27)、(28)得，當(dāng)n＞n0時，

成立．又由定理中的假設(shè)知存在n1，使得n≥n1時，滿足

而由范數(shù)定義［3］知

取n'=max {n0，n1}，由式(29)、(30)、(31)得，當(dāng)n≥n'時，

成立．因此，由第一、二和三步的證明以及文獻(xiàn)定理［2］可證得此定理成立．

3 結(jié) 論

對于有約束非線性混合整數(shù)規(guī)劃方程，提出了一種改進(jìn)的遺傳退火算法求解方法．通過建立算法對應(yīng)的Markov鏈并對其收斂性給出理論證明．

［1］陳斌，王曉．基于遺傳算法的可再用逆向物流網(wǎng)絡(luò)規(guī)劃研究［D］．上海海事大學(xué)，2006

［2］王凌，鄭大鐘．一類GASA混合策略及其收斂研究［J］．控制與決策，1998，13(6):669-672

［3］龔光魯，錢敏平．應(yīng)用隨機(jī)過程教程及算法和智能計算中的隨機(jī)模型［M］．北京:清華大學(xué)出版社，2004

［4］吳曉敏．隨機(jī)變量中馬氏鏈的常返與強(qiáng)常返［J］．重慶工商大學(xué)學(xué)報:自然科學(xué)版，2011，28(4)343-346

［5］龔光魯，錢敏平．應(yīng)用隨機(jī)過程教程及算法和智能計算中的隨機(jī)模型［M］．北京:清華大學(xué)出版社，2004

An Improved Genetic Annealing Algorithm and Its Convergence Analysis

GAO Fa-ling
(Qindao College，Qingdao Institute of Technology，Shandong Qingdao 266100，China)

Under the constraint condition of nonlinear mixed integer programming model with 0-1 variable and integer variable，the solution to an improved genetic annealing algorithm is given，the corresponding Markov Chain is set up and its convergence is theoretically proved．

genetic annealing;Markov chain;traversal;convergence

O221．2

A

1672－058X(2015)02－0049－05

10．16055/j．issn．1672－058X．2015．0002．010

責(zé)任編輯:田 靜

2014－06－15;

2014－09－10．

高發(fā)玲(1982-)女，山東青島人，講師，碩士，從事網(wǎng)絡(luò)優(yōu)化設(shè)計研究．