基于分級策略的演化算法

摘要：為了避免演化算法過早收斂，保持種群多樣性，增加算法的搜索能力，本文提出基于分級策略的演化算法.即通過對種群進行分級，來度量種群的多樣性，衡量算法是否陷入局部最優，協調種群多樣性和精英策略之間的矛盾，再根據種群分布的多樣性設計一種有效的半一致交叉算子與單重均勻變異算子.

關鍵詞：分級策略；種群多樣性；精英策略；演化算法

中圖分類號：024 文獻標識碼：A

1引言

演化算法是一類基于群智能的隨機優化算法[1]，適用于求解大量非線性、不可微和多峰值的復雜優化問題.由于算法程序實現起來異常簡潔、需要調整的參數也少，因而已應用于多個學科和工程領域[2][3].但演化算法與其他全局優化算法一樣存在著早熟收斂現象，尤其是在比較復雜的多峰搜索問題中.目前國內外學者已經提出了多種改進算法來克服粒子群算法的早熟收斂問題[4].

本文提出一種基于分級策略的種群多樣性度量方法，衡量算法是否陷入局部最優，協調種群多樣性和精英策略之間的矛盾，從而避免演化算法過早收斂.同時設計一種有效的半一致交叉算子與單重均勻變異算子，增加了算法的搜索能力.仿真的實驗結果表明所提出的基于分級策略的演化算法能有效地求解優化問題.

2基于分級策略的粒子群優化算法

演化算法求解的種群多樣性研究算法常常會受到多樣性問題的困擾而陷入早期收斂，其結果是算法陷入局部最優.因此，為保證演化算法的全局收斂性就必須維持種群的多樣性，它是提高算法的關鍵，是種群演化的動力.

2.1種群分級

演化過程中，在全局最優位置的吸引下，所有粒子不可避免地會出現聚集現象.因此本文根據種群個體的位置，對種群進行分級.

2.2種群多樣性的評估

若S是H上的一個劃分，利用S將種群P= 劃分為m個等級.若P中第k等級的個體數為 ，則稱 為種群在劃分S下的對種群多樣性的度量.演化過程中，隨著迭代次數的增加，所有個體會向某一級別圓環區域靠攏，即出現聚集現象，算法陷入局部最優.當種群個體全部處于同一級別時，達到其最小值0.當種群中所有粒子的平均位于不同的區間時，種群多樣性最豐富，達到最大值.可見，其值隨著種群多樣性的增加而增加.

2.3 精英保留策略

精英策略是對每代中一定數量的最優個體，使之直接進入下一代.這樣可以防止優秀個體由于復制、雜交或變異中的偶然因素而被破壞掉.這是增強算法穩定性和收斂性的有效方法[5].精英選取數量一直是一個很難解決的問題.如果選取過大，種群多樣性會受到影響.選取過小又沒有什么效果.大部分的精英策略都是通過選定一個恒量來執行，所以它就無法根據群體的多樣性做出變化，進而導致它無法很好控制算法的收斂和復雜性.如何將精英取值與種群多樣性結合起來是當前急需解決的問題[6].

2.5 單重均勻變異算子

常用變異算子按變異方式的不同又分為單重均勻變異算子、單重邊界變異算子、單重高斯變異算子[6].以上變異都是在單個變量上進行的，當變異操作是對每個變量獨立地按上述方式進行時，就得到了多重變異操作.因此，相應地有多重均勻變異、多重邊界變異和多重高斯變異算子等.

均勻變異和高斯變異要優于邊界變異，因為最優值取邊界的概率比較小.變異算子的主要作用就是在種群進化的后期在一定程度上幫助種群跳出局部最優解，而高斯變異算子使變異值更多停留在原值附近.并且因為它需要計算擾動 ，所以它的計算量比較大.綜上所述，本文采取單重均勻變異算子：按均勻分布隨機選擇一個變量 ，并將它變異為取值空間 中的均勻隨機數r ：

變異能改善遺傳算法的局部搜索性能，變異率設置不當，有可能破壞優良個體或使算法最終收斂到局部最優.在進化初期，個體的差異較大，種群能不斷產生新的更優良的個體，種群的平均適應度迅速提高，最優個體向著最（次）優解附近靠攏，此時變異概率很小.到了進化后期，由于種群個體間的差異變小，交叉難以產生新的個體，如果陷入局部最優，很難跳出來，這也是遺傳算法常出現不成熟收斂及收斂速度慢的主要原因，可通過加大變異率，使進化跳出局部最優狀態，并在局部最優點附近進行更有效的搜索.同樣我們也可根據種群熵來判斷變異率的取值，因為在種群演化的前大半段變異率比較小，但到了后半段特別是接近最（次）優解附近需要比較大.

4 結論

針對演化算法容易陷入局部最優的不足，本文提出一種基于分級策略的演化算法.數值實驗證實了新方法的可行性、有效性和通用性，其性能優于現有的一些演化算法.

參考文獻

[1]Eberhart R， Shi Y. Comparing inertia weights andconstriction Factor in particle swarm optimization[C].Proceedings of the IEEE Congress on Evolu-tionary Computation. San Diego： IEEE Inc， 2001：84-88.

[2] Wachowiak M P， Smolikova R， Zheng Y F. An ap-proach to multimodal biomedical image registration u-tilizing particle swarm optimization[J]. IEEE Trans-action on Evolutionary Computation， 2004， 8 （3）：289-301.

[3] Lu Z， Ji T Y， Tang W H. Optimal harmonic estima-tion using a particle swarm optimizer [ J]. IEEETransaction on Power Dilivery， 2008， 23（2）： 1 166-1 173.

[4] Higashi N， Iba H. Particle swarm optimization with Gaussian mutation [C].Proceedings of the IEEE Swarm Intelligence Symposium. [s.l.]： IEEE Inc，2003： 72-79.

[5] 石玉，于盛林.實數交叉算子的選取和算法改進[J].南京郵電學院學報，2002，22（2）：42-46

[6] 林丹，李敏強，寇紀凇.基于實數編碼的遺傳算法的收斂性研究[J].計算機研究與發展，2000，37（11）：1321-1327.

[7]T.P. Runarsson and X. Yao， Stochastic ranking for constrained evolutionary optimization. IEEE Trans[J]. on Evolutionary Computation，2000， 4（3）：284-294.

[8]Deb K.Pratap A.Mcyarivan T.Constrained Test Problems for Multi-objective Evolutionary Optimization [R].KanCAL report，200002，Kanpur：Indian Institute Technology，2002.

[9]WU Zhi-jian，KANG Li-shan，Zou Xiu-fen.An-Elite-subspace Evolutionary Algorithm for Solving Function Optimization Problems[J].Compution Applications，2003，2（2）：13-16.

[10] Yu L，Liu H.Efficient feature selection via analysis of relevance and redundancy [J]. Journal of Machine Learning Research， 2004，46（5）：1205-1224.