朱彥廷

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

1 引 言

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

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

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

（2）計算群體中各個個體的適應度；

（3）交叉操作；

（4）變異操作；

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

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

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

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

2 自適應遺傳算法

2.1 適應度函數(shù)

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

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

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

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

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

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

然后對適應度進行變換：

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

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

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

2.2 交叉概率

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

2.3 變異概率

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

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

3 實 驗

算法的在線性能定義為

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

離線性能定義為

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

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

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

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

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

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

從圖1可以看出，本算法的在線性能比基本遺傳算法稍好，這是因為本算法的變異概率是動態(tài)變化的，有效地保持了群體的多樣性，能夠向更廣的解空間進行探索，并避免了過早收斂.

從圖2可以看出，本算法的離線性能比基本遺傳算法有了較大提升，這是因為：

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

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

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

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

4 結(jié) 論

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

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

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

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

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

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

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