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

朱彥廷

（廣西現(xiàn)代職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系，廣西河池 547000）

1 引 言

遺傳算法[1]127-128由美國(guó)Michigan大學(xué)J. Holland教授1975年提出，它通過模擬生物進(jìn)化過程搜索最優(yōu)解，與傳統(tǒng)算法相比具有高魯棒性、全局搜索性、內(nèi)在并行性等優(yōu)點(diǎn)[2]94-97，因此，受到人們的普遍關(guān)注，被廣泛應(yīng)用到各個(gè)領(lǐng)域.

遺傳算法的基本步驟[3]133-135如下：

（1）設(shè)置群體大小M、終止代數(shù)T、交叉概率Pc、變異概率Pm，進(jìn)化代數(shù)t= 0，隨機(jī)生成M（應(yīng)為偶數(shù)）個(gè)個(gè)體，得到初始群體；

（2）計(jì)算群體中各個(gè)個(gè)體的適應(yīng)度；

（3）交叉操作；

（4）變異操作；

（5）選擇操作，得到下一代群體；

（6）如果t﹤T，t=t+ 1，轉(zhuǎn)到（2），如果t=T，結(jié)束運(yùn)算，將運(yùn)算過程中得到的適應(yīng)度最大的個(gè)體（即最優(yōu)解）輸出.

其中，適應(yīng)度函數(shù)和群體規(guī)模、交叉概率、變異概率等參數(shù)對(duì)算法的性能有很大影響[4]79-83，如何確定得更合理一直是人們的研究方向.

通過研究對(duì)適應(yīng)度函數(shù)、交叉概率和變異概率對(duì)遺傳算法性能的影響，本文提出一種自適應(yīng)的遺傳算法，使得群體進(jìn)化速度更快，并能避免發(fā)生早熟.

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

2.1 適應(yīng)度函數(shù)

適應(yīng)度表示個(gè)體接近最優(yōu)解的程度，個(gè)體的適應(yīng)度越高，被選擇（即遺傳）的概率越大.選擇運(yùn)算一般采用比例選擇[5]235-237，用個(gè)體的適應(yīng)度與群體中個(gè)體的適應(yīng)度的和的比值作為它被選擇的概率，因而在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)，要保證值非負(fù).

在進(jìn)化的初期，個(gè)體的適應(yīng)度普遍較低，可能出現(xiàn)個(gè)別適應(yīng)度很高的個(gè)體，因此這樣的個(gè)體被選擇的概率遠(yuǎn)大于其它個(gè)體，可能一再被選擇，從而充斥下一代群體，使進(jìn)化難以進(jìn)行（相同的個(gè)體交叉，得到的個(gè)體與原個(gè)體相同；相近的個(gè)體交叉，可能得到的個(gè)體與原個(gè)體相同），出現(xiàn)早熟現(xiàn)象；而在進(jìn)化的后期，個(gè)體的適應(yīng)度相近，較好的個(gè)體和較差的個(gè)體被選擇的概率接近，也使進(jìn)化難以進(jìn)行.

為解決上述問題，可對(duì)適應(yīng)度進(jìn)行比例變換，如線性比例變換、冪比例變換和指數(shù)比例變換等[6]90，但這通常需要對(duì)問題有深刻的了解，且經(jīng)多次試驗(yàn)，才能確定較好的變換方式及其參數(shù).

本算法用適應(yīng)度的差值來衡量適應(yīng)度的差異大小，先定義

其中，Δf為當(dāng)前群體中適應(yīng)度的差值，ΔF為適應(yīng)度的差值的理論最大值，fmin為當(dāng)前群體中適應(yīng)度的最大值，fmax為當(dāng)前群體中適應(yīng)度的最小值，F(xiàn)min為適應(yīng)度的理論最小值，F(xiàn)max為適應(yīng)度的理論最大值，易知β的取值范圍為[0，1].

如果用適應(yīng)度和其平均值的差值的絕對(duì)值的和（或差值的平方的和，即方差）等來衡量適應(yīng)度的差異大小，當(dāng)然更準(zhǔn)確，但計(jì)算繁瑣一些，在要求較高的情況下可以采用.這時(shí)理論上差值的絕對(duì)值（或差值的平方）的和的最大值出現(xiàn)在當(dāng)一半個(gè)體的適應(yīng)度均為Fmin，而另一半個(gè)體的適應(yīng)度均為Fmax時(shí).

然后對(duì)適應(yīng)度進(jìn)行變換：

其中，f（x）為原適應(yīng)度，f'（x）為變換后的適應(yīng)度，k是正常數(shù)，根據(jù)具體情況進(jìn)行設(shè)置，越大則變換力度越大，但應(yīng)盡量保證最后適應(yīng)度值非負(fù).

當(dāng)群體中個(gè)體的適應(yīng)度差異較大時(shí)（β>0.5），個(gè)體的適應(yīng)度都增加k（β -0.5），則適應(yīng)度小的個(gè)體增加的比例大，被選擇的概率將增大，有利于維持群體的多樣性，以對(duì)更廣的解空間進(jìn)行搜索，避免囿于局部極值；當(dāng)群體中的個(gè)體適應(yīng)度差異較小時(shí)（β< 0.5），個(gè)體的適應(yīng)度都減少k（0.5- β）（這往往發(fā)生在進(jìn)化后期，個(gè)體的適應(yīng)度普遍較大，減少后多半仍非負(fù)，如果個(gè)別個(gè)體的適應(yīng)度實(shí)在太小，減少后為負(fù)，可補(bǔ)充定義在這種情況下其為 0（意味著在下一代群體中不可能出現(xiàn)）或某個(gè)較小值（意味著在下一代群體中也可能出現(xiàn)，這有助于維持群體的多樣性），則適應(yīng)度大的個(gè)體減少的比例小，被選擇的概率將增大，增強(qiáng)了搜索的導(dǎo)向性，避免隨機(jī)搜索.

可以看出，該變換式只對(duì)個(gè)體之間的差異大小敏感，與單個(gè)個(gè)體適應(yīng)度的取值無關(guān)，與原適應(yīng)度函數(shù)的形式也無關(guān).

2.2 交叉概率

基本遺傳算法的交叉概率是固定的，但在進(jìn)化的初期，個(gè)體差異較大，交叉產(chǎn)生更好個(gè)體的可能性也較大，如果增大交叉概率，將加快進(jìn)化進(jìn)程；在進(jìn)化的后期，個(gè)體差異較小，交叉產(chǎn)生更好的個(gè)體的可能性也較?。ê帽取敖H結(jié)婚”），如果減小交叉概率，可減少計(jì)算量，故定義交叉概率Pc=β，顯見Pc的取值范圍為[0，1].

2.3 變異概率

基本遺傳算法的變異概率也是固定的，但當(dāng)個(gè)體差異較大時(shí)，如果減小變異概率，可減少計(jì)算量，也能保持群體的多樣性；當(dāng)個(gè)體差異較小時(shí)，如果增大變異概率，將保持群體的多樣性，故定義變異概率

變異概率一般取值較小（因?yàn)樽儺愡\(yùn)算可能破壞較好的個(gè)體），故這里乘以0.1（根據(jù)具體情況，也可以選別的數(shù)值），可知Pm的取值范圍為[0，0.1].

3 實(shí) 驗(yàn)

算法的在線性能定義為

其中f（t）是時(shí)刻t得到的適應(yīng)度的平均值.它表示算法在到當(dāng)前為止的時(shí)間內(nèi)得到的所有性能值的平均值（因算法在運(yùn)行過程中隨機(jī)性較大，故用平均值），反映了算法的動(dòng)態(tài)性能.

離線性能定義為

其中f*（t）是時(shí)間段[0，t]內(nèi)得到的適應(yīng)度的最小值.它表示算法在到當(dāng)前為止的時(shí)間內(nèi)得到的最優(yōu)性能值的平均值，反映了算法的收斂性能.

分別用基本遺傳算法和本算法求下列函數(shù)的最小值.

函數(shù)（1）是病態(tài)的，難以極小化，最小值為0（x1=1，x2=1）；

函數(shù)（2）含有高斯噪聲，若不考慮噪聲，最小值為0（x1=0，x2=0，…，x30=0）.設(shè)置M=50，T=100，基本遺傳算法的Pc=0.6，Pm=0.05，性能比較如圖l、圖2所示.

圖 l （a）、（b）分別為函數(shù)（1）、（2）的在線性能測(cè)試

圖2 （a）、（b）分別為函數(shù)（1）、（2）的離線性能測(cè)試

從圖1可以看出，本算法的在線性能比基本遺傳算法稍好，這是因?yàn)楸舅惴ǖ淖儺惛怕适莿?dòng)態(tài)變化的，有效地保持了群體的多樣性，能夠向更廣的解空間進(jìn)行探索，并避免了過早收斂.

從圖2可以看出，本算法的離線性能比基本遺傳算法有了較大提升，這是因?yàn)椋?/p>

（1）自適應(yīng)的適應(yīng)度函數(shù)能更好地推動(dòng)群體的進(jìn)化，當(dāng)個(gè)體的差異大時(shí)，它盡量縮小差距，既讓優(yōu)秀的個(gè)體能充分發(fā)展，也給較差的個(gè)體一定的進(jìn)化機(jī)會(huì)；當(dāng)個(gè)體的差異小時(shí)，它盡量增大差距，使群體能繼續(xù)進(jìn)化，不致過早收斂（即早熟）；

（2）自適應(yīng)的交叉概率能根據(jù)群體的狀況靈活調(diào)整進(jìn)化策略，當(dāng)個(gè)體的差異大時(shí)，它適當(dāng)增大，以更好地利用優(yōu)秀個(gè)體的基因，充分發(fā)揮優(yōu)秀個(gè)體對(duì)進(jìn)化的積極作用；當(dāng)個(gè)體的差異小時(shí)，由交叉產(chǎn)生更好個(gè)體的可能性減小，它適當(dāng)減小，以減少計(jì)算量；

（3）自適應(yīng)的變異概率在進(jìn)化過程中作用微妙，在進(jìn)化前期，個(gè)體的差異較大，只要很小的變異就足以保持群體的多樣性，因此它適當(dāng)減小，增強(qiáng)交叉的導(dǎo)向性（變異將改變交叉產(chǎn)生的個(gè)體）；而在進(jìn)化后期，個(gè)體的差異較小，因此它適當(dāng)增大，避免陷入局部極值.

還可以看出，本算法的收斂速度比基本遺傳算法要快不少，基本遺傳算法甚至發(fā)生早熟，這表明了本算法優(yōu)良的自適應(yīng)特性.

4 結(jié) 論

本算法把適應(yīng)度、交叉率、變異率的變化都統(tǒng)一反映在了一個(gè)β因子的變化上，能夠根據(jù)進(jìn)化情況自動(dòng)地調(diào)整適應(yīng)度、參數(shù)，具有明顯的自適應(yīng)性，能避免早熟現(xiàn)象，更快地搜索到更優(yōu)解，收斂性、收斂速度均比基本遺傳算法好，且比較簡(jiǎn)單，和基本遺傳算法十分接近，如果找到基本遺傳算法程序，略加改變即可，容易實(shí)現(xiàn).

[1]劉曉霞，竇明鑫.一種改進(jìn)的自適應(yīng)遺傳算法[J].合作經(jīng)濟(jì)與科技，2012（5）.

[2]張瑜，婁卉芳，文良浩，等.一種改進(jìn)的遺傳算法交叉策略[J].湖南科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（1）：94-97.

[3]苑士義，撒力.基本遺傳算法設(shè)計(jì)及改進(jìn)[J].微計(jì)算機(jī)信息，2011（12）：133-135.

[4]李擎，張偉，尹怡欣，等.一種新的調(diào)節(jié)交叉和變異概率的自適應(yīng)算法[J].控制與決策，2008（1）：79-83.

[5]趙志鵬.董紅斌.一種新的基于遺傳操作的改進(jìn)型遺傳算法[J].計(jì)算機(jī)應(yīng)用與軟件，2008（1）：235-237.

[6]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，1999.