種群自適應調整的克隆多峰函數優化

1.湖南機電職業技術學院 信息工程系，長沙 410151

2.華中科技大學 計算機科學系，武漢 430074

3.同濟大學 軟件學院，上海 230021

1.湖南機電職業技術學院 信息工程系，長沙 410151

2.華中科技大學 計算機科學系，武漢 430074

3.同濟大學 軟件學院，上海 230021

1 引言

現實生活中的很多問題都可以建模為函數優化問題。同時，由于問題本身的特點，很多問題都屬于多峰函數優化問題[1]，即需要求出多個全局最優解和局部最優解，進而為決策者提供多種選擇。如何求得多峰函數的極大值（包括全局和局部），一直是研究者關注的課題。

求解多峰函數優化問題主要有兩類方法：傳統的數學優化和智能優化算法。智能優化算法由于對目標函數沒有特殊要求而成為求解此類問題的有效方法。不同的研究者采用不同的智能優化算法對此問題進行求解[2-8]，如蜂群算法、遺傳算法、粒子群算法、免疫克隆算法等。已有研究表明，免疫克隆算法在求解多峰值函數優化問題方面表現出了優異的性能。

克隆優化算法是一種基于種群的優化方法，種群規模的大小直接影響算法的搜索能力和計算成本[3-4]。一般來說，種群規模越大，越有利于找到全局最優解，但也會增加計算時間，導致收斂速度較慢；如果種群規模過小，雖然運行時間較快，但種群多樣性不足，搜索的有效區域有限。對于多峰函數優化問題，還容易陷入局部最優，導致早熟收斂。所以，合適的種群大小對算法的效果具有重要的意義。顯然，如果種群大小能隨著進化代數動態變化，則能大大提高算法的性能。

基于此，本文提出了一種種群大小自適應變化的免疫克隆算法，并結合多峰函數的特點，采用基于拉馬克的局部搜索機制。實驗結果表明，算法可以找到更多的局部最優值，并且收斂速度較快。

2 關鍵技術

對于種群大小可變的克隆優化算法，需要解決3個問題：（1）種群規模大小什么時候變化，即用什么機制觸發增加/刪除個體的操作；（2）種群規模大小變化多少，即增加/刪除個體的數目如何確定；（3）種群規模大小如何變化，即增加/刪除個體具體如何實現。下面分別介紹。

2.1 種群規模大小的變化規則

對于種群規模什么時候變化的問題（第1個問題），本文主要思想為：個體是否更新來進行增加/刪除個體的操作。設 psmax、psmin分別表示種群規模大小的上界和下界，psg表示第g代的種群規模。具體更新規則如下：如果全局最優個體連續k代都更新，且 psg＞psmin，則認為現有個體對種群的搜索有冗余，執行刪除ninc個體的操作。反之，如果全局最優個體連續k代都不更新，則認為現有個體不足導致搜索區域不夠，則執行增加算子：當 psg＜psmax時，增加一個新個體；當 psg=psmax，則刪除一個性能較差的個體。其中，k是一個正整數，表示激活閾值。

2.2 種群規模變化數目

對于種群規模大小變化多少的問題（第2個問題），從本質上看，增加或者刪除個體的數目，決定了種群規模 psg的變化幅度。基本思路如下：隨著 psg的增大，種群規模會逐漸增加，由于資源有限，增加個體的數目ninc應該逐漸減小，而刪除個體的數目dinc應該逐漸增大。而且，當 psg較小時，ninc應該大于dinc，即種群規模的增長速率應大于收縮速率，以增強種群的全局探索能力;相反地，當 psg較大時，dinc應該大于ninc，以增強深度搜索能力。

對于種群規模變化問題，本文設計了自適應確定增加/刪除數目的方法。其中，增加個體的數目變化采用邏輯斯蒂（Logistic）模型直接實現[3]。

β為大于0的常數。

刪除個體數目方程：

2.3 種群規模變化策略

對于種群規模大小如何變化的問題（第3個問題），本文設計了一種兼顧有效性和多樣性的增加算子。

新個體的生成方法如下：

首選生成一個大小為ninc的父代個體集合s，設x1，x2為s中的任意兩個個體，新個體的產生方法如下，其中a為（0，1）之間的任意數。

可見，增加算子可以為種群帶來新個體，較好地改善種群的多樣性，同時，新生成的個體為種群的進化提供了有用信息，從而加速搜索過程。

2.4 Larmark局部搜索機制

對于多峰函數優化問題，應該盡可能多地找到局部最優值。因此，需要設計必要的局部搜索策略。這里，使用Lamarck學習進行局部搜索。

Lamarck進化理論認為，個體后天學習獲得的性狀能直接反饋在基因型上[10]。已有的研究表明，Lamarck學習是一種非常有效的學習策略。局部搜索可以看作是一個個體的后天學習過程，搜索到好的抗體片段直接反饋到抗體上，并且修改個體的適應度，通過遺傳作用遺傳給下一代。因此，局部搜索是父代個體在其鄰域上的學習過程，可以引導個體向更好的解移動。

具體如下：

假設抗體Ai原來的親和度值為 f(Ai)，學習后的抗體親和度為 f'(Ai)，則

其中，η為服從正態分布的隨機數。若 f'(Ai)＞f(Ai)并且f'(Ai')＞fbest(t)，則學習成功，用抗體基因 Ai'替換 Ai。其中，fbest(t)為第t代最高的適應度值。

3 算法具體實現

針對多峰函數優化問題，本文設計的克隆算法具體實現步驟如下：

步驟1分別設置種群最小值PSmin，最大值PSmax，設進化代數為g，令g=0，psg為第g代的種群規模，psg=PSmin，種群增加個數cinc、刪除個數dinc分別為0。

步驟3以進化代數g作為終止條件，判斷是否滿足結束條件。如果滿足結束條件，則終止程序，輸出最優解；否則，轉步驟4。

步驟4根據各個抗體的親和度值，進行克隆擴增操作。克隆采用自適應克隆[8]，即親和度高的抗體克隆數目較多。

步驟5對克隆種群進行自適應高頻變異；計算抗體的親和度；并對親和度較高的抗體進行larmrck學習（見2.4節）。

步驟7若cinc＞2k且 psg＞PSmin，則按2.3節執行刪除操作，psg-1=psg-dinc，dinc=0，否則，轉步驟10。

步驟8若cinc＜k，轉步驟9。

步驟9 若 psg＜PSmax，則按2.3節執行增加操作，psg-1= psg+dinc，dinc=0 。

步驟10 g=g+1，轉步驟3。

4 仿真實驗與結果分析

在Windows環境下，使用Matlab7.0進行編程實現。使用基準多模態測試函數對算法性能進行比較，并與文獻[7-8]進行比較。算法參數設置如下：種群PSmin=4，PSmax=100，采用二進制編碼，變異概率 pm=0.5，最大進化次數 g=300，β=0.8，k=2，學習系數η=1.3。每種算法獨立運行100次，結果如表1所示。

表1 相關算法性能比較

測試函數如下：

（1）Schaffer函數

（2）Shubert函數

（3）Rastrigin函數

（4）Griewank函數

（5）Schwefel函數

（6）Rosenbrock函數

上述測試函數中，Schaffer函數是具有強烈振蕩的多峰函數，理論最優值為－1；Shubert函數在搜索區域內約有760個局部極值點和18個全局最優點，理論最優值為－186.730 9；Rastrigrin函數為多極值函數，在解空間內存在大約10n個（n為解空間維數）局部極小點，理論最優值為0；Griewank函數有眾多局部極值，在（0，…，0）處取得全局最小值0；Schwefel函數是多峰多極值函數，在（420.96，…，420.96）處取得理論最優值0。

測試表明，本文算法表現出較強的全局尋優能力和較高的搜索精度。同時，本文算法方差較小，說明算法較為穩定。此外，本文算法運行速度較快，收斂次數較多。這些都說明本文設計的各種策略是有效的。

為了進一步說明算法在求解全局最優解方面的能力，以下面的多峰函數為例，進行說明。

該函數為多峰函數，有四個全局最大值2.118，對稱分布于（+0.64，+0.64），（－0.64，+0.64），（+0.64，－0.64），（－0.64，－0.64）。該函數存在大量局部極大值，尤其是在中間區域有一取值與全局最大值很接近的局部極大值（2.077）。

圖1、圖2為兩算法運行結束后所搜索到的最優解分布。由算法結果可以看出：本文算法具有較優的全局搜索能力，同時還可搜索到部分次優解；而文獻[7]算法容易陷入局部最優，且全局搜索能力差，說明本文設計的各種算子是有效的。

圖1 文獻[7]運行結束后的最優解分布

以上分析表明，本文算法對于解決上述多峰函數優化問題是非常有效和可靠的。

5 結論

圖2 本文算法運行結束后的最優解分布

本文提出了一種種群大小可變的克隆優化算法求解多峰函數優化問題，給出了種群變化的具體介紹和局部搜索機制。仿真實驗證明，本算法尋優能力更強，同時也更加穩定可靠。

[1]郭忠全，王振國，顏力.基于種群分類的變尺度免疫克隆選擇算法[J].國防科技大學學報，2011，33（5）：36-40.

[2]余航，焦李成，公茂果，等.基于正交試驗設計的克隆選擇函數優化[J].軟件學報，2010，21（5）：950-967.

[3]傅清平.基于新型免疫算法的多峰函數優化[J].計算機應用研究，2011，43（10）：10-15.

[4]戚玉濤，劉芳，焦李成.基于信息素模因的免疫克隆選擇函數優化[J].計算機研究與發展，2008，45（6）：991-997.

[5]魏臻，吳雷，葛方振，等.基于Memetic框架的混合粒子群算法[J].模式識別與人工智能，2012，46（12）：301-305.

[6]陸青，梁昌勇，楊善林，等.面向多峰值函數優化的自適應小生境遺傳算法[J].模式識別與人工智能，2009，43（2）：86-91.

[7]葉文，歐陽中輝，朱愛紅，等.求解多峰函數優化的小生境克隆選擇算法[J].系統工程與電子技術，2010，23（5）：210-214.

[8]薛文濤，吳曉蓓，徐志良.用于多峰函數優化的免疫粒子群網絡算法[J].系統工程與電子技術，2009，34（5）：213-217.

[9]王蓉芳，焦李成，劉芳，等.自適應動態控制種群規模的自然計算方法[J].軟件學報，2012，23（7）：1760-1772.

[10]Gong Maoguo，Jiao Licheng，Liu Fang，et al.Memetic computation based on regulation between neural and immune systems：the framework and a case study[J].Science China：Information Sciences，2010，45（11）：2131-2138.

[11]陳杰，陳晨，張娟，等.基于Memetic算法的要地防空優化部署方法[J].自動化學報，2010，32（2）：234-238.

[12]夏柱昌，劉芳，公茂果，等.基于記憶庫拉馬克進化算法的作業車間調度[J].軟件學報，2010，21（12）：3082-3093.

[13]羅曉明.求解VRP的變種群規模混合自適應遺傳算法[J].統計與決策，2011，346（22）：30-35.

[14]Gong M G，Jiao L C，Zhang L N，et al.Immune secondary responseand clonal selection inspired optimizers[J].Progress in Natural Science，2009，19：237-253.

[15]Chen Jie，Xin Bin，Peng Zhihong.Statistical learning makes the hybridization of particle swarm and differential evolution more efficient-a novel hybrid optimizer[J].IEEE Transactions on Evolutionary Computation，2008，6（3）：239-251.

種群自適應調整的克隆多峰函數優化

裴 芳1，2，張 潔1，2，唐 俊3

PEI Fang1，2,ZHANG Jie1，2,TANG Jun3

1.Department of Information Engineering,Hunan Mechanical&Electrical Polytechnic,Changsha 410151,China
2.Department of Computer Science,Huazhong University of Science and Technology,Wuhan 430074,China
3.School of Software,Tongji University,Shanghai 230021,China

In order to get the best solutions of the multi-model function,an immune clonal algorithm with self-adaptive population size is proposed.The self-adaptive population size changes with the evolutionary process are achieved to balance the impact of population size on the efficiency of the algorithm.In addition,in terms of multi-modal function optimization characteristics, Larmark learning is used as a local search strategy to enhance the search ability for the optimal solution.The experimental results show that the algorithm has better performances.

clone optimization;multi-model function;population size;local search

為了盡可能求得多峰函數的最優解，提出了一種種群規模自適應調整的克隆算法。實現了種群規模根據進化過程自適應的變化，平衡了種群規模對算法效率的影響。此外，結合多峰函數優化的特點，為了增強算法搜索最優解的能力，采用Larmack學習策略作為局部搜索機制。實驗結果表明，該算法求解效果較好。

克隆優化；多峰函數；種群規模；局部搜索

A

TP18

10.3778/j.issn.1002-8331.1210-0275

PEI Fang,ZHANG Jie,TANG Jun.Multi-model function optimization based on clonal optimization with self-adaptive population size.Computer Engineering and Applications,2013,49（11）：50-53.

湖南省教育廳自然科學研究項目（No.12C1065，No.11C0231，No.11C0232）。

裴芳（1979—），女，講師，主要研究方向為計算智能、網絡安全。

2012-10-26

2013-01-21

1002-8331（2013）11-0050-04