摘" 要：針對(duì)雞群優(yōu)化（chicken swarm optimization，CSO）算法已有的收斂性分析結(jié)果屬于弱收斂，不能保證算法能在有限步內(nèi)收斂到問題的全局最優(yōu)這一不足，提出了運(yùn)用鞅方法來研究CSO算法的全局收斂性.首先，基于CSO算法的相關(guān)定義，建立CSO算法的馬爾可夫（Markov）鏈模型，分析其Markov性質(zhì)；其次，將具有最小適應(yīng)度值的雞群狀態(tài)序列轉(zhuǎn)化成上鞅，利用上鞅收斂定理和Egoroff定理證明了CSO算法的幾乎處處強(qiáng)收斂性和一致收斂性，進(jìn)而得出了當(dāng)雞群狀態(tài)空間有限時(shí)，CSO算法能確保在有限步內(nèi)收斂到問題的全局最優(yōu)這一結(jié)論；最后，在仿真實(shí)驗(yàn)中成功驗(yàn)證了理論證明的正確性，并發(fā)現(xiàn)CSO算法比其他算法具有更強(qiáng)的尋優(yōu)能力和更高的收斂精度.

關(guān)鍵詞：CSO算法；Markov鏈；上鞅收斂定理；Egoroff定理；幾乎處處強(qiáng)收斂；一致收斂

中圖分類號(hào)：TP301.6;TP18""" ""文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1000-2367（2024）06-0080-08

雞群優(yōu)化算法［1］（簡稱雞群算法）屬于群智能優(yōu)化算法中的一種，主要通過模擬雞群中的等級(jí)秩序和覓食行為，利用雞的群體智能來解決優(yōu)化問題.相較于粒子群優(yōu)化［2］（particle swarm optimization，PSO）算法、差分進(jìn)化［3］（differential evolution，DE）算法，其具有參數(shù)少、收斂速度快、簡單易操作等特點(diǎn)［4］.目前，CSO算法已被成功地應(yīng)用到了車間調(diào)度、路徑規(guī)劃、圖像分類、資源分配等領(lǐng)域［5］中，并且根據(jù)實(shí)際問題的特殊性，出現(xiàn)了一大批CSO改進(jìn)算法［6-8］.不難發(fā)現(xiàn)，由于發(fā)展時(shí)間較短，CSO算法改進(jìn)與應(yīng)用雖然已有了不少研究成果，但與其他算法相比，它在數(shù)學(xué)理論方面的研究還比較少，特別是關(guān)于算法的收斂性研究仍不多見，因此在一定程度上也限制了CSO算法的改進(jìn)和應(yīng)用.

作為一種常用來分析群智能算法收斂性的數(shù)學(xué)工具，隨機(jī)搜索算法的收斂準(zhǔn)則已成功運(yùn)用到了蝙蝠算法（bat algorithm，BA）［9］、灰狼優(yōu)化（grey wolf optimization，GWO）算法［10］和螢火蟲算法（firefly algorithm，F(xiàn)A）［11］等算法的收斂性證明中.同樣地，文獻(xiàn)［12］通過建立CSO算法的Markov鏈模型，并結(jié)合該收斂準(zhǔn)則，證明了CSO算法能收斂到問題的全局最優(yōu).然而，上述證明方法存在如下不足：一是通過該方法進(jìn)行收斂性理論分析時(shí)過程較為復(fù)雜，且得到的收斂結(jié)果屬于依概率收斂，在弱大數(shù)定律范疇中；二是無法確保CSO算法能在有限步內(nèi)收斂到問題的全局最優(yōu).針對(duì)這兩點(diǎn)，本文基于CSO算法的Markov鏈模型，提出了用鞅方法代替Markov鏈的遍歷性分析來研究CSO算法的全局收斂性.不僅有效簡化了CSO算法全局收斂性理論分析的過程，而且還成功證明了當(dāng)雞群狀態(tài)空間有限時(shí)，CSO算法能確保在有限步內(nèi)以概率1收斂到問題的全局最優(yōu).

收稿日期：2023-05-04;修回日期：2023-07-04.

基金項(xiàng)目：國家自然科學(xué)基金（12361057）；貴州省數(shù)據(jù)驅(qū)動(dòng)建模學(xué)習(xí)與優(yōu)化創(chuàng)新團(tuán)隊(duì)項(xiàng)目（黔科合平臺(tái)人才［2020］5016）.

作者簡介：周婷婷（1998-），女，貴州遵義人，貴州大學(xué)碩士研究生，研究方向?yàn)橹悄軆?yōu)化算法、生物與醫(yī)學(xué)統(tǒng)計(jì)，E-mail：3075055469@qq.com.

通信作者：戴家佳（1976-），女，貴州貴陽人，貴州大學(xué)教授，博士，研究方向?yàn)樯锱c醫(yī)學(xué)統(tǒng)計(jì)、生存分析，E-mail：jjdai@gzu.edu.cn.

引用本文：周婷婷，戴家佳.基于鞅方法的雞群優(yōu)化算法收斂性分析［J］.河南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2024，52（6）：80-87.（Zhou Tingting，Dai Jiajia.Convergence analysis of chicken swarm optimization algorithm based on martingale method［J］.Journal of Henan Normal University（Natural Science Edition），2024，52（6）：80-87.DOI：10.16366/j.cnki.1000-2367.2023.05.04.0002.）

1" CSO算法

CSO算法綜合了PSO算法、DE算法的優(yōu)點(diǎn)，是通過4條規(guī)則將雞群中的等級(jí)秩序和覓食行為理想化，從而建立數(shù)學(xué)模型來求解優(yōu)化問題.本文考慮最小值優(yōu)化問題，即：min F（x），F(xiàn)（x）0.（1）

CSO算法在優(yōu)化問題的求解空間中隨機(jī)生成N只雞形成雞群x=（x1，x2，…，xN）.雞群中第i只雞在D維空間中所處的位置表示為：xi=（xi1，xi2，…，xiD）T，i=1，2，…，N.xi是優(yōu)化問題在解空間中的一個(gè)潛在解，每只雞通過適應(yīng)度函數(shù)f（xi）求出適應(yīng)度值.由于適應(yīng)度函數(shù)是定義在解空間上的任意非負(fù)實(shí)值函數(shù)，基于式（1），在解空間上定義的適應(yīng)度函數(shù)就是目標(biāo)函數(shù).

雞群中共有N只雞，其中公雞有Nr只、母雞有Nh只、小雞有Nc只、母雞媽媽有Nm只，且NmNh，Nr+Nh+Nc=N.第i只雞在第j維空間中第t次迭代的位置為xji（t）.因?yàn)椴煌N類的雞有不同的運(yùn)動(dòng)規(guī)律，故3種雞的位置更新策略也各不相同.

公雞的位置更新策略為：xji（t+1）=xji（t）×（1+R），（2）

σ2=1，fifk，exp［（fk-fi）|fi|+ε］，其他，" k=1，2，…，N且k≠i.（3）

式中：R是服從N（0，σ2）的隨機(jī)數(shù)；f為對(duì)應(yīng)x的適應(yīng)度值；ε是一個(gè)充分小的正數(shù)，用來避免式（3）中分母為0；k是所有公雞中除了i后的任一只公雞.

母雞的位置更新策略為：xji（t+1）=xji（t）+B1×V1×［xjr1（t）-xji（t）］+B2×V2×［xjr2（t）-xji（t）］，（4）

B1=exp［（fi-fr1）|fi|+ε］，（5）

B2=exp（fr2-fi）.（6）

式中：r1是與第i只母雞同在一個(gè)子群里的公雞；r2是整個(gè)雞群里的任意一只公雞或母雞，且r1≠r2；B1、B2為常數(shù)，取值范圍為（0，1）；V1、V2是服從［0，1］之間均勻分布的隨機(jī)數(shù).

小雞的位置更新策略為：xji（t+1）=xji（t）+FL×［xjm（t）-xji（t）］.（7）

式中：m是第i只小雞的母雞媽媽；FL是跟隨系數(shù)，為小雞跟著母雞媽媽覓食時(shí)母雞媽媽的位置對(duì)小雞位置的影響因子，取值范圍為（0，2）.

2" CSO算法的Markov鏈模型

Markov 鏈?zhǔn)菍?duì)隨機(jī)過程進(jìn)行分析的重要手段，指的是系統(tǒng)在任一時(shí)刻所處狀態(tài)組成的 Markov 隨機(jī)序列.下面先給出一些CSO算法的相關(guān)定義，以便建立其 Markov 鏈模型.

定義1" 在CSO算法中，雞群中每只雞覓食時(shí)所處的位置構(gòu)成了雞個(gè)體狀態(tài)，記為x，x∈C，C是可行解空間，一只雞的全部可能狀態(tài)組成了雞個(gè)體狀態(tài)空間，記為：x=｛x|x∈C｝.所有雞個(gè)體狀態(tài)就組成了雞群狀態(tài)，記為：θ=（x1，x2，…，xi），1iN.（8）

故雞群狀態(tài)空間記為：Θ=｛θ=（x1，x2，…，xN）|xi∈C，1iN｝.（9）

式中：xi為第i只雞的狀態(tài)，N為種群大小."""""""""""""""""""""""""""""""""""""""""""

定義2" 對(duì)于任意兩狀態(tài)xi∈θ，xj∈θ，CSO算法迭代過程中雞個(gè)體從狀態(tài)xi一步轉(zhuǎn)移到狀態(tài)xj，記為Tθ（xi）=xj.

定理1" CSO算法中，雞個(gè)體從狀態(tài)xi轉(zhuǎn)移到xj的一步轉(zhuǎn)移概率為：

P｛Tθ（xi）=xj｝=Pr｛Tθ（xi）=xj｝，公雞，Ph｛Tθ（xi）=xj｝，母雞，Pc｛Tθ（xi）=xj｝，小雞.（10）

證明" 過程詳見參考文獻(xiàn)［12］中的定理1.

由于CSO算法中公雞、母雞和小雞有不同的位置更新策略，故它們從狀態(tài)xi轉(zhuǎn)移到xj也有著不同的一步轉(zhuǎn)移概率.公雞的一步轉(zhuǎn)移概率為：

Pr｛Tθ（xi）=xj｝=1|xi×R|，xj∈［xi，xi+xi×R］，0，其他.（11）

母雞的一步轉(zhuǎn)移概率為：Ph｛Tθ（xi）=xj｝=1|S1×V1×（xr1-xi）+S2×V2×（xr2-xi）|，xj∈［xi，xi+S1×V1×（xr1-xi）+S2×V2×（xr2-xi）］，0，其他.（12）

小雞的一步轉(zhuǎn)移概率為：Pc｛Tθ（xi）=xj｝=1|FL×（xm-xi）|，xj∈［xi，xi+FL×（xm-xi）］，0，其他.（13）

定義3" CSO算法中對(duì)于θi∈Θ，θj∈Θ，雞群狀態(tài)θi一步轉(zhuǎn)移到θj記為TΘ（θi）=θj，則其一步轉(zhuǎn)移概率為：P｛TΘ（θi）=θj｝=∏Nk=1P｛Tθ（xik）=xjk｝.（14）

定義4（Markov鏈）［13］" 設(shè)｛Xn，n∈T｝為一列取值離散的隨機(jī)變量，參數(shù)集T為離散的時(shí)間序列，即T={0，1，2，…}，全體隨機(jī)變量Xn所對(duì)應(yīng)取值組成的離散狀態(tài)空間為I=｛i0，i1，i2，…｝.若對(duì)任意的狀態(tài)i0，i1，i2，…，in+1∈I和整數(shù)n∈T滿足如下條件概率：P｛Xn+1=in+1|X0=i0X1=i1，…，Xn=in｝=P｛Xn+1=in+1|Xn=in｝，（15）

則稱｛Xn，n∈T｝為Markov鏈.

定理2" CSO算法中的雞群狀態(tài)序列｛θ（t），t0｝是有限齊次Markov鏈.

證明" 對(duì)于θ（t）∈Θ，θ（t+1）∈Θ，根據(jù)定義3，其一步轉(zhuǎn)移概率P｛Tθ（θ（t））=θ（t+1）｝由雞群內(nèi)所有雞的轉(zhuǎn)移概率P｛Tθ（x（t））=x（t+1）｝決定.根據(jù)定理1，可知雞群內(nèi)任意雞的狀態(tài)轉(zhuǎn)移概率P｛Tθ（x（t））=x（t+1）｝僅與t時(shí)刻的狀態(tài)x（t）以及式（2）～（7）中隨機(jī)數(shù)R、V1、V2，常數(shù)B1、B2，第i只母雞有關(guān)的公雞xr1，雞群中隨機(jī)選擇的公雞或母雞個(gè)體xr2，跟隨系數(shù)FL和與小雞的母雞媽媽xm有關(guān).所以一步轉(zhuǎn)移概率P｛TΘ（θ（t））=θ（t+1）｝也僅與t時(shí)刻的狀態(tài)式（2）～（7）中的相關(guān)參數(shù)有關(guān)，而與t時(shí)刻無關(guān)，即：雞群狀態(tài)序列｛θ（t），t0｝具有Markov性；對(duì)于任何優(yōu)化算法來說，其搜索空間都是有限的，因此CSO算法中每只雞的狀態(tài)xi也都是有限的.而雞群狀態(tài)空間Θ又由N只雞的狀態(tài)共同組成，故Θ也是有限的；再根據(jù)定理1可知，狀態(tài)轉(zhuǎn)移概率P｛Tθ（x（t））=x（t+1）｝僅與時(shí)刻的狀態(tài)x（t）有關(guān)，而與t時(shí)刻無關(guān).故雞群狀態(tài)序列｛θ（t），t0｝是有限齊次Markov鏈.證畢.

3" CSO算法的全局收斂性分析

3.1" 基礎(chǔ)理論

定義5［14］" 若G=｛x*|x∈Θ，f（x*）f（x）｝為雞群狀態(tài)序列｛θ（t），t0｝的全局最優(yōu)狀態(tài)集，如果limt→∞" P｛［θ（t）∩G≠］｝=1（limt→∞" P｛［θ（t）G］｝=1），則稱雞群狀態(tài)序列｛θ（t），t0｝依概率弱（強(qiáng)）收斂到全局最優(yōu)狀態(tài)集G；如果P｛limt→∞［θ（t）∩G≠］｝=1（P｛limt→∞［θ（t）G］｝=1），則稱序列｛θ（t），t0｝幾乎處處弱（強(qiáng)）收斂到全局最優(yōu)狀態(tài)集G.

定理3" 雞群狀態(tài)序列｛θ（t），t0｝的4種收斂性有如下關(guān)系：（1）幾乎處處強(qiáng)收斂幾乎處處弱收斂依概率弱收斂；（2）幾乎處處強(qiáng)收斂依概率強(qiáng)收斂依概率弱收斂.

證明" 由［θ（t）G］［θ（t）∩G≠］可知，P｛［θ（t）G］｝P｛［θ（t）∩G≠］｝，所以依概率強(qiáng)收斂可推出依概率弱收斂，幾乎處處強(qiáng)收斂可推出幾乎處處弱收斂.又因limt→∞［θ（t）∩G≠］=∪∞t=1∩∞k=t［θ（t）∩G≠］，由概率的單調(diào)性可得：P｛limt→∞［θ（t）∩G≠］｝=limt→∞" P｛［∩∞k=tθ（t）∩G≠］｝limt→∞" P｛［θ（t）∩G≠］｝.所以幾乎處處弱收斂可推出依概率弱收斂.同理可得，幾乎處處強(qiáng)收斂可推出依概率強(qiáng)收斂.證畢.

定義6［15］" 如果對(duì)i∈E，有∑j∈Epij=1，稱狀態(tài)空間E為閉集.

定義7［15］" 如果閉集E有真閉子集，則稱E為可約的，反之稱E不可約.

命題1" 雞群狀態(tài)空間Θ是一個(gè)閉集.

證明" 根據(jù)定理2，雞群狀態(tài)序列｛θ（t），t0｝是有限齊次Markov鏈，故有i∈Θ，∑j∈ΘPij=1.根據(jù)定義6，可知Θ是一個(gè)閉集.證畢.

命題2" 在CSO算法中，全局最優(yōu)狀態(tài)集G是狀態(tài)空間Θ上的一個(gè)真閉子集.

證明" 首先，當(dāng)G=Θ時(shí)，Θ中的每一個(gè)解都是最優(yōu)解，優(yōu)化問題沒有討論意義，故本文是基于GΘ來討論優(yōu)化問題.其次，對(duì)于θi∈G，θj≠G，θj∈Θ.由定義3可知，TΘ（θi）=θj的轉(zhuǎn)移概率為：P｛TΘ（θi）=θj｝=∏Nn=1P｛Tθ（xin）=xjn｝.若在G中至少有1只雞的狀態(tài)達(dá)到了最優(yōu)，令x*～xi0n為最優(yōu)狀態(tài)，那么有xi0n∈G，使得P｛Tθ（xi0n）=xj0n｝=0，此時(shí)P｛TΘ（θi）=θj｝=0.故G是Θ上的一個(gè)真閉子集.證畢.

命題3" 雞群狀態(tài)空間Θ是可約的.

證明" 首先從命題1可以知道整個(gè)雞群狀態(tài)空間Θ是一個(gè)最大的閉集.其次由命題2可知，雞群的全局最優(yōu)狀態(tài)集G是狀態(tài)空間Θ上的一個(gè)真閉子集.最后由定義7可知雞群狀態(tài)空間Θ是可約的.證畢.

3.2" CSO算法的幾乎處處強(qiáng)收斂性分析

由于利用群智能算法求解優(yōu)化問題的過程是一個(gè)迭代尋優(yōu)的過程，所以可把它轉(zhuǎn)換成一類收斂問題，利用鞅的收斂定理對(duì)其過程進(jìn)行理論分析.本文考慮的是目標(biāo)函數(shù)為最小值的情況，即所求雞群的適應(yīng)度值越小越好，故只有找到全局最小適應(yīng)度值時(shí)，才能得到全局最優(yōu)狀態(tài)集（全局最優(yōu)解）.假若雞群在第t次迭代時(shí)得到的最佳個(gè)體適應(yīng)度值達(dá)到全局最優(yōu)狀態(tài)集所對(duì)應(yīng)的最小適應(yīng)度值f（θ*），即：f（θt）=f（θ*），那么在第t次迭代之后的任何一次迭代中雞群的最佳個(gè)體的適應(yīng)度值都不會(huì)大于全局最優(yōu)解所對(duì)應(yīng)的最小適應(yīng)度值f（θ*），即下一次迭代時(shí)雞群的最小適應(yīng)度值關(guān)于當(dāng)前迭代雞群的條件期望不大于當(dāng)前迭代雞群的最小適應(yīng)度值.因此可把雞群的最小適應(yīng)度函數(shù)f（θt）轉(zhuǎn)變?yōu)橐粋€(gè)上鞅，將研究雞群狀態(tài)序列｛θ（t），t0｝的收斂性轉(zhuǎn)化為研究f（θt）的收斂性.根據(jù)定理3可以知道，幾乎處處強(qiáng)收斂是強(qiáng)于依概率收斂的，故接下來本文將通過利用上鞅的性質(zhì)和上鞅收斂定理來證明CSO算法的幾乎處處強(qiáng)收斂性.

定義8［15］" 如果隨機(jī)過程｛Yk，k0｝與｛Xk，k0｝滿足以下條件：（1）E（|Yk|）＜∞；（2）E（Yk+1|X0，X1，…，Xk）Yk（或E（Yk+1|X0，X1，…，Xk）Yk）；（3）Yk是X0，X1，…，Xk的函數(shù)；則稱隨機(jī)過程｛Yk，k0｝是關(guān)于｛Xk，k0｝的上鞅（或下鞅）.

引理1（下鞅收斂定理）［15］" 若隨機(jī)過程｛Yk，k0｝是一個(gè)下鞅，且滿足sup E|Yk|＜∞，則一定存在一個(gè)隨機(jī)變量Y*∈｛Yk，k0｝使得E|Y*|＜∞，且｛Yk，k0｝以概率1收斂至Y*，即：P｛limt→∞" Yk=Y*｝=1.

引理2［15］" 引理1的結(jié)論對(duì)上鞅也成立.

定理4" 隨機(jī)過程｛f（θt），t0｝關(guān)于｛θt，t0｝是一個(gè)非負(fù)有界上鞅函數(shù)列，即對(duì)任意t0，則有E［f（θt+1）|θ0，θ1，…，θt］f（θt）.

證明" 由于適應(yīng)度函數(shù)是定義在解空間上的任意非負(fù)實(shí)值函數(shù)，故f（θt）0.又因CSO算法保證了下一次迭代時(shí)雞群的最小適應(yīng)度值不會(huì)大于當(dāng)前迭代雞群的最小適應(yīng)度值，所以可以得到：f（θt+1）f（θt）f（θt-1），所以｛f（θt），t0｝是非負(fù)有界的.再根據(jù)定理2的馬爾可夫性可得：E［f（θt+1）|θ0，θ1，…，θt］=E［f（θt+1）|θt］.（16）

因此只需證明對(duì)任意x∈Θ有：E［f（θt+1）|θt=x］f（x），（17）

根據(jù)式（17）和隨機(jī)過程的相關(guān)理論知識(shí)，式（17）不等號(hào)左邊可以轉(zhuǎn)化為：E［f（θt+1）|θt=x］=∑y∈Θf（y）P（θt+1=y|θt=x），（18）

因此需要證明的式（17）就轉(zhuǎn)化成：∑y∈Θf（y）P（θt+1=y|θt=x）f（x）.（19）

由于任意群狀態(tài)x之后的群狀態(tài)都存在：f（θt+1=y）f（θt=x），y∈Θ，可得：∑y∈Θf（y）P（θt+1=y|θt=x）∑y∈Θf（x）P（θt+1=y|θt=x）f（x）∑y∈ΘP（θt+1=y|θt=x）f（x）.（20）

由于Θ是一個(gè)閉集，故∑y∈ΘP（θt+1=y|θt=x）=1，所以式（20）成立.綜上，可以證得隨機(jī)過程｛f（θt），t0｝關(guān)于｛θt，t0｝是一個(gè)非負(fù)有界上鞅函數(shù)列.證畢.

定理5" 如果非負(fù)有界上鞅函數(shù)列｛f（θt），t0｝滿足sup E|f（θt）|＜∞，那么當(dāng)t→∞時(shí)，一定存在一個(gè)群狀態(tài)隨機(jī)變量θ*∈｛θt，t0｝使得雞群狀態(tài)序列｛θt，t0｝收斂，即P｛limt→∞" θt=θ*｝=1.

證明" 由于優(yōu)化問題的全局最小適應(yīng)度值f（θ*）存在（否則優(yōu)化問題無意義），則有：f（θ*）f（θt）＜∞，根據(jù)數(shù)學(xué)期望的性質(zhì)有：E［f（θ*）］E［f（θt）］＜∞，所以sup E|f（θt）|＜∞.又根據(jù)引理2，當(dāng)t→∞時(shí)，一定存在f（θ*）∈｛f（θt），t0｝，使得｛f（θt），t0｝以概率1收斂到f（θ*）.相應(yīng)地，當(dāng)t→∞時(shí)，存在θ*∈｛θt，t0｝，使得｛θt，t0｝以概率1收斂到θ*，即P｛limt→∞" θt=θ*｝=1.證畢.

由定理5中可知，若θ*的取值是在全局最優(yōu)狀態(tài)集G中，則CSO算法將幾乎處處強(qiáng)收斂至全局最優(yōu).因此在定理4和定理5的條件下，記P*t=min P（θt+1|θt）為CSO算法從狀態(tài)θt轉(zhuǎn)移到θt+1的最小轉(zhuǎn)移概率，從而引出要證的定理6.

定理6" 當(dāng)∑∞t=1P*t=∞時(shí)，P｛limt→∞（θtG）｝=1，即CSO算法以概率1幾乎處處強(qiáng)收斂到全局最優(yōu).

證明" 令Mt=｛θt∩G=|θt=a，t0｝=｛f（θt）≠f（θ*）｝，Nt=｛θt+1∩G≠|(zhì)θt+1=b，t0｝=｛f（θt）=f（θ*）｝.再令β=min｛|f（a）-f（b）|f（a）≠f（b）｝，則存在一個(gè)正實(shí)數(shù)λ，使得f（a）-f（b）λβ.由條件期望的性質(zhì)可得：

E［f（θt）］-E［f（θt+1）］=E［f（θt）］-E｛E［f（θt+1|θt）］｝=∑a∈ΘP（θt=a）｛f（θt）-

E［f（θt+1|θt=a）］｝=∑a∈ΘP（θt=a）∑b∈ΘP（b|a）［f（a）-f（b）］.

根據(jù)P*t=min P（θt+1|θt），t0與以下兩個(gè)不等式：∑a∈ΘP（b|a）P（b|a），∑a∈ΘP（θt=a）∑a∩G=P（θt=a），代入可得：E［f（θt）］-E［f（θt+1）］∑a∈ΘP（θt=a）∑b∈ΘP（b|a）λβ∑a∈ΘP（θt=a）P（b|a）λβ∑a∈ΘP（θt=a）λβP*t∑a∩G=P（θt=a）λβP*tλβP*tP（Mt），對(duì)上式中的t從1到N求和可得：E［f（θ1）］E［f（θ1）］-E［f（θN+1）］λβ∑Nt=1P（Mt）P*t，當(dāng)N→∞時(shí)，可得∑∞t=1P（Mt）P*t＜∞.當(dāng)∑∞t=1P*t=∞時(shí)，P（Mt）→0，有P｛limt→∞ f（θt）≠f（θ*），t0｝=0或P｛limt→∞ f（θt）=f（θ*），t0｝=1，即：P｛limt→∞ θt∩G=|θt=a，t0｝=0或P｛limt→∞ θtG|θt=a，t0｝=1.當(dāng)t→∞時(shí)，雞群狀態(tài)序列｛θt，t0｝收斂至群狀態(tài)隨機(jī)變量θ*.此外，θ*∈｛θt，t0｝且θ*的取值在全局最優(yōu)狀態(tài)集G中.即：當(dāng)∑∞t=1P*t=∞時(shí)，CSO算法幾乎處處強(qiáng)收斂到全局最優(yōu).證畢.

3.3" CSO算法的一致收斂性分析

定義9（一致收斂）［16］" 設(shè)在同一個(gè)可測集F上有函數(shù)列｛fn（x），n∈N｝和函數(shù)f（x），ε＞0，N（ε）＞0，使得當(dāng)nN（ε）時(shí)，對(duì)x∈F，都有|fn（x）-f（x）|＜ε，則稱在F上有函數(shù)列｛fn（x）｝一致收斂于f（x）.

引理3（Egoroff定理）［16］" 若μ（A）＜∞，｛fn（x），n∈N｝是可測集A上幾乎處處有限并可測的函數(shù)列，它在A上幾乎處處收斂于函數(shù)f（x），即：limn→∞ fn（x）=f（x）.則對(duì)每個(gè)ε＞0，存在可測集AcA，使得在Ac上函數(shù)列｛fn（x），n∈N｝一致收斂至函數(shù)f（x）.

定理7" 函數(shù)列｛f（θt），t0｝一致收斂于函數(shù)f（θ*）.

證明" 因雞群狀態(tài)空間Θ是有限的，故|Θ|中僅包含有限個(gè)不同的點(diǎn).又因｛f（θt），t0｝是非負(fù)有界上鞅，所以其極限幾乎處處存在且是有界的.由定理5可知，limt→∞ f（θt）=f（θ*），因此根據(jù)引理3可推出函數(shù)列｛f（θt），t0｝具有一致收斂性，即對(duì)ε＞0，N（ε）＞0，使得當(dāng)tN（ε）時(shí)，對(duì)θ∈G，GΘ，有|f（θt）-f（θ*）|＜ε.所以，函數(shù)列｛f（θt），t0｝一致收斂于函數(shù)f（θ*），由此可推出θt（ε）G.也就是說，能確保在有限步數(shù)N（ε）內(nèi)，CSO算法以概率1收斂到全局最優(yōu).一致收斂性具有“有限終止”的特點(diǎn)，因此它是強(qiáng)于幾乎處處強(qiáng)收斂性的.證畢.

4" CSO算法的實(shí)驗(yàn)與分析

為了驗(yàn)證本文理論證明的正確性及比較各算法的收斂性能和特點(diǎn)，本節(jié)決定對(duì)DE算法、PSO算法和CSO算法進(jìn)行仿真實(shí)驗(yàn)，即：選取具有不同特征的16個(gè)標(biāo)準(zhǔn)測試函數(shù)，再利用DE、PSO和CSO分別對(duì)它們進(jìn)行重復(fù)30次的尋優(yōu)計(jì)算，再從平均值、標(biāo)準(zhǔn)差、平均耗時(shí)3個(gè)方面來進(jìn)行算法間的比較.其中，算法的收斂精度和尋優(yōu)能力體現(xiàn)在平均值上，算法抗局部極值的能力和穩(wěn)定性體現(xiàn)在標(biāo)準(zhǔn)差上，算法的快速性體現(xiàn)在平均耗時(shí)上.在16個(gè)標(biāo)準(zhǔn)測試函數(shù)中，F(xiàn)1～F4是單峰函數(shù)，分別是Sphere，Schwefel's 2.22，Rosenbrock，Quartic，且最優(yōu)值都為0.單峰函數(shù)能很好地測試算法的收斂精度和尋優(yōu)能力；F5～F10是多峰函數(shù)，分別是Rastrigin，Griewank，Beale，Schaffer，Kowalik，Branin，且Rastrigin，Griewank，Beale，Schaffer的最優(yōu)值為0，Kowalik和Branin的最優(yōu)值分別為0.000 3和0.398 0.多峰函數(shù)能很好地展現(xiàn)算法的全局搜索能力以及避免局部最優(yōu)的能力；F11～F16是固定維多峰函數(shù)，分別是2維的Shekel's Foxholes，Drop-Wave，Three-hump Camel，Levy N.13，4維的Styblinski-Tang和6維的Powell，且Shekel's Foxholes的最優(yōu)值為1，Drop-Wave的最優(yōu)值為-1，Three-hump Camel，Levy N.13和 Powell的最優(yōu)值為0，Styblinski-Tang的最優(yōu)值為-156.664 0.固定維多峰函數(shù)能很好地衡量算法在低維時(shí)的全局搜索能力.

此外，為了方便對(duì)算法進(jìn)行比較，決定把3個(gè)算法的通用參數(shù)設(shè)置一樣，固定維度除外，即：最大迭代次數(shù)M=1 000，種群大小N=30，維度D=30.3個(gè)算法的其他參數(shù)設(shè)置如下，CSO算法：Nr=0.2N，Nh=0.6N，Nm=0.1Nh，Nc=N-Nr-Nh，G=10，F(xiàn)L∈［0.5，0.9］;PSO算法：c1=c2=2，w=0.75;DE算法：F=0.5，CR=0.3，Xmin=-30，Xmax=30.在仿真實(shí)驗(yàn)中，若實(shí)驗(yàn)運(yùn)行結(jié)果與函數(shù)的最優(yōu)值相差小于10-8，就認(rèn)為尋優(yōu)成功.表1為實(shí)驗(yàn)運(yùn)行得到的最終結(jié)果，并用粗體來標(biāo)出每個(gè)測試函數(shù)中平均值、標(biāo)準(zhǔn)差、平均耗時(shí)的最優(yōu)值.

在表1中，CSO算法在函數(shù)F1，F(xiàn)2，F(xiàn)7，F(xiàn)8，F(xiàn)10，F(xiàn)12，F(xiàn)13，F(xiàn)14和F16上都找到了它們的全局最小值，這表明CSO算法在有限的迭代次數(shù)內(nèi)可以收斂到問題的全局最優(yōu)，從而驗(yàn)證本文定理7中所得到的結(jié)論.從收斂精度和尋優(yōu)能力來看，與其他兩種算法相比，CSO算法在F1，F(xiàn)2，F(xiàn)3，F(xiàn)4，F(xiàn)5，F(xiàn)7，F(xiàn)8，F(xiàn)10，F(xiàn)12，F(xiàn)13，F(xiàn)14上收斂精度最高，尋優(yōu)能力最強(qiáng).雖然DE算法的收斂精度和尋優(yōu)能力在函數(shù)F6，F(xiàn)9，F(xiàn)11，F(xiàn)15和F16上是最高的，但CSO算法所得到的結(jié)果僅次于它.從對(duì)抗局部極值的能力和算法的穩(wěn)定性來看，相較于PSO算法和DE算法，CSO算法在函數(shù)F1，F(xiàn)2，F(xiàn)3，F(xiàn)4，F(xiàn)5，F(xiàn)7，F(xiàn)8，F(xiàn)12，F(xiàn)13，F(xiàn)14上抗局部極值能力較強(qiáng)，穩(wěn)定性較好.而在F6，F(xiàn)9，F(xiàn)10，F(xiàn)11，F(xiàn)15和F16上，CSO算法的抗局部極值能力和穩(wěn)定性稍差一點(diǎn)，在3種算法中居于第2.對(duì)于所有的標(biāo)準(zhǔn)測試函數(shù)，從平均耗時(shí)上看，PSO 算法平均耗時(shí)最短，CSO 算法的平均耗時(shí)要稍大于DE 算法的平均耗時(shí).總的來說，CSO算法的收斂性能要好于DE算法和PSO算法，同時(shí)還有著較好的抗局部極值能力和穩(wěn)定性.雖然在計(jì)算時(shí)間上要稍弱于其他算法，但是對(duì)于計(jì)算時(shí)間要求不是特別高的優(yōu)化問題，CSO 算法比其他兩種算法明顯在應(yīng)用上更具有優(yōu)勢(shì).

5" 結(jié)" 論

本文在CSO算法Markov鏈模型的基礎(chǔ)上，通過一系列的定義、定理把具有最小適應(yīng)度值的雞群狀態(tài)序列轉(zhuǎn)化成一個(gè)上鞅，利用鞅方法證明了CSO算法的幾乎處處強(qiáng)收斂性，進(jìn)一步也證明了CSO算法的一致收斂性.此外，仿真實(shí)驗(yàn)也成功驗(yàn)證了本文理論證明的正確性并體現(xiàn)出了CSO算法的特點(diǎn).與現(xiàn)有的結(jié)論相比，得到了CSO算法更強(qiáng)的收斂性證明結(jié)果，這將對(duì)未來CSO算法的改進(jìn)和應(yīng)用提供更多的理論基礎(chǔ).下一步將對(duì)CSO算法的改進(jìn)優(yōu)化進(jìn)行研究，并利用鞅方法對(duì)改進(jìn)的CSO算法進(jìn)行更深入的收斂性理論分析.

參" 考" 文" 獻(xiàn)

［1］ ""MENG X B，LIU Y，GAO X Z，et al.A new bio-inspired algorithm：chicken swarm optimization［C］// International Conference in Swarm Intelligence.Cham：Springer，2014：86-94.

［2］李冰曉，萬睿之，朱永杰，等.基于種群分區(qū)的多策略綜合粒子群優(yōu)化算法［J］.河南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2022，50（3）：85-94.

LI B X，WAN R Z，ZHU Y J，et al.Multi-strategy comprehensive article swarm optimization algorithm based on population partition［J］.Journal of Henan Normal University（Natural Science Edition），2022，50（3）：85-94.

［3］方景遠(yuǎn)，季益勝，趙新超.基于高斯分布估計(jì)的對(duì)位差分進(jìn)化算法［J］.河南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2021，49（3）：27-32.

FANG J Y，JI Y S，ZHAO X C.Opposition-based differential evolution algorithm with Gaussian distribution estimation［J］.Journal of Henan Normal University（Natural Science Edition），2021，49（3）：27-32.

［4］郭堃，薛太林，耿杰，等.基于改進(jìn)雞群算法的無功優(yōu)化綜合分析［J］.電氣自動(dòng)化，2021，43（6）：36-38.

GUO K，XUE T L，GENG J，et al.Comprehensive analysis of reactive power OptimizationBased on improved chicken population algorithm［J］.Electrical Automation，2021，43（6）：36-38.

［5］寇德昌.改進(jìn)的雞群算法及其應(yīng)用［D］.北京：北京建筑大學(xué)，2021.

［6］王英聰，劉馳，王延峰.基于刺激-響應(yīng)機(jī)制的改進(jìn)雞群算法［J］.控制與決策，2023，38（1）：58-66.

WANG Y C，LIU C，WANG Y F.Chicken swarm optimization algorithm based on stimulus-response mechanism［J］.Control and Decision，2023，38（1）：58-66.

［7］楊菊蜻，張達(dá)敏，張慕雪，等.一種混合改進(jìn)的雞群優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用研究，2018，35（11）：3290-3293.

YANG J Q，ZHANG D M，ZHANG M X，et al.Hybrid improved for chicken swarm optimization algorithm［J］.Application Research of Computers，2018，35（11）：3290-3293.

［8］李春紅，陸安江，邵麗萍.基于線性遞減權(quán)值更新的雞群算法［J］.智能計(jì)算機(jī)與應(yīng)用，2020，10（2）：43-47.

LI C H，LU A J，SHAO L P.Rooster algorithm based on linear decrement weight update［J］.Intelligent Computer and Applications，2020，10（2）：43-47.

［9］尚俊娜，程濤，岳克強(qiáng)，等.蝙蝠算法的Markov鏈模型分析［J］.計(jì)算機(jī)工程，2017，43（7）：198-202.

SHANG J N，CHENG T，YUE K Q，et al.Markov chain model analysis of bat algorithm［J］.Computer Engineering，2017，43（7）：198-202.

［10］張孟健，龍道銀，王霄，等.基于馬爾科夫鏈的灰狼優(yōu)化算法收斂性研究［J］.電子學(xué)報(bào)，2020，48（8）：1587-1595.

ZHANG M J，LONG D Y，WANG X，et al.Research on convergence of grey wolf optimization algorithm based on Markov chain［J］.Acta Electronica Sinica，2020，48（8）：1587-1595.

［11］張大力，夏紅偉，張朝興，等.改進(jìn)螢火蟲算法及其收斂性分析［J］.系統(tǒng)工程與電子技術(shù)，2022，44（4）：1291-1300.

ZHANG D L，XIA H W，ZHANG C X，et al.Improved firefly algorithm and its convergence analysis［J］.Systems Engineering and Electronics，2022，44（4）：1291-1300.

［12］吳定會(huì)，孔飛，紀(jì)志成.雞群算法的收斂性分析［J］.中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，48（8）：2105-2112.

WU D H，KONG F，JI Z C.Convergence analysis of chicken swarm optimization algorithm［J］.Journal of Central South University（Science and Technology），2017，48（8）：2105-2112.

［13］錢偉民，梁漢營，楊國慶.應(yīng)用隨機(jī)過程［M］.北京：高等教育出版社，2014.

［14］張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)［M］.西安：西安交通大學(xué)出版社，2000.

［15］LAWLER G F.Introduction to stochastic processes［M］.2nd ed.London：CRC Press，2006.

［16］程其襄，張奠宙，魏國強(qiáng)，等.實(shí)變函數(shù)與泛函分析基礎(chǔ)［M］.2版.北京：高等教育出版社，2003.

Convergence analysis of chicken swarm optimization algorithm based on martingale method

Zhou Tingting， Dai Jiajia

（School of Mathematics and Statistics， Guizhou University， Guiyang 550025， China）

Abstract： The most convergence analysis on chicken swarm optimization（CSO） algorithm belonged to weak convergence， and it cannot infer in general that the CSO algorithm would be convergent to a global optimum in a finite number of evolution steps. In order to make up for this deficiency， a martingale method was proposed to study the global convergence of CSO algorithm. Firstly， based on relevant definitions of CSO algorithm， the Markov chain model of CSO algorithm was established， and its Markov properties were analyzed. Secondly， the chicken swarm state sequence with the minimum fitness value was transformed into a supermartingale. By using the supermartingale convergence theorem and the Egoroff's theorem， it was proved that the CSO algorithm had almost surely strong convergence and uniform convergence. Furthermore， it was concluded that the CSO algorithm can surely convergence to a global optimum in a finite number of evolution steps when the chicken swarm state space was finite. Finally， the validity of the theoretical proofs were verified successfully in the simulation experiment， and it was found that the CSO algorithm had stronger ability to search for excellence and higher convergence accuracy than PSO algorithm and DE algorithm.

Keywords： chicken swarm optimization（CSO） algorithm; Markov chain; supermartingale convergence theorem;Egoroff's theorem; almost sure strong convergence; uniform convergence

［責(zé)任編校" 陳留院" 趙曉華］