種群自適應(yīng)調(diào)整的克隆多峰函數(shù)優(yōu)化

1.湖南機(jī)電職業(yè)技術(shù)學(xué)院 信息工程系，長沙 410151

2.華中科技大學(xué) 計算機(jī)科學(xué)系，武漢 430074

3.同濟(jì)大學(xué) 軟件學(xué)院，上海 230021

1.湖南機(jī)電職業(yè)技術(shù)學(xué)院 信息工程系，長沙 410151

2.華中科技大學(xué) 計算機(jī)科學(xué)系，武漢 430074

3.同濟(jì)大學(xué) 軟件學(xué)院，上海 230021

1 引言

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

求解多峰函數(shù)優(yōu)化問題主要有兩類方法：傳統(tǒng)的數(shù)學(xué)優(yōu)化和智能優(yōu)化算法。智能優(yōu)化算法由于對目標(biāo)函數(shù)沒有特殊要求而成為求解此類問題的有效方法。不同的研究者采用不同的智能優(yōu)化算法對此問題進(jìn)行求解[2-8]，如蜂群算法、遺傳算法、粒子群算法、免疫克隆算法等。已有研究表明，免疫克隆算法在求解多峰值函數(shù)優(yōu)化問題方面表現(xiàn)出了優(yōu)異的性能。

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

基于此，本文提出了一種種群大小自適應(yīng)變化的免疫克隆算法，并結(jié)合多峰函數(shù)的特點(diǎn)，采用基于拉馬克的局部搜索機(jī)制。實(shí)驗(yàn)結(jié)果表明，算法可以找到更多的局部最優(yōu)值，并且收斂速度較快。

2 關(guān)鍵技術(shù)

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

2.1 種群規(guī)模大小的變化規(guī)則

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

2.2 種群規(guī)模變化數(shù)目

對于種群規(guī)模大小變化多少的問題（第2個問題），從本質(zhì)上看，增加或者刪除個體的數(shù)目，決定了種群規(guī)模 psg的變化幅度?；舅悸啡缦拢弘S著 psg的增大，種群規(guī)模會逐漸增加，由于資源有限，增加個體的數(shù)目ninc應(yīng)該逐漸減小，而刪除個體的數(shù)目dinc應(yīng)該逐漸增大。而且，當(dāng) psg較小時，ninc應(yīng)該大于dinc，即種群規(guī)模的增長速率應(yīng)大于收縮速率，以增強(qiáng)種群的全局探索能力;相反地，當(dāng) psg較大時，dinc應(yīng)該大于ninc，以增強(qiáng)深度搜索能力。

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

β為大于0的常數(shù)。

刪除個體數(shù)目方程：

2.3 種群規(guī)模變化策略

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

新個體的生成方法如下：

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

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

2.4 Larmark局部搜索機(jī)制

對于多峰函數(shù)優(yōu)化問題，應(yīng)該盡可能多地找到局部最優(yōu)值。因此，需要設(shè)計必要的局部搜索策略。這里，使用Lamarck學(xué)習(xí)進(jìn)行局部搜索。

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

具體如下：

假設(shè)抗體Ai原來的親和度值為 f(Ai)，學(xué)習(xí)后的抗體親和度為 f'(Ai)，則

其中，η為服從正態(tài)分布的隨機(jī)數(shù)。若 f'(Ai)＞f(Ai)并且f'(Ai')＞fbest(t)，則學(xué)習(xí)成功，用抗體基因 Ai'替換 Ai。其中，fbest(t)為第t代最高的適應(yīng)度值。

3 算法具體實(shí)現(xiàn)

針對多峰函數(shù)優(yōu)化問題，本文設(shè)計的克隆算法具體實(shí)現(xiàn)步驟如下：

步驟1分別設(shè)置種群最小值PSmin，最大值PSmax，設(shè)進(jìn)化代數(shù)為g，令g=0，psg為第g代的種群規(guī)模，psg=PSmin，種群增加個數(shù)cinc、刪除個數(shù)dinc分別為0。

步驟3以進(jìn)化代數(shù)g作為終止條件，判斷是否滿足結(jié)束條件。如果滿足結(jié)束條件，則終止程序，輸出最優(yōu)解；否則，轉(zhuǎn)步驟4。

步驟4根據(jù)各個抗體的親和度值，進(jìn)行克隆擴(kuò)增操作。克隆采用自適應(yīng)克隆[8]，即親和度高的抗體克隆數(shù)目較多。

步驟5對克隆種群進(jìn)行自適應(yīng)高頻變異；計算抗體的親和度；并對親和度較高的抗體進(jìn)行l(wèi)armrck學(xué)習(xí)（見2.4節(jié)）。

步驟7若cinc＞2k且 psg＞PSmin，則按2.3節(jié)執(zhí)行刪除操作，psg-1=psg-dinc，dinc=0，否則，轉(zhuǎn)步驟10。

步驟8若cinc＜k，轉(zhuǎn)步驟9。

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

步驟10 g=g+1，轉(zhuǎn)步驟3。

4 仿真實(shí)驗(yàn)與結(jié)果分析

在Windows環(huán)境下，使用Matlab7.0進(jìn)行編程實(shí)現(xiàn)。使用基準(zhǔn)多模態(tài)測試函數(shù)對算法性能進(jìn)行比較，并與文獻(xiàn)[7-8]進(jìn)行比較。算法參數(shù)設(shè)置如下：種群PSmin=4，PSmax=100，采用二進(jìn)制編碼，變異概率 pm=0.5，最大進(jìn)化次數(shù) g=300，β=0.8，k=2，學(xué)習(xí)系數(shù)η=1.3。每種算法獨(dú)立運(yùn)行100次，結(jié)果如表1所示。

表1 相關(guān)算法性能比較

測試函數(shù)如下：

（1）Schaffer函數(shù)

（2）Shubert函數(shù)

（3）Rastrigin函數(shù)

（4）Griewank函數(shù)

（5）Schwefel函數(shù)

（6）Rosenbrock函數(shù)

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

測試表明，本文算法表現(xiàn)出較強(qiáng)的全局尋優(yōu)能力和較高的搜索精度。同時，本文算法方差較小，說明算法較為穩(wěn)定。此外，本文算法運(yùn)行速度較快，收斂次數(shù)較多。這些都說明本文設(shè)計的各種策略是有效的。

為了進(jìn)一步說明算法在求解全局最優(yōu)解方面的能力，以下面的多峰函數(shù)為例，進(jìn)行說明。

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

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

圖1 文獻(xiàn)[7]運(yùn)行結(jié)束后的最優(yōu)解分布

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

5 結(jié)論

圖2 本文算法運(yùn)行結(jié)束后的最優(yōu)解分布

本文提出了一種種群大小可變的克隆優(yōu)化算法求解多峰函數(shù)優(yōu)化問題，給出了種群變化的具體介紹和局部搜索機(jī)制。仿真實(shí)驗(yàn)證明，本算法尋優(yōu)能力更強(qiáng)，同時也更加穩(wěn)定可靠。

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

[2]余航，焦李成，公茂果，等.基于正交試驗(yàn)設(shè)計的克隆選擇函數(shù)優(yōu)化[J].軟件學(xué)報，2010，21（5）：950-967.

[3]傅清平.基于新型免疫算法的多峰函數(shù)優(yōu)化[J].計算機(jī)應(yīng)用研究，2011，43（10）：10-15.

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

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

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

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

[8]薛文濤，吳曉蓓，徐志良.用于多峰函數(shù)優(yōu)化的免疫粒子群網(wǎng)絡(luò)算法[J].系統(tǒng)工程與電子技術(shù)，2009，34（5）：213-217.

[9]王蓉芳，焦李成，劉芳，等.自適應(yīng)動態(tài)控制種群規(guī)模的自然計算方法[J].軟件學(xué)報，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算法的要地防空優(yōu)化部署方法[J].自動化學(xué)報，2010，32（2）：234-238.

[12]夏柱昌，劉芳，公茂果，等.基于記憶庫拉馬克進(jìn)化算法的作業(yè)車間調(diào)度[J].軟件學(xué)報，2010，21（12）：3082-3093.

[13]羅曉明.求解VRP的變種群規(guī)?；旌献赃m應(yīng)遺傳算法[J].統(tǒng)計與決策，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.

種群自適應(yīng)調(diào)整的克隆多峰函數(shù)優(yōu)化

裴 芳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

為了盡可能求得多峰函數(shù)的最優(yōu)解，提出了一種種群規(guī)模自適應(yīng)調(diào)整的克隆算法。實(shí)現(xiàn)了種群規(guī)模根據(jù)進(jìn)化過程自適應(yīng)的變化，平衡了種群規(guī)模對算法效率的影響。此外，結(jié)合多峰函數(shù)優(yōu)化的特點(diǎn)，為了增強(qiáng)算法搜索最優(yōu)解的能力，采用Larmack學(xué)習(xí)策略作為局部搜索機(jī)制。實(shí)驗(yàn)結(jié)果表明，該算法求解效果較好。

克隆優(yōu)化；多峰函數(shù)；種群規(guī)模；局部搜索

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.

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

裴芳（1979—），女，講師，主要研究方向?yàn)橛嬎阒悄?、網(wǎng)絡(luò)安全。

2012-10-26

2013-01-21

1002-8331（2013）11-0050-04