董 勇，李夢霞 （長江大學信息與數(shù)學學院，湖北 荊州 434023）

郭海敏 （油氣資源與勘探技術(shù)教育部重點實驗室 （長江大學），湖北 武漢 430100）

結(jié)合混沌搜索的自適應混沌粒子群算法

董 勇，李夢霞 （長江大學信息與數(shù)學學院，湖北 荊州 434023）

郭海敏 （油氣資源與勘探技術(shù)教育部重點實驗室 （長江大學），湖北 武漢 430100）

針對基于群體適應度方差的自適應混沌粒子群算法存在的局部搜索能力較弱的不足，在該算法中引入了混沌變異以及混沌搜索操作。使用An混沌映射對部分粒子進行混沌變異，對全局最優(yōu)粒子進行混沌搜索，提出了一種綜合考慮粒子位置、尋優(yōu)空間的自適應變尺度規(guī)則。數(shù)值仿真結(jié)果表明，改進算法的收斂性、全局和局部搜索能力都有所提高，能有效避免早熟收斂。

混沌映射；粒子群算法；適應度方差；收斂比率

粒子群優(yōu)化 （Particle Swarm Optimization，PSO）算法參數(shù)簡單，容易實現(xiàn)，對目標函數(shù)的性態(tài)基本沒有要求，能以一定的概率收斂到全局最優(yōu)解，所以PSO算法得到了廣泛應用，如過程動態(tài)優(yōu)化［1］、約束優(yōu)化［2］、交通控制［3］等。作為一種隨機性算法，粒子群優(yōu)化算法在高維、多峰搜索問題中容易出現(xiàn)早熟收斂現(xiàn)象。研究者給出了多種改進形式［4－7］，其中之一是結(jié)合混沌系統(tǒng)，利用混沌系統(tǒng)的偽隨機性及遍歷性提高粒子跳出局部最優(yōu)點的能力，從而提高全局收斂的概率和速度［8］。但普遍使用Logistic混沌映射來產(chǎn)生混沌序列［9－10］，注意到Logistic混沌映射產(chǎn)生的序列均勻性較差，會在一定程度上影響算法的優(yōu)化性能。文獻 ［11］提出采用An混沌映射構(gòu)建自適應混沌粒子群算法，利用An混沌映射初始化粒子群的位置和速度，并類似文獻 ［12］，通過適應度方差的變化來自適應控制部分粒子進行混沌更新。其優(yōu)化性能強于類似結(jié)構(gòu)的基于Logistic混沌映射的混沌粒子群算法。原因在于An混沌映射產(chǎn)生的混沌序列的均勻性優(yōu)于由Logistic混沌映射產(chǎn)生的混沌序列。但正如其所指出的，在迭代的末期，算法的局部搜索能力有大的削弱。為了改善算法的性能，筆者引入2種修改方式：一是基于An混沌映射，放寬混沌變異的觸發(fā)條件，以一定的概率對非全局最優(yōu)粒子進行混沌變異；二是對全局最優(yōu)粒子進行混沌搜索。利用混沌系統(tǒng)的偽隨機性及遍歷性提高算法的全局和局部尋優(yōu)能力。

1 An混沌映射

混沌映射產(chǎn)生的點，其運動軌跡復雜，具有偽隨機性、遍歷性等性質(zhì)，介于完全隨機現(xiàn)象和確定性現(xiàn)象之間。An引入的混沌映射隨機數(shù)生成遞推式為［13］：

2 改進的PSO算法

考慮如下所示的全局最優(yōu)化模型：

2.1 標準PSO算法

標準PSO算法的速度和位置迭代公式是：

2.2 混沌映射產(chǎn)生初始種群

隨機在0、1之間取一個值，用An混沌映射N×D－1次迭代，一共得到N×D個值，依次取出D個值構(gòu)成向量，可得N個D維向量，記為cx1，cx2，cx3，…，cxN。用式（8）轉(zhuǎn)換到優(yōu)化空間（lb，ub），作為初始種群。

2.3 迭代更新的改進

對粒子x（t），產(chǎn)生［0，1］上的均勻分布隨機數(shù)p，如果p＞0.5，則對該粒子按照式（12）、（1）、（3）、（8）進行變異，變異點落入?yún)^(qū)間［lb（t＋1），ub（t＋1）］，若適應度值變小則接受變異，否則拒絕變異；如果p≤0.5，則對該粒子不進行混沌變異。

2）混沌搜索 對全局極值gbest，反復利用式 （12）、（1）、（3）、（9）進行混沌迭代。如果直到混沌迭代次數(shù)達到設(shè)定上限時適應度值都沒變小，則終止混沌搜索；否則，當適應度值變小時，即終止混沌搜索，更新gbest。

混沌搜索的區(qū)間如前式 （9）～ （11）所示逐步縮小。

3）混沌擾動 參考文獻 ［11］，利用相鄰迭代中群體適應值方差的變化大小來判斷是否發(fā)生早熟收斂。如果相鄰兩次迭代的方差很接近，小于某給定值，例如eps＝10－6，就認為需要進行擾動。先確定當前粒子群中需要擾動的粒子比率，得到需要更替的粒子數(shù)s。按照2.2節(jié)的步驟利用An混沌映射，產(chǎn)生s個粒子，替代當前粒子群中適應值最差的s個粒子，然后繼續(xù)迭代。

2.4 迭代終止條件

迭代終止條件可以選達到最大迭代次數(shù)或者適應度值達到事先設(shè)置的收斂標準。筆者采用最大迭代次數(shù)作為終止條件。

2.5 改進的PSO算法的具體流程

算法流程圖如圖1所示：

步1 初始化參數(shù)：wmax、wmin、c1、c2、N、maxDT、D，方差差異上限eps＝10－6；設(shè)置優(yōu)化空間［lb，ub］、速度限制vmax、混沌搜索的最大迭代次數(shù)HDT。

步2 在 ［0，1）中隨機生成一個D維空間粒子，按照2.2節(jié)的敘述，得到N個D維粒子，記為xi，i＝1，2，…，N；類似生成N個D維向量，作為初始化的粒子飛行速度；令迭代次數(shù)為0，轉(zhuǎn)步3。

步3 將xi代入目標函數(shù)計算適應度fi，確定gbest、pbesti，i＝1，2，…，N，計算適應度方差σ2，轉(zhuǎn)步4。

步5 混沌擾動，替換適應度最差的s個粒子；然后轉(zhuǎn)步4。

步6 若迭代次數(shù)小于maxDT，轉(zhuǎn)步4；否則，轉(zhuǎn)步7。

步7 輸出尋優(yōu)結(jié)果：gbest、fbest。

圖1 算法流程圖

3 數(shù)值仿真

選用如表1所示的5個非線性標準函數(shù)，以測試改進算法的性能，同時也便于與文獻 ［11，16］中的數(shù)值仿真結(jié)果對比。其中，f1、f2為高維單峰函數(shù)；f3、f4為高維多峰函數(shù)；f5為低維多峰函數(shù)。

表1 標準測試函數(shù)

如同文獻 ［16］所指出的，部分測試函數(shù)的理論最優(yōu)解很難達到，因此，給出了收斂標準，在實踐中以達到收斂標準判斷算法收斂。表1中的收斂標準和文獻 ［16］的收斂標準是一致的。

參數(shù)取值為c1＝c2＝2；變量維數(shù)D、定義域［lb，ub］、收斂標準如表1所示；wmax＝0.9，wmin＝0.2；混沌擾動時粒子的比例更替是61.8%；eps＝10－6。迭代次數(shù)maxDT＝1000，混沌搜索迭代次數(shù)為100，粒子群規(guī)模取100，運行20趟。為比較算法搜索效率，定義如下標準：①搜索成功的前提下，最優(yōu)平均值，記為mB；②成功搜索的比率，記為Ir，結(jié)果對比如表2所示。

對高維單峰函數(shù)f1、f2，改進算法的收斂比率為1.0，平均最優(yōu)值也最優(yōu)。原因是An混沌映射的均勻性較好，而且混沌搜索強化了對混沌特性的利用；對多峰高維函數(shù)f3，改進算法收斂比率為1，平均最優(yōu)值就是理論最優(yōu)值。對f4，改進算法直接得到理論最優(yōu)值，收斂比率是1.0，和文獻 ［16］的算法有相同效果。對f5，改進算法的最優(yōu)值有0.95的比率是理論最優(yōu)值0，高于文獻 ［11］的算法，略低于文獻 ［16］算法的效果。分析原因是理論最優(yōu)點所在谷形的面積過小，占搜索范圍比率不足0.000256。而且改進算法對f5函數(shù)做20次優(yōu)化時，得到的優(yōu)化結(jié)果只有2個值：0、0.0097159，十分接近，表明需要進一步提高算法的局部搜索能力。

對各個測試函數(shù)運行20趟，每趟迭代1000次，1000次迭代對應1000個全局最優(yōu)值，將20趟的結(jié)果平均，記為far，取以10為底數(shù)的對數(shù)，作為縱坐標，以迭代次數(shù)為橫坐標，對比了標準粒子群算法 （PSO），文獻 ［11］算法 （ACPSO），改進算法 （MACPSO）的收斂速度，如圖2所示。測試結(jié)果表明，采用An混沌映射做粒子群初始化，利用適應度方差的變化來啟動混沌擾動機制，對非全局最優(yōu)粒子做混沌變異，對全局最優(yōu)粒子做混沌搜索，并動態(tài)的調(diào)整變異和搜索范圍，該算法表現(xiàn)出了良好的收斂效果。

圖2 平均全局最優(yōu)值與迭代次數(shù)關(guān)系對比

表2 函數(shù)搜索結(jié)果

［1］莫愿斌，陳德釗，胡上序 .混沌粒子群算法及其在生化過程動態(tài)優(yōu)化中的應用 ［J］.化工學報，2006，57（7）：2123-2127.

［2］李炳宇，蕭蘊詩，吳啟迪 .一種基于粒子群算法求解約束優(yōu)化問題的混合算法 ［J］.控制與決策，2004，19（5）：804-807.

［3］任子暉，王堅 .模擬退火粒子群算法在新交通控制模型中的應用 ［J］.計算機應用，2008，28（4）：2652-2654.

［4］Kadirmanathan V，Selvarajah K，F(xiàn)leming P J.Stability analysis of the particle dynamics in particle swarm optimizer ［J］.IEEE Transactions on Evolution Computation，2006，10 （3）：245-255.

［5］Jiang M，Luo Y P，Yang S Y.Stochastic convergence and parameter selection of the standard particle swarm optimization algorithm ［J］.Information Processing Letters，2007，102 （1）：8-16.

［6］Del Valle Y，Venayagamoorthy G K，Mohagheghi S，et al.Particle swarm optimization：Basic concepts，variants and applications in power systems［J］.IEEE Transactions on Evolution Computation，2008，12 （2）：171-195.

［7］Kameyama K.Particle swarm optimization-A survey ［J］.IEICE Transactions on Information and Systems，2009，E92D （7）：1354-1361.

［8］顏琳莉 .混沌模擬退火粒子群優(yōu)化算法 ［J］.山西建筑，2008，34（1）：97-98.

［9］馮斌，王璋，孫俊 .基于混沌變異算子的小生境量子粒子群算法 ［J］.計算機應用與軟件，2009，26（1）：50-52.

［10］劉華鎣，林玉娥，張君施 .基于混沌搜索解決早熟收斂的混合粒子群算法 ［J］.計算機工程與應用，2006，42（10）：77-79.

［11］董勇，郭海敏 .基于群體適應度方差的自適應混沌粒子群算法 ［J］.計算機應用研究，2011，28（3）：854-856.

［12］呂振肅，侯志榮 .自適應變異的粒子群優(yōu)化算法 ［J］.電子學報，2004，32（3）：416-420.

［13］馮艷 .一種產(chǎn)生隨機數(shù)新方法的研究與實現(xiàn) ［D］.北京：北京工業(yè)大學，2002.

［14］張廣強 .均勻隨機數(shù)發(fā)生器的研究和統(tǒng)計檢驗 ［D］.大連：大連理工大學，2005.

［15］Shi Y，Eberhart R C.A modified swarm optimizer［C］.IEEE International Conference of Evolutionary Computation.Anchorage，Alaska：IEEE Press，May，1998.

［16］李榮鈞，常先英.PSO算法速度更新時隨機數(shù)產(chǎn)生的分析 ［J］.計算機工程，2009，35（7）：192-194.

Adaptive Chaos Particle Swarm Optimization Combined with Chaos Search

DONG Yong，Ll Meng-xia（Yangtze University，Jingzhou434023）
GUO Hai-min（Key Laboratory of Exploration Technologies for Oil and Gas Resources（Yangtze University），Ministry of Education，Jingzhou434023）

In order to improve the local search ability of adaptive chaos particle swarm optimization based on colony fitness variance（ACPSO），chaos mutation and chaos search into ACPSO are introduced.A chaos mapping is used for chaos mutation for some particles，and chaos search is performed for the global optimal particle.The results of the numerical simulation indicates that the convergence，global searching ability and local searching ability of the presented algorithm are enhanced，the algorithm can effectively avoid trapping in local minima.

chaos mapping；particle swarm optimization（PSO）；fitness variance；convergent percentage

TP301.6

A

1673-1409（2013）31-0057-04

2013-07-14

國家自然科學基金項目 （61273179）；湖北省教育廳重點項目 （D20101304）；湖北省教育廳科學技術(shù)項目 （Q20121216）。

董勇 （1980-），男，博士，講師，現(xiàn)主要從事生產(chǎn)測井資料的解釋與最優(yōu)化算法方面的教學與研究工作。

［編輯］ 洪云飛