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

董 勇，李夢(mèng)霞 （長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023）

郭海敏 （油氣資源與勘探技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 （長(zhǎng)江大學(xué)），湖北 武漢 430100）

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

董 勇，李夢(mèng)霞 （長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023）

郭海敏 （油氣資源與勘探技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 （長(zhǎng)江大學(xué)），湖北 武漢 430100）

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

混沌映射；粒子群算法；適應(yīng)度方差；收斂比率

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

1 An混沌映射

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

2 改進(jìn)的PSO算法

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

2.1 標(biāo)準(zhǔn)PSO算法

標(biāo)準(zhǔn)PSO算法的速度和位置迭代公式是：

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

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

2.3 迭代更新的改進(jìn)

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

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

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

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

2.4 迭代終止條件

迭代終止條件可以選達(dá)到最大迭代次數(shù)或者適應(yīng)度值達(dá)到事先設(shè)置的收斂標(biāo)準(zhǔn)。筆者采用最大迭代次數(shù)作為終止條件。

2.5 改進(jìn)的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）中隨機(jī)生成一個(gè)D維空間粒子，按照2.2節(jié)的敘述，得到N個(gè)D維粒子，記為xi，i＝1，2，…，N；類似生成N個(gè)D維向量，作為初始化的粒子飛行速度；令迭代次數(shù)為0，轉(zhuǎn)步3。

步3 將xi代入目標(biāo)函數(shù)計(jì)算適應(yīng)度f(wàn)i，確定gbest、pbesti，i＝1，2，…，N，計(jì)算適應(yīng)度方差σ2，轉(zhuǎn)步4。

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

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

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

圖1 算法流程圖

3 數(shù)值仿真

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

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

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

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

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

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

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

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

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

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

［3］任子暉，王堅(jiān) .模擬退火粒子群算法在新交通控制模型中的應(yīng)用 ［J］.計(jì)算機(jī)應(yīng)用，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］.計(jì)算機(jī)應(yīng)用與軟件，2009，26（1）：50-52.

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

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

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

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

［14］張廣強(qiáng) .均勻隨機(jī)數(shù)發(fā)生器的研究和統(tǒng)計(jì)檢驗(yàn) ［D］.大連：大連理工大學(xué)，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í)隨機(jī)數(shù)產(chǎn)生的分析 ［J］.計(jì)算機(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

國(guó)家自然科學(xué)基金項(xiàng)目 （61273179）；湖北省教育廳重點(diǎn)項(xiàng)目 （D20101304）；湖北省教育廳科學(xué)技術(shù)項(xiàng)目 （Q20121216）。

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

［編輯］ 洪云飛