宮照煊，王 莉

(遼寧科技大學(xué) 電子與信息工程學(xué)院，遼寧 鞍山 114051)

對(duì)于函數(shù)優(yōu)化問題，傳統(tǒng)的經(jīng)典優(yōu)化方法大都是基于梯度下降或者需要求解問題的導(dǎo)數(shù)。而對(duì)于多峰、多態(tài)以及求解空間比較大的復(fù)雜函數(shù)，傳統(tǒng)算法的求解效果很有限，甚至無(wú)法求解。遺傳算法雖然簡(jiǎn)單易行，并以高效性、隱并行性成為求解優(yōu)化問題的有效方法[1]，但其為群體中的個(gè)體提供進(jìn)化機(jī)會(huì)的同時(shí)，在某種情況下退化現(xiàn)象也相當(dāng)明顯。近年來(lái)，人們?cè)诨谏锩庖咴淼幕A(chǔ)上提出了多種人工免疫系統(tǒng)模型和算法[2]，并應(yīng)用到自動(dòng)控制、故障診斷、優(yōu)化計(jì)算等領(lǐng)域。免疫克隆遺傳算法是將免疫原理與遺傳算法相結(jié)合所發(fā)展的一種新算法。免疫克隆遺傳算法提供記憶細(xì)胞，使變異向提高適應(yīng)值的方向發(fā)展，避免了搜索的盲目性。但對(duì)于求解一些高精度的復(fù)雜函數(shù)問題，免疫克隆遺傳算法的求解效果欠佳，主要原因是算法在進(jìn)化后期的局部搜索能力有限，以及種群多樣性的快速下降而導(dǎo)致算法過早收斂到最優(yōu)解的附近，而很難收斂到最優(yōu)解。針對(duì)上述問題，本文提出了一位修正算子來(lái)解決算法進(jìn)化后期存在的問題，并對(duì)免疫克隆遺傳算法的各個(gè)算子都做了相應(yīng)的改進(jìn)，最后用標(biāo)準(zhǔn)遺傳算法SGA(Standard Genrtic Algorithm)、免疫克隆遺傳算法IMGA(Immunity Monoclonal Genrtic Algorithm)以及本文的算法比較，并且與參考文獻(xiàn)[6]和參考文獻(xiàn)[7]的方法作了比較。實(shí)驗(yàn)結(jié)果表明，本文的算法收斂速度更快、求解精度更高，并且能有效解決免疫克隆遺傳算法后期進(jìn)化慢的問題。

1 改進(jìn)的免疫克隆遺傳算法計(jì)算步驟

1.1 基本步驟的改進(jìn)

1.1.1 編碼

改進(jìn)的免疫克隆遺傳算法采用實(shí)數(shù)編碼來(lái)處理算法的編碼過程，基于實(shí)數(shù)編碼不會(huì)存在二進(jìn)制編碼中的Hamming懸崖問題，并且求解精度要比二進(jìn)制編碼高很多，基于實(shí)數(shù)編碼的遺傳算法能很快收斂到最優(yōu)解附近。

1.1.2 初始化

不論采用離散重組算子還是算數(shù)雜交算子，搜索范圍只局限于初始群體所確定的最大矩體內(nèi)。采用混沌初始化方法，利用混沌的遍歷性、隨機(jī)性和內(nèi)在規(guī)律性來(lái)最大化初始種群所確定的矩體。混沌初始化在保持種群多樣性的同時(shí)，對(duì)防止算法陷入局部最優(yōu)解也起到了一定作用。Logist映射：

式中μ取 4，此時(shí)的 Logisti映射為在(0，1)區(qū)間上的完全混沌狀態(tài)。產(chǎn)生混沌初始種群的方法：隨機(jī)初始化x0∈(0，1)，利用式(1)生成混沌序列 x0，x1，x2，…xi(i=1，2，…m)，其中 m 為種群數(shù)。 利用混沌序列 x0，x1，x2，…xi生成初始群體 p0，p1，…pi(i=1，2，…m)。

1.1.3 選擇

本算法在采用輪盤賭選擇法的基礎(chǔ)上引入了適應(yīng)值的非單調(diào)標(biāo)度變換，用來(lái)解決種群中出現(xiàn)個(gè)別適應(yīng)值極高的個(gè)體時(shí)，可能導(dǎo)致這些個(gè)體在種群中迅速繁殖的現(xiàn)象，即讓一些適應(yīng)值較小的個(gè)體也有參加進(jìn)化的可能，從而增加種群多樣性。在選擇算子中采用精英保留策略，現(xiàn)已證明采用精英保留策略的遺傳算法能以概率1收斂到問題的最優(yōu)解[3]。適應(yīng)值的非單調(diào)標(biāo)度變換：

其中fmax為當(dāng)前適應(yīng)值最大的個(gè)體，fmin為當(dāng)前適應(yīng)值最小的個(gè)體，eval[i]為當(dāng)前各個(gè)體的適應(yīng)值[4]。

1.1.4 改進(jìn)的自適應(yīng)變異、雜交概率

改進(jìn)的自適應(yīng)變異、雜交概率能提高群體中表現(xiàn)優(yōu)良的個(gè)體交叉率和變異率，使得這些優(yōu)良個(gè)體避免出現(xiàn)近似停滯不前的狀態(tài)，從而增加進(jìn)化走出局部最優(yōu)解的可能性。

式中 Pc1=0.9，Pc2=0.6，Pm1=1，Pm2=0.001

因?yàn)槊庖呖寺∷阕佑杏洃浀墓δ埽沟眠M(jìn)化一直向適應(yīng)值增加的方向進(jìn)行，所以Pm1=1。

1.1.5 改進(jìn)的免疫克隆變異雜交

本算法在免疫克隆變異、雜交的基礎(chǔ)上考慮了染色體各個(gè)基因位對(duì)適應(yīng)值的影響程度。針對(duì)函數(shù)優(yōu)化問題，考慮到在進(jìn)化初期染色體的前幾位對(duì)適應(yīng)值的影響相對(duì)后幾位要大，所以在進(jìn)化初期算法主要對(duì)染色體的前幾位進(jìn)行變異和雜交；在進(jìn)化后期對(duì)染色體的后幾位進(jìn)行變異和雜交，這樣做可以大大縮小搜索范圍。免疫克隆變異、雜交是將各個(gè)體克隆一定數(shù)量后進(jìn)行變異、雜交操作，并且保留原個(gè)體信息。將克隆變異、雜交后的個(gè)體與原個(gè)體比較，選出適應(yīng)值最高的個(gè)體來(lái)作為新個(gè)體[5]。

1.1.6 位爬山局部搜索算法

免疫克隆遺傳算法最主要的特點(diǎn)是能以較快的速度搜索到最優(yōu)解的90%左右，全局搜索能力強(qiáng)，但是在進(jìn)化后期的局部搜索能力相對(duì)較弱。位爬山算法是一種傳統(tǒng)的局部搜索算法，將位爬山算法與免疫克隆遺傳算法相結(jié)合可以取得較好的效果，本文在傳統(tǒng)位爬山算法的基礎(chǔ)上提出了一位修正算子，用來(lái)改進(jìn)其在后期搜索過程中的不足，并在仿真實(shí)驗(yàn)中得到了滿意的結(jié)果。

1.2 改進(jìn)的位爬山算法

傳統(tǒng)的位爬山算法過程是[3]：

(1)對(duì)于染色體aji=(aj1，aj2，…aji)其中 i∈(1，2，…n)，j∈(1，2，…m)計(jì)算個(gè)體的適應(yīng)值：f*=f(aji)，i=1，j=1；

(2)變異各位基因值 ：a′ji=1-aji；

(3)計(jì)算新個(gè)體適應(yīng)值：f(a′ji)；

(4)比較新個(gè)體適應(yīng)值：if f(a′ji)＞f*then f*=f(a′ji)

a′ji=(aj1，aj2，…a′ji，aji+1，…ajn)；

(5)循環(huán) i=i+1，返回(2)；

(6)若 i=n，j=j+1 返回(1)；

(7)若 j=m，終止。

位爬山算法存在以下問題：(1)局部最大：某個(gè)節(jié)點(diǎn)比周圍任何一個(gè)鄰居都高，但是卻不是整個(gè)問題的最高點(diǎn)。(2)高地(也稱為平頂)：搜索一旦到達(dá)高地，就無(wú)法確定搜索最佳方向，會(huì)產(chǎn)生隨機(jī)走動(dòng)，使得搜索效率降低。(3)山脊：搜索可能會(huì)在山脊的兩面來(lái)回振蕩，前進(jìn)步伐很小。

對(duì)于函數(shù)優(yōu)化問題來(lái)說(shuō)，最優(yōu)解的每一位數(shù)的取值都受其后幾位的影響，所以傳統(tǒng)的位爬山算法很可能指導(dǎo)算法向偏離最優(yōu)解的方向搜索。

針對(duì)上述問題，本文提出了一位修正算子來(lái)改進(jìn)位爬山算法的不足。具體過程如下：

(1)設(shè)aij是利用位爬山算法搜索到的第i個(gè)個(gè)體中變異第j位基因所得到的最優(yōu)變異個(gè)體。

(2)對(duì)于該最優(yōu)變異個(gè)體，在其他位不變的情況下，搜索aij與aij-1的全部組合所得到的個(gè)體適應(yīng)值為evalk，k=0，1，2，…，99aij，aij-1∈(0，9)。

改進(jìn)的位爬山算法可以以較大的概率避免算法向遠(yuǎn)離最優(yōu)解的方向搜索，在進(jìn)化后期采用改進(jìn)的位爬山算法搜索到最優(yōu)解的能力也大大提高了。實(shí)驗(yàn)表明，改進(jìn)的位爬山算法能以較大的概率克服傳統(tǒng)位爬山算法的不足，并且能較快收斂到最優(yōu)解。

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

本文選取了4個(gè)具有相當(dāng)復(fù)雜度的測(cè)試函數(shù)：

F1函數(shù)在自變量取值區(qū)間內(nèi)有多個(gè)極值點(diǎn)，精確到10-12的最優(yōu)解為 2.850 273 766 768。

表1 4種函數(shù)50次獨(dú)立實(shí)驗(yàn)的統(tǒng)計(jì)結(jié)果

F2函數(shù)有6個(gè)局部極小點(diǎn)，其中有 2個(gè)點(diǎn)(-0.898，0.712 6)和(0.898，-0.712 6)為全局最小點(diǎn)，最小值為-1.031 628。

F3函數(shù)有760個(gè)局部極小點(diǎn)，其中有18個(gè)全局最小點(diǎn)，最小值為186.73，此函數(shù)極易陷入局部極小值185.25。

F4 函數(shù)(大海撈針函數(shù))，α∈{0.1，0.01，0.001}隨著α的取值不同，此函數(shù)形成不同嚴(yán)重程度的模式欺騙問題。當(dāng)α=0.001時(shí)，此函數(shù)有無(wú)限個(gè)局部極大點(diǎn)，其中只有1個(gè)點(diǎn)(0，0)為全局最大值點(diǎn)，最大值為1。此函數(shù)最大值周圍有1個(gè)圈脊，取值均為0.990 283，因此此函數(shù)非常容易停滯在此局部極大點(diǎn)。本文α取0.001。

對(duì)SGA、IMGA以及本文的算法進(jìn)行了比較，參數(shù)選取如下：F1種群數(shù) 50，最大進(jìn)化代數(shù) 50；F2種群數(shù)100，最大進(jìn)化代數(shù) 50；F3種群數(shù) 50，最大進(jìn)化代數(shù) 50；F4種群數(shù)100，最大進(jìn)化代數(shù)50。4種函數(shù)的50次獨(dú)立實(shí)驗(yàn)結(jié)果如表1所示：

從表1中可以看到，由于函數(shù)本身的復(fù)雜性，SGA的結(jié)果是不如人意的。IMGA對(duì)于前3個(gè)函數(shù)能較快收斂到最優(yōu)解，但由于F4函數(shù)具有嚴(yán)重的模式欺騙問題，使得IMGA只能搜索到局部最優(yōu)。而本文算法在求解精度和求得全局最優(yōu)解的次數(shù)上都遠(yuǎn)優(yōu)于SGA和IMGA。

[6]使用一種基于種群劃分和雜交的免疫遺傳算法對(duì)F1函數(shù)作了測(cè)試，表2為參考文獻(xiàn)[6]中的算法與本文算法在獨(dú)立測(cè)試100次后的比較結(jié)果：

從表2可以看出，在種群數(shù)一樣的前提下本文算法與參考文獻(xiàn)[6]中的算法都能收斂到最優(yōu)解，但本文算法利用一位修正算子大大提高了進(jìn)化后期的收斂速度，因此所需的平均進(jìn)化代數(shù)要比參考文獻(xiàn)[6]中的算法少得多。

表2 參考文獻(xiàn)[6]算法與本文算法在F1函數(shù)上的性能比較

參考文獻(xiàn)[7]對(duì)遺傳算法的各個(gè)算子都做了改進(jìn)，并對(duì)F2函數(shù)和F4函數(shù)作了測(cè)試，表3為參考文獻(xiàn)[7]算法與本文算法的比較結(jié)果。

表3 參考文獻(xiàn)[7]算法與本文算法在F2與F4函數(shù)上的性能比較

從表3可以看出對(duì)于F2函數(shù)與F4函數(shù)，當(dāng)進(jìn)化20代后，本文算法得到的最優(yōu)解都要優(yōu)于參考文獻(xiàn) [7]中的算法，在進(jìn)化到40代時(shí)，本文算法都收斂到了最優(yōu)解。

本文在免疫克隆遺傳算法的基礎(chǔ)上對(duì)各個(gè)算子都做了一些改進(jìn)，并且提出了一種一位修正算子來(lái)克服免疫克隆遺傳算法在后期搜索方面的不足。實(shí)驗(yàn)結(jié)果表明本文的算法在收斂速度和收斂精度上遠(yuǎn)遠(yuǎn)優(yōu)于SGA和IMGA，并且通過與參考文獻(xiàn)[6]和參考文獻(xiàn)[7]中的算法的比較，體現(xiàn)出本文算法在進(jìn)化代數(shù)上的優(yōu)勢(shì)。

參考文獻(xiàn)

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

[2]DU H， JIAO L， WANG S.Clonal Operator and antibody clone algorithms[C].Proceedings of the First International Conferrence on Machine Learning and Cybernetics， Beijing，2002.

[3]張文修.遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安：西安交通大學(xué)出版社，2000.

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

[5]焦李成，劉芳，緱水平.智能數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)[M].西安：西安電子科技大學(xué)出版社，2006.

[6]武研，李儒耘.一種基于種群劃分及雜交的免疫遺傳算法[J].計(jì)算機(jī)工程，2008，2(3)：220-222.

[7]王慶明，宋玉梅.基于改進(jìn)遺傳算法的函數(shù)優(yōu)化及其性能分析.機(jī)械設(shè)計(jì)與制造[J].2007，2(2)：52-54.